系統(tǒng)極化碼與非系統(tǒng)極化碼的研究現(xiàn)狀與發(fā)展趨勢

王秀敏,吳卓鋌,李 君,洪 波,汪曉鋒

(中國計量大學(xué) 信息工程學(xué)院,浙江 杭州 310018)

極化碼[1]是由Arikan提出的一種基于信道極化的信道糾錯碼,其在理論上被證明可達到香濃極限.極化碼相比目前被廣泛應(yīng)用的LDPC和Turbo碼有著更好的性能以及更低的復(fù)雜度,這使得極化碼成為當(dāng)前的一個研究熱點.極化碼分為非系統(tǒng)極化碼與系統(tǒng)極化碼.非系統(tǒng)極化碼[1]首先被Arikan提出并作為標(biāo)準(zhǔn)的極化碼.非系統(tǒng)極化碼以一串包含著信息位和凍結(jié)位的信息比特作為輸入信息輸入到編碼結(jié)構(gòu)中,編碼后的碼字不存在原始的信息位.非系統(tǒng)極化碼編碼之后的碼字中,信息位與校驗位相互交替,這使得非系統(tǒng)極化碼在譯碼后還需要另外找出相應(yīng)的信息[2].為了提高極化碼的性能,解決非系統(tǒng)極化碼的缺陷,Arikan提出了系統(tǒng)極化碼[3].系統(tǒng)極化碼與非系統(tǒng)極化碼主要不同之處在于,系統(tǒng)極化碼具備兩個輸入信號,這兩個信號分別從編碼結(jié)構(gòu)的兩端輸入.系統(tǒng)極化碼的輸出碼字中包含了原始的信息位.Arikan在文獻[3]中認(rèn)為系統(tǒng)極化碼在SC譯碼中的誤碼率比非系統(tǒng)極化碼低,且其編碼的硬件復(fù)雜度理論上與非系統(tǒng)極化碼相同.

本文首先介紹了非系統(tǒng)極化碼與系統(tǒng)極化碼的編碼方法.其次介紹現(xiàn)有的基于流水線方法的部分并行非系統(tǒng)極化碼編碼器的硬件實現(xiàn)方法.接著主要從遞歸與非遞歸、并行設(shè)計的角度介紹系統(tǒng)極化碼的硬件實現(xiàn)方案,并對不同方案進行對比與總結(jié).在介紹完硬件實現(xiàn)方案后,本文通過Matlab仿真驗證系統(tǒng)極化碼與非系統(tǒng)極化碼在SC譯碼、SCL譯碼以及BP譯碼條件下的性能差異.最后,通過總結(jié)前面分析的內(nèi)容,探討了系統(tǒng)極化碼與非系統(tǒng)極化碼各自的重要性并提出了一種基于生成矩陣簡化的研究方向.

1 極化碼編碼算法

1.1 非系統(tǒng)極化碼

根據(jù)文獻[1]中對非系統(tǒng)極化碼的定義,令極化碼碼長為N,核矩陣F=[1,0;1,1],極化碼的生成矩陣GN可由核矩陣F通過n(n=log2N)階克羅內(nèi)克積(Kronecker Product)運算得到,該運算用符號?表示,即

GN=F?n.

(1)

令U為未編碼的信息序列,X為編碼后的信息序列.對于非系統(tǒng)極化碼,序列U中包含了全部的信息位與凍結(jié)位.圖1為N=8的非系統(tǒng)極化碼編碼結(jié)構(gòu)圖[1],圖中黑色圓點為凍結(jié)位.u1～u7作為極化碼結(jié)構(gòu)的輸入信息,其中u1、u3、u5、u6、u7為信息位,u0、u2、u4為凍結(jié)位.經(jīng)過編碼運算得出編碼后的序列x0～x7,即有

X=U·G.

(2)

非系統(tǒng)極化碼的編碼過程與傳統(tǒng)的線性分組碼類似,編碼序列X由未編碼序列U與生成矩陣G進行模二累加和獲得.所不同的是,非系統(tǒng)極化碼編碼后的序列不包含原始信息比特.

圖1 8位非系統(tǒng)極化碼結(jié)構(gòu)圖Figure 1 Eight-bit non-system polar encoder structure

1.2 系統(tǒng)極化碼

