SC译码公式推导：f函数、g函数与递归结构

第 11 篇解释了 SC（successive cancellation，逐次消元译码）为什么按 i=0,1,\ldots,N-1 的顺序逐位判决：当前位的后验概率依赖已经得到的比特估计。本篇继续回答实现层面的关键问题：已知两个子信道的 LLR，上一级合成子信道的 LLR 到底怎样计算？

答案由两个递推函数组成：

• 减号子信道 W^- 使用 f，它把两个观测合成为“未知异或”的子信道；
• 加号子信道 W^+ 使用 g，它利用已经得到的前序部分和，把当前子信道变成带条件的观测。

本文仍采用 0-based 索引。码长为 N=2^n，信息长度为 K，码率为 R=K/N。信息位集合为 \mathcal{A}\subseteq[0,N-1]，冻结位集合为 \mathcal{A}^c=[0,N-1]\setminus\mathcal{A}。接收观测写作 \underline{y}，由信道观测得到的原始码字 LLR 写作 \underline{\lambda}=(\lambda_0,\ldots,\lambda_{N-1})；递推过程中产生的局部 LLR 则记为 \alpha、\beta 或 L_N^{(i)}。估计输入向量统一写作 \hat{\underline{u}}，编码后的码字比特是 c_i，BPSK 符号是 x_i=1-2c_i。

为什么 SC 的核心是递推

直接按照第 11 篇的子信道定义计算 L_N^{(i)}，需要对尚未判决的比特求和。若每一位都重新枚举后缀，复杂度会再次接近指数级。Polar 码的二阶核

F=\begin{bmatrix}1&0\\1&1\end{bmatrix}

把长度为 N 的变换拆成两个长度为 N/2 的合成子信道：减号子信道 W^- 和加号子信道 W^+。对应地，SC 先计算 W^- 的消息，得到前序判决及其部分和，再用这些部分和计算 W^+ 的条件消息。对得到的长度为 N/2 的输入继续按同样规则递推，直到输入长度降为 1；所有比特的判决顺序由这一递推过程确定。

递推的输入不是裸的接收观测，而是某一递推层收到的一组 LLR。设这一层的两个输入消息分别为 \alpha 和 \beta。减号、加号两个子信道需要的消息分别记作：

L^- = f(\alpha,\beta),\qquad L^+ = g(\alpha,\beta,\hat u)

这里 \hat u 是前序判决已经回传的局部部分和比特；在长度大于 2 的递推层中，它不是单个原始输入位，而是部分和向量中的一个分量。

从似然比统一定义两个输入

令二元输入信道的转移概率为 W(y\mid c)。对一对观测 (y_0,y_1)，定义两个底层 LLR：

\alpha=\ln\frac{W(y_0\mid0)}{W(y_0\mid1)},\qquad \beta=\ln\frac{W(y_1\mid0)}{W(y_1\mid1)}

再记对应的似然比为 A=e^\alpha、B=e^\beta。由于 SC 只需要比较两个假设的概率，所有与两个假设都相同的归一化因子都会在比值中消失。这也是递推公式可以只用 LLR 表示的原因。

f函数：未知异或的合并

先写出似然比

二阶核中，减号子信道对应输入比特 u_0，码字中的两个比特为 c_0=u_0\oplus u_1 和 c_1=u_1。当 u_0 固定时，u_1 仍未知，因此减号子信道要把两种 u_1 情况边缘化：

W^-(y_0,y_1\mid u_0)=\frac{1}{2}\sum_{u_1\in\{0,1\}}W(y_0\mid u_0\oplus u_1)W(y_1\mid u_1)

对 u_0=0 和 u_0=1 分别展开，公共的 1/2 因子相消。令 W_{00}=W(y_0\mid0)、W_{01}=W(y_0\mid1)、W_{10}=W(y_1\mid0)、W_{11}=W(y_1\mid1)，则

\frac{W^-(y_0,y_1\mid0)}{W^-(y_0,y_1\mid1)} =\frac{W_{00}W_{10}+W_{01}W_{11}}{W_{01}W_{10}+W_{00}W_{11}} =\frac{AB+1}{A+B}

因此减号子信道的 LLR 为

L^-=\ln\frac{AB+1}{A+B}

化成双曲正切形式

