信源→信道：两阶段编码
Hamming的第10章从Shannon的通信模型开始，该模型适用于每个移动信息的系统：电话、广播、硬盘、DNA复制、计算机内存。
两阶段结构
阶段1：信源编码（压缩）。将源消息转换为紧凑表示。目标：移除信源本身的冗余。摩斯码做到这一点：常见的字母用短码，稀有的字母用长码。
阶段2：信道编码（错误保护）。添加适应信道噪声特性的受控冗余。嘈杂的电话线需要比光纤电缆更多的冗余。两个阶段相互解耦：为各自的任务独立优化。
两个阶段之间的公共接口——标准化的比特流——意味着任何信源都可以与任何信道配对。这种模块性是Shannon的关键架构洞察。
存储即通信。 Hamming指出，通过空间发送消息（传输）和通过时间发送消息（存储）使用相同的模型。备份驱动器是时间上的一个嘈杂信道。
噪声的作用
Shannon的模型做出了一个激进的假设：噪声是不可避免的。每个信道、每个存储介质、每个交换电路都会引入某种错误概率。问题不是"我们如何消除噪声？"而是"我们如何在噪声存在的情况下恢复原始消息？"
这与古典物理学形成对比，后者中噪声作为事后才考虑的（测不准原理）。Shannon将噪声视为基础条件——所有理论都以它为基础。
现在，第10章关注无噪声情况：无错误的信源编码。信道编码问题（错误纠正）稍后再说。
何时可以唯一解码？
要使可变长编码有用，接收器必须唯一地解码比特流。Hamming用一个4符号的编码来说明这个失败，然后引入修复：无前缀码。
无前缀条件
一个编码是无前缀的（或即时的），如果没有码字是任何其他码字的前缀。给定接收到的比特流，一旦到达解码树中的叶子，你就知道符号已经结束——不需要向前看。
例子：{s1, s2, s3, s4}的无前缀码：s1 = 0, s2 = 10, s3 = 110, s4 = 111。
验证：0不是10、110或111的前缀。10不是110或111的前缀（10后跟更多位给出100...或101...，都不以110或111开头）。该编码合格。
解码过程：遵循树、对每个传入比特分支、在到达叶子时发出符号、返回根。
Kraft不等式
对于任何具有码字长度 l_1, l_2, ..., l_n 的无前缀二进制编码：
Σ 2^(−l_i) ≤ 1
等号成立当编码是完全的（叶子铺砌整个二进制树，没有间隙）。这是必要条件：没有无前缀码可以违反它。相反，对于任何满足Kraft不等式的长度集合，存在无前缀码。
应用Kraft不等式
给定码字长度，验证Kraft：Σ 2^(−l_i) ≤ 1。
对于{s1=0, s2=10, s3=110, s4=111}：长度为1, 2, 3, 3。
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1。 ✓
Shannon熵
可变长编码的平均码字长：L = Σ p_i · l_i，其中p_i是符号s_i的概率，l_i是其码字长度。
L最多能有多短？Shannon的答案：不低于信源熵。
Shannon熵： H = −Σ p_i · log₂(p_i) （单位：比特/符号）
熵衡量每个符号的平均信息。高熵意味着符号大致同样可能（最大不可预测性）。低熵意味着某些符号占主导地位（高可预测性，更可压缩）。
无噪声编码定理
对于任何无前缀码，H(信源) ≤ L ≤ H(信源) + 1。
没有码可以打败熵。Huffman编码（下一章）实现上界：L < H + 1。对于在n个符号上的块编码，界变得更紧：H ≤ L/n < H + 1/n。
熵也是理论压缩极限：你不能压缩信源低于每符号H比特而不失去信息。
计算熵
例子：4个符号，概率为p = [1/2, 1/4, 1/8, 1/8]。
H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)
= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3
= 0.5 + 0.5 + 0.375 + 0.375 = 1.75 比特/符号
而Huffman编码{0, 10, 110, 111}恰好实现L = 1.75 = H。
为什么熵是下界
无噪声编码定理的下界不仅仅是一个公式——它反映了关于信息的深层东西：你不能压缩已经最大不可预测的东西。
当所有符号同样可能时（均匀分布），熵H = log₂(n)对于n个符号。长度为log₂(n)比特的块编码恰好实现H。没有码可以做得更好。
当一个符号占主导（比如p(A) = 0.99, p(B) = 0.01）时，H很小——接近0。可变长码可以为A分配一个非常短的码，非常有效地编码流。
实际的建议：只有当符号概率差异很大时，才存在大的压缩增益。如果信源已经"均匀"（看起来随机），Huffman编码没有任何收益。