系統(tǒng)極化碼與非系統(tǒng)極化碼在編碼階段與譯碼階段都存在著差異.編碼階段,系統(tǒng)極化碼同時由編碼結(jié)構(gòu)的兩端輸入X與U.如圖2所示,根據(jù)文獻[3]中定義,設(shè)信息位下標(biāo)為A={1,3,5,6,7},凍結(jié)位下標(biāo)為B={0,2,4}.則編碼結(jié)構(gòu)左邊的輸入U被分為兩部分U={uA,uB},相對應(yīng)的,X被分為X={xA,xB}.文獻[3]中的編碼過程可表示為式(3)和式(4):

xA=uA·GAA+uAc·GAcA,

(3)

xB=uA·GAB+uB·GBB.

(4)

其中：GN=[GAA,GAB;GBA,GBB];GAA、GAB、GBA以及GBB分別為GN的一個子矩陣.這些子矩陣分別以A和B作為行列索引從矩陣GN中所得到.例如GAB是由矩陣GN以A作為行索引B作為列索引組成的,即GAB={Gmn:m∈A,n∈B}.式(3)、(4)中,uB存放凍結(jié)位信息,xA存放信息位信息,uA與xB為方程中的未知量,系統(tǒng)極化碼的編碼算法即求出其中的未知量xB.文獻[4]中指出,根據(jù)矩陣運算法則,只要GAA可逆,xB可表示為式(5).由于GN是一個上三角形矩陣,上述求解xB的過程可通過高斯消去法進行求解.高斯消去法所消耗的計算單元為3log2N,其計算單元消耗遠遠高于Arikan所提到的理論值Nlog2N[3].

(5)

圖2 8位系統(tǒng)極化碼結(jié)構(gòu)圖Figure 2 Eight-bit system polar encoder structure

在譯碼階段,非系統(tǒng)極化碼譯碼時直接輸出譯碼最后的判決結(jié)果.而系統(tǒng)極化碼在譯碼得到譯碼判決結(jié)果后,還要將判決結(jié)果進行一次非系統(tǒng)極化碼的編碼運算,其作用可理解為一種極化碼編碼判決[5].

系統(tǒng)極化碼在文獻[3]中被證明其誤碼糾錯性能優(yōu)于非系統(tǒng)極化碼,但系統(tǒng)極化碼的雙向編碼結(jié)構(gòu)增加了其硬件實現(xiàn)的復(fù)雜度.另一方面,系統(tǒng)極化碼譯碼輸出判決階段還要進行一次非系統(tǒng)極化碼編碼,這使得系統(tǒng)極化碼的輸出延遲比非系統(tǒng)極化碼高.

2 極化碼編碼硬件實現(xiàn)方案的研究現(xiàn)狀

2.1 非系統(tǒng)極化碼硬件實現(xiàn)方案

Arikan在文獻[1]中給出了一種完全并行的非系統(tǒng)極化碼的編碼結(jié)構(gòu).如圖1,當(dāng)編碼信息碼長為N時,該編碼結(jié)構(gòu)被分為n層(n=log2N).一次編碼同時輸入N比特信息進行一次性編碼并輸出N比特編碼后碼字.其計算復(fù)雜度為θ(N·log2N),系統(tǒng)延遲約為n個模二運算的總和.可以看出,隨著碼長的增加,該編碼器的計算復(fù)雜度和系統(tǒng)延遲增大趨勢明顯,這不利于長碼長編碼.而文獻[1]中又指出,極化碼碼長越長其糾錯性能越好.這表明要在實際應(yīng)用中獲得更好的極化碼糾錯性能,如何從硬件上降低極化碼編碼器在長碼長下的硬件復(fù)雜度和系統(tǒng)延遲將是一個關(guān)鍵的問題.

