循環(huán)冗余校驗串行抵消列表解碼算法改進(jìn)

徐東明, 孫 妍

(西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121)

極化碼(polar code)是在理論上能達(dá)到信道容量的一種編碼方式，是5G增強移動寬帶(enhance mobile broadband, eMBB)場景的信道編碼技術(shù)方案[1-4]。串行抵消(successive cancellation, SC)解碼算法作為早期的極化碼解碼算法，糾錯性能在無限碼長下能夠達(dá)到信道容量，但對中短碼的解碼性能較差[5-7]。串行抵消列表(successive cancellation list, SCL)解碼算法在SC解碼的搜索路徑上有了相應(yīng)擴展，提高了解碼性能，但也抬升了計算復(fù)雜度[8-10]。目前，性能最佳的極化碼解碼算法當(dāng)屬有循環(huán)冗余校驗(cyclic redundancy check, CRC)輔助的串行抵消列表(CRC-SCL)解碼算法，它可使極化碼解碼時在校驗性能方面與低密度校驗碼(low density parity check code, LDPC)相接近[11-13]，其糾錯性能更強，但計算復(fù)雜度也更高。

考慮到SCL算法同時對L條路徑進(jìn)行搜索解碼，這是影響其計算復(fù)雜度的主要原因。本文擬通過動態(tài)調(diào)節(jié)L值的大小，并對解碼序列進(jìn)行比特翻轉(zhuǎn)，以此來降低CRC-SCL算法的計算復(fù)雜度。

1 極化碼解碼方案及改進(jìn)

1.1 極化碼解碼方案

SC解碼是伴隨著極化碼同時被提出的[4]，其算法以似然比的取值為判決準(zhǔn)則，按比特序號從小到大的順序依次進(jìn)行解碼。當(dāng)碼長N趨于無限長時，由SC解碼算法可得無誤碼的解碼比特，且其時間復(fù)雜度僅為O(NlogN)。但是，對于中短碼，因信道不能完全極化，SC解碼會導(dǎo)致部分解碼錯誤。另外，SC解碼器在解碼過程中依賴于已經(jīng)解出的信息比特，一旦某解碼比特出現(xiàn)錯誤，勢必會影響后續(xù)多個解碼比特，最終降低解碼性能。

在SC解碼的搜索路徑上進(jìn)行相應(yīng)擴展，可得SCL解碼算法[8-9]。SCL解碼選取路徑度量值較大的L條路徑，同時對其進(jìn)行解碼搜索，而其他路徑則被丟棄[10]。根據(jù)解碼樹按位搜索，若某層路徑數(shù)小于L，則保留全部路徑；若路徑數(shù)大于L，則保留度量值較大的前L條候選路徑，繼續(xù)下層路徑選擇，直至解碼到最底層；從最底層路徑度量值最大的L條路徑序列還原發(fā)送比特。通常情形下，L值越大，解碼誤碼率越低，但內(nèi)存使用量也越大。

CRC在信息論和編碼空間中被應(yīng)用于錯誤檢測和糾錯[11]。CRC-SCL解碼即是在發(fā)送比特的信息位中加入CRC碼，先進(jìn)行SCL解碼，對保留下的L條路徑進(jìn)行CRC校驗，并在通過CRC校驗的路徑中還原發(fā)送比特，從而提高解碼算法的糾錯能力[12-13]。糾錯編碼器的輸入塊由長度為k的信息位和長度為m的CRC校驗碼組成，后者可看作糾錯碼源比特的一部分。

1.2 改進(jìn)后的低復(fù)雜度CRC-SCL解碼

設(shè)計新的解碼器，以降低CRC-SCL算法的計算復(fù)雜度。

改變SCL解碼算法中固定的L值，使其成倍數(shù)遞增。固定的L值具有一定缺陷：L值定義過小，不能正確還原發(fā)送比特；L值定義過大，又會增加算法的計算復(fù)雜度。為了解決L值定義過大或過小帶來的解碼問題，選取動態(tài)可調(diào)節(jié)L值的CRC-SCL解碼器。解碼器最初采用SC解碼，若序列未通過CRC校驗，則進(jìn)行L值為2的SCL解碼，若解碼一直未成功，迭代地增加L，直至L達(dá)到預(yù)定義的Lmax值。

