Fast Algorithm for Generating Candidate Codewords in Reliability-Based Maximum Likelihood Decoding

Hideki YAGI  Toshiyasu MATSUSHIMA  Shigeichi HIRASAWA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.10   pp.2676-2683
Publication Date: 2006/10/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.10.2676
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Information Theory and Its Applications)
Category: Coding Theory
maximum likelihood decoding,  binary block codes,  priority-first search,  most reliable basis,  reliability,  

Full Text: PDF>>
Buy this Article

We consider the reliability-based heuristic search methods for maximum likelihood decoding, which generate test error patterns (or, equivalently, candidate codewords) according to their heuristic values. Some studies have proposed methods for reducing the space complexity of these algorithms, which is crucially large for long block codes at medium to low signal to noise ratios of the channel. In this paper, we propose a new method for reducing the time complexity of generating candidate codewords by storing some already generated candidate codewords. Simulation results show that the increase of memory size is small.