極化碼及性質(zhì)

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

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

5、研究成果。信道極化對(duì)于二元離散無記憶信道 W(B-DMCV)，將N個(gè)獨(dú)立的信道W 按照一定的方式進(jìn)行合并，可以獲得長度為N的矢量信道，即有對(duì)于B-DMCWWJ:xNf yN,其中滿足 N=2n,n0,當(dāng)n=0時(shí),W仁W 圖 1 是 n=1 時(shí)的信道合成示意圖 1 。對(duì)于更一般的情況，由 N個(gè)信道W合成的信道為 WN WN可 以遞歸地由2個(gè)WN/2信道構(gòu)成，其中WN/2是由N/2個(gè)W信道合 并而成，具體如圖 1 所示1 。圖1 2個(gè)W信道的合并示意圖1其中，RN將sN1(sN1(s1,s2,sN)下面的標(biāo)識(shí)相同)映射為 vN1的線性變換。RN的實(shí)際操作就是對(duì)基于二進(jìn)制的元素序列編 號(hào)進(jìn)行循環(huán)右移

6、，只是改變了 sN1 的元素排列順序，比如 vN1=sN1RN則有vb1b2bn=sb2bn bl。對(duì)于所有的b1,b2,bn 0,1,其中vb1b2bn,sb2bnbl分別表示矢量 v和s的由二進(jìn)制表示的第 b1b2bn個(gè)和b2bnbl個(gè)元素。矩 陣變換RN的目的是保證合并信道輸出端的順序?yàn)?y1y2yN,如 果不適用該變換，則有可能輸出的順序會(huì)發(fā)生改變。?fe ?圖2 2個(gè)WN/2信道的合并成 WN示意圖用l(W(i)N)(i=1,2,N)表示N個(gè)W合并信道中第i個(gè)信道的對(duì)稱容量， 即為信息傳輸允許通過的最大速率。 信道對(duì)稱容 量的計(jì)算可以按照遞歸式 (1) 進(jìn)行：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)。當(dāng)信道是二元?jiǎng)h除信道時(shí)，有I(W)=1- ( 是二元?jiǎng)h除信道的刪除率)。圖3是當(dāng) =0.5時(shí)不同N的合并信道的對(duì)稱容量。從圖中可以看出，隨著N的增大，對(duì)稱 容量 I(W(i)N) 明顯地分別向 0或 1的方向趨近，這就是信道的極化過程，這也是極化碼的編碼基礎(chǔ)。圖3二元?jiǎng)h除信道( =0.5)在不同N的時(shí)候信道對(duì)稱容量極化碼編、譯碼極化碼的編碼類似于 RM(Reed-Muller) 碼，也屬于陪集碼的 范籌。極化碼的生成矩陣首先用表示 2 個(gè)矩陣的 Kronecker 積，

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

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

10、不用傳輸信息，用于休眠比特 (休 眠比特 frozen-bits 對(duì)于收、 發(fā)端都是已知的， 因此不失一般性 可以取比特0)。根據(jù)這樣的原則，在 N=8時(shí)，根據(jù)圖1的結(jié)果， 發(fā)現(xiàn) I(W(i)N)0.6(i=4,6,7,8) ，所以可以選擇 A=4,6,7,8 ， 此時(shí)K=4,因此編碼速率為 K/N=4/8=1/2。休眠比特的選取則也 按照A集合的元素進(jìn)行。因此有下面的編碼過程：由于編碼效率為 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 比較大時(shí)，在確

12、定了編碼效 率以后，貝V集合A的大小K就確定了，此時(shí)可以根據(jù)漢明距離從大到小來選取A的值，同時(shí)也就確定了 uAc,完成編碼。2.3極化碼的SC譯碼對(duì)于參數(shù)為(N,K,A,uAc)的極化碼，輸入信息uN1(其中包括 K個(gè)信息比特和N-K個(gè)休眠比特)通過編碼成為N位的編碼碼字 xN1，該碼字通過合成信道 WN最后的輸出為yN1。譯碼器的任 務(wù)就是從已知的接收矢量 yN1中計(jì)算輸入信息uN1的估計(jì)值N1。 實(shí)際中，由于休眠比特對(duì)于收、發(fā)雙方都是已知的，因此真正需 要估計(jì)的比特?cái)?shù)是 K個(gè)，對(duì)于休眠的比特則可以直接寫出Ac=uAc。 Korada 等人在研究二元加性高斯白噪聲信道時(shí) 8 ，把 休眠比特認(rèn)為是已知的，可以作為信道估計(jì)序列使用。當(dāng)Acm uAc 時(shí)就會(huì)產(chǎn)生錯(cuò)誤碼字判決，最后形成誤碼字概率。Arikan 在研究中介紹了連續(xù)抵消譯碼器 (SuccessiveCancellation , SC)。對(duì)于參數(shù)為(N,K,A,uAc)的極化碼，基于SC譯碼器的第i個(gè)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