探秘基带算法：从原理到5G时代的通信变革【四】Polar 编解码（二）

本博客为系列博客，主要讲解各基带算法的原理与应用，包括：viterbi解码、Turbo编解码、Polar编解码、CORDIC算法、CRC校验、FFT/DFT、QAMtiaozhi/解调、QPSK调制/解调。其他博客链接如下：

1. 探秘基带算法：从原理到5G时代的通信变革【一】引言
2. 探秘基带算法：从原理到5G时代的通信变革【二】Viterbi解码
3. 探秘基带算法：从原理到5G时代的通信变革【三】Turbo 编解码
4. 探秘基带算法：从原理到5G时代的通信变革【四】Polar 编解码（一）
5. 探秘基带算法：从原理到5G时代的通信变革【四】Polar 编解码（二）
6. 探秘基带算法：从原理到5G时代的通信变革【五】CORDIC算法
7. 探秘基带算法：从原理到5G时代的通信变革【六】CRC 校验
8. 探秘基带算法：从原理到5G时代的通信变革【七】FFT/DFT
9. 探秘基带算法：从原理到5G时代的通信变革【八】QAM 调制 / 解调
10. 探秘基带算法：从原理到5G时代的通信变革【九】QPSK调制/解调
11. 探秘基带算法：从原理到5G时代的通信变革【十】基带算法应用与对比

2.3.3 极化编码

极化编码（Polar Code）是一种由Erdal Arikan在2009年提出的新型信道编码方法，其核心思想是通过信道极化技术将多个独立的二进制输入离散无记忆信道（B-DMC, Binary-input Discrete Memoryless Channel）分裂为若干个极化子信道，其中一部分信道变得非常可靠，另一部分则变得非常不可靠。通过对这些极化子信道的选择和分配，可以实现接近香农极限的通信性能。

巴氏参数与信道可靠性

---

• 巴氏参数

巴氏参数$Z(W)$是衡量信道可靠性的关键指标。对于一个给定的信道$W$，$Z(W)$的值越大，说明该信道越不可靠；反之，$Z(W)$越小，则信道越可靠。具体来说，巴氏参数$Z(W)$与信道的对称容量$I(W)$存在反比关系：
$
Z(W) = 1 - I(W)
$
因此，当$Z(W)$接近于 0 时，信道几乎完全可靠；而当$Z(W)$接近于 1 时，信道几乎完全不可靠。

---

• BEC信道的可靠性估计

对于二进制删除信道（Binary Erasure Channel, BEC），Arikan在其论文中提出了通过计算巴氏参数来估计信道可靠性。BEC是一种特殊的 B-DMC，其输出要么是正确的比特值，要么是删除符号（表示传输失败）。由于 BEC 的特殊性质，其巴氏参数可以直接计算为：
$
Z(W) = p
$
其中$p$是信道的删除概率。

---

• 其他信道的可靠性估计

对于更一般的二进制输入对称信道（Binary-input Symmetric Channel, BSC）或二进制输入加性高斯白噪声信道（Binary-input Additive White Gaussian Noise Channel, BAWGNC），不存在直接计算$Z(W_N^{(i)})$的解析方法。为此，Mori 等人提出了密度进化（Density Evolution, DE）的方法，该方法适用于所有类型的 B-DMC。此外，在实际应用中，为了简化计算，还可以使用高斯近似（Gaussian Approximation, GA）方法来替代 DE。

---

• 极化过程中的巴氏参数递推公式

在极化过程中，原始信道$W_N^{(i)}$被分裂为两个子信道$W_{2N}^{(2i-1)}$和$W_{2N}^{(2i)}$，对应的巴氏参数递推公式为：
$$Z(W_{2N}^{(2i-1)})\le 2Z(W_N^{(i)})-[Z(W_N^{(i)}){]}^2$$

$$Z(W_{2N}^{(2i)})=[Z(W_N^{(i)}){]}^2$$

需要注意的是，上述不等式仅在$W_N^{(i)}$是 BEC 时成立。

---

• 示例代码：巴氏参数计算

以下是一个 MATLAB 函数示例，用于计算极化后的巴氏参数：

