做通信算法这些年经常被同行问到极化码。尤其是5G标准落地之后很多人听说控制信道用了极化码但又搞不清楚它和LDPC到底差在哪为什么偏偏是它被选中。每次解释我都得从“信道极化”这个底层现象讲起讲完之后对方一般都能理解为什么极化码会成为编码界的一个里程碑。干脆把这份讲解整理成一篇笔记写给项目组的新人也分享给所有对极化码感兴趣的人。这篇内容不追求堆公式重点是把极化码是什么、怎么工作、工程上怎么用、有哪些坑讲透尽量让没有编码理论基础的初学者也能跟上。1. 极化码是什么先给一个能直接落地的概括1.1 一句话定义和五个关键要素极化码是一种线性分组码它的编码和译码都建立在“信道极化”现象之上。所谓信道极化是指把一大堆独立信道通过特定的合并与分裂操作重新组合之后这些信道会沿着两个极端方向分化一部分信道变得几乎完全可靠另一部分信道变得几乎完全不可靠。于是信息比特可以只放在那些变得可靠的信道上传输不可靠的信道全部用来传约定好的固定比特。这样信息传输的错误率就能趋近于零。如果要在一句话里说出极化码最重要的身份标签那就是它是第一个在理论上被严格证明可以达到香农极限的构造性编码方案。这里“构造性”三个字非常关键。早期逼近香农极限的方案比如Turbo码和LDPC码都是通过迭代译码在实际性能上逼近极限但理论上始终缺少一个严格的构造性证明。极化码是同一个思路的对立面它先给出一个确定性的构造方法然后从理论上证明当码长足够长时错误率可以做到任意小。对于做工程的人来说记住下面这几点就够用了码长必须是2的幂次方常见长度是256、512、1024。编码复杂度是O(N logN)译码复杂度也是O(N logN)实现成本很低。核心操作是信道可靠性的排序信息只放在可靠的信道上。译码主流方案是SC、SCL和CA-SCL性能逐级提升代价是计算量增加。它在5G标准里被用于控制信道的编码数据信道则用了LDPC。1.2 和Turbo码、LDPC码的本质区别传统的优秀编码方案走的是“随机化纠错”路线。以LDPC为例它构造一个超大规模的稀疏校验矩阵信息比特和校验比特之间建立一种看似随机但具有约束关系的连接。译码时通过概率消息在图上反复传递逐步修正错误。这种方案性能非常好但问题是它没有从理论上严格证明为什么这个结构能逼近香农极限实际性能是靠大量仿真验证出来的。极化码完全不同。它的构造思想不是“纠错”而是“筛选”。通过信道变换把一批等同的信道变成一批好坏悬殊的信道然后在好的信道上传输信息。这个过程是确定性的存在严格的理论证明可以算出哪些信道趋近于可靠、哪些趋近于不可靠并给出明确的错误概率上界。这是它在理论地位上独特的地方。不过要注意理论上的优雅不等于实现上的顺手。极化码在有限码长下的性能受极化不完全的影响需要配合CRC校验和列表译码来弥补这是工程上绕不开的话题。1.3 一个直观的例子能量再分配可以把信道极化想象成一个水箱的分流过程。假设有N个大小完全相同的水管每个水管的水流量都代表一个信道的容量。现在构造一套复杂的管路系统把N个水管重新并联串联最后出口处的水流量不再均匀分配而是集中在少数水管上其余水管几乎断流。被集中的水管就是“可靠信道”断流的则是“不可靠信道”。在这个比喻里总水量不变对应的就是各个比特信道的容量之和等于原始信道的总容量。也就是说极化过程不损失任何理论上的容量它只是把容量重新分配了。这就是极化码能够逼近香农极限的底层原因。能理解这一点后面的所有讨论都有了根基。2. 信道极化现象从两个信道合并说起2.1 信道容量到底是什么讨论极化之前必须先明确什么是信道容量。香农给出的定义是在一个信道上能够可靠传输信息的最大速率单位是比特每信道使用。简单说如果信道容量是0.5就意味着平均每发送一个符号最多只有半个比特的信息能可靠到达接收端再多就会出错。为了便于分析很多理论研究都会使用二进制删除信道BEC作为参照模型。这种信道的行为非常直观发送0可能收到0也可能收到一个代表“丢失”的符号发送1同理。删除概率ε表示信息丢失的概率。BEC的容量就是1-ε。如果ε0.5那么信道容量就是0.5也就是每次传输平均只有0.5比特的信息能通过。BEC模型的好处是一切计算都是可解析的非常适合用来理解极化。2.2 两个信道合并后发生了什么现在做一件关键的事情把两个容量为0.5的BEC信道合并成一个双输入双输出的系统。具体操作可以这样描述。有两个独立信道记为W同时有两个输入比特u1和u2。构造的方式是x1等于u1与u2的异或结果x2等于u2。把x1送到第一个信道传输x2送到第二个信道传输。接收端同时得到两个观测值y1和y2。此时站在u2的角度看它同时被两个观测值保护着因为y1里也携带了和u2相关的信息相当于送了两次。于是u2面对的信道可靠度变高了。而站在u1的角度看它送出去的信息被x1和x2做了关联处理但在接收端人们先要处理u2才能推断u1这个过程引入了更多不确定性于是u1面对的信道可靠度变低了。在BEC上定量计算的话如果原始信道W的删除概率是ε那么极化后次信道u2所在信道的删除概率是ε²它对容量变成了1-ε²。而剩下的那个信道u1所在信道删除概率是2ε-ε²容量对应是(1-ε)²。当ε0.5时原始容量是0.5极化后一个是0.75一个是0.25。更关键的是0.75和0.25加起来正好等于1也就是两份原始容量之和一分不多一分不少。2.3 递归极化码长翻倍带来的极端分化上面只是一个最基本的二级合并。把合并后的系统当作一个新的“信道单元”再和另一个同样处理过的单元合并就得到四路输出的系统。这样递归下去每做一次合并信道数量翻一倍信道的两极分化也会更明显。对全体等效信道做统计会发现随着合并次数增加信道容量分布逐渐移向0和1这两个端点。容量接近1的信道比例越来越接近原始信道容量容量接近0的信道比例越来越接近1减原始信道容量。也就是说如果一个信道原本的容量是0.5那么经过充分极化后大约一半的信道会趋向于完全可靠另一半趋向于完全不可靠。这正好对应信息理论里“最多只能传一半信息”的直觉。这个递归过程在数学上非常优美它对应的是一个马尔可夫链的分支过程可以通过状态转移来计算每个信道的错误概率上界。这也是极化码能给出严格证明的原因。2.4 用班级成绩分布来类比理解极化还有一个非常贴近生活的类比一个班级刚开始所有学生成绩差不多。经过一种特殊的分班机制把学生重新组合每一次组合都会让一部分学生成绩明显提升另一部分明显下降。反复操作多次之后班级里出现两极分化一部分学生稳定高分一部分学生稳定低分。这时候如果让低分学生去参加高考显然不合理。于是极化码做的事就变成了只让那些稳定高分的学生去考试低分学生一律弃考。所谓“弃考”就是传输事先约定好的固定比特接收端提前知道它们的值所以不需要真的传信息。结果就是整个班级的“可靠升学率”非常高。这就是极化码的本质。3. 编码怎么做矩阵、蝶形网络和比特选择3.1 编码矩阵和蝶形网络极化码的编码器结构非常类似快速傅里叶变换中的蝶形运算网络。设码长为NN等于2的n次幂。编码过程就是对N个输入比特做n级蝶形变换每一级有N/2个异或运算所以总计算量是NlogN级别这个复杂度在工程上是完全可控的。数学上编码可以写成输入向量乘以一个生成矩阵。这个生成矩阵可以看作一个基础异或矩阵的n次克罗内克积。比如N等于2时输入(u1,u2)经过变换后输出的x1等于u1异或u2x2等于u2。N等于4时编码可以拆成两级蝶形运算每一级都重复同样的异或规律。这种结构的巧妙之处在于它正好对应了信道极化的过程。编码的每一级蝶形变换就是一次信道合并N级变换恰好完成了N次递归极化。编码本身和极化理论是完美对应的而不是先有极化现象再勉强设计编码矩阵。3.2 可靠性排序密度演进和极化权重法编码时最重要的步骤是确定哪些比特信道是可靠的、哪些是不可靠的。如果选错了位置把信息比特放到了不可靠信道上译码性能会大幅恶化。所以信道可靠性排序是极化码的核心算法之一。最经典的方法是密度演进。它通过概率密度函数在蝶形网络上的传播来精确计算每个比特信道的错误概率。理论上最精确缺点是计算量大因为要对整个概率密度做卷积运算。工程实现里常用它的近似版本高斯近似假设信道满足高斯分布只需要追踪均值和方差计算量大大降低。更高阶的简化方案是极化权重法这也是5G标准里实际使用的方案。它不依赖信道模型的详细参数直接根据比特位置的二进制展开形式计算一个权重值然后按权重排序。权重计算公式非常简单接收端只需要查表就可以得到完整的可靠性排序硬件实现非常友好。这也是极化码能够从学术研究走向标准落地的重要原因之一。3.3 信息比特放置与冻结比特填充得到可靠性排序后编码方案就变成了一个纯粹的规则。假设码长N要传K个信息比特码率是K除以N。从N个比特信道中选出可靠性最高的K个信道把K个信息比特放进去。剩下的N减K个信道全部填0这些位置叫做冻结比特。接收端译码时遇到冻结比特的位置不需要做判决直接把它当作0。这相当于告诉译码器这些位置不可能有信息等于把已知条件压缩进了译码过程。冻结比特的位置在编码端和译码端必须完全一致所以它们通常由协议预先规定。如果收发双方对冻结位置的理解不一致整个译码结果就会崩溃这是实现中最容易出现隐性bug的地方。3.4 速率匹配与打孔实际系统的码率不是任意可选的。5G标准里要求很多种传输块大小但极化码的母码长度只能是2的幂次。当需要传输的比特数量不满足这个约束时就要做速率匹配。最常用的做法是打孔即从编码后的比特中丢掉一部分不发送或者用缩短的方式把某些输入位置强制置为可靠位然后不发送对应输出。打孔位置的选择直接影响性能因为不同位置的比特对极化过程的贡献不同。好的打孔策略会尽量选择那些“重要性较低”的输出位置避免伤及核心的可靠信道。合理的速率匹配设计是极化码工程化过程中最考验细节的部分。4. 译码怎么做SC、SCL和CA-SCL4.1 SC译码的核心思路SC译码全称连续抵消译码它的思想可以概括为“按顺序猜边猜边修正”。由于极化码的编码过程引入了比特之间的递推关联译码时可以从第一个比特开始逐个计算出每个比特的对数似然比先判断当前比特是0还是1然后把这个判决结果作为已知条件带入下一级的计算。这个过程和回溯算法很相似。每一步都在利用之前所有已判决的信息来削弱当前比特的不确定性。编码时信道已经完成了两极分化所以那些可靠性较高的比特信道在SC译码下错误率很低而可靠性较低的比特信道由于被冻结根本不需要判决。SC译码的复杂度是O(NlogN)非常适合硬件实现。但它的缺点是判决过于激进一旦某个信息比特判错后续所有比特都会受到连带影响最终出现连续的错误爆发。这种错误传播现象是SC译码的先天短板。4.2 LLR计算和蝶形因子SC译码在计算过程中使用对数似然比来度量每种取值的可信程度。LLR定义为某个比特为0和1概率之比的对数。在蝶形网络里上一级的LLR可以由下一级的两个LLR组合得到公式形式很简单一组是取符号和最小绝对值运算另一组是带判决反馈的加法运算。工程实现时很多代码直接用最小和近似来代替精确的对数域计算。也就是把原先需要计算ln和求和的部分简化为比较和符号运算。这样做的损失很小但实现的资源消耗大大降低。仿真时如果发现性能比理论值偏差明显可以先确认是不是LLR计算中的符号约定搞反了这是我见过的高频初级错误。4.3 SCL路径保留与路径度量为了克服SC译码的激判决问题SCL译码引入了列表机制。它的思路是在每一个信息比特位置同时保留0和1两条候选路径而不是直接选其中一条。如果每一步都两路扩展路径数量会指数爆炸所以需要设定最大列表长度L每次只保留得分最高的L条路径。路径的得分就是路径度量累计代表该条路径在当前观测下有多可信。判决路径会不断叠加最终选出度量最优的一条作为译码结果。L越大保留的候选路径越多性能越好但计算复杂度也近似乘上L倍。实际系统经常在L等于8、16、32这几个档位之间权衡。简单说SCL译码是在SC框架里加入了“多个假设并行推进”的能力相当于考试时不再只选一个答案而是同时涂写多个备选答案等全部题目做完再检查哪个组合最合理。4.4 CRC辅助工程上最后一锤定音SCL译码仍然有一个问题路径度量最优的路径未必是正确的码字尤其是当L不够大时。如果信息序列本身带有循环冗余校验情况就完全不同。CRC相当于给信息比特加了一层错误检测的能力。译码时先从L条候选中找出所有能通过CRC校验的路径然后在其中选路径度量最优的。由于CRC能够排除大概率是错误的候选路径这使得CA-SCL译码的性能相比普通SCL有明显提升。这也是5G标准采用极化码时一定要搭配CRC的原因。实际仿真中CRC长度一般取8到16比特短CRC检测能力弱长CRC会占用有效码率这个平衡需要根据系统需求调整。使用CA-SCL之后有限码长下的极化码性能已经可以和LDPC码掰手腕了。5. 工程落地评价性能、复杂度和标准里的选型5.1 复杂度对比很多初学者会误以为极化码从理论到实现都“便宜”。其实极化码的编码复杂度确实很低但译码复杂度取决于算法选择。这里给出一个典型的复杂度对比表方便做方案选型时参考。算法编码复杂度译码复杂度性能档位SCO(N logN)O(N logN)基础档SCLO(N logN)O(L·N logN)中档CA-SCLO(N logN)O(L·N logN)高档LDPC迭代O(N logN)O(N logN)中高档从表里能看出来极化码的编码复杂度一直很低译码复杂度需要靠L来控制。工程选型时如果系统对时延极其敏感通常会在L上做文章。很多硬件实现会选择L等于8在性能损失和复杂度之间取得良好的平衡。5.2 不同码长和码率下的性能经验极化码有个非常明显的趋势码长越长极化越充分性能越好。码长256时即使使用CA-SCL性能也不如经典的Turbo码但码长1024以上极化码的优势就会逐渐显现出来。不过5G控制信道的实际信息长度往往很短极化码在这个场景下靠的是低码率下优异的纠错能力。码率的选择也很有讲究。高码率意味着信息比特占比较大可靠信道不够用性能会下降。低码率下极化码有大量冻结比特帮忙性能反而容易做到很好。这也是为什么控制信道这种信息量少但可靠性要求极高的场景特别适合极化码的原因。实测下来在码率0.5附近码长1024的情况下CA-SCL配合L等于32性能已经接近LDPC码的常用表现。如果码率降到0.25以下极化码在短数据包上的表现会更好误块率要低好几个百分点。这些数字在不同仿真配置下会有区别但趋势是稳定的。5.3 为什么控制信道选了极化码5G标准里数据信道用了LDPC控制信道用了极化码这个分工不是随意的。数据信道的负载大、码率偏高LDPC在这方面有自己的优势控制信道的数据量小、可靠性要求极高而且很多控制消息是一次性传输没有重传机会必须在单次传输中做到极低错误率。极化码的独特价值在于它在极短码长和低码率下的性能表现稳定并且自带一种“确定性收缩”的能力可以精确地适配各种信息长度。再加上编解码复杂度低冻结比特规则清晰硬件实现友好。综合考虑极化码成了控制信道最合适的选择。6. 常见坑与学习建议6.1 新手最容易犯的五个错误第一个错误是冻结比特的位置写错。很多人在实现时容易把冻结位置默认成前N减K个位置但实际上必须严格按照可靠性排序来计算。位置不同系统的性能是两个世界。第二个错误是LLR符号约定不一致。极化码实现了两种主流约定一种是正值代表0负值代表1另一种正好反过来。如果编码端和译码端采用不同约定性能会瞬间崩坏而且这种错误非常难排查。第三个错误是忽略速率匹配的影响。很多人仿真时只做整数码长的理想测试一旦加入打孔就发现性能大幅恶化于是怀疑极化码本身有问题。实际上这是打孔策略没有设计好可靠信道被误伤了。第四个错误是不做CRC辅助就寄望SCL达到完美性能。SCL不是万能药L值不够大时最优路径也可能错。CRC辅助带来的增益在短码场景下非常显著。第五个错误是直接用原始概率域进行计算忽略了数值稳定性。SC译码在长码下概率值会变得极小必须使用对数域运算。如果坚持用概率乘法很容易出现下溢溢出仿真正确性大打折扣。6.2 仿真与调试的小技巧我做极化码仿真时的习惯是先做超小码长验证再上完整系统。比如先实现N等于4或8的编解码用手动逐个比特验证每个环节的输出确保冻结比特位置、LLR计算方向和校验关系全部正确再扩展到N等于128、256。这样做省去了大量时间。调试时最有效的手段是打桩对比。在编码端和译码端分别导出中间变量检查每一级蝶形的输出是否符合预期。如果第一级就出错根本不需要怀疑后面的SCL路径管理。先确认基础链路正确再优化性能细节。另外建议把仿真结果分三层记录理论曲线、无速率匹配的仿真曲线、带速率匹配的仿真曲线。三层对比能够快速定位问题是出在算法本身还是工程实现细节上。如果三者差异过大八成是速率匹配或者冻结比特计算引入了错误。6.3 学习路线建议想学极化码不建议一上来就钻复杂度极高的密度演进推导。我的建议是先理解BEC信道下的完全极化过程亲手算一遍N等于2和4的容量变化获得直觉后再去看一般信道的近似算法。然后动手写一个最简单的SC译码器配合仿真数据逐点调试对极化的理解会立刻加深一层。当基础链路跑通之后再引入SCL和CRC这时候你对“路径度量”和“候选路径排序”的理解会来得非常扎实。最后再去看标准文档里的可靠性序列和速率匹配方案会发现那些看起来很技术化的表格本质上就是你手写代码时算出来的排序表。整个过程不需要特别深奥的数学功底线性代数和概率论基础就能完全覆盖。极化码的迷人之处就在于它把香农极限从一个遥不可及的理论目标变成了一个可以用清晰规则直接构造的编码方案。每次搭建完整个编解码链路回头再看信道极化的过程都会感叹那个从两个信道合并开始的小操作竟然能延伸出一个完整的标准编码方案。对于那些正在学编码理论的人我强烈建议不要只停留在公式推导亲手跑一遍N等于512的完整链路那种从仿真曲线上看到性能逼近极限的成就感是任何教科书都给不了的。