Digital Revolution (Part III) - Error Correction Codes

5. Theory and practice of codes

It was clear early in the history of the development of the mathematics of error correcting codes that such codes would have lots of economic value, something that is not always true for ideas developed in other parts of mathematics. Researchers in mathematics, like creative people in other fields, want rewards and recognition for their work. Someone who is the first to conjecture an important mathematical result, the person(s) who first proves a mathematical result, or the person who discovers ideas that can be applied all get forms of recognition (see the * below for a discussion of some of these forms of recognition).

Priority disputes, concerning the first person to develop important ideas, have occurred in mathematics just as they have in other fields. One of the most famous of such disputes was the controversy between Newton and Liebniz over who developed the Calculus first. Another such dispute, in much more modern times, was the dispute between Richard Hamming and Marcel Golay over the development of error correction codes. Although Golay's name is much less well known than Shannon's or Hammings', he made very important contributions to information theory, including calling attention to some special codes with very nice properties that are known as the Golay Codes. Though born in Switzerland, Golay earned a Ph.D. in Physics in the United States and spent a good part of his career in America working for Bell Labs and the U.S. Army Signal Corps before returning to Europe in the 1960's. Interestingly, though he used mathematics in his work, it was his tremendous intuition about the behavior of physical systems that helped Golay make the important contributions he did. In particular he was involved with over 50 patents. Golay also made important contributions to chromatography and to global navigation systems through the development of ideas that are incorporated into the Loran C system.

Ideally, one wants codes with lots of code words, which will correct lots of errors, and for which the code word length is short. Not surprisingly, these desires "work against" each other: There is a complex tradeoff between the number of errors that a code can correct, the number of binary digits in the code word, and the largest number of code words that a code can have. Shown below is a portion of what is known about the situation. The data is given for some small values of e, the number of errors per code word up to which the code can correct. The entries in the table give the maximum number of binary code words which a given length of string and error correction capability can have. For example, there is no binary code whose code words have length 5, which will correct up to 1 error and which has more than 4 code words. Similarly, there is no binary code with more than 2 code words where the code words are strings of length 7 and which will correct up to 2 errors.
 

(*)In science, among the most prestigious awards has been the Nobel Prize. These prizes, which carry a large monetary value, were funded by Alfred Nobel about 100 years ago. They are awarded in the field of medicine and in various sciences. There was initially no Nobel Prize in Economics but in 1969 the prestigious Nobel Memorial Prize in Economics was created. The mathematician John Nash won this prize and the prize has been awarded to quite a few economists whose work is highly mathematical. No Nobel Prize in mathematics was created. There have been many "legends" about the reason for this. Although it appears that sometimes mathematical scientists have their eyes "on a prize" when deciding how much information to disclose about a line of research they might be pursuing, until very recently, with the lucrative Clay and Abel Prizes, the most prestigious prize in mathematics has been the unlucrative Fields Medal. Because of this, or in spite of this, mathematicians have often been quick to publish their work even when it had high potential for economic return. This does not mean that mathematicians are not sensitive to getting recognition both for the ideas they had discovered and to making money from their ideas.

1. Introduction
2. Basic ideas
3. The channel concept
4. Codes and geometry
5. Theory and practice of codes
6. Error correction technologies
7. References