番外 D：Beta-expansion 与 Polarization Weight
Polar 码构造要解决的问题是：在 N 个极化子信道中，哪些位置更适合承载信息。密度进化和高斯近似（Gaussian Approximation，GA）会结合设计信道估计可靠性；Polarization Weight（PW）采用另一种思路，它只读取子信道索引的二进制表示，再用一个加权和给出可靠性排序。
这种方法计算量很小，也不需要输入设计信噪比 \rho_{\mathrm{des}}。不过，PW 给出的是结构性的可靠性近似，不是每个子信道在指定信道条件下的精确错误概率。理解这一点，是正确使用 PW 的前提。
本文采用 0-based 索引。令码长 N=2^n，第 i 个极化子信道记作 W_N^{(i)}，其中 i\in[0,N-1]。可靠性排序序列统一写作
\boldsymbol{\pi}=(\pi_0,\pi_1,\ldots,\pi_{N-1}),其中 \pi_0 对应最可靠的子信道，随后可靠性依次降低。
在写出 PW 公式以前：通用偏序能告诉我们什么
有些子信道之间的可靠性关系不需要指定具体的信道参数。为了把方向说清楚，本文用
i\preceq k表示 W_N^{(i)} 的可靠性不高于 W_N^{(k)}。通用偏序（Universal Partial Order，UPO）中有两条容易理解的基本关系。
第一条是加法关系（addition）。若两个索引的二进制表示只有一位不同，把这一位由 0 改为 1 后，对应的子信道更可靠。例如在 N=8 时，1=(001)_2，3=(011)_2，因此有
1\preceq3.第二条是左交换关系（left-swap）。设 k>j，两个索引仅在第 k 位和第 j 位不同。若把较高位置和较低位置上的 01 换成 10，可靠性提高。例如
(001)_2\preceq(010)_2, \qquad\text{即}\qquad 1\preceq2.这两条关系能够确定许多索引的先后，却不能确定全部关系。以 N=8 为例，3=(011)_2 与 4=(100)_2 既不是简单地增加一个 1，也不能通过一次左交换相互得到，所以仅靠上述两条关系不能判断二者谁更可靠。
这就是“偏序”的含义：它只给出一部分必然成立的先后关系。构造 Polar 码需要完整排序，因此还要为这些未定关系补充判据。PW 的作用正是把每个二进制索引映射成一个实数，再按实数大小完成排序。
从偏序关系推到 Beta-expansion
先把索引 i 写成 n 位二进制数：
i=\sum_{j=0}^{n-1}b_j2^j, \qquad b_j\in\{0,1\}.这里 b_0 是最低有效位，b_{n-1} 是最高有效位。我们希望用一个加性分数表示索引的结构可靠性，最一般的线性形式可以写成
w(i)=\sum_{j=0}^{n-1}b_j a_j,其中 a_j 表示第 j 个二进制位置对分数的贡献。
现在把 UPO 的要求代入这个分数。
对于加法关系，把任意一位 b_j 从 0 改为 1 后，分数应增大，所以必须有
a_j>0.对于左交换关系，把较低位置 j 上的 1 移到较高位置 k，其中 k>j，分数也应增大，因此必须有
a_k>a_j.也就是说，各位置的权重应为正数，并且随位置升高而增大。为了只用一个参数描述全部位置，再作一个简化假设：相邻位置的权重保持固定倍率 \beta，即
\frac{a_{j+1}}{a_j}=\beta, \qquad \beta>1.由此得到 a_j=a_0\beta^j。整体乘上正常数不会改变排序，所以令 a_0=1，便得到
w_\beta(i)=\sum_{j=0}^{n-1}b_j\beta^j.这就是本文使用的 Beta-expansion 权重，也是 PW 的基本形式。需要强调的是，UPO 只要求 a_j 为递增正数；把相邻权重之比固定为 \beta 是为了得到简单、可扩展的全排序。换句话说，UPO 为公式规定了方向，固定倍率假设给出了具体形式，不能说 UPO 唯一推出了 \beta^j。
因为 \beta>1，加法关系和左交换关系都会使 w_\beta(i) 增大，所以 PW 不会违背这两条偏序关系。对于 UPO 无法判断的索引对，PW 则通过比较两个实数来决定先后。
在 Polar 码构造的语境中，Beta-expansion 指上述非整数基展开形式，PW 指用这个展开值衡量极化位置并完成排序。二者关注的重点不同，但在本文所讨论的基本算法里使用的是同一个公式。
N=16 的完整手算
下面采用文献中常用的参数
\beta=2^{1/4}\approx1.189207.因为 \beta^4=2，前四个位置权重可以逐项算出：
\beta^0=1, \qquad \beta^1\approx1.189207, \qquad \beta^2=\sqrt{2}\approx1.414214, \qquad \beta^3\approx1.681793.取索引 i=3。它的四位二进制表示是 0011，即 b_0=1,b_1=1,b_2=0,b_3=0，所以
w_\beta(3) =1\cdot\beta^0+1\cdot\beta^1 =1+1.189207 =2.189207.再取索引 i=12。因为 12=(1100)_2，所以
w_\beta(12) =1\cdot\beta^2+1\cdot\beta^3 =1.414213562+1.681792831 \approx3.096006.其余索引完全按照同一规则计算。下表保留 6 位小数，排序时使用未舍入的数值。
| i | (b_3b_2b_1b_0) | w_\beta(i) 的展开 | w_\beta(i) |
|---|---|---|---|
| 0 | 0000 | 0 | 0.000000 |
| 1 | 0001 | 1 | 1.000000 |
| 2 | 0010 | \beta | 1.189207 |
| 3 | 0011 | 1+\beta | 2.189207 |
| 4 | 0100 | \beta^2 | 1.414214 |
| 5 | 0101 | 1+\beta^2 | 2.414214 |
| 6 | 0110 | \beta+\beta^2 | 2.603421 |
| 7 | 0111 | 1+\beta+\beta^2 | 3.603421 |
| 8 | 1000 | \beta^3 | 1.681793 |
| 9 | 1001 | 1+\beta^3 | 2.681793 |
| 10 | 1010 | \beta+\beta^3 | 2.871000 |
| 11 | 1011 | 1+\beta+\beta^3 | 3.871000 |
| 12 | 1100 | \beta^2+\beta^3 | 3.096006 |
| 13 | 1101 | 1+\beta^2+\beta^3 | 4.096006 |
| 14 | 1110 | \beta+\beta^2+\beta^3 | 4.285214 |
| 15 | 1111 | 1+\beta+\beta^2+\beta^3 | 5.285214 |
参考资料常按权重升序列出索引，也就是从最不可靠排到最可靠：
(0,1,2,4,8,3,5,6,9,10,12,7,11,13,14,15).本系列的 \boldsymbol{\pi} 采用相反方向，即从最可靠排到最不可靠，因此要把上面的序列反转：
\boldsymbol{\pi}_{\mathrm{PW}} =(15,14,13,11,7,12,10,9,6,5,3,8,4,2,1,0).若取 K=8，就在这个有序序列中取最前面的 8 个索引，再组成信息集合
\mathcal{A} =\{7,9,10,11,12,13,14,15\}.这里把集合写成索引升序，只是为了阅读方便；选位依据仍然是可靠性降序序列 \boldsymbol{\pi}_{\mathrm{PW}}。
下图把 N=2,4,8,16 的 PW 顺序放在一起。码长增加时，原有索引之间的相对次序仍然保留，新出现的索引插入已有次序之中。
图 1：\beta=2^{1/4} 时的嵌套排序。
\beta 为什么会改变排序
对任意两个索引 i 和 k，设它们的二进制位分别为 b_j 和 d_j，权重差为
w_\beta(i)-w_\beta(k) =\sum_{j=0}^{n-1}(b_j-d_j)\beta^j.右侧是关于 \beta 的多项式。当这个多项式经过 0 时，两个索引的相对顺序就会交换。
最简单的例子正是 UPO 未确定的索引 3 和 4：
w_\beta(3)=1+\beta, \qquad w_\beta(4)=\beta^2.令两者相等，可以得到临界值：
\beta^2-\beta-1=0, \qquad \beta=\frac{1+\sqrt{5}}{2}\approx1.618034.因此：
- 当 1<\beta<1.618034 时，1+\beta>\beta^2，索引 3 的 PW 较大；
- 当 \beta>1.618034 时，1+\beta<\beta^2，索引 4 的 PW 较大；
- 当 \beta 正好等于临界值时，两者同分，必须另外规定并列处理方式。
对 N=16，需要比较的未定关系更多，因此会出现多个临界值。参考页用下图展示了五个 \beta 区间对应的排序；黑色箭头表示 UPO 已经确定的关系，红色箭头表示通过多项式比较补充的关系。
图 2：N=16 时不同 \beta 区间对应的排序。
这也说明，使用 PW 时不能只写“采用 Beta-expansion”，还必须同时说明 \beta、二进制位方向、排序方向和并列规则。
为什么常取 \beta=2^{1/4}
\beta=2^{1/4}\approx1.1892 不是由某一个 AWGN 信噪比直接代入公式算出的。He 等人的工作先用 UPO 固定必然成立的关系，再比较 UPO 尚未确定的索引对。由于每一对索引的权重差都是关于 \beta 的多项式，其正根会把 \beta>1 划分成若干区间；同一区间内不会发生新的顺序交换。
随后，可以用 GA 结果和有限码长仿真检查哪些区间更合适。随着考察码长增加，文献给出的可用范围逐渐收窄到 1.1892 附近，并结合 Beta-expansion 的渐近分析选取
\beta=2^{1/4}.因此，更准确的理解是：2^{1/4} 是兼顾偏序、跨码长稳定性和数值结果的常用固定参数，而不是所有信道、码长、码率和译码方式下都严格最优的常数。若研究目标是某个指定的 AWGN 工作点，仍应把 PW 与该 \rho_{\mathrm{des}} 下的 GA 或密度进化构造放在相同仿真条件下比较。
嵌套性质具体指什么
设码长由 N=2^n 增加到 2N=2^{n+1}。对于原来的索引 i\in[0,N-1]，新增的最高位为 0，所以权重不变：
w_\beta^{(2N)}(i)=w_\beta^{(N)}(i).与它对应的新索引 i+N 的最高位为 1，因此
w_\beta^{(2N)}(i+N) =w_\beta^{(N)}(i)+\beta^n.这两个等式带来两个直接结论：原有 N 个索引之间的相对次序不变；新增 N 个索引之间的相对次序也与原序列相同。长度 2N 的完整序列，只需要把这两个内部顺序不变的序列合并。
这里的“嵌套”说的是排序结构可以跨码长复用，并不自动保证任意 K 下都有 \mathcal{A}_N\subseteq\mathcal{A}_{2N}。信息集合还取决于两个码长各自选取多少个位置，以及索引如何对应。
PW 与 GA、RM、5G 可靠性序列的区别
| 方法 | 使用的信息 | 是否依赖 \rho_{\mathrm{des}} | 结果的含义 |
|---|---|---|---|
| GA | AWGN 下 LLR 均值的近似演化 | 是 | 指定设计条件下的可靠性估计 |
| RM | 索引的汉明重量或生成矩阵行重量 | 否 | 只区分极化变换的行重量结构 |
| PW | 二进制索引及参数 \beta | 否 | 满足基本偏序关系的结构性全排序 |
| 5G 可靠性序列 | 3GPP 规定的预定义序列 | 否 | 标准链路必须遵守的选位依据 |
当 \beta 趋近于 1 时，\beta^j 之间的差别缩小，PW 越来越接近按二进制 1 的个数分组，因此与 RM 的结构更接近。当 \beta 增大时，高位置上的 1 获得更大的影响。PW 由此比 RM 给出了更细的次序，但它仍然没有使用具体信道的 LLR 分布。
PW 与 GA 在部分参数下可能给出相同或接近的信息集合，但两者的依据不同。参考文献 [2] 和参考页 [1] 给出的特定 AWGN、码长及译码配置中，两种构造的仿真结果接近；这不能推广为所有配置下严格等价。
PW 也不能代替 5G NR 的预定义可靠性序列。实现标准链路时，应直接遵守 3GPP TS 38.212；PW 适合教学、研究和不受标准表约束的构造实验。
一个可独立运行的 C++ 示例
下面的程序输入 N、K 和 \beta，先计算每个索引的 PW，再按“权重降序、同分时索引升序”生成 \boldsymbol{\pi}_{\mathrm{PW}}。程序随后从该有序序列中选出最可靠的 K 个索引，并把信息集合按索引升序输出。
程序仍采用本文的位序：b_0 是最低有效位。权重比较不使用人为容差，因为把“足够接近”直接当作相等可能破坏排序的一致性；若浮点结果完全相等，则用索引升序作为确定的并列规则。
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <vector>
struct PwResult {
// reliability_order[0] 是 PW 最大、因而被认为最可靠的索引。
std::vector<std::size_t> reliability_order;
// information_set 保存选出的 K 个位置，并按索引升序排列。
std::vector<std::size_t> information_set;
// weight[i] 与子信道索引 i 一一对应，便于复核每一步计算。
std::vector<long double> weight;
};
PwResult build_pw_order(std::size_t N,
std::size_t K,
long double beta) {
// N 必须是正的 2 的幂；K 不能超过 N；beta>1 才满足本文的
// 加法关系和左交换关系的权重方向。
if (N == 0 || (N & (N - 1)) != 0 || K > N || beta <= 1.0L) {
throw std::invalid_argument("N, K, or beta is outside its range");
}
// n=log2(N)，同时也是表示每个索引所需的二进制位数。
std::size_t n = 0;
for (std::size_t length = N; length > 1; length >>= 1) {
++n;
}
// powers[j]=beta^j。先递推幂值，可以避免为每个索引重复求幂。
std::vector<long double> powers(n, 1.0L);
for (std::size_t j = 1; j < n; ++j) {
powers[j] = powers[j - 1] * beta;
}
std::vector<long double> weight(N, 0.0L);
for (std::size_t i = 0; i < N; ++i) {
// 循环不变量：处理完位置 0 到 j 后，weight[i] 等于这些
// 已处理位置中所有非零二进制位对应的 beta 幂之和。
for (std::size_t j = 0; j < n; ++j) {
if (((i >> j) & 1U) != 0U) {
weight[i] += powers[j];
}
}
if (!std::isfinite(weight[i])) {
throw std::overflow_error("polarization weight overflow");
}
}
std::vector<std::size_t> order(N);
std::iota(order.begin(), order.end(), 0);
// 权重大的索引排在前面；若权重完全相等，以索引升序消除歧义。
std::sort(order.begin(), order.end(),
[&weight](std::size_t a, std::size_t b) {
if (weight[a] > weight[b]) {
return true;
}
if (weight[a] < weight[b]) {
return false;
}
return a < b;
});
// 先从可靠性有序序列中选 K 个位置，再按索引升序保存集合。
// 排序集合不会改变已经选中了哪些位置。
std::vector<std::size_t> information(order.begin(), order.begin() + K);
std::sort(information.begin(), information.end());
return {order, information, weight};
}
int main() {
const std::size_t N = 16;
const std::size_t K = 8;
const long double beta = std::pow(2.0L, 0.25L);
const PwResult result = build_pw_order(N, K, beta);
std::cout << "Reliability order: ";
for (std::size_t i : result.reliability_order) {
std::cout << i << ' ';
}
std::cout << "\nInformation set: ";
for (std::size_t i : result.information_set) {
std::cout << i << ' ';
}
std::cout << '\n';
}程序输出应为：
Reliability order: 15 14 13 11 7 12 10 9 6 5 3 8 4 2 1 0
Information set: 7 9 10 11 12 13 14 15这个结果与前面的 N=16 手算完全一致。若得到相反序列，首先检查排序方向；若只在少数位置不同，首先检查 b_0 是否确实对应最低有效位，以及 \beta 是否采用了同一个数值。
怎样公平比较 PW 与其它构造
比较 PW、GA 或 RM 时，应先固定 N、K、编码方式、信道、调制、译码方法、列表最大宽度 L_{\max} 和 CRC 长度，再分别生成信息集合。仿真信噪比统一记为 \rho_{\mathrm{sim}}；GA 使用的设计信噪比另记为 \rho_{\mathrm{des}}，不能混成同一个参数。
若只想比较两个方法选位是否相同，可以计算信息集合的对称差：
d_{\mathrm{set}} =\left|\mathcal{A}_{\mathrm{PW}}\mathbin{\triangle}\mathcal{A}_{\mathrm{GA}}\right|.其中 \triangle 表示对称差。这个数只说明两个集合有多少个位置不同，不能直接推出谁的 BLER 更低。性能结论仍应来自相同 \rho_{\mathrm{sim}}、相同译码和相同停止条件下的块错误率比较。
参考页还转载了 PW 与 GA 在特定参数下的对比结果。图中两组曲线接近，只能说明该实验配置下的结果，不能作为所有码长和码率下的普遍结论。
图 3：参考页给出的 PW 与 GA 仿真比较，纵轴表示达到 \mathrm{BLER}=10^{-3} 所需的 SNR；图中配置包括 AWGN、QPSK、L_{\max}=8 的 SCL 和 19 比特 CRC。
小结
PW 的逻辑可以归纳为四步：先用 UPO 确定不依赖具体信道的可靠性关系；再把二进制索引写成各位置贡献的加权和；随后用 a_{j+1}/a_j=\beta 的固定倍率假设得到 w_\beta(i)=\sum b_j\beta^j；最后按权重降序生成可靠性序列 \boldsymbol{\pi}_{\mathrm{PW}}。
\beta=2^{1/4} 是常用参数，但不是任意场景下的最优值。实际使用 PW 时，必须同时记录 \beta、位序、排序方向和并列规则。它的优势是计算简单、跨码长结构稳定；它的限制是没有利用指定信道和 \rho_{\mathrm{des}} 的 LLR 分布。
参考文献
- [1] Marshall，“Polar Code（20）Beta-expansion”，Marshall的通信小站，2017 年 9 月 19 日。https://marshallcomm.cn/2017/09/19/polar-code-20-beta-expansion/。网页及本文转载图片采用 CC BY-NC-SA 4.0 许可。
- [2] G. He, J.-C. Belfiore, I. Land, G. Yang, X. Liu, Y. Chen, R. Li, J. Wang, Y. Ge, R. Zhang, and W. Tong, “Beta-Expansion: A Theoretical Framework for Fast and Recursive Construction of Polar Codes,” in Proc. 2017 IEEE Global Communications Conference (GLOBECOM), Singapore, pp. 1–6, Dec. 2017, doi: 10.1109/GLOCOM.2017.8254146.
- [3] C. Schürch, “A Partial Order for the Synthesized Channels of a Polar Code,” in Proc. 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, pp. 220–224, Jul. 2016, doi: 10.1109/ISIT.2016.7541293.
- [4] 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.
- [5] 3GPP, NR; Multiplexing and Channel Coding, TS 38.212, V17.9.0, Mar. 2023, §§5.3–5.4.