極化碼譯碼算法研究現(xiàn)狀及發(fā)展前景

王秀敏，張志紅，李　君，王　怡，洪　波

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

隨著現(xiàn)代科技的不斷發(fā)展，人們對(duì)于通信系統(tǒng)的可靠性與即時(shí)性要求也越來越高.5G時(shí)代的到來更是將這一需求提升到了一個(gè)新的高度.極化碼[1](Polar Codes)是一種新型編碼方式，它可以實(shí)現(xiàn)對(duì)稱二進(jìn)制輸入離散無記憶信道(例如二進(jìn)制對(duì)稱信道(BSC，Binary Symmetric Channel)和二進(jìn)制擦除信道(BEC，Binary Erasure Channel))的容量代碼構(gòu)造方法.極化碼作為目前唯一可理論證明達(dá)到香農(nóng)極限，并且具有可實(shí)用的線性復(fù)雜度編譯碼能力的信道編碼技術(shù)，成為下一代通信系統(tǒng)5G中信道編碼方案的強(qiáng)有力候選者.

2016年在美國內(nèi)華達(dá)州里諾結(jié)束的3GPP的RAN1#87會(huì)議上，3GPP確定了由華為等中國公司主推的Polar碼方案作為5G eMBB(增強(qiáng)移動(dòng)寬帶)場景的控制信道編碼方案.至此，5G eMBB場景的信道編碼技術(shù)方案完全確定，其中Polar碼作為控制信道的編碼方案.2017年12月，5G標(biāo)準(zhǔn)初步確定了極化碼的譯碼方案.

極化碼作為編碼界的后起之秀在未來的通信系統(tǒng)中將會(huì)有很廣泛的應(yīng)用.隨著新的通信標(biāo)準(zhǔn)的出爐，相信極化碼會(huì)有更大的發(fā)展空間.因此，研究極化碼的譯碼算法對(duì)于通信技術(shù)的進(jìn)步與通信系統(tǒng)性能的提高，具有非常重大的現(xiàn)實(shí)意義.

1　極化碼研究現(xiàn)狀分析

1.1　極化碼簡介

極化碼的概念由信道極化理論而來.N個(gè)相互獨(dú)立的信道經(jīng)過信道集合和信道分解之后，變成N個(gè)相關(guān)的信道.這N個(gè)相關(guān)的信道中的一部分信道容量接近于1，另一部分則接近于0.隨著N的增大，這種極化現(xiàn)象會(huì)趨于明顯.即信道容量趨近于1或者0的信道越來越多.在信息傳遞時(shí)，我們就可以選擇那些信道容量較好的信道來傳遞信息比特，剩余的信道則默認(rèn)傳遞零比特.這樣就可以提高傳遞信息的效率.

2011年Erdal Arikan教授提出系統(tǒng)極化碼[2]，從此極化碼可以分為非系統(tǒng)極化碼和系統(tǒng)極化碼兩類.非系統(tǒng)極化碼編碼過程

x=uG=uAGA⊕uAcGAc.

(1)

x和u分別是碼字比特和信息比特.uA為信息位比特向量，uAc為固定位比特向量.GA和GAc為生成矩陣G的子向量，GA由生成矩陣的信息位序號(hào)所在的行組成.GAc由生成矩陣的固定位序號(hào)所在的行組成.系統(tǒng)極化碼為

(2)

式(2)中的子矩陣構(gòu)成方式與式(1)中相同.具體的編譯碼過程如圖1.與非系統(tǒng)極化碼相比，除了編碼方式的不同以外，系統(tǒng)極化碼的譯碼還多了一個(gè)編碼部分，但譯碼的主要核心部分是一樣的.由此可見，我們的研究核心可以放在非系統(tǒng)極化碼譯碼上，一舉兩得.

兩者的性能比較如圖2、圖3.調(diào)制方式為BPSK，信道為AWGN，碼長為2 048，碼率為0.5.在相同的信道環(huán)境下，系統(tǒng)極化碼比非系統(tǒng)極化碼的誤碼率有明顯的提升，誤幀率則變化不大.

圖1　極化碼編譯碼過程Figure 1　Process of polar codes encoding and decoding

圖2　系統(tǒng)與非系統(tǒng)極化碼誤碼率Figure 2　BER of non-systematic andsystematic polar codes

圖3　系統(tǒng)與非系統(tǒng)極化碼誤幀率Figure 3　FER of non-systematic andsystematic polar codes

