冻结位和信息位怎么选：Polar码构造的第一原则

第 4 篇已经完成了 Polar 编码：先把信息比特和冻结比特放入 $\underline{u}_0^{N-1}$ ，再通过 $\mathbf{G}_N$ 得到码字 $\underline{c}_0^{N-1}$ 。第 6、7 篇又说明，不同索引对应的极化子信道可靠性并不相同。

因此，编码器真正开始工作之前，还有一个不能跳过的问题：哪些位置值得放信息，哪些位置应该固定为已知的冻结值？这个决定就是 Polar 码构造（construction）。构造不是重新设计编码矩阵，而是在给定信道、码长和信息长度后，决定 $\mathcal{A}$ 与 $\mathcal{A}^c$ 。

本文继续使用 0-based 索引。设 Polar 码长为 $N=2^n$ ，信息长度为 $K$ ，码率为：

R=\frac{K}{N}

接收观测写作 $\underline{y}$ ，原始信道 LLR 写作 $\underline{\lambda}$ ，二元码字和 BPSK 符号分别写作 $c_i$ 与 $x_i$ 。全文用 $\boldsymbol{\pi}$ 表示可靠性排序序列，用 $\mathcal{A}$ 表示信息位集合。

为什么编码前必须先做构造

如果把所有 $N$ 个位置都当成同样可靠，那么信息比特可以任意放置，冻结位也没有存在的必要。但 Polar 变换的作用恰恰是把许多次相同的物理信道组合成一组可靠性不同的子信道：有些位置几乎能可靠传递当前比特，有些位置却很容易被噪声混淆。

这时，直接把信息均匀地放入所有位置会浪费最可靠的子信道，也会把信息放进最不可靠的子信道。冻结位的作用，是把后者固定成发送端和接收端都知道的值，让译码器不必从噪声中猜测这些位置；信息位则集中放在更适合传输的索引上。

所以 Polar 码的编码链路不是只有：

\underline{u}_0^{N-1}\longrightarrow\underline{c}_0^{N-1}

在这一步之前，还要有：

\mathrm{reliability}\longrightarrow\mathcal{A},\mathcal{A}^c\longrightarrow\underline{u}_0^{N-1}\longrightarrow\underline{c}_0^{N-1}

如果 $\mathcal{A}$ 选错，即使生成矩阵和蝶形编码器完全正确，最终性能仍然可能很差。构造因此是 Polar 码性能的第一道门槛。

信息位集合和冻结位集合是什么

长度为 $N$ 的极化输入向量写作：

\underline{u}_0^{N-1}=(u_0,u_1,\cdots,u_{N-1})

其中每个位置 $i$ 对应一个极化子信道 $W_N^{(i)}$ 。构造要把索引集合 $[0,N-1]$ 分成两部分：

\mathcal{A}\subseteq[0,N-1],\qquad|\mathcal{A}|=K

$\mathcal{A}$ 是信息位集合，放入原始信息向量 $\underline{m}_0^{K-1}$ ；补集是冻结位集合：

\mathcal{A}^c=[0,N-1]\setminus\mathcal{A},\qquad|\mathcal{A}^c|=N-K

最常见的冻结规则是固定为全零：

\underline{u}_{\mathcal{A}}=\underline{m}_0^{K-1},\qquad \underline{u}_{\mathcal{A}^c}=\underline{0}

这里的下标含义需要说清楚。 $\mathcal{A}$ 是集合，本身没有前后顺序； $\underline{u}_{\mathcal{A}}$ 按 $\mathcal{A}$ 中索引的升序抽取，依次放入 $m_0,m_1,\cdots,m_{K-1}$ 。例如：

\mathcal{A}=\{1,4,6,7\}\longrightarrow \underline{u}_{\mathcal{A}}=(u_1,u_4,u_6,u_7)=(m_0,m_1,m_2,m_3)

冻结位不是“删除位”。它们仍然参与 Polar 变换，仍然影响码字 $\underline{c}$ ；只是发送端预先知道它们的值，接收端也可以在译码时利用这些已知信息。

理想情况下应该如何选择子信道

第 6 篇已经给出两个可靠性指标：对称容量 $I(W_N^{(i)})$ 越大越可靠，Bhattacharyya 参数 $Z(W_N^{(i)})$ 越小越可靠。为了把这种比较写成可以执行的规则，先定义一个有序的可靠性排序序列：

