LIST VITERBI DECODING ALGORITHMS WITH APPLICATIONS

A list Viterbi decoding algorithm (LVA) produces a rank ordered list o f the L globally best candidates after a trellis search. Here, we pres ent two such algorithms, (i) a parallel LVA that simultaneously produc es the L best candidates and (ii) a serial LVA that iteratively produc es the k(th) best candidate based on knowledge of the previously found k-1 best paths. The application of LVA to a concatenated communicatio n 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 obt ained when the inner decoder, which is conventionally based on the Vit erbi algorithm (VA), is replaced by the LVA. An improvement of up to 3 dB is obtained for the additive white Gaussian noise (AWGN) channel d ue to an increase in the minimum Euclidean distance. Ever larger gains are obtained for the Rayleigh fading channel due to an increase in th e time diversity. It is also shown that a 10% improvement in throughpu t is obtained along with significantly reduced probability of a decodi ng failure for a hybrid FEC/ARQ scheme with the inner code being a rat e compatible punctured convolutional (RCPC) code.