極化碼及性質

摘 要：主要介紹了基于二元離散無記憶信道的極化碼的構造以及相關性質。極化碼不但能夠在離散對稱信道的條件下達到系統的對稱容量，而且編譯碼的復雜度和碼字長度幾乎呈線性關系，即當碼字長度為N時，其復雜度約為O(Nlog N)。最后討論了極化碼的應用以及研究熱點。



關鍵詞：極化碼; 信道極化; 生成矩陣; 譯碼器

中圖分類號：TN911.7-34

文獻標識碼：A

文章編號：1004-373X(2012)01-0065-03

Polar code and its characters



WANG Jun-xuan， ZHANG Yan-yan

(School of Communication and Information Engineering， Xi’an University of Post and Telecommunications， Xi’an 710121， China)



Abstract：

The construction and characteristics of polar code with binary discrete memoryless channel (BDMC) are introduced. 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; channel polarization; general matrix; decoder





收稿日期：2011-09-10

基金項目：陜西省教育廳科技項目(09JK726)

0 引 言

最近幾年，無線通信發展得非常迅速，從3G到LTE，再到4G技術，系統的傳輸速率也從2M到幾十兆甚至數百兆。無線通信物理層中的信號處理技術相對發展較慢，從20世紀90年代的Turbo編碼、LDPC編碼以及MIMO多天線技術以來，更多的研究可能集中在認知無線電、合作通信等熱點上，以至于有的研究者認為未來的信號處理領域可能已經走入困境[1]。

自2008年以來，E. Ankan等人研究了信道極化問題，根據信息論的相關理論，基于二元離散對稱信道構造了所謂的人造虛擬信道，類似于信息論中的信源擴展；發現隨著人造信道擴展維數N的增加，信道的對稱容量(平均互信息)分別趨近于0或1。在此基礎上，E.Ankan等人構造了極化碼(Polar Code)[2-4]，基本的思想就是當信道對稱容量較好時可以傳輸信息，當對稱容量接近于0的時候則不在該信道傳輸信息。這樣構造的極化碼就可以達到信道的對稱容量，而且具有較好的復雜度[5-7]，即編碼和譯碼的復雜度幾乎與編碼長度呈線性關系。

本文主要介紹極化碼的構造以及性質，分析編碼長度對極化碼信道選取的影響，同時也分析了極化碼近期的主要研究成果。

1 信道極化

對于二元離散無記憶信道W(B-DMC W)，將N個獨立的信道W按照一定的方式進行合并，可以獲得長度為N的矢量信道，即有對于B-DMC W，WN:xN→yN，其中滿足N=2n，n≥0，當n=0時，W1=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的實際操作就是對基于二進制的元素序列編號進行循環右移，只是改變了sN1的元素排列順序，比如vN1=sN1RN，則有vb1b2…bn=sb2…bnb1。對于所有的 b1，b2，…，bn∈{0，1}，其中vb1b2…bn，sb2…bnb1分別表示矢量v和s的由二進制表示的第b1b2…bn個和b2…bnb1個元素。矩陣變換RN的目的是保證合并信道輸出端的順序為y1y2…yN，如果不適用該變換，則有可能輸出的順序會發生改變。



圖2 2個WN/2信道的合并成WN示意圖

用I(W(i)N)(i=1，2，…，N)表示N個W合并信道中第i個信道的對稱容量，即為信息傳輸允許通過的最大速率。信道對稱容量的計算可以按照遞歸式(1)進行：

I(W(2i－1)N)=I(W(i)N/2)2

