番外 C：PAC 码与 RM 构造：为什么这种速率剖面适合 PAC 码

在前面的文章中，Polar 码的信息位通常按照子信道可靠性来选择。这样的构造会使用 BEC、Bhattacharyya 参数、密度进化或高斯近似等信道相关方法。本篇讨论另一条思路：先用 Reed–Muller（RM）规则确定信息位和冻结位的位置，再在 Polar 变换前加入卷积预编码，形成 PAC 码。

这里最容易混淆的一点是：RM 构造和 PAC 码不是同一个概念。

RM 构造是一条选位规则，决定哪些位置承载信息、哪些位置固定为 0。
PAC 码是一种级联结构，在这条选位规则之后还要进行卷积预编码，最后进行 Polar 变换。

RM 规则之所以常和 PAC 码一起出现，是因为卷积预编码改变了编码序列的整体结构，单独根据 Polar 子信道的可靠性排序未必能反映这种变化。RM 速率剖面提供了一个与信道无关、但与 Polar 生成矩阵结构相适应的起点。它通常适合用来设计 PAC 码，但不能因此断言它对所有码长、码率和卷积多项式都最优。

PAC 码的基本编码链路

先固定本文的符号。码长为 $N=2^n$ ，消息向量长度为 $K$ ，码率为

R=\frac{K}{N}.

消息向量写作

\underline{m}_0^{K-1}=(m_0,m_1,\ldots,m_{K-1}),\qquad m_j\in\mathbb{F}_2.

PAC 码在 Polar 变换前增加了一步卷积预编码。这种“卷积预编码后接 Polar 变换”的构造由 Arıkan 提出，后续研究将其称为 polarization-adjusted convolutional（PAC）码 [2, 3]。整条链路可以写成

\underline{m}_0^{K-1}\xrightarrow{\text{速率剖面}}\underline{s}_0^{N-1}\xrightarrow{\text{卷积预编码}}\underline{u}_0^{N-1}\xrightarrow{\text{Polar变换}}\underline{c}_0^{N-1}.

其中：

$\underline{s}$ 是放置了消息比特和冻结比特的长度 $N$ 向量；
$\underline{u}$ 是卷积预编码后的 Polar 变换输入；
$\underline{c}$ 是最终发送的二元码字。

PAC码的编码链路：速率剖面、卷积预编码和Polar变换

图中的“码率配置”就是本文所说的速率剖面。它不改变向量长度，而是回答一个具体问题： $\underline{s}$ 的哪些位置放入消息比特，哪些位置固定为冻结比特。

设信息集合为 $\mathcal{A}$ ，冻结集合为

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

把消息向量依次放入 $\mathcal{A}$ 中的各个位置，并把其余位置置为 0，即

s_i=\begin{cases} m_j, & i=a_j,\quad \mathcal{A}=\{a_0<a_1<\cdots<a_{K-1}\},\\ 0, & i\in\mathcal{A}^c. \end{cases}

这里的冻结约束作用在 $\underline{s}$ 上，而不是直接作用在卷积预编码后的 $\underline{u}$ 上。这一点是理解 PAC 码的关键：即使 $s_i=0$ ，卷积预编码仍可能使 $u_i$ 等于 1，因为 $u_i$ 还受到前面若干个 $s$ 比特的影响。

卷积预编码到底做了什么

设卷积预编码器的记忆阶数为 $q$ ，系数为

g_0=1,\qquad g_1,g_2,\ldots,g_q\in\mathbb{F}_2.

约定 $s_t=0$ （当 $t<0$ 时），则卷积预编码的第 $i$ 位为

u_i=\bigoplus_{j=0}^{q}g_j s_{i-j},\qquad i\in[0,N-1].

由于 $g_0=1$ ，上式总是包含当前的 $s_i$ 。因此知道 $\underline{u}$ 和已经处理的较早位置，就可以逐步恢复 $\underline{s}$ 。这种一一对应的卷积变换不会改变信息比特数量，但会把一个消息比特的影响扩散到多个 Polar 输入位置。

