N=8与N=16的Polar编码完整算例

上一篇我们已经知道，Polar 编码可以写成一个线性变换：

\underline{c}_0^{N-1}=\underline{u}_0^{N-1}\mathbf{G}_N

其中 $\underline{u}_0^{N-1}$ 是进入极化变换之前的输入向量， $\underline{c}_0^{N-1}$ 是编码后的二元码字向量，所有运算都在二元域 $\mathbb{F}_2=\{0,1\}$ 上进行，加法统一写作 $\oplus$ 。

这一篇不再只看矩阵长什么样，而是完整走两遍编码流程：

第一个例子使用 $N=8,K=4$ ，适合手算每一步。
第二个例子使用 $N=16,K=8$ ，用来观察同样结构如何扩展。

注意，本文只讲编码过程，不讲“哪些位置最可靠”。信息位集合 $\mathcal{A}$ 在这里是为了演示而显式指定的。真正根据信道可靠性选择 $\mathcal{A}$ 的问题，会在后面的构造篇里单独展开。

另外，本文输出统一写作 $\underline{c}$ 。有些资料会把编码输出也写成 $\underline{x}$ ，但本系列把 $\underline{x}$ 留给 BPSK 调制后的实数发送符号。也就是说，先有二元码字 $c_i$ ，再有调制符号 $x_i=1-2c_i$ 。

本文采用的生成矩阵约定

为了让手算过程尽量清楚，本文采用自然顺序生成矩阵：

\mathbf{G}_N^{\mathrm{nat}}=\mathbf{F}_2^{\otimes n},\qquad N=2^n

因此编码公式写作：

\underline{c}_0^{N-1} = \underline{u}_0^{N-1}\mathbf{G}_N^{\mathrm{nat}}

也就是说，本文暂时不在编码前加入 bit-reversal 矩阵 $\mathbf{B}_N$ 。如果采用上一篇提到的 bit-reversal 约定，则应写作 $\mathbf{G}_N^{\mathrm{br}}=\mathbf{B}_N\mathbf{F}_2^{\otimes n}$ ，并且要先说明输入索引如何重排。

重点是：bit-reversal 是进入普通蝶形核心之前的输入重排，不是额外的异或计算层。图中的 $\underline{v}$ 表示重排后的输入顺序，随后才进入 $\mathbf{F}_2^{\otimes 3}$ 对应的普通蝶形网络。

自然顺序的好处是，它和下面的分层蝶形更新可以直接对应：

先在每个长度为 2 的小块里做一次二阶核。
再在每个长度为 4 的块里把两个长度为 2 的部分耦合。
继续扩大块长，直到整个长度 $N$ 被耦合完成。

这种写法的核心更新规则很简单：每一层把块的上半部分和下半部分逐位异或，上半部分被更新，下半部分保持不变。

N=8：先确定码长、码率、信息位和冻结位

先看一个最适合手算的例子。取：

N=8,\qquad n=3,\qquad K=4,\qquad R=\frac{K}{N}=\frac{1}{2}

本文指定信息位集合为：

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

冻结集合是相对于全集 $[0,7]$ 的补集：

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

这里再次强调： $\mathcal{A}$ 不是本文推导出来的最优集合，而是为了把编码流程演示完整而先指定的集合。后面讲构造时，我们才会讨论如何根据子信道可靠性排序序列 $\boldsymbol{\pi}$ 选择 $\mathcal{A}$ 。

令信息向量为：

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

按照集合 $\mathcal{A}$ 的升序把信息比特放入对应位置：

信息位索引	放入的比特
$3$	$m_0=1$
$5$	$m_1=0$
$6$	$m_2=1$
$7$	$m_3=1$

冻结位统一置 0：

u_i=0,\qquad i\in\mathcal{A}^c

于是极化输入向量为：

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

这个向量就是编码器真正接收的输入。它不是原始信息向量本身，而是把信息位和冻结位放到长度 $N$ 的极化输入位置之后得到的向量。

用生成矩阵算出 N=8 码字

对 $N=8$ ，自然顺序生成矩阵是：

\mathbf{G}_8^{\mathrm{nat}} = \mathbf{F}_2^{\otimes 3} = \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 = (0,0,0,1,0,0,1,1)\mathbf{G}_8^{\mathrm{nat}}

因为只有 $u_3,u_6,u_7$ 为 1，且 $u_5=0$ ，所以可以把矩阵乘法理解为选出第 3、6、7 行做异或。为了避免和 SC 译码里的 $g(\cdot)$ 函数混淆，本文把 $\mathbf{G}_8^{\mathrm{nat}}$ 的第 $i$ 行写作 $\boldsymbol{\gamma}_i$ ，于是：

\underline{c}_0^7 = \boldsymbol{\gamma}_3\oplus\boldsymbol{\gamma}_6\oplus\boldsymbol{\gamma}_7

逐行写出来就是：

