A low-weight trellis-based iterative soft-decision decoding algorithm for binary linear block codes

This paper presents a new low-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. The algorithm is devised based on a set of optimality conditions and the generation of a sequence of candidate codewords for an optimality test. The initial candidate codeword is generated by a simple decoding method. The subsequent candidate codewor ds, if needed, are generated by a chain of low-weight trellis searches, one at a time. Each search is conducted through a low-weight trellis diagram c entered around the latest candidate codeword and results in an improvement over the previous candidate codewords that have been already tested. This i mprovement is then used as the next candidate codeword for a test of optima lity. The decoding iteration stops whenever a candidate codeword is found t o satisfy a sufficient condition on optimality or the latest low-weight tre llis search results in a repetition of a previously generated candidate cod eword. A divide-and-conquer technique is also presented for codes that are not spanned by their minimum-weight codewords. The proposed decoding algori thm has been applied to some well-known codes of lengths 48, 64, and 128. S imulation results show that the proposed algorithm achieves either practica lly optimal error performance for the example codes of length 48 and 64 or near optimal error performance for the (128, 29, 32) RM code with a signifi cant reduction in computational decoding complexity.