奇偶校驗和CRC級聯的極化碼編譯碼研究

張文宇，郭 銳

(杭州電子科技大學通信工程學院，浙江 杭州 310018)

0 引 言

由Arikan提出的極化碼是一種基于信道極化的信道編碼方案[1]，是目前理論上唯一能實現香農容量的方法，適用于任意二進制離散無記憶信道(Binary Discrete Memoryless Channel, B-DMC)，在加性高斯白噪聲信道(Additive White Gaussian Noise, AWGN)中也具有優(yōu)異的糾錯能力，是未來6G通信的主要候選方案之一[2]。串行抵消(Successive Cancellation, SC)算法[1]譯碼復雜度較低，但譯碼性能不夠理想。串行抵消列表(Successive Cancellation List, SCL)算法[3]通過保留多條譯碼路徑并從中選取可靠性最高的路徑作為輸出，性能優(yōu)于SC算法[4]，但計算復雜度是SC算法的L倍，其中L代表列表數。在SCL算法中引入循環(huán)冗余校驗(Cyclic Redundancy Check, CRC)可以有效提升譯碼性能，CRC輔助的列表譯碼(CRC Aided SCL, CA-SCL)算法[5]將一段很長的CRC比特連接在信息序列尾部。分段CRC輔助的極化碼[6]將校驗比特均勻插入到信息序列中，可以更及時地檢測錯誤的發(fā)生。將奇偶校驗和極化碼級聯，在中短碼長的情況下，可以提升一定的譯碼性能[7]。在SCL譯碼中引入奇偶校驗和CRC，在擁有優(yōu)于SCL算法譯碼性能的同時還能實現更低的譯碼復雜度[8]。雙奇偶校驗和CRC輔助的SCL算法[9]可以進一步提升譯碼性能，該算法以每2個奇偶檢驗比特為1組插入到極化碼中。減少路徑分裂次數的列表譯碼(Split Reduced Successive Cancellation List, SR-SCL)算法[10]提出一種新的路徑分裂規(guī)則，當滿足該規(guī)則時，說明極化子信道的可靠性足夠高，直接執(zhí)行硬判決而不是進行路徑分裂。此外，在路徑分裂的過程中還設定了閾值，用于刪除那些分裂次數較少的路徑。SR-SCL算法還證明，假設在某個特定比特之前的所有譯碼比特全部正確，在該特定比特之后可以將原有算法替換為SC譯碼，進而提出增強的SR-SCL(Enhanced Split-Reduced SCL, ESR-SCL)算法[10]，保持相似譯碼性能的同時降低了復雜度。

雖然SR-SCL算法的譯碼復雜度低于SCL算法，但譯碼性能較差。針對這一問題，本文提出一種奇偶校驗和CRC輔助的ESR-SCL算法，引入奇偶校驗比特及時刪除部分錯誤路徑，并通過CRC校驗選取可靠性最高的譯碼路徑作為輸出，有效提升了譯碼性能，降低了譯碼復雜度。

1 極化碼的編譯碼方案

1.1 極化碼的構造

1.2 譯碼原理

(1)

(2)

SC譯碼器采用的是硬判決方式。在中短碼長情況下，信道極化不充分，導致一些信息比特發(fā)生譯碼錯誤，發(fā)生錯誤傳播。針對這一缺點，SCL譯碼算法將每個譯碼路徑分裂成2個候選路徑，通過列表保留L(L代表列表數)條候選路徑，當路徑數大于列表數時，選取路徑度量值最大的L條路徑存入列表。路徑度量值可通過遞歸計算得到：

(3)

1.3 SR-SCL譯碼算法

SR-SCL是一種基于SCL算法的改進算法，在某些條件下不進行路徑分裂，判決是否進行分裂的公式為：

(4)

式中，Pe(ui)為第i個信息比特的錯誤概率。當譯碼比特的錯誤概率較低時，將不進行分裂。SR-SCL算法還引入了計數器對路徑進行剪枝的操作，對路徑在不分裂情況下的生存階段數ωl[i]進行計數。當路徑數大于列表數時，如果ωl[i]達到預先設定的閾值ω，刪除計數器的計數值小于ω的路徑。

2 奇偶校驗和循環(huán)冗余校驗級聯的極化碼

2.1 奇偶校驗和CRC級聯極化碼的結構