N = 8; % 极化码长度
ZW = 0.5; % 初始信道的巴氏参数
ZW8 = ZW_cal(N, ZW);
ZW8 = bitrevorder(ZW8); % 按位置二进制比特翻转function ZWi = ZW_cal(N, ZW)ZWi = zeros(N, 1);ZWi(1) = ZW;m = 1; % 极化级数while(m < N) for j = 1 : m% 计算信道极化Z_tmp = ZWi(j);ZWi(j) = 2 * Z_tmp - Z_tmp * Z_tmp; % 好信道ZWi(j + m) = Z_tmp * Z_tmp; % 差信道endm = m * 2;end
end

---

比特混合

在极化码的构造过程中，需要选择可靠性最高的$K$个分裂子信道来传输消息比特，其余的分裂子信道则用于传输冻结比特（frozen bits）。对于 BEC 信道而言，这一过程可以通过选择巴氏参数最小的$K$个子信道来实现。

---

生成矩阵

在极化码的理论中，生成矩阵$G_N$是编码过程的核心组成部分。通过数学推导可以得到，编码器递归构造（生成矩阵）表示为：
$$G_N=B_N{F}^{\otimes n}$$
其中，$B_N$是一个比特翻转矩阵，定义为：
$$B_N=R_N(I_2\otimes B_{N/2})$$
这里，$F^{\otimes n}$表示对矩阵$F$进行$n$次克罗内克积运算，而$F$定义为：
$$F=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$$

---

• 克罗内克积定义

克罗内克积（Kronecker Product）是两个矩阵之间的运算，记作$A\otimes B$，其结果是一个更大的矩阵。具体定义如下：

$$A\otimes B=\left[\begin{array}{cccc}{a}_{11}B& a_{12}B& \cdots & a_{1N}B\\ a_{21}B& a_{22}B& \cdots & a_{2N}B\\ ⋮& ⋮& \ddots & ⋮\\ a_{N1}B& a_{N2}B& \cdots & a_{NN}B\end{array}\right]$$

例如，对于两个矩阵：

$$A=\left[\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right],B=\left[\begin{array}{cc}{b}_{11}& b_{12}\\ b_{21}& b_{22}\end{array}\right]$$

它们的克罗内克积为：

$$A\otimes B=\left[\begin{array}{cc}{a}_{11}B& a_{12}B\\ a_{21}B& a_{22}B\end{array}\right]=\left[\begin{array}{cccc}{a}_{11}{b}_{11}& a_{11}{b}_{12}& a_{12}{b}_{11}& a_{12}{b}_{12}\\ a_{11}{b}_{21}& a_{11}{b}_{22}& a_{12}{b}_{21}& a_{12}{b}_{22}\\ a_{21}{b}_{11}& a_{21}{b}_{12}& a_{22}{b}_{11}& a_{22}{b}_{12}\\ a_{21}{b}_{21}& a_{21}{b}_{22}& a_{22}{b}_{21}& a_{22}{b}_{22}\end{array}\right]$$

---

• 比特翻转矩阵$B_N$

比特翻转矩阵$B_N$的递归定义为：
$$B_N=R_N(I_2\otimes B_{N/2})$$
其中，$I_n$是$n$-阶单位矩阵，例如：
$$I_2=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$$

对于$B_2$，有：
$$B_2=I_2=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$$

矩阵$R_N$是一个排列运算矩阵，用于将奇数位放在前面，偶数位放在后面。例如，对于$N=4$：
$$[1,3,2,4]=[1,2,3,4]R_4$$
对应的$R_4$矩阵为：
$$R_4=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right]$$

---

• 生成矩阵的构造过程

生成矩阵$G_N$的构造过程可以通过以下步骤实现：

1. 计算$F^{\otimes n}$
   对矩阵$F$进行$n$次克罗内克积运算，其中$N=2^n$。例如：
   $$F^{\otimes 1}=F=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$$

$$F^{\otimes 2}=F\otimes F=\left[\begin{array}{cc}F& 0\\ F& F\end{array}\right]=\left[\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 0& 0\\ 1& 0& 1& 0\\ 1& 1& 1& 1\end{array}\right]$$

2. 构造比特翻转矩阵$B_N$
   根据递归公式$B_N=R_N(I_2\otimes B_{N/2})$，逐步构造$B_N$。例如：
   $$B_2=I_2=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$$