\begin{aligned} \boldsymbol{\gamma}_3&=(1,1,1,1,0,0,0,0),\\ \boldsymbol{\gamma}_6&=(1,0,1,0,1,0,1,0),\\ \boldsymbol{\gamma}_7&=(1,1,1,1,1,1,1,1). \end{aligned}

三行异或后得到：

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

这就是本例的二元码字。它的每一位仍然属于 $\mathbb{F}_2$ ，还没有进入调制环节。

用蝶形结构重做一次 N=8 编码

直接矩阵相乘虽然清楚，但工程实现不会真的存一个 $8\times 8$ 矩阵再相乘。下面用蝶形结构重做一次同样的编码。

N=8 Polar 编码蝶形图与本文算例取值

图 1 把本文 $N=8$ 例子的输入、三层蝶形结构和输出放在同一张图里。每一个 $\oplus$ 表示一次二元域异或，黑点表示该位置的比特被向上送入异或节点。

从初始向量开始：

\underline{a}^{(0)}=(0,0,0,1,0,0,1,1)

第 1 层在每个长度为 2 的块里做二阶核：

\underline{a}^{(1)}=(0,0,1,1,0,0,0,1)

第 2 层在每个长度为 4 的块里耦合上下两半：

\underline{a}^{(2)}=(1,1,1,1,0,1,0,1)

第 3 层把整个长度为 8 的块耦合完成：

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

所以：

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

和前面生成矩阵得到的结果完全一致。

把三层更新整理成表格：

阶段	向量
初始 $\underline{a}^{(0)}$	$(0,0,0,1,0,0,1,1)$
长度 2 核后 $\underline{a}^{(1)}$	$(0,0,1,1,0,0,0,1)$
长度 4 耦合后 $\underline{a}^{(2)}$	$(1,1,1,1,0,1,0,1)$
长度 8 耦合后 $\underline{a}^{(3)}$	$(1,0,1,0,0,1,0,1)$

这一张表已经很接近程序里的实现过程：每一层只做若干个异或，最终原地把 $\underline{u}$ 变成 $\underline{c}$ 。

N=16：同一套流程如何扩展

再看一个稍微大一点的例子。取：

N=16,\qquad n=4,\qquad K=8,\qquad R=\frac{1}{2}

为了演示，指定信息位集合为：

\mathcal{A}=\{7,9,10,11,12,13,14,15\}

冻结集合是相对于全集 $[0,15]$ 的补集：

\mathcal{A}^c=[0,15]\setminus\mathcal{A} =\{0,1,2,3,4,5,6,8\}

取信息向量：

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

仍然按照 $\mathcal{A}$ 的升序放入信息比特：

信息位索引	放入的比特
$7$	$m_0=1$
$9$	$m_1=0$
$10$	$m_2=1$
$11$	$m_3=1$
$12$	$m_4=0$
$13$	$m_5=1$
$14$	$m_6=0$
$15$	$m_7=1$

冻结位仍然置 0，于是：

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

如果直接写 $\mathbf{G}_{16}^{\mathrm{nat}}$ ，矩阵会变成 $16\times16$ ，可读性反而变差。这里直接使用蝶形结构，因为它更能说明规模扩展时发生了什么。

N=16 Polar 编码四层蝶形结构示意

图 2 只强调结构扩展： $N=16=2^4$ 时，蝶形网络从 $N=8$ 的三层变成四层，对应块长 $2,4,8,16$ 。具体取值仍按下面的阶段向量逐步更新。

初始阶段：

\underline{a}^{(0)} = (0,0,0,0,0,0,0,1,0,0,1,1,0,1,0,1)

第 1 层，块长 2：

\underline{a}^{(1)} = (0,0,0,0,0,0,1,1,0,0,0,1,1,1,1,1)

第 2 层，块长 4：

\underline{a}^{(2)} = (0,0,0,0,1,1,1,1,0,1,0,1,0,0,1,1)

第 3 层，块长 8：

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

第 4 层，块长 16：

\underline{a}^{(4)} = (1,0,0,1,1,1,0,0,0,1,1,0,0,0,1,1)

因此 $N=16$ 例子的编码结果是：

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

可以看到，从 $N=8$ 到 $N=16$ ，规则没有变，只是蝶形层数从 3 层变成 4 层。一般地， $N=2^n$ 时共有 $n=\log_2 N$ 层。

为什么矩阵写法和蝶形写法等价

这两个例子里，我们用了两种视角：

矩阵写法： $\underline{c}_0^{N-1}=\underline{u}_0^{N-1}\mathbf{G}_N^{\mathrm{nat}}$ 。
蝶形写法：把 $\underline{u}_0^{N-1}$ 按层做原地异或更新。

它们等价的原因在上一篇已经出现过： $\mathbf{F}_2^{\otimes n}$ 本身就是递归块矩阵。