\boldsymbol{\pi}=(\pi_0,\pi_1,\cdots,\pi_{N-1})

如果按照 $Z$ 从小到大排序，则：

Z\left(W_N^{(\pi_0)}\right)\le Z\left(W_N^{(\pi_1)}\right)\le\cdots\le Z\left(W_N^{(\pi_{N-1})}\right)

此时 $\pi_0$ 是最可靠的索引， $\pi_{N-1}$ 是最不可靠的索引。给定信息长度 $K$ 后，选择排序序列前面的 $K$ 个索引：

\mathcal{A}=\{\pi_0,\pi_1,\cdots,\pi_{K-1}\}

冻结集合则相对于全集 $[0,N-1]$ 定义为：

\mathcal{A}^c=[0,N-1]\setminus\mathcal{A}

如果可靠性使用的是均值 $\mu_i$ ，也可以按 $\mu_i$ 从大到小排序；如果使用错误概率上界，则按上界从小到大排序。重要的不是固定某一个指标，而是先说明比较依据和升降序，再从有序序列中选位。

构造到底在优化什么

把信息位放到可靠子信道上，不只是经验规则。以 SC 译码为例，Polar 码块错误概率有经典上界：

P_{\mathrm{e}}\le\sum_{i\in\mathcal{A}}Z\left(W_N^{(i)}\right)

在 $N$ 、 $K$ 和基础信道固定时，右侧是被选信息位的可靠性代价。若只能选择 $K$ 个位置，选择 $Z$ 最小的 $K$ 个子信道，就直接最小化这个上界的逐项和。

这也解释了为什么冻结位不能随意指定。把一个高 $Z$ 的子信道放进 $\mathcal{A}$ ，等于把信息比特交给一个更容易出错的判决位置；把低 $Z$ 的子信道冻结，则等于放弃了本来可以可靠传输的信息通道。

不过，上界不是完整的真实性能模型。有限码长、译码算法、CRC、实现中的近似和实际信道条件都会影响结果。因此构造的完整输入至少包括：

输入	作用
基础信道模型	决定可靠性如何计算
码长 $N$	决定递归层数和子信道数量
信息长度 $K$	决定需要保留多少可靠位置
可靠性指标	决定排序依据
目标译码器	影响排序是否适合最终性能

N=8：从 BEC 可靠性递归到信息位选择

现在完整做一个 $N=8$ 的例子。取基础信道：

W=\mathrm{BEC}(0.5),\qquad N=8=2^3

第 7 篇已经说明，BEC 中每个子信道的 $Z$ 就是擦除率。减号和加号递推分别为：

T_-(z)=2z-z^2,\qquad T_+(z)=z^2

从 $Z_0=0.5$ 开始，每一层把一个节点扩展成“先减号、后加号”的两个节点。为了避免路径记号和数组索引混淆，下面直接按 0-based 索引列出结果：

\begin{array}{c|c|c|c} i&\text{路径}&Z\left(W_8^{(i)}\right)&I\left(W_8^{(i)}\right)=1-Z\left(W_8^{(i)}\right)\\\hline 0&---&0.99609375&0.00390625\\ 1&--+&0.87890625&0.12109375\\ 2&-+-&0.80859375&0.19140625\\ 3&-++&0.31640625&0.68359375\\ 4&+--&0.68359375&0.31640625\\ 5&+-+&0.19140625&0.80859375\\ 6&++-&0.12109375&0.87890625\\ 7&+++&0.00390625&0.99609375 \end{array}

例如，索引 $3$ 的路径是 $-++$ ：

0.5\xrightarrow{T_-}0.75\xrightarrow{T_+}0.5625\xrightarrow{T_+}0.31640625

索引 $5$ 的路径是 $+-+$ ：

0.5\xrightarrow{T_+}0.25\xrightarrow{T_-}0.4375\xrightarrow{T_+}0.19140625

这两个路径都包含两个加号和一个减号，但顺序不同，所以最后的可靠性也不同。构造不能只数路径中有几个加号，而必须使用明确的数值指标。

按 $Z$ 从小到大排序：

\boldsymbol{\pi}=(7,6,5,3,4,2,1,0)

这里的排序含义是：

