SC译码的复杂度与错误传播

第 12 篇已经从似然比推导了 f 和 g 递推。本篇不重复公式，而是回答两个实现问题：递归到底访问了多少节点，以及为什么一次错误的逐位判决会改变后续 LLR。本文把沿蝶形边传递的量称为“LLR 更新量”，把由已判决比特合成的二元量称为“部分和”；两者分别属于实数域和二元域，作用不同，不能混用。符号定义：码长 N=2^n，信息集合为 \mathcal{A}，冻结集合为 \mathcal{A}^c=[0,N-1]\setminus\mathcal{A}，接收观测为 \underline{y}，原始码字 LLR 为 \underline{\lambda}，估计向量为 \hat{\underline{u}}_0^{N-1}。

用码树理解 SC 的递归遍历

长度为 1 的叶节点对应一个 u_i。长度为 2^s 的内部节点先把输入分成两路：左子节点使用 f，右子节点使用 g。SC 的深度优先顺序固定为

\text{左子树（减号）}\;\longrightarrow\;\text{右子树（加号）}\;\longrightarrow\;\text{部分和回传}

以 N=8 为例，根节点范围是 [0,7]，两个长度为 4 的子节点范围为 [0,3] 和 [4,7]。左节点继续访问 [0,1]、[2,3]，右节点继续访问 [4,5]、[6,7]。因此叶节点顺序仍是 u_0,u_1,\ldots,u_7，但每个叶节点得到的 LLR 是沿树上多次 f/g 组合后的 L_8^{(i)}。

每次左子树返回后，局部部分和必须按二元域规则合并。若左、右子树的局部部分和分别为 \underline{s}^{-} 和 \underline{s}^{+}，父节点回传的顺序是

\underline{s}=(\underline{s}^{-}\oplus\underline{s}^{+},\;\underline{s}^{+})

右子树的 g 输入需要的是左子树的部分和，而不是左子树的某一个 \hat{u}_i。

一次完整的 N=8 访问顺序

把节点写成“区间、进入顺序、离开时回传的部分和”，可以得到如下深度优先序列。区间端点均为包含关系：

步骤	节点区间	动作
1	[0,7]	根节点先计算 4 个 f 型 LLR 更新量
2	[0,3]	左子树再计算 2 个 f 型 LLR 更新量
3	[0,1]	计算 f，判决 u_0，计算 g，判决 u_1
4	[2,3]	用左半部分和计算 f/g，判决 u_2,u_3
5	[0,3]	将 [0,1]、[2,3] 的部分和合并并回传
6	[4,7]	使用根节点的 g 和左侧部分和
7	[4,5]	判决 u_4,u_5
8	[6,7]	判决 u_6,u_7
9	[4,7]	合并右子树部分和并回传根节点

这个表说明“访问叶节点 8 次”并不意味着只做 8 次 LLR 更新：同一条路径在进入每个内部节点时都要完成一组向量化的 f 或 g 运算。实现中的 offset、节点长度和父子索引必须同时保存，否则很容易把 [2,3] 的部分和误当成根节点的左半部分和。

对于区间 [a,a+2^s-1]，左子树回传的向量记为 \underline{s}^{-}_{a,s}，右子树回传的向量记为 \underline{s}^{+}_{a,s}。父节点回传时第 j 个分量满足

s_{a,s}[j]=s^{-}_{a,s}[j]\oplus s^{+}_{a,s}[j],\quad s_{a,s}[2^s+j]=s^{+}_{a,s}[j],\quad 0\le j<2^s

显式写出下标有助于检查“局部索引”和“全局索引”的区别：j 在节点内部从 0 开始，真正对应的码树叶节点位置还要加上区间起点 a。

用蝶形网络理解LLR传递

把每一层长度相同的节点横向排列，就得到蝶形网络。第 s 层的蝶形跨度为 2^s，每个蝶形包含 2^{s-1} 次 f 和 2^{s-1} 次 g 的位置更新。全网共有 n=\log_2N 层，因此每一层恰好处理 N 个 LLR 位置。

对 N=8 而言，三层更新量如下：