以 $q=2$ 、 $(g_0,g_1,g_2)=(1,1,1)$ 为例：

u_i=s_i\oplus s_{i-1}\oplus s_{i-2}.

因此，卷积预编码的作用不是重新选择信息位，而是改变进入 Polar 变换的比特组合。PAC 码的性能来自两部分的配合：速率剖面选择了哪些位置传递自由信息，卷积预编码则在这些位置之间建立了额外的结构联系。

RM 构造为什么要看行重量

现在说明 RM 速率剖面从哪里来。采用本文系列约定的自然顺序生成矩阵

\mathbf{G}_N=\mathbf{F}_2^{\otimes n},\qquad \mathbf{F}_2=\begin{bmatrix}1&0\\1&1\end{bmatrix}.

第 $i$ 行记为 $\boldsymbol{\gamma}_i$ ，其汉明重量记为 $r(i)$ ：

r(i)=w_H(\boldsymbol{\gamma}_i).

这里有两个不同的汉明重量： $w_H(\boldsymbol{\gamma}_i)$ 统计矩阵第 $i$ 行中 1 的个数； $w_H(i)$ 统计整数 $i$ 写成二进制后包含多少个 1。

从 $N=2$ 开始

二阶核的两行重量分别为 1 和 2：

\mathbf{G}_2=\begin{bmatrix}1&0\\1&1\end{bmatrix},\qquad r(0)=1,\quad r(1)=2.

把矩阵扩大一倍时，Kronecker 结构满足

\mathbf{G}_{2N}=\begin{bmatrix}\mathbf{G}_N&\mathbf{0}\\ \mathbf{G}_N&\mathbf{G}_N\end{bmatrix}.

如果 $\boldsymbol{\gamma}_i$ 是 $\mathbf{G}_N$ 的第 $i$ 行，那么 $\mathbf{G}_{2N}$ 中对应的两行分别是

(\boldsymbol{\gamma}_i,\mathbf{0}),\qquad (\boldsymbol{\gamma}_i,\boldsymbol{\gamma}_i).

第一行的重量仍为 $r(i)$ ，第二行的重量变成 $2r(i)$ 。而 $i$ 变成 $N+i$ 时，二进制表示相当于多出一个 1。于是，每增加一个二进制位 1，行重量就翻倍；增加一个二进制位 0，行重量不变。

一般公式

将 $i$ 写成 $n$ 位二进制数

i=\sum_{t=0}^{n-1}b_t2^t,\qquad b_t\in\{0,1\}.

二进制重量为

w_H(i)=\sum_{t=0}^{n-1}b_t.

根据上面的递推，每一个 $b_t=1$ 都使行重量乘 2，每一个 $b_t=0$ 都不改变行重量。因此

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

这个公式只描述生成矩阵的结构，并没有使用接收信号、噪声方差或设计信噪比。RM 构造利用这个结构指标排列位置。用生成矩阵的行重量进行 Polar 与 RM 的比较，见 Arıkan 的相关研究 [1]。

RM 速率剖面如何产生

定义 RM 排序序列 $\boldsymbol{\pi}_{\mathrm{RM}}$ 时，本文采用以下明确规则：先按 $r(i)$ 降序排列；若行重量相同，再按索引 $i$ 升序排列。

r(\pi_0)\ge r(\pi_1)\ge\cdots\ge r(\pi_{N-1}).

并列时的索引升序只是确定性规则，不代表这些并列位置在所有信道上的实际可靠性完全相同。给定信息长度 $K$ ，取排序序列的前 $K$ 个位置组成信息集合：

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

这里说“前 $K$ 个”是针对已经定义好的有序序列 $\boldsymbol{\pi}_{\mathrm{RM}}$ ，不是把无序集合直接进行截取。

需要特别强调：RM 规则本身不是一个额外的编码变换。在 PAC 码中，它只负责生成 $\mathcal{A}$ 和 $\mathcal{A}^c$ ；真正的编码仍然由卷积预编码和 Polar 变换完成。

$N=8$ 时完整生成 RM 速率剖面

