Introduction

Communication is so familiar that it can seem almost too ordinary to need a theory. We speak, send messages, stream video, store photographs, read files from memory, and receive signals from satellites. In each case, something is selected at one place or time and must be reproduced, approximately or exactly, somewhere else.

Shannon theory begins by asking a sharply mathematical question:

What are the fundamental limits of representing and transmitting messages?

This question is not about the emotional meaning of a message, the truth of a sentence, or the beauty of a photograph. Those matters are real and important, but Shannon’s theory deliberately separates them from the engineering problem of communication. In his 1948 paper, Claude E. Shannon framed communication as the problem of reproducing at one point either exactly or approximately a message selected at another point, and he explicitly distinguished this engineering problem from semantic interpretation (Shannon, 1948).

That separation is one of the reasons the theory is powerful. The same mathematics can describe a text file, a digital image, a stream of sensor measurements, a genetic sequence, or a radio transmission. Shannon theory does not need to know what a message means in order to study how many bits are needed to describe it, how many errors noise may cause, or how fast it can be transmitted reliably.

The basic situation

Imagine a friend wants to send you one of four possible messages:

• A: “Meet at 10.”
• B: “Meet at 11.”
• C: “Meet at 12.”
• D: “Cancel.”

If all four messages are equally likely, then before the message arrives you are uncertain among four possibilities. A natural binary representation is:

Here each message is represented by two binary digits, or bits. A bit is a symbol that can take one of two values, usually written as 0 or 1. Two bits can represent four possibilities because there are \(2^2 = 4\) binary strings of length two.

This tiny example already contains several central ideas of the book:

1. There is a source, which selects a message.
2. There is a representation, or code, that turns the message into symbols.
3. There may be a channel, such as a wire, radio link, storage device, or network connection, through which the symbols pass.
4. There may be noise, meaning random disturbance that can change, erase, or corrupt symbols.
5. There is a receiver or decoder, which tries to reconstruct the original message.
6. We care about efficiency, because we want to use as few symbols as possible.
7. We care about reliability, because we want the reconstructed message to be correct.

Communication theory studies these ideas with probability, algebra, and limits.

Why probability enters the theory

A message is often uncertain before it is observed. If your friend always sends A, then receiving A tells you nothing surprising. If your friend may send any of four messages, then receiving one of them removes more uncertainty. Shannon’s key insight was that information can be treated quantitatively by connecting it to uncertainty and probability (Shannon, 1948).

For example, suppose a weather station sends one of two messages every morning:

• S: sunny
• R: rainy

If the station is in a desert where S occurs with probability \(0.99\), then S is not very surprising. The message R, with probability \(0.01\), is much more surprising. Shannon theory captures this by assigning more self-information to rarer events. Later, we will define the self-information of an event with probability \(p\) as

\[ \log_2 \frac{1}{p}. \]

This formula is not introduced as a mysterious trick. It will be motivated carefully in Chapter 3. For now, notice only the direction: smaller probability means larger information.

When we average the information over all possible outcomes of a random source, we obtain entropy. Entropy is one of the central quantities in this book. For a discrete source with possible symbols \(x\) and probabilities \(p(x)\), its Shannon entropy is

\[ H(X) = -\sum_x p(x)\log_2 p(x). \]

At this point, do not worry if the formula feels new. The important first idea is this:

Entropy measures the average uncertainty of a random source, in bits.

This interpretation is standard in information theory and is the foundation of both lossless compression and communication over noisy channels (Cover & Thomas, 2006).

Compression: removing predictable structure

One major question in Shannon theory is:

How many bits are really needed to describe messages from a source?

If every possible message is equally likely and unrelated to every other, there may be little opportunity for compression. But real data is often predictable. English text has patterns. Images have neighboring pixels that are often similar. Sensor readings change gradually. These patterns can be exploited.

Consider a source that emits four symbols with these probabilities:

A fixed-length code would use two bits per symbol, because there are four symbols. But since A is much more common than C or D, we might assign a shorter codeword to A and longer codewords to rare symbols:

This is a prefix-free code, meaning no codeword is the beginning, or prefix, of another codeword. That property allows a receiver to decode a stream of bits unambiguously from left to right. For example,

\[ 0101110 \]

is decoded as

\[ A,\ B,\ D,\ A. \]

The average length of this code is

