彭文凱 周華

關(guān)鍵詞： 極化碼; 連續(xù)刪除譯碼; 連續(xù)刪除列表譯碼; 循環(huán)冗余校驗(yàn)碼; 譯碼算法; 譯碼性能

中圖分類(lèi)號(hào)： TN820.1+1?34 ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)： 1004?373X（2019）06?0137?05

Abstract： The polar code which has a simple and definite encoding mode and decoding algorithm is proved that it can reach the Shannon limit theoretically， but its successive cancellation decoding （SCD） performs decoding along the single path bit by bit， leading to unsatisfactory practical decoding performance. The successive cancellation list decoding （SCLD） is a modified algorithm of the SCD， which improves the decoding performance of the polar code at the cost of increasing the decoding complexity. The combination of SCLD and the cyclic redundancy check （CRC） can further reduce the probability of decoding errors in the multiple paths of the SCLD without increase of the decoding complexity. Based on this， the performance difference generated by different combinations of CRC codes with polar codes is analyzed in this paper， so as to obtain appropriate combinations of CRC codes with polar codes.

Keywords： polar code; successive cancellation decoding; successive cancellation list decoding; cyclic redundancy check code; decoding algorithm; decoding performance

極化碼（Polar codes）是Erikan在2009年提出的基于信道極化理論的一種編譯碼方式，該編譯碼具有明確的編碼和譯碼算法數(shù)學(xué)公式[1]，Erikan在理論上證明了該編譯碼方式能夠達(dá)到香農(nóng)極限。由于極化碼在理論上的優(yōu)異性能，該編譯碼一經(jīng)提出便成為眾多領(lǐng)域的研究熱點(diǎn)。美國(guó)當(dāng)?shù)貢r(shí)間2016年11月17日凌晨0點(diǎn)45分，在美國(guó)內(nèi)華達(dá)州里諾召開(kāi)的3GPP RAN1 87次會(huì)議的5G短碼方案討論中，以中國(guó)華為公司主推的極化碼方案成為5G控制信道eMBB場(chǎng)景（上行/下行）編碼方案。

作為極化碼的原始算法，SC譯碼（Successive Cancellation Decoding）[2]在實(shí)際仿真實(shí)驗(yàn)中的譯碼性能并不如傳統(tǒng)的LDPC碼和Turbo碼。SCL譯碼（Successive Cancellation List Decoding）[3]作為SC譯碼的改進(jìn)算法，以付出一定的譯碼復(fù)雜度為代價(jià)，通過(guò)保留盡可能多的路徑來(lái)獲得正確的譯碼序列，從而提高譯碼性能。但是隨著保留路徑的增加，一方面譯碼復(fù)雜度呈倍數(shù)增長(zhǎng)，另一方面錯(cuò)過(guò)正確譯碼序列的概率也隨之增加。CRC?SCL譯碼[4]是在SCL譯碼基礎(chǔ)上改進(jìn)的譯碼算法，該算法在不增加譯碼復(fù)雜度的情況下，能一定程度上提高SCL譯碼算法的性能。仿真結(jié)果表明并不是所有的CRC（Cyclic Redundancy Check）都可以對(duì)極化碼產(chǎn)生積極的影響，不同的CRC對(duì)不同碼長(zhǎng)的極化碼產(chǎn)生的譯碼性能也不盡相同。

本文以SCL譯碼算法為基礎(chǔ)，在譯碼復(fù)雜度不增加的基礎(chǔ)上結(jié)合不同的CRC碼進(jìn)行仿真，以找出不同碼長(zhǎng)下盡可能提高SCL譯碼性能的CRC，并分析CRC對(duì)SCL譯碼的性能影響。

1 ?極化碼的編碼和譯碼算法

譯碼樹(shù)為SCL譯碼的另一個(gè)概念[7]，每個(gè)碼長(zhǎng)為N的極化碼均可以對(duì)應(yīng)一個(gè)N層的譯碼樹(shù)，譯碼樹(shù)中任意上下兩個(gè)節(jié)點(diǎn)之間的邊對(duì)應(yīng)一個(gè)譯碼碼元，用0或1表示，從根節(jié)點(diǎn)到任意葉節(jié)點(diǎn)形成的路徑對(duì)應(yīng)一段完整的譯碼序列。每個(gè)節(jié)點(diǎn)均對(duì)應(yīng)一個(gè)路徑度量值，根節(jié)點(diǎn)為路徑度量值的初始值，即[PM?=0]，葉節(jié)點(diǎn)為整個(gè)譯碼序列最終的路徑度量值。圖1為碼長(zhǎng)為4的譯碼樹(shù)。

