動態(tài)擾動輔助的串行抵消雙比特翻轉(zhuǎn)Polar譯碼算法*

曾俏麗,陳海強,周 泉,劉遠博,孫友明,黎相成

(1.廣西大學 計算機與電子信息學院,南寧530004;2.廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點實驗室,南寧530004)

0 引 言

Polar碼是首個可在理論上被證明達到信道容量的編碼技術(shù)。Arikan給出其最基礎(chǔ)的串行抵消(Successive Cancellation,SC)譯碼算法,但譯碼性能有限。Tal等人[1]提出串行抵消列表(Successive Cancellation List,SCL)譯碼算法,其性能可逼近最大似然(Maximum Likelihood,ML)譯碼。在此基礎(chǔ)上,Niu等人[2]將CRC碼與Polar碼進行級聯(lián),提出CA-SCL譯碼算法,獲得了優(yōu)于低密度奇偶校驗碼(Low Density Parity Check Code,LDPC)和Turbo碼的譯碼性能[3]。這些算法獲得了譯碼性能的提升,但增加了譯碼空間復(fù)雜度。Afisiadis等人[4]提出串行抵消翻轉(zhuǎn)(Successive Cancellation Flip,SCF)譯碼算法,在譯碼性能提升的同時獲得與SC譯碼相同的空間復(fù)雜度。Gerrar等人[5]將加噪譯碼的思想運用于SC譯碼上,提出串行抵消擾動(Successive Cancellation Perturbation,SCP)譯碼算法。Xiao等人[6]對SCP進行改進,提出了動態(tài)擾動的串行抵消(Dynamic Perturbation SC,DP-SC)譯碼算法。相比于原始的SC譯碼,SCF和SCP雖然可以獲得一定的性能增益,但譯碼性能仍與CA-SCL存在較大的差距。

本文針對SCF受限于單比特翻轉(zhuǎn)而性能提升有限問題,提出雙比特翻轉(zhuǎn)的SCF(Successive Cancellation Flip with 2 Bits,SCF2))譯碼算法;針對SCP擾動方差初始值固定的問題,通過仿真實驗獲取最適合的初始方差值,并對擾動噪聲的方差進行改動,提出了改進算法。在此基礎(chǔ)上,提出了一種動態(tài)擾動輔助的串行抵消雙比特翻轉(zhuǎn)(Dynamic Perturbation-Aided SCF2,DPA-SCF2)譯碼算法,并對其譯碼復(fù)雜度和性能進行了分析。仿真結(jié)果顯示,所提出的DPA-SCF2算法在性能上獲得了進一步的提升。

1 系統(tǒng)模型和符號定義

將二進制離散無記憶信道(Binary Input Discrete Memoryless Channel,BI-DMC)表示為W:X→Y,X∈{0,1}為輸入信號,Y∈為輸出信號。N個W經(jīng)信道極化得到N個極化信道其中一部分極化信道的信道容量用于放置信息比特;另一部分用于存放凍結(jié)比特。

2 改進的SCP譯碼算法

在LDPC譯碼算法的研究中,隨機擾動就被用于提高譯碼性能[7-8]。而對于Polar碼,隨機擾動最早被用于BP譯碼算法。這一策略加快了BP譯碼算法的收斂速度并有效提升了其譯碼性能[9-10]。

考慮到重復(fù)擾動會帶來相同的譯碼結(jié)果,文獻[6]提出了DP-SC譯碼算法。該算法采用估計序列列表P來調(diào)整σp,以便更大程度地糾正接收值的錯誤。文獻[5-6]提出的兩種算法的初始σp均固定,但經(jīng)過實驗仿真發(fā)現(xiàn),不同Polar碼的最佳初始σp值是不同的。因此,本文根據(jù)仿真結(jié)果進行初始σp值設(shè)定?？紤]到調(diào)整σp是為了獲得方差更大的噪聲,本文提出直接對方差σp2進行改進。為了更快速簡潔地獲得P中最可靠的接收序列,本文對估計序列選擇方案進行改進。

2.1 初始σp值的選擇和σp2的步進設(shè)置

本文對碼長128、碼率1/2的Polar碼進行測試,其中CRC設(shè)置為24。本文以σp=0.25進行左右擴展,對不同初始值下的SCP進行性能仿真。仿真結(jié)果表明,該Polar碼的最優(yōu)σp處在于0.3～0.35之間。為了后續(xù)調(diào)整方便,將其初始σp設(shè)置為0.3。

