On the complexity of turbo decoding algorithms

Author

Wu, Peter H Y

Author_Institution

Lincoln Lab., MIT, Lexington, MA, USA

Volume

2

fYear

2001

fDate

2001

Firstpage

1439

Abstract

We evaluate the computational complexity of several turbo decoding algorithms: log maximum a posteriori (log-MAP), maximum log-MAP (max-log-MAP) and the soft output Viterbi (see IEEE Journal on Selected Areas in Communications, vol.16, no.2, p.260-64,1998) algorithm (SOVA). The computational complexity is analyzed in terms of mathematical operations and the results are normalized by an equivalent addition operation for easy comparison. Furthermore, these algorithms are programmed on a DSP and the number of CPU cycles per decoded bit is measured. Our approach leads to a quick complexity estimate of a turbo decoder with respect to the conventional Viterbi decoder. Both analyzed and measured results suggest that the max-log-MAP algorithm is the best implementation choice because it is the least complex and exhibits only minor performance loss

Keywords

Viterbi decoding; computational complexity; maximum likelihood decoding; turbo codes; CPU cycles per decoded bit; DSP; SOVA; Viterbi decoder; computational complexity; log maximum a posteriori algorithm; max-log-MAP algorithm; soft output Viterbi algorithm; turbo decoding algorithms; Algorithm design and analysis; Computational complexity; Decoding; Digital signal processing; Laboratories; Loss measurement; Performance analysis; Performance loss; Turbo codes; Viterbi algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Vehicular Technology Conference, 2001. VTC 2001 Spring. IEEE VTS 53rd

Conference_Location

Rhodes

ISSN

1090-3038

Print_ISBN

0-7803-6728-6

Type

conf

DOI

10.1109/VETECS.2001.944625

Filename

944625