極化碼的原理及分析

［］

1 引言

信道編碼技術(shù)是無線通信物理層的最核心的基礎(chǔ)技術(shù)之一，它的主要目的是使數(shù)字信號(hào)進(jìn)行可靠的傳遞。信道編碼技術(shù)通過在發(fā)送信息序列上增加額外的校驗(yàn)比特，并在接收端采用譯碼技術(shù)對(duì)傳輸過程中產(chǎn)生的差錯(cuò)進(jìn)行糾正，從而實(shí)現(xiàn)發(fā)送信息序列的正確接收。為了實(shí)現(xiàn)可靠的信號(hào)傳輸，編碼學(xué)家在過去的半個(gè)多世紀(jì)提出多種糾錯(cuò)碼技術(shù)如RS碼、卷積碼，Turbo碼等，并在各種通信系統(tǒng)中取得了廣泛的應(yīng)用[1]。我們知道LDPC是碼長足夠長時(shí)，是逼近香農(nóng)極限的。香農(nóng)極限即香農(nóng)第二定理通俗來說就是，在碼長R不大于信道容量C的情況下，存在一種能夠?qū)崿F(xiàn)信息的絕對(duì)可靠傳輸?shù)木幋a方案。而所謂香農(nóng)限就是同時(shí)滿足絕對(duì)可靠、R逼近C的理想情況。香農(nóng)第二定理并沒有告訴我們?nèi)绾芜M(jìn)行信道編碼，但是它指導(dǎo)著我們?nèi)ふ腋臃线@種理想狀態(tài)的編碼方案，從turbo碼到LDPC碼，越來越逼近這一理想，而極化碼的出現(xiàn)，在理論上實(shí)現(xiàn)了這一理想。2008年在國際信息論ISIT會(huì)議上，Arikan首次提出了信道極化的概念[2]，這種理想的編碼方案使我們能夠在一個(gè)噪聲信道中以理論上最小的差錯(cuò)率和最快的速度進(jìn)行信息傳輸。極化碼的編碼長度設(shè)計(jì)都是2的N次方，而目前航天器與地面計(jì)算機(jī)系統(tǒng)都是32位的比特計(jì)算與存儲(chǔ)，所以極化碼的特性也適合應(yīng)用于未來的衛(wèi)星領(lǐng)域。Polar碼具有明確而簡單的編碼及譯碼算法。該編碼因?yàn)閾碛薪Y(jié)構(gòu)簡單，譯碼復(fù)雜度低，而被國際移動(dòng)通信標(biāo)準(zhǔn)化組織3GPP確定為5G eMBB(增強(qiáng)移動(dòng)寬帶)場景的信道編碼技術(shù)方案，其中，Polar碼作為控制信道的編碼方案。本文將對(duì)極化碼的原理進(jìn)行闡述，研究其在二進(jìn)制信道下碼長，信道索引和信道極化現(xiàn)象的關(guān)系，并對(duì)連續(xù)刪除SC譯碼基于matlab下進(jìn)行了仿真實(shí)現(xiàn)，同時(shí)引入LDPC碼中BP譯碼和最小和BP譯碼，將這三種譯碼方式進(jìn)行了仿真對(duì)比。

2 信道極化

2.1 信道的參數(shù)與符號(hào)

極化碼是基于二進(jìn)制GF（2）構(gòu)造的，其中Px表示X的概率分布，Px,y表示聯(lián)合概率分布。表示行向量；表示由N個(gè)合成信道；表示將分解成N個(gè)子信道第i個(gè)子信道；信道轉(zhuǎn)移概率W(y|x)[3-4]。定義在二進(jìn)制DMC下信道容量和巴氏參數(shù)分別為I（W）和Z(W):

I(W)表示無錯(cuò)誤傳輸?shù)淖畲笮畔⑺俾?，Z(W)表示信道的可靠性。

2.2 信道的組合

信道組合就是將二進(jìn)制DMC信道遞歸操作組合起來形成WN,其中N=2n，n>=0。

當(dāng)n=0時(shí)，信道復(fù)制一次，有W1=W。當(dāng)n=1時(shí)，信道進(jìn)行組合得到信道W2，如圖1所示：

圖1 W2的信道組合

當(dāng)n=2時(shí)，信道進(jìn)行組合得到W4,如圖2所示：

圖2 W4的信道組合

當(dāng)n=3時(shí)，信道進(jìn)行組合得到W8，如圖3所示：

圖3 W8的信道組合示意圖

以此類推可以得到n=n-1時(shí)，組合信道WN,如圖4所示：

圖4 WN的信道組合示意圖

