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.
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.
The authors present a novel and efficient maximum-likelihood soft-decision decoding algorithm for linear block codes. The approach used here converts the decoding problem into a search problem through a graph that is a trellis for an equivalent code of the transmitted code. A generalized Dijkstra's algorithm, which uses a priority-first search strategy, is employed to search through this graph. This search is guided by an evaluation function f defined to take advantage of the information provided by the received vector and the inherent properties of the transmitted code. This function f is used to reduce drastically the search space and to make the decoding efforts of this decoding algorithm adaptable to the noise level. For example, for most real channels of the 35 000 samples tried, simulation results for the (128,64) binary extended BCH code show that the proposed decoding algorithm is fifteen orders of magnitude more efficient in time and in space than that proposed by Wolf (1978). Simulation results for the (104, 52) binary extended quadratic residue code are also given.>
This dissertation deals with maximum-likelihood soft-decision decoding as well as suboptimal soft-decision decoding of linear block codes. We present three new decoding algorithms: $MA\sp*D,\ H\sp*,$ and Directed Search. The first algorithm, $MA\sp*D,$ is an instance of Algorithm $A\sp*$ that conducts heuristic search through a code tree of the transmitted code when the decoding problem is transformed into a problem of graph-search through a code tree. $MA\sp*D$ takes into consideration more properties of the code and is considerably more efficient than the original $A\sp*$ decoding algorithm presented by Han, Hartmann, and Chen in 1993. The second algorithm, $H\sp*,$ is a new decoding algorithm that determines the value of every component of a minimum-cost codeword by estimating the cost of the minimum-cost codeword, which has a fixed value at one of the k most reliable, linearly independent bit positions. The suboptimal version of this algorithm is combined with other decoding algorithms to reduce the search space during the decoding process. The third algorithm, Directed Search, is designed to enhance the performance of soft-decision decoding by searching in continuous space. This approach explores the search space between a given vector and the received vector and finds the codeword closest to the received vector in the space explored. We also present a novel and efficient hybrid decoding algorithm for (n, k) linear block codes. It hybridizes $MA\sp*D,\ H\sp*,$ and Directed Search algorithms, utilizing their strengths to make the decoding more efficient. Simulation results for this hybrid algorithm are presented for the (104,52) binary-extended quadratic residue code and for the (128,64), the (256, 131), and the (256, 139) binary-extended BCH codes. This hybrid algorithm can efficiently decode the (104,52) binary extended quadratic residue code and the (128,64) code for any signal-to-noise ratio and has near-optimal to optimal performance. Previously, no practical decoder could decode these two codes with such a performance for all signal-to-noise ratio ranges.
Maximum-likelihood soft-decision decoding of linear block codes is addressed. A binary multiple-check generalization of the Wagner rule is presented, and two methods for its implementation, one of which resembles the suboptimal Forney-Chase algorithms, are described. Besides efficient soft decoding of small codes, the generalized rule enables utilization of subspaces of a wide variety, thereby yielding maximum-likelihood decoders with substantially reduced computational complexity for some larger binary codes. More sophisticated choice and exploitation of the structure of both a subspace and the coset representatives are demonstrated for the (24, 12) Golay code, yielding a computational gain factor of about 2 with respect to previous methods. A ternary single-check version of the Wagner rule is applied for efficient soft decoding of the (12, 6) ternary Golay code.>
The maximum-likelihood decoding of linear block codes by Wagner rule decoding is discussed. In this approach, the Wagner rule decoding, which has been primarily applied to single parity check codes, is employed on acyclic Tanner graphs. Accordingly, a coset decoding equipped with Wagner rule decoding is applied to the decoding of a code C having a Tanner graph with cycles. A subcode C1 of C with acyclic Tanner graph is chosen as the base subcode. All cosets of C1 have the same Tanner graph and are distinguished by their values of parity nodes in the graph. The acyclic Tanner graph of C1, together with a trellis representation of the space of the parity sequences, represent the code C. This graphical representation provides a unified and systematic approach to search for an efficient method for the maximum-likelihood decoding of a given linear block code. It is shown that the proposed method covers the most efficient techniques known for the decoding of some important block codes, including the hexacode H6, extended Golay codes, Reed–Muller codes, Hamming code and (32, 16, 8) quadratic residue codes. The generalisation to the decoding of lattices is briefly explained.
An efficient maximum-likelihood soft-decision decoding algorithm for linear block codes using a generalized Dijkstra's algorithm was proposed by Han, Hartmann, and Chen (1993). We prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10/sup -3/ by finding an upper bound of the computational effort of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code, and within 0.5 dB of the optimal performance for the (128, 64) binary BCH code, respectively.