★ FEATURED ARTICLE 我这些年被问过最多的问题之一就是信息论里那些编码到底怎么分信源编码、信道编码、哈夫曼、LDPC、极化码……名字一堆关系又绕很多人学到后面直接记串了。其实把编码这条线捋清楚之后会发现它的逻辑非常顺一类编码在帮你“省空间”另一类编码在帮你“抗干扰”剩下的事情全是围绕这两件事展开的工程权衡。这篇总结不是教科书那种从头抄到尾的罗列而是把我自己学习和做项目时反复用到、反复踩坑的内容全部梳理成一套能直接拿去用的框架。无论你是准备面试、考试还是正在做通信系统、存储系统、文件压缩这类实际项目都应该能从这篇文章里找到用得上的部分。1. 编码体系全景先想清楚你面对的是哪种“编码”1.1 编码的本质是变换不是什么玄学编码这件事说到底就是“信息的表示形式变换”。同一个消息你可以用ASCII表示也可以用二进制表示还可以用一串带奇偶校验的码字表示。不同的表示方法对应不同的能力有的表示法很省比特有的表示法很抗噪但很难同时做到又省又抗。把这个逻辑想明白你就不会被各种编码名词带跑了。我习惯用一个特别朴素的类比信源编码好比出差前打包行李箱你拼命把衣服卷紧、把缝隙填满目的是少带箱子信道编码好比给易碎品裹气泡膜箱子变大了但磕碰一下东西也不会坏。一个是做减法一个是做加法方向完全不同。这两个方向对应着信息论里两大基本问题无失真压缩的极限是多少有噪信道上可靠传输的极限又是多少。前者的答案由信源编码定理给出后者的答案由信道编码定理给出。虽然行业里经常把“编码”当总称但你在选型的时候必须第一时间搞清楚自己到底在做哪件事。1.2 两大阵营的分工以及它们为什么容易被搞混很多人搞混信源编码和信道编码是因为它们都叫“编码”而且经常出现在同一个系统里。比如你打电话语音先做压缩信源编码再在无线链路上加纠错保护信道编码然后发射。如果只看链路层的数据你看到的全是冗余比特根本没有“压缩”的影子如果你只盯着压缩算法又完全看不到抗噪声的部分。这是两个层面的事情但它们会串联在一起工作。判断方法很简单看它的输出变长还是变短了。信源编码的目标是把数据变短所以平均码长会趋向于信源熵信道编码的目标是把数据变“结实”所以码字长度一定大于原始信息长度多出来的比特就是冗余。写到这里我突然想起来有些人会把“加密”也归类进来这又是一个常见的误解。加密的目标是让别人看不懂它既不压缩也不纠错是另一个维度的事情。至少在做信息论编码梳理的时候不要把加密混进去否则整条逻辑线会很乱。1.3 一张表看清两大阵营的经典成员为了让你后面读起来有谱我先给一张总表把主流编码全部铺开。阵营核心目标经典成员典型应用场景信源编码去除数据冗余降低存储/传输开销哈夫曼编码、算术编码、LZ77/LZ78、DEFLATE文件压缩、图像编码、流媒体传输信道编码增加可控冗余抵抗信道噪声汉明码、循环码、BCH码、卷积码、Turbo码、LDPC码、极化码存储系统、无线通信、卫星通信、深空通信这张表其实就是整篇文章的骨架。下面我会把表里的每一类展开讲包括它们为什么这么设计、怎么计算、实际工程里怎么取舍。你会发现这些编码没有一个是凭空冒出来的全都是某个具体问题逼出来的答案。2. 信源编码把冗余挤干净但要保证能还原2.1 从等长编码到变长编码节省比特的逻辑先问一个问题给你四个符号A、B、C、D每个符号出现的概率一样你用二进制表示它们需要几个比特答案是两个00、01、10、11这是等长编码。但如果四个符号的概率不一样呢假设A出现90%其他三个加起来10%你还会坚持每个符号都用两个比特吗显然不会。A应该用最短的码字比如1比特其他三个用稍微长一点的码。这样平均下来总比特数会明显下降。这就是变长编码的核心思想高频符号给短码低频符号给长码。但这里有个前提——你任意分配码长是不行的所有码字之间必须能唯一区分。最简单的做法是用前缀码任何一个码字都不能是另一个码字的前缀。比如A是0B是10C是110D是111这就是一组前缀码读的时候从左往右扫遇到一个匹配的码字就切一刀不会产生歧义。那最短能短到什么程度答案是信源熵。假设符号概率是p_i那么平均码长的下界就是信息的平均自信息量单位是比特。你在工程里经常会做一个检查算一下编码后的平均码长减去理论熵值多出来的部分就是编码冗余。如果冗余太多说明你的编码方案还有优化空间。2.2 哈夫曼编码自底向上的贪心合并哈夫曼编码是变长编码里最经典、也可能是你第一个学会的信源编码。它的构造过程可以概括为“反复合并两个最小概率的节点”。我举个例子。五个符号A、B、C、D、E概率分别是0.4、0.2、0.2、0.1、0.1。先取概率最小的D和E合并成一个0.2的节点现在集合变成了0.4、0.2、0.2、0.2再取两个最小的0.2合并成0.4接着集合变成0.4、0.4、0.2取0.2和一个0.4合并成0.6最后合并0.4和0.6得到1.0。树的构造完成之后从根出发左分支记0、右分支记1每个叶子就拿到了自己的码字。这套操作下来A和C可能拿到两位码字D和E会拿到四位码字。计算一下这组编码的平均码长是每个符号2.2比特。而五个符号的熵是多少算一下约等于2.122比特。实际码长距离理论极限只差了0.078比特编码效率大约96.5%在符号数量这么少的情况下已经相当不错了。我个人的体会是哈夫曼编码最大的优点不是它能逼近熵而是它构造简单、有明确的算法流程而且保证生成的是最优前缀码。缺点也很明显它需要知道每个符号的先验概率而且遇到符号概率不是2的负幂次时单符号编码很难完全达到熵极限。这时候算术编码就登场了。2.3 算术编码用一个小数表示整条消息算术编码的思路和哈夫曼完全不同。哈夫曼是给每个符号一个码字算术编码是给整条消息一个区间然后输出区间里的一个小数。不熟悉的人第一次听到这个会觉得特别玄其实过程不复杂。初始区间是[0, 1)根据每个符号的概率把当前区间按比例切分每读一个符号就把区间缩小到该符号对应的子区间。消息越长区间就越窄表示这个区间所需的比特数也会越多。最终输出区间内任意一个二进制小数接收端用同一个区间划分过程就能倒推出原始符号序列。算术编码的优势在于它可以把多符号的联合概率一次性编码而不是每个符号独立给码所以它能比哈夫曼更贴近熵极限。就算符号概率是像0.3、0.3、0.4这种“不太整齐”的数值算术编码也能应付得比较好。代价是计算过程必须高精度执行否则区间一偏整个序列就解错了。工程上常用整数运算实现自适应算术编码复杂度虽然比哈夫曼高但在很多压缩场景里值得。2.4 字典编码LZ77和LZ78的思路以及DEFLATE如果你只了解哈夫曼这种基于统计的编码那你面对文本压缩时会有个疑惑文档里的“the”“and”这些词反复出现但单独统计字符又统计不出什么名堂。这时你需要另一种思路把“重复出现的片段”用引用表示出来这就是字典编码。LZ77的思路是开一个滑动窗口。窗口里存着过去一段时间内出现过的数据当新数据和窗口里的某段匹配时就不输出原始内容而是输出一个“距离加长度”的引用比如“往前数3个字节连续复制18个字节”。LZ78则反过来它不是用滑动窗口而是维护一个不断增长的字典遇到新短语就加入字典。后续很多压缩工具用的DEFLATE算法就是LZ77加哈夫曼的组合先找重复再对重复的引用信息做二次熵编码。这个组合在工程上非常能打。你电脑里的很多文件压缩软件、网站传输用的压缩格式核心都是这套东西。我在实际项目里试过用这套思路压缩结构化文本压缩率可以轻松达到几比一。要注意的是字典编码对重复度高的大文件效果好对小文件反而可能因为保存字典等额外信息导致压缩后比原来还大。3. 信道编码故意加冗余和噪声对着干3.1 信道编码的基本模型码率、最小距离与纠错能力切换到信道编码问题变成了信号经过有噪声的信道怎么保证接收端还能正确恢复答案听起来有点“笨”——加冗余。假设你有k个信息比特把信息映射成一个n比特的码字其中n大于k这就是一个(n, k)编码。码率R等于k除n码率越低冗余越多抗噪声能力越强但同时传输有效数据的速度也越低。这本身就是第一个工程权衡点。光加冗余还不够不同的冗余添加方式决定了不同的纠错能力。教材里通常用“最小距离”来描述一组码字之间的差异把任意两个码字逐位比较不一样的位数的数量就是这两个码字的汉明距离所有码字对里最小的那个就是码的最小距离d。如果最小距离是3说明任意两个码字至少有3位不同那么接收端最多可以安全地纠正发生在单个码字里的1位错误因为错1位之后它离原始码字依然比离任何其他码字都近。这个“距离”视角特别像城市里的小区。每个码字是一栋楼它周围画了一圈半径t的安全区只要错误没把接收向量推出安全区你就能判断它属于哪栋楼。设计信道编码的本质就是在一维、二维甚至更高维的向量空间里尽量多塞一些互相隔得够远的码字。3.2 线性分组码与汉明码最简单的纠错例子线性分组码是一大类码它的结构可以用矩阵描述信息比特乘一个生成矩阵得到码字。为什么强调“线性”因为线性结构能大幅简化译码过程——任何两个码字相加还是码字这样你只需要关心错误图样而不需要逐条比对码表。汉明码是最经典的线性分组码以(7, 4)汉明码为例4个信息比特变成7个码字比特多出来的3位是奇偶校验位。它的校验矩阵有7列每一列是3比特的一个非零向量。译码时先计算伴随式如果伴随式是全零说明没有检测到错误如果伴随式是某个非零向量它的值正好对应出错位置的列号翻转那一位就完成纠错了。这种“伴随式直接告诉你在哪出错”的设计非常优雅。我在讲给别人听时喜欢强调汉明码只纠1位错误这在很多信道场景其实是够用的因为很多系统的底层本来就只要求把差错率压到很低的水平剩下的是靠重传和上层协议解决。但如果你遇到连续多位错汉明码就无能为力了。3.3 循环码与CRC从数学到硬件好实现的校验码线性分组码里有一个重要的子类叫循环码它要求码字循环移位后仍然是码字。这个性质让它可以用多项式运算来统一描述非常适合硬件实现也方便用移位寄存器构成编码器。BCH码就是循环码的一种扩展它通过选择特殊的多项式来获得比较大的最小距离能纠正多位错误在存储领域很常用。CRC循环冗余校验虽然名字里有“校验”但它是循环码思想里最接地气的应用。它的计算方法是把待发送数据当作一个多项式的系数除以一个约定的生成多项式得到的余数就是CRC校验值。接收端重新计算余数如果余数不为零就认为数据出错了。这里我必须强调CRC是检错码不是纠错码它只能告诉你“这包数据坏了”不能告诉你坏在哪几位。工程里CRC的定位是“可靠性兜底”。你想想看很多通信协议和数据存储场景里因为信道本身有纠错能力可能绝大多数据都被修好了但万一出现一个超出纠错能力的错误CRC会把这一帧标记为错误并触发重传。没有CRC兜底你根本不知道被“修复”的数据到底修对了没有。3.4 卷积码与维特比译码带记忆的编码器分组码处理数据是按块来的但很多通信系统是连续比特流。这时候用卷积码更自然。卷积码的编码器是一组移位寄存器和异或门它输出的每个比特不但和当前输入比特有关还和前几个输入比特有关。这个“记忆”特性让卷积码可以看作一个有限状态机每个时刻的状态由寄存器内容决定输入0或1会让状态转移到新状态同时输出对应的编码比特。维特比译码就是在这个状态图上找一条最优路径的算法。给定接收序列它从初始状态出发逐段比较每个状态转移的“代价”保留每个状态上累积代价最小的路径。到终点时代价最小的那条路径对应的输入序列就是最大似然译码结果。我第一次接触维特比算法时感觉这东西像个动态规划后来发现确实如此。它的计算量比硬判别的汉明码译码大不少但它能利用“软信息”即把接收符号的可信度也纳入距离计算获得非常好的性能。早年代通信系统里卷积码加维特比译码是绝对主力直到Turbo码出现才被挑战。4. 现代编码逼近极限的三次接力4.1 Turbo码两个分量码和一个交织器很长一段时间里大家都认为找到一种既能纠错又容易工程实现的编码已经到瓶颈了。Turbo码的出现打破了这种局面原理可以用一句话概括两个卷积码通过一个交织器并联译码时在两个分量译码器之间来回交换“软信息”。这个“交换软信息”的机制是关键。第一个译码器吐出的不仅仅是硬判决结果还带着对数似然比即每个比特为0和为1的概率比值。第二个译码器把这些信息当作先验信息继续译然后把自己更新的信息反馈回去。迭代几次之后误码率会明显下降。这个思路后来被称为迭代译码它让编码性能一下子接近了理论极限。Turbo码的缺点也很鲜明交织器会引入延迟迭代译码的计算量不低所以对时延敏感的场景要谨慎。当年它在移动通信标准里能大规模商用是因为系统设计了比较灵活的交织深度和迭代次数可以按需调整。4.2 LDPC码稀疏校验矩阵下的置信传播LDPC码其实上世纪60年代就被提出来了但当时硬件完全消化不了这种“稀疏校验矩阵”的译码计算量后来被重新发现才翻身。LDPC码的校验矩阵特别之处在于“稀疏”矩阵里1的数量很少。这个矩阵可以用一个二分图来表示一边是变量节点对应码字中的每一个比特另一边是校验节点对应每个校验方程。如果校验矩阵里第i行第j列是1就把变量节点j和校验节点i连上一条边。译码时每个变量节点从信道拿到初始的软信息然后用自己的信息给相邻校验节点“投票”校验节点综合收到的信息判断自己对应的校验方程应该让哪些变量更倾向于0或1再把反馈传回去。这个过程反复迭代所有校验方程都不再矛盾时就得到一组合理译码结果。因为图中节点是并行更新的LDPC译码在硬件上天然可以做成高度并行这对高吞吐系统特别有吸引力。实际项目里LDPC还有一个好处码参数灵活。你可以根据信道质量调整校验矩阵的维度自由选择码率和码长这让它成为很多现代通信系统里数据信道的首选。4.3 Polar码信道极化与递归构造Polar码是三种逼近极限的码里最年轻的但思路反而最“信息论”。它基于一个叫信道极化的现象把一堆独立信道的输入输出组合起来再拆分成N个虚拟信道你会发现这些虚拟信道出现了分化一部分信道的容量接近1几乎无噪声另一部分信道的容量接近0完全是纯噪声。这个过程像筛豆子筛到最后好豆子和坏豆子分得很开。编码时极化码把信息比特放在那些容量接近1的位置上那些“坏信道”的位置就填固定比特冻结比特接收端反正知道这些位置是什么值可以不译或者强制当作先验信息。译码可以用改进的逐次消除算法配合路径排序之后性能已经能和LDPC、Turbo在同一水平线竞争。而且极化码在短码长下的表现经常比LDPC还好这对控制信道这类短包场景是巨大的优势。我见过的不少新系统控制信道用极化码、数据信道用LDPC恰恰就是看中了极化码短码性能过硬的特点。5. 编码选型与工程落地性能、成本与坑5.1 选型时先看这几个指标我在实际项目里做编码选型时不会只看“谁纠错能力强”。纠错强往往意味着译码复杂、功耗高、时延大这个代价在有些场景根本付不起。通常我会列一张检查表核心指标就五个编码增益、译码复杂度、时延、硬件开销、码率灵活度。编码增益这个词值得解释一下。它是指在相同的误码率下采用编码之后比未编码时节省了多少信噪比。比如某种编码要求误码率在1e-5未编码系统需要信噪比9.6dB采用某LDPC方案之后只需要1.2dB那编码增益就是8.4dB。你在方案汇报时别人更爱听“能省多少信噪比”而不是“距离理论极限差多少”。指标关注点典型影响编码增益同误码率下节省的信噪比决定链路预算和发射功率译码复杂度每比特需要多少运算决定芯片面积和功耗时延编码块大小加迭代次数决定能否用于实时交互硬件开销存储、迭代次数、并行度决定成本和生产难度码率灵活度能否动态调整信息比特比例决定自适应传输能力拿这些指标套场景时你会发现存储系统要低误码、高吞吐、容忍中等时延所以LDPC经常是首选短报文遥测这类场景每个包可能只有几十字节用长码反而不划算BCH码或卷积码可能更合适低功耗传感器节点CPU弱、内存小那就别碰大规模迭代译码老老实实用汉明码或简单的循环码。5.2 常见坑一把CRC当纠错码用我在不少代码评审里见过这样的设计数据帧加了一个CRC之后接收端发现CRC校验失败处理方式是“去掉校验字节继续解析后面的内容”。这种用法的隐患是CRC只能检测错误不能定位错误你根本不知道坏的是哪一位反正“校验没过”这个事实已经说明数据不可靠了。正确做法是丢弃或者请求重传而不是继续用。还有一种情况是在已经用强纠错码的链路上过度使用粗粒度校验导致每一帧都带大量CRC字段有效载荷占比下降。CRC的长度要按帧长和信道误码率来定不是越长越安全。5.3 常见坑二只关心随机错误忘了突发错误信道编码教材里讲的纠错能力默认错误是随机分布的比如误码率1e-4意味着平均一万个比特里错一个具体错在哪一位是独立的。但真实信道经常不按这个套路出牌。无线信道一个深衰落就能导致连续几十上百个比特全错这种情况下再强的纠错码也会被打穿因为错误的集中程度已经超过码字的设计纠错能力。解决手段是交织。发射前把码字的比特顺序打乱让原本位置相邻居的比特分散到不同的码字里去这样连续错误到达译码器时就被“摊开”了。接收端先解交织再把“鸡蛋壳被撞碎但鸡蛋本身没坏”的数交给译码器。这一点在存储系统里同样存在。磁盘坏道是成片出现的如果编码器没有应对突发错误的机制坏道一覆盖就是一片码字全挂。所以很多存储方案会在纠错码之外再做一层交织或加长码字来分摊风险。5.4 常见坑三码率选择与反馈重传的权衡很多人误以为码率越低越好冗余越多纠错越强。但码率降低会让有效吞吐率下降。本来信道速率是10Mbps码率1/2之后实际能传的数据最多只有5Mbps。如果你可以用自动重传请求来保证可靠性那在中等信道质量下直接用一个较高的码率加轻量重传往往比一味堆低码率更高效。自适应调制编码系统就是干这个的信道好的时候用高码率多传数据信道差的时候用低码率多保数据。动态调整的依据是信道质量反馈和误码统计。选型的时候一定要把“重传”当成系统级的可选机制来考虑而不是把所有可靠性要求都压在信道编码这一层上。做过几个真实项目之后我的体会是编码选型从来不是“最新最强”的赢而是“适合场景”的赢。你问我推荐哪个如果场景是大吞吐连续数据流我会选LDPC如果场景是短突发控制信息极化码很有优势如果只是给一个协议帧加个完整性保障CRC才是最务实的答案。最后再分享一个小技巧。不管用哪种编码调试的时候一定要先把“无错误信道”跑通。先确认编码器输出的码字能被译码器原样还原再往信道里逐步注入随机错误。很多项目一开始就跳到误码率测试结果编码器本身位序错了都不知道后面排查起来特别折磨人。先把基线建立好后面每一步都有据可循这个习惯能帮你省下非常多时间。
阅读完成 · 觉得有帮助？
