信道極化與Polar碼構(gòu)造

唐嘉麒

(廣東省電信規(guī)劃設(shè)計院有限公司 移動咨詢設(shè)計院云南項目部，云南 昆明 630299)

?

信道極化與Polar碼構(gòu)造

唐嘉麒

(廣東省電信規(guī)劃設(shè)計院有限公司 移動咨詢設(shè)計院云南項目部，云南 昆明 630299)

摘要：極化碼是一種基于信道極化現(xiàn)象的容量可達的新型編碼技術(shù)。該文從信道極化原理入手，介紹信道極化現(xiàn)象及極化信道模型，詳細闡述了線性陪集的極化碼構(gòu)造方法，給出了串行抵消譯碼算法的具體實現(xiàn)流程和仿真結(jié)果。

關(guān)鍵詞：信道極化；極化碼；串行抵消譯碼算法

香農(nóng)第二定理指出，在有擾信道中，只要信息傳輸速率小于信道容量，就有可能實現(xiàn)任意可靠的信息傳輸。這個存在性定理揭示出，我們可以用接近信道容量的傳輸速率進行通信。香農(nóng)在證明該定理時，為了保證碼字本身具有很好的糾錯能力，采用了無窮碼長的隨機編碼的思想，同時采用最大似然譯碼算法充分發(fā)揮碼的糾錯性能。然而，這在實際中是無法實現(xiàn)的，因為采用隨機編碼會使碼長度趨于無窮大，而且采用最大似然譯碼算法進行譯碼會使系統(tǒng)的復(fù)雜度變高，在程序上難以實現(xiàn)[1]。

在隨后的研究中發(fā)現(xiàn)，最終能夠逼近香農(nóng)容量限的Turbo碼和LDPC碼，都部分使用了隨機編碼的思想[2]。LDPC碼以其瀑布區(qū)域良好的性能，已經(jīng)成為了新一代衛(wèi)星通信中的信道編碼方案。盡管這些信道編碼技術(shù)被統(tǒng)一納入因式圖的理論框架，采用迭代譯碼技術(shù)，能夠逼近香農(nóng)極限，具有優(yōu)越的糾錯性能。但其編譯碼的理論基礎(chǔ)尚不完備，如何證明這些碼具有漸進最優(yōu)性能非常困難[3]。2009年，Arikan提出信道極化碼(polar codes)的設(shè)計思想[4]，基于信道極化(channel polarization)現(xiàn)象，首次以構(gòu)造性的方法分析了編碼的漸進性能，引起了信息論與編碼學(xué)術(shù)界的極大關(guān)注。

Polar 碼是一種新的信道編碼方案，它是基于信道極化理論提出的一種線性分組碼。理論上，它在低譯碼復(fù)雜度下能夠達到信道容量且無錯誤平層[5]，而且當碼長N增大時，其優(yōu)勢會更加明顯。

1信道極化原理

Arikan針對一組獨立的二進制對稱輸入離散無記憶信道(B-DMC)，提出了采用編碼的方法，使各個子信道呈現(xiàn)出不同的可靠性，隨著碼長(即信道數(shù)目)的增加，這些子信道呈現(xiàn)兩極分化現(xiàn)象，稱為信道極化。研究發(fā)現(xiàn)，信道的極化現(xiàn)象是普遍存在的。

1.1信道參數(shù)

在信道極化的描述中，存在兩個極為重要的參數(shù)——對稱容量(Symmetriccapacity)和巴塔恰利亞系數(shù)(Bhattacharyyaparameter)，分別描述如下：

(1)

(2)

對稱容量表達的是信道的速率，而巴氏系數(shù)則反映了信道的可靠性。

1.2信道極化模型

假設(shè)B-DMC信道W：對于兩個信道極化，是信道的輸入比特，是信道的輸出比特，如圖1所示。

由圖1可以看出，數(shù)據(jù)在極化信道的傳輸分為編碼、傳輸兩個步驟。顯然，編碼部分存在如下關(guān)系：

(3)

四個信道的極化模型如圖2所示，其編碼關(guān)系由式(4)給出，G4是生成矩陣。

圖1　兩信道的極化模型

圖2　四信道的極化模型

(4)

值得注意的是，在圖2中顯然存在一個位置交換的結(jié)構(gòu)，稱為比特翻轉(zhuǎn)。因此，G4與F之間存在如下關(guān)系，其中BN是比特翻轉(zhuǎn)矩陣，運算F?F是克羅內(nèi)克積。

G4=B4F?2

(5)

推而廣之，當信道數(shù)目增加到N(=2n)時，生成矩陣可表達為

GN=BNF?n

(6)

1.3信道極化現(xiàn)象

(7)

(8)

2Polar碼構(gòu)造方法

Arikan提出了一種線性陪集的Polar碼構(gòu)造方法——從N個信道中選擇信道質(zhì)量較好的一部分作為信息傳輸信道，剩余部分作為凍結(jié)比特傳輸信道，并用式(9)完成編碼。

(9)

