Butterfly structure for Viterbi decoders of all rates k/n
This paper proposes a butterfly structure for Viterbi decoders, which works for convolutional codes of all rates k/n. The proposed butterfly structure can exploit the inherent symmetry of trellis branches, so that only some branch metrics need to be computed, while the others can be derived from the computed branches. Consequently, the computational complexity of the Viterbi decoder can be significantly reduced without any error performance loss. The applicability of the butterfly structure is validated by the best codes of rates 1/2, 2/3, and 3/4. Most of the best codes can apply the butterfly structure to reduce their branch metric computation complexity by a factor of 2 or 4. This study also reports a number of new codes with high branch symmetry under the symmetry consideration. Their branch metric computation can be reduced by a factor of 4, 8 or 16 with the similar performance to the best codes.
butterfly structure viterbi decoder convolutional codes computational complexity