Information theory - Ciallo Wiki

Information theory is a branch of applied mathematics and electrical engineering that quantifies the storage, transmission, and processing of information. Founded by Claude Shannon in his 1948 paper "A Mathematical Theory of Communication," it provides a rigorous framework for measuring information content (entropy), data compression (source coding), and reliable communication over noisy channels (channel coding). Its core concepts underpin modern digital communications, data compression algorithms (e.g., ZIP, JPEG), cryptography, and machine learning, influencing fields from linguistics to neuroscience.

1 Introduction

1.1 Historical background

The origins of information theory lie in earlier developments in telegraphy, telephony, and probability theory. In the 1920s, Harry Nyquist and Ralph Hartley at Bell Labs laid groundwork by relating the transmission rate to bandwidth and signal levels. However, it was Claude Shannon who, in 1948, synthesized these ideas into a unified mathematical theory. His work addressed both the fundamental limits of data compression and reliable communication, establishing entropy as the core measure of information. The theory quickly found applications in cryptography (Shannon's 1949 paper on communication theory of secrecy systems) and later expanded into computing, statistics, and physics.

1.2 Basic elements of a communication system

1.2.1 Source, encoder, channel, decoder, destination

A generic communication system consists of five parts. The source produces a message (e.g., a text, an image). The encoder transforms the message into a signal suitable for transmission, often adding redundancy for error protection. The channel is the physical medium (e.g., wire, radio) that may introduce noise or distortion. The decoder reverses the encoding, attempting to recover the original message. The destination is the intended receiver. Information theory studies optimal designs for each component under given constraints.

1.2.2 The role of uncertainty and probability

Uncertainty is central to information theory. The amount of information in a message is measured by how much uncertainty it resolves. This requires a probabilistic model of the source or channel. For example, a message from a source with equally likely outcomes conveys more information than one from a biased source. Similarly, a noisy channel introduces uncertainty about what was transmitted. Probability distributions thus underlie all core concepts.

2 Core Concepts

2.1 Entropy and information content

2.1.1 Shannon entropy

2.1.1.1 Definition for discrete random variables

For a discrete random variable *X* with possible outcomes *x*1, …, *x*n and probability distribution *p*(*x*), the Shannon entropy *H*(*X*) is defined as *H*(*X*) = –∑i *p*(*x*i) log2 *p*(*x*i), measured in bits. If the logarithm base is *e*, the unit is nats. The entropy is zero if one outcome is certain, and maximum when all outcomes are equally likely.

2.1.1.2 Relationship to surprise and average uncertainty

Entropy can be interpreted as the average "surprise" (or uncertainty) associated with the random variable. The surprise of an outcome *x* is –log *p*(*x*); entropy is the expectation of that quantity. A highly predictable source has low entropy, whereas an unpredictable one has high entropy.

2.1.2 Joint and conditional entropy

The joint entropy H(X,Y) of two random variables is defined analogously using their joint distribution. Conditional entropy H(Y	X) measures the remaining uncertainty about Y given knowledge of X: H(Y	X) = H(X,Y) – H(X). These quantities obey the chain rule H(X,Y) = H(X) + H(Y	X).

2.1.3 Relative entropy (Kullback–Leibler divergence)

The Kullback–Leibler divergence *D*(*P*‖*Q*) measures the inefficiency of assuming distribution *Q* when the true distribution is *P*. For discrete *P* and *Q*, *D*(*P*‖*Q*) = ∑ *p*(*x*) log [*p*(*x*)/*q*(*x*)]. It is nonnegative and zero only if *P* = *Q* almost everywhere. It is not a metric (asymmetric), but it is fundamental to statistical inference and coding.

2.1.4 Mutual information

2.1.4.1 Definition and properties

Mutual information I(X;Y) quantifies the amount of information shared between X and Y: I(X;Y) = H(X) – H(X	Y) = H(Y) – H(Y	X) = D(P<sub>XY</sub>‖P<sub>X</sub>P<sub>Y</sub>). It is symmetric, nonnegative, and zero if and only if X and Y are independent.

2.1.4.2 Relation to correlation and independence

Mutual information is a more general measure of dependence than linear correlation: it captures any statistical relationship, not just linear ones. For Gaussian variables, mutual information is a monotonic function of the correlation coefficient. Independence implies zero mutual information, but zero mutual information does not guarantee independence in the sense of all joint moments—though it does mean the distributions factorize.

2.2 Source coding (data compression)

2.2.1 Lossless compression

2.2.1.1 Prefix codes and Kraft inequality

A prefix code is a set of codewords such that no codeword is a prefix of another. The Kraft inequality gives a necessary and sufficient condition for the existence of a prefix code with given codeword lengths *l**i*: ∑ 2–*l**i* ≤ 1. If equality holds, the code is complete. Prefix codes are uniquely decodable without lookahead.

2.2.1.2 Huffman coding

Huffman coding produces an optimal prefix code for a given symbol probability distribution. The algorithm builds a binary tree by repeatedly merging the two least probable symbols, assigning shorter codewords to more frequent symbols. The resulting code achieves an average codeword length within one bit of the source entropy.

2.2.1.3 Arithmetic coding

Arithmetic coding encodes a sequence of symbols into a single fractional number in [0,1). It partitions the interval according to symbol probabilities, updating the range as each symbol is processed. It can achieve near-optimal compression for any source, with no need for integer-length codewords per symbol. It is widely used in formats like JPEG and ZIP.

2.2.2 Lossy compression

2.2.2.1 Rate–distortion theory

Rate–distortion theory deals with compressing a source when some distortion is allowed. Given a distortion measure *d*(*x*,*x̂*), the rate–distortion function *R*(*D*) is the minimum bit rate needed to achieve average distortion ≤ *D*. It generalizes entropy to lossy settings and provides fundamental limits for codec design.

2.2.2.2 Quantization and perceptual coding

Quantization maps a continuous or high-resolution signal to a finite set of levels, introducing loss. Scalar quantization assigns a single threshold; vector quantization considers blocks. Perceptual coding exploits the limits of human senses (e.g., hearing, vision) to allocate bits where distortions are least noticeable. Examples include MP3 audio (psychoacoustic model) and JPEG (discrete cosine transform with quantization tables).

2.3 Channel capacity

2.3.1 Noisy channel coding theorem

Shannon's noisy channel coding theorem states that for any discrete memoryless channel with capacity *C* (bits per channel use), there exist codes that allow reliable communication at any rate *R* < *C* (with arbitrarily low error probability as block length increases). Conversely, rates above *C* are impossible. This fundamental limit is achieved by random coding and typical-set decoding.

2.3.2 Capacity of discrete memoryless channels

2.3.2.1 Binary symmetric channel

The binary symmetric channel (BSC) flips each bit with crossover probability *p* (and transmits correctly with probability 1 – *p*). Its capacity is *C* = 1 – *H*(*p*) bits per use, where *H*(*p*) = –*p* log *p* – (1–*p*) log (1–*p*) is the binary entropy function.

2.3.2.2 Binary erasure channel

The binary erasure channel (BEC) either delivers the input bit correctly or erases it (reports an erasure symbol "?") with probability *ε*. The capacity is *C* = 1 – *ε* bits per use, since the non-erased bits are known perfectly.

2.3.3 Continuous channels (AWGN)

The additive white Gaussian noise (AWGN) channel has input *X*, output *Y* = *X* + *Z*, where *Z* is zero-mean Gaussian noise with variance *N*0/2 per dimension. With an average power constraint *P*, the capacity is *C* = (1/2) log(1 + *P*/*N*) bits per channel use (for real signals) or *C* = log(1 + *P*/*N*) for complex signals (where *N* is noise power per dimension).

2.3.4 Capacity per unit cost

In many practical systems, resources such as energy or time are costly. Capacity per unit cost measures the maximum number of bits that can be transmitted reliably per unit of a given resource (e.g., energy per bit). For the AWGN channel, the minimal energy per bit is –1.59 dB (the Shannon limit). This concept guides the design of power-efficient communication systems.

3 Advanced Topics

3.1 Multiterminal information theory

3.1.1 Network coding

3.1.1.1 Butterfly network example

The classic butterfly network consists of two sources sending messages to two destinations via a shared relay link. Without network coding, the relay cannot simultaneously forward both messages without collisions. With linear network coding, the relay broadcasts the XOR of the two messages, allowing each destination to decode its desired message. This shows that in-network processing can increase throughput beyond traditional routing.

3.1.1.2 Linear network coding

Linear network coding treats messages as vectors over a finite field. Each node transmits linear combinations of received packets. The resulting capacity region achieves the max-flow min-cut bound for multicast traffic, and decoding is performed by solving linear equations. It is used in practical systems like peer-to-peer file sharing and wireless relays.

3.1.2 Multiple-access channels

A multiple-access channel (MAC) has several independent transmitters and one common receiver. The capacity region is the set of achievable rate tuples, characterized by constraints on sums of rates. For the Gaussian MAC with power constraints, the capacity region is a pentagon determined by the total power and noise.

3.1.3 Broadcast channels

The broadcast channel (BC) has one transmitter and multiple receivers. Its capacity region is harder to find; a superposition coding scheme achieves the "capacity region" for degraded BCs (e.g., AWGN with different noise levels). General BC capacity remains a subject of research.

3.1.4 Relay channels

A relay channel has a source, a destination, and an intermediate node (relay) that helps transmission. The capacity is not fully known in general, but decode-and-forward and compress-and-forward strategies provide lower bounds. The relay can improve rate and reliability.

3.2 Information theory and statistics

3.2.1 Fisher information

Fisher information is a key concept in estimation theory and is related to the curvature of the log-likelihood function. It appears in the Cramér–Rao bound, which lower-bounds the variance of unbiased estimators. There is a formal connection with mutual information via the de Bruijn identity.

3.2.2 Minimum description length principle

The minimum description length (MDL) principle selects models that minimize the total description length of data and model. It is rooted in Kolmogorov complexity and Shannon coding: a model that compresses data well is likely to capture its true regularities. MDL is used in machine learning, hypothesis testing, and regression.

3.2.3 Information geometry

Information geometry studies statistical manifolds where each point represents a probability distribution. Fisher information defines a Riemannian metric (the Fisher–Rao metric) on such manifolds. Key concepts include geodesics, the α-divergence (which includes Kullback–Leibler divergence), and natural gradient descent for machine learning.

3.3 Information theory in computing

3.3.1 Algorithmic information theory (Kolmogorov complexity)

Kolmogorov complexity (or algorithmic entropy) quantifies the amount of information in a binary string by the length of the shortest program that outputs it. Unlike Shannon entropy, it does not assume a known probability distribution. It is a fundamental concept in computability theory and provides a definition of randomness.

3.3.2 Kolmogorov complexity and randomness

A string is algorithmically random if its Kolmogorov complexity is close to its length—i.e., it cannot be significantly compressed. This notion of randomness is tied to Martin-Löf randomness and statistical tests. Most strings are random, but fewer are provably so.

3.3.3 Independence, conditional Kolmogorov complexity

Conditional Kolmogorov complexity K(x	y) is the length of the shortest program that outputs x given y as an input. Mutual algorithmic information I(x;y) = K(x) – K(x	y) measures the algorithmic similarity. It can capture hidden regularities not evident from probabilistic models.

3.4 Quantum information theory

3.4.1 Quantum entropy (von Neumann entropy)

The quantum analog of Shannon entropy is the von Neumann entropy *S*(*ρ*) = –Tr(*ρ* log *ρ*), where *ρ* is a density matrix (quantum state). It measures the mixedness of a quantum system. For a pure state, *S* = 0; for a maximally mixed state, it is log *d* (where *d* is dimension).

3.4.2 Quantum channel capacity

Quantum channels (e.g., depolarizing, amplitude damping) have various capacities: classical capacity, quantum capacity, and private classical capacity. The capacities are often expressed using coherent information and Holevo quantities. The classical capacity of a quantum channel is given by the Holevo–Schumacher–Westmoreland theorem.

3.4.3 Quantum error correction

Quantum error correction (QEC) protects quantum information against decoherence and operational errors. Examples include the Shor code (nine qubits) and the Steane code (seven qubits). QEC is essential for building reliable quantum computers. The quantum error-correcting codes are analogous to classical codes but must treat superposition and entanglement.

4 Applications

4.1 Telecommunications and networking

4.1.1 Error-correcting codes (Hamming, Reed–Solomon, LDPC, turbo)

Error-correcting codes add redundancy to correct errors introduced by noisy channels. Hamming codes are simple single-error correcting codes (e.g., (7,4)). Reed–Solomon codes are powerful for burst errors, used in CDs, QR codes, and satellite communication. Low-density parity-check (LDPC) codes achieve performance near the Shannon limit and are used in Wi-Fi (802.11n/ac/ax) and DVB. Turbo codes (parallel concatenated convolutional codes) also approach capacity and are used in 3G/4G mobile networks.

4.1.2 Modulation and coding schemes

Modern communication systems combine modulation and coding into modulation and coding schemes (MCS). For example, in Wi-Fi, rates are chosen adaptively based on channel quality (e.g., QPSK 1/2, 64-QAM 5/6). Information theory guides optimal power allocation (water-filling) and adaptive modulation to maximize throughput.

4.2 Data compression in practice

4.2.1 Lossless: ZIP, PNG, FLAC

ZIP uses LZ77 and Huffman coding; PNG uses LZ77 with filtering; FLAC uses linear prediction and Rice coding. All exploit redundancy in data (repeating patterns, correlations) to reduce size without loss.

4.2.2 Lossy: JPEG, MP3, video codecs

JPEG compresses images using DCT, quantization, and Huffman/arithmetic coding. MP3 uses a perceptual model based on the human auditory system (masking), plus Huffman coding. Video codecs (H.264, HEVC, AV1) use motion compensation, transform coding, and entropy coding, guided by rate–distortion optimization.

4.3 Cryptography and security

4.3.1 Perfect secrecy and the one-time pad

Shannon proved that perfect secrecy—where the ciphertext reveals nothing about the plaintext—requires a key at least as long as the message, and that the key must be used only once. The one-time pad (XOR with a truly random key) achieves this. Information theory provides the measure of uncertainty (equivocation) to characterize security.

4.3.2 Entropy as a measure of randomness

Entropy is used to quantify the unpredictability of cryptographic keys, passwords, and random number generators. A high-entropy source is essential for secure keys. Min-entropy (instead of Shannon entropy) is often used in side-channel analysis and physical unclonable functions.

4.4 Machine learning and artificial intelligence

4.4.1 Maximum entropy models

Maximum entropy (MaxEnt) models choose the probability distribution that maximizes entropy subject to observed constraints (e.g., expected feature values). This yields the least biased distribution consistent with data. Examples include logistic regression and conditional random fields.

4.4.2 Variational inference and information bottleneck

Variational inference uses the evidence lower bound (ELBO), which involves Kullback–Leibler divergence, to approximate intractable posterior distributions. The information bottleneck method extracts a compressed representation *Z* from input *X* that retains maximal mutual information with output *Y*. It has been applied to deep learning to improve generalization and interpretability.

4.4.3 Mutual information in feature selection

Mutual information between a feature and the target variable is used to rank or select informative features for classification/regression. Conditional mutual information helps remove redundant features. This approach is model-agnostic and captures non-linear dependencies.

5.1 Connections to thermodynamics and physics

5.1.1 Maxwell’s demon and Landauer’s principle

Maxwell's demon thought experiment (sorting molecules using a "demon") seemed to violate the second law of thermodynamics. Later analyses showed that the demon must perform measurements and store information, and that erasing that information costs energy (Landauer's principle). The minimal energy to erase one bit is *k*B*T* ln 2. This links information theory to thermodynamics.

5.1.2 Statistical mechanics and entropy

The thermodynamic entropy *S* = *k*B ln Ω (where Ω is the number of microstates) is analogous to Shannon entropy. Formal connections exist in the Gibbs and Boltzmann distributions. Information theory has been used to derive thermodynamic laws and to analyze fluctuation theorems.

5.2 Information theory and biology

5.2.1 Neural coding and information flow

Neurons encode information in spike trains. Mutual information measures how much a stimulus can be decoded from neural responses. Single-neuron and population coding efficiencies are studied, affecting models of sensory systems (e.g., retina, auditory nerve). The capacity of neural channels is debated.

5.2.2 DNA as a storage medium

DNA can store vast amounts of data (up to 1018 bytes per gram). Information theory is used to design error-correcting codes for DNA storage (e.g., Reed–Solomon codes) and to analyze the capacity of DNA channels (with synthesis errors, deletions, and mutations). Recent experiments have stored texts, images, and even operating systems in DNA.

5.3 Open problems and current research

5.3.1 Capacity of wireless networks

Determining the exact capacity region of general ad hoc wireless networks remains open. While single-hop point-to-point capacity is well understood, the interference-limited multi-user scenario (with multiple nodes, fading, and mobility) lacks a comprehensive closed-form solution. Current work focuses on scaling laws, interference alignment, and network coding.

5.3.2 Finite-blocklength information theory

Classical information theory often assumes asymptotically long block lengths to achieve capacity. Finite-blocklength analysis provides tighter bounds on achievable rates for short blocks, essential for low-latency communication (e.g., in 5G and Internet of Things). The dispersion of a channel quantifies the penalty for finite length.

5.3.3 Semantic information theory

Shannon's theory ignores the meaning of messages. Semantic information theory (pioneered by Bar-Hillel, Carnap, and more recently by Floridi and others) aims to account for context, relevance, and truth. Practical approaches include joint source–channel coding with side information and applications in natural language understanding. This is an active interdisciplinary research area.