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

1. 从“硬”到“软”：为什么我们需要SO-FSCL？

在无线通信的纠错码领域，极化码（Polar Codes）自被确立为5G eMBB场景的控制信道编码标准以来，其地位就无可撼动。对于工程实现而言，解码算法的效率与性能是决定其能否落地的关键。我们最熟悉的莫过于连续删除列表解码（Successive Cancellation List, SCL），它通过维护一个候选路径列表，显著提升了传统连续删除（SC）解码的性能，尤其是在中短码长下。然而，标准的SCL解码器输出的是“硬判决”——即一个确定的0或1比特序列。在许多现代通信系统中，比如采用迭代解码的Turbo或LDPC方案，或者需要与高阶调制结合时，接收端更希望得到的是“软输出”——即每个解码比特是0或1的可靠性度量，通常用对数似然比（LLR）来表示。这个软信息可以作为下一级解码或处理的先验信息，从而带来额外的性能增益。这就是SO-FSCL（Soft-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(ui=0 | 接收序列y) / P(ui=1 | 接收序列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小很多），那么差值就是一个很大的正数，强烈支持ui=0；反之则支持ui=1；如果两者最佳路径的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（按极化码解码顺序）：

1. 计算比特LLR：对于当前每条存活路径，根据接收到的信道LLR和之前比特的部分和，计算当前比特ui的LLR值。这里使用的是标准的SC解码核（如f/g函数）。
2. 路径分裂：每条存活路径根据当前比特ui的LLR，分裂成两条候选子路径：一条假设ui=0，另一条假设ui=1。每条子路径更新其PM：
   • 如果判决（0或1）与LLR的符号一致，PM增加较小值log(1+exp(-|LLR|))，通常用查表或近似计算（如最小和近似）。
   • 如果不一致，PM增加|LLR|。
3. 路径排序与剪枝：此时有2L条候选路径。根据更新后的PM值对所有候选路径进行排序，保留PM最小的L条作为新的存活路径。
4. 关键记录：对于每一条新的存活路径，必须记录它对于当前比特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)的步骤如下：

1. 分离路径集合：对于比特i，遍历所有L条最终存活路径。根据路径的decision[i]值，将所有路径分为两个集合：
   • S0: 所有decision[i] = 0的路径。
   • S1: 所有decision[i] = 1的路径。
2. 查找最小PM：
   • 在集合S0中，找到路径度量最小的值，记为PM_min_0。如果S0为空（极端情况），则设置PM_min_0为一个很大的值（如+∞），或采用惩罚值。
   • 在集合S1中，找到路径度量最小的值，记为PM_min_1。同理处理空集情况。
3. 计算LLR：LLR(ui) = PM_min_1 - PM_min_0。

根据这个公式：

• 如果LLR(ui) > 0，则软判决倾向于ui=0（因为选0的最佳路径代价更小）。
• 如果LLR(ui) < 0，则软判决倾向于ui=1。
• |LLR(ui)|的大小反映了可靠性，绝对值越大越可靠。

复杂度分析： 后向计算需要对每个比特i遍历L条路径进行分类和找最小值，总计算复杂度为O(NL)。这与前向SCL解码的复杂度O(LNlogN)相比是较低的，尤其是当L不大时（通常L=8, 16, 32），这个开销是可接受的。存储开销主要是每条路径的N比特判决记录，总计O(LN)比特。

3.3 一个简化实例：L=4的情况

假设一个极短的码，解码后最终4条路径的PM和第三个比特的判决如下：

对于比特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，软输出倾向于u3=0，且具有一定的可靠性（因为0.9是一个中等正值）。如果PM_min_0和PM_min_1相差很大，比如5.0 vs 0.5，那么LLR=-4.5，会强烈倾向于u3=1。

4. 工程实现中的关键优化与踩坑点

将SO-FSCL从论文公式转化为实际可运行的代码或硬件设计，会遇到一系列教科书上不会提的问题。以下是我在多个项目中总结的关键点和踩过的坑。

4.1 路径度量PM的表示与计算

问题：PM在解码过程中不断累加，可能变得非常大。使用浮点数计算精度高但硬件不友好；使用定点数需要仔细设计字长和动态范围。

解决方案与经验：

