Polar碼編譯碼技術(shù)研究

魯信金，舒冰心，雷 菁

(國防科技大學(xué) 電子科學(xué)學(xué)院，湖南 長沙 410000)

0 引言

通信系統(tǒng)中信道干擾和噪聲總是影響系統(tǒng)的可靠性，信道編碼技術(shù)可用最小代價(jià)來提升通信系統(tǒng)可靠性。1948年，香農(nóng)(Claude Shannon)在《通信的數(shù)學(xué)理論》[1]中指出對(duì)于去認(rèn)定的信道容量，當(dāng)碼率小于其信道容量時(shí)，總是可以找到一種編碼方案使得碼長足夠大時(shí)，使用最大似然譯碼可使誤碼率任意小，這奠定了糾錯(cuò)編碼理論的基礎(chǔ)。此后，很多學(xué)者致力于研究設(shè)計(jì)出能夠逼近信道容量(也即香農(nóng)界)的實(shí)用編碼方案，如線性分組碼[2]、卷積碼[3]和代數(shù)幾何碼[4]。進(jìn)入20世紀(jì)90年代，信道編碼進(jìn)入了第一次快速發(fā)展的階段，研究的重點(diǎn)集中為Turbo碼[5]和LDPC碼[6]，隨后二者在實(shí)際的通信系統(tǒng)得到了廣泛的應(yīng)用和很深入的研究，雖然這兩種編碼沒有達(dá)到理論證明的香農(nóng)限，還具有很高的復(fù)雜度，但依然備受青睞。

近年來，無線通信物理層中的編碼領(lǐng)域發(fā)展較慢。在2009年，E.Arikan等人研究了信道極化問題，根據(jù)信道極化提出了極化碼[7]。不僅證明了極化碼在二進(jìn)制離散無記憶信道(Binary Discrete Memoryless Channel,BDMC)下，可以達(dá)到信道容量，還提出了具有低復(fù)雜度的編碼和譯碼方案。R.Moil和T.Tanaka[8]針對(duì)任意對(duì)稱二進(jìn)制無記憶信道提出了一個(gè)新的被證明可實(shí)現(xiàn)的編碼構(gòu)造方法。編碼構(gòu)造方面對(duì)于不同的信道，Bhattacharyya參數(shù)的計(jì)算和信息位選擇方法是不同的，而很多學(xué)者研究了很多適用于不同信道的信息位選擇的方法，如蒙特卡洛迫近法、密度演化構(gòu)造方法等。

對(duì)于信道編碼而言，譯碼算法的復(fù)雜度和性能至關(guān)重要。自極化碼提出后就受到大量學(xué)者對(duì)其譯碼算法進(jìn)行研究。目前polar碼譯碼算法主要有SC算法[9]、SCL算法[10]、CA-SCL算法[11]、BP算法[12]、SCAN算法[13]，以及各種算法的簡化版本[14-16]。其中SC算法最初由Arikan提出，但其在碼長有限長情形下，性能一般。SCL是SC算法性能提升的改進(jìn)版本，原理是在SC的基礎(chǔ)上提供了多條路徑；而CA-SCL是在SCL的基礎(chǔ)上對(duì)信息比特進(jìn)行了循環(huán)冗余校驗(yàn)，它通過簡單的校驗(yàn)就可以帶來性能的極大提升。目前基于CA-SCL譯碼算法，polar碼性能已經(jīng)優(yōu)于LDPC碼。SC、SCL以及CA-SCL算法均是硬輸出算法，即最終輸出的是0、1比特序列，而不是對(duì)應(yīng)的LLR值。為了在一些聯(lián)合設(shè)計(jì)中使用polar碼，就必須提供polar碼的軟輸出算法，即輸出對(duì)應(yīng)比特的LLR值。BP和SCAN算法就是軟輸出算法，由于BP和SCAN算法在消息傳遞和遞歸規(guī)則上不同，導(dǎo)致了兩種算法的譯碼延時(shí)和收斂速度不同。譯碼延時(shí)上，BP消息傳遞采用“洪水”規(guī)則[17]，SCAN采用類SC算法的串行消除規(guī)則，因此BP算法的譯碼延時(shí)好于SCAN算法。SCAN算法1次迭代就能達(dá)到稍好于SC算法的性能，一般而言，BP算法需要40～50次的迭代過程，而SCAN算法1次迭代就能達(dá)到稍好于SC算法的性能。性能上幾種算法排序?yàn)椋篊A-SCL>LDPC>SCL>BP=SCAN>SC。

