SCL译码：为什么要从单路径走向列表搜索

第 13 篇讲过，SC 译码每到一个信息位就立即做出唯一选择。这个选择如果错了，后面的 g 更新会使用错误的比特估计，译码器也没有机会回头检查另一种可能。

SCL 的想法很直接：信息位不再只试一个值，而是同时保留 0 和 1 两种候选。每条候选都带着自己的已判决比特序列、部分和以及路径度量。候选太多时，译码器按路径度量排序，只留下最有希望的 L_{\max} 条。

本文重点说明路径度量、冻结位更新和一次完整的 N=8,\ L_{\max}=2 手算。

先统一符号和译码约定

本文使用 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}_0^{N-1}，与码字比特 c_j 对齐的原始 LLR 写作 \underline{\lambda}_0^{N-1}：

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

列表中的一条候选路径用 \ell 标记。处理到位置 i 时，它保存已判决比特序列 \hat{u}_{0}^{i,\ell}、部分和以及路径度量 PM_\ell^{(i)}。第 i 位、路径 \ell 的条件 LLR 记为 \Lambda_{i,\ell}。

所有路径使用同一组接收 LLR，但因为已判决比特和部分和不同，它们在下一位得到的 \Lambda_{i,\ell} 也可能不同。条件 LLR 由第 12 篇的 f/g 递归计算。

SC 的问题：当前最优不一定是整体最优

如果当前信息位的 LLR 略偏向 0，SC 会立即选择 0。另一条选择 1 的路径虽然在这一位暂时吃亏，后面的条件 LLR 却可能更支持它。SC 一旦删掉这条路径，后面的证据就没有机会发挥作用。

SCL 的做法是暂时保留多种可能。路径度量记录“到目前为止，这条路径和接收信号是否相符”；剪枝把同时存活的路径数限制在 L_{\max} 以内。

SCL 的基本流程

处理第 i 个输入位时：

1. 对每条存活路径，根据它自己的部分和计算 \Lambda_{i,\ell}；
2. 冻结位只生成 0，信息位生成 0 和 1；
3. 对每个候选增加路径代价；
4. 把所有新候选合在一起，按 PM 升序保留前 L_{\max} 条。

初始时只有一条空路径，且 PM=0。处理完 i=N-1 后，每条存活路径都包含完整的 \hat{\underline{u}}_0^{N-1}。普通 SCL 输出其中 PM 最小的一条；CA-SCL 还会进行 CRC 筛选。

路径最大宽度 L_{\max}

|\mathcal{S}_i|\le L_{\max},\qquad i=-1\text{ 或 }i\in[0,N-1]

L_{\max} 只是同时保存的路径数量上限。L_{\max}=1 时，SCL 退化为 SC；L_{\max}=2 时，两条父路径在信息位最多生成四条候选，再剪枝回两条。如果中间完全不剪枝，处理 q_i 个信息位后最多会有 2^{q_i} 条路径。

路径度量从哪里来

一个分支的概率

固定一条存活路径。译码器在第 i 位真正要比较的是两个数：在当前接收信号和已判决比特条件下，u_i=0 与 u_i=1 哪个更可信。先把这两个条件概率记为

q_0=P(u_i=0\mid\underline{y}_0^{N-1},\hat{\underline{u}}_0^{i-1,\ell}),\qquad q_1=P(u_i=1\mid\underline{y}_0^{N-1},\hat{\underline{u}}_0^{i-1,\ell})

这里的 q_0,q_1 是同一个二元随机变量的两个可能取值，所以

q_0+q_1=1

条件 LLR 的定义是“0 的概率除以 1 的概率再取对数”：

\Lambda_{i,\ell}=\ln\frac{q_0}{q_1}

因此 q_0=e^{\Lambda_{i,\ell}}q_1。把它代入 q_0+q_1=1：

e^{\Lambda_{i,\ell}}q_1+q_1=1 \quad\Longrightarrow\quad q_1=\frac{1}{1+e^{\Lambda_{i,\ell}}}

再由 q_0=e^{\Lambda_{i,\ell}}q_1 得到

q_0=\frac{e^{\Lambda_{i,\ell}}}{1+e^{\Lambda_{i,\ell}}}=\frac{1}{1+e^{-\Lambda_{i,\ell}}}

到这里没有使用任何额外结论，只用了 LLR 定义和两个概率相加为 1。把 b=0 和 b=1 合并，就得到文章中常用的统一写法：

q_{i,\ell}(b)=P(u_i=b\mid\underline{y}_0^{N-1},\hat{\underline{u}}_0^{i-1,\ell})=\frac{1}{1+\exp\left(-(1-2b)\Lambda_{i,\ell}\right)},\qquad b\in\{0,1\}