利用恒等式

\tanh\left(\frac{\alpha}{2}\right)=\frac{A-1}{A+1},\qquad \tanh\left(\frac{\beta}{2}\right)=\frac{B-1}{B+1}

可以验证

\exp(L^-)=\frac{1+\tanh(\alpha/2)\tanh(\beta/2)} {1-\tanh(\alpha/2)\tanh(\beta/2)}

而 \ln((1+t)/(1-t))=2\operatorname{atanh}(t)，所以得到 SC 中最常用的 f 函数：

\boxed{f(\alpha,\beta)=2\operatorname{atanh}\left(\tanh\frac{\alpha}{2}\tanh\frac{\beta}{2}\right)}

这个公式还保留了三个直观性质：

1. 当 \alpha 或 \beta 等于 0 时，f=0，因为其中一路没有方向信息。
2. f 的符号是 \operatorname{sign}(\alpha)\operatorname{sign}(\beta)，也就是两条输入 LLR 的符号相乘。
3. 当两路都很可靠时，输出的绝对值仍通常小于较弱一路，符合“未知异或会损失可靠性”的直觉。

g函数：已知前序部分和后的条件合并

把前序判决作为条件

加号子信道对应输入比特 u_1，并且已经知道 u_0 的估计值。固定 \hat u_0 后，不再对 u_0 求和：

W^+(y_0,y_1,\hat u_0\mid u_1) =\frac{1}{2}W(y_0\mid\hat u_0\oplus u_1)W(y_1\mid u_1)

计算 u_1=0 与 u_1=1 的似然比：

\frac{W^+(y_0,y_1,\hat u_0\mid0)} {W^+(y_0,y_1,\hat u_0\mid1)} = \begin{cases} e^{\alpha+\beta},&\hat u_0=0,\\ e^{-\alpha+\beta},&\hat u_0=1. \end{cases}

两种情况可合并成

\boxed{g(\alpha,\beta,\hat u_0)=\beta+(1-2\hat u_0)\alpha}

因此，前序条件位为 0 时，\alpha 与 \beta 相加；前序条件位为 1 时，\alpha 的符号翻转后再与 \beta 相加。这里的“翻转”不是修改接收观测，而是二元异或关系在 LLR 域中的等价表示。

一个数值例子

为了说明 \alpha、\beta 的来源，先由接收信号计算进入 SC 递归的 LLR。设 BPSK 映射为 x=1-2c（c=0 映射为 +1，c=1 映射为 -1），信道为方差 \sigma^2=1 的 AWGN：

W(y\mid c)=\frac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{(y-(1-2c))^2}{2\sigma^2}\right)

对于接收观测向量 \underline{y}=(y_0,y_1)=(1,0.5)，每个码字位置的似然比为

\lambda_j=\ln\frac{W(y_j\mid0)}{W(y_j\mid1)}=\frac{2y_j}{\sigma^2}

因此两条输入 LLR 分别为

\alpha=\lambda_0=\frac{2\times1}{1}=2,\qquad \beta=\lambda_1=\frac{2\times0.5}{1}=1

这就得到下面递推式的输入 \alpha=2、\beta=1：

f(2,1)=2\operatorname{atanh}\left(\tanh(1)\tanh(0.5)\right)\approx0.735

而

g(2,1,0)=3,\qquad g(2,1,1)=-1

减号子信道只得到约 0.735 的可靠性；加号子信道在已知前序条件位后，将两条输入 LLR 按条件符号相加。当条件位为 1 时，第一条输入 LLR 先取反，再与第二条输入 LLR 相加。

N=4 完整手推：从接收信号 LLR 到四个判决

本节完全按照步骤图的符号逐步计算。为便于和图逐项对照，本节临时采用 1-based 索引：第一层输入写作 L_1^{(1)}(y_1),\ldots,L_1^{(4)}(y_4)，第二层写作 L_2^{(1)}、L_2^{(2)}，最终条件 LLR 写作 L_4^{(1)},\ldots,L_4^{(4)}。全文其他章节、代码和集合仍采用 0-based，映射为图中 i 对应正文 i-1。这也是本节唯一使用 1-based 的原因。

取冻结位 u_1=0，信息位为 u_2,u_3,u_4。接收端根据四个观测得到第一层接收信号 LLR：