從極化碼被廣泛關(guān)注研究之后，極化碼逐漸應(yīng)用在現(xiàn)代通信系統(tǒng)中以及不同信道場景中，如二進(jìn)制對(duì)稱信道、混合信道、非對(duì)稱信道、非二進(jìn)制信道、多址接入信道、并行信道、高斯信道以及瑞利信道等。

1 信道極化原理

polar碼的基本原理是信道極化。信道極化是這樣的一種現(xiàn)象：對(duì)二進(jìn)制對(duì)稱信道進(jìn)行特定的“組合”和“拆分”，則拆分后的“比特信道”將呈現(xiàn)極化現(xiàn)象，即一部分“比特信道”的對(duì)稱信道容量趨近于1，而其余部分“比特信道”的對(duì)稱信道信道容量趨近于0。如果發(fā)送端將源信息比特放置在“好的比特信道上”，而在“壞的比特信道上”放置固定比特(如0)，同時(shí)在接收端采用連續(xù)消除譯碼算法，在碼長N→∞ 時(shí)將可以達(dá)到信道容量。雖然基于二進(jìn)制離散無記憶信道提出了信道極化，但是信道極化的現(xiàn)象是普遍存在的，除B-DMC信道外其他信道也存在此現(xiàn)象，而信道極化包括信道組合和信道分解兩個(gè)重要過程，接下來對(duì)其進(jìn)行介紹。

1.1 信道組合

在物理信道W(y|x)上連續(xù)發(fā)送N個(gè)符號(hào)，若發(fā)送端對(duì)這N個(gè)符號(hào)進(jìn)行特定方式的組合，則等效于信道W的組合。

如圖1所示，對(duì)發(fā)送的信息源符號(hào)以一定方式進(jìn)行組合，并記組合后的信道為W2(y1,y2|u1,u2)，則：

W2(y1,y2|u1,u2)=W(y1|u1⊕u2)W(y2|u2)。

(1)

進(jìn)一步將兩個(gè)W2信道組合為W4信道，依次往復(fù)，直至遞歸到兩個(gè)WN/2信道組合為WN信道，如圖2所示。其中,RN是置換矩陣，其滿足RN:(v1,v2,…vN)→(v1,v3,…vN-1,v2,v4,…vN)。

圖1 W2信道Fig.1 Channel W2

圖2 WN信道Fig.2 Channel WN

1.2 信道拆分

(2)

可以將上式迭代的形式，保證極化碼的編碼和譯碼具有線性復(fù)雜度。圖3展示了N=8時(shí)，信道W8分解的過程：獨(dú)立的8個(gè)信道W通過信道組合之后可以得到一個(gè)信道W8，信道分解時(shí)，信道W8先分解為兩個(gè)相互獨(dú)立的信道W4，之后信道W4分解為兩個(gè)相互獨(dú)立的信道W2，最后信道W2分解為兩個(gè)相互獨(dú)立的信道W，因此信道分解是一個(gè)遞歸的過程。

圖3 N=8信道分解Fig.3 Channel decomposition(N=8)

1.3 信道極化定理

polar碼選擇在“比特信道”量為1的比特信道上發(fā)送信源信息(比特信道容量為0的比特信道上發(fā)送固定信息，如0)。當(dāng)信道W為二進(jìn)制刪除(Binary Erasure Channel，BEC)信道時(shí)，圖4是碼長N=210刪余概率ε=0.5時(shí)仿真結(jié)果圖，圖4(a)是信道極化現(xiàn)象的仿真，圖4(b) 是各信道容量占比統(tǒng)計(jì)柱狀圖。圖5是N=220，刪余概率ε=0.5時(shí)的仿真結(jié)果圖，圖6是N=220,刪余概率ε=0.3時(shí)的仿真結(jié)果圖。

(a) 信道極化

(b) 各信道容量占比統(tǒng)計(jì)柱狀圖圖4 N=210,ε=0.5時(shí)信道極化現(xiàn)象及各信道容量占比Fig.4 Channel polarization phenomenon and the proportion of each channel capacity when N=210,ε=0.5