譯碼時(shí)，從根節(jié)點(diǎn)出發(fā)按廣度優(yōu)先的方法向下層擴(kuò)展，每一層向下一層擴(kuò)展時(shí)，當(dāng)前層每一個(gè)節(jié)點(diǎn)均有0和1兩種選擇，每種選擇結(jié)合前面已經(jīng)譯碼出來(lái)的碼元使用式（4）或式（5）可以計(jì)算出當(dāng)前碼元的對(duì)數(shù)似然比，結(jié)合式（3）求出該路徑的度量值;然后保留路徑度量值較大的L條路徑繼續(xù)向下層擴(kuò)展直到葉節(jié)點(diǎn);最后從保留的L條路徑中選擇最大路徑度量值對(duì)應(yīng)的路徑作為最后的譯碼序列。

SCL譯碼算法[8]的詳細(xì)過(guò)程如下：

1） 初始化：初始化路徑度量值，即[PM?=0]。

2） 路徑擴(kuò)展：將之前i-1層保留的路徑向第i層擴(kuò)展，計(jì)算第i層所有節(jié)點(diǎn)選擇0或1的路徑度量值，并保留所有擴(kuò)展后的路徑。

3） 路徑選擇：將步驟2）中保留的路徑按路徑度量值從大到小進(jìn)行排序，如果此時(shí)的路徑數(shù)量小于L，則保留所有路徑，否則保留路徑度量值較大的L條，其余的路徑不再向下層擴(kuò)展。

4） 擴(kuò)展結(jié)束：如果譯碼進(jìn)行到第i層且i

SCL譯碼作為SC譯碼的改進(jìn)算法，從理論上可以解決SC譯碼由于單路徑的局限性，從而提高譯碼性能，然而隨著保留路徑的增加，譯碼復(fù)雜度也隨之提高。同時(shí)會(huì)出現(xiàn)正確的譯碼序列存在于保留路徑中，但其路徑度量值并不是最大值，而最大路徑度量值對(duì)應(yīng)的序列不是正確的譯碼序列，保留路徑越多，出現(xiàn)這種譯碼錯(cuò)誤的概率也越高。

2 ?CRC?SCL譯碼

CRC是一種利用除法和余數(shù)原理來(lái)進(jìn)行檢查譯碼錯(cuò)誤的校驗(yàn)碼[9?10]。實(shí)際應(yīng)用時(shí)，發(fā)送端計(jì)算CRC值并隨數(shù)據(jù)一同發(fā)送給接收端，接收端對(duì)接收到的軟信息進(jìn)行譯碼，并檢查得到的譯碼序列能否通過(guò)CRC校驗(yàn)。對(duì)于一個(gè)給定的（N，K）碼，可以證明存在一個(gè)最高冪次為N-K=R的多項(xiàng)式G（x）。根據(jù)G（x）可以生成K位信息的校驗(yàn)碼，G（x）為這個(gè)校驗(yàn)碼的生成多項(xiàng)式。若發(fā)送信息用信息多項(xiàng)式C（x）表示，將其整體左移R位，則可表示成C（x）*2R，左移R位后C（x）的右邊會(huì)空出R位，即校驗(yàn)碼的位置，通過(guò)C（x）*2R除以生成多項(xiàng)式G（x）得到的余數(shù)就是校驗(yàn)碼。

SCL譯碼的信息位為K，碼率為[KN]，該算法在譯碼時(shí)會(huì)保留L條路徑，若編碼時(shí)在M位信息比特后添加K-M位的檢驗(yàn)碼可以得到K位含有檢驗(yàn)碼的信息比特序列，此時(shí)碼率為[MN]。將含有檢驗(yàn)碼的序列作為信息比特序列與固定比特序列混合后進(jìn)行編碼，經(jīng)過(guò)信道傳輸后譯碼器對(duì)接收到的軟信息進(jìn)行譯碼可以得到L條譯碼序列，提取信息位上的碼元可以得到L條含有K-M位校驗(yàn)碼的信息比特序列，如圖2所示。將這L條信息比特序列進(jìn)行CRC校驗(yàn)，將能通過(guò)CRC校驗(yàn)的序列除去檢驗(yàn)碼作為最后的譯碼序列，若保留的L條信息比特序列都不能通過(guò)CRC校驗(yàn)，則將路徑度量值最大的序列作為最后的譯碼序列。CRC?SCL譯碼系統(tǒng)結(jié)構(gòu)[11]如圖3所示。