$$B_4=R_4(I_2\otimes B_2)=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right]\cdot \left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right]=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right]$$

3. 生成矩阵$G_N$
   最终生成矩阵为：
   $$G_N=B_N{F}^{\otimes n}$$

---

• 总结

生成矩阵$G_N$是极化码编码的核心工具，它通过比特翻转矩阵$B_N$和克罗内克积矩阵$F^{\otimes n}$构造而成。这种递归构造方式不仅理论清晰，而且便于硬件实现，是极化码高效编解码的重要基础。

编码举例

在极化码的编码过程中，假设我们已经计算出各个分裂信道的巴氏参数，并根据信道容量对子信道进行排序。例如，假设序号为“4, 6, 7, 8”的子信道具有最小的巴氏参数，因此将这些子信道用于传输信息比特，而将休眠比特放置在序号为“1, 2, 3, 5”的位置。假设休眠比特为 0，信息比特为 (1, 1, 1, 1)，则最终得到输入序列$u_8=[0,0,0,1,0,1,1,1]$。

接下来，我们需要构造生成矩阵$G_8$来完成编码过程。生成矩阵由排序矩阵$B_N$和克罗内克积矩阵$F^{\otimes n}$构成，即$G_N=B_N{F}^{\otimes n}$。

---

• 求排序矩阵$B_N$

排序矩阵$B_N$是通过递归方式构造的。首先定义$B_2=I_2$，其中$I_2$是单位矩阵：
$
B_2 =
\begin{bmatrix}
1 & 0 \
0 & 1
\end{bmatrix}
$

接着，利用递归公式$B_4=R_4(I_2\otimes B_2)$和$B_8=R_8(I_2\otimes B_4)$，可以逐步求得$B_8$。具体步骤如下：

1. 计算$I_2\otimes B_2$：

$$I_2\otimes B_2=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right]$$

2. 计算$R_4$：

$$R_4=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right]$$

3. 计算$B_4$：

$$B_4=R_4(I_2\otimes B_2)=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right]\cdot \left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right]=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right]$$

4. 计算$I_2\otimes B_4$：

$$I_2\otimes B_4=\left[\begin{array}{cccccccc}1& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 0& 0& 1\end{array}\right]$$

5. 计算$R_8$：

$$R_8=\left[\begin{array}{cccccccc}1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1\end{array}\right]$$

6. 最终计算$B_8$：

$$B_8=R_8(I_2\otimes B_4)=\left[\begin{array}{cccccccc}1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1\end{array}\right]$$

---

• 求$F$的$n$次克罗内克积

$F$是一个$2\times 2$的生成矩阵，定义为：
$$F=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$$
通过递归方式计算$F^{\otimes n}$：

1.$F^{\otimes 1}=F$：

$$F^{\otimes 1}=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$$

2.$F^{\otimes 2}=F\otimes F$：

$$F^{\otimes 2}=\left[\begin{array}{cc}F& 0\\ F& F\end{array}\right]=\left[\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 0& 0\\ 1& 0& 1& 0\\ 1& 1& 1& 1\end{array}\right]$$

3.$F^{\otimes 3}=F\otimes F^{\otimes 2}$：

$$F^{\otimes 3}=\left[\begin{array}{cc}{F}^{\otimes 2}& 0\\ F^{\otimes 2}& F^{\otimes 2}\end{array}\right]=\left[\begin{array}{cccccccc}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{array}\right]$$

---

• 计算生成矩阵$G_8$

生成矩阵$G_8$定义为$G_8=B_8{F}^{\otimes 3}$。将$B_8$和$F^{\otimes 3}$相乘即可得到$G_8$。
$$G_8=B_8{F}^{\otimes 3}=\left[\begin{array}{cccccccc}1& 0& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 1& 0& 0& 0\\ 1& 1& 0& 0& 0& 0& 0& 0\\ 1& 1& 0& 0& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 0& 0\\ 1& 0& 1& 0& 1& 0& 0& 0\\ 1& 1& 1& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 1\end{array}\right]$$

---

• 生成 Polar 码

最终，利用生成矩阵$G_8$对输入序列$u_8$进行编码：

$x_8=u_8{G}_8$

具体计算如下：