L_1^{(1)}(y_1)=1.5,\quad L_1^{(2)}(y_2)=2.0,\quad L_1^{(3)}(y_3)=-1.0,\quad L_1^{(4)}(y_4)=0.5

这里的四个输入按图片中的相邻位置配对：(y_1,y_2) 和 (y_3,y_4)。记 f、g 分别为前文定义的未知异或合并和已知前序条件合并。

第一步：由第一层输入计算 L_2^{(1)}

对两组相邻输入分别使用 f：

L_2^{(1)}(y_1^2)=f\left(L_1^{(1)}(y_1),L_1^{(2)}(y_2)\right)=f(1.5,2.0)\approx1.0557\approx1.06 L_2^{(1)}(y_3^4)=f\left(L_1^{(3)}(y_3),L_1^{(4)}(y_4)\right)=f(-1.0,0.5)\approx-0.2273\approx-0.23

这两个数值就是下一层计算 u_1、u_2 时使用的两路输入。

第二步：计算冻结位 u_1

把两路 L_2^{(1)} 再次送入 f，得到第一个条件 LLR：

L_4^{(1)}=f\left(L_2^{(1)}(y_1^2),L_2^{(1)}(y_3^4)\right)=f(1.0557,-0.2273)\approx-0.1096\approx-0.11

u_1 属于冻结位集合，因此不读取 LLR 符号，直接按约定判决 \hat u_1=0。

第三步：计算信息位 u_2

已知前一个判决 \hat u_1=0 后，用 g 计算第二个条件 LLR：

L_4^{(2)}=g\left(L_2^{(1)}(y_1^2),L_2^{(1)}(y_3^4),\hat u_1\right)=g(1.0557,-0.2273,0)\approx0.8284\approx0.83

u_2 是信息位，且 L_4^{(2)}>0，所以判决为 \hat u_2=0。

第四步：根据已判决比特计算 L_2^{(2)}

在计算后两个比特前，先将已得到的比特对应的部分和带回第一层。第一路的条件是 \hat v_1 = \hat u_1\oplus\hat u_2=0，第二路的条件是 \hat v_2 = \hat u_2=0：

L_2^{(2)}(y_1^2,\hat v_1) = L_2^{(2)}(y_1^2,\hat u_1\oplus\hat u_2)=g\left(L_1^{(1)}(y_1),L_1^{(2)}(y_2),\hat u_1\oplus\hat u_2\right)=g(1.5,2.0,0)=3.5 L_2^{(2)}(y_3^4,\hat v_2) = L_2^{(2)}(y_3^4,\hat u_2)=g\left(L_1^{(3)}(y_3),L_1^{(4)}(y_4),\hat u_2\right)=g(-1.0,0.5,0)=-0.5

两个 g 的条件不同，不能把同一个判决比特重复传给两路。

第五步：计算信息位 u_3

使用刚刚得到的两路 L_2^{(2)}，再次使用 f：

L_4^{(3)}=f\left(L_2^{(2)}(y_1^2,\hat v_1),L_2^{(2)}(y_3^4,\hat v_2)\right)=f(3.5,-0.5)\approx-0.4696\approx-0.47

这是信息位，LLR 为负，因此判决为 \hat u_3=1。

第六步：计算信息位 u_4

最后一个比特使用已经得到的 \hat u_3=1 进入 g：

L_4^{(4)}=g\left(L_2^{(2)}(y_1^2,\hat v_1),L_2^{(2)}(y_3^4,\hat v_2),\hat u_3\right)=g\left(L_2^{(2)}(y_1^2,\hat u_1 \oplus \hat u_2),L_2^{(2)}(y_3^4,\hat u_2),\hat u_3\right)=g(3.5,-0.5,1)=-4.0

因此 L_4^{(4)}<0，判决为 \hat u_4=1。

四个判决按图片中的 1-based 记号汇总为

\left(\hat u_1,\hat u_2,\hat u_3,\hat u_4\right)=(0,0,1,1)

本节的计算链是：L_1 接收信号 LLR → 第一层 f 得到 L_2^{(1)} → 判决 u_1,u_2 → 第一层 g 得到 L_2^{(2)} → 再由 f/g 得到 L_4^{(3)},L_4^{(4)}。

