Sequential Decoding - The Computation Problem

Sequential decoding procedures are important because they achieve, at modest cost, a decoding error rate which approximates the error rate of the optimum and expensive maximum-likelihood decoder. Sequential decoding procedures have this near-optimum performance at modest cost because they allow the level of the channel noise to determine the level of the decoding computation. The level of the decoding computation is a function of the source rate as well as the channel noise and if the source rate is held at less than a computational cutoff rate, R0omp , the computation level on the average will be small. 1,216 Thus, a sequential decoder may be constructed from a logic unit capable of handling two or three times the average computation rate and from a buffer to store data during those noisy periods which require a computation rate which exceeds that of the basic decoding machine. The maximum likelihood decoder, however, always requires a very high computation rate and, in effect, is designed to handle the peak noise levels. The buffer portion of the decoder stores data during periods of high computation and since it has finite capacity, it will fill and overflow if the high computation intervals are too frequent or too long. If and when a buffer overflow occurs, the decoder cannot continue to decode reliably since data which are important to the continuing decoding process are lost. Consequently, a buffer overflow forces a halt in the decoding process while both the encoding and decoding processes are restarted.