$$x_8=\left[\begin{array}{cccccccc}0& 0& 0& 1& 0& 1& 1& 1\end{array}\right]\cdot \left[\begin{array}{cccccccc}1& 0& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 1& 0& 0& 0\\ 1& 1& 0& 0& 0& 0& 0& 0\\ 1& 1& 0& 0& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 0& 0\\ 1& 0& 1& 0& 1& 0& 0& 0\\ 1& 1& 1& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 1\end{array}\right]=\left[\begin{array}{cccccccc}0& 1& 1& 0& 1& 0& 0& 1\end{array}\right]$$
因此，生成的 Polar 码为：

$$x_8=[0,1,1,0,1,0,0,1]$$

• MATLAB 仿真

在 MATLAB 中，可以通过递归算法和矩阵运算两种方式实现编码。以下为代码示例：

% 极化编码
u = [0 0 0 1 0 1 1 1]; % 添加休眠比特后的码字x1 = polarCode(u); % 递归算法实现
x2 = polarMatrix(u); % 矩阵运算实现编码function x = polarCode(u)N = length(u);if N == 1x = u; % 待编码序列长度为 1 时，极化编码就是它本身else% 将待编码序列 u 分为前半段、后半段% 前半段与后半段进行模 2 加，结果存放于前半段中u1 = mod(u(1:N/2) + u(N/2+1:N), 2);u2 = u(N/2+1:N); % 后半段不变% 运行递归计算x = [polarCode(u1), polarCode(u2)];end
endfunction x = polarMatrix(u)N = length(u);if N == 1x = u;elseif 2^nextpow2(N) ~= Ntmp = zeros(1, 2^nextpow2(N));tmp(1:N) = u;x = polarMatrix(tmp);x = x(1:N);elsen = log2(N);Gpre = 1;for i = 1:nNi = 2^i;A = zeros(Ni);for j = 1:Ni/2A(2*j-1, j) = 1;A(2*j, j) = 1;A(2*j, Ni/2+j) = 1;endG = A * kron(eye(2), Gpre);Gpre = G;endGN = Gpre; % 生成矩阵 GNx = mod(u * GN, 2); % GN 与 u 的运算中加法代表异或运算end
end

通过上述代码，我们可以验证递归算法和矩阵运算两种方法的结果是否一致。

2.3.4 极化译码

极化译码的核心思想是基于接收信号的似然比（Likelihood Ratio, LR）或对数似然比（Log-Likelihood Ratio, LLR）进行逐比特判决。以下详细解释极化译码中的最小单元译码过程。

---

最小单元译码

在极化码的译码过程中，最小单元译码是最基本的一步，用于计算每个比特的似然比$L_R({\hat{u}}_1)$和$L_R({\hat{u}}_2)$。

---

• 似然比

根据信道模型和递归构造原理，可以推导出以下公式：
$$L_R({\hat{u}}_1)=\frac{P({\hat{u}}_1=0)}{P({\hat{u}}_1=1)}=\frac{P({\hat{x}}_1=0)P({\hat{x}}_2=0)+P({\hat{x}}_1=1)P({\hat{x}}_2=1)}{P({\hat{x}}_1=0)P({\hat{x}}_2=1)+P({\hat{x}}_1=1)P({\hat{x}}_2=0)}$$

进一步简化后可得：
$$L_R({\hat{u}}_1)=\frac{1+L_R({\hat{x}}_1)L_R({\hat{x}}_2)}{L_R({\hat{x}}_1)+L_R({\hat{x}}_2)}$$

如果假设${\hat{u}}_1=0$，则当${\hat{u}}_2=0$时，必须满足${\hat{x}}_1={\hat{x}}_2=0$；而当${\hat{u}}_2=1$时，则${\hat{x}}_1={\hat{x}}_2=1$。因此，条件似然比$L_R({\hat{u}}_1=0)({\hat{u}}_2)$可表示为：
$$L_R({\hat{u}}_1=0)({\hat{u}}_2)=\frac{P_{{\hat{u}}_1=0}({\hat{u}}_2=0)}{P_{{\hat{u}}_1=0}({\hat{u}}_2=1)}=\frac{P({\hat{x}}_1=0)P({\hat{x}}_2=0)}{P({\hat{x}}_1=1)P({\hat{x}}_2=1)}=L_R({\hat{x}}_1)L_R({\hat{x}}_2)$$