(a) 極化現(xiàn)象

(b) 各信道容量占比圖5 N=220,ε=0.5時(shí)信道極化現(xiàn)象及各信道容量占比Fig.5 Channel polarization phenomenon and the proportion of each channel capacity when N=220,ε=0.5

(a) 極化現(xiàn)象

(b) 各信道容量占比圖6 N=220,ε=0.3時(shí)信道極化現(xiàn)象及各信道容量占比Fig.6 Channel polarization phenomenon and the proportion of each channel capacity when N=220,ε=0.3

圖4和圖5可以看出，當(dāng)ε=0.5時(shí)，隨著N的增大，信道容量為0和1的信道所占比例增大，信道極化的現(xiàn)象越來越明顯。由圖5和圖6對(duì)比可以看出，當(dāng)N=220，信道容量為0時(shí)的信道所占比例趨向于信道刪除概率ε的值，信道容量為1的信道所占比例趨于信道刪除概率1-ε，與上述定理所述一致。

基于信道極化的現(xiàn)象，選擇其中較好的信道，即信道容量趨向于I(W)的信道作為信息位傳輸數(shù)據(jù)，而較差的信道，即信道容量趨向于1-I(W)的信道作為凍結(jié)位。運(yùn)用該思想進(jìn)行極化碼的編碼和譯碼。

2 polar碼編碼構(gòu)造

polar碼碼長N→∞時(shí)，polar碼可達(dá)信道容量。而實(shí)際編碼過程中碼長N不可能趨于無窮，因此polar碼也不可能做到信道完全極化?？傆胁糠帧氨忍匦诺馈钡男诺廊萘拷橛?和1中間。因此確定對(duì)稱信道容量最大的K個(gè)“比特信道”是解決polar碼碼字構(gòu)造的主要問題；其次，生成矩陣決定了信道重組的形式，信道重組的形式作用于待發(fā)送信息上的函數(shù)運(yùn)算法則，經(jīng)典的極化編碼方案以二維核矩陣F=[1 0;1 1]為基底，迭代構(gòu)造生成矩陣。

2.1 生成矩陣

(3)

類似地，對(duì)于重組信道W4，其生成矩陣G4可以簡化為G2的矩陣形式：

(4)

其中，?為Kronecker內(nèi)積。繼而推算出任意生成矩陣的遞歸表達(dá)式，即生成矩陣GN：

GN=F?log2(N),

(5)

其中,F=G2。考慮到連續(xù)消除算法的譯碼順序，Arikan在生成矩陣中引入比特翻轉(zhuǎn)置換操作：對(duì)于任意正整數(shù)i，定義(b1,b2...,bn)為其二進(jìn)制表示，比特翻轉(zhuǎn)操作rvsl(i)=(bn...,b2,b1)，對(duì)于任意矢量(v0,v1...,vn-1)，其比特翻轉(zhuǎn)置換后的矢量為(vrvsl(0),vrvsl(1)...,vrvsl(n-1))，該操作可以用N×N維的置換矩陣BN表示。設(shè)BN中第i行第j列的元素為bi,j，則有：

(6)

則生成矩陣的一般形式為：

GN=BNF?log2(N)。

(7)

2.2 信息集

信息集是信息信道的索引集合，而信息信道的質(zhì)量通常由對(duì)稱容量及巴特查里亞因子所度量。對(duì)稱容量與巴特查里亞因子是信道性質(zhì)的相反描述度量，其中對(duì)稱容量的計(jì)算復(fù)雜度更高，因此巴特查里亞因子更多地應(yīng)用在實(shí)際系統(tǒng)中。在此，僅討論基于巴特查里亞因子的信息集選取準(zhǔn)則。

(8)

(9)

(10)

當(dāng)且僅當(dāng)物理信道為BEC時(shí)，式(8)及式(9)的等號(hào)成立，此時(shí)比特信道的巴特查里亞因子可迭代計(jì)算。但對(duì)于其他二進(jìn)制信道而言，比特信道的轉(zhuǎn)移概率計(jì)算復(fù)雜度較大，其巴特查里亞因子難以確定，當(dāng)前較為常用的處理方法為近似迭代法。近似迭代法針對(duì)不同物理信道重定義了巴特查里亞因子，并使用近似迭代準(zhǔn)則迭代計(jì)算比特信道的巴特查里亞因子。在此給出BSC、BAWGNC、BFC的巴特查理亞因子。

