On the Error Probability of Sequential Decoding on the BSC

Abslract-Upper bounds are derived on the error probability that can be achieved by using the maximum-likelihood algorithm of sequential decoding for the binary symmetric channel. The bounds are functions of constraint length and backsearch limit. I T IS known [1] that the error probability of decoding a convolutional code, considered as a function of delay (backsearch limit), cannot be less than Hamming’s bound. It is also known [2], [3] that a method of sequential decoding exists for which the probability of error satisfies the random coding bound for block codes. The last result was obtained by decoding with a limitation on backsearch, which is equal to (or less than) the constraint length. On the other hand, it is known [2], [4] that the error probability of sequential decoding can satisfy .the YudkinViterbi bound [2], [4] if there is no limitation on the backsearch. In this paper we obtain an upper bound on the error probability on the BSC, using the constraint length v atld the backsearch limit z(z > v). The results are obtained for the maximum-likelihood (“stack”) algorithm of sequential decoding [5] (also see [6]) and may be generalized without difficulty to the case of decoding with the Fano algorithm.