Empowering Digital Communications

A little five-page article published by two Lincoln Laboratory researchers in a 1960 issue of the Journal of the Society for Industrial and Applied Mathematics had big consequences for the digital world. Irving Reed and Gustave Solomon authored “Polynomial Codes over Certain Finite Fields,” in which they mathematically laid out a new scheme for detecting and correcting errors in digital transmissions. Their concept, familiarly known as the Reed-Solomon codes, is still used today, enabling satellite communications to and from deep space; CDs and DVDs storing audio, video, and text data; 2D bar codes such as QR codes; and high-definition television broadcasts.

Reed and Solomon did not set out to revolutionize communications technology. In their work on the SAGE (Semi-Automatic Ground Environment) air defense system, the two engineers were exploring ways to fix errors in radar data sent over noisy communication links. The digital data that needed to be transmitted among the SAGE radars, command centers, and interceptors had to be reliable. The then commonly accepted method of detecting errors in a digital message was to send the message multiple times and let the receiving decoder spot the anomalies among the versions. The system would then correct to a version that had the most frequently — and thus assumed most correctly — transmitted data bits. This method was inefficient and not always accurate. Reed and Solomon sought a better strategy.

That early method of comparing multiple versions of a transmission only looked at the individual bits, the 0's and 1's, in the message, possibly with an appended check-sum of bits. Reed and Solomon proposed that information bits could be transmitted in groups, significantly reducing the number of comparisons at the receiver. A message would consist of several groups, with a typical group possibly consisting of eight bits (now known as a byte). In their scheme, the message encoder adds redundant groups to a message on the basis of a prescribed polynomial. When the decoder receives the transmission, it applies the polynomial, which recreates the redundant groups. If the recreated redundant groups do not correspond to the rest of the message, then an error remains in the transmission. Another polynomial function then determines the positions of the erroneous bits and corrects them. 

The Reed-Solomon codes were innovative — but they were also computationally intensive at a time when computers were not powerful enough to handle them efficiently. Despite their potential, the codes did not initially find widespread practical use. Interest in them was mainly academic, with variations on the codes developed by researchers from institutions in the United States and abroad.

Burst of applications

Reed-Solomon codes have enabled the Hubble Telescope to transmit images like this back to scientists on Earth. The galaxy depicted in this Hubble image is a barred spiral galaxy, known as NGC 7541, in the constellation of Pisces. Photo courtesy of NASA

When computing caught up with the mathematical rigors of the Reed-Solomon codes, these flexible, robust tools found many applications. An early application was in the tactical ultrahigh-frequency Department of Defense satellite system developed by Lincoln Laboratory in the 1960s, with the codes used on the Lincoln Experimental Satellite (LES)-6 (launched in 1968) and later operational satellites. In 1977, the NASA Voyager program tapped the Reed-Solomon codes to enable its deep-space communication system. The Voyager's communication system achieved a data rate of 21,600 bits per second from 2 billion miles away, and required less energy than used by a battery for a wristwatch.^[1] The Hubble Space Telescope, launched in 1990 by NASA, continues to use Reed-Solomon codes in transmitting its data back to Earth. And, today's space missions still count on the Reed-Solomon codes to keep their data trustworthy.

Adopted by the commercial sector in the early 1980s, Reed-Solomon codes have made digital recording of various data reliable and aesthetically pleasing. The error-correcting power of the codes allows CDs and DVDs to play sound and motion that are unaffected by scratches on the disks. Information stored on disks is readable and accurate because of the codes. Reed-Solomon error correction also proved perfect for allowing 2D bar codes to be parsed by scanners even if pieces of the codes are damaged, for example, by getting wet on a package or being crumpled in a magazine. 

In 1995, the Institute for Electrical Engineering and Electronics (IEEE) recognized Reed and Solomon with its Masaru Ibuka Consumer Electronics Award for "contributions to basic error-correcting codes, specifically the Reed-Solomon Codes, which led to the compaction of data and made possible a generation of consumer compact optical disk products."

Next time you marvel at the Hubble Space Telescope's image of a colorful explosion of gases from the Crab Nebula or listen to a much-played DVD of your favorite Star Wars movie, know that two former Lincoln Laboratory radar engineers are responsible for your delight.

^[1] W.A. Geisel, "Tutorial on Reed-Solomon Error Correction Coding," NASA Technical Memorandum 102162, August 1990.