一種基于奇偶校驗碼級聯(lián)極化碼的低復雜度譯碼算法

劉順蘭 王 燕

(杭州電子科技大學電子信息學院 杭州 310018)

1 引 言

極化碼于2009年由Arikan[1]首次提出，是唯一可以理論上證明可達到任意二進制離散無記憶對稱信道容量的新型高效信道編碼技術，并且由于其較低的編、譯碼復雜度等優(yōu)勢，受到了廣泛的關注，因此，極化碼成為近年來最具吸引力的信道編碼之一[2-4]，成功入選5G標準，作為增強移動寬帶場景中控制信道的編碼方案[5]。當極化碼的長度趨于無窮時，才能更好地達到信道容量，然而在中短碼長時性能不佳。為了提高極化碼的糾錯性能，先后提出了許多不同的譯碼方法。文獻[1]提出采用串行抵消(Successive Cancellation, SC)譯碼算法，由于SC譯碼算法是一種次優(yōu)的譯碼算法，在有限長碼長中性能有待提升，并且在譯碼時前面的信息位一旦判決出錯，將會影響后面的譯碼結果，造成錯誤傳播。為了解決這一問題，文獻[6,7]提出了串行抵消列表(Successive Cancellation List, SCL)譯碼算法，該算法通過擴張譯碼路徑，提高了譯碼結果的正確性，但增加了時間復雜度和空間復雜度，成為一套功能強大并在不斷改進的一種算法[8]。文獻[9]引入循環(huán)冗余校驗碼與極化碼級聯(lián)，提出CRC輔助SCL譯碼算法(Cyclic redundancy Check Aided SCL, CA-SCL)，有助于在SCL譯碼的列表中挑選出正確的譯碼結果。此后文獻[10]提出的奇偶校驗碼級聯(lián)極化碼引入校驗比特，在譯碼過程中能夠實時校驗譯碼路徑，即奇偶校驗碼輔助SCL譯碼算法(Parity Check Aided Successive Cancellation List,PC-SCL)。這兩種譯碼算法雖然在性能上優(yōu)于SC譯碼和SCL譯碼，但是與SCL譯碼一樣，有著較大的復雜度。

根據(jù)極化碼極化原理可知，在碼長趨于無窮時，一部分信道的信道容量趨于1，另一部分的信道容量趨于0，在信道容量趨于1的信道上傳輸信息比特，趨于0的信道上傳輸凍結比特，而對于有限碼長，存在著未被完全極化的子信道，這些子信道的可靠性較低?；谏鲜龇治觯疚奶岢隽艘环N基于奇偶校驗碼級聯(lián)極化碼的低復雜度譯碼算法，即基于奇偶校驗碼級聯(lián)極化碼的串行抵消局部列表算法(Parity Check aided Partial Successive Cancellation List, PC-PSCL)，對于可靠性較低的信息子信道進行SCL譯碼，并加入奇偶校驗比特輔助校驗，其余可靠性較高的信息子信道僅采取SC譯碼算法，該算法降低了復雜度，并在性能上逼近PCSCL譯碼算法。

2 極化碼

極化碼的構造是編碼中的一個重要步驟，根據(jù)極化碼的構造可以進行極化子信道的選擇。目前常用的子信道可靠性估計算法有：Arikan[1]首次提出極化碼時給出了一種只針對二進制擦除信道的巴氏參數(shù)法；Mori等人[11]借鑒對 LDPC碼的研究成果，提出了密度進化法(Density Evolution, DE)；Trifonov[12]提出的適用于高斯信道的高斯近似法(Gaussian Approximation, GA)，目前已成為一種比較有效的度量方法；Schürch[13]揭示極化碼子信道間的偏用通序關系，華為提出了利用極化權重(Polarization Weight, PW)，并引入?yún)?shù)β擴展，來計算AWGN信道下子信道可靠度的算法[14]。在構造完成后，就可以根據(jù)極化碼極化原理將信息比特與凍結比特混合，即可靠性比較高的子信道傳輸信息比特，可靠性比較低的子信道傳輸凍結比特。