2.2 奇偶校驗位的構造

(5)

式中，σ2表示噪聲方差，φ(x)為一個單調遞減函數，可以近似計算為：

(6)

取信噪比為1 dB，碼長N為256，碼率R為0.5，計算得到未凍結比特信道的錯誤概率如圖1所示。圖1中，垂直虛線代表根據錯誤概率繪制的信息段邊界，極化碼被7條邊界分為8個信息段。通過不同信噪比劃分不同的突發(fā)錯誤段來構造奇偶校驗位，能更好地檢測和刪除信道產生的錯誤。

圖1 極化碼子信道的錯誤概率分布圖

對于(N,K)的極化碼，假設共有8個信息段和16個奇偶校驗比特，校驗方式為奇校驗，信息位的長度為K，前i個信息段的長度為Ki，xj表示第j個信息比特，所有的第1校驗位由之前所有的信息比特決定，第i(i是奇數)個奇偶校驗比特表示為：

(7)

當第1奇偶校驗位完成編碼后，由于預先設定為奇校驗，為了保證第1奇偶校驗位進行校驗時不受影響，則第2奇偶校驗位的編碼結果為：

pi=0i=2,4,6,8

(8)

譯碼階段首先通過第1奇偶校驗位進行校驗，若校驗不通過則直接刪除譯碼路徑，而第2奇偶校驗位的譯碼結果可直接通過硬判決得到，如果和預先已知的編碼結果不相符，說明譯碼發(fā)生錯誤，則調整該路徑的路徑度量值。采用二進制相移鍵控(Binary Phase Shift Keying, BPSK)進行調制，流程如圖2所示。

圖2 奇偶校驗和CRC輔助的SR-SCL譯碼算法流程

2.3 奇偶校驗和CRC級聯的極化碼譯碼

譯碼凍結比特和信息比特的過程和SR-SCL算法相同，不同之處在于增加了奇偶校驗和CRC校驗，譯碼階段分為2種情況，當譯碼信息比特時，遵循式(4)的分裂規(guī)則，若滿足條件則進行路徑分裂，若分裂后的路徑數大于L，將保留L條路徑度量值較小的路徑，同時在第i階段譯碼完成后根據計數器中記錄的值進行剪枝。由于正確的譯碼路徑只在極少情況下分裂甚至不進行分裂，計數器的閾值ω的大小將直接影響最終的譯碼性能，因此引入路徑分裂次數相對數的概念[13]，其定義為：

(9)

式中，m為路徑編號。設定只有在Sl[i]≥T的情況下才會刪除路徑，T為閾值。當譯碼校驗比特時，若為奇偶校驗比特，對于第1奇偶校驗比特，校驗并刪除那些錯誤的譯碼路徑；對于第2奇偶校驗位，硬判決如下：

(10)

如果譯碼結果不為0，說明譯碼發(fā)生錯誤，則根據式(3)調整該條路徑的度量值，最后通過CRC校驗列表中幸存的L條路徑。如果只有1條路徑通過檢測，將其作為最終輸出；如果有多條路徑通過了檢測，選擇其中路徑度量值最大的一條作為最終輸出；如果沒有路徑通過檢測，則直接在所有路徑中選擇路徑度量值最大的一條作為最終輸出。為了進一步降低譯碼復雜度，把一段較長的CRC比特序列插入第N-K/4+1個比特之后，將剩余的信息比特連接在該段CRC比特之后，記錄通過CRC校驗后的路徑，之后的信息比特采用逐位譯碼的SC譯碼算法。本文提出的奇偶校驗和CRC輔助的ESR-SCL(Parity Check and CRC Aided ESR-SCL, PC-CA-ESR-SCL)譯碼算法的具體流程描述如下。

輸入:信息比特和凍結比特的索引集合B,信息位碼長K,列表大小L,閾值T,碼長N for i=1 to N-K/4+1 do if i∈B then 執(zhí)行SR-SCL譯碼,判斷路徑是否分裂并根據L和T對路徑進行剪枝; else 執(zhí)行雙奇偶校驗,刪除沒有通過檢測的候選路徑; end if end for 執(zhí)行CRC校驗,如果第k條路徑通過了校驗則終止算法,僅保留第k條譯碼路徑;如果沒有路徑通過CRC校驗,保留列表中路徑度量值最大的一條譯碼路徑; for i=N-K/4+2 to N do 執(zhí)行SC譯碼 end for輸出:u ^N1

