An analysis of sequential decoding for specific time-invariant convolutional codes
- 1 July 1978
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 24 (4) , 443-451
- https://doi.org/10.1109/tit.1978.1055916
Abstract
A new analysis of the computational effort and the error probability of sequential decoding is presented, which is based entirely on the distance properties of a particular convolutional code and employs no random-coding arguments. An upper bound on the computational distributionP(C_{t}>N_{t})for a specific time-invariant code is derived, which decreases exponentially with the column distance of the code. It is proved that rapid column-distance growth minimizes the decoding effort and therefore also the probability of decoding failure or erasure. In an analogous way, the undetected error probability of sequential decoding with a particular fixed code is proved to decrease exponentially with the free distance and to increase linearly with the number of minimum free-weight codewords. This analysis proves that code construction for sequential decoding should maximize column-distance growth and free distance in order to guarantee fast decoding, a minimum erasure probability, and a low undetected error probability.Keywords
This publication has 15 references indexed in Scilit:
- Distance and computation in sequential decodingIEEE Transactions on Communications, 1976
- Robustly optimal rate one-half binary convolutional codes (Corresp.)IEEE Transactions on Information Theory, 1975
- Convolutional codes III. Sequential decodingInformation and Control, 1974
- Free distance bounds for convolutional codesIEEE Transactions on Information Theory, 1974
- Rate 1/2 convolutional codes with complementary generatorsIEEE Transactions on Information Theory, 1971
- Convolutional Codes and Their Performance in Communication SystemsIEEE Transactions on Communication Technology, 1971
- Nonsystematic convolutional codes for sequential decoding in space applicationsIEEE Transactions on Communication Technology, 1971
- Fast Sequential Decoding Algorithm Using a StackIBM Journal of Research and Development, 1969
- Minimum distance estimates of the performance of sequential decodersIEEE Transactions on Information Theory, 1969
- An upper bound on moments of sequential decoding effortIEEE Transactions on Information Theory, 1969