對于給定的碼長N，極化碼的編碼方式為

SCL 譯碼算法通過對信息位進行路徑擴展，相對于 SC 譯碼算法提高了譯碼的可靠性，PC-SCL譯碼算法在SCL譯碼算法的基礎上添加了PC校驗比特，輔助路徑篩選，進一步提高了譯碼算法的性能，但與SCL譯碼算法一樣，L倍路徑的增加帶來了較大的復雜度。本文提出的PC-PSCL譯碼算法在保持與PC-SCL譯碼算法相近性能的情況下，復雜度有了較大的下降，如下文所述。

3 PC-PSCL譯碼算法

3.1 理論分析

圖1 PC-Polar級聯(lián)方案

3.2 外碼構造

本文提出的PC-PSCL譯碼算法，在極化碼編碼前，需構造外碼塊，包括在傳輸信息比特的子信道中選擇相對較不可靠信息子信道以及奇偶校驗位。構造算法如下：

步驟1 根據(jù)高斯近似，子信道錯誤概率小于目標概率的子信道傳輸信息比特，在傳輸這些信息比特中的子信道仍存在有些信道相對而言較不可靠，用其索引下標值構成集合B，B ?A，在B中選擇M ?1個可靠性最高的信息子信道放置奇偶校驗位，則B集合以奇偶校驗比特為限，被分成M個外碼塊，第M位奇偶校驗位取B中的最后一位索引，保證檢驗B中所有的信息比特。如圖2所示，pj ∈B, j=1,2,...,M表示第j個奇偶校驗位的索引，因此B集合被劃分為M個外碼塊，表示為Tj ?B,j=1,2,...,M。

圖2 PC-PSCL譯碼算法外碼構造示意圖

例如，在碼長N=256，信噪比(Signal to Noise Ratio, SNR)等于1.5 dB時，經(jīng)過高斯近似得到的子信道錯誤概率如圖4所示。子信道錯誤概率越接近0，說明該信道越可靠，反之，子信道錯誤概率越接近0.45，說明該信道越不可靠，而子信道錯誤概率處于0到0.45之間的信道稱為未完全極化信道。假設碼率R=1/2，選定目標概率0.0425，子信道錯誤概率低于0.0425的信道傳輸信息比特，反之傳輸凍結比特。在信息比特中選擇較不可靠信息位，取信息比特總數(shù)的50%，此時b=50%，集合B為子信道錯誤概率低于0.0425的64個信道，取奇偶校驗比特個數(shù)M為5，按照上述的步驟1選取奇偶校驗比特集合P，P中前4個奇偶校驗位選擇集合B中子信道錯誤概率較低的信道，第5位取集合B中的最后一個比特，則P={64,119,159,217,233}，因此外碼塊T={T1,T2,...,TM}的取值如表1所示。

3.3 PC-PSCL譯碼具體實現(xiàn)

由上述構造算法可知，本文提出的級聯(lián)極化碼包含多個外碼塊，以一個外碼塊為例闡述譯碼過程，具體算法流程圖如圖5所示，多個譯碼塊類似。假設外碼塊為T={t1,t2,...,tm}，i表示譯碼比特索引值。

當1≤i

當t1≤i ≤tm時，該段主要有兩種情況：

圖3 含有外碼塊碼長為N的極化碼示意圖

圖4 N = 256信道極化示意圖

表1 外碼塊T的取值

圖5 PC-PSCL譯碼算法流程圖

(1)i ∈T。說明第i位是外碼塊中的比特，此時有兩種情況，一是被選取的較不可靠的信息位，將該信息位進行路徑擴展，同時保留0和1兩條路徑，并記錄路徑度量值。假設此時擴展路徑一共有l(wèi)條，當l大于設定的最大保留路徑數(shù)Lmax時，選擇路徑度量較小的Lmax條路徑保留；二是第i位是奇偶校驗位，根據(jù)式(23)奇偶校驗方程得到奇偶校驗估計值，保留一條或多條通過奇偶校驗的路徑，路徑數(shù)記為Lp，若奇偶校驗均未通過，則選擇路徑度量最小的Lp條路徑作為外碼塊區(qū)間內的估計序列。

