極化碼及性質(zhì)

1、極化碼及性質(zhì)文獻標識碼： 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 引 言最近幾年，無線通信發(fā)展得非常迅速，從3G到LTE再到4G技術(shù)，系統(tǒng)的傳輸速率也從 2M到幾十兆甚至數(shù)百兆。無線通 信物理層中的信號處理技術(shù)相對發(fā)展較慢， 從 20 世紀 90 年代的 Turbo編碼、LDPC編碼以及MIMO多天線技術(shù)以來，更多的研究 可能集中在認知無線電、 合作通信等熱點上， 以至于有的研究者 認為未來的信號處理領(lǐng)域可能已經(jīng)走入困境 1 。自 2008年以來， E. Ankan 等人研究了信道極化問題

4、，根據(jù) 信息論的相關(guān)理論， 基于二元離散對稱信道構(gòu)造了所謂的人造虛 擬信道， 類似于信息論中的信源擴展； 發(fā)現(xiàn)隨著人造信道擴展維 數(shù)N的增加，信道的對稱容量(平均互信息)分別趨近于0或1。 在此基礎(chǔ)上， E.Ankan 等人構(gòu)造了極化碼 (Polar Code)2-4，基本的思想就是當信道對稱容量較好時可以傳輸信息， 當對稱容 量接近于 0 的時候則不在該信道傳輸信息。 這樣構(gòu)造的極化碼就 可以達到信道的對稱容量，而且具有較好的復(fù)雜度 5-7 ，即編 碼和譯碼的復(fù)雜度幾乎與編碼長度呈線性關(guān)系。本文主要介紹極化碼的構(gòu)造以及性質(zhì)， 分析編碼長度對極化 碼信道選取的影響，同時也分析了極化碼近期的主要

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信道構(gòu)成，其中WN/2是由N/2個W信道合 并而成，具體如圖 1 所示1 。圖1 2個W信道的合并示意圖1其中，RN將sN1(sN1(s1,s2,sN)下面的標識相同)映射為 vN1的線性變換。RN的實際操作就是對基于二進制的元素序列編 號進行循環(huán)右移

6、，只是改變了 sN1 的元素排列順序，比如 vN1=sN1RN則有vb1b2bn=sb2bn bl。對于所有的b1,b2,bn 0,1,其中vb1b2bn,sb2bnbl分別表示矢量 v和s的由二進制表示的第 b1b2bn個和b2bnbl個元素。矩 陣變換RN的目的是保證合并信道輸出端的順序為 y1y2yN,如 果不適用該變換，則有可能輸出的順序會發(fā)生改變。?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的方向趨近，這就是信道的極化過程，這也是極化碼的編碼基礎(chǔ)。圖3二元刪除信道( =0.5)在不同N的時候信道對稱容量極化碼編、譯碼極化碼的編碼類似于 RM(Reed-Muller) 碼，也屬于陪集碼的 范籌。極化碼的生成矩陣首先用表示 2 個矩陣的 Kronecker 積，

8、則 Kronecker 的 n 次方就可以定義為：An=AAn1(2)式中對于所有的n1, A0?茫？1。極化碼的生成矩陣是極化碼編碼的關(guān)鍵。對于N=2 n,n0,定義極化碼的生成矩陣為：GN=BNFn(3)式中：F=1011；BN是一個線性變換矩陣，類似于第1節(jié)的RN是基于二 進制的元素序列編號進行循環(huán)左移， 其只是改變了矩陣的元素排 列順序，比如 vN1=sN1BN則有vb2bnb1=sb1b2bn,對于所 有的 b1,b2,bn 0,1。極化碼的產(chǎn)生極化碼的編碼與線性碼相同，在N=2n,n0的條件下，都可以用生成矩陣的形式進行：xN1=uN1GN(4)如果A是1,2,N的一個子矩陣，則式

9、(4)可以重寫為:xN1=uAGN(A)?uAcGN(Ac)(5)式中：GN(A)是矩陣GN的一個子集，它由A中數(shù)值決定的 GN的行元素矩陣構(gòu)成；uA是uN1中由A集合元素確定的子矢量； Ac是集合A的補集。因此，如果能夠確定集合A和子矢量uAc，就可以獲得信息uA的編碼碼字xN1。這就是GNM咅集編碼，此 編碼的參數(shù)是(N,K,A,uAc)。其中，K是集合A的大?。籏/N是編 碼速率；A被稱作信息集合，基于補集的 Ac的剩余uAc就稱作 休眠比特。因此，極化碼編碼的關(guān)鍵就是集合A和子矢量uAc的確定。根據(jù)第 1 節(jié)的敘述， 在合并信道中， 選擇對稱容量大的信道傳輸 信息，而對稱容量小的信道則

10、不用傳輸信息，用于休眠比特 (休 眠比特 frozen-bits 對于收、 發(fā)端都是已知的， 因此不失一般性 可以取比特0)。根據(jù)這樣的原則，在 N=8時，根據(jù)圖1的結(jié)果， 發(fā)現(xiàn) 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 ， 所以加上相應(yīng)位置的休眠比特，u81=(0,0,0,u4,0,u6,u7,u8) ，根據(jù)式 (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就確定了，此時可以根據(jù)漢明距離從大到小來選取A的值，同時也就確定了 uAc,完成編碼。2.3極化碼的SC譯碼對于參數(shù)為(N,K,A,uAc)的極化碼，輸入信息uN1(其中包括 K個信息比特和N-K個休眠比特)通過編碼成為N位的編碼碼字 xN1，該碼字通過合成信道 WN最后的輸出為yN1。譯碼器的任 務(wù)就是從已知的接收矢量 yN1中計算輸入信息uN1的估計值N1。 實際中，由于休眠比特對于收、發(fā)雙方都是已知的，因此真正需 要估計的比特數(shù)是 K個，對于休眠的比特則可以直接寫出Ac=uAc。 Korada 等人在研究二元加性高斯白噪聲信道時 8 ，把 休眠比特認為是已知的，可以作為信道估計序列使用。當Acm uAc 時就會產(chǎn)生錯誤碼字判決，最后形成誤碼字概率。Arikan 在研究中介紹了連續(xù)抵消譯碼器 (SuccessiveCancellation , SC)。對于參數(shù)為(N,K,A,uAc)的極化碼，基于SC譯碼器的第i個N1的判決量為：i=ui,for i Achi(yN1,i - 11),for i A(6)式中判決函數(shù) hi(yN1,i -11)的定義為：hi(yN1,i -11)=0, if W(i