DECODING LINEAR BLOCK-CODES USING A PRIORITY-FIRST SEARCH - PERFORMANCE ANALYSIS AND SUBOPTIMAL VERSION

An efficient maximum-likelihood soft-decision decoding algorithm for l inear block codes using a generalized Dijkstra's algorithm was propose d by Han, Hartmann, and Chen. In this correspondence we prove that thi s algorithm is efficient for most practical communication systems wher e the probability of error is less than 10(-3) by finding an upper bou nd of the computational effort of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decodi ng algorithm is within 0.25 dB of the performance of an optimal decodi ng 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.