1.2　國內(nèi)外研究現(xiàn)狀

極化碼最早的譯碼算法為SC(Successive-Cancellation)算法，它具有O(Nlog2N)的譯碼復(fù)雜度.在不同的碼長碼率下的譯碼性能如圖4、圖5.從圖中可以看出，碼長越長碼率越低,極化碼的誤碼率越低，性能越好.當(dāng)極化碼的碼率到達(dá)0.95時(shí)，它就已經(jīng)失去了極化特性的優(yōu)勢，所以誤碼率性能會(huì)變差.

圖4　不同碼長誤碼率(R=0.5)Figure 4　BER of different code length(R=0.5)

圖5　不同碼率誤碼率(N=1 024)Figure 5　BER of different code rate(N=1 024)

Camille Leroux[3]基于SC算法發(fā)現(xiàn)了FFT、樹形和線形結(jié)構(gòu)，并以此為基礎(chǔ)提出了部分并行的譯碼器結(jié)構(gòu).文獻(xiàn)[4]中提出的SC譯碼器硬件整體結(jié)構(gòu)如圖6.圖7是譯碼流程圖.圖7中最左側(cè)為判決層，最右側(cè)為信道層.圖中每個(gè)節(jié)點(diǎn)上方的數(shù)字表示在譯碼過程中被激活的順序.

圖6　SC譯碼器硬件結(jié)構(gòu)圖Figure 6　Structure of polar codes decoder

通過觀察每個(gè)時(shí)鐘周期內(nèi)算法的具體計(jì)算情況，發(fā)現(xiàn)可以在某些時(shí)鐘周期將處理單元PE(Processing unit)并行處理來盡量減少延時(shí).而文獻(xiàn)[5]中則提出了一種串聯(lián)結(jié)構(gòu)，再加上用觸發(fā)器代替ROM降低時(shí)延的方式來提高譯碼吞吐率.文獻(xiàn)[6]中提出了一種鏈接的處理單元和變化的量化方案，并且對(duì)內(nèi)存(SRAM)進(jìn)行了處理，減少了復(fù)用器的使用.從而減少了硬件資源消耗和時(shí)延.

除了在硬件結(jié)構(gòu)上的改進(jìn)之外，還有對(duì)算法本身的優(yōu)化.由于極化碼固定位的特殊性能，在譯碼時(shí)我們已經(jīng)知道固定位的值就是零，所以可以在算法的計(jì)算過程中直接忽略掉有關(guān)固定位的計(jì)算.這就是SSC(Simplified Successive-Cancellation)算法[7].SSC算法將譯碼過程中所有的節(jié)點(diǎn)分為三類：

Rate-1:節(jié)點(diǎn)的后裔子節(jié)點(diǎn)都是信息位；

Rate-0:節(jié)點(diǎn)的后裔子節(jié)點(diǎn)都是固定位；

Rate-R:節(jié)點(diǎn)的后裔子節(jié)點(diǎn)既有固定位又有信息位.

其中，Rate-0的節(jié)點(diǎn)可以完全不用計(jì)算，直接將相對(duì)應(yīng)的譯碼比特置零.這樣的處理方式不僅可以節(jié)省計(jì)算資源也可以大大減少處理時(shí)延.文獻(xiàn)[8]中則針對(duì)Rate-R節(jié)點(diǎn)的LLR值處理進(jìn)行了MS近似，提高了譯碼性能.在此基礎(chǔ)上，Gabi Sarkis[9]提出了相對(duì)應(yīng)的硬件結(jié)構(gòu)，與以前的譯碼器相比提高了近八倍的吞吐量.在文獻(xiàn)[10]、[11]中又定義了校驗(yàn)子(Syndrome Check)的概念，將計(jì)算路徑的修剪進(jìn)一步細(xì)化，降低了計(jì)算復(fù)雜度和時(shí)延.

SCL(Successive-Cancellation List)譯碼算法[12-13]通過增加計(jì)算路徑L提高了極化碼的譯碼性能，但是隨著路徑L的增加，譯碼復(fù)雜度也會(huì)成倍增加.為了找到折中的方式盡量的提高SCL譯碼算法的性能來彌補(bǔ)計(jì)算復(fù)雜度上的損失，CRC校驗(yàn)[14-15]的加入是一個(gè)很好的方式.文獻(xiàn)[16-17]中通過改變極化碼的構(gòu)造方法或者加交織器的方式來提高極化碼的譯碼性能，這也是一種可取的方法.