將未通過CRC校驗的比特位按其似然比排序，選取似然比最小的比特位進(jìn)行翻轉(zhuǎn)，構(gòu)成新的序列再次進(jìn)行CRC校驗，校驗成功便輸出信號，否則執(zhí)行L擴充解碼。

改進(jìn)后的低復(fù)雜度CRC-SCL解碼算法流程，可具體描述如下。

步驟1對輸入信號序列進(jìn)行SC解碼。

步驟2SC解碼完成后，在SC解碼保留路徑上執(zhí)行CRC校驗。

步驟3如果路徑通過CRC校驗，則輸出該路徑，并退出解碼，否則轉(zhuǎn)到步驟4。

步驟4先對解碼序列進(jìn)行比特翻轉(zhuǎn)，再進(jìn)行CRC驗證，若通過則輸出路徑，否則執(zhí)行步驟5。

步驟5選擇L，執(zhí)行SCL解碼，在SCL解碼保留路徑上執(zhí)行CRC校驗。

步驟6如果有路徑通過CRC校驗，則輸出路徑，并退出解碼，否則轉(zhuǎn)到步驟8。

步驟7對解碼序列進(jìn)行比特翻轉(zhuǎn)再進(jìn)行CRC校驗，如果該條路徑通過CRC校驗，則輸出路徑，否則執(zhí)行步驟8。

步驟8將L更新為2×L，如果L≤Lmax，則執(zhí)行步驟5，否則輸出路徑度量值最大的序列并退出解碼。

2 仿真結(jié)果

在加性高斯白噪聲(additive white Gaussian noise, AWGN)信道，使用含CRC的極化碼(1024，512)，仿真信號由二進(jìn)制相移鍵控調(diào)制(binary phase shift keying, BPSK)調(diào)制?？紤]到CRC長度對極化碼解碼性能的影響，采用16位CRC校驗碼[14-15]。

選取參數(shù)N=1 024,k=512,m=16,在不同Eb/No下，各解碼算法的誤碼率如圖1所示。SC解碼性能遠(yuǎn)低于CRC-SCL解碼性能，改進(jìn)算法當(dāng)Lmax=8和Lmax=16時分別與原CRC-SCL算法當(dāng)L=8和L=16時的解碼性能非常接近。

圖1 各解碼算法的誤碼率

隨著Eb/No增加，改進(jìn)后的低復(fù)雜度CRC-SCL解碼器更容易成功解碼，且其列表長度的平均值也會變得更小，逐漸趨近于SC解碼算法的L值。各算法成功解碼的列表長度如圖2所示。

(a) Lmax=16

(b) Lmax=32

(c) Lmax=128

當(dāng)Lmax=16，Eb/No=2 dB時，改進(jìn)后的低復(fù)雜度CRC-SCL解碼算法雖并不比SC解碼算法具有更小計算量，但其成功解碼所選列表長度的均值接近于2，相比于L=16對應(yīng)的SCL解碼算法，其計算復(fù)雜度還不到后者的1/8。

當(dāng)Lmax=32，Eb/No=2 dB時，或當(dāng)Lmax=128，Eb/No=1.8 dB時，改進(jìn)后的低復(fù)雜度CRC-SCL解碼算法所選列表長度的均值，已非常接近于SC解碼的L值。

所選列表長度越小，算法的計算復(fù)雜度越低，故從仿真結(jié)果可知，經(jīng)過改進(jìn)后的CRC-SCL解碼器能夠降低解碼復(fù)雜度，且Eb/No越高，復(fù)雜度降低越明顯。當(dāng)Eb/No=1.4 dB時，與原CRC-SCL算法相比，改進(jìn)算法取Lmax=16時的計算復(fù)雜度平均降低62.5%，取Lmax=32時的計算復(fù)雜度平均降低87.9%。

3 結(jié)語

通過動態(tài)調(diào)節(jié)列表長度以及對序列進(jìn)行比特翻轉(zhuǎn)，改進(jìn)CRC-SCL解碼算法，可降低其計算復(fù)雜度。使用具有16位CRC的極性碼(1024,512)進(jìn)行仿真實驗，結(jié)果顯示，當(dāng)Lmax=32，Eb/No=2 dB時，或當(dāng)Lmax=128,Eb/No=1.8 dB時，改進(jìn)算法的計算復(fù)雜度已接近于SC解碼算法的計算復(fù)雜度。