Search properties of some sequential decoding algorithms

Abstract

Sequential decoding procedures are studied in the context of selecting a path through a tree. Several algorithms are considered and their properties compared. It is shown that the stack algorithm introduced by Zigangirov and by Jelinek is essentially equivalent to the Fano algorithm with regard to the set of nodes examined and the path selected, although the description, implementation, and action of the two algorithms are quite different. A modified Fano algorithm is introduced, in which the quantizing parameterDeltais eliminated. It can be inferred from limited simulation results that, at least in some applications, the new algorithm is computationally inferior to the old; however, it is of some theoretical interest since the conventional Fano algorithm may be considered to be a quantized version of it.