• 定点数化：在硬件实现中，普遍采用定点数。需要分析LLR的动态范围以及路径度量的最大可能增长值。一个经验是，对于列表大小L=8或16，PM的整数部分预留8-10比特，小数部分预留4-6比特通常足够。必须进行充分的定点仿真，与浮点结果对比，确保性能损失在可接受范围内（通常<0.1dB）。
• PM归一化：这是SCL解码的常见技巧，在SO-FSCL中依然重要且影响软输出。每当我们对2L条候选路径进行排序后，可以对保留的L条存活路径的PM同时减去它们中的最小值。这样做不会改变路径间的相对顺序，但能防止PM溢出。关键点：这个减法操作必须在记录当前比特判决之后进行。因为后向LLR计算依赖的是路径间的绝对PM差值，如果提前做了归一化，这个差值的信息就丢失了。正确的顺序是：更新PM -> 记录判决 -> 排序剪枝 -> PM归一化。
• LLR近似计算：在路径分裂时更新PM需要计算log(1+exp(-|LLR|))。硬件中常用“最小和”或“偏移最小和”近似：max(0, α*(β - |LLR|))，通过选择参数α和β来逼近原函数。需要针对特定的信噪比范围优化这两个参数。

4.2 后向LLR计算的高效架构

问题：后向计算需要为N个比特，每个比特遍历L条路径，朴素实现复杂度为O(N*L)。在高速解码器中（如要求数Gbps吞吐量），这可能成为瓶颈。

优化方案：

1. 并行查找单元：对于每个比特i，我们可以设计一个专用的比较电路。由于L通常不大（≤32），可以并行比较所有路径的判决位和PM值。例如，用L个比较器同时判断路径判决是否为0，并用一个最小树（min-tree）结构在符合条件的PM中快速找到最小值。同样为判决为1的路径设计另一套最小树。这样，每个比特的LLR可以在几个时钟周期内算出。
2. 流水线处理：后向LLR计算可以与下一个码字的前向解码流水进行。当前码字进入后向计算阶段时，下一个码字可以开始前向解码，充分利用硬件资源。
3. 存储优化：每条路径的判决数组（N比特）是主要的存储开销。在硬件中，这通常用寄存器文件或SRAM实现。可以考虑压缩存储，例如，只存储与信息位或冻结位相关的判决，但这样会增加后向计算的寻址复杂度，需要权衡。

踩坑记录：在一个FPGA原型项目中，我们最初将每条路径的判决存在独立的Block RAM中。后向计算时需要同时读取L个RAM的同一地址（对应比特i），导致读写端口冲突和时序紧张。后来改为将L条路径的同一比特判决存储在同一块RAM的不同字中，一次读取就能获得所有路径在该比特的判决，极大地简化了后向计算逻辑并提高了频率。

4.3 列表大小L的选择与软输出质量权衡

问题：L越大，SCL解码性能越好，但计算和存储开销线性增长。SO-FSCL的软输出质量也强烈依赖于L。

经验之谈：

• 软输出质量的饱和：当L较小时（如L=4），最终列表中的路径多样性不足，可能导致对于某些比特，S0或S1集合为空。此时需要给空集赋予一个大的惩罚PM值，但这会引入偏差。随着L增大，软输出LLR的精度和可靠性显著提升。但通常L超过16或32后，性能提升变得非常缓慢。对于大多数应用，L=8或L=16是一个在性能和复杂度之间很好的折中点。
• 与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）曲线

我们可以通过仿真来对比：

1. 标准SCL（硬输出）：解码后直接输出硬判决比特。
2. SO-FSCL（软输出）：解码后输出LLR，再将LLR进行硬判决（符号函数）得到比特。
3. 理想软输出（如基于最大后验概率的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后，在目标BLER=1e-5处获得了约0.8dB的增益。这意味着在相同的发射功率下，通信距离可以更远，或者对于相同的距离，可以降低发射功率。

6. 总结与扩展思考

SO-FSCL技术完美地诠释了工程上的“优雅”：它没有推翻重来，而是在已被充分验证的SCL解码骨架上，通过巧妙的后期处理，挖掘出了额外的、极具价值的软信息。它使得极化码不仅能作为独立的“硬判决高手”，更能无缝融入现代通信系统中复杂的“软处理链条”。

在实际项目中应用SO-FSCL，我的体会是，前期充分的定点化和性能仿真至关重要。必须明确系统对软输出精度和动态范围的要求，据此确定PM和LLR的位宽、量化方案。后向计算的硬件架构需要精心设计，以平衡速度、面积和功耗。

此外，SO-FSCL的思想可以进一步扩展。例如，对于更长的码字，可以采用“分段”的SO-FSCL，将码字分成若干段，每段独立进行列表解码和软输出计算，以降低存储压力。也有研究探索在解码过程中动态地、选择性地为某些比特计算软输出，而不是全部N个比特，以进一步降低复杂度。

最后，不要忘记与CRC辅助解码的结合。在计算软输出时，优先考虑CRC校验通过的路径，甚至可以根据路径的PM值赋予不同的权重，而不是简单地取最小PM路径，这能在不增加列表大小L的情况下，进一步提升软输出的质量。这些细微的改进，往往就是在实际系统性能比拼中胜出的关键。