极化码及性质

1、极化码及性质文献标识码： APolar code and its charactersWANG Jun-xuan, ZHANG Yan-yan(School of Communication and Information Engineering, Xian University of Post and Telecommunications, Xian710121, China)The construction and characteristics of polar code with binary discrete memoryless channel (BDMC) are introdu

2、ced. Polar code can archive symmetric capacity under BDMC, and has almost linear complexity of the code block. When the code block is N, the complexities of both encoding and decoding are almost O(NlogN). The application and recent research of polar code are also discussed.Keywords： polar code; chan

3、nel polarization; general matrix; decoder收稿日期： 2011-09-10 基金项目：陕西省教育厅科技项目 (09JK726) 0 引 言最近几年，无线通信发展得非常迅速，从3G到LTE再到4G技术，系统的传输速率也从 2M到几十兆甚至数百兆。无线通 信物理层中的信号处理技术相对发展较慢， 从 20 世纪 90 年代的 Turbo编码、LDPC编码以及MIMO多天线技术以来，更多的研究 可能集中在认知无线电、 合作通信等热点上， 以至于有的研究者 认为未来的信号处理领域可能已经走入困境 1 。自 2008年以来， E. Ankan 等人研究了信道极化问题

4、，根据 信息论的相关理论， 基于二元离散对称信道构造了所谓的人造虚 拟信道， 类似于信息论中的信源扩展； 发现随着人造信道扩展维 数N的增加，信道的对称容量(平均互信息)分别趋近于0或1。 在此基础上， E.Ankan 等人构造了极化码 (Polar Code)2-4，基本的思想就是当信道对称容量较好时可以传输信息， 当对称容 量接近于 0 的时候则不在该信道传输信息。 这样构造的极化码就 可以达到信道的对称容量，而且具有较好的复杂度 5-7 ，即编 码和译码的复杂度几乎与编码长度呈线性关系。本文主要介绍极化码的构造以及性质， 分析编码长度对极化 码信道选取的影响，同时也分析了极化码近期的主要

5、研究成果。信道极化对于二元离散无记忆信道 W(B-DMCV)，将N个独立的信道W 按照一定的方式进行合并，可以获得长度为N的矢量信道，即有对于B-DMCWWJ:xNf yN,其中满足 N=2n,n0,当n=0时,W仁W 图 1 是 n=1 时的信道合成示意图 1 。对于更一般的情况，由 N个信道W合成的信道为 WN WN可 以递归地由2个WN/2信道构成，其中WN/2是由N/2个W信道合 并而成，具体如图 1 所示1 。图1 2个W信道的合并示意图1其中，RN将sN1(sN1(s1,s2,sN)下面的标识相同)映射为 vN1的线性变换。RN的实际操作就是对基于二进制的元素序列编 号进行循环右移

6、，只是改变了 sN1 的元素排列顺序，比如 vN1=sN1RN则有vb1b2bn=sb2bn bl。对于所有的b1,b2,bn 0,1,其中vb1b2bn,sb2bnbl分别表示矢量 v和s的由二进制表示的第 b1b2bn个和b2bnbl个元素。矩 阵变换RN的目的是保证合并信道输出端的顺序为 y1y2yN,如 果不适用该变换，则有可能输出的顺序会发生改变。?fe ?图2 2个WN/2信道的合并成 WN示意图用l(W(i)N)(i=1,2,N)表示N个W合并信道中第i个信道的对称容量， 即为信息传输允许通过的最大速率。 信道对称容 量的计算可以按照递归式 (1) 进行：l(W(2i 1)N)=

7、l(W(i)N/2)2l(W(2i)N)=2l(W(i)N/2)l(W(i)N/2)2(1)式中:I(W(1)1)=I(W)。当信道是二元删除信道时，有I(W)=1- ( 是二元删除信道的删除率)。图3是当 =0.5时不同N的合并信道的对称容量。从图中可以看出，随着N的增大，对称 容量 I(W(i)N) 明显地分别向 0或 1的方向趋近，这就是信道的极化过程，这也是极化码的编码基础。图3二元删除信道( =0.5)在不同N的时候信道对称容量极化码编、译码极化码的编码类似于 RM(Reed-Muller) 码，也属于陪集码的 范筹。极化码的生成矩阵首先用表示 2 个矩阵的 Kronecker 积，

