Feature Column from the AMS

Digital Revolution (Part III) - Error Correction Codes

Posted February 2003.

Feature Column Archive

1. Introduction

The age of the LP - the long playing record - radically changed the delivery of music to the public but its lifetime as a technology was surprisingly short. The LP was born in 1948 and by the 1980's the popularity of the audio CD ended the LP era. The age of VHS (Video Home System) format videotape developed by JVC (which won the competition with the probably superior Betamax standard developed by SONY), radically changed the delivery of video to the public. This change was so radical that for a while it did not seem as if the public would be able to benefit from it! No sooner had the VCR (Video Cassette Recorder) arrived than attempts were made to prevent this technology from being made available to the public. The argument was that the VCR made it possible for the public to tape copyrighted material off the air. After all, lots of money and creativity went into original TV programming and uncut movies were being shown on TV. What prevented someone from taping this programming or movies and having a party at which they invited 30 friends to stop by and watch, and perhaps charge admission?

The attempt of the SONY Corporation to market its VCR (VTR in those days) eventually made its way to the United States Supreme Court. In a landmark case the Court decided by 5-4 (!) that SONY could sell its new machine. The Court accepted the idea, overruling the Appeals court decision, that people could make copies of these copyrighted materials for their personal use and developed the idea of "fair use." Contrary to the doom and gloom opinions of some in the movie and TV industry, the VCR did not mean the end for motion picture theaters. In fact, the public continued to go to the theaters to see movies and to watch TV. A huge market was created for blank and prerecorded tapes with all kinds of content, from movies to self-help to exercise regimens, and the tapes sold like hot cakes.

However, perhaps the age of VHS tape is coming to an end, just as the audio CD spelled the death knell for the LP. The reason ultimately is that the LP and VHS are analog technologies and the CD and DVD, which is rapidly replacing VHS, are digital technologies. DVD allows one to have a better picture than VHS while taking up less physical room, and along with the movies and other materials on a DVD there are numerous "enhancements" that the VHS versions of the materials do not have. Whereas a few years back DVD players were so expensive and the number of DVD's available were so few in number that only the very rich purchased DVD players, their price has since dropped dramatically. Recently many hardware companies are marketing VHS-DVD players that cost the same amount the VCR's did a few years back. Many stores that rent movies now carry increasingly fewer movies in VHS format because the balance between usage of DVD's and VHS has shifted to DVD's! Part of the reason for the quickening pace of DVD technology is the knowledge that the recently passed congressional legislation calling for all TV sets to be equipped with digital tuners within a few years will rapidly quicken the pace of the digital revolution in television. More action in the HDTV (High Definition Television) area is just around the corner.

I have already explored two aspects of the digital revolution that mathematics helped make possible. In earlier columns I looked at the use of codes to speed information and to compress information. There are many other aspects to the digital revolution, but one essential aspect is that when digital information is transmitted from one location to another or changed from one medium to another (e.g. pictures sent via a telephone hookup) there are ways of encoding the information involved so that if errors occur in the transmission between one medium or location and another, these errors can be corrected!

At first, the fact that there existed error correction codes was merely a tour-de-force of pure mathematics. Claude Shannon showed that there existed codes that could correct errors. He did this by showing that certain long random strings used as codewords would do the job. However, his ideas could not be put to immediate practical use. It remained for Richard Hamming (1915-1998) and Marcel J. E. Golay (1902-1989) to explicitly construct error correcting codes that ushered in many practical applications.

In addition to Shannon and Hamming, many other scientists who worked for the Bell System developed both theoretical and practical ideas related to error correction systems. Among these people were D. Slepian, E. Berlekemp, and E. Gilbert. F. Jessie MacWilliams (1917-1990) and N. Sloane summarized the state of the art through the 1970's in a well-known book. The work of these and other mathematicians laid the foundation for a revolution in communications technology that is still being played out today.

Joseph Malkevitch
York College (CUNY)

Email: malkevitch@york.cuny.edu