Information theory: measuring, compressing and transmitting messages

Information theory is one of the invisible foundations of the digital world. It answers questions that seem simple but were long difficult to formulate mathematically: how much information does a message contain? How far can it be compressed? How quickly can it be transmitted reliably over a noisy channel?

In 1948, American mathematician and engineer Claude Shannon provided a revolutionary framework in his paper A Mathematical Theory of Communication. His goal was not to understand the meaning of a message, but to measure the information it carries and study the physical and mathematical limits of its transmission.

This approach gave rise to information theory.

Today, its concepts are everywhere: compressed files, telecommunications, Wi-Fi, mobile networks, digital storage, error-correcting codes, cryptography, data processing, and many techniques used in artificial intelligence.

Before Shannon: transmitting messages reliably

Long-distance communication existed well before computing.

The telegraph, telephone, and radio had already raised essential technical questions: how could a signal be transmitted as faithfully as possible? How could a communication line be used efficiently? How could a useful message be distinguished from the noise that alters it?

Engineers knew how to improve equipment, amplify signals, and reduce interference. What was still missing was a general theory capable of mathematically describing information and the limits of a communication system.

Claude Shannon worked at Bell Telephone Laboratories during the 1940s, where these questions were particularly important.

His decisive idea was to separate two problems that are easy to confuse:

• what a message means;
• how much information is required to represent and transmit it.

For an engineer transmitting a sequence of symbols, the philosophical or emotional meaning of the message is not required to determine the capacity of the channel.

This separation turned communication into a mathematical problem.

The general model of a communication system

Shannon represented communication using a remarkably simple model.

An information source produces a message.

A transmitter transforms that message into a signal suitable for the channel being used.

The signal then travels through a communication channel.

During its journey, noise may disturb the signal.

A receiver then attempts to reconstruct the message before delivering it to its destination.

This model can apply to very different situations:

• a telephone conversation;
• a radio message;
• data transmitted through optical fiber;
• a packet traveling across a computer network;
• a file being read from a storage medium.

One of Shannon’s major contributions was showing that all these systems could be studied within the same mathematical framework.

The bit: a unit for measuring information

To measure information, Shannon used a unit that became universal: the bit.

A bit represents a choice between two possibilities.

In the simplest case, those possibilities are written as 0 and 1.

But a bit is not merely a binary digit stored inside a computer. More fundamentally, it represents an amount of information sufficient to distinguish between two equally likely possibilities.

Imagine a perfectly fair coin.

Before it is tossed, there are two possible outcomes: heads or tails.

Learning the result provides one bit of information.

If we need to identify one possibility among four equally likely outcomes, two binary decisions are enough: 00, 01, 10, and 11.

We therefore need two bits.

For eight possibilities, three bits are enough.

This relationship explains why the base-2 logarithm plays such a central role in information theory.

The term bit, short for binary digit, had been suggested by statistician John Tukey. Shannon helped establish it as the fundamental unit of his theory.

Not all information is equally surprising

A message carries more information when it was harder to predict.

If someone announces that the Sun will rise tomorrow, very little new information has been provided because the event is almost certain.

By contrast, learning that a highly improbable event has occurred provides more information.

Shannon’s theory formalizes this intuition: the less probable an event is, the more informative its occurrence is.

This idea is essential to understanding entropy.

Entropy: measuring uncertainty

In information theory, entropy measures the average uncertainty associated with a source of messages.

If a source always produces exactly the same symbol, there is no uncertainty. Its entropy is therefore zero.

Conversely, if several symbols are possible with similar probabilities, uncertainty increases and entropy is higher.

For a random variable (X) that can take different values with probabilities (p(x)), Shannon entropy is written as:

[ H(X) = - \sum{=tex}_x p(x)\log{=tex}_2 p(x) ]

The result is expressed in bits when the logarithm uses base 2.

The formula may look abstract, but its intuition is straightforward: it measures how much information we gain on average when we learn the outcome.

A simple example with a coin

Consider a perfectly fair coin.

Heads and tails each have a probability of 50%.

Uncertainty is maximal for an experiment with two outcomes: before the toss, neither result is more predictable than the other.

The entropy is therefore 1 bit.

Now consider a heavily biased coin that lands on heads 99% of the time.

The result is much easier to predict, so the entropy is less than 1 bit.

Finally, if the coin always lands on heads, there is no uncertainty at all: learning the result provides no new information.

The entropy is then zero.

This relationship between probability, surprise, and information is one of the most powerful ideas introduced by Shannon.

Why can data be compressed?