Z\left(W_8^{(7)}\right)\le Z\left(W_8^{(6)}\right)\le\cdots\le Z\left(W_8^{(0)}\right)

取 $K=4$ ：一半位置承载信息

先取 $K=4$ ，于是码率为：

R=\frac{K}{N}=\frac{4}{8}=0.5

排序序列中的前四个索引是 $7,6,5,3$ ，因此信息集合是无序集合：

\mathcal{A}=\{3,5,6,7\}

冻结集合相对于全集 $[0,7]$ 为：

\mathcal{A}^c=[0,7]\setminus\mathcal{A}=\{0,1,2,4\}

取一组信息比特：

\underline{m}_0^3=(1,0,1,1)

按照 $\mathcal{A}$ 的升序 $3,5,6,7$ 放入 $\underline{u}$ ：

\underline{u}_0^7=(0,0,0,1,0,0,1,1)

这里 $u_0,u_1,u_2,u_4$ 是冻结位，全部取 0； $u_3,u_5,u_6,u_7$ 依次承载 $m_0,m_1,m_2,m_3$ 。之后编码器才执行：

\underline{c}_0^7=\underline{u}_0^7\mathbf{G}_8

如果沿用第 4 篇的自然生成矩阵和蝶形约定，这组输入得到：

\underline{c}_0^7=(1,0,1,0,0,1,0,1)

这个码字不是构造本身的结果，而是构造结果 $\mathcal{A}$ 经过信息填充后，再交给编码器得到的结果。两者的职责必须分开。

取 $K=3$ ：只保留最可靠的三个位置

如果把信息长度改成 $K=3$ ，可靠性排序序列不变，但信息集合要重新选择：

R=\frac{3}{8},\qquad \mathcal{A}=\{5,6,7\}

此时：

\mathcal{A}^c=[0,7]\setminus\mathcal{A}=\{0,1,2,3,4\}

可以看到， $K$ 改变时不一定要重新计算所有子信道的可靠性；在同一个信道模型和码长下，只需从同一排序序列中取排在前面的 $K$ 个索引即可。若 $N$ 、信道模型或构造方法改变，排序序列通常也要重新计算。

有限码长下不能只谈“完全极化”

极化定理描述的是 $N$ 趋于无穷时的趋势，但工程构造使用的是有限 $N$ 。在本例中，最可靠的索引 $7$ 的 $Z$ 约为 $0.0039$ ，最不可靠的索引 $0$ 的 $Z$ 约为 $0.9961$ ，两端已经很接近 0 和 1；然而索引 $3$ 与 $4$ 的 $Z$ 分别为 $0.3164$ 和 $0.6836$ ，仍然处在中间区域。

这带来三个实际后果。

第一，信息位选择不是“可靠或不可靠”这样简单的二分类，而是要在有限数量的候选位置中比较相对可靠性。

第二，码率越高，需要放入 $\mathcal{A}$ 的位置越多，就越可能把中间可靠性的子信道也用于传输信息。

第三，同一个 $\mathcal{A}$ 配合 SC、SCL 或 CA-SCL 时，性能不必完全相同。构造指标提供的是选位依据，译码器决定这些选位在实际错误事件中的表现。

因此，“容量达成”不是说有限码长下每一个信息位都同样可靠，而是说随着码长增加，可以找到一组比例接近 $I(W)$ 的高可靠子信道。

四类常见构造方法为什么不同

不同构造方法的共同输出都是可靠性排序序列 $\boldsymbol{\pi}$ ，但它们观察信道的方式不同。可以把区别先压缩成一个问题：构造器拿什么作为输入，又用什么近似或结构判断子信道好坏？

Bhattacharyya / BEC 构造

如果基础信道是 BEC，子信道仍然是 BEC，擦除率递推完全由：

z^-=2z-z^2,\qquad z^+=z^2

决定。此时 $Z$ 就是擦除率，计算简单、结果直观，特别适合手算和解释极化机制。它的限制也很明确：AWGN 的输出是连续实数，不能用一个擦除率完整描述。

密度进化与高斯近似 GA

对于 BI-AWGN，严格的密度进化（DE）追踪每个子信道的 LLR 分布。它比较准确，但离散化、卷积和 box-plus 映射都会带来较高数值代价。

高斯近似（GA）假设全零参考下的 LLR 近似服从：

L_i\sim\mathcal{N}(\mu_i,2\mu_i)