N=4译码树：判决顺序与路径展开

下面这张图展示的是 N=4 时四个待判决比特形成的二叉候选路径树。它和前文的蝶形图作用不同：这里每向下走一层，就为下一个比特追加一次候选判决；图中的数值是路径度量示意，不是某个叶节点的原始 LLR。

图顶部的“译码节点 -1”是尚未判决任何比特的根，初始路径度量标为 1.00。节点 0,1,2,3 分别对应依次判决 \hat u_0,\hat u_1,\hat u_2,\hat u_3 后的四层。每个父节点向下分出两条候选边：

• 虚线边表示候选比特 0；
• 实线边表示候选比特 1；

同一父节点下的两个子节点度量相加等于父节点度量，例如

0.60+0.20=0.80,\qquad 0.15+0.05=0.20

这说明图中的数字表示“到达该节点状态的累计权重”，用于帮助读者观察树的展开关系；实际 SC 实现通常直接比较两个候选的条件 LLR 符号，并不需要显式保存这 16 个叶端权重。沿着图中黑色节点读取分支标签，可以得到一条示意路径

\hat{\underline{u}}_{\mathrm{path}}=(0,0,1,0)

它经过的度量依次为 1.00\rightarrow0.80\rightarrow0.60\rightarrow0.35\rightarrow0.30，其中框出的 0.30 只是该示意路径的叶端度量。这个示意路径不等于上一节给定原始 LLR (1.5,2.0,-1.0,0.5) 时算出的 \hat{\underline{u}}=(0,0,1,1)；两者使用的是不同的演示数据。

把一个递归层单独抽出来，才得到真正执行 LLR 更新的计算单元。它与代码中的一次循环对应：两路输入同时参与 f 和 g 更新，但 g 必须等待减号子信道节点已经得到的部分和。

因此，译码树回答“先判决哪个比特、候选路径怎样展开”，而蝶形单元回答“每次判决所需的 LLR 如何计算”。在 SC 中，冻结位只保留编码约定允许的分支；信息位根据当前条件 LLR 选择一个分支，选定后继续向下一层递归。

对一个长度为 4 的局部节点，可以把传播过程写成下面四步：

1. 根节点把两组长度为 2 的消息按位置配对，计算减号子信道的 f 消息。
2. 减号子信道节点继续递归，直到长度为 1 的叶节点 L_1^{(0)}、L_1^{(1)}，得到 \hat u_0、\hat u_1。
3. 减号子信道节点根据局部 Polar 变换形成部分和 \hat{x}_{-}，再把它逐项带入加号子信道的 g 计算。
4. 加号子信道节点得到 \hat u_2、\hat u_3 后，父节点按二元域异或合成更高层部分和。

以 F 为局部变换时，长度为 2 的部分和是

\hat{x}_{-}[0]=\hat u_0\oplus\hat u_1,\qquad \hat{x}_{-}[1]=\hat u_1

因此，根节点加号子信道的两次 g 更新分别使用 \hat{x}_{-}[0] 和 \hat{x}_{-}[1]。这也是实现中不能把两次 g 调用都写成同一个 \hat u_0 的原因：节点长度增大后，条件信息已经变成减号子信道部分和向量。

父节点收到减号和加号两个子信道节点的部分和后，按

\hat{x}[j]=\hat{x}_{-}[j]\oplus\hat{x}_{+}[j],\qquad \hat{x}[j+N/2]=\hat{x}_{+}[j]

回传给更高层。这个回传规则与编码蝶形图的二元加法完全对应，只是译码时部分和从叶节点向根节点逐层汇合。

译码树和蝶形图中的递归

译码树适合说明“先处理减号子信道、再处理加号子信道”的控制流，蝶形图适合说明“消息在每一层如何流动”。对长度为 N 的节点，设输入 LLR 向量为 \boldsymbol{\ell}，半长为 M=N/2：

\ell^-_j=f(\ell_{2j},\ell_{2j+1}),\qquad \ell^+_j=g(\ell_{2j},\ell_{2j+1},\hat{x}_{-,j}),\quad 0\le j<M