圖7　N=8時(shí)SC譯碼結(jié)構(gòu)圖Figure 7　Structure of polar codes decoder when N=8

2　譯碼算法改進(jìn)

2.1　譯碼算法的局限性

接續(xù)消除(SC)譯碼算法是由Arikan教授提出的，當(dāng)N=8時(shí)的譯碼過程圖如圖7[4].圖中兩個(gè)函數(shù)的表達(dá)式為:

(3)

(4)

a,b分別表示節(jié)點(diǎn)的似然比.

信道層的計(jì)算公式為

(5)

L(yi)是似然比值，W(yi|0)是信道轉(zhuǎn)移概率.判決層的計(jì)算公式為

(6)

在譯碼過程中每個(gè)時(shí)鐘周期的處理單元類型與處理節(jié)點(diǎn)序號(hào)如圖8.

我們知道SC譯碼算法的過程是由圖7中最右側(cè)一列的信道層到最左側(cè)一列的判決層.而且由于信道極化后信道之間的相關(guān)性導(dǎo)致節(jié)點(diǎn)的計(jì)算順序是固定的，這就造成了譯碼過程有很大的時(shí)延.SC譯碼算法沒有迭代，若譯碼過程中出現(xiàn)錯(cuò)誤，在后續(xù)的過程中將不能糾正.

SCL算法雖然加入了路徑度量來提高糾錯(cuò)的能力，但是隨著L的增加，計(jì)算復(fù)雜度也將成倍增加.雖然科技的發(fā)展使得資源消耗變得不再是一個(gè)譯碼器主要考慮的部分，但是冗余路徑的存在還是會(huì)給譯碼過程增加時(shí)延.

增加CRC校驗(yàn)和交織器對(duì)譯碼性能提升并不大，尤其是在低碼率低信噪比部分，而且尋找合適的CRC生成多項(xiàng)式和靈活的交織器參數(shù)也是一個(gè)巨大的工作量.實(shí)現(xiàn)起來也是得不償失的.

2.2　譯碼算法的改進(jìn)

針對(duì)上文中提出的不足，我們對(duì)極化碼算法的改進(jìn)提出幾個(gè)方向：

1)在圖8中，每個(gè)時(shí)鐘周期內(nèi)只有一個(gè)計(jì)算階段和計(jì)算單元在處理，這樣就浪費(fèi)了大部分的計(jì)算資源.在第3、4,6、7，10、11，13、14個(gè)時(shí)鐘周期內(nèi)的譯碼比特判決是相互獨(dú)立的，在這一部分可以并行計(jì)算來達(dá)到降低譯碼延時(shí)的效果.

2)SSC算法和SCL算法在之前的改進(jìn)中是單獨(dú)的兩個(gè)算法，并且相互之間沒有影響.由此我們可以將SSC算法應(yīng)用到SCL算法之中，這樣在每個(gè)計(jì)算路徑中都可以減少相應(yīng)的固定位的計(jì)算.這樣可以既可以中和SCL算法的復(fù)雜度增加的問題，也可以保留SCL算法提高譯碼性能這一優(yōu)勢.

3)在LDPC/Turbo雙模譯碼器[18]中，引入的QPP交織器的動(dòng)態(tài)交織結(jié)構(gòu)能夠帶來比普通交織器更大的譯碼性能提升.高性能雙模譯碼器[19-20]中也介紹了可以與極化碼譯碼器公用的部分模塊.因?yàn)闃O化碼也具有卷積碼的性質(zhì)，所以這一交織器結(jié)構(gòu)可以應(yīng)用到譯碼器的結(jié)構(gòu)中，來提升譯碼性能.

圖8　N=8時(shí)的譯碼日程表Figure 8　Scheduling for the SC decoder with N=8

3　發(fā)展趨勢探討

目前5G標(biāo)準(zhǔn)的方案草稿還在不斷更新中，極化碼的研究與應(yīng)用正處在萬里長征的起點(diǎn).在硬件計(jì)算的近似處理中，極化碼的主要譯碼計(jì)算公式與LDPC碼是一致的.在SCL算法中路徑度量的更新則與Turbo碼前后向度量的更新規(guī)則有相似之處.QPP交織器的應(yīng)用更是可以大大提高這種三模(LDPC/Turbo/Polar)譯碼器的實(shí)現(xiàn)可能性.

【參考文獻(xiàn)】

