For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Butterfly Structure for Viterbi Decoders of All Rates k/n
Tsung Sheng KUO Chau-Yun HSU
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2007/02/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Coding Theory
butterfly structure, Viterbi decoder, convolutional codes, computational complexity,
Full Text: PDF(548.5KB)>>
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.