Information theory also helps explain why compression is possible.

Real-world data often contains redundancy.

In an English text, for example, not all letters appear with the same frequency. Some sequences are far more likely than others. After certain letters, the next character also becomes easier to predict.

A compression system can exploit these regularities.

The general idea is to use short representations for frequent events and longer representations for rare events.

This is the principle behind techniques such as Huffman coding.

Other methods use much more sophisticated models, but they still exploit, in one way or another, the structures and repetitions present in the data.

Lossless and lossy compression

Two major families of compression must be distinguished.

Lossless compression

With lossless compression, the original data can be reconstructed exactly.

This is essential for files such as:

• text;
• source code;
• documents;
• structured data;
• certain image formats.

ZIP, PNG, and FLAC, for example, use lossless compression techniques.

Losing a character from a computer program or altering a value in a data file could make the result unusable.

Lossy compression

Lossy compression, by contrast, deliberately discards some information in order to produce much smaller files.

It is commonly used for images, audio, and video.

JPEG, MP3, and many video codecs rely on this approach.

The goal is no longer to reconstruct the original signal exactly, but to preserve enough information for the difference to remain acceptable for the intended use.

Information theory has also developed tools for studying this trade-off between the amount of data and the fidelity of reconstruction.

Is there a limit to compression?

Yes.

This is one of Shannon’s fundamental results.

If a source has a certain entropy, there is a theoretical limit to the average compression that can be achieved without losing information.

In other words, no magical algorithm can compress every file indefinitely while still guaranteeing perfect reconstruction.

Highly redundant data may be compressed dramatically.

Other data that is already close to an efficient representation, or is essentially unpredictable, compresses very little.

This is why compressing an already optimized ZIP, JPEG, or MP4 file again often produces little benefit and may even create a slightly larger file because of the additional information required by the new format.

Shannon’s theory does not necessarily tell us which compression algorithm to use. Instead, it tells us where the limit lies that algorithms cannot beat on average.

Noise: when the message is disturbed

Data transmission faces another problem: noise.

In a real system, a signal may be disturbed by many factors:

• electromagnetic interference;
• hardware imperfections;
• attenuation;
• radio interference;
• reading or writing errors;
• random physical phenomena.

A bit sent as 1 may therefore be received as 0.

It might seem that perfectly reliable communication requires a channel completely free of noise.

Shannon demonstrated something far more interesting.

Information can be transmitted with arbitrarily high reliability over a noisy channel, provided the transmission rate remains below a certain limit and an appropriate coding scheme is used.

This is one of the most important results in all of information theory.

Channel capacity

Every channel has a maximum amount of information it can transmit reliably.

This limit is called the channel capacity.

It depends on factors including the characteristics of the channel and the amount of noise.

For a communication channel affected by Gaussian noise, the famous Shannon-Hartley formula relates capacity (C), bandwidth (B), and the signal-to-noise ratio:

[ C = B \log{=tex}_2(1 + S/N) ]

This equation establishes a theoretical limit.

Increasing bandwidth can increase capacity.

Improving the ratio between signal power and noise power can also increase it.

But there is always a physical limit to the reliable data rate that a channel can support under the given conditions.

Engineers can design systems that approach this limit, but they cannot simply ignore it.

Adding redundancy to correct errors

This may sound paradoxical.

When compressing data, we try to remove unnecessary redundancy.

When protecting data against errors, we sometimes do exactly the opposite: we deliberately add redundancy.

Suppose we want to transmit one bit.

Instead of sending 1, we could send 111.

If the receiver gets 101, it can infer that an error probably occurred and that the original value was likely 1.

This example is extremely crude, but it illustrates the principle.

Modern error-correcting codes use much more efficient mathematical techniques to detect and sometimes correct corrupted data without requiring it to be retransmitted.

Error-correcting codes are everywhere

This idea is now ubiquitous.

Error-correcting codes are used in:

• satellite communications;
• mobile networks;
• Wi-Fi;
• storage media;
• computer memory;
• space communications;
• QR codes;
• many other digital systems.

When a space probe transmits data from millions or billions of kilometers away, the signal received on Earth may be extremely weak and noisy.

Yet coding and error correction make it possible to reconstruct the information with remarkable reliability.

Shannon’s work provided the theoretical framework showing how far that reliability could be pushed.

A theory that does not concern itself with meaning

One of the most surprising aspects of information theory is that it does not attempt to measure the meaning of a message.

The sentence “The meeting starts at nine o’clock” may be extremely important to one person and completely irrelevant to another.

Shannon’s theory does not try to quantify that importance.