[1]ERDAL A. Channel Polarization: A method for constructing capacity achieving codes for symmetric Serbian-input memoryless channels[J].IEEETransactionsonInformationTheory,2009,55(7):3051-3073.

[2]ERDAL A. Systematic polar coding[J].IEEECommunicationsLetters, 2011,15(8):860-862.

[3]CAMILLE L, IDO T, ALEXANDER V, et al. Hardware architectures for successive cancellation decoding of polar codes[C]//2011IEEEInternationalConferenceonAcoustics,Speech&SignalProcessing. Prague, Czech Republic:IEEE, 2011: 1665-1668.

[4]CAMILLE L, ALEXANDRE J R, GABI S, et al. A semi-Parallel successive-cancellation decoder for polar codes[J].IEEETransactionsonSignalProcessing, 2013,61(2): 289-299

[5]ALPTEKIN P, ERDAL A. A two phase successive cancellation decoder architecture for polar codes[C]//2013IEEEInternationalSymposiumonInformationTheory.Turkey:ISIT, 2013: 957-961.

[6]ALEXANDRE J R, WARREN J G. A scalable successive-cancellation decoder for polar codes[J].IEEETransactionsonSignalProcessing, 2014, 62(20): 5339-5346.

[7]AMIN A Y, FRANK R K. A simplified successive-cancellation decoder for polar codes[J].IEEECommunicationsLetters, 2011, 15(12): 1378-1380.

[8]GABI S, WARREN J G. Increasing the throughput of polar decoders[J].IEEECommunicationsLetters, 2013, 17(4): 725-728.

[9]GABI S, PASCAL G, ALEXANDER V, et al. Fast Polar decoders: Algorithm and implementation[J].IEEEJournalonSelectedAreasinCommunications, 2014, 32(5): 946-957.

[10]HOYOUNG Y, IN C P. Efficient pruning for successive-cancellation decoding of polar codes[J].IEEECommunicationsLetters, 2016, 20(12): 2362-2365.

[11]JAEJOON C, IN C P. Improved successive-cancellation decoding of polar codes based on recursive syndrome decomposition[J].IEEECommunicationsLetters, 2017,21(11):2344-2347.

[12]CHEN K, NIU K, LIN J R. List successive cancellation decoding of polar codes[J].ElectronicsLetters, 2012, 48(9): 1-2.

[13]IDO T, ALEXANDER V. List decoding of polar codes[C]//2011IEEEInternationalSymposiumonInformationTheoryProceedings. Russia:ISIT, 2011: 1-5.

[14]ZHANG Q S, LIU A J, PAN X F, et al. CRC code design for list decoding of polar codes[J].IEEECommunicationsLetters,2017, 21(6) : 1229-1232.

[15]TANKUMI M, HIDEKI O. On design of CRC codes for polar codes with successive cancellation list decoding[C]//2017IEEEInternationalSymposiumonInformationTheory. Germany:ISIT, 2017: 1868-1872.

[16]SARIT B, ARMAN F, PAUL H S, et al, Permuted successive cancellation decoding for polar codes[C]//2017IEEEInternationalSymposiumonInformationTheory. Germany:ISIT, 2017: 2618-1622.

[17]GIACOMO R, MARCO B, FRANCO C. On the error probability of short concatenated polar and cyclic codes with interleaving[C]//2017IEEEInternationalSymposiumonInformationTheory. Germany:ISIT, 2017:1858-1862.

[18]SUN Y, CAVALLARO J R. Efficient hardware implementation of a highly parallel 3GPP LTE /LTE-advance Turbo decoder[J].Intergation,theVLSIJoural, 2011, 44: 305-315.

[19]王秀敏, 洪芳菲, 單良, 等. LDPC/Turbo雙模譯碼器技術(shù)發(fā)展與前景綜述[J]. 中國計(jì)量學(xué)院學(xué)報(bào), 2016, 27(1): 63-67.

WANG X M, HONG F F, SHAN L, et al. The advance overview on LDCP/Turbo dual-mode decoders[J].JournalofChinaUniversityofMetrology, 2016, 27(1): 63-67.

[20]王秀敏, 宿晨, 單良, 等. 高性能LDPC/Turbo雙模譯碼器的發(fā)展綜述[J]. 中國計(jì)量大學(xué)學(xué)報(bào), 2017, 28(2): 203-207.

WANG X M, SU C, SHAN L, et al. A development overview of high-performance LDCP/Turbo dual-mode decoders[J].JournalofChinaUniversityofMetrology, 2017, 28(2): 203-207.