對(duì)于交叉概率為Pε的BSC，其巴特查理亞因子按原定義計(jì)算：

(11)

對(duì)于連續(xù)信道，其巴特查里亞因子的定義為積分函數(shù)：

(12)

對(duì)于二進(jìn)制加性高斯白噪聲(Binary AWGN,BAWGN)信道，根據(jù)定義計(jì)算其轉(zhuǎn)移概率，其中σ2為噪聲方差，調(diào)制方式為BPSK(Binary Phase Shift Keying)。

(13)

(14)

將式(13)與式(14)帶入式(12),可得：

(15)

對(duì)于二進(jìn)制衰落信道(Binary Fading Channel)，可將其近似為AWGN信道處理，則其轉(zhuǎn)移概率為：

(16)

(17)

(18)

2.3 polar碼編碼

polar碼實(shí)際上就是線性分組碼，因此其編碼過程和一般的線性分組碼一樣。不同的是一般的線性分組碼根據(jù)碼字漢明重量等挑選生成矩陣某些行(RM碼根據(jù)的是最大漢明重量)，而polar碼由信息比特集A確定生成矩陣的某些行。假設(shè)C為N比特長的碼字，UI為K比特信源信息，UF=0為N-K比特固定信息，則：

C=UGN×N=UIGK×N+UFG(N-K)×N,

(19)

其中，GN×N是polar碼生成矩陣，GK×N是根據(jù)信息比特集A中元素從GN×N中挑選的行組成矩陣。

3 polar碼譯碼

3.1 SC譯碼原理

(20)

判定準(zhǔn)則為：

(21)

(22)

如圖7所示，首先譯碼器計(jì)算標(biāo)號(hào)為1的點(diǎn)的左消息LLR值，而此時(shí)必須知道標(biāo)號(hào)為2和3點(diǎn)的LLR值，同理要計(jì)算2的LLR值應(yīng)計(jì)算4和5的LLR值，而3需要計(jì)算6和7的LLR值，而4、5、6、7的LLR值可以直接根據(jù)信道傳輸過來的LLR值直接進(jìn)行計(jì)算。通過以上遞歸過程則得到了1點(diǎn)的LLR值。此時(shí)先判定該點(diǎn)是否是固定比特，如果是固定比特則直接譯為0；如果是信息比特，則根據(jù)剛計(jì)算得到的LLR值進(jìn)行判決:LLR值大于0判為0、LLR值小于0判為1。同理直至SC譯碼器將u0～u7的LLR值全部計(jì)算出來，并判決得到比特值。

圖7 遞歸順序Fig.7 Recursive order

3.2 SCL譯碼算法

通過這種多路徑譯碼策略，極化碼在中短碼長下的誤碼性能得到顯著提高。當(dāng)L足夠大時(shí)，SCL算法的誤碼性能能夠接近于最大似然(ML)算法。但是隨著L的增加，SCL算法的復(fù)雜度也呈指數(shù)倍增長。其時(shí)間復(fù)雜度和空間復(fù)雜度均為O(LNlog2N)。所以，SCL算法僅適用于中短碼長的情況，當(dāng)碼長N和譯碼路徑數(shù)L足夠大時(shí)，高復(fù)雜度的SCL算法難以實(shí)現(xiàn)。

圖8 SCL譯碼Fig.8 SCL decoding

3.3 CA-SCL譯碼算法

CA-SCL算法相較于SCL算法而言，能夠大幅降低譯碼復(fù)雜度。其需要對(duì)所有得到的譯碼結(jié)果進(jìn)行校驗(yàn)，如果滿足校驗(yàn)，則從中選取轉(zhuǎn)移概率最大的譯碼路徑作為最終譯碼結(jié)果；CA-SCL算法本具有較低的時(shí)延，但由于引入了再編碼步驟，導(dǎo)致仍具有較大時(shí)延。然而，在時(shí)間復(fù)雜度以及空間復(fù)雜度上，CA-SCL算法相比于SCL算法都有較大改進(jìn)。