同理，当${\hat{u}}_1=1$时，有：
$$L_R({\hat{u}}_1=1)({\hat{u}}_2)=\frac{P_{{\hat{u}}_1=1}({\hat{u}}_2=0)}{P_{{\hat{u}}_1=1}({\hat{u}}_2=1)}=\frac{L_R({\hat{x}}_2)}{L_R({\hat{x}}_1)}$$

综合上述结果，最终可得：
$$L_R({\hat{u}}_2)=[L_R({\hat{x}}_1){]}^{1-2{\hat{u}}_1}{L}_R({\hat{x}}_2)$$

---

• 对数似然比（LLR）的应用

在实际应用中，通常使用对数似然比（LLR）代替似然比，以简化计算复杂度。定义$L_1=\ln (L_R({\hat{x}}_1))$和$L_2=\ln (L_R({\hat{x}}_2))$，则有：
$$L_{LR}({\hat{u}}_1)=\ln \left(\frac{1+e^{L_1+L_2}}{e^{L_1}+e^{L_2}}\right)$$

在高斯信道下，该式可以近似为：
L L R ( u ^ 1 ) ≈ sign ⁡ ( L 1 ) sign ⁡ ( L 2 ) min ⁡ { ∣ L 1 ∣ , ∣ L 2 ∣ } L_{LR}(\hat{u}_1) \approx \operatorname{sign}(L_1)\operatorname{sign}(L_2)\min\{|L_1|, |L_2|\} LLR​(u^1​)≈sign(L1​)sign(L2​)min{∣L1​∣,∣L2​∣}

其中，$\mathrm{sign}$表示取符号位操作，上式被称为$f$运算。得到${\hat{u}}_1$后，即可进一步计算${\hat{u}}_2$的 LLR：
$$L_{LR}({\hat{u}}_2)=(1-2{\hat{u}}_1)L_1+L_2$$

上式被称为$g$运算。

通过计算$L_{LR}({\hat{u}}_1)$和$L_{LR}({\hat{u}}_2)$，可以进行判决：若$L_{LR}\ge 0$，判决为 0；若$L_{LR}<0$，判决为 1。同样地，对于似然比$L_R$，若$L_R\ge 1$，判决为 0；否则判决为 1。

---

• BPSK 调制下的 LLR 计算

在二进制相移键控（BPSK）调制中，发送信号$s$定义为：
s = 1 − 2 x , s ∈ { 1 , − 1 } s = 1 - 2x, \quad s \in \{1, -1\} s=1−2x,s∈{1,−1}

接收信号$y$表示为：
$$y=s+n$$

其中$n$是均值为 0、方差为${\sigma }^2$的高斯白噪声。此时，接收信号$y$的 LLR 可表示为：
$$L_{LR}=\ln \left(\frac{\frac{1}{\sqrt{2\pi {\sigma }^2}}{e}^{-(y-1{)}^2/(2{\sigma }^2)}}{\frac{1}{\sqrt{2\pi {\sigma }^2}}{e}^{-(y+1{)}^2/(2{\sigma }^2)}}\right)=\frac{2y}{{\sigma }^2}$$

---

串行抵消译码（SC译码）算法

串行抵消译码（Successive Cancellation, SC）是极化码的一种经典译码算法。它通过递归的方式对二叉树结构进行遍历，逐步完成对每个子信道的判决。以下以一个具体例子来说明 SC 译码的过程。

---

• 配置与问题描述

假设在 AWGN 信道中传输数据，配置如下：

• 码长$N=8$
• 信息比特数$K=4$
• 码率$R=K/N=0.5$
• 信息比特集合为 { 4 , 6 , 7 , 8 } \{4, 6, 7, 8\} {4,6,7,8}，冻结比特全部取 0
• 信息比特为$(1,1,1,1)$，则输入序列$u_1^8=(00010111)$
• 编码后得到 Polar 码$x_1^8=u_1^8{F}^{\otimes 3}=(01101001)$
• 对应 BPSK 序列为$x_1^8=(1,-1,-1,1,-1,1,1,-1)$
• 生成随机噪声序列$n_1^8=(-1.4,0.5,0.2,-0.8,-0.3,0.2,2.3,1.7)$
• 接收信号为$y_1^8=s_1^8+n_1^8=(-0.4,-0.5,-0.8,0.2,-1.3,1.2,3.3,0.7)$
• 接收对数似然比（LLR）序列为：

