block codes, decoding, Dijkstra's algorithm, maximum-likelihood, priority-first search, soft-decision, trellis, performance analysis, suboptimal
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. In this report we prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10-3 by finding an upper bound of the computation performance of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB and 0.5 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code and the (128, 64) binary extended BCH code, respectively.
Han, Yunghsiang S.; Hartmann, Carlos R.P.; and Mehrotra, Kishan, "Decoding Linear Block Codes Using a Priority-First Search: Performance Analysis and Suboptimal Version" (1994). Electrical Engineering and Computer Science Technical Reports. 155.