Feature Column from the AMS

Digital Revolution (II) - Compression Codes and Technologies

Digital Revolution (II) - Compression Codes and Technologies; Introduction

1. Introduction

In this column I will discuss some ideas about the mathematics behind compression and show how mathematics is a hidden partner in the development of the digital revolution. Also, I will try to mention a few of the people who made important contributions to this area of work within mathematics.

In August, 2002 the Federal Communications Commission voted that by 2004 all new television sets with at least a 36-inch screen will have to be equipped with digital tuners and all sets, regardless of the size of their screens, will have to meet this standard by 2007. This action was taken to accelerate the results of earlier FCC actions aimed at moving along towards digital television or HDTV (high definition television). Although television was born as an analog technology, initially dominated by a broadcast delivery mode (i.e. the signal is transmitted directly to one's home through the air from a local transmitter ) increasingly television is being delivered to homes via either cable (underground fiber optic cable) or satellite delivery (signals are directed towards one's home by beaming them from a space satellite). These signals are often not digital and the signal one receives may not be locally produced. Currently very few television sets sold in the United States can receive digital pictures and the ones that can are very expensive.

Clearly, the future of television and radio involve digital technologies. The resistance to change involves chicken and egg issues. It's hard to take a first step when consumers have few sets that can receive digital signals, when it's expensive for TV to be produced in digital format (new cameras, etc. are necessary) and when different manufacturers of equipment for sending and receiving digital signals are unsure of which emerging standard will be used as the format for delivering digital TV. Japan developed a high definition television format which involved analog signals but it plays a small role in Japan and was never adopted outside of Japan. The politics of technology and economics have played a major part in the evolution of which technologies can become successful. There is a lot of money to be made or lost.

Mathematics has also played a major role because with an assist from mathematics, technologies that can not otherwise be implemented become possible. One major assist, among many, lies in the world of compression. Data compression deals with how to take a large collection of binary bits, the life blood of digital technologies, and replaces this collection with a small compressed version of the original bits, from which the original bits can be reconstructed (because the compressed collection has a structure lacking in the original or because the compressed set allows the reconstruction of a close approximation of the original).

A good way to think about compression is that if data is redundant in some way, it can be made to take up less room, that is, it can be compressed. As a very simple example, there are 26 letters in the English alphabet and since letters can come in upper or lower case, and one needs a symbol for space, one requires a rock bottom minimum of 53 symbols to represent English. If one is representing the text using binary bits and each symbol is represented by the same number of binary bits, this means that one needs 6 binary bits. If one is willing to give up upper and lower case, then 5 bits will do. This is an example of compression where some information is lost. (Braille, a system which codes information in blocks of dots for the blind, uses a rectangular system of 3 rows of 2 dots each. Each dot is either raised or level, which means that, in essence, a 6 bit system is being used. Braille does not code for both upper and lower case but instead uses the six binary choices available to code 64 pieces of information to represent common words and word endings.) Morse code involves a compression strategy by using a single dot for the letter e and a single dash for the letter t, reflecting that these letters are more common in English than letters represented by longer strings of dots and dashes.

Joseph Malkevitch
York College (CUNY)

Email: malkevitch@york.cuny.edu