$$L_1^8=\frac{2}{{\sigma }^2}{y}_1^8=(-2.0,-2.5,-4.0,1.0,-6.5,6.0,16.6,3.5)$$

---

• SC 译码的二叉树表示

SC 译码过程可以用二叉树表示，其结构与编码图一致。

每个节点对应一个长度为$N$的 LLR 序列，按照以下规则递归处理：

1. 母节点到左子节点：

   • 将母节点长度为$N$的 LLR 序列进行$N/2$次$f$运算，得到左子节点的 LLR 序列。
   • 如果左子节点不是叶节点，则将其作为新的母节点继续向下递归。
   • 如果左子节点是叶节点：
     • 若为冻结比特，直接判决为 0；
     • 若为信息比特，通过 LLR 硬判决（大于等于 0 判决为 0，小于 0 判决为 1），并将判决结果传回母节点。

2. 母节点到右子节点：

   • 使用部分判决结果和 LLR 序列进行$N/2$次$g$运算，得到右子节点的 LLR 序列。
   • 对右子节点重复上述操作。

3. 母节点判决：

   • 当左右子节点的判决结果都已知时，通过运算得到母节点对应的判决结果。

递归实现整个二叉树的译码过程，最终得到完整的译码结果。

---

• $f$和$g$函数定义

在 SC 译码中，$f$和$g$是两个核心运算函数，分别用于计算左子节点和右子节点的 LLR 序列。

1. $f$函数：

   • 定义为：

$$f(x,y)=\text{sign}(x)\cdot \text{sign}(y)\cdot \min (|x|,|y|)$$

• 作用是对两个 LLR 值进行组合，保留较小的绝对值并保持符号一致性。

2. $g$函数：

   • 定义为：

$$g(u,x,y)=(1-2u)\cdot x+y$$

• 作用是根据部分判决结果$u$和 LLR 值$x,y$计算新的 LLR 序列。

---

• MATLAB 仿真实现

以下是基于 MATLAB 的 SC 译码实现代码，使用上述 LLR 序列进行仿真。

% 极化译码
% 对数似然比
LLR = [-2.0, -2.5, -4.0, 1.0, -6.5, 6.0, 16.6, 3.5];
% 冻结比特位（1是冻结位）
frozen_bits = [1, 1, 1, 0, 1, 0, 0, 0];
[u, b] = SC_decode(LLR, frozen_bits);function [u, b] = SC_decode(llr, frozen_bits)N = length(llr);if N == 1if frozen_bitsu = 0; % 冻结比特直接判决为0elseu = llr < 0; % 硬判决；小于0判决为1，大于等于0判决为0endb = u;else% 运行f运算alpha_left = f(llr(1:N/2), llr(N/2+1:N));% 递归译码[u_left_child, beta_left_child] = SC_decode(alpha_left, frozen_bits(1:N/2));% 运行g运算alpha_right = g(beta_left_child, llr(1:N/2), llr(N/2+1:N));% 递归译码[u_right_child, beta_right_child] = SC_decode(alpha_right, frozen_bits(N/2+1:N));% 合并译码结果u = [u_left_child, u_right_child];b = zeros(1, N);b(1:N/2) = mod(beta_left_child + beta_right_child, 2);b(N/2+1:N) = beta_right_child;end
endfunction [z] = f(x, y) % f函数z = sign(x) .* sign(y) .* min(abs(x), abs(y));
endfunction [z] = g(u, x, y) % g函数z = (1 - 2 * u) .* x + y;
end

---

• 总结

SC 译码算法通过递归方式对二叉树结构进行遍历，结合$f$和$g$运算完成对每个子信道的判决。该算法具有较低的复杂度，适用于中小规模的极化码译码。然而，对于大规模码长，SC 译码的性能可能受到限制，因此衍生出了多种改进算法（如 SCL、CA-SCL 等）。

SCL译码算法

SCL（Successive Cancellation List，串行抵消列表）译码算法是Polar Code的一种改进译码方法。与SC（Successive Cancellation）译码相比，SCL通过引入列表机制来缓解错误传递问题，从而显著提升有限码长下的性能。