检查一下：b=0 时，统一式变成 1/(1+e^{-\Lambda})=q_0；b=1 时变成 1/(1+e^{\Lambda})=q_1。所以 \Lambda>0 支持 0，\Lambda<0 支持 1。

为了让“概率大”对应“小代价”，定义

\Delta(b,\Lambda)=-\ln q(b)=\ln\left(1+\exp\left(-(1-2b)\Lambda\right)\right)

累计路径度量

一条路径的逐位条件概率是各步概率的乘积。取负对数后，乘积变成求和：

PM_\ell^{(i)}=PM_\ell^{(i-1)}+\Delta(\hat{u}_{i,\ell},\Lambda_{i,\ell}),\qquad PM_\ell^{(-1)}=0

因此 PM 越小，表示这条路径得到的累计条件概率越大。对同一个父路径，两个分支的度量差为

\Delta(0,\Lambda)-\Delta(1,\Lambda)=-\Lambda

LLR 的符号决定当前哪个分支更好，LLR 的绝对值决定差距大小；最终仍要比较从第 0 位累计到当前位的 PM。

冻结位为什么也要更新度量

上面的 q_{i,\ell}(b) 先解释信息位的两个候选分支。实现路径度量时，冻结位也复用同一个 LLR 代价公式；这相当于比较“当前观测对合法值 0 的支持程度”。如果先把冻结约束直接放进概率归一化，合法值的概率会被强行变成 1，反而无法区分不同路径的信道似然。

冻结位和信息位的区别是“能不能分裂”，不是“要不要看信道证据”。冻结位被编码约束为 0，因此译码器只能写入 0；但在当前路径下，信道递归仍会给出一个 \Lambda_{i,\ell}，它反映接收信号对这个 0 的支持程度。

为避免一个容易混淆的说法，这里的 \Delta(0,\Lambda) 不是把冻结位当成一个需要二选一的信息位，而是把“这条路径被迫写入 0”带来的似然代价记入路径度量。假设某条路径在冻结位得到 \Lambda=2，它只能选择 0，代价为

\Delta(0,2)=\ln(1+e^{-2})\approx0.126928

另一条路径同样只能选择 0，但如果它得到 \Lambda=-2，代价为

\Delta(0,-2)=\ln(1+e^{2})\approx2.126928

两条路径都满足冻结约束，但接收信号对它们的支持程度不同，所以 PM 必须增加不同的数值。冻结位的实际规则是：不分裂，只写入 0，并增加 \Delta(0,\Lambda_{i,\ell})。如果把冻结位的增量全部设为 0，就会丢掉不同路径在这一位上的信道似然差异。只有真正对所有路径都相同的加性常数，才可以从所有 PM 中统一减去。

N=8,\ L_{\max}=2 的完整手算

例子设置

N=8,\qquad K=3,\qquad \mathcal{A}=\{4,6,7\},\qquad \mathcal{A}^c=\{0,1,2,3,5\},\qquad L_{\max}=2

所有冻结位固定为 0。接收端从观测 \underline{y} 得到这一组码字 LLR：

\underline{\lambda}_0^7=(-2.1,-1.9,-1.7,2.3,1.8,0.7,1.3,1.3)

下面沿用第 12 篇的连续位置 f/g 递归约定：

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

从头到尾只使用这一组 \underline{\lambda}_0^7。每条路径都用自己的部分和回传 g 的条件，因而会得到自己的 \Lambda_{i,\ell}。下面数值保留 6 位小数，计算时使用未四舍五入的数值。

先算出前几步的递推消息

这一节只做一件事：把后面表格里的 \Lambda_{i,\ell} 从原始 LLR 一步步算出来。为了避免符号太长，先约定：

• a_j 是一对相邻原始 LLR 做一次 f 运算得到的结果；
• b_j 是两个 a 结果再做一次 f 运算得到的结果；
• \Lambda_i 是当前路径判决第 i 位时使用的 LLR；
• d_j 是把路径 0000 中已经确定的比特代入原始 LLR 后得到的四个 g 结果；
• r_0,r_1 是计算第 6 位时，由路径 000010 的判决得到的两个 g 结果。

这些字母都只是中间计算结果，不是新的接收 LLR，也不是新的路径。先把原始 LLR 按相邻位置两两组合：

\begin{aligned} a_0&=f(-2.1,-1.9)=1.320011,&a_1&=f(-1.7,2.3)=-1.280662,\\ a_2&=f(1.8,0.7)=0.491554,&a_3&=f(1.3,1.3)=0.678498. \end{aligned}

