Polar码（2）- Polar编码

       信道通过信道合并和分裂后，比特信道的容量产生极化现象，一部分子信道的容量趋向于1（“好”信道），另一部分的信道的容量趋向于0（“坏”信道）。因此，我们在“好”信道上发送信息比特，在“坏”信道上发送冻结比特（发端和收端都已知的比特信息）。本文主要介绍Polar的编码过程。
       对于给定的比特输入$u_1^N=(u_1,u_2,...,u_N{)}^T$，其中N为码长，则编码后的结果为
$$x_1^N=u_1^N\ast G_N$$       其中$G_N$为 $N\times N$的生成矩阵。进一步，对子信道进行选择，假设信道比特选择的子信道集合为$A$，在A中的子信道上传输信息比特；另外$A_c=(1,2,...,N)-A$，在$A_c$集合中的子信道传输冻结比特；$G_N(A)$为$G_N$的子信道；用公式可表示为$$x_1^N=u_A{G}_N(A)\oplus u_{A_c}{G}_N(A_c)$$       众所周知，Polar是陪集码的一种特例，因此，以$G_N$为生成矩阵生成的陪集码可以由参数$(N,K,A,u_{A_c})$确定，其中K为信息比特的长度；$N=2^n$为所有分裂子信道的数目；K/N即为码率；A为信息比特的索引集合；$A_c=(1,2,...N)-A$为冻结比特的索引集合；$u_{A_c}$为冻结比特信息，通常我们将冻结比特信息全部置为0。
       但在实际中，为了Polar译码的递归便利性，我们采用如下Polar生成矩阵进行编码
$$G_N=B_N{F}^{\otimes n}$$       其中有$$B_N=R_N(I_2\otimes B_{N/2})$$$$B_2=I_2$$$$F^{\otimes n}=F\otimes F^{\otimes n-1}$$ F = [ 1 0 1 1 ] F=

$$\begin{bmatrix}1 & 0 \\ 1 & 1 \\\end{bmatrix}$$ F=[11​01​]       上式中的$R_N$为奇偶分离矩阵；具体$G_N$的推导过程如下
       根据如下图递归编码结构有$$G_N=(I_{N/2}\otimes F)R_N(I_2\otimes G_{N/2})，N⩾2，G_1=I_1$$

       根据交换律有$$(I_{N/2}\otimes F)R_N=R_N(F\otimes I_{N/2})$$       对应的信道极化图为

       因此，上式可变换为$$G_N=R_N(F\otimes I_{N/2})(I_2\otimes G_{N/2})=R_N(F\otimes G_{N/2})，N⩾2$$       进一步，用$G_{N/2}=R_{N/2}(F\otimes G_{N/4})$做等量替换，则有
$$G_N=R_N(F\otimes (R_{N/2}(F\otimes G_{N/4})))=R_N(I_2\otimes R_{N/2})(F^{\otimes 2}\otimes G_{N/4})$$       根据性质$(AC)\otimes (BD)=(A\otimes B)(C\otimes D)$并令$A=I_2，B=R_{N/2}，C=F，D=F\otimes G_{N/4}$，则有$G_N$的最终表达式
$$G_N=B_N{F}^{\otimes n}$$       其中$$B_N=R_N(I_2\otimes R_{N/2})(I_4\otimes R_{N/4})\cdots (I_{N/2}\otimes R_2)$$       进一步$B_N$的化简形式为$$B_N=R_N(I_2\otimes B_{N/2})$$

参考文献：Channel Polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels, Erdal Arikan