极化码-编码

极化编码的基本思想是:只在 Z ( W N ( i ) ) Z\left( W_{N}^{\left( i \right)} \right) Z(WN(i)​)近于0的坐标信道 W N ( i ) W_{N}^{\left( i \right)} WN(i)​上发送数据比特。极化码具有一般的二元线性分组码的基本编码要素,因而可以通过显示地写出其生成矩阵来完成编码:

x 1 N = u 1 N G N x_{1}^{N}=u_{1}^{N}{G_{N}} x1N​=u1N​GN​

其中,编码生成矩阵 G N = B N F ⊗ n {G_{N}}\text{=}{B_{N}}{F^{\otimes n}} GN​=BN​F⊗n, B N B_{N} BN​是排序矩阵,完成比特的反序操作, F ⊗ n F^{\otimes n} F⊗n表示矩阵 F F F进行 n n n次 K r o n e c k e r Kronecker Kronecker积操作,有递归公式 F ⊗ n = F ⊗ F ⊗ ( n − 1 ) {F^{\otimes n}}=F\otimes {F^{\otimes \left( n-1 \right)}} F⊗n=F⊗F⊗(n−1)且 F ⊗ 1 = F = [ 1 0 1 1 ] {F^{\otimes 1}}\text{=}F=\left[ \begin{matrix} 1 & 0 \\ 1 & 1 \\ \end{matrix} \right] F⊗1=F=[11​01​]。

主要的步骤为:

极化码-编码

可靠性估计

可靠性估计就是极化码的构造,这个过程我们选出信道容量高的子信道进行传输,信道容量低的子信道传输冻结比特。

常见的几种可靠性估计的方法(极化码构造方法)有:

  1. 巴士参数估计法。

  2. 蒙特卡洛法。

  3. 密度进化法。

  4. 高斯近似法。

比特混合

假设通过错误概率进行极化码构造之后得到极化序列为 { 3 , 5 , 6 , 7 , 0 , 1 , 2 , 4 } \left\{ 3,5,6,7,0,1,2,4 \right\} {3,5,6,7,0,1,2,4} ,选择前面K个信道即 A = { 3 , 5 , 6 , 7 } A=\left\{ 3,5,6,7\right\} A={3,5,6,7}发送信息比特;另外的信道集合 A c = { 0 , 1 , 2 , 4 } {A^{c}}=\left\{ 0,1,2,4\right\} Ac={0,1,2,4}作为固定比特传输。设信息比特集合为 ( i 0 , i 1 , i 2 , i 3 ) = ( 1 , 1 , 1 , 1 ) \left( {i_{0}},{i_{1}},{i_{2}},{i_{3}} \right)=\left( 1,1,1,1 \right) (i0​,i1​,i2​,i3​)=(1,1,1,1),固定比特设置为0,则最终得到待编码的信息比特:

u 0 7 = [ 0 , 0 , 0 , i 0 , 0 , i 1 , i 2 , i 3 ] = [ 0 , 0 , 0 , 1 , 0 , 1 , 1 , 1 ] u_{0}^{7}=\left[ 0,0,0,{i_{0}},0,{i_{1}},{i_{2}},{i_{3}} \right]=\left[ 0,0,0,1,0,1,1,1 \right] u07​=[0,0,0,i0​,0,i1​,i2​,i3​]=[0,0,0,1,0,1,1,1]

经过上面的过程我们就完成了对信息位和冻结位的比特混合。

构造生成矩阵

首先我们求出排序矩阵 B N B_{N} BN​,其有递归式:

B N = R N ( I 2 ⊗ B N / 2    ) {B_{N}}={R_{N}}\left( {I_{2}}\otimes {B_{N/{2}\;}} \right) BN​=RN​(I2​⊗BN/2​)

B 2 = I 2 {B_{2}}={I_{2}} B2​=I2​

我们得到排序矩阵 B N B_{N} BN​,对输入序列完成奇序元素和偶序元素的分离,即先排奇序元素,再排偶序元素,其作为效果如下:

( u 1 , u 2 , u 3 , u 4 , . . . , u ∗ N ) × R ∗ N = ( u 1 , u 3 , u 5 , . . . , u N − 1 , u 2 , u 4 , u 6 , . . . , u N ) \left( {u_{1}},{u_{2}},{u_{3}},{u_{4}},...,u{}*{N} \right)\times {R* {N}}=\left( {u_{1}},{u_{3}},{u_{5}},...,{u_{N-1}},{u_{2}},{u_{4}},{u_{6}},...,{u_{N}} \right) (u1​,u2​,u3​,u4​,...,u∗N)×R∗N=(u1​,u3​,u5​,...,uN−1​,u2​,u4​,u6​,...,uN​)

F F F矩阵我们可以根据下面的递归式进行求解:

F ⊗ n = F ⊗ F ⊗ ( n − 1 ) {F^{\otimes n}}=F\otimes {F^{\otimes \left( n-1 \right)}} F⊗n=F⊗F⊗(n−1)

F = [ 1 0 1 1 ] F=\left[ \begin{matrix} 1 & 0 \\ 1 & 1 \\ \end{matrix} \right] F=[11​01​]

最后,我们将求得的排序矩阵和 F F F矩阵相乘,得到生成矩阵 G N G_{N} GN​:

G N = B N F ⊗ n {G_{N}}={B_{N}}{F^{\otimes n}} GN​=BN​F⊗n

假设我们求得的生成矩阵是:

极化码-编码

生成极化码

将信息比特与生成矩阵 G N G_{N} GN​相乘得到最终编码后的极化码,例如:

极化码-编码


参考:

上一篇:同调代数笔记3


下一篇:P4719 【模板】"动态 DP"&动态树分治