4 仿真與分析

此處采用經(jīng)典SC譯碼，選擇BEC、BSC、AWGN三種信道進(jìn)行仿真，仿真通過計(jì)算誤碼率來分析編譯碼方案的優(yōu)劣。

4.1 BEC信道下極化碼的仿真

4.1.1 不同刪除概率及不同碼率下

BEC信道刪除概率p表示信道中傳輸符號(hào)在接收端無法識(shí)別的概率大小，在極化碼中改變碼率R通過改變極化信道的選擇比例。圖9為碼長N=64時(shí)，誤碼率在刪除概率和碼率這兩個(gè)參數(shù)變化時(shí)的變化曲線。橫坐標(biāo)為刪除概率，不同顏色曲線對(duì)應(yīng)不同碼率R。

圖9 當(dāng)N=64時(shí)BER變化曲線Fig.9 BER change curve when N=64

由圖9可知，每一條曲線變化趨勢一致，隨著BEC信道刪除概率增大，誤碼率變大。這是因?yàn)樵诖a長N和碼率R固定時(shí)，隨著BEC信道刪除概率的增大，巴氏參數(shù)Z增大，信道極化現(xiàn)象變差，選擇用來傳輸信息的子信道參數(shù)Z也增大，所以誤碼率增大。

比較不同顏色的4條曲線，碼率R越大，誤碼率越大。這是因?yàn)楫?dāng)參數(shù)N及p一定時(shí)，極化信道巴氏參數(shù)Z的值確定。當(dāng)碼率R增大時(shí)，所選的子信道個(gè)數(shù)增大，此時(shí)會(huì)將參數(shù)Z較大的信道選擇為傳輸信息的信道，將不好的信道選做信息位，造成誤碼的增加。

4.1.2 不同碼長條件下

BEC信道中，碼長N值越大，極化現(xiàn)象越明顯，此時(shí)碼率R=0.5、刪除概率p=0.2，如圖10所示，隨著碼長N的增大，誤碼率明顯變小。這是因?yàn)楫?dāng)N值增大時(shí)，信道容量為0和1的信道總數(shù)增大，信道容量為其他值所占的總數(shù)減小，即極化的效果更加明顯，此時(shí)巴氏參數(shù)Z的值向著0和1兩個(gè)方向集中。所以當(dāng)碼長N增大時(shí)，選擇用來傳輸信息信道的巴氏參數(shù)值更趨向于0，所以誤碼率減小。

圖10 當(dāng)p=0.2,R=0.5時(shí)BER變化曲線Fig.10 BER change curve when p=0.2,R=0.5

4.2 BSC信道下極化碼的仿真

4.2.1 不同交叉概率下

BSC信道中信元符號(hào)按交叉概率的大小比例進(jìn)行翻轉(zhuǎn)。圖11為誤碼率在BSC信道交叉概率p變化時(shí)的變化曲線，此時(shí)碼長N=256和碼率R=0.1。橫坐標(biāo)為BSC信道的交叉概率，縱坐標(biāo)為誤碼率。

由圖11可知，隨著BSC信道交叉概率p的增大，誤碼率變大。很明顯，此次仿真的誤碼率與BEC信道具有相似的特性，故造成這種結(jié)果的原因也與其相似，可以總結(jié)為：在碼長N和碼率R固定時(shí)，隨著BSC信道交叉概率在0～0.5的范圍內(nèi)增大，巴氏參數(shù)Z增大，信道極化現(xiàn)象變差，選擇用來傳輸信息的子信道參數(shù)Z也增大，所以誤碼率增大。

圖11 當(dāng)N=256,R=0.1時(shí)BER變化曲線Fig.11 BER change curve when N=256,R=0.1

4.2.2 不同碼率下

取N=256，p=0.2，圖12為極化碼在不同的碼率條件下的誤碼率曲線。隨著碼率R的增大，誤碼率明顯變大。曲線的變化趨勢與BEC信道的結(jié)果相似，但從仿真結(jié)果可以看出,當(dāng)誤碼率小于0.15時(shí)，誤碼率才小于1/100。所以BSC信道中可用的碼率范圍很小，一個(gè)碼字可以傳輸?shù)男畔⒂邢?。BSC信道中不同碼長N的情況下，誤碼率與BEC信道具有相似性，隨著碼長N的增大，誤碼率明顯變小。

