EFFICIENT PRIORITY-FIRST SEARCH MAXIMUM-LIKELIHOOD SOFT-DECISION DECODING OF LINEAR BLOCK-CODES

In this paper we 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. Simulation results for the (104, 52) binary extended quadratic residue code are also given.