本科高年级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
本主题的课程尚未编写。下面的提纲是课程地图的一部分，尚未经过审校。
前置知识
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)