A comparison of reduced complexity decoding algorithms for trellis codes
- 1 January 1989
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 7 (9) , 1369-1380
- https://doi.org/10.1109/49.44582
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 requiredKeywords
This publication has 20 references indexed in Scilit:
- Decision depths of convolutional codesIEEE Transactions on Information Theory, 1989
- Coset codes. I. Introduction and geometrical classificationIEEE Transactions on Information Theory, 1988
- A multiple stack algorithm for erasurefree decoding of convolutional codesIEEE Transactions on Communications, 1977
- A reduced state variant of maximum likelihood sequence detection attaining optimum performance for high signal-to-noise ratiosIEEE Transactions on Information Theory, 1977
- Generalized stack algorithms for decoding convolutional codesIEEE Transactions on Information Theory, 1975
- The viterbi algorithmProceedings of the IEEE, 1973
- Variable-length codes and the Fano metricIEEE Transactions on Information Theory, 1972
- Instrumentable tree encoding of information sources (Corresp.)IEEE Transactions on Information Theory, 1971
- Fast Sequential Decoding Algorithm Using a StackIBM Journal of Research and Development, 1969
- A heuristic discussion of probabilistic decodingIEEE Transactions on Information Theory, 1963