LIST VITERBI DECODING ALGORITHMS WITH APPLICATIONS

A list Viterbi decoding algorithm (LVA) produces a rank ordered list of the L globally best candidates after a trellis search. Here, we 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(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.