為了在更少的擾動次數(shù)下更快地得到正確估計序列,本文不再對噪聲的方差平方根σp做修正,轉(zhuǎn)而直接對噪聲的方差σp2做修正,當出現(xiàn)相同估計序列后,使σp2=σp2+Δt,Δt為步進長度。通過仿真試驗,得到(128,64)的Polar碼的最優(yōu)Δt為0.005。該結(jié)果將用于后續(xù)的改進SCP譯碼算法中。

2.2 接收估計序列選擇

文獻[6]提出如式(1)的可靠度判斷方法:

(1)

(2)

如上所示,公式(2)僅使用ci與其對應(yīng)RLL相加做一級運算,相較于公式(1)使用了乘方運算這一三級運算,降低了運算復(fù)雜度。

2.3 改進的SCP譯碼算法描述

根據(jù)以上描述,改進的SCP算法可總結(jié)如下:

步驟1 設(shè)置最大擾動次數(shù)為Pmax,擾動次數(shù)P_num=0,將估計列表P內(nèi)部數(shù)據(jù)清零。對Y進行SC譯碼并作CRC校驗,若能通過則輸出,反之執(zhí)行步驟2。

步驟6 執(zhí)行σp2=σp2+Δt,且使得擾動次數(shù)P_num=P_num+1。重復(fù)步驟2直至P_num=Pmax。

2.4 改進SCP譯碼算法的性能分析

在這部分,本文使用校驗位長度為24 b的CRC碼與信息位長度為40 b的Polar碼級聯(lián),得到級聯(lián)CRC-Polar碼,其參數(shù)為(128,64)。在AWGN信道中進行SC、CA-SCL2、SCP、DP-SC和本文所提的改進SCP譯碼算法的仿真,其誤幀率(Frame Error Rate,FER)性能如圖1所示。由圖可見,隨著擾動次數(shù)的增加,改進SCP譯碼的FER性能逐漸提升,當Pmax等于16時,改進的SCP譯碼算法相較于CA-SCL2譯碼算法 將獲得約0.1 dB的FER性能增益;當Pmax達到32時,增益將提高至0.25 dB,相比于DP-SC譯碼算法也有約0.1 dB的FER增益。

圖1 N=128,R=1/2的不同譯碼算法性能Fig.1 FER performance of different decoding algorithms (N=128,R=1/2)

3 雙比特翻轉(zhuǎn)譯碼算法

該算法的主要實現(xiàn)步驟如下:當初始SC譯碼失敗后,對初始SC譯碼得到的估計序列進行|RLL|排序,選取其中|RLL|最小的T個比特組成翻轉(zhuǎn)集合。在后續(xù)的每一次翻轉(zhuǎn)譯碼過程中,依次在翻轉(zhuǎn)集合中選擇一個比特作為翻轉(zhuǎn)比特,使該比特前的估計比特保持不變,對該比特進行0→1或1→0的翻轉(zhuǎn),并在此基礎(chǔ)上繼續(xù)進行SC譯碼。重復(fù)執(zhí)行上述的翻轉(zhuǎn)譯碼過程直至譯碼成功,或達到最大譯碼次數(shù)。但對于SC這類串行譯碼算法,其譯碼失敗的原因往往不是單個比特錯誤造成的。為了提高SC譯碼的糾錯能力,本文提出一種雙比特翻轉(zhuǎn)(SCF2)譯碼算法,給予SC譯碼2次糾錯機會,在不造成譯碼復(fù)雜度大幅度上升的同時獲得較SCF譯碼算法更優(yōu)異的譯碼性能。

3.1 翻轉(zhuǎn)比特位置的選擇

為獲取翻轉(zhuǎn)比特位置集合F,需對估計序列中的K個信息位進行|RLL|排序,選取其中值最小的T個比特,將其下標放入F中?？紤]到估計比特的正確性正比于|RLL|,本文提出在翻轉(zhuǎn)2位估計比特時,將F[1]對應(yīng)的估計比特固定為第一個翻轉(zhuǎn)比特,再將F[2]～F[T]對應(yīng)的T-1比特分別作為第二個翻轉(zhuǎn)比特與之結(jié)合,構(gòu)成雙比特翻轉(zhuǎn)集。為了驗證F[1]對雙比特翻轉(zhuǎn)譯碼的性能影響,本文對圖2所示的兩種翻轉(zhuǎn)比特選取方式進行了測試。

(a)翻轉(zhuǎn)比特下標為F[1]+F[i]

(b)翻轉(zhuǎn)比特下標為F[i]+F[i+1]圖2 翻轉(zhuǎn)比特下標示意圖Fig.2 Flip bit index illustration

