从哈夫曼到曼彻斯特：信源、信道与线路编码解析

编码这两个字大概是工程圈里最容易撞车的词。翻翻手边正在跑的东西数据库连接串里写着charsetutf8前端调接口时纠结 GBK 还是 UTF-8压缩包里躺着一层 LZWTransformer 论文里满屏 positional encoding连乘法器都要用 Booth 编码省几个加法器。名字全都叫编码内涵差了十万八千里。我最近在补数字通信这块的底子把信源编码、信道编码、线路编码三条线从头捋了一遍顺手用 Python 把哈夫曼、曼彻斯特和 CRC 都手搓了一遍这篇就是整理出来的学习笔记尽量把每个设计决策背后的原因写清楚。适合看这篇的人大概有三类正在啃《数字通信》《信息论与编码》这类课程的学生写了几年业务代码但对底层链路一知半解的开发者还有做嵌入式、协议栈、FPGA 的同行。我的写法不堆公式重点回答三个问题每一类编码到底解决什么问题代价是什么实际工程里怎么选。读完你至少能分清哈夫曼和曼彻斯特根本不在一个层面上也能明白 CRC 校验为什么换个实现就算不出同样的值。1. 先把编码这个词拆开看1.1 一条链路里的三次编码任何一次数字传输从信息产生到送进物理介质中间会经历至少三次编码。第一次是信源编码把原始信息语音、图像、文本压成紧凑的比特流第二次是信道编码给比特流加上受控的冗余让接收端能发现甚至纠正传输错误第三次是线路编码把比特流转换成适合特定介质传输的电平或光信号形态。三者串在一起方向还不一样。我第一次接触这块的时候最大的困惑就在这儿——信源编码在删冗余信道编码在加冗余这不是自相矛盾吗。后来想通了删冗余是为了省传输资源加冗余是为了对抗传输损伤两者服务的目标根本不同是在少占带宽和传得可靠之间做平衡。杀掉一个链路要么浪费资源要么一碰就碎。具体到实际系统里手机打语音电话大致是这样走的麦克风采样得到 PCM 数据先经过 AMR 或 Opus 这类信源编码压到十几 kbps然后进信道编码器加上纠错冗余再经过调制和发送端的处理送上射频。接收端反过来拆。整个过程里每一层都在做取舍。1.2 三类编码各自的位置和边界信源编码站在最上层关心的是信息本身有多少冗余能用掉。它只对内容负责不管后面怎么传。哈夫曼、算术编码、LZW 属于这一类JPEG、MP3、H.264 这些具体格式内部也大量用到它们。信道编码处在中间层关心的是传过去的比特有多大可能被破坏我加多少冗余能扛住。奇偶校验、CRC、汉明码、卷积码、RS 码、LDPC、Polar 码都属于它。这一层不管内容是什么只把比特流当黑盒处理。线路编码贴在最底层关心的是这串比特怎么变成电压或光功率才能在铜线、光纤上跑得稳。NRZ、曼彻斯特、AMI、4B5B、8B/10B 是它的代表。它要解决的是直流分量、时钟恢复、频谱整形这些物理层问题。很多人会把曼彻斯特编码和哈夫曼编码混在一起记因为它们名字里都带个人名听起来像是同一类东西。其实一个在物理层管电平跳变一个在上层管码字分配中间隔着好几层协议。这个混淆在面试里踩雷的概率不低。1.3 一个具体场景把三者串起来拿有线以太网举例更清楚。你在浏览器里敲下回车HTTP 报文先被 TCP/IP 封装这些是协议层面的东西真正进到网卡报文会被切成帧帧头加上 FCS 字段这个 FCS 用的就是 CRC-32属于信道编码的范畴准确说是检错码帧再往下走网卡的 PHY 芯片把比特流做 4B5B 或者 8B/10B 编码然后才是电压信号送到双绞线上。这条路径里三次编码各司其职缺一层都跑不通。理解了这个分层再看各种编码名词就不会乱。看到一个编码方案先问它在链路的哪一段解决什么问题心里立刻就有数了。1.4 我踩过的一个认知坑说个我自己的教训。刚学的时候我以为编码就等于压缩以为只要编码效率够高传输就万事大吉。结果真正动手做一个红外遥控接收的小项目时才傻眼数据本身很简单但接收端总是间歇性错位我一开始在数据压缩上找了半天原因最后发现是线路层的同步问题——发送端和接收端的位定时没对齐采样点偏到了边沿附近。这件事给我上了一课编码不是单点技术是一整条链路的配合。2. 信源编码把冗余挤出去2.1 熵是压缩绕不过去的天花板信源编码的理论根基是香农的信息论。对于一个离散无记忆信源它的熵定义为 H(X) -Σ p(x)·log2 p(x)单位是比特每符号。这个数的含义是每个符号平均携带的信息量也正是一切无损编码平均码长的理论下界。换句话说任何无损压缩算法的平均码长都不可能低于信源熵这是物理规律不是工程能力问题。所以以后再看到无损压缩 20 倍的宣传第一反应应该是问信源熵是多少。英文文本每个字符的熵大概在 1 到 2 比特之间考虑上下文还能更低一段真正的随机二进制数据熵就是 8 比特每字节压不动是正常的硬压只能靠有损。搞清楚这个下界的存在你对压缩算法的期待就会理性很多。熵这个概念还有一个直接推论编码效率等于平均码长除以熵越接近 1 越好。这个指标在后面评估哈夫曼这类编码时非常有用。2.2 哈夫曼编码的手工推演哈夫曼编码是最经典的无损编码之一思路简单到可以用一句话概括让出现概率大的符号用短码概率小的用长码从底向上贪心合并构造二叉树。具体步骤是这样的统计每个符号的频率或概率把所有权值放进一个集合每轮取出权值最小的两个节点合并成一个新节点新节点的权值是两个子节点之和把它放回集合重复到只剩一个节点最后从根节点往下走往左走记 0往右走记 1这个约定反过来也行只要收发两端一致。用一组实际数据推一遍更直观。假设有五个符号概率分别是 A0.4、B0.2、C0.2、D0.1、E0.1。第一轮合并 D 和 E 得到节点 N1权值 0.2第二轮合并 B 和 C 得到 N2权值 0.4第三轮合并 N1 和 N2 得到 N3权值 0.6最后一轮合并 A 和 N3 得到根节点权值 1.0。如果规定左分支为 0、右分支为 1那么 A 的码字是 01 位N3 分支出来的 N1 部分编码为 10 开头、N2 部分为 11 开头继续展开得到 D100、E101、B110、C111。算出平均码长0.4×1 0.2×3 0.2×3 0.1×3 0.1×3 2.2 比特每符号。再算这组分布的熵-0.4×log2(0.4) - 0.2×log2(0.2)×2 - 0.1×log2(0.1)×2代入数值约等于 2.122 比特每符号。编码效率 2.122 / 2.2 ≈ 96.5%相当接近理论极限了。2.3 哈夫曼的几个短板哈夫曼编码好用但不是没有代价。第一个问题是要预先知道概率分布。实际压缩文件时得先扫一遍统计频率再扫一遍编码两遍扫描的开销在处理流式数据时很难接受。工程上一般用自适应哈夫曼来规避一边编码一边更新码表但实现复杂度直线上升。第二个问题是码长必须是整数比特。当某个符号的概率特别极端时理论最优码长可能远小于 1 比特比如 p0.99 对应的自信息量只有 0.0145 比特可哈夫曼最少也得给 1 位白白浪费。这也是哈夫曼平均码长最多比熵差 1 比特每符号的原因。第三个问题是码表本身要传。接收端得先拿到这棵树才能解码小文件上这笔开销很扎眼。实际格式里通常用规范哈夫曼canonical Huffman把码表压得很紧凑只传每个码长的符号个数接收端自己重建码表。2.4 算术编码和 LZW 的适用场景算术编码绕开了整数比特限制它把整个消息映射成 [0,1) 区间上的一个小数理论上可以无限逼近熵代价是复杂度高、对错误极其敏感一个比特翻转可能导致整个解码崩溃。另外历史上它也有一段专利争议期早期很多格式不敢用。现在一些现代格式和视频编码里能看到它的影子。LZW 走的是另一条路属于字典压缩。它不用预先统计概率而是边读边维护一张字符串到码字的映射表遇到没见过的串就把它加进字典。优点是不需要两遍扫描适合流式数据缺点是字典会不断膨胀需要定期重置。GIF 图片、老式 TIFF、早期 PDF 里的压缩都用过它。LZW 有个著名的专利史感兴趣可以自己查这里不展开。选哪个看场景小文件、已知分布、要简单哈夫曼追求极致压缩率、错误不敏感算术编码流式、无先验知识、要省内存LZW。编码方法是否需要先验分布能否达到熵典型用途哈夫曼需要最多差 1 bit/符号通用压缩、DEFLATE算术编码需要几乎可达现代视频编码LZW不需要一般GIF、老式 TIFF游程编码不需要视数据而定传真、二值图像3. 信道编码让错误可检测、可纠正3.1 从最简单的奇偶校验说起信道编码的起点是奇偶校验。做法很简单在数据后面加一位使得整组数据里 1 的个数为奇数奇校验或偶数偶校验。接收端重新数一遍对不上就知道出错了。它的能力很有限只能检测出奇数个比特错误偶数个错误会让校验位恢复一致从而漏检而且它只能告诉你错了不能告诉你哪里错了更没法纠正。冗余开销倒是最小只加 1 位。在低误码率、只要求发现问题的场景里够用比如某些内存的 ECC 就用更复杂一点的变体。想做得好一点可以用二维奇偶校验把数据排成矩阵每行每列都加校验位。这样不但能发现错误还能通过行列交叉定位单个比特错误的位置并直接翻转回来。代价是冗余度上去了能纠正的错误数量依然有限。3.2 汉明码的构造思路汉明码是第一个真正意义上的纠错码思路非常漂亮。以经典的 (7,4) 汉明码为例7 位码字里放 4 位数据、3 位校验能纠正任意 1 位错误、检测 2 位错误。校验位数量 r 和数据位 m 之间要满足 2^r ≥ m r 1代入 m4 得到 2^3 8 ≥ 8刚好够用。它的巧妙之处在于校验位放在码字的 1、2、4、8……这些 2 的幂的位置上。每个校验位负责一组数据位的奇偶负责范围由它在下标二进制中为 1 的位决定。具体到 (7,4) 码位置 1 的校验位覆盖位置 1、3、5、7位置 2 覆盖位置 2、3、6、7位置 4 覆盖位置 4、5、6、7。每个数据位会被它下标中所有为 1 的位对应的校验位覆盖。接收端对三组分别做校验把三个校验结果拼成一个二进制数这个数直接就是出错位置的下标。全 0 表示无错非 0 就是出错位置翻转它即可。这种伴随式直接指向错误位置的设计是汉明码能在当时流行的核心原因。它的代价也很清楚码率只有 4/7 ≈ 0.571也就是说发 7 位只有 4 位是真正的信息冗余度相当高。数据块越大这个开销相对越小但纠错能力不变所以后来出现了各种扩展汉明码和 BCH 码来提升。3.3 CRC 为什么比奇偶校验强那么多CRC循环冗余校验是工程里最常用的检错手段。它把数据位串当成一个多项式的系数除以一个约定的生成多项式余数就是校验码。整个运算基于模 2 算术没有进位借位实质就是异或。它之所以强是因为对生成多项式有数学上的保证只要多项式选得好可以做到检测出所有单个比特错误、所有双比特错误以及所有长度不超过多项式阶数的突发错误。相比之下奇偶校验只能管到奇数个错误的层面。工程上最容易踩的坑不是原理而是实现参数。CRC-32 算法实际有四个可调参数初始值、输入数据是否按位反射、输出是否反射、最后是否和某个固定值异或。这四个参数不一样同一个数据算出来的结果天差地别。所以你会看到同一个CRC-32在有些地方结果是 0xCBF43926在有些地方却是别的值不用怀疑代码写错了先核对参数表。常见的 CRC-16/CCITT 用 0x1021 多项式CRC-32 用 0x04C11DB7。3.4 卷积码和维特比译码汉明码和 CRC 都属于分组码按固定的块处理。卷积码换了个思路它不按块而是把当前输入和前面若干比特做卷积运算输出速度取决于码率。经典的一个配置是 (2,1,3) 卷积码约束长度 3每输入 1 位输出 2 位码率 1/2生成多项式分别是 111 和 101。卷积码的解码用维特比算法在网格图上找和接收序列最匹配的路径属于最大似然译码。它的纠错能力比同码率的分组码强代价是解码器复杂度随约束长度指数增长。这也是它在早期硬件上比较难做的原因直到芯片算力上来才普及。现代通信早就换到了更强的编码上。LTE 的数据信道用 Turbo 码5G 数据信道改用 LDPC控制信道用 Polar 码。它们都是逼近香农限的编码方案把可靠传输这件事推到了理论极限附近。想深入这块直接看 5G 标准里的编码章节是最快的路径。4. 线路编码把比特送上物理介质4.1 为什么最简单的 NRZ 不够用NRZ不归零码是最直觉的方案高电平代表 1低电平代表 0一个比特占满一个码元周期。实现简单带宽利用率也高每个码元承载 1 位。早期串口、SPI、I2C 这些近距离低速接口基本都用它。但它在长距离传输上有三个绕不开的毛病。第一是时钟恢复困难接收端要判断每位从哪儿到哪儿需要从数据本身提取时钟可如果碰上一长串连续的 1 或 0信号线上根本没有跳变接收端就不知道比特边界在哪采样点会逐渐漂移直到失锁。第二是直流分量如果数据里 1 比 0 多平均电平就偏高经过变压器或耦合电容时会被滤掉一部分导致基线漂移。第三是频谱能量集中在低频对某些信道不友好。工程上的应对要么加扰码把长连 0/1 打散要么换一种自带跳变的编码。曼彻斯特就是后一条路。4.2 曼彻斯特编码自同步的代价曼彻斯特编码的核心思想是每个比特周期中间强行插一次跳变充当时钟跳变的方向代表数据。最常见的一种约定是 IEEE 802.3 里规定的0 表示从高到低跳变1 表示从低到高跳变。这样接收端永远能看到规律性的边沿时钟恢复变得非常稳。代价也很直接每个比特至少要两个电平变化意味着码元速率是数据速率的两倍。10 Mbps 的 10BASE-T 以太网实际线路上跑的是 20 MBaud 的信号占用的带宽翻倍。对带宽敏感的应用就很受伤。还有一个实际调试里特别容易被坑的点约定方向。IEEE 802.3 是 0 从高到低、1 从低到高但一些教材、一些芯片厂商的文档里是反过来的。两个设备对接时如果不核对约定解码出来的数据全是反的而且看起来没报错非常隐蔽。我调一个板子的时候就被这个坑过一晚上。差分曼彻斯特更进一步它用比特起始位置有没有跳变来表示数据中间的跳变只提供时钟。好处是天然抗极性反转——线序接反了也不影响解码因为它看的是跳变的有无而不是方向。4.3 4B5B 和 8B/10B 的工程取舍4B5B 编码把每 4 位数据映射成 5 位码字。5 位组合一共有 32 种从中挑出 16 个适合做数据的保证足够的跳变、不含太长的连续同值剩下的挑一些做控制码比如全 11111 表示空闲。这样每 4 位数据配 1 位开销码率 4/5 80%比曼彻斯特的 50% 好很多也保证了时钟恢复。100BASE-FX 和 FDDI 都用它。8B/10B 是它的升级版把 8 位映射成 10 位开销同样约 20%实际是 25% 里的一部分用于控制但提供了更精细的性质连续相同比特不超过 5 个同时通过运行不一致性机制把直流分量长期控制在 ±1 以内。这套编码在千兆以太网、PCIe、SATA、光纤通道里广泛使用是有线高速串行链路的事实标准之一。再往后万兆以太网用 64B/66B把开销压到 3% 左右代价是必须配合扰码来保证跳变特性。开销越小对物理层器件的均衡能力要求越高这是典型的省了编码开销、加了模拟难度的取舍。线路编码跳变/时钟直流平衡码率典型应用NRZ无保证差100%短距板内信号曼彻斯特每比特必跳好50%10BASE-T、令牌环4B5B保证中80%100BASE-FX、FDDI8B/10B保证好80%千兆以太网、PCIe64B/66B靠扰码靠扰码约 97%万兆以太网5. 用 Python 把三种编码亲手搓一遍5.1 哈夫曼编码的实现与验证看代码比看文字更容易理解哈夫曼的构造过程。Python 标准库里的 heapq 拿来处理最小堆正好。import heapq from collections import Counter class Node: def __init__(self, freq, symNone, leftNone, rightNone): self.freq freq self.sym sym self.left left self.right right # heapq 需要可比较按频率比 def __lt__(self, other): return self.freq other.freq def build_tree(data): freq Counter(data) heap [Node(f, s) for s, f in freq.items()] heapq.heapify(heap) while len(heap) 1: a heapq.heappop(heap) b heapq.heappop(heap) heapq.heappush(heap, Node(a.freq b.freq, None, a, b)) return heap[0] def build_table(root): table {} def walk(node, prefix): if node.sym is not None: table[node.sym] prefix or 0 return walk(node.left, prefix 0) walk(node.right, prefix 1) walk(root, ) return table data ABRACADABRA root build_tree(data) table build_table(root) encoded .join(table[c] for c in data) print(table) print(原始长度:, len(data) * 8, 比特) print(编码长度:, len(encoded), 比特)跑一遍会看到ABRACADABRA 这 11 个字符里 A 出现 5 次、B 出现 2 次、R 出现 2 次、C 和 D 各 1 次。A 分到最短的码字C、D 分到最长的。原始按每字符 8 位算是 88 位编码后能压到 30 位上下。用真实语料时压缩率取决于符号分布的偏斜程度分布越不均匀效果越好。解码就是把编码流沿着树从根往下走遇到叶子输出一个符号再回根。需要注意短码是长码的前缀这一点在哈夫曼树上天然成立不会出现歧义。5.2 曼彻斯特编码的模拟实现曼彻斯特编码用代码模拟一下能直观看到它为什么占双倍带宽。def manchester_encode(bits, conventionieee): out [] for b in bits: if convention ieee: # 0: 高-低, 1: 低-高 out [1, 0] if b 0 else [0, 1] else: out [0, 1] if b 0 else [1, 0] return .join(out) def manchester_decode(levels, conventionieee): bits [] for i in range(0, len(levels), 2): pair levels[i:i2] if convention ieee: bits.append(0 if pair 10 else 1) else: bits.append(0 if pair 01 else 1) return .join(bits) data 1101001 enc manchester_encode(data) print(编码后电平序列:, enc) print(解码结果:, manchester_decode(enc))输出会看到 7 位数据变成了 14 个电平这就是带宽翻倍的直观体现。顺便可以试试把 convention 换一下验证之前的判断约定不匹配时解码结果会全反而且没有任何报错提示。5.3 CRC-32 的实现与交叉验证CRC 手搓一遍再和标准库的结果对齐是理解它参数含义的最好方式。import zlib def crc32_manual(data, poly0xEDB88320, init0xFFFFFFFF, xorout0xFFFFFFFF): crc init for byte in data: crc ^ byte for _ in range(8): if crc 1: crc (crc 1) ^ poly else: crc 1 return crc ^ xorout msg b123456789 print(手搓结果: %08X % crc32_manual(msg)) print(zlib 结果: %08X % (zlib.crc32(msg) 0xFFFFFFFF))标准测试向量 123456789 对应 CRC-32 的结果是 0xCBF43926。手搓代码里的 poly 0xEDB88320 其实是 0x04C11DB7 的反射形式因为标准 CRC-32 的过程用了反射输入输出。如果你把 init 和 xorout 改成别的值结果立刻就不一样——这就是前面说的参数坑调通信协议对接时务必把四个参数抄全。6. 实战里常见的坑和排查思路6.1 压缩率不达标怎么定位如果某段数据压缩后几乎没变小先做的不是换算法而是算一下它的熵。做法很简单统计字节值的频率分布代入熵公式估算一下。如果熵已经接近 8 比特每字节说明数据本身接近随机无损压缩确实没什么空间。加密过的数据、已经压过的数据、真正随机的采样都属于这一类。如果熵不高但压缩率还是差才轮到怀疑实现。常见的原因有哈夫曼没做码表压缩导致表本身占了大量空间数据分块太小每块都要重新传码表字典算法LZW的字典没及时重置膨胀后反而拖累效率。这些点逐一排查基本都能定位。6.2 通信偶发错位往哪儿查偶发性的数据错位、校验失败最容易被误判成信道噪声实际排查时应该按层次往下走。先看误码率统计如果误码率本身很低但错误集中在特定时刻出现多半是同步问题而不是信道问题。然后检查物理层的位定时余量接收端采样位置是不是压得太靠边。再看发送端的线路编码有没有保证足够的跳变长连 0/1 有没有通过扰码或线路编码处理。如果是位定时问题通常表现为错误随温度、电压、线长变化很有规律如果是真正的信道噪声错误分布更随机。这两类问题的现象差别其实挺明显的多看几次就能凭直觉分辨。还有一个高频坑是极性接反。差分曼彻斯特能免疫普通曼彻斯特和 NRZ 就不行接反了全错。排查时直接量一下空闲态电平就能确认。6.3 参数和现象速查表现象可能原因排查动作CRC 结果和别人对不上四个参数没对齐比对 init、poly、反射、xorout长数据流偶发失帧位定时漂移或失锁看跳变密度检查线路编码压缩率远低于预期信源熵本身很高先估算熵再查码表开销解码全反曼彻斯特约定相反或极性接反核对协议约定量空闲电平短包传输开销大码表或帧头占比高增大块长度或用规范哈夫曼6.4 几条我自己总结的实操心得第一做任何跨设备对接前先把编码约定、CRC 参数、字节序这些接口契约写成一张清单双方逐条确认。文档里看着一致、代码里实现不同的情况太常见了一晚上调不出来的问题往往就在这儿。第二能靠现成库的就别手搓。CRC、压缩、纠错码这些算法自己写的实现很容易在边界条件上出问题用经过验证的库更稳。手搓的过程适合学习理解不适合上生产。第三评估一个编码方案好不好别只看压缩率或者纠错能力要把计算开销、延迟、内存占用、实现复杂度一起算进去。嵌入式设备上一个压缩率高 1% 但内存翻倍的算法是不划算的一个纠错能力强但解码延迟翻番的方案在某些实时场景里也不能用。工程决策永远是综合权衡的结果。6.5 后续可以往哪儿深挖真想把这块吃透建议按这个顺序推进先把信息论里熵、互信息、信道容量这几个核心概念抠明白这是理解一切编码方案的底座然后自己动手实现一遍哈夫曼和 CRC建立直觉接着读 5G 或者 Wi-Fi 标准里的编码章节看看工业界现在在用什么最后可以拿 FPGA 或者软件无线电平台做点实际收发实验理论到硬件之间那层差距只有动手才能补上。我个人学下来最大的体会是编码这件事看着零碎其实背后有一条主线——用最小的代价对抗不确定性。信源编码里不确定性是内容本身的分布信道编码里是噪声线路编码里是物理介质的特性。抓住这条主线再多的名词也不会乱。