Maximum Likelihood Decoding for Linear Block Codes Using Grobner Bases

Daisuke IKEGAMI  Yuichi KAJI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A   No.3   pp.643-651
Publication Date: 2003/03/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Engineering Acoustics
maximum likelihood decoding,  Grobner basis,  soft-decision decoding,  hard-decision decoding,  

Full Text: PDF(298KB)>>
Buy this Article

New algorithms for the soft-decision and the hard-decision maximum likelihood decoding (MLD) for binary linear block codes are proposed. It has been widely known that both MLD can be regarded as an integer programming with binary arithmetic conditions. Recently, Conti and Traverso have proposed an efficient algorithm which uses Grobner bases to solve integer programming with ordinary integer arithmetic conditions. In this paper, the Conti-Traverso algorithm is extended to solve integer programming with modulo arithmetic conditions. We also show how to transform the soft-decision and the hard-decision MLD to integer programming for which the extended Conti-Traverso algorithm is applicable.