这四个数分别来自 (\lambda_0,\lambda_1)、(\lambda_2,\lambda_3)、(\lambda_4,\lambda_5)、(\lambda_6,\lambda_7)。再把相邻的 a 结果各组合一次：

b_0=f(a_0,a_1)=-0.678594,b_1=f(a_2,a_3)=0.157812

b_0,b_1 是计算前两个冻结位时需要的两个输入量。因此第 0 位的条件 LLR 是

\Lambda_0=f(b_0,b_1)=-0.051485

第 0 位是冻结位，写入 \hat{u}_0=0。把这个 0 代入同一组输入的 g 运算，第 1 位得到

\Lambda_1=g(b_0,b_1,0)=b_1+b_0=-0.520782

前两个冻结位已经确定为 \hat u_0=\hat u_1=0。把这两个 0 分别代入两组 a 结果：

s_0=g(a_0,a_1,0)=0.039349,\qquad s_1=g(a_2,a_3,0)=1.170052

s_0 和 s_1 是两次 g 运算的结果。再对它们做一次 f 运算，就得到第 2 位的 LLR：

\Lambda_2=f(s_0,s_1)=0.020708

第 2 位仍然冻结，写入 \hat u_2=0。把这个 0 代入 g 运算：

\Lambda_3=g(s_0,s_1,0)=1.209401

第 3 位也冻结，写入 \hat u_3=0。所以四个冻结位处理完后，路径为 0000，路径度量为 2.650246。到这里可以看到固定的计算顺序：先用 f 得到当前位的 LLR；确定当前位后，再把这个比特代入 g，为后面的位生成新的输入。

接下来计算信息位。对路径 0000，把已经判决的四个 0 分别代入四对原始 LLR 的 g 运算：

d_0=g(-2.1,-1.9,0)=-4.0,\quad d_1=g(-1.7,2.3,0)=0.6,\quad d_2=g(1.8,0.7,0)=2.5,\quad d_3=g(1.3,1.3,0)=2.6

d_0,d_1 组合后，就得到第 4 位的 LLR：

\Lambda_4=f(d_0,d_1)=f(-4.0,0.6)=-0.416488

如果第 4 位选择 1，计算第 5 位时就把 u_4=1 代入。先分别计算 f(d_0,d_1) 和 f(d_2,d_3)，再用 g 得到第 5 位的 LLR：

\Lambda_{5,00001}=g\left(f(d_0,d_1),f(d_2,d_3),1\right)=2.438855

如果第 4 位选择 0，则同理得到 \Lambda_{5,00000}=1.284508。第 6 位还要继续使用 u_4,u_5 的判决。例如路径 000010 的这两个比特是 1、0，把它们分别代入两组 d 结果：

r_0=g(d_0,d_1,1)=4.6,\qquad r_1=g(d_2,d_3,0)=5.1

这里 r_0,r_1 已经是带入路径 000010 的 u_4,u_5 后得到的两个中间结果，不再是概率 q_0,q_1。于是第 6 位的 LLR 为

\Lambda_{6,000010}=f(r_0,r_1)=4.125984

路径 000000 的 u_4,u_5 是 0、0，对应 r_0=-3.4,r_1=5.1，所以 \Lambda_{6,000000}=-3.232417。最后，把第 6 位的选择代入 g 运算即可得到第 7 位：路径 0000100 使用 u_6=0，得到 \Lambda_{7,0000100}=g(4.6,5.1,0)=9.7；路径 0000001 使用 u_6=1，得到 \Lambda_{7,0000001}=g(-3.4,5.1,1)=8.5。这就是后面各张表中条件 LLR 的来源。

第 0 到第 3 位：四个冻结位

位置 i	位类型	\Lambda_{i,\ell}	选择	增量	累计 PM
0	冻结	-0.051485	0	0.719221	0.719221
1	冻结	-0.520782	0	0.987064	1.706285
2	冻结	0.020708	0	0.682847	2.389132
3	冻结	1.209401	0	0.261114	2.650246

这四步没有分裂，处理完 i=3 后只有

\hat{\underline{u}}_0^3=0000,\qquad PM^{(3)}=2.650246

第 4 位：第一次分裂

i=4 是信息位，当前路径得到

\Lambda_4=-0.416488

负 LLR 更支持 1，但两个分支都保留：

候选路径 \hat{\underline{u}}_0^4	当前选择	增量	PM^{(4)}	处理
00001	1	\Delta(1,-0.416488)=0.506431	2.650246+0.506431=3.156677	保留
00000	0	\Delta(0,-0.416488)=0.922919	2.650246+0.922919=3.573165	保留

