Overview
The Mathematical Theory of Communication, commonly known as information theory, is a branch of applied mathematics and electrical engineering pioneered by Claude Shannon in his 1948 paper of the same name. It quantifies the fundamental limits of data compression, reliable communication, and signal processing through concepts such as entropy, channel capacity, and coding theorems. The theory provides a rigorous framework for measuring information, modeling noisy channels, and designing efficient codes, and it underpins modern digital communication systems, data storage, and cryptography.
1 Fundamental Concepts
1.1 Definition of Information
1.1.1 Messages and Signals
In information theory, a message is a sequence of symbols drawn from a finite alphabet, intended to convey meaning between a source and a destination. A signal is the physical representation of that message, such as an electrical voltage, radio wave, or light pulse, used to transmit it over a medium.
1.1.2 Uncertainty and Surprise
Information is quantified not by the semantic content of a message but by the uncertainty it resolves. The less probable an event, the more surprising it is, and thus the more information it conveys. This notion is formalized as the self-information of an event, measured in bits: \( I(x) = \log_2(1/p(x)) \).
1.2 Shannon’s Communication System Model
1.2.1 Source, Encoder, Channel, Decoder, Destination
Shannon’s model consists of five elements: an information source that produces messages; an encoder that converts the message into a signal; a channel over which the signal is transmitted; a decoder that reconstructs the message from the received signal; and a destination that receives the message. This abstraction captures the essential features of any communication system.
1.2.2 Noise and Distortion
A channel may introduce noise, which randomly alters the transmitted signal, or distortion, which deterministically corrupts it. The receiver must compensate for these impairments using error-correcting codes or signal processing to recover the original message.
1.3 Entropy
1.3.1 Discrete Entropy Formula
The entropy \( H(X) \) of a discrete random variable \( X \) with probability distribution \( p(x) \) is defined as \( H(X) = -\sum_{x} p(x) \log_2 p(x) \). It represents the average number of bits needed to optimally encode outcomes from \( X \).
1.3.2 Properties of Entropy
1.3.2.1 Non‑negativity and Maximum Entropy
| Entropy is always non‑negative and equals zero only when the outcome is deterministic. For a given set of possible outcomes, entropy is maximized when the distribution is uniform, achieving \( H_{\max} = \log_2 | \mathcal{X} | \). |
|---|
1.3.3 Joint and Conditional Entropy
| Joint entropy \( H(X,Y) \) measures the uncertainty of a pair of random variables, while conditional entropy \( H(Y | X) \) quantifies the remaining uncertainty about \( Y \) given knowledge of \( X \). |
|---|
1.3.3.1 Chain Rule for Entropy
| The chain rule states that \( H(X,Y) = H(X) + H(Y | X) \), generalizing to any number of variables. It provides a recursive way to decompose joint uncertainty. |
|---|
1.4 Mutual Information
1.4.1 Definition and Interpretation
| Mutual information \( I(X;Y) \) measures the reduction in uncertainty about one variable due to knowledge of the other: \( I(X;Y) = H(X) – H(X | Y) = H(Y) – H(Y | X) \). It quantifies the shared information between \( X \) and \( Y \). |
|---|
1.4.2 Relationship with Entropy
Mutual information is symmetric, non‑negative, and bounded by the individual entropies: \( 0 \le I(X;Y) \le \min(H(X), H(Y)) \). When \( X \) and \( Y \) are independent, \( I(X;Y)=0 \); when one determines the other, it equals the entropy of the determined variable.
2 Source Coding and Data Compression
2.1 Source Coding Theorem
2.1.1 Lossless Compression
Shannon’s source coding theorem states that a discrete source with entropy \( H \) can be compressed losslessly to an average code length arbitrarily close to \( H \) bits per symbol, but not below it. This establishes the theoretical limit for lossless compression.
2.1.2 Lossy Compression
When some degradation is acceptable, the source can be compressed to a lower rate at the cost of distortion. The rate‑distortion function (see §4.1) gives the minimum rate needed to achieve a given distortion level.
2.2 Variable‑Length Codes
2.2.1 Prefix Codes (Kraft Inequality)
A prefix code is a set of codewords where no codeword is a prefix of another. The Kraft inequality \( \sum 2^{-l_i} \le 1 \) (where \( l_i \) are codeword lengths) provides a necessary and sufficient condition for the existence of such a code.
2.2.2 Huffman Coding
Huffman coding is an optimal prefix code for a given probability distribution. It constructs a binary tree by repeatedly merging the two least probable symbols, achieving the minimum average code length among all prefix codes.
2.3 Universal Source Coding
2.3.1 Lempel‑Ziv Algorithms
Lempel‑Ziv algorithms (e.g., LZ77, LZ78) are universal compression methods that build a dictionary of repeated patterns. They do not require knowledge of the source statistics and achieve asymptotically optimal compression for stationary ergodic sources.
2.3.2 Arithmetic Coding
Arithmetic coding represents a message as an interval within [0,1), mapping the entire sequence to a single fractional number. It can achieve near‑entropy compression for arbitrary source models and is often used in combination with other techniques.
3 Channel Coding and Capacity
3.1 Channel Models
3.1.1 Discrete Memoryless Channel
| A discrete memoryless channel (DMC) is defined by an input alphabet \( \mathcal{X} \), an output alphabet \( \mathcal{Y} \), and a transition probability matrix \( p(y | x) \). The output depends only on the current input (memoryless property). |
|---|
3.1.2 Binary Symmetric Channel
| The binary symmetric channel (BSC) has binary inputs and outputs, with crossover probability \( p \): \( p(0 | 1)=p(1 | 0)=p \). It is a simple but widely used model for symmetric noise. |
|---|
3.1.3 Gaussian Channel
The additive white Gaussian noise (AWGN) channel adds independent Gaussian noise to the input signal. The output is continuous, and the channel is characterized by the signal‑to‑noise ratio (SNR).
3.2 Channel Capacity
3.2.1 Definition and Formula
Channel capacity \( C \) is the maximum mutual information between input and output over all possible input distributions: \( C = \max_{p(x)} I(X;Y) \). It represents the highest rate at which information can be transmitted with arbitrarily low error probability.
3.2.2 Capacity of Common Channels
3.2.2.1 Binary Symmetric Channel Capacity
For the BSC with crossover probability \( p \), the capacity is \( C = 1 – H(p) \) bits per channel use, where \( H(p) = -p \log_2 p – (1-p) \log_2(1-p) \) is the binary entropy function.
3.2.2.2 Additive White Gaussian Noise (AWGN) Capacity
For an AWGN channel with average power constraint \( P \) and noise variance \( N_0/2 \), the capacity is \( C = \frac{1}{2} \log_2\left(1 + \frac{2P}{N_0}\right) \) bits per symbol, known as the Shannon–Hartley theorem.
3.3 Channel Coding Theorem
3.3.1 Existence of Good Codes
Shannon’s channel coding theorem proves that for any rate \( R < C \), there exists a sequence of codes achieving arbitrarily small error probability as the block length increases. Conversely, for \( R > C \) reliable communication is impossible.
3.3.2 Error Probability and Rate
The theorem does not provide a constructive code but guarantees existence. The error probability can be made to decay exponentially with block length for rates below capacity, as quantified by the error exponent.
3.4 Error‑Correcting Codes
3.4.1 Block Codes (Hamming, Reed–Solomon)
Block codes map a fixed‑length block of input symbols to a longer codeword. Hamming codes are simple linear block codes that can correct single errors. Reed–Solomon codes, based on finite fields, correct multiple symbol errors and are used in CDs and QR codes.
3.4.2 Convolutional Codes
Convolutional codes process input sequences through shift registers, producing a continuous stream of encoded bits. They are commonly decoded using the Viterbi algorithm, which finds the most likely transmitted sequence.
3.4.3 Turbo and LDPC Codes
Turbo codes and low‑density parity‑check (LDPC) codes approach the Shannon limit through iterative decoding. Turbo codes use parallel concatenation with interleavers, while LDPC codes employ sparse parity‑check matrices and belief propagation. Both are widely used in modern communication standards.
4 Advanced Topics
4.1 Rate‑Distortion Theory
4.1.1 Rate‑Distortion Function
| The rate‑distortion function \( R(D) \) gives the minimum rate needed to achieve an expected distortion \( D \) for a given source. It is defined as the infimum of mutual information \( I(X;\hat{X}) \) over all conditional distributions \( p(\hat{x} | x) \) satisfying a distortion constraint. |
|---|
4.1.2 Lossy Compression Bounds
Rate‑distortion theory provides the theoretical limits for lossy compression algorithms such as JPEG (image) and MP3 (audio). For example, the Gaussian source’s rate‑distortion function under mean‑squared error is \( R(D) = \frac{1}{2} \log_2(\sigma^2/D) \) for \( D \le \sigma^2 \).
4.2 Network Information Theory
4.2.1 Multiple Access Channels
In a multiple access channel (MAC), multiple senders communicate to a single receiver. The capacity region is a convex set of achievable rate tuples, often characterized by constraints like \( R_1 + R_2 \le C_{12} \).
4.2.2 Broadcast Channels
A broadcast channel has one sender and multiple receivers. The capacity region depends on whether receivers can cooperate or not. The degraded broadcast channel is one of the few cases with a complete characterization.
4.2.3 Relay Channels
Relay channels involve a relay node that helps the source communicate to the destination. The capacity is generally unknown, but strategies such as decode‑and‑forward and compress‑and‑forward provide achievable rates.
4.3 Entropy Rate and Stochastic Processes
4.3.1 Markov Chains and Entropy Rate
For a stationary stochastic process, the entropy rate is the limit of the joint entropy per symbol: \( H(\mathcal{X}) = \lim_{n\to\infty} \frac{1}{n} H(X_1,\ldots,X_n) \). For a Markov chain, it simplifies to the conditional entropy of the next state given the current one.
4.3.2 Source with Memory
Sources with memory (e.g., text, speech) have dependencies between symbols that reduce their entropy rate below the per‑symbol entropy. This is exploited by compression algorithms that model context, such as prediction by partial matching (PPM).
4.4 Applications
4.4.1 Data Storage and Compression (ZIP, JPEG)
Entropy coding is fundamental to file compressors like ZIP (using Huffman or LZ77) and image formats like JPEG (using Huffman or arithmetic coding on transformed coefficients).
4.4.2 Cryptography (Secrecy Capacity)
Information‑theoretic security models the secrecy capacity as the maximum rate at which a message can be transmitted confidentially over a wiretap channel, preventing an eavesdropper from extracting information.
4.4.3 Machine Learning and Statistical Inference
Mutual information and entropy are used in feature selection, decision tree induction, and variational inference. The information bottleneck method and maximum entropy principles guide model design in classification and clustering tasks.