层级	节点长度	蝶形数量	f 次数	g 次数
0	2	4	4	4
1	4	2	4	4
2	8	1	4	4
合计			12	12

按一对 f/g 计作一次蝶形更新时，共有 N\log_2N/2=12 个蝶形、N\log_2N=24 个标量 LLR 更新。

这个计数可以推广到任意 N=2^n。固定第 s 层（节点长度为 2^{s+1}，其中 s=0,1,\ldots,n-1），该层有 N/2^{s+1} 个节点。每个节点需要 2^s 次 f 和 2^s 次 g，所以这一层分别有

\frac{N}{2^{s+1}}\,2^s=\frac{N}{2}

次 f 与 g。每一层的计数与层号无关，叠加 n 层便得到

N_f= N_g=\frac{N}{2}\log_2N,\qquad N_{\mathrm{LLR}}=N_f+N_g=N\log_2N.

叶节点的 N 次判决不包含在 N_{\mathrm{LLR}} 中。若实现还统计冻结位检查、部分和异或和饱和裁剪，这些操作应单独列为不同计数项，不能把它们悄悄并入 f/g 次数。

以 N=8 展开一次就能看到层间关系：长度为 2 的四个节点各自贡献 1 次 f、1 次 g；长度为 4 的两个节点各自贡献 2 次 f、2 次 g；长度为 8 的根节点贡献 4 次 f、4 次 g。三层相加正好得到表中的 12 次 f 和 12 次 g。

下面的交互动画把这三层 LLR 更新调度按步骤展开。动画中的 Col 4 是接收信号的 LLR，两条红色连线连接到下一个节点表示左枝的 f 更新，两条蓝色连线连接到下一个节点表示使用部分和的右枝 g 更新。点击“下一步”可以沿着 SC 的访问顺序观察节点如何变为已知，点击“上一步”或“重置”可以回到前面的状态。

这段动画只展示 N=8 各层的 LLR 存储和访问调度。把动画停在任意一步时，可以回看当前已点亮的节点数量，再与上面的分层计数对应：四个长度为 2 的局部蝶形、两个长度为 4 的蝶形和一个长度为 8 的根蝶形共同构成完整的 24 次标量 LLR 更新。

SC 译码的时间复杂度和空间复杂度

每个叶节点判决一次，共 N 次。LLR 更新在 \log_2N 层上进行，每层有 N 个标量位置，所以

T(N)=\Theta(N\log_2N)

也可以从递归式直接看到这一点。长度为 N 的节点先花 N/2 次 f 和 N/2 次 g，再访问两个长度为 N/2 的子节点，因此

T(N)=2T(N/2)+\Theta(N),\qquad T(1)=\Theta(1)

展开到第 n=\log_2N 层后，每层的线性项总和都是 \Theta(N)，共有 n 层，得到同一个结论。

递归程序若为每个节点复制 vector，会产生临时对象；工程实现通常预分配分层 LLR 数组与部分和数组并复用槽位，空间复杂度为

S(N)=\Theta(N)

递归栈深度虽然是 \log_2N，但不能据此把总存储写成对数级；沿当前路径保留的 LLR 更新量和部分和仍占线性空间。

一种常见的内存布局是用分层数组保存不同深度的 LLR，部分和数组另占一块长度为 N 的二元存储。兄弟节点访问结束后，已经不再需要的槽位可以复用；因此“每层有 N 个位置”并不自动意味着总空间是 N\log N。单路径 SC 的峰值存储为 O(N)，而 SCL 需要为最多 L_{\max} 条路径保存相应状态，才会扩大到 O(L_{\max}N)。

还要区分缓存递归和朴素递归。若每次叶节点判决前都从根节点重新计算整棵树，相同的 f/g LLR 更新量会被重复求出，实际时间可能接近 O(N^2)。只有在节点访问过程中缓存并复用已经计算的 LLR，或者采用等价的迭代蝶形调度，才能得到前面递推式对应的 O(N\log N) 复杂度。

C++ 仿真时的复杂度统计