3 仿真實驗與分析

仿真實驗采用AWGN信道和BPSK調制，實驗仿真幀數為105，信噪比的范圍設定為0.5～2.5 dB，閾值T=7，列表大小L=8。對于仿真參數，保證所有仿真的有效碼率是一致的。例如，對于(512,256)的極化碼，R=0.5，校驗位的總數目固定為24，奇偶校驗比特的數目為P，CRC比特的數目為C，滿足P+C=24，則K=232，所有算法中的信息比特數目都是232個，即有效碼率Re=232/512。

3.1 仿真實驗結果

設定碼長N=256，奇偶校驗比特的數目P分別為8，12，16，對應的CRC比特數目C分別為16，12，8，組成3種校驗比特組合(8，16)，(12，12)，(16，8)，PC-CA-ESR-SCL和CRC輔助的SR-SCL(CA-SR-SCL)算法的譯碼性能如圖3所示，其中EbN0表示信噪比。從圖3可以看出，當信噪比較低時，無論奇偶校驗比特組合和CRC比特的分配方式如何，PC-CA-ESR-SCL算法的譯碼性能都優(yōu)于CA-SR-SCL算法；且在3種組合中，P=16，C=16的組合得到的譯碼性能最好；與P=8，C=16的組合相比較，在誤塊率(Block Error Rate, BLER)為10-2處可以獲得0.2 dB的性能增益，這是因為增加奇偶校驗比特的數目有助于在譯碼過程中提前檢測和刪除錯誤的譯碼路徑。

圖3 N=256時，不同校驗比特組合下的譯碼性能

設定奇偶校驗位和CRC的組合為P=16，C=8，CA-SR-SCL算法的CRC比特數為24，保證了2種算法信息比特的數目相同，碼長N=256，閾值T分別為4和7時，PC-CA-ESR-SCL和CA-SR-SCL算法的譯碼性能如圖4所示。從圖4可以看出，和CA-SR-SCL譯碼算法相比，碼長N=256，T=4的情況下，BLER為10-2時，PC-CA-ESR-SCL算法可以獲得的性能增益大約為0.25 dB；碼長N=256，T=7的情況下，BLER為10-2時的性能增益約為0.21 dB。

圖4 N=256時，不同譯碼算法的性能

取和圖4實驗相同的參數，碼長分別為512和128時，PC-CA-ESR-SCL和CA-SR-SCL算法的譯碼性能如圖5所示。從圖5可以看出，在相同信噪比和碼長的情況下，閾值T=7的譯碼性能好于T=4，這是因為增大閾值會在列表中保留更多條路徑，從而更有可能得到正確的譯碼路徑；在相同閾值、相同碼長和信噪比的情況下，PC-CA-ESR-SCL算法譯碼性能優(yōu)于CA-SR-SCL算法，這是因為PC-CA-ESR-SCL算法使用了奇偶校驗比特和CRC校驗，能及時刪除錯誤的譯碼路徑。

圖5 不同碼長下，不同算法的譯碼性能對比

3.2 譯碼復雜度分析

為了描述譯碼復雜度，譯碼每個信息比特的時延用W表示，假定每個階段幸存的譯碼路徑數為Li，則CA-SR-SCL算法的平均譯碼延遲為WS=W×Li×Nlog2N，PC-CA-ESR-SCL算法的平均譯碼延遲為：

(11)

式中，V表示信息比特的段數，經過奇偶校驗刪除部分錯誤路徑，并在第N-K/4+1個比特之后將譯碼算法替換為SC算法，這意味著有25%的信息比特通過SC算法譯碼，顯然可以得出Wm

表1 不同算法的平均列表大小

4 結束語

本文提出一種奇偶校驗和循環(huán)冗余校驗級聯的極化碼編譯碼方案。采用雙奇偶校驗和CRC相結合的方式，在一定程度上提升了譯碼性能；并在某個特定比特之后將原有算法替換為SC算法，降低了算法的譯碼復雜度。但是，本文是在AWGN信道下進行的仿真實驗，其實際應用價值有待進一步探討，后續(xù)將針對本文算法在更多通信系統(tǒng)中的應用展開進一步研究。