Sequential Decoding
Rolf Johannesson, Kamil Sh. Zigangirov · 2015
This chapter describes a class of algorithm, known as sequential decoding algorithms, whose intricacy is essentially independent of the memory of the encoder. The chapter begins by introducing a quality measure that could guide a decoder in its search for the most promising path to explore. This leads naturally to the stack algorithm, which is the simplest one to describe and analyze. After discussing the stack algorithm, it provides a more intricate Fano algorithm. Then the chapter discusses Creeper, which combines the best properties of the other two algorithms. For all three algorithms, it analyzes their computational performances and obtain upper bounds on the decoding error probabilities.