Binary Block Coding
S. P. Lloyd · Bell System Technical Journal · 1957
From the work of Shannon one knows that it is possible to signal over an error-making binary channel with arbitrarily small probability of error in the delivered information. The effects of errors produced in the channel are to be eliminated, according to Shannon, by using an error correcting code. Shannon's proof that such codes exist does not provide a practical scheme for constructing them, however, and the explicit construction and study of such codes is of considerable interest. Particularly simple codes in concept are the ones called here close packed strictly e-error-correcting (the terminology is explained later). It is shown that for such a code to exist, not only must a condition due to Hamming be satisfied, but also another condition. The main result may be put as follows: a close-packed strictly e-error-correcting code on n, n > e, places cannot exist unless e of the coefficient vanish in (1 + x)e(1 − x)n−1−ewhen this is expanded as a polynomial in x