\mathbf{F}_2^{\otimes n} = \begin{bmatrix} \mathbf{F}_2^{\otimes(n-1)} & \mathbf{0}\\ \mathbf{F}_2^{\otimes(n-1)} & \mathbf{F}_2^{\otimes(n-1)} \end{bmatrix}

这个块结构对应到向量更新时，就是“上半部分异或下半部分，下半部分保留”。不断递归下去，就得到一层一层的蝶形网络。

所以矩阵形式适合回答：

哪些输入位会影响某个码字位？
生成矩阵的行、列和线性关系是什么？
如何证明编码是线性变换？

蝶形形式适合回答：

编码器实际怎样计算？
为什么复杂度是 $O(N\log N)$ 而不是 $O(N^2)$ ？
如何写一个最小可运行的 Polar 编码器？

两种写法不是互相替代，而是从推导和实现两个角度描述同一个对象。

最小 Polar 编码器的 C++ 设计思路

本文的编码器只做一件事：输入已经填好冻结位和信息位的 $\underline{u}_0^{N-1}$ ，输出二元码字 $\underline{c}_0^{N-1}$ 。

也就是说，它不负责选择 $\mathcal{A}$ ，不负责计算可靠性排序 $\boldsymbol{\pi}$ ，也不负责 CRC、调制、信道或译码。那些模块会在后面的文章里逐步加入。

核心过程可以写成下面这样：

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

std::vector<int> polar_encode(std::vector<int> u) {
    const std::size_t N = u.size();

    if (N == 0 || (N & (N - 1)) != 0) {
        throw std::invalid_argument("N must be a power of two");
    } // if

    for (std::size_t step = 1; step < N; step <<= 1) {
        for (std::size_t base = 0; base < N; base += 2 * step) {
            for (std::size_t j = 0; j < step; ++j) {
                u[base + j] ^= u[base + j + step];
            } // for j
        } // for base
    } // for step

    return u;
} // polar_encode

这段代码正对应本文的蝶形表格：

step = 1 对应长度 2 的核。
step = 2 对应长度 4 的耦合。
step = 4 对应长度 8 的耦合。
继续下去，直到 step = N / 2。

如果输入：

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

输出就是：

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

如果输入：

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

输出就是：

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

这就是最小 Polar 编码器的骨架。后续如果要把它扩展成更完整的工程模块，通常会在它前面加一个“构造和填充输入向量”的步骤：

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

其中第一步负责根据 $\mathcal{A}$ 和 $\mathcal{A}^c$ 放置信息位与冻结位，第二步才是本文讨论的极化变换。

容易混淆的几个点

第一， $\mathcal{A}$ 是信息位集合，不是一个有序数组。本文在把 $\underline{m}$ 放入 $\underline{u}$ 时，明确说明了“按照 $\mathcal{A}$ 的升序”。如果以后要按照可靠性顺序处理，应该另外使用可靠性排序序列 $\boldsymbol{\pi}$ 。

第二，本文的 $\mathcal{A}$ 只是演示用集合，不代表已经完成 Polar 构造。真正的构造问题是：在给定信道、码长和码率下，哪些子信道更适合承载信息。这个问题会在第 8 篇到第 10 篇逐步展开。

第三，本文采用自然顺序 $\mathbf{G}_N^{\mathrm{nat}}=\mathbf{F}_2^{\otimes n}$ 。如果某个实现采用 bit-reversal 约定，输入进入蝶形网络之前需要重排，不能直接拿本文的中间向量逐项对比。

第四，不要把 $\underline{c}$ 和 $\underline{x}$ 混用。本文得到的是二元码字 $\underline{c}$ 。只有进入 BPSK 调制时，才会进一步写 $x_i=1-2c_i$ 。

第五，所有异或都发生在 $\mathbb{F}_2$ 上。这里没有普通整数加法，表达式中的 $\oplus$ 都表示 mod 2 加法。

小结

这一篇把 Polar 编码完整算了两遍。

对 $N=8,K=4$ ，我们指定 $\mathcal{A}=\{3,5,6,7\}$ ，把 $\underline{m}_0^3=(1,0,1,1)$ 放入极化输入向量，得到：

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

再经过 $\mathbf{G}_8^{\mathrm{nat}}$ 或等价的三层蝶形更新，得到：

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

对 $N=16,K=8$ ，我们使用同一套规则，只是层数增加到 4 层，最终得到：

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

到这里，编码端的基本流程已经走通：先根据 $\mathcal{A}$ 和 $\mathcal{A}^c$ 形成 $\underline{u}$ ，再用 $\mathbf{F}_2^{\otimes n}$ 的蝶形结构得到 $\underline{c}$ 。

下一篇开始，我们会把视角从“编码器怎样算”转到“为什么这种结构会让信道产生好坏分化”。也就是正式进入 Polar 码最核心的概念：信道极化。

参考

E. Arikan, “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.