这里的配对写法与本节步骤图采用的连续位置分组一致；若外部编码器使用自然顺序 F^{\otimes n} 或额外 bit-reversal，应在模块接口处先完成索引映射，再把映射后的 LLR 送入本递归。加号子信道的 \hat{x}_{-,j} 必须等减号子信道节点完成后才可用，所以 SC 的遍历顺序是深度优先的：

\text{decode}(W^-)\;\longrightarrow\; \text{compute }g\;\longrightarrow\; \text{decode}(W^+)\;\longrightarrow\; \text{combine partial sums}

这和 BP（置信传播）那种同时迭代两个方向的调度不同。SC 每个叶节点只访问一次，已经判决的比特立即成为后续条件；因此它具有确定的串行顺序，也产生了错误传播。

C++17：可运行的SC递归实现

下面的程序实现一个最小但完整的 SC 译码核心。输入的 llr[j] 是与码字比特 c_j 对齐的原始 LLR，约定

\lambda_j=\ln\frac{W(y_j\mid c_j=0)}{W(y_j\mid c_j=1)}

代码采用与步骤图一致的连续位置蝶形顺序，不负责生成 AWGN 噪声、BPSK 符号或构造 \mathcal{A}；若外部编码器使用自然顺序 F^{\otimes n} 或 bit-reversal，应在接口处先完成索引映射。仿真器只需把 \rho_{\mathrm{sim}} 生成的观测转换成 llr，再把构造阶段由 \rho_{\mathrm{des}} 得到的信息位索引传入 decode。返回值是长度为 N 的 \hat{\underline{u}}，其中冻结位已经固定为 0。

代码中的 leftLlr、rightLlr、left、right 只是递归数组和返回值的存储名称；在数学上它们分别对应减号子信道 W^- 和加号子信道 W^+，不改变 f/g 的定义。

由于递归函数需要把“输入位估计”和“局部码字部分和”同时返回，定义 ScResult。对长度为 1 的节点，部分和就是该节点的估计位；对更高层，部分和按蝶形异或规则合成。代码中的每个索引均为 0-based。

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <vector>

