Generalized stack algorithms for decoding convolutional codes
David Haccoun, M.J. Ferguson · IEEE Transactions on Information Theory · 1975
A new class of generalized stack algorithms for decoding convolutional codes is presented. It is based on the Zigangirov-Jelinek (Z-J) algorithm but, instead of extending just the top node of the stack at all times, a number of the most likely paths are simultaneously extended. This number of paths may be constant or may be varied to match the current decoding effort with the prevalent noise conditions of the channel. Moreover, the trellis structure of the convolutional code is used by recognizing and exploiting the reconvergence of the paths. As a result the variability of the computation can be reduced up to a limit set by the "ideal" stack algorithm. Although the tail of the computational distribution is still Pareto, it is shown and verified from simulation with short constraint length codes(K \leq 9)of rate\frac{1}{2}that, compared to sequential decoding, the variability of the number of computations per decoded bit and the maximum computational effort are both reduced at the cost of a modest increase in the average decoding effort. Moreover, some of the error events of sequential decoding are corrected. These algorithms fill the gap between the one-path sequential decoding nad the all-path Viterbi decoding.
Cited by 77 works. doi:10.1109/tit.1975.1055463
Authors
References
- Information Theory and Reliable Communication
- Information Theory and Reliable Communication.
- Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
- A heuristic discussion of probabilistic decoding
- Fast Sequential Decoding Algorithm Using a Stack
- On the Viterbi decoding algorithm
- A lower bound to the distribution of computation for sequential decoding
- A hybrid sequential and algebraic decoding scheme
- An upper bound on moments of sequential decoding effort
- THE COMPUTATION PROBLEM WITH SEQUENTIAL DECODING