針對長碼長非系統(tǒng)極化碼編碼,文獻[6]提出了一種部分并行的極化碼編碼方案.該方案充分利用了編碼結(jié)構(gòu)同一層數(shù)據(jù)的計算不相互依賴的特性,利用流水線方法將原本的全并行輸入結(jié)構(gòu)改為部分并行輸入.對于全并行輸入,假設(shè)輸入數(shù)據(jù)所需的時間為t1,系統(tǒng)編碼過程所需時間為t2,則系統(tǒng)的總延遲為(t1+t2).文獻[6]中假設(shè)每個分段數(shù)據(jù)輸入的時間為t3(t3

目前,非系統(tǒng)極化碼已經(jīng)具備相對成熟的硬件實現(xiàn)基礎(chǔ),由于非系統(tǒng)極化碼的編碼結(jié)構(gòu)與快速傅里葉變換的結(jié)構(gòu)非常類似,文獻[7]借鑒FFT算法設(shè)計出了等價于核矩陣F運算結(jié)構(gòu)的PE2,以及并行度為4的PE4.該編碼器巧妙地運用先進先出結(jié)構(gòu)(FIFO)來實現(xiàn)極化碼結(jié)構(gòu)中不同部分的輸入順序轉(zhuǎn)換.如表1所示為上述方法與文獻[1]在碼長分別為1 024、4 096以及163 884時的資源消耗情況.圖3給出了部分并行編碼器[7]在碼長為8 192與基于PE2設(shè)計的編碼器[6]在碼長為16 384時的吞吐率以及單位并行度吞吐率(NT)柱形對比圖.

表1 計算單元消耗對比圖

圖3 吞吐率與NT對比圖Figure 3 Throughput rate and NT

從表1與圖3中可看出,文獻[6]與文獻[7]中設(shè)計的編碼器相對于Arikan在文獻[1]中設(shè)計的編碼器在計算單元消耗方面有著顯著改進.令文獻[7]設(shè)計的編碼器為Encoder 1,文獻[6]中設(shè)計的編碼器為編碼器Encoder 2.則由于Encoder 1中對PE2或PE4有著極高的重復(fù)利用率,使得其計算單元消耗小于Encoder 2.另一方面,雖然Encoder 2中的編碼整體吞吐率比Encoder 1高,但其單位并行度吞吐率(NT)相對較低.這說明了在相同并行度的條件下Encoder 1的吞吐率性能優(yōu)于Encoder 2.隨后基于PE2的16路并行編碼器在文獻[8]中被提出,該編碼器在碼長為8 192時吞吐率可達160 Gb/s.表明了16路并行下的PE2的吞吐率性能遠遠高于Encoder 2的性能.從以上幾種非系統(tǒng)極化碼的編碼方案中可以看出,非系統(tǒng)極化碼的編碼技術(shù)改進主要是通過分割編碼結(jié)構(gòu),將原本一步完成的工作分成幾步完成,雖然這減少編碼過程中每一步的運算時間,提高了工作頻率的上限,但這將使得編碼器在運行初期的數(shù)十個周期內(nèi)輸出無意義的信號,以致降低了系統(tǒng)工作的整體穩(wěn)定性.

2.2 系統(tǒng)極化碼硬件實現(xiàn)方案

系統(tǒng)極化碼在編碼過程中需要進行雙向來回運算,這使得上述非系統(tǒng)極化碼編碼方案無法直接適用于系統(tǒng)極化碼.另外,雙向運算大大增加了系統(tǒng)極化碼的硬件復(fù)雜度.降低系統(tǒng)極化碼硬件實現(xiàn)的復(fù)雜度,提高系統(tǒng)極化碼的編碼效率將是系統(tǒng)極化碼的主要優(yōu)化方向.在復(fù)雜度方面,目前主要的優(yōu)化方法有遞歸編碼與非遞歸編碼[4].而在編碼效率方面,主要采用部分并行流水線方法.

2.2.1 遞歸編碼與非遞歸編碼

遞歸編碼結(jié)構(gòu)首先由Arikan在文獻[3]中提出,文獻[4]中提出了遞歸編碼結(jié)構(gòu)的硬件實現(xiàn)方法.系統(tǒng)極化碼遞歸編碼將u與x進行L(L=log2N)次的分裂.文獻[4]將分裂后的信息表示為式(6)和式(7)：

(6)

(7)

rl,2i-1=rl-1,i

(8)

(9)

u′=x′+r.

(10)

其中:u′和x′分別為u和x中的一個元素.已知系統(tǒng)極化碼中u與x中相同下標(biāo)的兩個元素有且僅有一個已知值,故上述等式只要求得r值,便可根據(jù)u′求x′或者根據(jù)x′求u′.

該算法中,僅需要計算并存儲二叉樹圖中每一級的rli值便可通過(10)得到編碼碼字.故該方法僅需2N-1個存儲單元分別存儲二叉樹中的每一個節(jié)點.除了頂部節(jié)點以外,其他節(jié)點均被訪問并計算3次,

故其計算單元的消耗為N·(1+log2N).從圖4可以看出,該編碼的編碼結(jié)構(gòu)基于圖中單元的運算與分裂.可參考文獻[8]中的編碼方案,將該單元作為一個基礎(chǔ)運算單元,類似于PE2,通過流水線技術(shù)進行單步運算,以提高整體的吞吐率.

圖4 8位遞歸結(jié)構(gòu)二叉樹圖Figure 4 Binary tree diagram of Eight-bit

非遞歸編碼直接通過系統(tǒng)極化碼的編碼結(jié)構(gòu)進行編碼計算.系統(tǒng)極化碼編碼時行與行之間并不是相互獨立的,上面的行在編碼的時候依賴于下面行的中間信息.如圖2,當(dāng)編碼器計算節(jié)點x4時,編碼器同時需要節(jié)點a和b的信息,其中a由u4與節(jié)點b通過模二運算得來,而節(jié)點b來源于x6與x7.該過程中,計算x4所需要的信息需要來自下方的x6與x7.文獻[4]提出的Encoder A符合了系統(tǒng)極化碼的運算特點.其通過由下至上、由已知端到未知端進行橫向的逐行編碼.每一行除了存儲最后的編碼結(jié)果之外,還需要進行中間結(jié)果的儲存,如圖2中a與b的值,其存儲單元消耗為N(1+log2N).相比文獻[1]中提出的非系統(tǒng)極化碼編碼方案,Encoder A消耗了更多的存儲單元,但其所需的計算單元與非系統(tǒng)極化碼的一致,即Arikan提出的理論值.為了降低存儲單元的消耗.文獻[9]中在Encoder A的基礎(chǔ)上提出了一種減小存儲單元消耗的非遞歸編碼器.該編碼器采用與Encoder A相同的計算流程,所不同的是,該方法將極化碼編碼結(jié)構(gòu)分為λ(λ=0,1,2,…,n-1)層,并將每一層的節(jié)點按相對獨立性劃分為2(n-1)-λ塊.比如當(dāng)n=3時,編碼結(jié)構(gòu)被劃分為3層,第0層的節(jié)點分為4塊,第1層劃分為2塊,第2層劃分為1塊.如圖2所示,該算法運行第0層的運行步驟為：

1)將x7傳入編碼結(jié)構(gòu)右下角的c,d,e中;