CRC?SCL譯碼算法[12]的前3個(gè)步驟與SCL譯碼算法相同，只需將最后一步更改如下：

4） 擴(kuò)展結(jié)束：如果譯碼進(jìn)行到第i層且i

5） CRC校驗(yàn)：若L=1，則該路徑就是最后的譯碼序列，若L>1，對(duì)保留的L條路徑進(jìn)行校驗(yàn)，通過(guò)CRC校驗(yàn)的序列作為最后的譯碼序列，若保留的L條路徑都不能通過(guò)CRC校驗(yàn)，則將最大路徑度量值對(duì)應(yīng)的路徑作為最后的譯碼序列。

3 ?仿真結(jié)果分析

該仿真實(shí)驗(yàn)主要以SCL譯碼為基礎(chǔ)，以Matlab軟件為平臺(tái)，所有仿真實(shí)驗(yàn)都在AWGN信道下完成，調(diào)制方式為BPSK調(diào)制。

圖4顯示了SCL譯碼在不同的保留路徑數(shù)下所產(chǎn)生的性能差異，該仿真實(shí)驗(yàn)的碼長(zhǎng)為256，信息比特長(zhǎng)度為128，碼率為0.5，路徑分別為L(zhǎng)=1，4，8。從該仿真結(jié)果可以看出路徑為4和路徑為8時(shí)的譯碼性能明顯優(yōu)于路徑為1時(shí)的譯碼性能。然而路徑為8時(shí)的譯碼復(fù)雜度是路徑為4時(shí)的譯碼復(fù)雜度的2倍，但是兩者的譯碼性能卻相差不大。

圖5顯示了不同碼長(zhǎng)對(duì)SCL譯碼性能的影響，該仿真實(shí)驗(yàn)的碼率為0.5，保留路徑數(shù)均為4。信噪比小于1.1 dB時(shí)，碼長(zhǎng)為256時(shí)的譯碼性能略?xún)?yōu)于碼長(zhǎng)為1 024時(shí)的譯碼性能，當(dāng)信噪比大于1.1 dB時(shí)，碼長(zhǎng)為1 024時(shí)的譯碼性能優(yōu)于碼長(zhǎng)為256時(shí)的譯碼性能，且隨著信噪比的增加，碼長(zhǎng)為1 024時(shí)的誤碼率和碼長(zhǎng)為256時(shí)的誤碼率差異也隨之增大。

圖6顯示了SCL譯碼和CRC?SCL譯碼在保留路徑分別為4，8和16時(shí)的性能差異。路徑L=4時(shí)，在信噪比大于3.4 dB的部分，CRC?SCL譯碼的譯碼性能優(yōu)于SCL譯碼的譯碼性能;路徑L=8時(shí)，在信噪比大于2.7 dB的部分，CRC?SCL譯碼的譯碼性能優(yōu)于SCL譯碼的譯碼性能;路徑為16時(shí)，在信噪比大于2.4 dB的部分，CRC?SCL譯碼的譯碼性能優(yōu)于SCL譯碼的譯碼性能。造成這種結(jié)果的原因是CRC?SCL譯碼在編碼過(guò)程中增加CRC冗余導(dǎo)致碼率降低，此時(shí)碼元的能量不能使CRC?SCL譯碼降低極化碼的誤碼率;當(dāng)信噪比足夠大時(shí)，碼元的能量也隨之增大并且能夠滿(mǎn)足CRC?SCL譯碼對(duì)極化碼產(chǎn)生有利影響，所以在高信噪比區(qū)域，CRC?SCL譯碼的譯碼性能優(yōu)于SCL譯碼的譯碼性能。

