List and soft symbol output Viterbi algorithms: extensions and comparisons

The Viterbi algorithm (VA) is the maximum likelihood decoding algorithm for convolutionally encoded data. Improvements in the performance of a concatenated coding system that uses VA decoding (inner decoder) can be obtained when, in addition to the standard VA output, an indicator of the reliability of the VA decision is delivered to the outer stage of processing. Two different approaches of extending the VA are considered. In the first approach, the VA is extended with a soft output (SOVA) unit that calculates reliability values for each of the decoded output information symbols. In the second approach, coding gains are obtained by delivering a list of the L best estimates of the transmitted data sequence, namely the list Viterbi decoding algorithm (LVA). Our main interest is to evaluate the LVA and the SOVA in comparison with each other, determine suitable applications for both algorithms and to construct extended versions of the LVA and the SOVA with low complexity that perform the task of the other algorithm. We define a list output VA using the output symbol reliability information of the SOVA to generate a list of size L and that also has a lower complexity than the regular LVA for a long list size. We evaluate the list-SOVA in comparison to the LVA. Further, we introduce a low complexity soft symbol output viterbi algorithm that accepts the (short) list output of the LVA and calculates for each of the decoded information bits a reliability value. The complexity and the performance of the soft-LVA (LVA and soft decoding unit) is a function of the list size L. The performance of the soft-LVA and the SOVA are compared in a concatenated coding system. A new software implementation of the iterative serial version of the LVA is also included.<>