In this letter, we propose a butterfly structure for rate 2/n convolutional codes to reduce the computational complexity of Viterbi decoders. By using the butterfly structure, the branch metric computation complexity of some best known codes can be reduced by a factor of 2 or 4.

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.