圖12 當(dāng)N=256,p=0.2時(shí)BER變化曲線Fig.12 BER change curve when N=256,p=0.2

4.3 AWGN信道下極化碼的仿真

雖然極化碼是基于B-DMC信道提出的，但信道極化現(xiàn)象卻是普遍存在的，基于前面提到的理論方法對(duì)高斯信道中的極化碼進(jìn)行仿真分析，采用BPSK調(diào)制，調(diào)制之后變?yōu)殡p極性的信號(hào)然后再傳送至信道，選用加性高斯白噪聲。在高斯信道中，需考慮參數(shù)信噪比SNR，其為高斯信道重要的衡量指標(biāo)。

4.3.1 不同信噪比下

圖13為誤碼率在信噪比變化時(shí)的變化曲線，此時(shí)碼長N=1 024，由圖可知，隨著信噪比的增大，誤碼率變小。

在高斯信道中，信噪比越大則信道條件越好，出錯(cuò)的概率越小，類似于BEC中的刪除概率。信噪比越大說明原始信道的條件越好，而高斯信道的極化依賴于信噪比，所以信噪比越大，極化效果件也越好，即巴氏參數(shù)Z的值越小。所以當(dāng)碼長N和碼率R一定時(shí)，選擇用來傳輸信息的子信道個(gè)數(shù)也就確定了，此時(shí)Z的大小就決定了選擇信道的質(zhì)量好壞。因此信噪比越大，信道的方差越小，極化信道參數(shù)Z越小，極化碼性能越好，誤碼率越小。

4.3.2 不同碼率條件下

極化碼是一種依賴于信道的信道編碼，所以信道確定時(shí)，信道極化的參數(shù)便隨之確定，此時(shí)碼率便是一個(gè)影響誤碼性能的變量。圖14為誤碼率在碼率變化時(shí)的變化曲線，此時(shí)碼長N=1 024。

圖14 當(dāng)N=1 024時(shí)BER變化曲線Fig.14 BER change curve when N=1 024

由圖14可知，隨著碼率R的減小，誤碼率也隨之變小。由于信道極化的參數(shù)已經(jīng)確定，選擇其中的信道都是好的信道。但當(dāng)R增大時(shí)，選擇傳輸信息的信道也會(huì)增多，這時(shí)不太好的信道會(huì)加入進(jìn)來，造成誤碼率的增大。

4.3.3 不同碼長條件下

碼長的值對(duì)信道極化現(xiàn)象有很重要的影響，從而影響誤碼性能。圖15為誤碼率在碼長變化時(shí)的變化曲線，此時(shí)碼率R=0.3，由圖可知，隨著碼長N的增大，誤碼率明顯變小。這與BEC信道中的情況類似，當(dāng)N值增大時(shí)，極化的效果更加明顯，選擇用來傳輸信息的信道巴氏參數(shù)Z的值，肯定比N值小時(shí)選出的信道Z值小，所以誤碼率減小。此外，不同的碼長N下，誤碼率隨信噪比的增大差距逐漸變大。

圖15 當(dāng)R=0.3時(shí)BER變化曲線Fig.15 BER change curve when R=0.3

5 結(jié)論

極化碼是通信領(lǐng)域?qū)碚撎剿鞯囊淮钨|(zhì)的飛躍，是編碼領(lǐng)域的里程碑，具有很高的研究價(jià)值。本文重點(diǎn)介紹了信道極化的原理和信道極化的現(xiàn)象，對(duì)信道極化中信道組合和信道分解兩部分進(jìn)行了詳細(xì)分析，并且進(jìn)一步研究了極化碼的編譯碼過程。雖然信道極化是基于二進(jìn)制對(duì)稱信道提出的，但是信道極化現(xiàn)象卻是普遍存在的，為此討論了不同信道中極化的計(jì)算方法以及編碼參數(shù)對(duì)誤碼率的影響。作為目前已知的唯一一種能夠被嚴(yán)格證明達(dá)到香農(nóng)限的信道編碼方法，極化碼可以應(yīng)用到許多領(lǐng)域，后續(xù)的研究還可以從很多方面進(jìn)行改進(jìn)。