Reduced complexity decoding of convolutional codes based on the M-algorithm and the minimal trellis

In this paper, we propose three new sub-optimum, reduced complexity decoding algorithms for convolutional codes. The algorithms are based on the minimal trellis representation for the convolutional code and on the M-algorithm. Since the minimal trellis has a periodically time-varying state profile, each algorithm has a different strategy to select the number of surviving states in each trellis depth. We analyse both the computational complexity, in terms of arithmetic operations, and the bit error rate performance of the proposed algorithms over the additive white Gaussian noise channel. Results demonstrate that considerable complexity reductions can be obtained at the cost of a small loss in the performance, as compared to the Viterbi decoder.