下面的统计器只计算 f、g 的标量调用次数，信道生成和真正的 LLR 数值计算由外部模块负责。offset 是当前节点在全局估计向量中的起点，所有索引均为 0-based。

#include <cstddef>
#include <iostream>
#include <vector>

struct ScCounters {
    std::size_t f_calls = 0;
    std::size_t g_calls = 0;
    std::size_t leaf_decisions = 0;
};

// 这里用占位 f 只演示调度和计数，不产生可用译码结果。
double f_counted(double alpha, double beta, ScCounters& counter) {
    ++counter.f_calls;                 // 统计一次减号分支的标量 LLR 更新
    return alpha + beta;
}

double g_counted(double alpha, double beta, int partial,
                 ScCounters& counter) {
    ++counter.g_calls;                 // 统计一次加号分支的标量 LLR 更新
    return beta + (partial == 0 ? alpha : -alpha);
}

void visit(const std::vector<double>& llr, std::size_t offset,
           ScCounters& counter) {
    const std::size_t length = llr.size();
    if (length == 1) {
        ++counter.leaf_decisions;      // 冻结位和信息位都只访问一次
        return;
    }
    const std::size_t half = length / 2;
    std::vector<double> left(half), right(half);
    for (std::size_t j = 0; j < half; ++j) {
        left[j] = f_counted(llr[2 * j], llr[2 * j + 1], counter);
    }
    visit(left, offset, counter);      // 先取得左侧部分和
    for (std::size_t j = 0; j < half; ++j) {
        right[j] = g_counted(llr[2 * j], llr[2 * j + 1], 0, counter);
    }
    visit(right, offset + half, counter);
}

int main() {
    const std::vector<double> lambda{1, 1, 1, 1, 1, 1, 1, 1};
    ScCounters counter;
    visit(lambda, 0, counter);
    std::cout << "f=" << counter.f_calls
              << " g=" << counter.g_calls
              << " leaves=" << counter.leaf_decisions << '\n';
}

对于 N=8，输出应为 f=12 g=12 leaves=8。其中 partial=0 只是计数示意，真实实现必须把左节点返回的部分和传入 g；统计器用于验证调度次数，不替代译码器。

为什么 SC 会出现错误传播

第 i 位的判决会参与后续合成信道的条件概率。当信息位 u_i 被错判为 \hat{u}_i=1-u_i 时，后续 L_N^{(j)}（j>i）使用了错误的已判决比特。错误通过局部部分和进入若干次 g 更新，可能改变后续 LLR 的符号或幅度。

对长度为 2 的节点，

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

真实前序比特为 0 而译码器给出 1 时，两种 g 型 LLR 更新量之差为

g(\alpha,\beta,1)-g(\alpha,\beta,0)=-2\alpha

因此 |\alpha| 较大时，错误的已判决比特对后续计算的影响也较大。

错误传播并不是“每一个后继位必然判错”。若 |\beta| 远大于 |\alpha|，即使已判决比特从 0 改成 1，g 的符号仍可能保持不变；此时后继位暂时不会翻转。但它的后验概率已经改变，后续多级 f/g 组合仍可能在别的位置触发符号翻转。因此这里的“传播”首先指条件 LLR 发生改变，是否最终形成比特错误取决于后继 LLR 的幅度和符号。

从复杂度与传播看 SC 的边界

SC 的优点是调度确定、存储线性、实现容易验证；弱点是每一位只有一个候选路径，早期错误没有回退机制。第 14 篇将保留多条候选路径，把一次不可回退的选择改成受 L_{\max} 限制的列表搜索。

小结

SC 在 \log_2N 层上进行蝶形 LLR 更新，每层处理 N 个标量位置，因此时间复杂度为 \Theta(N\log_2N)，采用分层复用存储时空间复杂度为 \Theta(N)。错误的已判决比特通过部分和进入后续 g 更新，可能改变后续 LLR 的方向。理解这一点后，SCL 的路径分裂和剪枝就是针对 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.2009.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.
• 牛凯，《极化码原理与应用》，科学出版社，2021，ISBN 978-7-03-071269-1。