對(duì)輸入序列u進(jìn)行線性變換后可得到編碼序列x，其變換過程可用生成矩陣GN來表示

此時(shí)其信道的轉(zhuǎn)移概率為：

2.3 信道分裂

信道分裂是信道組合的逆過程，將合成信道WN再分解成N個(gè)二進(jìn)制輸入信道，其對(duì)應(yīng)的轉(zhuǎn)換概率為：

2.4 信道極化

信道極化是信道合并與信道分裂兩種信道操作的結(jié)果[4]。在上述兩種操作下，原本相同的N個(gè)W信道產(chǎn)生了極化現(xiàn)象，其中一部分信道容量趨于1，另一部分信道容量趨于0。

從圖可以看出當(dāng)刪除概率為0.5時(shí)，隨著編碼長度N的增加，信道極化形象越加明顯，圖中所有點(diǎn)呈中心對(duì)稱，當(dāng)信道索引號(hào)很小時(shí)，對(duì)稱信道容量趨近0；當(dāng)信道索引號(hào)很大時(shí)，對(duì)稱信道容量趨近于1。

由柱狀統(tǒng)計(jì)圖（6）中可以看出，當(dāng)N比較小時(shí)，趨于0或1的個(gè)數(shù)占總個(gè)數(shù)比例不高，當(dāng)N=32768時(shí)，信道容量0和1的數(shù)目比例都分別占到了大約49%。這就是信道極化現(xiàn)象。

3 極化碼的原理

3.1 極化碼編碼

首先聲明定義Kronecker(克羅內(nèi)克積)：

圖5 N=64，1024，32768時(shí)的信道容量

將式（8）帶入，可得：

3.2 SC譯碼

圖6 信道極化現(xiàn)象的柱狀統(tǒng)計(jì)圖

設(shè)定第i個(gè)信息比特ui對(duì)應(yīng)分裂信道為，通過該信道發(fā)出的信息，在接收端宜采用軟判決譯碼，計(jì)算對(duì)數(shù)似然比：

從上面推導(dǎo)過程中可以看出似然值的復(fù)雜度為N（1+logN）。

3.3 BP 譯碼

極化碼生成矩陣可以 用因子圖來表示，這樣就可以使用BP譯碼算法對(duì)其進(jìn)行譯碼【6,7,8】。BP譯碼就是通過節(jié)點(diǎn)之間相互傳遞信息，每個(gè)節(jié)點(diǎn)的更新公式如下：

其中g(shù)(x,y)=ln((1+xy)/(x+y))，從信源端發(fā)出的信息,與信息集和固定比特值選取有關(guān)：

最后一層信道端的信息，接收到的信息設(shè)置為：

達(dá)到最大迭代值時(shí)，停止迭代，并做出判決：

由以上譯碼過程可以看出，極化碼的BP譯碼算法作為一種并行的譯碼算法具有不錯(cuò)的譯碼性能。

3.4 最小和BP譯碼

雖然BP譯碼具有不錯(cuò)的性能，但在LDPC碼中我們可知其復(fù)雜度還是相對(duì)較高，因此，我們引入BP譯碼的改進(jìn)方式，最小和BP譯碼。其譯碼時(shí)的節(jié)點(diǎn)更新公式依舊如式（15）一樣。只是令其中g(shù)(x,y)=sign(x)sign(y)min(|x|,|y|),當(dāng)y時(shí)，sign(y)=0,否則sign(y)=1。其譯碼算法迭代過程如下：

輸入：接收矢量y;

迭代更新：對(duì)式15進(jìn)行迭代更新每個(gè)節(jié)點(diǎn)先從右向左進(jìn)行更新，到達(dá)最左側(cè)后再從左向右進(jìn)行更新，到達(dá)迭代最大值時(shí)停止更新。

最小和BP譯碼與BP譯碼方式最大的區(qū)別，在于判決處，BP的判決條件是否則。

4 仿真結(jié)果分析

圖7 不同碼長下極化碼的性能

在AWNG信道下，選取碼率為0.25，采用SC譯碼方式，分別選取不同碼長的極化碼，在matlab下對(duì)其進(jìn)行仿真，得到圖4.7.其中黑色的為碼長256，綠色為碼長512，紅色為碼長1024，藍(lán)色為碼長2048.從圖中可以看出，碼長越長性能越好。隨著SNR的逐漸增加，越加明顯。這是因?yàn)榇a長越長，有前面信道極化仿真可知，信道極化越加明顯，無躁信道的個(gè)數(shù)和比例都會(huì)顯著提高，所以性能就越加好。

