English
Information theory studies the limits of representing and transmitting uncertain data. How many bits are needed to describe outputs from a source? How much information can pass through a noisy channel reliably? The answers depend on a probability model, the allowed error, and the resources or constraints of the channel.
Here, information measures distinguishability and uncertainty, rather than truth or usefulness. A random bit can have maximal entropy without telling you anything about tomorrow’s weather. Conversely, a short, highly predictable message may be important to its recipient. Separating these questions makes the mathematics useful without asking it to measure every meaning of “information.”
Start with probability, expectation, conditional distributions, and logarithms (§2.5). This section connects those concepts to codes and communication, then explains their uses and limits in statistical modeling. A logarithm to base two gives units of bits; changing the base changes the unit.
How the Concept of Information Became Precise
Telegraphy and telephony raised practical questions about signaling speed, bandwidth, and noise before information theory became a unified subject. Nyquist studied transmission limits, and Hartley used a logarithmic measure of the number of possible messages. Shannon’s 1948 work combined probabilistic source descriptions with coding and channel models, giving precise achievable limits and converses.
One major change was to distinguish selecting a message from the meaning assigned to it. A communication system must reproduce the selected signal even when it does not understand the content. This abstraction allowed speech, text, and other sources to be studied through common models. Shannon’s earlier work connecting switching circuits to Boolean algebra addressed a different question: how to implement logical relations in circuits.
Coding research then developed methods that approach the limits under particular conditions. Huffman coding gives optimal binary prefix codes for individual symbols with a specified distribution. Arithmetic coding works with longer sequences and can avoid the per-symbol rounding cost. Error-correcting codes add structured redundancy so that a receiver can recover data despite noise. Source coding removes predictable redundancy; channel coding adds redundancy chosen for error recovery. Both can therefore appear in the same communication system.
Connections to statistics and computing expanded the subject. Algorithmic information theory asks about the length of a program describing an individual object, while statistical information theory begins with distributions over possible outcomes. Learning theory uses quantities such as entropy, cross-entropy, and mutual information to analyze prediction and representation. Their common mathematical vocabulary does not make every learning problem a solved coding problem.
Entropy, Channels, and the Geometry of Distributions
Keep the source, code, and channel distinct. The source model assigns probabilities to messages; the code chooses their representations; the channel model describes how transmitted symbols become observations. Entropy concerns the source, expected length concerns the code, and capacity concerns what the channel can support after optimizing the input distribution under its constraints.
Entropy and Its Extensions
For a discrete outcome with probability p, its self-information is −log₂ p. Independent probabilities multiply, so their self-information adds. Entropy is the average: H(X) = −Σₓ p(x) log₂ p(x), with zero-probability terms contributing zero. A fair coin has entropy one bit; a deterministic outcome has entropy zero. For a finite alphabet of size m, entropy is at most log₂ m, attained by the uniform distribution.
Conditional entropy averages the remaining uncertainty after observing another variable: H(X|Y). The chain rule H(X,Y) = H(Y) + H(X|Y) separates the cost of describing Y from the additional cost of describing X once Y is known. Mutual information is I(X;Y) = H(X) − H(X|Y). If Y copies a fair bit X, this is one bit; if they are independent, it is zero. The reduction is an average over observations: a particular unexpected observation can leave more uncertainty than the prior average.
Cross-entropy measures the average ideal code length when outcomes follow P but probabilities are assigned using Q: H(P,Q) = −Σₓ P(x) log₂ Q(x). Its excess over entropy is D_KL(P||Q). If Q assigns zero probability to an outcome that can occur under P, this excess is infinite. The distinction explains why an overconfident wrong prediction can be much more costly than a modestly uncertain one. KL divergence is asymmetric and is not a distance metric.
The data-processing inequality states that, for a Markov chain X → Y → Z, processing Y into Z cannot increase its mutual information with X. The Markov condition means that Z receives no additional information about X beyond Y. A feature transformation can still make existing information easier for a limited predictor to use. Adding an external database or a new measurement changes the available information and therefore the setup of the theorem.
Continuous variables need additional care. Differential entropy depends on coordinates: scaling a variable by a nonzero constant changes it by the logarithm of the scale magnitude, when the relevant entropies exist. It can be negative and is not the number of bits needed to record an exact real number. Quantization introduces a resolution; mutual information and KL divergence retain useful invariance under invertible changes of variables when defined appropriately.
In machine learning, these quantities describe particular objectives and assumptions. Cross-entropy training fits predicted probabilities to observed outcomes; it does not by itself guarantee calibration on a new distribution. A variational lower bound separates a model’s log likelihood into the bound and a nonnegative gap involving the approximate and true posterior. Contrastive objectives can relate to mutual-information bounds under their sampling assumptions. In each case, identify the distributions and the bound before attributing a broader learning guarantee to the formula.
Source Coding: Compression and Its Limits
For binary prefix codes of a finite discrete source, expected length L satisfies H(X) ≤ L, and there is a code with L < H(X)+1. A prefix code has no codeword that begins another, so concatenated codewords can be decoded without separators. Huffman coding minimizes expected length within this class for the supplied symbol probabilities.
Consider four symbols with probabilities 1/2, 1/4, 1/8, 1/8. Assign the codewords 0, 10, 110, 111. They are prefix-free, and their expected length is 1/2 × 1 + 1/4 × 2 + 1/8 × 3 + 1/8 × 3 = 1.75 bits, exactly the entropy. More likely symbols receive shorter codewords. The bound concerns an average over the source; individual messages can be longer or shorter.
Coding blocks of n independent symbols gives entropy nH(X) and reduces the less-than-one-bit rounding overhead per block to less than 1/n bit per symbol. For a finite independent identically distributed source, long sequences concentrate in a typical set whose size grows roughly as 2^(nH). Naming a typical sequence therefore takes about nH bits. Rare sequences still need to be handled, which is why precise coding theorems specify expected length or a vanishing error probability rather than claiming every length-n string fits into nH bits. Dependencies change the source entropy. If fair bits always occur in identical pairs, each individual bit has entropy one, but each pair has only one bit of uncertainty. A model that ignores the dependency misses available compression. Entropy rate describes the asymptotic uncertainty per symbol of a process when the limit exists.
Real files also carry model descriptions, headers, and finite-length overhead. No lossless compressor can shorten every possible input: there are too few shorter strings to represent them all uniquely. Arithmetic coding can approach the entropy rate when supplied with a suitable probabilistic model; it does not generally beat the entropy of that model on average. DEFLATE uses LZ77-style references together with Huffman coding, as specified in RFC 1951, rather than arithmetic coding.
Kolmogorov complexity asks for the shortest program that outputs a particular string on a fixed universal machine. It concerns an individual object, and its general value is uncomputable. Changing the reference universal machine changes complexity by at most an additive constant in the usual invariance theorem. Practical minimum-description-length methods instead compare computable descriptions from a chosen model class, accounting for both the model and the data encoded using it. They do not compute an unrestricted shortest program.
Lossy compression allows reconstruction error. Rate-distortion theory asks for the minimum asymptotic rate under a source model and a specified average distortion constraint. A squared-error distortion measure and a task-based notion of acceptable reconstruction may value different losses. Choosing what may be discarded is therefore part of the problem definition, not something entropy alone determines.
Channel Coding: Reliable Communication and Its Limits
A channel model specifies a conditional distribution P(Y|X) from transmitted input to received output. For a finite discrete memoryless channel, capacity is C = max_{P(X)} I(X;Y) bits per channel use. The maximization matters: a channel may convey more information under one input distribution than another. Memorylessness is also an assumption; channels with memory require a more general treatment.
A small code makes the role of redundancy concrete. Append a parity bit so that each transmitted block has an even number of 1s: data 101 becomes 1010. A single bit flip makes the total odd, revealing an error, but the parity check does not locate the damaged bit. Two flips restore even parity and go undetected. Detection and correction are different capabilities.
To correct any one bit flip in a three-bit block, encode 0 as 000 and 1 as 111, then decode by majority vote. Two or three flips produce the wrong answer. If bits flip independently with probability p, the decoding error probability is 3p²(1−p) + p³; at p=0.1, it is 0.028. The improvement costs three transmitted bits per data bit. Source coding removes redundancy to shorten a representation; channel coding adds structured redundancy to make corruption detectable or correctable.
The coding theorem states that rates below capacity permit codes whose error probability tends to zero as block length grows. Rates above capacity cannot achieve vanishing error under the model’s conditions. This is an asymptotic statement, not a guarantee of zero error for a short block or an efficient decoder at a chosen latency. The theorem distinguishes a fundamental limit from the engineering work of constructing a suitable code.
For a binary symmetric channel that independently flips each bit with probability p, capacity is 1−h₂(p), where h₂ is binary entropy. At p=0.1, capacity is about 0.531 bit per channel use. At p=0.5, the output is independent of the input and capacity is zero. At p=1, every bit is predictably reversed, so the receiver can reverse it back and capacity is one. The obstacle is uncertainty about the alteration, not alteration alone.
For a real-valued additive white Gaussian noise channel with average input power at most P and noise variance σ² per use, capacity is ½ log₂(1+P/σ²) bits per real channel use. The familiar bandlimited formula W log₂(1+SNR) uses bits per second with the corresponding bandwidth and power conventions. Units and channel assumptions are part of the formula; it is not a universal prediction of every wireless link’s observed throughput.
Error-correcting codes make different input messages produce sufficiently distinguishable transmitted sequences. A receiver uses that redundancy to infer the likely message after corruption. Block length, decoding complexity, latency, and the actual noise process all affect the resulting design. Shannon’s original paper establishes the role of probabilistic models and asymptotic coding limits; practical performance must be evaluated for the selected code and channel.
What Studying This Changes
The subject changes how you read a performance claim. For compression, ask about the source model, dependencies, code overhead, and allowed distortion. For communication, ask about units, channel assumptions, block length, and error probability. For learning, identify the distributions inside the loss and distinguish fitting those distributions from obtaining useful behavior on a new task.
Calculate the four-symbol code above, then compare coding individual bits with coding identical pairs. Simulate a small error-correcting code at several noise rates and measure its block error rate. Compare the code’s information rate with channel capacity, while keeping the asymptotic theorem separate from finite-block measurements. These exercises turn the limits into quantities that can be interpreted rather than slogans about compression or intelligence.
Resources
Books and Texts
Cover and Thomas’s Elements of Information Theory (2nd ed., Wiley, 2006) is the canonical mathematical reference. It covers entropy, mutual information, the source and channel coding theorems, rate-distortion theory, Kolmogorov complexity, and network information theory with full proofs and careful attention to technical conditions. It is rigorous and comprehensive — a primary reference for anyone who wants the full mathematical treatment. The notation and proof style are standard and will be recognized throughout the information theory literature.
MacKay’s Information Theory, Inference, and Learning Algorithms (Cambridge, 2003, free at inference.org.uk) is the alternative with a different emphasis. MacKay develops information theory in connection with Bayesian inference, error-correcting codes, and machine learning — making the connections to statistical learning explicit rather than treating information theory as a separate subject. The writing is clear and example-based for a technical textbook, and the book’s integration of information theory with inference and learning makes it a possible primary text for machine learning practitioners. It is both broader (covering neural networks, Monte Carlo methods, and approximate inference) and less technically complete than Cover-Thomas. The free availability and the ML focus make it the more commonly recommended starting point for CS learners.
Shannon’s A Mathematical Theory of Communication (1948) is a primary source for probabilistic source models, entropy, and noisy-channel coding. Read selected sections after working through an introductory explanation, and compare the assumptions of its models with the practical communication problem you have in mind.
For Kolmogorov complexity and algorithmic information theory, Li and Vitányi’s An Introduction to Kolmogorov Complexity and Its Applications (4th ed., Springer, 2019) is the standard reference. It covers Kolmogorov complexity, the incompressibility method, MDL, and the connections to computability and complexity theory with full rigor.
Blahut’s Algebraic Codes for Data Transmission develops algebraic coding, including BCH and Reed–Solomon codes. Richardson and Urbanke’s Modern Coding Theory develops modern probabilistic coding methods, including LDPC codes. Select a text according to whether you want the algebraic construction of codes or iterative decoding and performance analysis.
Moser and Chen’s A Student’s Guide to Coding and Information Theory (Cambridge, paid) is a short, accessible bridge from practical coding examples to entropy, mutual information, channel capacity, and the information transmission theorem. It is much less deep than Cover-Thomas and less ML-oriented than MacKay, but it is useful for learners who need the communication-and-coding intuition before the full mathematical treatment.
| Book | Role | Type |
|---|---|---|
| Cover & Thomas, Elements of Information Theory (2nd ed.) | Canonical mathematical reference | Reference |
| MacKay, Information Theory, Inference, and Learning Algorithms (free) | ML-oriented entry; unified treatment | Entry |
| Li & Vitányi, Introduction to Kolmogorov Complexity (4th ed.) | Algorithmic information theory | Depth |
| Richardson & Urbanke, Modern Coding Theory | LDPC and turbo codes | Depth |
| Shannon, “A Mathematical Theory of Communication” (1948, free) | Founding paper; historically central | Auxiliary |
| Moser & Chen, A Student’s Guide to Coding and Information Theory (paid) | Gentle coding-first bridge | Auxiliary |
Courses and Lectures
MIT 6.441 (Information Theory, free on MIT OCW) is the standard graduate course using Cover-Thomas. Full lecture notes, problem sets, and exams are available. The course emphasizes mathematical rigor and covers the standard topics of the Cover-Thomas curriculum.
David MacKay’s Cambridge information-theory lectures accompany his book and connect coding to inference and learning. Work through the distribution and coding calculations alongside the lectures; those examples give the formulas an operational meaning.
Stanford EE376A (Information Theory, materials from Tsachy Weissman and others, available online) covers the course in a more applied direction with connections to statistics and data compression.
| Course | Platform | Type |
|---|---|---|
| MIT 6.441 Information Theory (free) | MIT OCW | Depth |
| MacKay’s Cambridge Information Theory lectures (free) | YouTube | Entry |
| Stanford EE376A Information Theory (free) | Stanford course site | Depth |
Practice, Tools, and Current Sources
Calculate entropy for a fair coin, a biased coin, a fair die, and a uniform distribution on 256 symbols. Then estimate letter frequencies in a text sample and compare the resulting single-letter entropy with a model conditioned on preceding letters. They estimate different quantities; neither gives a universal entropy value for a language. Report the sample, preprocessing, context length, and estimation method.
For mutual information in practice: compute I(X;Y) for two correlated Gaussian variables with known correlation ρ, observing how mutual information relates to correlation but is not the same. Compute the mutual information between features and labels in a simple dataset using kernel density estimation or histogram methods, and observe the computational difficulties — mutual information estimation is hard in high dimensions, which explains why contrastive learning methods use proxy objectives.
For compression, implement Huffman coding and compare expected code length with entropy on the four-symbol example in this section. Then use a highly skewed distribution: a nontrivial binary prefix code still uses at least one bit per symbol, even when entropy is far below one. Compare block or arithmetic coding while including finite-length and model overhead. Nayuki’s Huffman and arithmetic-coding implementations provide readable examples for comparison.
For channel coding, implement a Hamming (7,4) code: four data bits become seven transmitted bits, giving rate 4/7. Introduce independent bit flips and measure the decoded block error probability. Plot that error probability against flip probability. Separately compare 4/7 with the BSC capacity 1−h₂(p); error probability and capacity have different meanings and cannot be treated as interchangeable axes or crossing thresholds.
SciPy (scipy.stats.entropy) and scikit-learn (sklearn.metrics.mutual_info_score) provide implementations of entropy and mutual information for empirical distributions. PyTorch and TensorFlow implement cross-entropy loss; understanding that these are information-theoretic quantities rather than arbitrary loss functions is the practical payoff of studying information theory.
| Resource | Platform | Type |
|---|---|---|
| Entropy and mutual information calculations | Python / SciPy | Practice |
| Huffman coding implementation | Local | Practice |
| Nayuki reference implementations: Huffman and arithmetic coding (free) | GitLab / nayuki.io | Practice |
| Hamming code implementation | Local | Practice |
| SciPy entropy and MI functions (free) | scipy.org | Practice |
Traps
| Trap | Why it misleads | Better response |
|---|---|---|
| Equating entropy with truth or usefulness | Unpredictable noise can have high entropy. | State which variable and probability model are being measured. |
| Treating average length as a bound on every message | Individual code lengths vary and real files have overhead. | Compare expected lengths and include model and header costs. |
| Ignoring dependencies between symbols | Marginal entropies can exceed the entropy rate. | Compare independent coding with a model of sequences or blocks. |
| Treating differential entropy as literal storage bits | It depends on scale and may be negative. | Specify quantization or use an appropriately invariant quantity. |
| Reading capacity as finite-block zero-error throughput | Capacity concerns asymptotically vanishing error under a channel model. | Report rate, block length, error probability, and channel assumptions. |
| Applying data processing after adding outside information | New observations violate the original Markov setup. | Identify all inputs to the transformation before applying the inequality. |
中文
信息论研究表示和传输不确定数据的极限。描述一个信源的输出需要多少比特？通过有噪信道能够可靠传送多少信息？答案依赖概率模型、允许的错误，以及信道的资源或约束。
这里的信息度量区分能力与不确定性，而不是真实性或用途。一个随机比特可以具有最大熵，却不告诉你任何关于明天天气的事情。反过来，一条很短、很容易预测的消息，也可能对接收者十分重要。分清这些问题，才能使用数学结论，而不要求它衡量“信息”这个词的所有含义。
从概率、期望、条件分布与对数开始（§2.5）。这一节把这些概念连接到编码和通信，再解释它们在统计建模中的用途与限制。以二为底的对数给出比特单位；改变底数就改变单位。
信息概念如何变得精确
在信息论形成统一学科之前，电报与电话已经提出了信号速度、带宽和噪声等实际问题。Nyquist 研究传输限制，Hartley 用对数度量可能消息的数量。Shannon 在 1948 年把概率性的信源描述与编码、信道模型结合起来，给出了精确的可达极限及相应逆向限制。
一个重要变化，是区分消息的选择与赋予消息的含义。通信系统即使不理解内容，也需要重现被选中的信号。这种抽象让语音、文本和其他信源能够通过共同模型研究。Shannon 早先把开关电路连接到布尔代数的工作，处理的是另一问题：怎样在电路中实现逻辑关系。
后续编码研究发展了在特定条件下接近极限的方法。Huffman 编码为具有指定分布的单个符号提供最优二进制前缀码。算术编码处理更长序列，可以避免逐符号取整的成本。纠错码加入有结构的冗余，使接收者能在噪声存在时恢复数据。信源编码去掉可预测的冗余；信道编码加入专为纠错选择的冗余。因此，两者可以出现在同一个通信系统中。
与统计和计算的联系扩展了这一领域。算法信息论询问描述单个对象的程序长度，而统计信息论从可能结果上的分布出发。学习理论使用熵、交叉熵和互信息等量分析预测与表示。共同的数学词汇，并不意味着每个学习问题都已经转化成解决了的编码问题。
熵、信道与分布的几何
需要分清信源、编码与信道。信源模型给消息分配概率，编码选择表示方式，信道模型描述发送符号怎样变成接收观察。熵描述信源，平均长度描述编码，容量则描述在约束下优化输入分布之后，信道能够支持什么。
熵及其扩展
一个概率为 p 的离散结果，其自信息为 −log₂ p。独立事件的概率相乘，因此自信息相加。熵是其平均值：H(X) = −Σₓ p(x) log₂ p(x)，零概率项贡献零。公平硬币的熵是一比特，确定性结果的熵是零。对于大小为 m 的有限字母表，熵至多为 log₂ m，均匀分布达到这个值。
条件熵 H(X|Y) 平均了观察另一个变量之后剩余的不确定性。链式法则 H(X,Y) = H(Y) + H(X|Y)，把描述 Y 的成本与已知 Y 后描述 X 的额外成本分开。互信息是 I(X;Y) = H(X) − H(X|Y)。如果 Y 复制公平比特 X，互信息是一比特；如果二者独立，则为零。这种减少是对观察结果取平均：某个意外观察之后，剩余不确定性可以高于原先的平均值。
交叉熵衡量结果服从 P、却用 Q 分配概率时的平均理想编码长度：H(P,Q) = −Σₓ P(x) log₂ Q(x)。它超过熵的部分就是 D_KL(P||Q)。如果 Q 给某个在 P 下可能发生的结果分配零概率，这个额外成本就是无限大。这解释了为什么过度自信的错误预测，代价可能远高于适度的不确定。KL 散度不对称，也不是距离度量。
数据处理不等式指出，对于马尔可夫链 X → Y → Z，把 Y 处理成 Z，不能增加它与 X 的互信息。马尔可夫条件意味着 Z 没有从 Y 之外获得关于 X 的额外信息。特征变换仍然可以使已有信息更容易被能力有限的预测器使用。增加外部数据库或新测量，会改变可用信息，也就改变了定理讨论的设定。
连续变量需要额外注意。微分熵依赖坐标：在相关熵存在时，把变量乘以非零常数，会使微分熵增加该常数绝对值的对数。微分熵可以为负，也不是记录一个精确实数所需的比特数。量化引入分辨率；在适当定义下，互信息与 KL 散度对可逆变量变换保留有用的不变性。
在机器学习中，这些量描述特定目标和假设。交叉熵训练把预测概率拟合到观察结果，本身不保证在新分布上校准良好。变分下界把模型的对数似然分成下界与一个非负间隙，后者涉及近似后验与真实后验。对比目标可以在其采样假设下联系到互信息下界。每种情况下，都应先识别分布与界，再判断公式是否支持更广泛的学习保证。
信源编码：压缩及其极限
对于有限离散信源的二进制前缀码，平均长度 L 满足 H(X) ≤ L，并且存在使 L < H(X)+1 的编码。前缀码中，没有码字是另一码字的开头，因此拼接后的码字不需要分隔符就能解码。对于给定符号概率，Huffman 编码在这类编码中最小化平均长度。
考虑概率分别为 1/2, 1/4, 1/8, 1/8 的四个符号，分配码字 0, 10, 110, 111。它们满足前缀条件，平均长度为 1/2 × 1 + 1/4 × 2 + 1/8 × 3 + 1/8 × 3 = 1.75 比特，恰好等于熵。更可能出现的符号得到更短码字。这个界讨论信源上的平均值；单条消息可以更长，也可以更短。
把 n 个独立符号组成块进行编码，块熵为 nH(X)，每块小于一比特的取整开销，就降低为每符号小于 1/n 比特。对于有限的独立同分布信源，长序列集中在一个典型集合中，其大小大致按 2^(nH) 增长。因此，标识一个典型序列需要大约 nH 比特。仍然必须处理罕见序列，这解释了为什么精确编码定理讨论平均长度或趋零的错误概率，而不声称每个长度为 n 的字符串都能装进 nH 比特。依赖关系会改变信源熵。如果公平比特总是以相同的两个组成一对，每个比特单独看都有一比特熵，但每对只有一比特不确定性。忽略依赖的模型会错过可用的压缩空间。对一个过程，只要相应极限存在，熵率就描述渐近的每符号不确定性。
真实文件还包含模型描述、头部和有限长度开销。无损压缩器不可能缩短每个输入：较短字符串的数量不足以唯一表示所有输入。在适当概率模型下，算术编码可以接近熵率，但一般不能在平均意义上低于该模型的熵。DEFLATE 使用 LZ77 风格的引用与 Huffman 编码，具体见 RFC 1951，并非算术编码。
Kolmogorov 复杂度询问：在固定通用机器上输出某个字符串的最短程序有多长？它讨论单个对象，其一般取值不可计算。在通常的不变性定理中，改变参考通用机器，只使复杂度相差至多一个加性常数。实际的最小描述长度方法，则在选定模型类中比较可计算的描述，同时计算模型成本与使用模型编码数据的成本。它们并不计算不受限制的最短程序。
有损压缩允许重建误差。率失真理论在给定信源模型与平均失真约束下，询问最小渐近编码速率。平方误差与基于任务的可接受重建标准，可能对不同损失作出不同评价。因此，选择哪些内容可以丢弃，是问题定义的一部分，不能只由熵来决定。
信道编码：可靠通信及其极限
信道模型用条件分布 P(Y|X) 描述发送输入怎样变成接收输出。对于有限离散无记忆信道，容量为 C = max_{P(X)} I(X;Y)，单位是每次信道使用的比特数。最大化很重要：在某种输入分布下，信道可能比另一种分布传递更多信息。无记忆性也是一项假设；有记忆信道需要更一般的处理。
一个小编码就能说明冗余的作用。附加一个校验位，使每个发送块中 1 的总数为偶数：数据 101 变成 1010。单个比特翻转会使总数变成奇数，从而暴露错误，但这项校验不能定位哪个比特受损。翻转两个比特又会恢复偶数，错误便无法检出。检错与纠错是不同能力。
如果要纠正一个三比特块中的任意一次比特翻转，可以把 0 编成 000，把 1 编成 111，再按多数表决解码。翻转两个或三个比特会得到错误答案。若各比特以概率 p 独立翻转，解码错误概率为 3p²(1−p) + p³；在 p=0.1 时，结果为 0.028。代价是每个数据比特需要发送三个比特。信源编码去除冗余以缩短表示，信道编码则增加有结构的冗余，使损坏可以被检测或纠正。
编码定理指出，低于容量的速率允许构造这样的码：随着块长增加，错误概率趋于零。在模型条件下，高于容量的速率无法实现趋零错误。这是渐近陈述，并不保证短块上的零错误，也不保证在指定延迟下存在高效解码器。定理把基本极限与构造合适编码所需的工程工作区分开。
对于以概率 p 独立翻转每个比特的二元对称信道，容量为 1−h₂(p)，其中 h₂ 是二元熵。p=0.1 时，容量约为每次信道使用 0.531 比特；p=0.5 时，输出与输入独立，容量为零；p=1 时，每个比特都会以可预测的方式反转，接收者可以再反转回来，容量为一。障碍在于不知道发生了怎样的改变，而不只是发生了改变。
对于实值加性白高斯噪声信道，若平均输入功率至多为 P，每次使用的噪声方差为 σ²，容量为 ½ log₂(1+P/σ²) 比特／实信道使用。熟悉的带限公式 W log₂(1+SNR) 则采用每秒比特数，并有相应的带宽与功率约定。单位和信道假设都是公式的一部分；它不是对每条无线链路实际吞吐量的通用预测。
纠错码让不同输入消息产生足够容易区分的发送序列。接收者利用这些冗余，在发生损坏后推断可能的消息。块长、解码复杂度、延迟与实际噪声过程都会影响设计。Shannon 的原论文建立了概率模型与渐近编码极限的作用；实际表现还需针对选定编码和信道评估。
学习这个主题会改变什么
这门学科改变阅读性能主张的方式。对于压缩，询问信源模型、依赖关系、编码开销与允许失真；对于通信，询问单位、信道假设、块长与错误概率；对于学习，识别损失中的分布，区分拟合这些分布与在新任务中得到有用行为。
计算上面的四符号码，再比较逐比特编码与对相同比特对编码。在若干噪声率下模拟一个小型纠错码，测量块错误率。比较编码的信息速率与信道容量，同时区分渐近定理与有限块测量。这些练习使极限成为可以解释的量，而不只是关于压缩或智能的口号。
资源
书籍与文本
Cover 和 Thomas 的 Elements of Information Theory（第 2 版，Wiley，2006）是经典数学参考。它覆盖熵、互信息、信源和信道编码定理、rate-distortion theory、Kolmogorov complexity，以及 network information theory，并给出完整证明，同时仔细处理技术条件。它严格而综合——对于任何想获得完整数学处理的人，这是正确主参考。其记号和证明风格是标准的，在整个信息论文献中都能被识别。
MacKay 的 Information Theory, Inference, and Learning Algorithms（Cambridge，2003，可在 inference.org.uk 免费获取）是另一种重点不同的选择。MacKay 把信息论与 Bayesian inference、纠错码和机器学习联系起来发展——它明确连接统计学习，而不是把信息论当成孤立主题。对一本技术教材来说，它的写作异常清晰且有吸引力；它对信息论、推断和学习的整合，使其成为机器学习实践者的正确主文本。它比 Cover-Thomas 更广，覆盖神经网络、Monte Carlo methods 和 approximate inference；但技术上没有 Cover-Thomas 完整。免费获取和 ML 取向，使它成为 CS 学习者更常被推荐的起点。
Shannon 的 A Mathematical Theory of Communication（1948）是概率信源模型、熵与有噪信道编码的一手材料。学习入门解释后，可以选读相关章节，并比较其模型假设与自己关心的实际通信问题。
对于 Kolmogorov complexity 和 algorithmic information theory，Li 和 Vitányi 的 An Introduction to Kolmogorov Complexity and Its Applications（第 4 版，Springer，2019）是标准参考。它以完整严格性覆盖 Kolmogorov complexity、incompressibility method、MDL，以及与可计算性和复杂性理论的联系。
Blahut 的 Algebraic Codes for Data Transmission 发展代数编码，包括 BCH 码与 Reed–Solomon 码。Richardson 与 Urbanke 的 Modern Coding Theory 发展现代概率编码方法，包括 LDPC 码。可以根据自己关心编码的代数构造，还是迭代解码与性能分析来选择。
Moser 和 Chen 的 A Student’s Guide to Coding and Information Theory（Cambridge，付费）是一座短而易进入的桥梁，从实际编码例子通向熵、互信息、信道容量和信息传输定理。它远不如 Cover-Thomas 深，也不如 MacKay 面向 ML，但适合那些在进入完整数学处理前，需要先建立通信与编码直觉的学习者。
| 书籍 | 作用 | 类型 |
|---|---|---|
| Cover & Thomas，Elements of Information Theory（第 2 版） | 经典数学参考 | 参考 |
| MacKay，Information Theory, Inference, and Learning Algorithms（免费） | 面向 ML 的入口；统一处理 | 入门 |
| Li & Vitányi，Introduction to Kolmogorov Complexity（第 4 版） | 算法信息论 | 深入 |
| Richardson & Urbanke，Modern Coding Theory | LDPC 和 turbo codes | 深入 |
| Shannon，“A Mathematical Theory of Communication”（1948，免费） | 奠基论文；历史中心 | 辅助 |
| Moser & Chen，A Student’s Guide to Coding and Information Theory（付费） | 温和的编码优先桥梁 | 辅助 |
课程与讲座
MIT 6.441（Information Theory，MIT OCW 免费）是标准研究生课程，使用 Cover-Thomas。完整讲义、习题和考试都可获取。课程强调数学严格性，覆盖 Cover-Thomas 课程体系的标准主题。
David MacKay 的 Cambridge 信息论讲座配合其教材，把编码连接到推断与学习。可以随讲座完成分布和编码计算，通过例子理解公式的操作含义。
Stanford EE376A（Information Theory，Tsachy Weissman 等人的材料可在线获取）以更应用的方向覆盖课程，并连接统计和数据压缩。
| 课程 | 平台 | 类型 |
|---|---|---|
| MIT 6.441 Information Theory（免费） | MIT OCW | 深入 |
| MacKay’s Cambridge Information Theory lectures（免费） | YouTube | 入门 |
| Stanford EE376A Information Theory（免费） | Stanford 课程网站 | 深入 |
实践、工具与当前来源
计算公平硬币、偏置硬币、公平骰子，以及 256 个符号上均匀分布的熵。再从文本样本估计字母频率，比较所得单字母熵与以此前字母为条件的模型。它们估计的是不同量，都不能给出某种语言的通用熵值。应报告样本、预处理、上下文长度与估计方法。
对于 实践中的 mutual information：计算两个具有已知相关系数 ρ 的相关 Gaussian 变量之间的 I(X;Y)，观察 mutual information 与 correlation 如何相关但并不相同。使用 kernel density estimation 或 histogram methods，在一个简单数据集中计算特征与标签之间的 mutual information，并观察计算困难——高维 mutual information estimation 很难，这解释了为什么 contrastive learning 方法会使用 proxy objectives。
压缩练习可以实现 Huffman 编码，在本节四符号例子上比较平均码长与熵。再采用高度偏斜的分布：即使熵远低于一，非平凡的逐符号二进制前缀码仍至少使用每符号一比特。比较分块或算术编码时，计入有限长度与模型开销。Nayuki 的 Huffman 和算术编码实现提供了可读的对照例子。
信道编码练习可以实现 Hamming (7,4) 码：四个数据位变成七个发送位，码率为 4/7。引入独立位翻转，测量解码后的块错误概率，并绘制它随翻转概率的变化。另外比较 4/7 与 BSC 容量 1−h₂(p)；错误概率与容量含义不同，不能把两者当成可以直接互换的坐标或交叉阈值。
SciPy（scipy.stats.entropy）和 scikit-learn（sklearn.metrics.mutual_info_score）提供了经验分布的熵和互信息实现。PyTorch 和 TensorFlow 实现了 cross-entropy loss；理解这些是信息论量，而不是任意 loss function，是学习信息论的实践回报。
| 资源 | 平台 | 类型 |
|---|---|---|
| 熵与互信息计算 | Python / SciPy | 实践 |
| Huffman coding 实现 | 本地 | 实践 |
| Nayuki 参考实现：Huffman 和 arithmetic coding（免费） | GitLab / nayuki.io | 实践 |
| Hamming code 实现 | 本地 | 实践 |
| SciPy entropy 和 MI 函数（免费） | scipy.org | 实践 |
陷阱
| 陷阱 | 为什么会误导 | 更好的做法 |
|---|---|---|
| 把熵等同于真实性或用途 | 不可预测的噪声可以具有高熵。 | 说明度量的是哪个变量与概率模型。 |
| 把平均长度当成每条消息的界 | 单个码长不同，真实文件还有额外开销。 | 比较平均长度，并计入模型与头部成本。 |
| 忽略符号之间的依赖 | 边缘熵可能高于熵率。 | 比较独立编码与序列或分块模型。 |
| 把微分熵当成实际存储比特数 | 它依赖尺度，且可以为负。 | 指明量化方式，或使用适当的不变量。 |
| 把容量读成有限块的零错误吞吐量 | 容量讨论信道模型下渐近趋零的错误。 | 报告速率、块长、错误概率与信道假设。 |
| 加入外部信息后仍直接应用数据处理不等式 | 新观察违反原来的马尔可夫设定。 | 应用不等式前，识别变换的全部输入。 |