现在列表有两条路径。字符串 00001 只是 u_0,\ldots,u_4 的当前判决结果，不是新的接收信号。

第 5 位：两条路径处理同一个冻结约束

i=5 是冻结位。两条路径都只能写入 0，但它们的条件 LLR 不同：

父路径	\Lambda_{5,\ell}	合法选择	增量	新路径	PM^{(5)}
00001	2.438855	0	0.083661	000010	3.240338
00000	1.284508	0	0.244346	000000	3.817512

这里没有分裂，但 PM 仍然更新。如果把冻结位的增量都写成 0，就会错误地认为这两条路径在这一位受到的信号支持完全相同。

第 6 位：四条候选合并后再剪枝

i=6 是信息位。两条父路径得到

\Lambda_{6,000010}=4.125984,\qquad \Lambda_{6,000000}=-3.232417

由父路径 000010 生成：

候选	增量	PM^{(6)}
0000100	\Delta(0,4.125984)=0.016019	3.240338+0.016019=3.256357
0000101	\Delta(1,4.125984)=4.142003	3.240338+4.142003=7.382341

由父路径 000000 生成：

候选	增量	PM^{(6)}
0000000	\Delta(0,-3.232417)=3.271121	3.817512+3.271121=7.088632
0000001	\Delta(1,-3.232417)=0.038703	3.817512+0.038703=3.856215

四条候选必须放在一起排序：

排名	候选路径	PM^{(6)}	处理
1	0000100	3.256357	保留
2	0000001	3.856215	保留
3	0000000	7.088632	剪枝
4	0000101	7.382341	剪枝

所以 }

\mathcal{S}_6=\{0000100,\ 0000001\}

这一步说明了为什么不能只在每个父路径内部保留一个分支。路径 0000001 来自当时较差的父路径 000000，但它在 i=6 选择 1 后，凭借较小的增量进入了前两名。

第 7 位：最后一次分裂

i=7 也是信息位。两条存活路径的条件 LLR 为

\Lambda_{7,0000100}=9.7,\qquad \Lambda_{7,0000001}=8.5

父路径	候选	增量	累计 PM^{(7)}
0000100	00001000	\Delta(0,9.7)=0.000061	3.256418
0000100	00001001	\Delta(1,9.7)=9.700061	12.956418
0000001	00000010	\Delta(0,8.5)=0.000203	3.856418
0000001	00000011	\Delta(1,8.5)=8.500203	12.356418

合并排序后：

排名	完整 \hat{\underline{u}}_0^7	PM^{(7)}	处理
1	00001000	3.256418	保留，最终首选
2	00000010	3.856418	保留
3	00000011	12.356418	剪枝
4	00001001	12.956418	剪枝

普通 SCL 输出 PM 最小的 00001000，对应信息位 (u_4,u_6,u_7)=(1,0,0)。第二条路径对应 (0,1,0)，它虽然不是最终首选，但一直保留到了最后，后续可以交给 CRC 等外部约束继续判断。 }

这个例子说明了什么

1. 信息位的两个候选必须先生成，再统一比较；
2. 冻结位不分裂，但仍要根据每条路径自己的 LLR 更新 PM；
3. PM 是从第 0 位开始累计的，不能只比较当前 LLR；
4. 剪枝发生在所有父路径的候选合并之后，而不是每个父路径单独保留一个孩子。

当 L_{\max}=1 时，i=4 后只留一条路径，另一种信息位选择永远失去竞争机会。增大 L_{\max} 可以降低真实路径过早被删掉的概率，但也会增加计算、存储和排序开销。

复杂度和实现边界

T_{\mathrm{SCL}}(N,L_{\max})=\Theta\left(L_{\max}N\log_2N\right),\qquad S_{\mathrm{SCL}}(N,L_{\max})=O(L_{\max}N)

每条存活路径都需要自己的 LLR 消息、部分和、已判决比特和 PM。工程实现可以用 lazy copy 减少实际复制，但不能让不同路径共享可变的部分和或路径度量。

计算 \ln(1+e^x) 时要使用稳定的 softplus 形式；冻结位只生成 0；候选排序需要定义稳定的平局规则，保证相同 PM 时结果可复现。

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

struct Path {
    std::vector<int> uHat;       // 当前已判决比特，按 0-based 位置保存。
    double pathMetric = 0.0;     // 累计负对数概率，越小越符合当前观测。
    std::size_t birthOrder = 0;  // PM 相等时按生成顺序稳定打破平局。
};

