[⑤5G NR]: 5G Polar编码算法_5g polar码编码标准

前言

博主在[①5G NR]: 3GPP协议中Polar编码流程解读中介绍了5G中Polar码编码的相关流程，在这篇博客中就介绍下在5G中Polar码基础编码的算法，Polar码(极化码)的发明者是Erdal Arikan教授。

Arikan kernel

首先来介绍下什么是Arikan kernel。Arikan kernel或者Arikan matrix是个$2\ast 2$的矩阵：

G 2 = [ 1 0 1 1 ] G_2=

$$\begin{bmatrix} 1&0\\ 1&1\\ \end{bmatrix}$$ G2​=[11​01​]

对于最基础情形，$\underline{b}=[b_0,b_1]$为信息比特序列，$\underline{c}=[c_0,c_1]$为码字比特序列，那么就满足：

$\underline{c}=\underline{b}\cdot G_2$

结果可以由下图来描述：

生成矩阵$G_N$

Polar码的长度为$N=2^n$，根据协议章节5.3.1.2，Polar码的生成矩阵$G_N$由$G_2$通过Kronecker prodcut(克罗内克内积)计算得到：

G N = G 2 n = G 2 ⊗ G 2 n − 1 = [ G 2 n − 1 0 G 2 n − 1 G 2 n − 1 ] = ( G 2 ) ⊗ n G_N=G_{2^n}=G_2\otimes G_{2^{n-1}}=

$$\begin{bmatrix} G_{2^{n-1}}&0\\ G_{2^{n-1}}&G_{2^{n-1}}\\ \end{bmatrix}$$ =(G_2)^{\otimes n} GN​=G2n​=G2​⊗G2n−1​=[G2n−1​G2n−1​​0G2n−1​​]=(G2​)⊗n

如果$\underline{u}=[u_0,u_1,...,u_{N-1}]$为编码前的输入的信息比特序列，$\underline{d}=[d_0,d_1,...,d_{N-1}]$为编码后的输出的码字比特序列，那么就满足：

$\underline{d}=\underline{u}\cdot G_N$

样例$N=8$

Polar码码字的结果可以通过(recursive encoding)迭代的方式计算得出，以$N=2^3=8$为例，可以通过迭代3次计算得出，首先生成矩阵$G_8$为：

G 8 = G 2 ⊗ G 2 ⊗ G 2 = [ 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 ] G_8=G_2\otimes G_2 \otimes G_2=

$$\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}$$ G8​=G2​⊗G2​⊗G2​= ​11111111​01010101​00110011​00010001​00001111​00000101​00000011​00000001​ ​

记${\underline{u}}^{(n)}$ 为第n次迭代，那么3次迭代的过程见下图：

如果$\underline{u}=[0,0,0,1,0,1,1,1]$，那么

${\underline{u}}^{(1)}=[0,0,1,1,1,1,0,1]$
${\underline{u}}^{(2)}=[1,1,1,1,1,0,0,1]$
${\underline{u}}^{(3)}=[0,1,1,0,1,0,0,1]$
$\underline{d}=\underline{u}\cdot G_8=[0,1,1,0,1,0,0,1]$