An Application of Set Theory to Coding Theory
Noca Alon, Andy Liu · Mathematics Magazine · 1989
As high-speed electronic communication becomes commonplace, there is a tremendous need for better transmission schemes-ones that minimize the effect of inevitable transmission errors, ones that protect confidential or secret messages, ones that route messages most efficiently. Many of the best schemes are based on patterns or properties of classical algebraic and geometric objects, originally studied for their intrinsic interest. Mathematically, these are the subjects of information theory, coding and encryption [5]. In this note, we will confine our attention to one aspect of information theory: error-correcting codes. We first state our assumptions about the setting in which these codes come into play. Messages are in the form of sequences of 0's and l's. In transmission, the only errors that may occur are in the form of digit-reversals; that is, an error may change a 0 to a 1, or vice versa. The transmission device handles blocks of 1 digits at a time, and we know the maximum number of errors per transmission. If the original message is broken up into blocks of length 1, and transmitted as is, potential transmission errors will compromise the reliability of the received message. To trade off economy for accuracy, the original message is broken up into words of length in < 1, and each word is augmented with I m digits in such a way that the correct word can be deciphered despite possible errors. An error-correcting code may be defined as a pair of companion procedures. The first, that of determining how the 1 mn additional digits are to be chosen, is called encoding. The second, that of recovering the correct word from the received block, is called decoding. The ratio m/i is a measurement of the efficiency of the code. The subject of error-correcting codes is of immense scope and depth, as detailed in the monumental treatise by MacWilliams and Sloane [6]. An excellent exposition by Thompson [10] shows the interrelationship between codes and many other mathematical structures. Our primary purpose is to give another example along this line. We will show how a recent set-theoretic result of Frankl and Pach [2] provides an alternative justification for a family of known codes. Error-correcting codes may be based on very simple ideas (see for example [1] and [8]), but these tend to suffer in efficiency. The extended Hamming codes (see [3] and [4]), discovered early in the history of information theory, enjoy the best of both worlds. We will begin by describing such a code in set-theoretic language.