摘 要：主要介紹了基于二元離散無(wú)記憶信道的極化碼的構(gòu)造以及相關(guān)性質(zhì)。極化碼不但能夠在離散對(duì)稱信道的條件下達(dá)到系統(tǒng)的對(duì)稱容量，而且編譯碼的復(fù)雜度和碼字長(zhǎng)度幾乎呈線性關(guān)系，即當(dāng)碼字長(zhǎng)度為N時(shí)，其復(fù)雜度約為O(Nlog N)。最后討論了極化碼的應(yīng)用以及研究熱點(diǎn)。



關(guān)鍵詞：極化碼; 信道極化; 生成矩陣; 譯碼器

中圖分類號(hào)：TN911.7-34

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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

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

0 引 言

最近幾年，無(wú)線通信發(fā)展得非常迅速，從3G到LTE，再到4G技術(shù)，系統(tǒng)的傳輸速率也從2M到幾十兆甚至數(shù)百兆。無(wú)線通信物理層中的信號(hào)處理技術(shù)相對(duì)發(fā)展較慢，從20世紀(jì)90年代的Turbo編碼、LDPC編碼以及MIMO多天線技術(shù)以來(lái)，更多的研究可能集中在認(rèn)知無(wú)線電、合作通信等熱點(diǎn)上，以至于有的研究者認(rèn)為未來(lái)的信號(hào)處理領(lǐng)域可能已經(jīng)走入困境[1]。

自2008年以來(lái)，E. Ankan等人研究了信道極化問(wèn)題，根據(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ù)雜度幾乎與編碼長(zhǎng)度呈線性關(guān)系。

本文主要介紹極化碼的構(gòu)造以及性質(zhì)，分析編碼長(zhǎng)度對(duì)極化碼信道選取的影響，同時(shí)也分析了極化碼近期的主要研究成果。

1 信道極化

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



圖2 2個(gè)WN/2信道的合并成WN示意圖

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

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)。當(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的方向趨近，這就是信道的極化過(guò)程，這也是極化碼的編碼基礎(chǔ)。

圖3 二元?jiǎng)h除信道(ε=0.5)在不同N的時(shí)候信道對(duì)稱容量

2 極化碼編、譯碼

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

2.1 極化碼的生成矩陣

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

An=AAn－1

(2)

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

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

GN=BNFn

(3)

式中：F=10

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

2.2 極化碼的產(chǎn)生

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

xN1=uN1GN

(4)

如果A是{1，2，…，N}的一個(gè)子矩陣，則式(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。 這就是GN-陪集編碼，此編碼的參數(shù)是(N，K，A，uAc)。其中，K是集合A的大小；K/N是編碼速率；A被稱作信息集合，基于補(bǔ)集的Ac的剩余uAc就稱作休眠比特。

因此，極化碼編碼的關(guān)鍵就是集合A和子矢量uAc的確定。根據(jù)第1節(jié)的敘述，在合并信道中，選擇對(duì)稱容量大的信道傳輸信息，而對(duì)稱容量小的信道則不用傳輸信息，用于休眠比特(休眠比特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)行。因此有下面的編碼過(guò)程：

由于編碼效率為1/2， 所以加上相應(yīng)位置的休眠比特，u81=(0，0，0，u4，0，u6，u7，u8)，根據(jù)式(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比較大時(shí)，在確定了編碼效率以后，則集合A的大小K就確定了，此時(shí)可以根據(jù)漢明距離從大到小來(lái)選取A的值，同時(shí)也就確定了uAc，完成編碼。

2.3 極化碼的SC譯碼

對(duì)于參數(shù)為(N，K，A，uAc)的極化碼，輸入信息uN1(其中包括K個(gè)信息比特和N-K個(gè)休眠比特)通過(guò)編碼成為N位的編碼碼字xN1，該碼字通過(guò)合成信道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)Ac≠uAc時(shí)就會(huì)產(chǎn)生錯(cuò)誤碼字判決，最后形成誤碼字概率。

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

i=ui，for i∈Ac

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

(6)

式中判決函數(shù)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 極化碼的特點(diǎn)

極化碼與傳統(tǒng)信道編碼的區(qū)別是，極化碼的編碼利用了信道極化條件，在進(jìn)行編碼的時(shí)候考慮了輸入和輸出之間的互信息，使得極化碼在保證性能的條件下可以達(dá)到信道的對(duì)稱速率。極化碼的主要特點(diǎn)有：

(1) 對(duì)于一個(gè)二元的離散無(wú)記憶信道，假設(shè)輸入/輸出間的平均互信息為I(W)，則當(dāng)系統(tǒng)的傳輸速率R

(2) 在編譯碼復(fù)雜度上，極化碼的復(fù)雜度幾乎與碼字長(zhǎng)度呈線性關(guān)系，是具有簡(jiǎn)單復(fù)雜度的編碼；

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

4 結(jié) 語(yǔ)

極化碼的出現(xiàn)引起了巨大的影響，很多研究者都進(jìn)行了相關(guān)的研究。不僅在信道編碼領(lǐng)域，有的研究者還在新源編碼領(lǐng)域進(jìn)行了相關(guān)的研究[8-10]。同時(shí)為了進(jìn)一步提高極化碼的應(yīng)用， 文獻(xiàn)［11］研究了以極化碼作為內(nèi)碼、RS作為外碼的級(jí)聯(lián)碼；也有人研究了多用戶信道、高斯信道等，隨著研究的深入將會(huì)有更多的實(shí)用成果出現(xiàn)。

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

參 考 文 獻(xiàn)

［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.



作者簡(jiǎn)介：

王軍選 男，1970年出生，陜西戶縣人，博士，副教授。主要研究方向?yàn)闊o(wú)線通信中的信號(hào)處理技術(shù)。