It studies the statistical structure of the message, the amount of information required to represent it, and the conditions under which it can be transmitted.

Two messages with radically different meanings can therefore carry the same amount of information in Shannon’s sense.

This abstraction is precisely what makes the theory applicable to such a wide range of fields.

From theory to digital networks

When a smartphone sends a photograph, several problems directly or indirectly related to information theory arise.

The image may first be compressed to reduce the amount of data.

The information is then represented in a form suitable for the communication system.

Error detection or correction mechanisms may be added.

The data then crosses a network subject to various physical constraints.

At the destination, it is decoded and possibly decompressed.

The user sees only a photograph appear on the screen.

Behind this ordinary operation, however, lie decades of research into the representation, compression, transmission, and reliability of information.

Storing information also means transmitting it through time

Information theory does not concern only communication between two places.

A storage medium can be viewed as a channel that transmits information through time.

When we save a file today to read it tomorrow, a signal is encoded onto a medium and retrieved later.

Physical storage media are never perfect.

Errors can occur in memory, disks, or transmission systems.

The same principles of error detection and correction can therefore be used to improve storage reliability.

Communication and storage are thus two sides of the same problem: preserving information despite the imperfections of the physical world.

Information, probability, and artificial intelligence

Concepts from information theory also appear in machine learning and artificial intelligence.

Entropy is used to measure the uncertainty of a probability distribution.

Cross-entropy is a very common function used to train classification models and neural networks.

Other concepts, such as mutual information, help study dependencies between variables.

However, an important shortcut should be avoided: Shannon obviously did not develop his theory for today’s artificial intelligence models.

Rather, the mathematical tools he helped establish proved general enough to be reused in many fields decades later.

An influence extending beyond computing

Information theory has also influenced or inspired work in:

• statistics;
• biology;
• neuroscience;
• linguistics;
• physics;
• cryptography;
• systems theory;
• machine learning.

The word “information,” however, can have different meanings across disciplines.

Information in Shannon’s sense has a precise mathematical definition. It should not automatically be confused with knowledge, truth, meaning, or the value of a message.

This distinction is essential to avoid attributing claims to the theory that it does not actually make.

Why is information theory still fundamental?

The digital world depends on enormous quantities of data.

We continuously produce, compress, store, transmit, and copy information.

At every stage, the same questions return:

• how much data is actually necessary?
• which parts are predictable or redundant?
• how much information can pass through a channel?
• how can an error be detected?
• how can damaged information be reconstructed?
• how far can data be compressed without loss?

Information theory provides a mathematical language for asking these questions precisely.

It does not merely describe technologies from the 1940s.

It establishes fundamental limits that modern technologies still have to obey.

Key takeaways

Claude Shannon’s great contribution was not the invention of one particular new communication method.

It was showing that information itself could be measured and studied mathematically.

A few essential ideas summarize this revolution:

• the bit measures an amount of information;
• entropy measures the average uncertainty of a source;
• redundancy makes compression possible;
• there is a theoretical limit to lossless compression;
• a noisy channel has a maximum capacity;
• appropriate coding allows data to be transmitted with extremely high reliability even in the presence of noise;
• deliberate redundancy makes it possible to detect and correct errors.

Behind a ZIP file, a Wi-Fi connection, a photograph sent from a smartphone, or data received from a space probe are still the questions Shannon formulated more than seventy years ago.

Information theory has therefore become one of the mathematical foundations of our digital world.

Frequently asked questions

What is information theory?

Information theory is a mathematical field that studies the measurement, representation, compression, and transmission of information. It was established as a modern discipline by Claude Shannon with his 1948 paper A Mathematical Theory of Communication.

What is a bit in information theory?

A bit is a unit of information. When there are two equally likely possibilities, learning which one occurred provides one bit of information.

What is Shannon entropy?

Entropy measures the average uncertainty associated with the possible outcomes of a source. The harder the outcomes are to predict, the higher the entropy.

Why can’t a file be compressed indefinitely without loss?

Because a source has a minimum average amount of information required to represent its messages. Shannon’s source coding theorem establishes a theoretical limit for lossless compression.

Can data be transmitted without errors over a noisy channel?

A real channel may introduce errors, but Shannon showed that if the transmission rate remains below the channel capacity and suitable codes are used, the probability of error can be made arbitrarily small.

What is the connection between information theory and artificial intelligence?

Concepts such as entropy, cross-entropy, and mutual information are used in machine learning. Shannon’s theory was not created for modern AI, but its mathematical tools are general enough to be highly useful in the field.