圖2(a)所示方案為第一位翻轉(zhuǎn)比特下標固定為F[1],第二位翻轉(zhuǎn)比特下標依次為F[i],i∈2,3,…,T。圖2(b)所示方案為第一位翻轉(zhuǎn)比特下標依次為F[i],i∈1,2,…,T-1,第二位翻轉(zhuǎn)比特下標為F[i+1]。測試結(jié)果表明,圖2(a)所示翻轉(zhuǎn)比特選取方案較圖2(b)方案可獲得更大的性能增益。

3.2 雙比特翻轉(zhuǎn)譯碼算法描述

雙比特翻轉(zhuǎn)譯碼算法流程如下:

步驟3 選取F[T_num]對應(yīng)比特為翻轉(zhuǎn)比特進行SC重譯碼并做CRC校驗,校驗通過則輸出,否則令T_num=T_num+1,并判斷是否滿足T_num≤Tmax:若滿足,則重新執(zhí)行步驟3;若不滿足,則設(shè)置T_num=2,執(zhí)行步驟4。

步驟4 選取F[1]和F[T_num]對應(yīng)比特為翻轉(zhuǎn)比特進行重譯碼,并對重譯碼結(jié)果進行CRC校驗,通過則輸出,反之則令T_num=T_num+1,判斷是否滿足T_num≤Tmax,滿足則返回執(zhí)行步驟4,反之則退出譯碼程序。

3.3 雙比特翻轉(zhuǎn)譯碼算法的性能分析

本文使用校驗位長度為24 b,參數(shù)為(128,64)的級聯(lián)CRC-Polar碼在AWGN信道下進行翻轉(zhuǎn)譯碼算法的性能測試。分別使用單比特翻轉(zhuǎn)譯碼算法(SCF)和雙比特翻轉(zhuǎn)譯碼算法(SCF2)進行譯碼操作,其結(jié)果如圖3所示,圖中譯碼算法名稱中的(xb)表示該算法的翻轉(zhuǎn)集合包含了x個翻轉(zhuǎn)比特。由圖可見,當翻轉(zhuǎn)集合達到16時,所提算法可獲得近似于CA-SCL4的譯碼性能,而SCF在此情況下與CA-SCL4還存在0.25～0.35 dB的性能差異。

圖3 N=128,R=1/2的SCF2和SCF譯碼性能Fig.3 FER performance of SCF2 and SCF (N=128,R=1/2)

4 動態(tài)擾動輔助的串行抵消雙比特翻轉(zhuǎn)譯碼算法

4.1 動態(tài)擾動輔助的串行抵消雙比特翻轉(zhuǎn)譯碼算法描述

雖然兩種改進算法可以帶來譯碼性能的提升,但是改進的SCP譯碼算法無法針對某個指定比特進行糾正;當譯碼錯誤多于2 b時,SCF2則無法糾正?；诖?本文提出一種動態(tài)擾動輔助的串行抵消2比特翻轉(zhuǎn)(DPA-SCF2)譯碼算法,在進行隨機擾動后仍無法正確譯碼時,轉(zhuǎn)而對其執(zhí)行SCF2譯碼。算法描述如下:

4.2 動態(tài)擾動輔助的串行抵消雙比特翻轉(zhuǎn)譯碼算法性能分析

仿真采用2PSK調(diào)制的(128,64),(128,96)以及(256,128)3組Polar碼,其CRC校驗比特都為24 b。仿真對比的算法包括DPA-SCF2譯碼算法、SC譯碼算法、CA-SCL譯碼算法以及SCF、SCP的改進譯碼算法,仿真結(jié)果如圖4～6所示。圖中擾動譯碼算法名稱后的(x)表示算法執(zhí)行x次擾動運算,圖5和圖6的T_max=16。

(a)翻轉(zhuǎn)算法最大翻轉(zhuǎn)次數(shù)T_max=8

(b)翻轉(zhuǎn)算法最大翻轉(zhuǎn)次數(shù)T_max=16圖4 (128,64) Polar碼FER性能Fig.4 FER performance of Polar code (128,64)

圖5 (128,96) Polar碼FER性能Fig.5 FER performance of Polar code (128,96)

圖6 (256,128) Polar碼FER性能Fig.6 FER performance of Polar code (256,128)

由圖4可以看出,隨著T_max的增加,原本FER性能落后于改進SCP的SCF2譯碼算法將超越改進SCP而接近CA-SCL4。受SCF2在T_max增加時所帶來的影響,DPA-SCF2在T_max=16時獲得比T_max=8高出約0.35 dB的FER增益。當最大擾動次數(shù)P_max達到8時,DPA-SCF2較CA-SCL4可獲得約0.5 dB的FER性能提升。從圖5可以看出,當T_max=16,P_max=8時,DPA-SCF2較CA-SCL4可獲得約0.45 dB的FER性能提升。從圖6可以看出,DPA-SCF2較CA-SCL4最多可以獲得約0.25 dB的性能增益。