取 $N=8$ ，所以每个索引写成 3 位二进制数。由 $r(i)=2^{w_H(i)}$ 得到：

索引 $i$	3 位二进制表示	$w_H(i)$	行重量 $r(i)$
0	000	0	1
1	001	1	2
2	010	1	2
3	011	2	4
4	100	1	2
5	101	2	4
6	110	2	4
7	111	3	8

按行重量降序、并列索引升序排列：

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

例如取 $K=4$ ，则

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

这一步只得到位置配置，还没有进行卷积预编码，也没有生成码字。

用一个 PAC 例子走完三步编码

仍取 $N=8$ 、 $K=4$ ，并取消息向量

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

第一步：按照 RM 速率剖面放置消息向量

信息集合按索引升序写成 $(3,5,6,7)$ 。因此

s_3=m_0=1,\quad s_5=m_1=0,\quad s_6=m_2=1,\quad s_7=m_3=1.

冻结位置 $0,1,2,4$ 全部置 0，得到

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

第二步：进行卷积预编码

取

u_i=s_i\oplus s_{i-1}\oplus s_{i-2},

并规定负索引位置的 $s$ 为 0。逐位计算如下：

\begin{aligned} u_0&=s_0=0,\\ u_1&=s_1\oplus s_0=0,\\ u_2&=s_2\oplus s_1\oplus s_0=0,\\ u_3&=s_3\oplus s_2\oplus s_1=1,\\ u_4&=s_4\oplus s_3\oplus s_2=1,\\ u_5&=s_5\oplus s_4\oplus s_3=1,\\ u_6&=s_6\oplus s_5\oplus s_4=1,\\ u_7&=s_7\oplus s_6\oplus s_5=0. \end{aligned}

所以

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

注意 $s_4=0$ ，但 $u_4=1$ 。这不是冻结约束失效，而是卷积预编码的预期结果：冻结约束施加在 $s_4$ ，而 $u_4$ 还包含 $s_3$ 的影响。

第三步：进行 Polar 变换

采用自然顺序生成矩阵

\mathbf{G}_8=\begin{bmatrix} 1&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0\\ 1&0&1&0&0&0&0&0\\ 1&1&1&1&0&0&0&0\\ 1&0&0&0&1&0&0&0\\ 1&1&0&0&1&1&0&0\\ 1&0&1&0&1&0&1&0\\ 1&1&1&1&1&1&1&1 \end{bmatrix}.

最终码字由

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

给出。由于 $u_3=u_4=u_5=u_6=1$ ，所以这是第 3、4、5、6 行的逐位模 2 相加：

\begin{aligned} \underline{c}_0^7 &=\boldsymbol{\gamma}_3\oplus\boldsymbol{\gamma}_4\oplus\boldsymbol{\gamma}_5\oplus\boldsymbol{\gamma}_6\\ &=(0,0,0,1,1,1,1,0). \end{aligned}

这个例子中的 $\underline{c}$ 恰好与 $\underline{u}$ 相同，是这组比特取值造成的偶然结果，不能把它当作 PAC 变换的一般性质。一般情况下，卷积预编码会改变 $\underline{u}$ ，Polar 变换还会进一步改变码字。

从这个例子可以清楚地区分三种向量：

$\underline{s}$ 决定消息比特和冻结比特的位置；
$\underline{u}$ 是卷积预编码后的 Polar 输入；
$\underline{c}$ 是发送给信道的码字。

RM 速率剖面与 PAC 码的关系

PAC 论文中速率剖面的角色

Arıkan 提出 PAC 码时，将卷积预编码放在 Polar 变换之前，并强调需要采用合适的速率剖面 [2]。Yao、Fazeli 和 Vardy 也把 PAC 描述为“卷积预编码与 Polar 变换的组合”，并指出速率剖面是这一构造的重要组成部分 [4]。Sun、Viterbo 和 Liu 的论文明确把 RM 设计称为 PAC 最初提出的速率剖面设计，并把它作为后续优化方法的比较对象 [5]。