---

• 问题背景

在Polar Code中，当码长趋于无穷时，信道极化才会完全实现。但在实际应用中，由于码长有限，信道极化并不完全，这可能导致某些信息比特无法被正确译码。SC译码器的一个主要缺点是，它在对后续信息比特进行译码时依赖于先前比特的估计值。如果前面的信息比特译码发生错误，则会引发错误传递，且这种错误无法修正。

为了解决这一问题，SCL算法应运而生。SCL通过增加列表机制，在每一层路径搜索后保留多个候选路径，从而降低错误传递的概率。

---

• 路径度量值（PM）

为了评估每条候选路径的优劣，定义路径度量值（Path Metrics, PM）。路径度量值反映了某个译码结果的后验概率$\mathrm{Pr}(u_1^i|y_1^N)$，其值越大，说明该译码结果越可能正确。经过数学推导，路径度量值可以表示为：
$$-\ln \mathrm{Pr}(u_1^i|y_1^N)=\sum _{k=1}^i\ln (1+e^{-(1-2u_k)L_N(k)})$$
令$PM=-\ln \mathrm{Pr}(u_1^i|y_1^N)$，则路径度量值越小，译码正确率越高。

---

• 算法流程

SCL译码算法的具体步骤如下：

（1）初始化

在SCL译码器内部并行放置$L$个SC译码器，记作$S{C}_1,S{C}_2,\dots ,S{C}_L$。初始状态下，所有译码器均未激活，未激活译码器集合为 S s l e e p = { 2 , 3 , … , L } S_{sleep} = \{2, 3, \dots, L\} Ssleep​={2,3,…,L}，仅激活1号译码器。

（2）接收LLR序列

SCL译码器获得接收对数似然比（LLR）序列$(L_1,L_2,\dots ,L_N)$，并将路径度量值初始化为0。

（3）逐比特译码

激活的译码器按照标准SC译码流程进行逐比特译码。对于当前比特$u_i$：

• 如果$u_i$是冻结比特，直接令$u_i=0$。

• 如果$u_i$是信息比特，判断未激活译码器集合$S_{sleep}$是否为空：

  • 若$S_{sleep}\ne \varnothing$，从$S_{sleep}$中弹出一个译码器，并继承当前激活译码器的所有数据。

  • 原始路径（例如$S{C}_1$）设$u_i=0$，克隆路径设$u_i=1$。

  • 分别计算两条路径的路径度量值：
    $$\mathrm{Pr}(u_1^i,1|y_1^N)=\sum _{k=1}^{i-1}\ln (1+e^{-(1-2u_k,1)L_N(k)})+\ln (1+e^{-L_N(i)})$$

$$\mathrm{Pr}(u_1^i,2|y_1^N)=\sum _{k=1}^{i-1}\ln (1+e^{-(1-2u_k,2)L_N(k)})+\ln (1+e^{L_N(i)})$$

此时，SCL译码器同时保留了$u_i=0$和$u_i=1$两种译码结果。

（4）扩展路径

激活的不同译码器继续独立译码，重复上述步骤（3），直到$S_{sleep}=\varnothing$。

（5）路径选择

在某一时刻，假设所有$L$个已激活译码器各自有判决$u_t$的路径度量值$P{M}_l,LLR:L_N,l^t,1\le l\le L$。根据公式：
$$PM=\left[\begin{array}{ccccc}P{M}_1+\ln (1+e^{-L_N,1(t)})& \dots & P{M}_l+\ln (1+e^{-L_N,l(t)})& \dots & P{M}_L+\ln (1+e^{-L_N,L(t)})\\ P{M}_1+\ln (1+e^{L_N,1(t)})& \dots & P{M}_l+\ln (1+e^{L_N,l(t)})& \dots & P{M}_L+\ln (1+e^{L_N,L(t)})\end{array}\right]$$
从上述$2L$条路径中选取路径度量值最小的$L$条路径保留。

对于每列路径度量值，可能存在以下三种情况：