5 復(fù)雜度分析

首先,對SCF2譯碼算法和改進的SCP譯碼算法的復(fù)雜度進行分析。對SCF2而言,其復(fù)雜度可計算為Tmax次單比特翻轉(zhuǎn)譯碼的復(fù)雜度O(Tmax·NlbN)和(Tmax-1)次雙比特翻轉(zhuǎn)譯碼的復(fù)雜度O((Tmax-1)·NlbN)之和,即O((2Tmax-1)·NlbN),而Tmax為最大翻轉(zhuǎn)次數(shù),因此O((2Tmax-1)·NlbN)也是一次SCF2譯碼所產(chǎn)生的最大譯碼復(fù)雜度。對改進的SCP譯碼算法而言,其復(fù)雜度相當于Pmax次SC譯碼,即O(Pmax·NlbN)。在此基礎(chǔ)上,可以輕松地獲得動態(tài)擾動輔助的串行抵消雙比特翻轉(zhuǎn)譯碼算法的譯碼復(fù)雜度。

對DPA-SCF2而言,其第2步執(zhí)行的SC譯碼,譯碼復(fù)雜度為O(NlbN)。而第3步和第4步均在當前幀的SC譯碼失敗后才會被執(zhí)行,假設(shè)每幀SC譯碼失敗的概率為Pe,則第3步的平均譯碼復(fù)雜度可計算為O(Pe·(2Tmax-1)·NlbN),第4步的可計算為O(Pe·Pmax·NlbN)。由前面的算法描述可以看到,當改進SCP譯碼失敗后,SCF2會被繼續(xù)執(zhí)行。因此,第3、4步的譯碼復(fù)雜度可共同計算為O(Pe·(Pmax+1)·(2Tmax-1)·NlbN) 。因此,總體上DPA-SCF2的平均譯碼復(fù)雜度為O(Pe·(Pmax+1)·(2Tmax-1)·NlbN+NlbN)。需要指出的是,式中的Pe反比于信道中的信噪比[11]。因此,當系統(tǒng)的信噪比增大到一定程度時,DPA-SCF2的譯碼復(fù)雜度接近SC譯碼的O(NlbN)。

為更直觀地顯示所提算法的復(fù)雜度,本文對SC譯碼算法、CA-SCL4譯碼算法、翻轉(zhuǎn)比特集合為8的SCF2譯碼算法、加噪次數(shù)為32的改進SCP譯碼算法,以及翻轉(zhuǎn)集合為8、加噪次數(shù)分別為4和8的DPA-SCF2譯碼算法這6組算法進行平均 SC 譯碼次數(shù)仿真,結(jié)果如圖7所示。

圖7 各算法平均SC譯碼次數(shù)對比Fig.7 Average SC decoding number for each algorithm

由圖7可見,當信噪比達到2.0 dB時,所提出的改進SCP譯碼算法、雙比特翻轉(zhuǎn)譯碼算法,以及動態(tài)擾動輔助的串行抵消雙比特翻轉(zhuǎn)譯碼算法均獲得了低于CA-SCL4的平均SC譯碼次數(shù);當信噪比增加時,上述算法的平均SC譯碼次數(shù)均趨向于1,可獲得接近SC譯碼算法的譯碼復(fù)雜度。

6 結(jié) 論

本文在SCP和SCF兩種Polar碼后處理譯碼算法的基礎(chǔ)上,提出了改進的SCP譯碼算法和雙比特翻轉(zhuǎn)譯碼算法(SCF2)。仿真實驗顯示,兩種改進的算法都能獲得一定的性能增益。結(jié)合本文提出的雙比特翻轉(zhuǎn)和可變方差擾動機制,進一步提出了一種動態(tài)擾動輔助的串行抵消雙比特翻轉(zhuǎn)(DPA-SCF2)譯碼算法。在復(fù)雜度方面,所提算法在大信噪比區(qū)域,其譯碼復(fù)雜度接近SC譯碼;在性能方面,相比于列表長度為4的循環(huán)冗余校驗輔助串行抵消列表(CA-SCL)譯碼算法,最大可獲得約0.5 dB的增益。需要指出的是,所提出的譯碼算法適用于不同的碼長和碼率,其譯碼性能隨著最大翻轉(zhuǎn)次數(shù)和最大擾動次數(shù)的增加而有不同程度的提升。