I(W(2i)N)=2I(W(i)N/2)－I(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的時候信道對稱容量

2 極化碼編、譯碼

極化碼的編碼類似于RM(Reed-Muller)碼，也屬于陪集碼的范籌。

2.1 極化碼的生成矩陣

首先用表示2個矩陣的Kronecker 積，則Kronecker的n次方就可以定義為：

An=AAn－1

(2)

式中對于所有的n≥1，A0［1］。

極化碼的生成矩陣是極化碼編碼的關鍵。對于N=2n，n≥0，定義極化碼的生成矩陣為：

GN=BNFn

(3)

式中：F=10

11;BN是一個線性變換矩陣，類似于第1節的RN，是基于二進制的元素序列編號進行循環左移，其只是改變了矩陣的元素排列順序，比如vN1=sN1BN，則有vb2…bnb1=sb1b2…bn，對于所有的 b1，b2，…，bn∈{0，1}。

2.2 極化碼的產生

極化碼的編碼與線性碼相同，在N=2n，n≥0的條件下，都可以用生成矩陣的形式進行：

xN1=uN1GN

(4)

如果A是{1，2，…，N}的一個子矩陣，則式(4)可以重寫為:

xN1=uAGN(A)⊕uAcGN(Ac)

(5)

式中：GN(A)是矩陣GN的一個子集，它由A中數值決定的GN的行元素矩陣構成；uA是 uN1中由A集合元素確定的子矢量；Ac是集合A的補集。因此，如果能夠確定集合A和子矢量uAc，就可以獲得信息uA的編碼碼字xN1。 這就是GN-陪集編碼，此編碼的參數是(N，K，A，uAc)。其中，K是集合A的大小；K/N是編碼速率；A被稱作信息集合，基于補集的Ac的剩余uAc就稱作休眠比特。

因此，極化碼編碼的關鍵就是集合A和子矢量uAc的確定。根據第1節的敘述，在合并信道中，選擇對稱容量大的信道傳輸信息，而對稱容量小的信道則不用傳輸信息，用于休眠比特(休眠比特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=BNF3=1 0 0 0 0 0 0 0

1 0 0 0 1 0 0 0

1 1 0 0 0 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 0 0 0 0

1 0 1 0 1 0 1 0

1 1 1 1 0 0 0 0

1 1 1 1 1 1 1 1

所以編碼后的碼字:

x81=u81GN=(0，0，0，u4，0，u6，u7，u8)1 0 0 0 0 0 0 0

1 0 0 0 1 0 0 0

1 1 0 0 0 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 0 0 0 0

1 0 1 0 1 0 1 0

1 1 1 1 0 0 0 0

1 1 1 1 1 1 1 1

在該例中，選取的編碼矩陣的行矢量的漢明距離都是比較大的，要么為8，要么為4，所以在N比較大時，在確定了編碼效率以后，則集合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]，把休眠比特認為是已知的，可以作為信道估計序列使用。當Ac≠uAc時就會產生錯誤碼字判決，最后形成誤碼字概率。

Arikan在研究中介紹了連續抵消譯碼器(Successive Cancellation，SC)。對于參數為(N，K，A，uAc)的極化碼，基于SC譯碼器的第i個N1的判決量為：

i=ui，for i∈Ac

hi(yN1，i－11)，for i∈A

(6)

式中判決函數hi(yN1，i－11)的定義為：

hi(yN1，i－11)=0， if W(i)N(yN1，i－11|0)W(i)N(yN1，i－11|1)≥1

1，otherwise

(7)

3 極化碼的特點

極化碼與傳統信道編碼的區別是，極化碼的編碼利用了信道極化條件，在進行編碼的時候考慮了輸入和輸出之間的互信息，使得極化碼在保證性能的條件下可以達到信道的對稱速率。極化碼的主要特點有：

(1) 對于一個二元的離散無記憶信道，假設輸入/輸出間的平均互信息為I(W)，則當系統的傳輸速率R

(2) 在編譯碼復雜度上，極化碼的復雜度幾乎與碼字長度呈線性關系，是具有簡單復雜度的編碼；

(3) 極化碼具有良好的無碼字性能，而且隨著碼字長度N的增加，錯誤率迅速下降。

4 結 語

極化碼的出現引起了巨大的影響，很多研究者都進行了相關的研究。不僅在信道編碼領域，有的研究者還在新源編碼領域進行了相關的研究[8-10]。同時為了進一步提高極化碼的應用， 文獻［11］研究了以極化碼作為內碼、RS作為外碼的級聯碼；也有人研究了多用戶信道、高斯信道等，隨著研究的深入將會有更多的實用成果出現。

作為一個新出現的技術，還有很多的研究需要進行，特別是在譯碼上，找到一個合適可行并且有效的譯碼算法就十分迫切，已經有學者研究了在LDPC中的BP算法以及改進的線性處理BP(Linear Processing)算法。在實際的應用上可能還有一段路要走，但是極化碼出色的性能會引起越來越多的研究者注意，會加速它的使用。

參 考 文 獻

［1］DOHLER M， HEATH R W， LOZANO A， et al. Is the PHY layer dead? [J]. Communications Magazine， IEEE， 2011， 49(4): 159-165.



［2］ANKAN E. Channel polarization: a method for constructing capacity achieving codes for symmetric binary-input memory less channels [J]. IEEE Trans. Inform. Theory， 2009， 55(7): 3051-3073.



［3］ANKAN E. A performance comparison of polar codes and Reed-Muller codes [J]. IEEE Commun. Lett.， 2008，12(6): 447-449.



［4］SASOGLU E， TELATAR E， ARIKAN E. Polarization for arbitrary discrete memoryless channels [C]// Information Theory Workshop. Taormina： IEEE， 2009: 144-148.



［5］TELATAR Emre. Polar coding: a brief tour [C]// 2010 International Conference on Signal Processing and Communications (SPCOM)， Lausanne， Switzerland: IEEE， 2010: 1-2.



［6］MARI Ryuhei， TANAKA Toshiyuki. Performance and construction of polar codes on symmetric binary-input memoryless channels [C]// ISIT 2009. Seoul， Korea: IEEE， 2009:1496-1500.



［7］KORADA Satish Babu， SASOGLU Eren， URBANKE Rüdiger. Polar codes: characterization of exponent， bounds， and constructions [J]. IEEE Transaction on Information， 2010， 56(12):6253-6264.



［8］KORADA Satish Babu. Polar codes for channel and source coding [D]. [S.l.]: Ecole Polytechnique Fédérale de Lausanne (EPFL)， 2009.



［9］GOELA Naveen， KORADA Satish Babu， GASTPAR Michael. On LP decoding of polar codes [C]// 2010 IEEE Information Theory Workshop. Dublin: IEEE， 2010: 1-5.



［10］BAKSHI Mayank， JAGGI Sidharth， EFFROS Michelle， Concatenated polar codes [C]// 2010 IEEE International Symposium on Information Theory Proceedings (ISIT). Pasadena， CA， USA: IEEE， 2010: 918-922.



［11］ARIKAN Erdal. Source polarization [C]// 2010 IEEE International Symposium on Information Theory Proceedings (ISIT). Pasadena， CA， USA: IEEE， 2010: 899-903.



作者簡介：

王軍選 男，1970年出生，陜西戶縣人，博士，副教授。主要研究方向為無線通信中的信號處理技術。