2)將x6傳入c中并與d進行異或運算，將得到的值賦給b;

3)復(fù)用c,將x5的值存入c中并進行后續(xù)操作.

該算法采用復(fù)用存儲單元的方法,每一層的計算僅需要一個塊的存儲單元.其最終消耗的存儲單元為N,相比于Encoder A有了明顯的改進.

雖然這些方法有效的降低了式(3)和(4)進行高斯消去法求解的復(fù)雜度θ(3log2N).但三種算法的計算單元消耗仍然無法低于θ(N·log2N).這不利于長碼長情況下的系統(tǒng)極化碼編碼器設(shè)計.系統(tǒng)極化碼的遞歸與非遞歸算法中,雖然節(jié)省了大量的存儲單元,但其設(shè)計過程中并未考慮其編碼的吞吐率,利用這兩種算法與非系統(tǒng)極化碼高速編碼器的設(shè)計思想相結(jié)合將是一個重要的研究方向.

2.2.2 系統(tǒng)極化碼的部分并行設(shè)計

系統(tǒng)極化碼的雙向運算結(jié)構(gòu)是其進行部分并行設(shè)計的難點之一.文獻[10]提出了一種基于非系統(tǒng)極化碼編碼結(jié)構(gòu)的系統(tǒng)極化碼單向傳播結(jié)構(gòu).如圖5所示,該方法將系統(tǒng)極化碼的雙向傳播改造為與非系統(tǒng)極化碼類似的單向傳播結(jié)構(gòu).該編碼碼步驟如下：

1)將輸入u進行一次非系統(tǒng)編碼得出碼字u′;

2)u′中凍結(jié)位所在位置的信息置為0,其他位置的信息保持不變;

3)將u′再次作為輸入碼字進行非系統(tǒng)極化碼編碼,最終輸出結(jié)果即為系統(tǒng)極化碼編碼碼字.

圖5 8位單向運算系統(tǒng)極化碼編碼結(jié)構(gòu)圖Figure 5 The polar code structure diagram ofthe 8-bit unidirectional operation system

文獻[11]指出,上述單向傳播系統(tǒng)極化碼編碼結(jié)構(gòu)可以看作是兩個非系統(tǒng)極化碼結(jié)構(gòu)的結(jié)合,并以文獻[10]作為基礎(chǔ)設(shè)計出一種單向傳播的部分并行系統(tǒng)極化碼編碼方案.該編碼器采用兩個非系統(tǒng)極化碼編碼器串聯(lián)的方式設(shè)計出了多路并行編碼器.

