Soft-Decision Decoding for Linear Codes : The Quest to Maximum Likelihood Decoding

W. Stieritz, Jack K. Wolf

P.A.H. Bours, N.J.C. Lous, Henk C. A. van Tilborg

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.

Y.S. Han

In this paper we present a new method to convert the maximum-likelihood soft-decision problem for linear block codes into a graph search problem. The cost assigned to every arc in the graph is based on a generalization of the Wagner rule which is an equivalent form of the maximum-likelihood decoding rule used previously by the author (1993). We also show that the arc costs assigned will carry more 'information' than the one previously defined.

Tadao Kasami

Hitoshi Tokushige