极化码SO-FSCL软输出解码：原理、实现与工程优化

1. 从“硬”到“软”为什么我们需要SO-FSCL在无线通信的纠错码领域极化码Polar Codes自被确立为5G eMBB场景的控制信道编码标准以来其地位就无可撼动。对于工程实现而言解码算法的效率与性能是决定其能否落地的关键。我们最熟悉的莫过于连续删除列表解码Successive Cancellation List, SCL它通过维护一个候选路径列表显著提升了传统连续删除SC解码的性能尤其是在中短码长下。然而标准的SCL解码器输出的是“硬判决”——即一个确定的0或1比特序列。在许多现代通信系统中比如采用迭代解码的Turbo或LDPC方案或者需要与高阶调制结合时接收端更希望得到的是“软输出”——即每个解码比特是0或1的可靠性度量通常用对数似然比LLR来表示。这个软信息可以作为下一级解码或处理的先验信息从而带来额外的性能增益。这就是SO-FSCLSoft-Output Fast Successive Cancellation List解码技术要解决的核心问题在保持SCL解码高速度和高性能的同时为每一个解码比特生成高质量的软输出。我最初接触这个问题是在一个5G基带芯片的预研项目中。当时我们需要评估在极低信噪比下控制信道的解码可靠性。单纯使用硬判决的SCL虽然误块率BLER已经不错但当我们试图将极化码与外部信道如多径信道或与其他编码级联时缺乏软信息成为了瓶颈。我们尝试过在SCL解码后简单计算外附信息但效果很差计算复杂度也高得离谱。直到深入研究SO-FSCL才找到了一个在性能、复杂度和可实现性之间近乎完美的平衡点。它不是一个空中楼阁的理论而是一个能直接嵌入到现有SCL解码器架构中的、极具工程美感的增强方案。2. SO-FSCL的核心思想在路径度量中挖掘软信息要理解SO-FSCL我们必须先回到SCL解码的基本原理。SCL解码可以看作是在一个二叉树上进行宽度优先的路径搜索。每解码一个比特当前所有存活路径都会分裂为两条对应比特0和1然后根据路径度量PM进行排序只保留度量值最好的L条路径L为列表大小。在解码结束时从最终存活的L条路径中选择PM最小的那条作为输出。那么软信息从哪里来一个最直观的想法是最终L条存活路径每一条都代表了对整个码字的一种“解释”。这些路径之间的差异特别是它们在某些比特位置上的不同选择本身就包含了关于该比特可靠性的丰富信息。如果L条路径在某一位上都选择0那么这一位是0的置信度就非常高反之如果有些路径选0有些选1那么这一位就比较“模糊”置信度低。SO-FSCL正是基于这一观察。它的核心创新在于不改变SCL解码的前向遍历过程而是在解码完成后利用整个解码过程中积累的所有路径信息——特别是最终存活列表中的路径以及它们在每个比特上的选择——来反向计算每个比特的LLR。这种方法巧妙地避免了为计算软输出而大幅增加解码延迟或重构解码流程实现了“快速”。具体来说计算第i个比特ui的软输出LLR一个经典且有效的方法是L(ui) ≈ log( P(ui0 | 接收序列y) / P(ui1 | 接收序列y) )在SCL的语境下概率P可以近似用最终列表中的路径来估计。假设最终列表中有L条路径其中在比特i上选择0的路径集合为S0选择1的路径集合为S1。每条路径l都有一个对应的路径度量PM_l通常为负对数似然值越小越好。那么比特i的LLR可以近似计算为L(ui) ≈ min_{l in S1} PM_l - min_{l in S0} PM_l这个公式的直观解释是我们分别找到在比特i上做出0和1决策的“最佳”路径即PM最小的路径然后用这两个最佳路径的度量值之差来反映该比特的可靠性。如果做出0决策的最佳路径远比做出1决策的最佳路径好PM小很多那么差值就是一个很大的正数强烈支持ui0反之则支持ui1如果两者最佳路径的PM差不多那么差值接近0表示该比特不确定。注意这里的“min”操作是因为PM是负对数似然越小代表似然概率越大。这个公式是SO-FSCL最常用的LLR计算方法因其计算简单、性能良好而被广泛采用。它被称为“基于最小路径度量的LLR计算”。3. 算法实现详解前向解码与后向LLR计算让我们把SO-FSCL拆解成可一步步实现的模块。整个算法分为两个清晰的阶段前向SCL解码和后向LLR计算。3.1 前向SCL解码阶段为软输出做准备这一阶段与标准SCL解码几乎完全相同但需要额外记录一些信息。步骤1初始化设定列表大小L码长N信息位长度K。初始化L条路径每条路径包含路径度量PM初始为0、部分和状态用于计算后续比特的LLR、以及一个长度为N的数组用于存储该路径对每个已解码比特的判决值0或1。准备一个大小为L的路径列表用于存活路径管理。步骤2逐比特解码与路径管理对于i从1到N按极化码解码顺序计算比特LLR对于当前每条存活路径根据接收到的信道LLR和之前比特的部分和计算当前比特ui的LLR值。这里使用的是标准的SC解码核如f/g函数。路径分裂每条存活路径根据当前比特ui的LLR分裂成两条候选子路径一条假设ui0另一条假设ui1。每条子路径更新其PM如果判决0或1与LLR的符号一致PM增加较小值log(1exp(-|LLR|))通常用查表或近似计算如最小和近似。如果不一致PM增加|LLR|。路径排序与剪枝此时有2L条候选路径。根据更新后的PM值对所有候选路径进行排序保留PM最小的L条作为新的存活路径。关键记录对于每一条新的存活路径必须记录它对于当前比特i的判决值0或1到其路径判决数组中。这是后续计算软输出的关键数据源。步骤3解码终止当所有N个比特解码完成后我们得到最终的L条存活路径。选择其中PM最小的一条路径的判决序列作为硬输出。同时这L条路径的完整判决数组和最终的PM值被传递给后向处理阶段。这个阶段与标准SCL的唯一区别在于第4步——需要持续记录每条路径在每个比特上的判决。这增加了一些存储开销每个路径一个N比特的数组但几乎不增加计算复杂度。3.2 后向LLR计算阶段从路径历史中提取软信息前向阶段结束后我们手头有L条路径每条路径有最终路径度量PM_final和一个记录了该路径对所有N个比特判决的数组decision[1...N]。计算每个比特i的软输出LLR(ui)的步骤如下分离路径集合对于比特i遍历所有L条最终存活路径。根据路径的decision[i]值将所有路径分为两个集合S0: 所有decision[i] 0的路径。S1: 所有decision[i] 1的路径。查找最小PM在集合S0中找到路径度量最小的值记为PM_min_0。如果S0为空极端情况则设置PM_min_0为一个很大的值如∞或采用惩罚值。在集合S1中找到路径度量最小的值记为PM_min_1。同理处理空集情况。计算LLRLLR(ui) PM_min_1 - PM_min_0。根据这个公式如果LLR(ui) 0则软判决倾向于ui0因为选0的最佳路径代价更小。如果LLR(ui) 0则软判决倾向于ui1。|LLR(ui)|的大小反映了可靠性绝对值越大越可靠。复杂度分析 后向计算需要对每个比特i遍历L条路径进行分类和找最小值总计算复杂度为O(NL)。这与前向SCL解码的复杂度O(LNlogN)相比是较低的尤其是当L不大时通常L8, 16, 32这个开销是可接受的。存储开销主要是每条路径的N比特判决记录总计O(LN)比特。3.3 一个简化实例L4的情况假设一个极短的码解码后最终4条路径的PM和第三个比特的判决如下路径编号最终路径度量 (PM)对比特u3的判决Path 11.20Path 22.11Path 33.00Path 44.51对于比特u3选择0的路径集合 S0 {Path 1, Path 3}其中最小PM为PM_min_0 1.2。选择1的路径集合 S1 {Path 2, Path 4}其中最小PM为PM_min_1 2.1。计算LLR:LLR(u3) PM_min_1 - PM_min_0 2.1 - 1.2 0.9。结果LLR(u3)0.9 0软输出倾向于u30且具有一定的可靠性因为0.9是一个中等正值。如果PM_min_0和PM_min_1相差很大比如5.0 vs 0.5那么LLR-4.5会强烈倾向于u31。4. 工程实现中的关键优化与踩坑点将SO-FSCL从论文公式转化为实际可运行的代码或硬件设计会遇到一系列教科书上不会提的问题。以下是我在多个项目中总结的关键点和踩过的坑。4.1 路径度量PM的表示与计算问题PM在解码过程中不断累加可能变得非常大。使用浮点数计算精度高但硬件不友好使用定点数需要仔细设计字长和动态范围。解决方案与经验定点数化在硬件实现中普遍采用定点数。需要分析LLR的动态范围以及路径度量的最大可能增长值。一个经验是对于列表大小L8或16PM的整数部分预留8-10比特小数部分预留4-6比特通常足够。必须进行充分的定点仿真与浮点结果对比确保性能损失在可接受范围内通常0.1dB。PM归一化这是SCL解码的常见技巧在SO-FSCL中依然重要且影响软输出。每当我们对2L条候选路径进行排序后可以对保留的L条存活路径的PM同时减去它们中的最小值。这样做不会改变路径间的相对顺序但能防止PM溢出。关键点这个减法操作必须在记录当前比特判决之后进行。因为后向LLR计算依赖的是路径间的绝对PM差值如果提前做了归一化这个差值的信息就丢失了。正确的顺序是更新PM - 记录判决 - 排序剪枝 - PM归一化。LLR近似计算在路径分裂时更新PM需要计算log(1exp(-|LLR|))。硬件中常用“最小和”或“偏移最小和”近似max(0, α*(β - |LLR|))通过选择参数α和β来逼近原函数。需要针对特定的信噪比范围优化这两个参数。4.2 后向LLR计算的高效架构问题后向计算需要为N个比特每个比特遍历L条路径朴素实现复杂度为O(N*L)。在高速解码器中如要求数Gbps吞吐量这可能成为瓶颈。优化方案并行查找单元对于每个比特i我们可以设计一个专用的比较电路。由于L通常不大≤32可以并行比较所有路径的判决位和PM值。例如用L个比较器同时判断路径判决是否为0并用一个最小树min-tree结构在符合条件的PM中快速找到最小值。同样为判决为1的路径设计另一套最小树。这样每个比特的LLR可以在几个时钟周期内算出。流水线处理后向LLR计算可以与下一个码字的前向解码流水进行。当前码字进入后向计算阶段时下一个码字可以开始前向解码充分利用硬件资源。存储优化每条路径的判决数组N比特是主要的存储开销。在硬件中这通常用寄存器文件或SRAM实现。可以考虑压缩存储例如只存储与信息位或冻结位相关的判决但这样会增加后向计算的寻址复杂度需要权衡。踩坑记录在一个FPGA原型项目中我们最初将每条路径的判决存在独立的Block RAM中。后向计算时需要同时读取L个RAM的同一地址对应比特i导致读写端口冲突和时序紧张。后来改为将L条路径的同一比特判决存储在同一块RAM的不同字中一次读取就能获得所有路径在该比特的判决极大地简化了后向计算逻辑并提高了频率。4.3 列表大小L的选择与软输出质量权衡问题L越大SCL解码性能越好但计算和存储开销线性增长。SO-FSCL的软输出质量也强烈依赖于L。经验之谈软输出质量的饱和当L较小时如L4最终列表中的路径多样性不足可能导致对于某些比特S0或S1集合为空。此时需要给空集赋予一个大的惩罚PM值但这会引入偏差。随着L增大软输出LLR的精度和可靠性显著提升。但通常L超过16或32后性能提升变得非常缓慢。对于大多数应用L8或L16是一个在性能和复杂度之间很好的折中点。与CRC辅助的结合在5G标准中极化码通常与CRC校验结合使用CA-SCL。解码结束后会用CRC从最终L条路径中筛选出第一条正确的路径。在SO-FSCL中一个常见的改进是在计算软输出时只考虑那些通过CRC校验的路径。如果有多条路径通过CRC则在这些路径中按上述方法计算LLR如果只有一条通过则该比特的LLR可以赋予一个固定的大值表示绝对可靠或者结合该路径的PM和次优路径的PM来计算。这种方法能显著提升软输出的准确性尤其是在高信噪比区域。冻结比特的处理极化码中有大量冻结比特Frozen Bits其值在编解码双方都是事先已知的通常为0。对于冻结比特其软输出LLR理论上应为无穷大对应已知值。在实现中我们可以直接将其LLR设为一个预设的最大值而不需要进行后向计算从而节省资源。4.4 软输出的量化与下游接口问题计算出的软输出LLR是浮点或高精度定点数如何传递给下一级处理模块如迭代解码器或解映射器解决方案动态范围压缩SO-FSCL产生的LLR动态范围可能很大。直接使用可能需要很多比特来表示。一个实用的技巧是进行饱和与限幅。例如分析LLR的统计分布设定一个最大值MAX_LLR和最小值-MAX_LLR将超出范围的LLR截断到边界值。MAX_LLR的选择会影响性能通常通过仿真确定比如8或16。量化比特宽经过限幅后的LLR可以用较少的比特数来量化如4比特或5比特。量化时可以采用均匀量化也可以采用非均匀量化如对高可靠性区域使用更精细的量化。在资源紧张的系统中4比特量化通常已经能保留大部分性能增益。接口时序需要定义清晰的握手信号。当后向计算完成所有N个比特的软输出LLR准备就绪后应产生一个有效信号下游模块在读取这些数据时可能还需要一个反压机制。5. 性能评估SO-FSCL带来了什么谈论任何解码算法的改进最终都要落到性能数据上。SO-FSCL的收益主要体现在两个方面作为独立软输出解码器的误码性能以及作为软信息提供者在级联系统中的整体增益。5.1 软输出解码的误块率BLER曲线我们可以通过仿真来对比标准SCL硬输出解码后直接输出硬判决比特。SO-FSCL软输出解码后输出LLR再将LLR进行硬判决符号函数得到比特。理想软输出如基于最大后验概率的BCJR算法复杂度极高作为参考上界。仿真结果通常会显示在低到中信噪比区域SO-FSCL的硬判决性能与标准SCL几乎完全重合。这是因为SCL本身已经接近最大似然性能其硬判决输出已经非常准确。关键增益在于软输出本身的质量。我们不能只看硬判决误码率而要看输出的LLR序列的统计特性是否接近“真实”的后验概率LLR。一个常用的评估指标是计算输出LLR与通过昂贵算法得到的近似真实LLR之间的均方误差MSE或者观察LLR的分布直方图。SO-FSCL的输出LLR分布通常与理想情况非常接近尤其是在使用较大L和CRC辅助时。5.2 在级联系统中的应用增益这才是SO-FSCL真正大放异彩的地方。假设一个系统模型信息先经过一个外码如LDPC码或卷积码编码再经过极化码作为内码编码然后发送。接收端先进行极化码的SO-FSCL解码得到软输出LLR再将这组LLR作为外码解码器的输入先验信息。对比实验方案A硬判决级联极化码用标准SCL解码输出硬比特给外码解码器。外码解码器只能基于可能有错误的硬比特进行解码。方案B软判决级联极化码用SO-FSCL解码输出软LLR给外码解码器。外码解码器如置信传播BP算法可以利用这些可靠性信息进行更有效的纠错。仿真结果几乎毫无悬念方案B的系统整体BLER性能会有显著的提升通常可以获得0.5dB到1dB甚至更多的额外增益。这个增益几乎可以看作是“免费”的因为SO-FSCL相对于SCL增加的计算和存储开销相对较小却为整个系统解耦和性能提升打开了空间。我在一个卫星通信的仿真项目中验证了这一点。我们将极化码与一个简单的卷积码级联使用SO-FSCL后在目标BLER1e-5处获得了约0.8dB的增益。这意味着在相同的发射功率下通信距离可以更远或者对于相同的距离可以降低发射功率。6. 总结与扩展思考SO-FSCL技术完美地诠释了工程上的“优雅”它没有推翻重来而是在已被充分验证的SCL解码骨架上通过巧妙的后期处理挖掘出了额外的、极具价值的软信息。它使得极化码不仅能作为独立的“硬判决高手”更能无缝融入现代通信系统中复杂的“软处理链条”。在实际项目中应用SO-FSCL我的体会是前期充分的定点化和性能仿真至关重要。必须明确系统对软输出精度和动态范围的要求据此确定PM和LLR的位宽、量化方案。后向计算的硬件架构需要精心设计以平衡速度、面积和功耗。此外SO-FSCL的思想可以进一步扩展。例如对于更长的码字可以采用“分段”的SO-FSCL将码字分成若干段每段独立进行列表解码和软输出计算以降低存储压力。也有研究探索在解码过程中动态地、选择性地为某些比特计算软输出而不是全部N个比特以进一步降低复杂度。最后不要忘记与CRC辅助解码的结合。在计算软输出时优先考虑CRC校验通过的路径甚至可以根据路径的PM值赋予不同的权重而不是简单地取最小PM路径这能在不增加列表大小L的情况下进一步提升软输出的质量。这些细微的改进往往就是在实际系统性能比拼中胜出的关键。