Sequential decoding

Abstract

In this investigation, the coding problem for a binary symmetric channel (BSC) has been studied in detail, in order to provide a clear exposition of the work done by Wozencraft and Reiff en on sequential decoding. A new exposition of the random coding technique and a precise formulation in terms of set concepts of a mathematical model for the probability of the decoding error are presented. A suitable threshold IT for the threshold block decoding has also been derived. The sequential decoding scheme proposed by Wozencraft has been examined carefully and certain modifications have been made. The new analysis enables us to obtain a tighter bound on the average number of computations per message digit for any transmission rate Rt which is less than a certain critical value. Finally, several random variables encountered in random coding have been rigorously studied, and a proof of their independence has been worked out.