于是每个子信道用均值 $\mu_i$ 表示，并通过加号分支的均值相加和减号分支的 $\phi$ 递推得到排序。GA 需要 design-SNR 作为构造输入，记作 $\rho_{\mathrm{des}}$ ；实际仿真时的信噪比另记为 $\rho_{\mathrm{sim}}$ ，不能混用。第 9、10 篇会分别展开 DE 和 GA。

Reed-Muller / RM 构造

RM 构造不先追踪某个具体信道的 LLR 分布，而是利用生成矩阵行重量的结构。若 $\boldsymbol{\gamma}_i$ 是 $\mathbf{G}_N$ 的第 $i$ 行，则自然顺序约定下：

w_H(\boldsymbol{\gamma}_i)=2^{w_H(i)}

其中左边是行向量的汉明重量，右边的 $w_H(i)$ 是整数 $i$ 的二进制展开中 1 的个数。行重量较大的位置通常具有更强的结构保护，因此可以按行重量从大到小构造排序。

RM 的优点是简单、与信道参数无关；缺点是它没有利用当前 AWGN 信道的具体可靠性，短码或特定信噪比下可能不如信道相关构造。

Polarization Weight / PW 构造

PW 用一个轻量的解析权重近似子信道可靠性。它不需要进行完整 DE 或 GA，而是根据索引的二进制展开和一个经验参数计算权重，再按权重排序。

PW 的定位介于“完全结构化的 RM”与“信道相关的 GA”之间：计算便宜、容易复现，适合资源有限或需要固定可靠性序列的场景，但它是近似排序，不能保证在所有 $N$ 、码率和信道条件下都最优。

四类方法可以这样对照：

方法	主要输入	排序依据	是否依赖信道参数	典型用途
Bhattacharyya / BEC	擦除率 $\epsilon$	$Z$ 从小到大	是，且主要适合 BEC	手算、理论说明
DE	LLR 密度	密度导出的可靠性	是	高精度构造、基准验证
GA	$\rho_{\mathrm{des}}$ 和均值递推	$\mu$ 从大到小	是	AWGN 工程构造
RM	生成矩阵行结构	行重量从大到小	否	简单、信道无关构造
PW	索引二进制展开、权重参数	PW 从大到小	通常弱依赖或不依赖	轻量近似、固定序列

这里的“从前到后”仍然只对排序序列成立。最终得到的 $\mathcal{A}$ 仍是集合，不能把排序序列的顺序误写成集合的顺序。

构造器应该输出什么

从软件接口看，构造器不应该把可靠性计算、信息位填充、Polar 编码和译码全部揉成一个函数。最小的构造接口可以分成两步：

根据 $N$ 、信道参数和方法得到可靠性排序序列 $\boldsymbol{\pi}$ 。
根据 $K$ 取 $\boldsymbol{\pi}$ 中排在前面的 $K$ 个索引生成 $\mathcal{A}$ ，再由全集得到 $\mathcal{A}^c$ 。

用伪接口表示：

\boldsymbol{\pi}=\mathrm{ReliabilityRanking}(N,\mathrm{channel},\mathrm{method})

\mathcal{A}=\mathrm{SelectInformationSet}(\boldsymbol{\pi},K),\qquad \mathcal{A}^c=[0,N-1]\setminus\mathcal{A}

最小 C++ 结构可以只负责第二步。假定 reliabilityOrder 已经按照“最可靠到最不可靠”返回索引：

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

// 构造结果只包含两个集合：信息位索引和冻结位索引。
struct PolarConstruction {
    std::vector<std::size_t> information;
    std::vector<std::size_t> frozen;
};

