A Multiple Stack Algorithm for Erasurefree Decoding of Convolutional Codes

A new algorithm for erasurefree sequential decoding of convolutional codes is introduced which achieves low error probabilities at substantially higher decoding speeds than the Viterbi decoding algorithm. The algorithmic properties of the Multiple Stack Algorithm (MSA) are investigated and it is demonstrated that the MSA reaches a decision with an exponentially rather than Pareto distributed computational effort. The MSA's error probability on the binary symmetric channel is studied as a function of its parameters and its performance and complexity compared to that of the Viterbi algorithm. The MSA is seen to achieve equal and lower error probabilities with a significantly lower average decoding effort. The new algorithm can thus be considered an attractive alternative to the Viterbi algorithm where low error probabilities and high decoding speeds are required simultaneously.