namespace polar_sc {

// 一个递归节点返回两类结果：
// u      : 当前节点范围内的输入位估计，顺序与该节点的局部索引一致。
// partial: 当前节点经过 F^(log2(length)) 变换后的部分和，
//          父节点的加号子信道必须使用它，而不能只使用减号节点的第一个 u。
struct ScResult {
    std::vector<int> u;
    std::vector<int> partial;
};

// f 是未知异或对应的 box-plus LLR。
// alpha、beta 是同一递归节点中两路独立观测的 LLR，输入输出均使用自然对数。
// tanh/atanh 形式避免显式计算 exp(alpha)、exp(beta)，对中等和大 LLR 更稳定。
double f(double alpha, double beta) {
    const double product = std::tanh(alpha / 2.0)
                         * std::tanh(beta / 2.0);

    // 浮点舍入可能让 product 略微达到 +/-1，而 atanh(+-1) 会得到无穷大。
    // 这里保留一个极小安全裕量；它只处理数值边界，不改变理论递推。
    constexpr double epsilon = 1.0e-15;
    const double clipped = std::clamp(
        product, -1.0 + epsilon, 1.0 - epsilon);
    return 2.0 * std::atanh(clipped);
}

// g 是已知减号子信道部分和后的条件 LLR：
// g(alpha, beta, 0) = beta + alpha，g(alpha, beta, 1) = beta - alpha。
// leftPartial 必须是 0/1；调用者应传入减号节点的 partial[j]。
double g(double alpha, double beta, int leftPartial) {
    if (leftPartial != 0 && leftPartial != 1) {
        throw std::invalid_argument("partial sum must be a binary value");
    }
    return beta + (leftPartial == 0 ? alpha : -alpha);
}

// 递归译码一个局部节点。
// llr 的长度必须是 2 的幂，offset 是该节点在全局 u 向量中的起始索引。
// frozen[i] 为 true 表示 u_i 属于 A^c，必须无条件判为 0；
// frozen[i] 为 false 表示 u_i 属于 A，按叶节点 LLR 符号做 MAP 硬判决。
ScResult decodeNode(const std::vector<double>& llr,
                    std::size_t offset,
                    const std::vector<bool>& frozen) {
    const std::size_t length = llr.size();
    if (length == 0 || (length & (length - 1)) != 0) {
        throw std::invalid_argument("node length must be a positive power of two");
    }
    if (offset + length > frozen.size()) {
        throw std::invalid_argument("frozen mask is shorter than the node");
    }

    // 叶节点没有更小的子问题：冻结位固定为 0，信息位由 LLR 符号决定。
    // LLR >= 0 时 0 假设的后验不小于 1 假设；等号约定选择 0。
    if (length == 1) {
        const int bit = frozen[offset] ? 0 : (llr[0] >= 0.0 ? 0 : 1);
        return ScResult{{bit}, {bit}};
    }

    const std::size_t half = length / 2;
    std::vector<double> leftLlr(half);

    // 递归不变量：leftLlr[j] 是减号子节点第 j 个局部子信道的 LLR。
    // 当前递归把相邻输入 [2*j, 2*j+1] 作为一组，
    // 这与步骤图的连续位置分组一致；递归后 leftLlr 长度减半。
    for (std::size_t j = 0; j < half; ++j) {
        leftLlr[j] = f(llr[2 * j], llr[2 * j + 1]);
    }

    // SC 必须先完成减号子信道节点，才能取得加号子信道 g 所需的部分和。
    ScResult left = decodeNode(leftLlr, offset, frozen);
    std::vector<double> rightLlr(half);
    for (std::size_t j = 0; j < half; ++j) {
        // 关键边界：这里使用减号节点的 partial[j]，而不是 left.u[0]。
        // 对 length > 2 的节点，partial 已经包含减号节点内部的异或结果。
        rightLlr[j] = g(llr[2 * j], llr[2 * j + 1], left.partial[j]);
    }

    ScResult right = decodeNode(rightLlr, offset + half, frozen);
    ScResult result;
    result.u.reserve(length);
    result.partial.resize(length);

    // u 向量按全局索引区间 [offset, offset+length) 拼接，
    // 但 partial 必须按照父节点蝶形的局部码字顺序合并。
    result.u.insert(result.u.end(), left.u.begin(), left.u.end());
    result.u.insert(result.u.end(), right.u.begin(), right.u.end());
    for (std::size_t j = 0; j < half; ++j) {
        result.partial[j] = left.partial[j] ^ right.partial[j];
        result.partial[j + half] = right.partial[j];
    }
    return result;
}

// 对外的译码入口。
// llr[j] 与码字位置 c_j 对齐；informationIndices 是 A 中的全局 0-based 索引。
// 函数先构造冻结掩码，再从根节点递归到叶节点，返回完整的 u_hat。
std::vector<int> decode(
    const std::vector<double>& llr,
    const std::vector<std::size_t>& informationIndices) {
    const std::size_t N = llr.size();
    if (N == 0 || (N & (N - 1)) != 0) {
        throw std::invalid_argument("N must be a positive power of two");
    }

    std::vector<bool> frozen(N, true);
    for (const std::size_t index : informationIndices) {
        if (index >= N) {
            throw std::invalid_argument("information index is out of range");
        }
        if (!frozen[index]) {
            throw std::invalid_argument("information indices must be unique");
        }
        frozen[index] = false;
    }

    return decodeNode(llr, 0, frozen).u;
}

}  // namespace polar_sc

int main() {
    // 这是一个可直接编译的最小调用示例。
    // 真实仿真中，llr 应由 AWGN 观测和 rho_sim 换算得到；
    // informationIndices 则来自构造阶段的 rho_des 排序结果。
    // 这里沿用上面的 N=4 手推输入：冻结位为 0，信息位为 1、2、3。
    const std::vector<double> llr{1.5, 2.0, -1.0, 0.5};
    const std::vector<std::size_t> informationIndices{1, 2, 3};
    const std::vector<int> estimate =
        polar_sc::decode(llr, informationIndices);

    std::cout << "u_hat:";
    for (const int bit : estimate) {
        std::cout << ' ' << bit;
    }
    std::cout << '\n';
    return 0;
}

这段程序的模块边界是明确的：decode 只负责 SC 递归和冻结位约束，f、g 只负责 LLR 消息更新，信道仿真、构造和性能统计由外部模块完成。这样可以把第 10 篇的 GA 构造器、第 12 篇的 SC 译码器和后续 AWGN 仿真连接起来，而不会把 \rho_{\mathrm{des}} 与 \rho_{\mathrm{sim}} 混在同一个函数里。