在AWNG信道下，選取碼長為512，采用SC譯碼方式，分別選取不同碼率的極化碼，在matlab下對(duì)其進(jìn)行仿真，得到圖4.8.其中綠色為碼率0.25，黑色為碼率為0.5，紅色為碼率0.75。從圖中可以看出，碼率越小，極化碼的性能就越好，說明編碼效率直接影響碼字的好壞。因?yàn)榇a率越低，信道編碼對(duì)信道信息增加的冗余就越多，使得信息受到的保護(hù)就越多，因而性能就越好。所以編碼速率不同時(shí)，發(fā)送的信息越多性能越差，因?yàn)樾诺罉O化，其中一部分信道是完美的無噪信道，當(dāng)發(fā)送的信息多于好的信道個(gè)數(shù)時(shí)，就會(huì)導(dǎo)致其余部分信息在完全噪聲信道下發(fā)送，最終出現(xiàn)這種情況。所以，信息位的選擇很大程度上也與編碼速率有關(guān)，碼率越高，有效性越高，但可靠性就低；碼率越低，有效性就低，但信息傳輸可靠性就高。

圖8 不同碼率下極化碼的性能

圖9 不同碼長下極化碼的性能

在AWNG信道下，對(duì)極化碼采取不同譯碼方式，將LDPC碼中的BP譯碼和最小和譯碼方式引入，分別對(duì)其仿真，得到如圖4.9所示。在SNR約小于3.5時(shí)，SC譯碼性能好于兩種BP譯碼方式。當(dāng)SNR大于3.5時(shí)，兩種BP譯碼性能優(yōu)于SC譯碼。而BP譯碼性能始終優(yōu)于最小和BP譯碼方式。因?yàn)镾C譯碼是一種串行譯碼，而BP譯碼方式是一種并行譯碼方式，在碼長較大時(shí)，BP性能會(huì)優(yōu)越一些。但BP譯碼一般在硬件上實(shí)現(xiàn)比較復(fù)雜，所以一般都用最小和BP譯碼來近似，雖然降低了BP復(fù)雜度，但譯碼性能卻打了折扣。

5 總結(jié)

從代數(shù)編碼和概率編碼的角度來說，極化碼具備了兩者各自的特點(diǎn)。首先，只要給定編碼長度，極化碼的編譯碼結(jié)構(gòu)就唯一確定了，而且可以通過生成矩陣的形式完成編碼過程，這一點(diǎn)和代數(shù)編碼的常見思維是一致的。其次，極化碼在設(shè)計(jì)時(shí)并沒有考慮最小距離特性，而是利用了信道聯(lián)合（Channel Combination）與信道分裂（Channel Splitting）的過程來選擇具體的編碼方案，而且在譯碼時(shí)也是采用概率算法，這一點(diǎn)比較符合概率編碼的思想。

SC譯碼算法以LLR為判決準(zhǔn)則，對(duì)每一個(gè)比特進(jìn)行硬判決，按比特序號(hào)從小到大的順序依次判決譯碼。當(dāng)碼長趨近于無窮時(shí)，由于各個(gè)分裂信道接近完全極化（其信道容量或者為0或者為1）， 個(gè)消息比特都會(huì)獲得正確的譯碼結(jié)果，可以在理論上使得極化碼達(dá)到信道的對(duì)稱容量,而且SC譯碼器的復(fù)雜度僅為O(NlogN)和碼長呈近似線性的關(guān)系。然而，在有限碼長下，由于信道極化并不完全，依然會(huì)存在一些消息比特?zé)o法被正確譯碼。當(dāng)前面i-1個(gè)消息比特的譯碼中發(fā)生錯(cuò)誤之后，由于SC譯碼器在對(duì)后面的消息比特譯碼時(shí)需要用到之前的消息比特的估計(jì)值，這就會(huì)導(dǎo)致較為嚴(yán)重的錯(cuò)誤傳遞。因此，對(duì)于有限碼長的極化碼，采用SC譯碼器往往不能達(dá)到理想的性能。

為進(jìn)一步提高有限碼長極化碼的性能，相繼也提出了很多其它譯碼算法，SCL譯碼，CRC輔助SCL譯碼。通過多保留候選路徑篩選來保證譯碼的正確性，但相對(duì)SC譯碼，其復(fù)雜度會(huì)提高很多，消耗更多存儲(chǔ)空間。基于并行譯碼的置信傳播（BP）譯碼，在低時(shí)延條件下可以獲得比SC更好的性能。

極化碼想要得到更多應(yīng)用還要克服高速率通信下的時(shí)延和吞吐率問題，這是polar codes應(yīng)用上最大的問題。