List Viterbi decoding algorithms with applications

• Published in: IEEE transactions on communications 1994-02, Vol.42 (234), p.313-323
• Main Authors: Seshadri, N., Sundberg, C.-E.W.
• Format: Article
• Language: English
• Subjects: Additive white noise; Algorithm design and analysis; Analytical models; Applied sciences; AWGN; Coding, codes; Concatenated codes; Convolutional codes; Exact sciences and technology; Information, signal and communications theory; Iterative algorithms; Iterative decoding; Performance analysis; Signal and communications theory; Telecommunications and information theory; Viterbi algorithm
• ISSN: 0090-6778; 1558-0857
• DOI: 10.1109/TCOMM.1994.577040

A list Viterbi decoding algorithm (LVA) produces a rank ordered list of the L globally best candidates after a trellis search. The authors present two such algorithms, (i) a parallel LVA that simultaneously produces the L best candidates and (ii) a serial LVA that iteratively produces the k/sup th/ best candidate based on knowledge of the previously found k-1 best paths. The application of LVA to a concatenated communication system consisting of an inner convolutional code and an outer error detecting code is considered in detail. Analysis as well as simulation results show that significant improvement in error performance is obtained when the inner decoder, which is conventionally based on the Viterbi algorithm (VA), is replaced by the LVA. An improvement of up to 3 dB is obtained for the additive white Gaussian noise (AWGN) channel due to an increase in the minimum Euclidean distance. Ever larger gains are obtained for the Rayleigh fading channel due to an increase in the time diversity. It is also shown that a 10% improvement in throughput is obtained along with significantly reduced probability of a decoding failure for a hybrid FEC/ARQ scheme with the inner code being a rate compatible punctured convolutional (RCPC) code.< >