Skip to content
The Lumenary
Advanced undergraduateApplied MathematicsPlanned

Information theory

Entropy and information, Shannon's source coding theorem, prefix codes and Huffman coding, mutual information, channel capacity and the noisy-channel coding theorem.

math.applied.information-theory

Show everything needed to reach this topic

The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.

Builds on

Probability theory

Required prerequisites, all the way down: 41

You will learn to

  • Compute entropy, joint and conditional entropy, and mutual information.
  • Construct Huffman codes and prove Kraft's inequality.
  • State the source coding and noisy-channel coding theorems and compute the capacity of the binary symmetric channel.

Definition

  • The entropy of a discrete random variable X is H(X) = −Σ p(x) log₂ p(x).
  • The mutual information of X and Y is I(X; Y) = H(X) − H(X | Y).
  • The capacity of a channel is the maximum of I(X; Y) over all input distributions.

Theorem

  • The expected length of an optimal binary prefix code for X lies between H(X) and H(X) + 1 bits.
  • Kraft: a binary prefix code with codeword lengths ℓᵢ exists if and only if Σ 2^(−ℓᵢ) ≤ 1.
  • The binary symmetric channel with crossover probability p has capacity 1 − H(p).
  • Noisy-channel coding theorem: reliable communication is possible at every rate below capacity and impossible at rates above it.

Common misconceptions

  • Equating information with meaning; Shannon information measures uncertainty.
  • Thinking a compression method can shrink every file.

Optional discoveries

Learning pathways

Further reading

  • Thomas M. Cover and Joy A. Thomas, Elements of Information Theory (1991)
  • David J. C. MacKay, Information Theory, Inference, and Learning Algorithms (2003)