1. 两个元素均未选入：对应译码器$S{C}_l$休眠并回收入$S_{sleep}$。
2. 仅一个元素选入：对应译码器$S{C}_l$保留选入的比特，并更新路径度量。
3. 两个元素均选入：保留$u_t,l=0$的路径，并更新路径度量；随后从$S_{sleep}$中弹出一个译码器继承$S{C}_l$的数据，设$u_t,k=1$，并据此更新路径度量。

（6）完成译码

若当前比特为冻结比特，直接判为0并更新路径度量；若为信息比特，则重复上述步骤。以此类推，直至完成所有$N$个比特的译码。

（7）输出结果

在所有译码结束后，选择路径度量值最小的译码结果作为最终输出。

---

• 搜索宽度参数$L$

在SCL译码算法中，参数$L$称为搜索宽度：

• 当$L=1$时，SCL退化为SC译码算法。
• 当$L\ge 2^K$（$K$为信息比特数）时，SCL等价于最大似然译码。

SC译码算法是深度优先的，目标是从根节点快速到达叶子节点；而SCL译码算法则是广度优先的，先扩展多条路径，再通过剪枝操作保留最优路径，最终到达叶子节点。

通过合理设置$L$，可以在复杂度和性能之间取得平衡，从而有效提升Polar Code的译码性能。

2.3.5 总结

Polar 码是一种基于信道极化这一数字信号处理技术的纠错编码方法，本文对信道极化现象以及 Polar 码的编码和译码原理进行了深入研究。以下将从优势、主要问题及应用前景等方面对 Polar 码进行总结。

---

Polar 码的优势

1. 容量可达性
   在实际通信系统中，Turbo 码和 LDPC 码等传统信道编码方案在码长接近无限时能够非常逼近信道容量，但始终无法被严格证明达到容量。而 Polar 码在码长趋于无穷的场景下，已被严格数学证明能够达到信道容量。这是 Polar 码的核心理论优势之一。

2. 明确的构码方法
   Polar 码具有明确的构造方法，通过信道极化过程生成好的子信道用于传输信息比特，差的子信道用于冻结比特。这种构造方式不仅理论清晰，而且便于实现。

3. 较低的编译码复杂度
   Polar 码的编译码复杂度相对较低，其复杂度为$O(N\log N)$，与 Turbo 码和 LDPC 码相当。同时，采用串行抵消（SC）译码算法可以获得接近最大似然解码的性能。

4. 优异的性能表现
   在适当的译码方法（如 SCL 或 CA-SCL）支持下，Polar 码的性能可以超越最好的 LDPC 码和 Turbo 码，特别是在中短码长的情形下表现尤为突出。

---

Polar 码的主要问题

1. 最小汉明距离较小
   Polar 码的最小汉明距离相对较小，这可能在一定程度上影响其解码性能，尤其是在高误码率场景下可能导致错误传播。
2. SC 译码时延较长
   SC 译码算法虽然复杂度较低，但由于其串行特性，译码时延较长。为缓解这一问题，可以通过并行解码方法（如 SCL 或 List 解码）来提高译码效率，但这会增加硬件复杂度。

Polar 码的应用前景

Polar 码较好地平衡了性能和复杂性，在中短码长的情形下表现出显著优势。因此，它在现代通信系统中有广阔的应用前景，特别是在以下领域：

1. 信源编码
   Polar 码不仅可以用于信道编码，还可以扩展到信源编码领域。例如，通过构造对偶码，Polar 码可以实现高效的压缩编码。

2. 多用户通信
   在多用户通信场景中，Polar 码可以结合网络编码技术，优化多用户间的资源共享和干扰管理。

3. 物理层保密通信
   Polar 码在物理层保密通信中具有潜在应用价值，例如通过设计特定的冻结比特模式来实现信息的安全传输。

尽管这些应用领域已引起部分学者的关注，但大多数研究仍停留在理论阶段。为了在未来的通信系统中实现 Polar 码的实际部署和应用，仍然需要大量的研究工作，包括算法优化、硬件实现以及与其他通信技术的融合。

---

2.3.6 参考文档

[1] Erdal Arikan. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Transactions on information Theory, 55(7):3051–3073, 2009.

[2] 于永润. 极化码讲义

[3] Polar Code 24节

[4] 不错的PPT

文章亦发布在博客：LiQ’s blog - 个人博客 学习经验分享，欢迎关注。

参考链接：5G 信道编码技术—Polar码 - 知乎