A comparison of reduced complexity decoding algorithms for trellis codes

Author

Pottie, Gregory J. ; Taylor, Desmond P.

Author_Institution

Dept. of Electr. & Comput. Eng., McMaster Univ., Hamilton, Ont., Canada

Volume

7

Issue

9

fYear

1989

fDate

12/1/1989 12:00:00 AM

Firstpage

1369

Lastpage

1380

Abstract

Comparisons are made of a genie-aided sequential algorithm due to D. Haccoun and M.J. Ferguson (1975), the Viterbi algorithm, the M -algorithm, and the Fano algorithm for rate-1/2 and rate-2/3 trellis modulation codes on rectangular signal sets. The effects of signal-to-noise ratio and decoding-delay constraints on the choice of decoding algorithms for framed data are examined by computer simulation. Additionally, the genie-aided algorithm is used as a tool in estimating the asymptotic behavior of the M-algorithm. In general, the results conform closely to experience with convolutional codes due to the similar distance structure of the codes. The Fano algorithm produces good error performance with a low average number of computations when long decoding delay is permissible. The M-algorithm provides a savings in computation compared to the Viterbi algorithm if a small decoding delay is required

Keywords

decoding; telecommunications computing; Fano algorithm; M-algorithm; Viterbi algorithm; computer simulation; convolutional codes; decoding-delay constraints; framed data; genie-aided sequential algorithm; rectangular signal sets; reduced complexity decoding algorithms; signal-to-noise ratio; trellis codes; Algorithm design and analysis; Computer simulation; Convolutional codes; Costs; Decoding; Delay effects; Modulation coding; Quadrature amplitude modulation; Signal to noise ratio; Viterbi algorithm;

fLanguage

English

Journal_Title

Selected Areas in Communications, IEEE Journal on

Publisher

ieee

ISSN

0733-8716

Type

jour

DOI

10.1109/49.44582

Filename

44582