The following is an extract from our Lost in Space-Time newsletter. Each month, we hand over the keyboard to a physicist or mathematician to tell you about fascinating ideas from their corner of the universe. You can sign up for Lost in Space-Time here.
Beginning in the mid-20th century, the digital revolution ushered in the information age, radically changing the way information is processed and transmitted. Audio and video, which traditionally had been analogue, became digital. Phones gained more computational power than the room-filling machines of the 60s and 70s. How did this change come about?
Certainly, technological advances played an important part. The invention of the transistor and then the integrated circuit helped with miniaturisation, reliability and speed. But mathematics also had a key role. Mathematical theories of computation, information and communication – though not as well-known as theories of quantum mechanics and relativity – contain some stunning results telling us the limits of what information can and cannot be shared.
Advertisement
In 1948, Claude Shannon published “A mathematical theory of communication”, an article that is now regarded as the foundation of information theory. Our intuitive idea of information is subjective, closely related to the idea of meaningfulness. Shannon needed an objective definition of information that might not have any connection to the meaning being conveyed, a definition that would make sense even if the communication were between two machines. Let’s look at an example.
We’ll consider three scenarios. In each, I will send you a brief text at the start of the day, with the message’s contents determined by a coin toss.
In the first, I toss a coin. If it lands heads up, I send you 0. If it is heads down, I send 1. So you receive a binary digit each morning and, though we have yet to define “bits of information”, you also receive one bit of information telling you the result of my coin toss.
In the second scenario, I toss the coin twice. There are four possible outcomes, which we can denote as HH, HT, TH and TT, where H means heads up and T means tails up. As before, I am going to assign 0 to H and 1 to T and so will send you one of four two-bit texts: 00, 01, 10 or 11. As you might guess, each of these corresponds to two bits of information: the two outcomes from tossing the coin twice.
The third scenario comes from adding a third toss. Now, there are eight possibilities – HHH, HHT, HTH, HTT, THH, THT, TTH, TTT – and I send you the appropriate the digit string of 0s and 1s. You are now receiving three bits. For example, if you receive 000, then you have three bits of information telling you that my coin landed heads up all three times.
Now that we have the initial set-up, let’s change things slightly. As in the third scenario, I am going to toss my coin three times, but this time, if it lands heads up three times in a row, I will send just 0. For the other seven possible outcomes, I send just 1. Each day, you will receive just one binary digit, but on days when you receive a 0, you know my coin landed heads up all three times and, as we noted above, this is three bits of information. Of course, on days when you receive a 1, you receive much less than three bits of information – you only know that it could correspond to one of seven possible outcomes.
It is clear that in this case, the binary digit 0 conveys not one, but three bits of information, while the binary digit 1 conveys some information, but not a lot. To calculate exactly how many bits it conveys, we first need to know its probability: a binary digit 1 represents seven out of eight possible coin toss outcomes, giving it a probability of â…ž. The information given by an event that occurs with probability p is defined to be the logarithm to base 2 of the reciprocal of the probability. In our scenario, plugging the probability of â…ž into this mathematical definition of information results in 0.193. So 1 conveys 0.193 bits in this scenario.
Imagine that we repeat this 1000 times. You receive a string of 1000 binary digits. About â…ž of them will be 1s and â…› will be 0s. The total number of bits of information will be the probability telling us how often each outcome will occur, times 1000, times the amount of information each outcome conveys, so about (â…ž x 1000 x 0.193) + (â…› x 1000 x 3) = 543.875. Averaging this out, each binary digit that I send you contains only 0.544 bits of information on average. Shannon called this number the entropy of the digit.
But if we go back to the first examples, where I am sending the outcome of the individual tosses, you receive 1 bit of information for each binary digit. Shannon asked the question: Is it possible to devise a way of compressing data, transmitting the compressed data and then decompressing it, so that the receiver obtains the original message, but, during the transmission stage, each binary digit conveys 1 bit of information? In our example, can we compress the string of 1000 binary digits in order to obtain a string of 544 binary digits and still keep all the information?
Shannon proved that this is indeed the case. Data can be compressed so that each digit contains 1 bit of information. This is the essence of Shannon’s first theorem. (The precise statement involves limits. It says that as the size of the data set gets larger, we can approach 1 bit of information per binary digit.) We use compression all the time for data storage and transmitting files. Shannon’s result concerns lossless compression—the original data set can be reconstructed from the compressed data. We can use lossy compression for pictures and videos, but for much data, it is important that we can retrieve the original version, not a close facsimile. For this, we need lossless compression.
Shannon studied written English. He estimated its entropy to be about 0.5, meaning we could eliminate about half the letters in a book and keep all the information! He realised that this redundancy has a purpose: we use it to correct errors. Typos are annoying, but we can usually recognise them and correct them. This led Shannon to ask whether we could add some useful redundancy back into our compressed data, which machines could use to detect and correct errors.
One simple way to do this is by repetition. Send 000 for each 0 and 111 for each 1. If the receiver gets three of the same digit, she assumes this is the intended digit. If she receives two copies of one digit and one of the other, she assumes there was one mistake. This method will correct one mistake in each triplet, but it gives the wrong answer if there are two or three mistakes in a triplet. Though it does improve accuracy, it does so at the expense of speed: the transmission rate has slowed to one third of the original rate. Shannon showed we could do much better. I will illustrate this with another example.
Suppose I am sending you a large data set. We have designed our equipment to be as reliable as possible, but even so, random errors can still occur. Suppose I transmit one binary digit each second and the noise randomly flips one-tenth of the bits. We can think of the transmission as containing our message along with another message – the noise – superimposed upon it, and we can calculate the entropy of the noise. In this case, it is about 0.469. This means that, on average, each binary digit is conveying 0.469 bits of information that we aren’t interested in. Each binary digit can convey up to 1 bit of information, so that leaves 0.531 bits of information per symbol that we can use.
Our compressed data now contains 1 bit of information per binary digit. Can we add some redundancy in a clever way, resulting in an expanded data set containing 0.5 bits of information per binary digit, so that when we transmit it, all the errors caused by the noise can be corrected using the cunning application of redundancy? Remarkably, Shannon showed this is true. If our original data set is large, we can add redundancy to error correct and obtain an accuracy approaching 100 per cent.
This stunning result, known as the noisy channel theorem, is Shannon’s most famous result. Not only is the result unexpected, but the proof was startling. In our example, we need to design a way of adding redundancy for error correction. Shannon showed that chopping the data into blocks of binary digits of length n and randomly assigning them to blocks of length 2n will work as n gets larger.
Shannon’s communication paper tells us how to compress data and transmit it without errors. However, this is for digital data. What do we do for analogue data like audio and video? Shannon gave the answer in another paper, also published in 1948, explaining how we can sample an analogue signal, convert it to a digital signal, transmit that signal and then convert it back to the analogue signal. Shannon didn’t claim the result was his – he stated this is “common knowledge in the communication art” and mentioned that it was contained in the previous work of a colleague, Harry Nyquist. Indeed, the theoretical ideas behind this go back to French mathematician Joseph Fourier, who was born in the 18th century. But Shannon gave a clear exposition and published it at exactly the right time. This important result is now known as the Nyquist-Shannon sampling theorem.
We use methods of compression, error-correction and conversion between analogue and digital data multiple times each day. The fact that these work so seamlessly makes them unnoticeable to the casual observer, but the mathematical theory of information provides the framework upon which much of the digital revolution is based. Without it, you wouldn’t be able to receive, say, the information conveyed in these words.