double pathIncrement(double llr, int bit) {
    if (bit != 0 && bit != 1) {
        throw std::invalid_argument("bit must be 0 or 1");
    }
    // 该表达式实现正文中的 Delta(bit, llr)，而不是简单的硬判决罚分。
    const double z = -(1.0 - 2.0 * bit) * llr;
    // 分段计算 log(1+exp(z))，避免 z 很大时直接求 exp(z) 溢出。
    return z > 0.0 ? z + std::log1p(std::exp(-z))
                   : std::log1p(std::exp(z));
}

std::vector<Path> extendAndPrune(const std::vector<Path>& alive,
                                 const std::vector<double>& llr,
                                 std::size_t position,
                                 const std::vector<bool>& frozen,
                                 std::size_t maxWidth,
                                 std::size_t& nextBirthOrder) {
    if (position >= llr.size() || position >= frozen.size() || maxWidth == 0) {
        throw std::invalid_argument("invalid SCL input dimensions");
    }

    std::vector<Path> candidates;
    for (const Path& parent : alive) {
        if (parent.uHat.size() != position) {
            throw std::invalid_argument("path history is not aligned");
        }
        // 冻结位只允许 0；信息位才产生两个合法候选。
        const std::vector<int> bits = frozen[position]
            ? std::vector<int>{0} : std::vector<int>{0, 1};
        for (const int bit : bits) {
            Path child = parent;                 // 复制父路径历史和 PM。
            child.uHat.push_back(bit);           // 只修改当前子路径。
            child.pathMetric += pathIncrement(llr[position], bit);
            child.birthOrder = nextBirthOrder++;
            candidates.push_back(std::move(child));
        }
    }

    // 必须合并所有父路径的孩子后再排序，否则会错删跨父路径的优质候选。
    std::stable_sort(candidates.begin(), candidates.end(),
        [](const Path& left, const Path& right) {
            if (left.pathMetric != right.pathMetric) {
                return left.pathMetric < right.pathMetric;
            }
            return left.birthOrder < right.birthOrder;
        });
    if (candidates.size() > maxWidth) {
        candidates.resize(maxWidth);
    }
    return candidates;
}

int main() {
    // llr[j] 与码字比特 c_j 对齐，约定 llr=log(W(y|0)/W(y|1))。
    // 这里演示路径扩展和 PM 更新；完整译码器要先用每条路径的
    // f/g 递归计算条件 LLR，再把当前位置的标量传进本模块。
    const std::vector<double> llr{1.0, -0.4, 0.7, 1.2,
                                  -0.8, 0.3, 1.1, 0.6};
    const std::vector<bool> frozen{true, true, true, true,
                                   false, true, false, false};

    std::vector<Path> alive{{{}, 0.0, 0}};
    std::size_t nextBirthOrder = 1;
    for (std::size_t i = 0; i < llr.size(); ++i) {
        alive = extendAndPrune(alive, llr, i, frozen, 2, nextBirthOrder);
    }

    for (const Path& path : alive) {
        std::cout << "PM=" << path.pathMetric << " u=";
        for (const int bit : path.uHat) std::cout << bit;
        std::cout << '\n';
    }
}

这段代码只负责列表管理：冻结约束、路径度量、候选合并和全局剪枝。传入的 <code>llr[position]</code> 应该已经是某条路径在当前位置的条件 LLR；完整 SCL 译码器还要为每条路径保存 f/g 递归所需的部分和，并在分裂时复制或延迟复制这些状态。

小结

SC 在每个信息位只选择一个值，早期错误没有回退机会。SCL 为每条存活路径保留自己的已判决比特序列和部分和，在信息位处分裂出 0、1 两个候选，在冻结位只保留 0，然后用

PM_\ell^{(i)}=PM_\ell^{(i-1)}+\ln\left(1+\exp\left(-(1-2\hat{u}_{i,\ell})\Lambda_{i,\ell}\right)\right)

累计路径度量，最后按 PM 升序剪枝。L_{\max}=1 恢复 SC；更大的 L_{\max} 给暂时落后的路径留下继续竞争的机会，但代价是更多的 LLR 计算、路径存储和候选排序。下一篇将在这些候选上加入 CRC 约束。

参考

• 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.
• A. Balatsoukas-Stimming, M. B. Parizi, and A. Burg, “LLR-based successive cancellation list decoding of polar codes,” IEEE Transactions on Signal Processing, vol. 63, no. 19, pp. 5165–5179, Oct. 2015, doi: 10.1109/TSP.2015.2456427.
• 牛凯，《极化码原理与应用》，科学出版社，2021，第 5 章，ISBN 978-7-03-071269-1。