RM 规则还有一个明确的数学特点：它只根据 Polar 生成矩阵的行重量选位，不依赖某个具体信道的设计信噪比。本文前面已经从 Kronecker 结构推导了这一点。这里需要注意，这个特点只能说明 RM 是一种固定的结构性选位规则，不能单独推出它对 PAC 码性能最优。

RM、Polar 构造与 PAC 的关系

下面把三者放在一起比较：

对象	选位依据	是否使用卷积预编码	主要特点
Polar 的 BEC/Bhattacharyya 构造	合成子信道的擦除概率或 Bhattacharyya 参数	否	依赖信道模型，适合理论分析和 BEC 构造
Polar 的 GA/DE 构造	合成子信道的 LLR 均值或分布	否	能反映 AWGN 等具体信道，但需要设计参数
PAC 的 RM 速率剖面	$\mathbf{G}_N$ 行重量或索引二进制重量	是	PAC 研究中最初采用的速率剖面之一

因此，不能把 RM 排序直接称为“Polar 码的可靠性排序”。它首先是一条结构排序；在 PAC 码中，它作为速率剖面与卷积预编码共同工作。若比较不同方案，应固定 $N$ 、 $K$ 、信道、译码器和列表最大宽度 $L_{\max}$ ，只改变速率剖面，才能知道性能差异究竟来自选位还是其它因素。

使用 RM 速率剖面时的三个检查

第一，确认生成矩阵约定一致。本文使用 $\mathbf{G}_N=\mathbf{F}_2^{\otimes n}$ 的自然顺序。如果编码器采用了额外的比特反转排列，必须同步说明 RM 索引是否也随之改变。

第二，确认冻结约束作用在正确的向量上。PAC 码中应先在 $\underline{s}$ 中放置信息和冻结比特，再计算 $\underline{u}$ 。不能把 RM 选出的信息位置直接当成 $\underline{u}$ 中的冻结位置，否则会把卷积预编码前后的两个层次混为一谈。

第三，确认译码器使用同一套速率剖面和卷积系数。编码器和译码器只要有一处不一致，译码器所搜索的就不再是发送端生成的 PAC 码集合。

小结

RM 构造在本文中不是一个独立于 PAC 的“第二种 Polar 编码器”，而是一条用于生成速率剖面的选位规则。对自然顺序的 Polar 生成矩阵，Kronecker 结构给出

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

因此可以按行重量降序排列索引，并用排序结果确定 $\mathcal{A}$ 和 $\mathcal{A}^c$ 。PAC 码再把这个速率剖面与卷积预编码、Polar 变换结合起来。

RM 规则特别适合用作 PAC 码的结构化起点，但它不等于对所有 Polar 码或所有 PAC 参数都最优。Polar 构造更强调具体信道下的子信道可靠性；PAC 码构造则必须同时考虑速率剖面和卷积预编码的联合效果。

参考

E. Arıkan, “A performance comparison of polar codes and Reed-Muller codes,” IEEE Communications Letters, vol. 12, no. 6, pp. 447–449, Jun. 2008, doi: 10.1109/LCOMM.2008.080017.
E. Arıkan, “From sequential decoding to channel polarization and back again,” arXiv preprint arXiv:1908.09594, Aug. 26, 2019. [Online]. Available: https://arxiv.org/abs/1908.09594
M. Rowshan, A. Burg, and E. Viterbo, “Polarization-adjusted convolutional (PAC) codes: Sequential decoding vs list decoding,” IEEE Transactions on Vehicular Technology, vol. 70, no. 2, pp. 1434–1447, Feb. 2021, doi: 10.1109/TVT.2021.3052550.
H. Yao, A. Fazeli, and A. Vardy, “List decoding of Arıkan’s PAC codes,” in Proceedings of the 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA, Jun. 2020, pp. 443–448, doi: 10.1109/ISIT44484.2020.9174118.
H. Sun, E. Viterbo, and R. Liu, “Optimized rate-profiling for PAC codes,” arXiv preprint arXiv:2106.04074, Jun. 8, 2021. [Online]. Available: https://arxiv.org/abs/2106.04074