用一个小树检查实现是否正确

调试时可以对 N=4 的递归节点逐层打印三个量：

层级	应观察的量	正确性检查
根节点	leftLlr[j]	每个位置都应为 f(\lambda_{2j},\lambda_{2j+1})
减号节点返回后	left.partial[j]	它应是减号节点局部编码后的部分和
加号节点输入	rightLlr[j]	每个位置都应使用对应的 left.partial[j]
叶节点	冻结掩码与 LLR 符号	冻结位恒为 0，信息位才读取符号

如果加号子信道的 LLR 与手算不符，优先检查两件事：第一，接收信号计算的 LLR 是否仍按码字位置 c_j 排列；第二，是否错误地把减号节点的输入位估计 \hat u_j 当成了父节点需要的部分和。

复杂度和数值实现边界

每一层的所有节点总共处理 N 个 LLR，递归深度为 \log_2N，因此 f/g 运算总量为

O(N\log N)

示例代码为了让返回值和部分和关系清楚，递归中会创建多个临时向量，空间开销高于工程里的原地实现。实际译码器通常把 LLR 阵列和部分和阵列预先分层分配，在不改变递推公式的前提下把额外空间压到 O(N) 量级。

当 LLR 绝对值很大时，直接用 e^\alpha 计算似然比容易上溢；代码使用 tanh/atanh 形式并在 \pm1 边界处截断。若目标平台更关注速度，也可以使用 min-sum 近似

f(\alpha,\beta)\approx \operatorname{sign}(\alpha)\operatorname{sign}(\beta) \min\{|\alpha|,|\beta|\}

但这会牺牲一部分精度，不能再把近似结果称作精确的 f。

常见误区

第一，把 f 写成普通加法。加法属于已知前序条件后的 g 分支；未知异或必须使用 box-plus 关系。

第二，加号分支始终传入同一个前序比特。只有长度为 2 的局部节点可以把它看成单个位；一般节点必须使用减号节点部分和的对应分量。

第三，把冻结位也交给 LLR 符号判决。冻结位由 \mathcal{A}^c 预先规定，观测再强烈也不能改变这个约束。

第四，混淆 \lambda_j 和 L_N^{(i)}。前者是码字观测的原始 LLR，后者是递归过程中针对第 i 个合成子信道的条件 LLR。

第五，忽略索引和生成矩阵约定。代码、蝶形图和公式必须使用同一套 0-based 顺序；若外部编码器采用了额外 bit-reversal，就应在模块边界显式完成映射，不能默默交换数组。

小结

SC 的两个核心递推来自二阶核的两个子信道：

f(\alpha,\beta)= 2\operatorname{atanh}\left( \tanh\frac{\alpha}{2}\tanh\frac{\beta}{2} \right) g(\alpha,\beta,\hat u)= \beta+(1-2\hat u)\alpha

f 对未知异或进行边缘化，g 则把减号子信道节点已经得到的部分和作为条件。递归实现必须先完成减号子信道节点，再计算加号子信道的 g 消息，最后按二元域异或合并部分和。这样，似然比推导、译码树、蝶形网络和 C++ 函数就对应到了同一个计算过程。

下一篇将从这棵树的遍历顺序、消息存储和错误传播继续展开，说明 SC 的时间复杂度、空间组织以及为什么一次错误判决会影响后续路径。

参考

• E. Arıkan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051–3073, Jul. 2009, doi: 10.1109/TIT.2021379.
• I. Tal and A. Vardy, “List decoding of polar codes,” IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2213–2226, May 2015, doi: 10.1109/TIT.2015.2410251.
• R. Mori and T. Tanaka, “Performance and construction of polar codes on symmetric binary-input memoryless channels,” IEEE Transactions on Information Theory, vol. 59, no. 5, pp. 2883–2901, May 2013, doi: 10.1109/TIT.2013.2248212.
• Marshall, “Polar Code（6）SC译码算法,” 13 Mar. 2017, https://marshallcomm.cn/2017/03/13/polar-code-6-sc-decoder/ （逐步译码图来源，访问日期：2026-08-28）。