// reliabilityOrder 必须按“最可靠到最不可靠”排列；K 决定选取多少个信息位。
PolarConstruction selectInformationSet(
    const std::vector<std::size_t>& reliabilityOrder,
    std::size_t K) {
    // 排序序列的长度就是 Polar 母码长 N。
    const std::size_t N = reliabilityOrder.size();
    // 信息位数量不能超过可用的索引总数。
    if (K > N) {
        throw std::invalid_argument("K must not exceed N");
    }

    // 排序序列前 K 个索引是最可靠的位置，先复制为信息位候选。
    PolarConstruction result;
    result.information.assign(reliabilityOrder.begin(), reliabilityOrder.begin() + K);

    // 用布尔表记录已选索引，便于检查重复项并生成冻结集合。
    std::vector<bool> isInformation(N, false);
    for (const std::size_t index : result.information) {
        // 合法排序必须是 [0, N-1] 的排列，不能越界或重复。
        if (index >= N || isInformation[index]) {
            throw std::invalid_argument("reliability order must be a permutation");
        }
        isInformation[index] = true;
    }

    // 没有被选为信息位的索引全部归入冻结集合。
    for (std::size_t index = 0; index < N; ++index) {
        if (!isInformation[index]) {
            result.frozen.push_back(index);
        }
    }

    // 信息集合本身无序；按索引升序保存，方便后续填充 u 向量。
    std::sort(result.information.begin(), result.information.end());
    return result;
}

这个函数有两个值得注意的边界。

第一，输入的 reliabilityOrder 是有序序列，所以前 $K$ 个元素表示选择顺序；输出的 information 在最后按索引升序整理，方便按照 $\mathcal{A}$ 的升序把信息向量写入 $\underline{u}$ 。

第二，函数检查排序序列是否真的是 $[0,N-1]$ 的一个排列，避免重复索引或越界索引悄悄破坏编码输入。它不计算 LLR，不生成码字，也不执行 SC/SCL 译码，这些属于其它模块。

初学者最容易混淆的几个点

第一，构造不是编码。构造输出的是 $\mathcal{A}$ 和 $\mathcal{A}^c$ ；编码器接收填好冻结位的信息向量后，才输出码字 $\underline{c}$ 。

第二， $\mathcal{A}$ 不是排序列表。排序列表是 $\boldsymbol{\pi}$ ，集合 $\mathcal{A}$ 没有“第一个”或“前四个”这样的内在顺序。

第三， $N$ 、 $K$ 和 $R$ 不是同一个量。 $N$ 是母码长， $K$ 是进入 Polar 编码器的信息比特数， $R=K/N$ 是码率。

第四，BEC 的排序不能无条件搬到 AWGN。BEC 中 $Z$ 是擦除率，AWGN 需要 LLR 分布、DE 或 GA 等信道模型相关方法。

第五，构造所用的 design-SNR $\rho_{\mathrm{des}}$ 不等于实际仿真的 $\rho_{\mathrm{sim}}$ 。前者影响选位，后者用于测试曲线；两者可以不同，也必须分别记录。

小结

Polar 码构造解决的是“ $N$ 个极化子信道中，哪 $K$ 个用来承载信息”这个问题。先根据可靠性指标形成有序序列：

\boldsymbol{\pi}=(\pi_0,\pi_1,\cdots,\pi_{N-1})

再取排序序列中最可靠的 $K$ 个索引组成信息集合：

\mathcal{A}=\{\pi_0,\pi_1,\cdots,\pi_{K-1}\},\qquad \mathcal{A}^c=[0,N-1]\setminus\mathcal{A}

在 $W=\mathrm{BEC}(0.5)$ 、 $N=8$ 的例子中，可靠性排序为：

\boldsymbol{\pi}=(7,6,5,3,4,2,1,0)

当 $K=4$ 时：

\mathcal{A}=\{3,5,6,7\},\qquad \mathcal{A}^c=\{0,1,2,4\}

Bhattacharyya/BEC、DE、GA、RM、PW 的区别，不在于最后输出的集合形式不同，而在于它们用不同方式估计子信道可靠性。BEC 适合解释和手算，DE 提供高精度分布追踪，GA 以较低代价服务 AWGN 构造，RM 和 PW 则利用结构或近似权重降低计算复杂度。

下一篇将进入 AWGN 下的密度进化：既然连续信道不能用一个擦除率表示，构造器究竟如何追踪每个子信道的 LLR 分布？

参考

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.
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.
I. Tal and A. Vardy, “How to construct polar codes,” IEEE Transactions on Information Theory, vol. 59, no. 10, pp. 6562–6582, Oct. 2013, doi: 10.1109/TIT.2013.2272694.
S. B. Korada, E. Şaşoğlu, and R. Urbanke, “Polar Codes: Characterization of Exponent, Bounds, and Constructions,” IEEE Transactions on Information Theory, vol. 56, no. 12, pp. 6253–6264, Dec. 2010, doi: 10.1109/TIT.2010.2080990.