\[ 0.50(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75 \]

bits per symbol, which is better than the fixed two-bit code.

Shannon’s source coding theorem explains the fundamental limit behind such examples: for a discrete memoryless source, the entropy gives the best achievable compression rate in the limit of long blocks, up to arbitrarily small excess rate (Shannon, 1948; Cover & Thomas, 2006). This book will build the theorem step by step instead of simply stating it.

Noise: communication is not just compression

Compression asks how short a representation can be. Communication over a noisy channel asks a different question:

How can we transmit messages reliably when the channel sometimes makes errors?

Suppose a channel sends one bit at a time. Most of the time it transmits correctly, but occasionally it flips a bit:

\[ 0 \to 1,\qquad 1 \to 0. \]

This is a simple example of a binary symmetric channel. It is “binary” because the input and output symbols are bits. It is “symmetric” because the probability of flipping \(0\) to \(1\) is the same as the probability of flipping \(1\) to \(0\).

If the sender transmits only one bit, an error may be impossible to detect. But if the sender transmits repeated or structured bits, the receiver may be able to infer the intended message. For example, to send one bit, use the repetition code:

If the receiver gets 001, it may guess that 000 was sent, because only one bit appears corrupted. This is a simple error-correcting code. It uses extra symbols, called redundancy, to make communication more reliable.

But redundancy has a cost: it lowers the rate. If one message bit is transmitted using three channel bits, the rate is \(1/3\) message bits per channel use. Shannon’s noisy channel coding theorem shows that this tradeoff has a precise limit. For a channel, there is a number called its capacity, and reliable communication is possible at rates below capacity and impossible at rates above capacity, under the standard asymptotic assumptions of the theorem (Shannon, 1948; Gallager, 1968).

This is one of the deepest messages of the subject:

Noise does not make reliable communication impossible. It imposes a maximum reliable rate.

The meaning of capacity

The word capacity has an everyday meaning: how much something can hold. In Shannon theory, channel capacity is the largest rate at which information can be transmitted with probability of error approaching zero, when arbitrarily long codes are allowed.

For a discrete memoryless channel, capacity is expressed using mutual information:

\[ C = \max_{p(x)} I(X;Y). \]

This formula will be developed later. For now:

• \(X\) represents the channel input.
• \(Y\) represents the channel output.
• \(I(X;Y)\) measures how much observing \(Y\) tells us about \(X\), on average.
• The maximization over \(p(x)\) means that the sender may choose the best input distribution for the channel.

Mutual information is central because communication is successful only when the channel output preserves information about the channel input. If \(Y\) is independent of \(X\), then the output tells us nothing about the input. If \(Y\) nearly determines \(X\), then the channel can carry information well.

Capacity is not merely a formula. It is a boundary between possible and impossible performance. Practical systems may fail to reach capacity because of finite block length, complexity limits, imperfect modeling, delay constraints, or implementation losses. Shannon theory tells us what the ideal limit is, not automatically how to build the best practical system. Modern communication engineering often uses Shannon capacity as a benchmark for code and system design (Gallager, 1968; MacKay, 2003).

Long blocks and asymptotic thinking

Many results in this book concern what happens when messages are encoded in long blocks. A block is a finite sequence of symbols treated as one unit. For example, instead of compressing one letter at a time, we may compress a block of \(n\) letters. Instead of transmitting one bit at a time, we may encode \(k\) message bits into \(n\) channel input symbols.

Why use long blocks? Because long random sequences often become statistically regular. This may sound paradoxical: randomness becomes regular. The point is not that the exact sequence becomes predictable. Rather, the overall pattern of frequencies becomes predictable.

For example, if a fair coin is tossed many times, we cannot predict the exact sequence:

\[ HTTHTHHHTT\cdots \]

But we can expect the fraction of heads to be close to \(1/2\) for a large number of tosses. Shannon theory uses this type of regularity through the idea of typical sequences. Roughly speaking, typical sequences are the long sequences whose statistical behavior resembles the probability model of the source.

The asymptotic equipartition property, often abbreviated AEP, says that for many common source models, long random sequences behave as though they were drawn nearly uniformly from a set of about

\[ 2^{nH} \]

typical sequences, where \(H\) is the entropy per symbol and \(n\) is the block length. This idea gives a powerful intuitive path to source coding: if most likely length-\(n\) messages lie in a set of size about \(2^{nH}\), then about \(nH\) bits are enough to describe them. The AEP is a standard organizing principle in information theory and will be studied carefully in Chapter 8 (Cover & Thomas, 2006).

What this book will build

This book follows a gradual path.

We begin with Shannon’s abstraction of communication systems: sources, encoders, channels, decoders, destinations, noise, reliability, and efficiency. Then we develop the probability needed to reason about uncertain messages. After that, we define self-information, entropy, conditional entropy, mutual information, and relative entropy.

With those tools, we study two major limits:

1. The source coding limit: how much data can be compressed without losing information.
2. The channel coding limit: how fast data can be transmitted reliably over a noisy channel.

Then we connect the theory to practical coding methods, continuous channels, Gaussian noise, bandwidth-power tradeoffs, rate-distortion theory, sources with memory, and modern applications.

The book is not only about formulas. It is about learning how to think in Shannon’s style:

• model uncertainty with probability;
• measure information in bits;
• separate representation from meaning;
• distinguish what is possible in principle from what is practical in a real system;
• use long-block behavior to reveal fundamental limits.

A first mental model

Keep this picture in mind as you read:

\[ \text{Source} \longrightarrow \text{Encoder} \longrightarrow \text{Channel} \longrightarrow \text{Decoder} \longrightarrow \text{Destination}. \]

The source selects a message. The encoder turns the message into a signal or sequence of symbols. The channel may disturb it. The decoder tries to reconstruct the message. The destination receives the result.

A text message sent through a mobile network fits this model. So does a file written to a flash drive and read later. So does a spacecraft sending measurements back to Earth. The physical details differ, but the mathematical structure is similar.

That is the promise of Shannon theory: it gives a common language for compression, transmission, uncertainty, noise, and reliability.

We now begin with the first step: communication as a mathematical problem.

References

Cover, T. M., & Thomas, J. A. (2006). Elements of Information Theory (2nd ed.). Wiley-Interscience.

Gallager, R. G. (1968). Information Theory and Reliable Communication. Wiley.

MacKay, D. J. C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press.

Shannon, C. E. (1948). A mathematical theory of communication. Bell System Technical Journal, 27(3), 379–423; 27(4), 623–656.