LCS/AI Lab Timeline

Convolutional coding (1955)

This paper introduced convolutional error-correcting codes, which won an IEEE award in 1998. They appear in the last sentence of the abstract:

Shannon's and Feinstein's versions of the channel capacity theorem, specialized to the binary symmetric channel, are presented. A much stronger version is proved for this channel. It is shown that the error probability as a function of delay is bounded above and below by esponentials, whose exponents agree for a considerable range of values of the channel and code parameters. In this range the average performance of all codes is essentially optimum, but for small transmission rates this is not true. The results of this analysis are shown to apply to check-symbol codesof four kinds which have progressively simpler decoding procedures. The last of these is error-free, and makes it possible to transmit information at a rate equal to the channel capacity with a probability one that no decoded symbol will be in error.

References:
Peter Elias, "Coding for Noisy Channels", IRE Convention Record, pt. 4, pp. 37-46, Mar. 1955 (initial publication, without figures). Reprinted (with figures) in pp. 102-111 of Key papers in the Development of Information Theory, David Slepian, Ed., IEEE Press, 1974. Reprinted (without figures) in pp. 39-47 of Key Papers in the Development of Coding Theory, Elwyn Berlekamp, Ed., IEEE Press, 1974.

Reported By:
Peter Elias