Butterfly Structure for Viterbi Decoders of All Rates k/n

Tsung Sheng KUO  Chau-Yun HSU  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.2   pp.504-510
Publication Date: 2007/02/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.2.504
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Coding Theory
Keyword: 
butterfly structure,  Viterbi decoder,  convolutional codes,  computational complexity,  

Full Text: PDF(548.5KB)>>
Buy this Article




Summary: 
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.