信道質(zhì)量可以采用1.1節(jié)中提出的對稱容量或者巴氏系數(shù)來衡量，Arikan采用的是后者。本文采用前者(BEC方法)來作為衡量指標，構(gòu)造任意碼率R的Polar編碼算法如下：

圖3　N=1 024時的信道極化現(xiàn)象

1)用式(7)及式(8)計算信道容量值I(W)；

2)將I(W)按值從大到小排序，排序過程中用標記數(shù)組flag記錄原信道的索引值，保持兩個數(shù)組同一下標記錄的值對應(yīng)同一個子信道；

3)flag中的前N×R個記錄就是該信道下需要找出的信息位下標，存入A中，剩余部分存入Ac中；

4)構(gòu)造生成矩陣GN，從中選取A所對應(yīng)的行構(gòu)造G(A)，其余部分構(gòu)造G(Ac)；

5)凍結(jié)比特序列uA，全部置0，用式(9)完成編碼。

值得注意的是，在構(gòu)造生成矩陣GN時，如果采用了比特翻轉(zhuǎn)，譯碼結(jié)果即為信息序列，否則在譯碼時則需比特翻轉(zhuǎn)。下面以ε=0.5，uA=(1，1，0，1)的Polar編碼為例，給出(8,4,A,(0,0,0,0))編碼的結(jié)果，其中A={4，6，7，8}。

(10)

3基于串行抵消(SC)的Polar譯碼算法的實現(xiàn)

(11)

(12)

(13)

圖4　SC譯碼算法流程

值得一提的是，圖4所示的算法中設(shè)計了一個位置標志序列z。該標記序列是一個二進制向量，明確指示了碼字中的信息位(“1”表示)和凍結(jié)位(“0”表示)。譯碼時當識別到某一位符號zi=0時，即認定為凍結(jié)位，對應(yīng)的比特直接譯碼為ui=0。由于在編碼過程中，采用了比特翻轉(zhuǎn)，其譯碼結(jié)果即為最終結(jié)果。

4Polar碼的可靠性評價

Polar碼是一種“容量可達”而非“逼近”的結(jié)構(gòu)化編碼方式，并且譯碼性能不存在錯誤平層。本節(jié)利用誤塊率(BlockErrorRatio,BLER)和巴氏系數(shù)來衡量Polar碼的SC譯碼可靠性。

(14)

(15)

假設(shè)碼率為R，碼長為N，信息信道的個數(shù)|A|=K=N×R，誤塊率的上下界可以分別由式(16)和(17)表示。

(16)

(17)

圖5給出了碼長分別為210、215、220時，刪除概率ε=1/2的BEC信道誤塊率上下界。顯然，當碼長增大時Polar碼是容量可達的。另外，如果碼率足夠小，采用SC譯碼實現(xiàn)容量可達的Polar碼是完全可行的。圖6給出了碼長為N=256時的誤塊率仿真曲線。

圖5　碼長分別為210、215、220時，刪除概率ε=1/2的BEC信道誤塊率

5結(jié)束語

Polar碼是一種依賴于信道極化現(xiàn)象的全新編碼方式，具有編譯碼簡單、可靠性高等特點，然而譯碼算法局限于串行譯碼的瓶頸。另外，Polar碼與LDPC碼和Turbo碼一樣，是基于有限域的編碼方法，其碼長也受到2n的限制。譯碼算法的并行化，碼長的自由化以及歐式域的編碼拓展已成為目前研究的重點。

圖6　碼長N=27時，刪除概率ε=1/2的BEC信道誤塊率

參考文獻：

[1]孫葉.基于SC算法的Polar碼譯碼性能研究[D].西安：西安電子科技大學(xué)，2013.

[2]李斌，王學(xué)東，王繼偉.極化碼原理及應(yīng)用[J].通信技術(shù)，2012，45(10)：21-23.

[3]李桂萍，任華，劉小航.信道極化與極化碼的研究進展與展望[J].科學(xué)技術(shù)與工程，2014，14(1)：132-138.

[4]ERDAL Arikan. Channel polarization：a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[J].IEEE Transactions on Information Theory，2009，55(7)：3 051-3 073.

[5]SARKIS Gabi，GIARD Pasca，VARDY Alexander，et al.Fastpolar decoders：algorithm and implementation[J].IEEE Journal on Selected Areas in Communications，2014，32(5)：946-957.

A Study on the Channel Polarization and Construction of the Polar Code

TANG Jiaqi

(Yunnan Mobile Support Center of Mobile Communications Consulting and Design Institute of Guangdong Planning and Designing Institute of Telecommunications Co., Ltd.，Kunming Yunnan650299，P.R.China)

Abstract：The polar code is a new capacity-achieving coding technology based on the channel polarization．Based on its principle，this article introduces the channel polarization and the polarized channel model，expounds the construction method of the polar code based on the linear coset，and gives the implementation process and simulation result of the successive cancellation decoding algorithm．

Key words：channel polarization；polar code；SC decoding algorithm

收稿日期：2015-10-30

作者簡介：唐嘉麒(1986-)，工程師，研究方向為無線通信技術(shù)。

中圖分類號：TN911.22

文獻標識碼：A

文章編號：1008-8032(2016)02-0049-04