基于循環(huán)冗余校驗的極化碼研究

彭文凱 周華

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

中圖分類號： TN820.1+1?34 ? ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ? 文章編號： 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年提出的基于信道極化理論的一種編譯碼方式，該編譯碼具有明確的編碼和譯碼算法數學公式[1]，Erikan在理論上證明了該編譯碼方式能夠達到香農極限。由于極化碼在理論上的優(yōu)異性能，該編譯碼一經提出便成為眾多領域的研究熱點。美國當地時間2016年11月17日凌晨0點45分，在美國內華達州里諾召開的3GPP RAN1 87次會議的5G短碼方案討論中，以中國華為公司主推的極化碼方案成為5G控制信道eMBB場景（上行/下行）編碼方案。

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

本文以SCL譯碼算法為基礎，在譯碼復雜度不增加的基礎上結合不同的CRC碼進行仿真，以找出不同碼長下盡可能提高SCL譯碼性能的CRC，并分析CRC對SCL譯碼的性能影響。

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

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

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

SCL譯碼算法[8]的詳細過程如下：

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

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

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

4） 擴展結束：如果譯碼進行到第i層且i

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

2 ?CRC?SCL譯碼

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

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

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

4） 擴展結束：如果譯碼進行到第i層且i

5） CRC校驗：若L=1，則該路徑就是最后的譯碼序列，若L>1，對保留的L條路徑進行校驗，通過CRC校驗的序列作為最后的譯碼序列，若保留的L條路徑都不能通過CRC校驗，則將最大路徑度量值對應的路徑作為最后的譯碼序列。

3 ?仿真結果分析

該仿真實驗主要以SCL譯碼為基礎，以Matlab軟件為平臺，所有仿真實驗都在AWGN信道下完成，調制方式為BPSK調制。

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

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

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

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

4 ?結 ?論

本文研究了極化碼的編碼和譯碼原理，對不同碼長的極化碼在SCL譯碼下進行仿真，分析了碼長和路徑數L對極化碼性能的影響。在此基礎之上對CRC?SCL譯碼和SCL譯碼的仿真結果進行對比分析，分析了CRC?SCL譯碼在低信噪比部分和高信噪比部分對極化碼的性能產生不同影響的原因。同時在碼長N=256時，將不同長度的CRC校驗碼對極化碼的性能影響進行仿真，通過大量的仿真數據證明，在碼長N=256時，12位CRC校驗碼的CRC?SCL譯碼的譯碼性能較好。

參考文獻

[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.