8、则 Kronecker 的 n 次方就可以定义为：An=AAn1(2)式中对于所有的n1, A0?茫？1。极化码的生成矩阵是极化码编码的关键。对于N=2 n,n0,定义极化码的生成矩阵为：GN=BNFn(3)式中：F=1011；BN是一个线性变换矩阵，类似于第1节的RN是基于二 进制的元素序列编号进行循环左移， 其只是改变了矩阵的元素排 列顺序，比如 vN1=sN1BN则有vb2bnb1=sb1b2bn,对于所 有的 b1,b2,bn 0,1。极化码的产生极化码的编码与线性码相同，在N=2n,n0的条件下，都可以用生成矩阵的形式进行：xN1=uN1GN(4)如果A是1,2,N的一个子矩阵，则式

9、(4)可以重写为:xN1=uAGN(A)?uAcGN(Ac)(5)式中：GN(A)是矩阵GN的一个子集，它由A中数值决定的 GN的行元素矩阵构成；uA是uN1中由A集合元素确定的子矢量； Ac是集合A的补集。因此，如果能够确定集合A和子矢量uAc，就可以获得信息uA的编码码字xN1。这就是GNM咅集编码，此 编码的参数是(N,K,A,uAc)。其中，K是集合A的大小；K/N是编 码速率；A被称作信息集合，基于补集的 Ac的剩余uAc就称作 休眠比特。因此，极化码编码的关键就是集合A和子矢量uAc的确定。根据第 1 节的叙述， 在合并信道中， 选择对称容量大的信道传输 信息，而对称容量小的信道则

10、不用传输信息，用于休眠比特 (休 眠比特 frozen-bits 对于收、 发端都是已知的， 因此不失一般性 可以取比特0)。根据这样的原则，在 N=8时，根据图1的结果， 发现 I(W(i)N)0.6(i=4,6,7,8) ，所以可以选择 A=4,6,7,8 ， 此时K=4,因此编码速率为 K/N=4/8=1/2。休眠比特的选取则也 按照A集合的元素进行。因此有下面的编码过程：由于编码效率为 1/2 ， 所以加上相应位置的休眠比特，u81=(0,0,0,u4,0,u6,u7,u8) ，根据式 (4) 则有：GN=BNF3=1 0 0 0 0 0 0 01 0 0 0 1 0 0 01 1 0

11、 0 0 0 0 01 1 0 0 1 1 0 01 0 1 0 0 0 0 01 0 1 0 1 0 1 01 1 1 1 0 0 0 01 1 1 1 1 1 1 1所以编码后的码字 :x81=u81GN=(0,0,0,u4,0,u6,u7,u8)1 0 0 0 0 0 0 01 0 0 0 1 0 0 01 1 0 0 0 0 0 01 1 0 0 1 1 0 01 0 1 0 0 0 0 01 0 1 0 1 0 1 01 1 1 1 0 0 0 01 1 1 1 1 1 1 1在该例中，选取的编码矩阵的行矢量的汉明距离都是比较大 的，要么为 8，要么为 4，所以在 N 比较大时，在确

12、定了编码效 率以后，贝V集合A的大小K就确定了，此时可以根据汉明距离从大到小来选取A的值，同时也就确定了 uAc,完成编码。2.3极化码的SC译码对于参数为(N,K,A,uAc)的极化码，输入信息uN1(其中包括 K个信息比特和N-K个休眠比特)通过编码成为N位的编码码字 xN1，该码字通过合成信道 WN最后的输出为yN1。译码器的任 务就是从已知的接收矢量 yN1中计算输入信息uN1的估计值N1。 实际中，由于休眠比特对于收、发双方都是已知的，因此真正需 要估计的比特数是 K个，对于休眠的比特则可以直接写出Ac=uAc。 Korada 等人在研究二元加性高斯白噪声信道时 8 ，把 休眠比特认为是已知的，可以作为信道估计序列使用。当Acm uAc 时就会产生错误码字判决，最后形成误码字概率。Arikan 在研究中介绍了连续抵消译码器 (SuccessiveCancellation , SC)。对于参数为(N,K,A,uAc)的极化码，基于SC译码器的第i个N1的判决量为：i=ui,for i Achi(yN1,i - 11),for i A(6)式中判决函数 hi(yN1,i -11)的定义为：hi(yN1,i -11)=0, if W(i