从二阶核F到生成矩阵：Polar编码蝶形图怎么来的
前两篇文章里，我们先建立了 Polar 码的大图景，又补齐了 B-DMC、码率、容量和 LLR 这些预备概念。从这一篇开始，正式看 Polar 编码本身：给定一个长度为 N 的极化输入向量 \underline{u}_0^{N-1}，怎样得到发送前的二元码字向量 \underline{c}_0^{N-1}。
这篇只讨论编码结构，不讨论哪些位置放信息、哪些位置冻结。也就是说，本文先回答：
- 二阶核 \mathbf{F}_2 到底在做什么。
- \mathbf{G}_N 为什么可以由 Kronecker 幂构造。
- 为什么有的资料写 \mathbf{F}_2^{\otimes n}，有的资料写 \mathbf{B}_N\mathbf{F}_2^{\otimes n}。
- 生成矩阵和蝶形图之间怎样一一对应。
本文统一使用 0-based 索引，所有比特运算都在二元域 \mathbb{F}_2=\{0,1\} 上进行。异或写作 \oplus。编码向量采用行向量约定：
\underline{c}_0^{N-1}=\underline{u}_0^{N-1}\mathbf{G}_N其中 N=2^n 是码长，\underline{u}_0^{N-1}\in\mathbb{F}_2^N 是极化输入向量，\underline{c}_0^{N-1}\in\mathbb{F}_2^N 是编码后的二元码字向量，\mathbf{G}_N 是本文要讲清楚的生成矩阵。
为什么从一个 2×2 核开始
Polar 编码最小的变换来自极化二阶核：
\mathbf{F}_2= \begin{bmatrix} 1 & 0\\ 1 & 1 \end{bmatrix}把长度为 2 的行向量 (u_0,u_1) 右乘这个矩阵，得到：
(c_0,c_1)=(u_0,u_1)\mathbf{F}_2=(u_0\oplus u_1,\ u_1)这就是 Polar 编码的最小单元。第一个输出 c_0 同时依赖 u_0 和 u_1，第二个输出 c_1 保留 u_1。如果只看编码结构，这个核做的事情可以说是“耦合”：它用一次异或把两个输入比特混在一起。
这里先不要把它和后面信道极化里的 channel combining / channel splitting 混成一件事。本文讲的是编码端的矩阵和蝶形结构；第 5 篇再从信道角度正式讲 combining 和 splitting。
如果把这个最小单元写成“文字版蝶形图”，可以看成下面两条输出线：
\begin{array}{ccc} u_0 & \longrightarrow & c_0=u_0\oplus u_1\\ u_1 & \longrightarrow & c_1=u_1 \end{array}这两条线里，只有 u_1 会向上参与一次异或；这就是二阶核里最小的耦合关系。上面的“文字版蝶形图”和矩阵乘法是同一个关系：
c_0=u_0\oplus u_1,\qquad c_1=u_1如果把 \mathbf{F}_2 换成单位矩阵，两个输入比特不会发生这种耦合，也就失去了 Polar 编码后面能够形成递归结构的基础。
从 \mathbf{F}_2 到 Kronecker 幂
码长为 N=2^n 时，最直接的生成矩阵来自 Kronecker 幂：
\mathbf{G}_N^{\mathrm{nat}}=\mathbf{F}_2^{\otimes n}这里上标 \mathrm{nat} 表示 natural order，也就是暂时不加入 bit-reversal 的自然顺序写法。Kronecker 幂的递推定义是：
\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}, \qquad \mathbf{F}_2^{\otimes 1}=\mathbf{F}_2这条式子非常重要。它说明长码的生成矩阵不是凭空写出来的，而是把两个更短的生成矩阵按块拼起来：左下角多出来的一块 \mathbf{F}_2^{\otimes(n-1)}，正是“下半部分输入也会影响上半部分输出”的来源。
对 N=4，也就是 n=2，有：
\mathbf{G}_4^{\mathrm{nat}} =\mathbf{F}_2^{\otimes 2} = \begin{bmatrix} 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 1 & 1 & 1 & 1 \end{bmatrix}于是：
\underline{c}_0^3 =\underline{u}_0^3\mathbf{G}_4^{\mathrm{nat}}逐位展开就是：
\begin{aligned} c_0&=u_0\oplus u_1\oplus u_2\oplus u_3,\\ c_1&=u_1\oplus u_3,\\ c_2&=u_2\oplus u_3,\\ c_3&=u_3. \end{aligned}这就是 N=4 的最小完整编码例子。它已经包含了 Polar 编码的两个关键特征：递归结构和蝶形异或网络。
N=4 的蝶形图怎么对应矩阵
直接做矩阵乘法当然可以得到 \underline{c}_0^3，但 Polar 编码通常不会真的存一个完整的 \mathbf{G}_N 再相乘。原因是 \mathbf{G}_N 很有结构，可以用类似 FFT 的蝶形网络完成同样的运算。
对 N=4，自然顺序下的蝶形结构可以直接写成两层变量更新。
第一层在相邻 pair 内做二阶核：
(u_0,u_1)\mapsto (u_0\oplus u_1,\ u_1), \qquad (u_2,u_3)\mapsto (u_2\oplus u_3,\ u_3)记第一层输出为 \underline{a}_0^3，则：
a_0=u_0\oplus u_1,\quad a_1=u_1,\quad a_2=u_2\oplus u_3,\quad a_3=u_3第二层把两个长度为 2 的部分再耦合起来：
c_0=a_0\oplus a_2,\qquad c_1=a_1\oplus a_3,\qquad c_2=a_2,\qquad c_3=a_3把这两层合在一起，就是下面这个“公式版蝶形图”：
\begin{array}{ccccc} u_0 & \longrightarrow & a_0=u_0\oplus u_1 & \longrightarrow & c_0=a_0\oplus a_2\\ u_1 & \longrightarrow & a_1=u_1 & \longrightarrow & c_1=a_1\oplus a_3\\ u_2 & \longrightarrow & a_2=u_2\oplus u_3 & \longrightarrow & c_2=a_2\\ u_3 & \longrightarrow & a_3=u_3 & \longrightarrow & c_3=a_3 \end{array}代回去，就正好得到前面矩阵乘法展开出来的四条式子：
c_0=u_0\oplus u_1\oplus u_2\oplus u_3,\quad c_1=u_1\oplus u_3,\quad c_2=u_2\oplus u_3,\quad c_3=u_3所以蝶形图不是另一种编码定义，而是 \underline{u}_0^{N-1}\mathbf{G}_N 的快速实现方式。矩阵告诉你“谁影响谁”，蝶形图告诉你“怎样用分层异或高效算出来”。
生成矩阵的两种常见形式
初学 Polar 码时，一个很容易混乱的点是：不同资料里的生成矩阵不总是长得一模一样。最常见的是下面两种。
| 写法 | 本系列中的记号 | 含义 |
|---|---|---|
| 自然顺序 | \mathbf{G}_N^{\mathrm{nat}}=\mathbf{F}_2^{\otimes n} | 先忽略 bit-reversal，直接使用 Kronecker 幂 |
| bit-reversal 顺序 | \mathbf{G}_N^{\mathrm{br}}=\mathbf{B}_N\mathbf{F}_2^{\otimes n} | 先按 bit-reversal 重排输入索引，再进入同一个 Kronecker 蝶形核心 |
这里 \mathbf{B}_N 是 bit-reversal 置换矩阵。本文采用行向量约定，所以 \mathbf{B}_N 写在 \mathbf{F}_2^{\otimes n} 左侧：
\underline{c}_0^{N-1} =\underline{u}_0^{N-1}\mathbf{B}_N\mathbf{F}_2^{\otimes n}如果某本书或某篇论文采用列向量约定，置换矩阵可能出现在另一侧。遇到这种差异时，先看清楚它的向量是行向量还是列向量，不要只盯着矩阵符号本身。
对 N=4，bit-reversal 把索引二进制反转。两位二进制索引的反转关系是：
| 原索引 i | 二进制 | 反转后 |
|---|---|---|
| 0 | 00 | 0 |
| 1 | 01 | 2 |
| 2 | 10 | 1 |
| 3 | 11 | 3 |
在本文的行向量写法下，可以定义：
(\underline{u}_0^3\mathbf{B}_4)_0^3=(u_0,u_2,u_1,u_3)对应的置换矩阵可以写为：
\mathbf{B}_4= \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 \end{bmatrix}因此：
\mathbf{G}_4^{\mathrm{br}} =\mathbf{B}_4\mathbf{F}_2^{\otimes 2} = \begin{bmatrix} 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 0\\ 1 & 1 & 1 & 1 \end{bmatrix}这和 \mathbf{G}_4^{\mathrm{nat}} 不是同一个矩阵。差别不在二阶核本身，而在进入蝶形网络之前，输入索引有没有先做 bit-reversal。
bit-reversal 和蝶形图的对应关系
从结构上看，bit-reversal 形式可以理解为：先做一个输入重排，再进入和自然顺序相同的 Kronecker 核心。
这个对应关系可以直接写成：
\underline{u}_0^3 \xrightarrow{\ \mathbf{B}_4\ } (u_0,u_2,u_1,u_3) \xrightarrow{\ \mathbf{F}_2^{\otimes 2}\ } \underline{c}_0^3有些资料或图示会把这个重排模块写成 R_N，也有资料写成 B_N。本系列公开文章统一把 bit-reversal 矩阵写作 \mathbf{B}_N。如果图中出现 R_N，可以把它理解为“重排模块”的图形标注，而不是新的编码核心。
对 N=4，bit-reversal 约定下等价于先把输入顺序变成：
(u_0,u_1,u_2,u_3)\mathbf{B}_4=(u_0,u_2,u_1,u_3)然后对这个新顺序运行自然顺序蝶形。于是输出变为：
\begin{aligned} c_0&=u_0\oplus u_1\oplus u_2\oplus u_3,\\ c_1&=u_2\oplus u_3,\\ c_2&=u_1\oplus u_3,\\ c_3&=u_3. \end{aligned}和自然顺序相比，c_1 与 c_2 的表达式交换了位置。这不是错误，而是索引约定不同导致的结果。
这个差异在短例子里看起来只是两个位置互换，但后面涉及信息位集合 \mathcal{A}、可靠性序列 \boldsymbol{\pi}、译码顺序和工程实现时，就不能随便忽略。只要一篇文章第一次出现 \mathbf{G}_N，就应该明确采用哪一种约定。
本系列后续默认采用下面的写法：
- 如果文章不讨论 bit-reversal 细节，优先写 \mathbf{G}_N=\mathbf{F}_2^{\otimes n}，把注意力放在核心递归结构上。
- 如果文章需要讨论 bit-reversal，则显式写 \mathbf{G}_N^{\mathrm{br}}=\mathbf{B}_N\mathbf{F}_2^{\otimes n}，并说明输入索引如何重排。
- 不把两种 \mathbf{G}_N 写法混在同一段推导里。
一般 N 的蝶形结构
当 N=2^n 时，\mathbf{F}_2^{\otimes n} 对应 n 层蝶形异或。自然顺序下可以这样理解：
- 第 1 层：每隔 2 个位置做一次长度为 2 的核。
- 第 2 层：每隔 4 个位置，把两个长度为 2 的部分耦合。
- 第 3 层：每隔 8 个位置，把两个长度为 4 的部分耦合。
- 继续下去，直到长度为 N 的整体被耦合完成。
每一层只做异或和连线，所以总复杂度是：
O(N\log N)这也是 Polar 编码很适合实现的原因之一：它的生成矩阵虽然是 N\times N，但真正编码时不需要做普通矩阵乘法。只要按照蝶形图逐层更新，就可以完成同样的线性变换。
更形式化地说，蝶形图是在执行同一个矩阵乘法：
\underline{c}_0^{N-1}=\underline{u}_0^{N-1}\mathbf{F}_2^{\otimes n}如果采用 bit-reversal 约定，则只是多了输入重排：
\underline{c}_0^{N-1}=\underline{u}_0^{N-1}\mathbf{B}_N\mathbf{F}_2^{\otimes n}因此看 Polar 编码图时，不要把“矩阵形式”和“蝶形形式”当成两套理论。它们描述的是同一个线性编码器：矩阵形式适合推导，蝶形形式适合实现。
容易混淆的几个点
第一，不要把普通加法和二元域加法混在一起。本文所有比特之间的相加都写成 \oplus，表示 mod 2 加法。
第二，不要把 \underline{c} 和 \underline{x} 混用。本文的 \underline{c}_0^{N-1} 是二元码字向量；如果后面进入 BPSK 调制，才会用 \underline{x}_0^{N-1} 表示实数发送符号。
第三，不要把 \mathbf{G}_N^{\mathrm{nat}} 和 \mathbf{G}_N^{\mathrm{br}} 当成完全相同的矩阵。它们共享同一个二阶核和蝶形核心，但输入索引约定不同。
第四，不要把编码端的“耦合”提前等同于信道端的“分裂”。二阶核把输入比特耦合起来；信道 combining / splitting 是下一阶段从接收观测和逐位判决角度定义的东西。
小结
这一篇把 Polar 编码的结构根基搭起来了。
最小单元是二阶核 \mathbf{F}_2，它把 (u_0,u_1) 变成 (u_0\oplus u_1,u_1)。把这个核做 Kronecker 幂，就得到自然顺序生成矩阵 \mathbf{G}_N^{\mathrm{nat}}=\mathbf{F}_2^{\otimes n}。如果采用 Arikan 原始论文里常见的 bit-reversal 约定，在本文行向量写法下则写作 \mathbf{G}_N^{\mathrm{br}}=\mathbf{B}_N\mathbf{F}_2^{\otimes n}。
矩阵形式和蝶形图不是两套东西。矩阵形式说明线性变换是什么，蝶形图说明怎样用 O(N\log N) 次结构化异或把它算出来。
下一篇我们会把这些符号真正放进一个完整的短码长例子里：给定 N、K、信息位和冻结位，手算一遍 Polar 编码全过程。
参考
- E. Arikan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” IEEE Trans. Inf. Theory, vol. 55, no. 7, pp. 3051-3073, Jul. 2009, doi: 10.1109/TIT.2009.2021379.