源→通道:两阶段编码
哈明第10章以香农的通信模型开篇,这个模型适用于所有将信息传递给系统:电话通话,无线电,硬盘,DNA复制,计算机内存。
两阶段架构
阶段1:源编码 (压缩). 将源消息转换为紧凑的表示形式。目标:消除源本身的冗余。摩斯密码这样做:常见的字母得到短代码,罕见的字母得到长代码。
阶段2:通道编码 (错误保护). 根据通道噪声特性的有控制的冗余。有噪声的电话线需要比光纤有更多的冗余。两个阶段之间的共同接口——一个标准化的比特流——意味着任何源都可以与任何通道配对。这使得模块性成为香农的关键建筑设计见解。
将信息传递给空间(传输)和将信息传递给时间(存储)使用相同的模型。备份驱动器在时间中的噪声通道。
Storage as communication. Hamming notes that sending a message through space (transmission) and sending it through time (storage) use the same model. A backup drive is a noisy channel in time.
噪音的作用
香农的模型做出了一种激进的假设:噪音是不可避免的。每个通道,每个存储介质,每个交换电路都引入了一定程度的错误的可能性。问题不在于'我们如何消除噪音?'而在于'我们如何在噪音中恢复原始消息?'
这与经典物理学形成了对比,其中噪音作为一个附加内容进入(不确定性原理)。香农将噪音视为基础条件——所有理论都建立在它之上。
目前,第10章关注于无噪声情况下的源编码:没有错误。通道编码问题(错误纠正)将在后面的章节中讨论。
在什么情况下你可以唯一地解码？
为了使变长代码有用，接收器必须以无歧义的方式解码比特流。Hamming 用一个4符号代码来说明这个问题，然后引入解决方案：前缀无关代码。
前缀无关条件
一个代码是前缀无关的（或即时的）如果没有码字是另一个码字的前缀。接收到比特流时，你知道一个符号已经结束，直到在解码树上到达一个叶子节点——不需要预先查看。
前缀无关代码示例：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. ✓
香农熵
变长代码的 平均代码长度：L = Σ p_i · l_i，其中 p_i 是符号 s_i 的概率，l_i 是其代码长度。
L 可以缩短到什么程度？香农的答案：不低于源熵。
香农熵：H = −Σ p_i · log₂(p_i)（单位：比特/符号）
熵衡量每个符号的平均信息量。熵高意味着符号的可能性相差不远（最大不可预测性）。熵低意味着一些符号占据优势（高可预测性，更易压缩）。
无噪声编码定理
对于任何前缀无缝代码，H(source) ≤ L ≤ H(source) + 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 bits/symbol
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 编码无法获得任何收益。