Recursive maximum-likelihood decoding algorithm for binary linear block codes

Shu Wen Lin, M.P.C. Fossorier

Tadao Kasami

W. Stieritz, Jack K. Wolf

Yunghsiang Sam Han, Hung-Ta Pai, Po‐Ning Chen +1 more

Based on the notion of supercodes, we propose a two-phase maximum-likelihood soft-decision decoding (tpMLSD) algorithm for binary linear block codes in this work. The first phase applies the Viterbi algorithm backwardly to a trellis derived from the parity-check matrix of the supercode of the linear block code. Using the information retained from the first phase, the second phase employs the priority-first search algorithm to the trellis corresponding to the linear block code itself, which guarantees finding the ML decision. Simulations on Reed-Muller codes show that the proposed two-phase scheme is an order of magnitude more efficient in average decoding complexity than the recursive maximum-likelihood decoding (RMLD) [1] when the signal-to-noise ratio per information bit is 4.5 dB.

Yingtao Zhou, Yuichi Kaji

The maximum likelihood (ML) decoding is essential for error-correcting codes, but the ML decoding problem is NP-hard in general. This suggests that there is no single universal ML decoding algorithm that works efficiently for an arbitrary code. Therefore researchers developed many ML decoding algorithms with different characteristics so that they can be used complementary. This study is intended to propose an ML decoding algorithm that can be used for general non-binary linear codes. The algorithm proposed in this paper is a generalization of the adaptive and recursive ML decoding algorithm that was studied for binary codes. This paper shows that the structure and properties of linear codes that helped realizing the decoding algorithm for binary codes can be generalized to nonbinary cases, and reports the implementation results of the soft-decision ML decoding alogorithm for several non-binary linear codes.

Hitoshi Tokushige