跳到正文
The Lumenary
本科高年级Applied Mathematics课程已上线

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

打开课程 显示到达此主题所需的全部内容

前置知识

Probability theory

41 项必需的前置知识（一直追溯到底）

你将学会

  • 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.

定义

  • 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.

定理

  • 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.

常见误解

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

可选发现

学习路径

延伸阅读

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