(2)i∈/T。表明第i位是凍結位或者較可靠的信息位，若該位是信息位則進行SC譯碼判決，記錄對數(shù)似然比，若是凍結位直接判為0。

當tm

由上述的譯碼過程分析可知，PC-PSCL譯碼算法只對外碼塊中的信息比特分支擴展、奇偶校驗，其余比特均只進行SC譯碼。本文的譯碼算法利用了SC譯碼具有較低復雜度這一優(yōu)點，在外碼塊中引入SCL譯碼和奇偶校驗，彌補了SC譯碼性能不佳的問題，相對于PC-SCL譯碼算法既降低了復雜度，又保持了較好的性能。

3.4 PC-PSCL譯碼算法復雜度分析

4 仿真結果和分析

本文在加性高斯白噪聲信道下對比了幾種不同譯碼算法的誤幀率(Frame Error Rate, FER)，仿真次數(shù)為15000次。

圖6 在不同譯碼算法下存儲空間占用情況

表2 3種譯碼算法復雜度對比

圖7 不同碼長、不同L p情況下譯碼算法的性能

圖7是不同碼長，碼率為1/2，Lmax=8，奇偶校驗比特數(shù)M為5，b=50%的仿真結果，其中Lp取值分別為1, 2, 4。如圖7(a)中N=512，由圖7(a)可知：在PC-PSCL譯碼算法中，當Lp逐漸增大時，性能越來越好，但復雜度也增加，具體復雜度情況如表3所示。在Lp=2時，PC-PSCL譯碼算法性能已經(jīng)優(yōu)于SCL譯碼算法，與PC-SCL譯碼算法有著較小的差距，但空間復雜度節(jié)省了近63.09%；Lp=4時，PC-PSCL譯碼算法性能逼近PC-SCL譯碼算法，比SCL譯碼算法獲得了0.5 dB的增益，但較PC-SCL譯碼算法空間復雜度節(jié)省了近38.09%，時間復雜度節(jié)省了近15.63%。若考慮到性能和復雜度的折中，以犧牲較小的性能為代價，Lp=2也不失為一個較好的選擇。圖7(b)考慮N=128和N=1024的情況，由圖7(b)可以看到碼長越長，譯碼性能越好，在Lp=4時PC-PSCL譯碼算法的性能與PC-SCL譯碼算法的性能相近，可以推斷出在Lp=4時，PC-PSCL譯碼算法中經(jīng)過奇偶校驗保留的路徑已經(jīng)較為準確。

圖8是碼長為256，碼率為1/2，Lmax=8，奇偶校驗比特數(shù)M為5，Lp=4，選取的較不可靠信息比特占比b分別為20%, 30%, 50%的仿真結果。由圖8可以看出：在b=20%和30%的時候，PCPSCL譯碼算法的性能較PC-SCL譯碼算法有著一定的差距，但b增大至50%時，PC-PSCL譯碼算法的性能逼近PC-SCL譯碼算法。因此，隨著b的增大，擴展信息比特變多，PC-PSCL譯碼算法性能逐漸變好，同時復雜度也增大，如表4所示。

表3 N = 512時兩種譯碼算法復雜度對比

圖8 N = 256時不同b譯碼算法的性能

表4 N = 256時兩種譯碼算法復雜度對比

5 結束語

基于PC碼輔助的SCL譯碼算法，本文提出了一種低復雜度譯碼算法-PC-PSCL譯碼算法，對選取的局部信息比特進行奇偶校驗和SCL譯碼。仿真結果顯示，本文提出的譯碼算法在奇偶校驗后保留合適的路徑情況下有著和PC-SCL譯碼算法相近的性能，但是復雜度大大降低。