表2列出了碼長16 384、并行度32的系統(tǒng)與非系統(tǒng)極化碼部分并行編碼器系統(tǒng)的資源消耗與吞吐率.從表中可以看出,由于文獻[11]中的系統(tǒng)極化碼編碼方案采取了兩個非系統(tǒng)極化碼編碼器,其結(jié)構(gòu)復(fù)雜度與運算復(fù)雜度都要高于文獻[6]中的非極化碼編碼器.這使得其在各方面的性能都低于文獻[6].但相比于文獻[3],其資源消耗與吞吐率兩方面的性能已經(jīng)得到了很大的改進.

表2 計算單元消耗對比圖

目前,系統(tǒng)極化碼的并行設(shè)計方案的主要思路是將雙向運算轉(zhuǎn)化成單向運算,該方法雖然可行但卻大大的增加了系統(tǒng)的復(fù)雜度.而系統(tǒng)極化碼的遞歸結(jié)構(gòu)屬于單向運算過程,該編碼結(jié)構(gòu)將是系統(tǒng)極化碼并行設(shè)計的基礎(chǔ).

3 系統(tǒng)與非系統(tǒng)極化碼性能仿真

基于以上對系統(tǒng)極化碼與非系統(tǒng)極化碼硬件實現(xiàn)方案的分析.為了驗證兩種編碼在相同信道條件下的性能差異,本章基于Matlab仿真平臺,在其他條件相同的情況下,分別對兩種編碼在SC譯碼、SCL譯碼以及BP譯碼條件下進行了誤碼率與誤幀率的性能仿真,仿真結(jié)果如圖6～8,表3給出了具體的仿真方案.

表3 仿真方案詳細配置

圖6 系統(tǒng)與非系統(tǒng)極化碼在BP譯碼下的性能對比Figure 6 The performance comparison between system and non-system polar code under BP decoding

圖7 系統(tǒng)與非系統(tǒng)極化碼在SC譯碼下的性能對比Figure 7 The performance comparison between system and non-system polar code under SC decoding

圖8 系統(tǒng)與非系統(tǒng)極化碼在SCL譯碼下的性能比Figure 8 The performance comparison between system and non-system polar code under SCL decoding

4 發(fā)展趨勢探討

從以上的仿真中可以看出,系統(tǒng)極化碼性能優(yōu)于非系統(tǒng)極化碼.在未來的極化碼應(yīng)用中,系統(tǒng)極化碼終將取代非系統(tǒng)極化碼.但由于系統(tǒng)極化碼在譯碼階段仍然需要進行非系統(tǒng)極化碼判決.故對非系統(tǒng)極化碼繼續(xù)研究同樣重要.目前,系統(tǒng)極化碼的硬件實現(xiàn)方案仍然需要消耗大量硬件資源.系統(tǒng)極化碼雖然已經(jīng)實現(xiàn)了部分并行流水線的結(jié)構(gòu),但其吞吐率還遠比不上非系統(tǒng)極化碼.如何提高系統(tǒng)極化碼編碼吞吐率將是一個研究的熱點與難點.極化碼屬于線性分組碼,其編碼階段本質(zhì)上是生成矩陣G與輸入碼字的一次模二運算,而極化碼的生成矩陣G是由核矩陣F組成,具有一定的規(guī)律.如何從矩陣運算的角度找出G矩陣的規(guī)律并簡化其運算過程將會是接下來研究高速低功耗極化碼編碼器的另一個突破口.

隨著5G時代的到來,當(dāng)下的通信技術(shù)已經(jīng)越來越無法滿足網(wǎng)絡(luò)流量日益增長的需求.極化碼作為5G的控制信道編碼方案,其在短碼長的性能將更受關(guān)注.而極化碼的性能與碼長成正相關(guān)關(guān)系,也就是說極化碼的碼長越短,其性能越差.極化碼的級聯(lián)編碼可以有效的提高其短碼的性能.文獻[12]中,以LDPC短碼作為外碼,極化碼作為內(nèi)碼來提高有限碼長的極化碼的糾錯性能,該級聯(lián)碼在SC譯碼的條件下相比于傳統(tǒng)極化碼提高了0.5 dB.

另一方面,深度學(xué)習(xí)技術(shù)已經(jīng)滲透到了各種傳統(tǒng)的工業(yè)技術(shù)當(dāng)中,并帶來了突破性的成果,極化碼的編碼結(jié)構(gòu)與深度學(xué)習(xí)全連接神經(jīng)網(wǎng)絡(luò)非常相似,如何建立兩者的關(guān)系,利用深度學(xué)習(xí)技術(shù)來優(yōu)化極化碼編碼技術(shù)將是極化碼研究的另一個關(guān)鍵問題.