圖7顯示了在碼長(zhǎng)為256，保留路徑為4時(shí)，CRC?SCL譯碼方式在不同CRC校驗(yàn)碼下所產(chǎn)生的性能差異，在信噪比小于2.6 dB的部分，8位CRC校驗(yàn)碼的CRC?SCL譯碼的誤碼率比其他CRC?SCL譯碼的誤碼率更低;而在信噪比大于2.6 dB的部分，12位CRC校驗(yàn)碼的CRC?SCL譯碼的誤碼率最低。

4 ?結(jié) ?論

本文研究了極化碼的編碼和譯碼原理，對(duì)不同碼長(zhǎng)的極化碼在SCL譯碼下進(jìn)行仿真，分析了碼長(zhǎng)和路徑數(shù)L對(duì)極化碼性能的影響。在此基礎(chǔ)之上對(duì)CRC?SCL譯碼和SCL譯碼的仿真結(jié)果進(jìn)行對(duì)比分析，分析了CRC?SCL譯碼在低信噪比部分和高信噪比部分對(duì)極化碼的性能產(chǎn)生不同影響的原因。同時(shí)在碼長(zhǎng)N=256時(shí)，將不同長(zhǎng)度的CRC校驗(yàn)碼對(duì)極化碼的性能影響進(jìn)行仿真，通過(guò)大量的仿真數(shù)據(jù)證明，在碼長(zhǎng)N=256時(shí)，12位CRC校驗(yàn)碼的CRC?SCL譯碼的譯碼性能較好。

參考文獻(xiàn)

[1] ARIKAN E. Channel polarization： a method for constructing capacity?achieving codes for symmetric binary?input memoryless channels [J]. IEEE transactions on information theory， 2009， 55（7）： 3051?3073.

[2] XING C， WANG B， ZHAO S M. A reduced?complexity successive?cancellation decoding algorithm for polar codes [C]// Proceedings of 6th International Congress on Image and Signal Processing. Hangzhou： IEEE， 2013： 5?10.

[3] Tal I， VARDY A. List decoding of polar codes [C]// Proceedings of IEEE International Symposium on Information Theory， St. Petersburg： IEEE， 2011： 1?11.

[4] CAO M， ZHAO S， ZHAO S M. Multiple CRC?aided variable successive cancellation list decoder of polar codes [J]. The journal of China Universities of Posts and Telecommunications， 2017， 24（2）： 83?88.

[5] HASHEMI S A， BALATSOUKAS?STIMMING A， GIARD P， et al. Partitioned successive?cancellation list decoding of polar codes [C]// Proceedings of IEEE International Conference on Acoustics， Speech and Signal Processing. Shanghai： IEEE， 2015： 1?4.

[6] BALATSOUKAS?STIMMING A， PARIZI M B， BURG A. LLR?based successive cancellation list decoding of polar codes [J]. IEEE transactions on signal processing， 2015， 63（19）： 5165?5179.

[7] CHEN K， NIU K， LIN J R. A reduced?complexity successive cancellation list decoding of polar codes [C]// Proceedings of 77th Vehicular Technology Conference （VTC Spring）. Dresden： IEEE， 2013： 1?5.

[8] FAN Y Z， XIA C Y， CHEN J， et al. A low?latency list successive?cancellation decoding implementation for polar codes [J]. IEEE journal on selected areas in communications， 2016， 34（2）： 303?317.

[9] ZHANG Q S， LIU A J， PAN X F， et al. CRC code design for list decoding of polar codes [J]. IEEE communications letters， 2017， 21（6）： 1229?1232.

[10] LI S B， LU L J， DENG Y Q， et al. A reused?public?path successive cancellation list decoding for polar codes with CRC [J]. IEEE communications letters， 2017， 21（12）： 2566?2569.

[11] MURATA T， OCHIAI H. On design of CRC codes for polar codes with successive cancellation list decoding [C]// Proceedings of IEEE International Symposium on Information Theory. Aachen： IEEE， 2017： 1?6.

[12] YU Q P， SHI Z P， YAN Q H， et al. Hybrid parity?check and CRC aided SCL decoding for polar codes [C]// Proceedings of IEEE International Conference on Internet of Things （iThings） and IEEE Green Computing and Communications （GreenCom） and IEEE Cyber， Physical and Social Computing （CPSCom） and IEEE Smart Data （SmartData）. Chengdu： IEEE， 2016： 11?15.