一種基于深度學(xué)習(xí)預(yù)測的極化碼路徑移位SCL譯碼算法

田 浩,吳曉富,張索非

(1.南京郵電大學(xué) 通信與網(wǎng)絡(luò)技術(shù)國家工程研究中心,江蘇 南京 210003;2.南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院,江蘇 南京 210003)

0 引言

極化碼[1]已被證明在連續(xù)相消(Successive Cancellation,SC)譯碼下可以實現(xiàn)二進制對稱信道容量。盡管如此,相對于最大似然譯碼的性能,碼長較短的極化碼在SC譯碼的條件下表現(xiàn)仍顯不足。因此,為了提高極化碼的譯碼性能,文獻[2]提出了連續(xù)相消列表 (Successive Cancellation List,SCL) 譯碼。該方法在譯碼過程中保持L條譯碼路徑,從而實現(xiàn)了高性能的譯碼。此外,文獻[3]提出了一種基于循環(huán)冗余校驗(Cyclic Redundancy Checksum,CRC)級聯(lián)極化碼的SCL譯碼方法(CRC-Aided SCL,CA-SCL),進一步提高了極化碼的譯碼性能。

當(dāng)CA-SCL譯碼器譯碼失敗時,原則上可以使用各種Post-Processing方法來進一步提高譯碼性能,這些方法通?；谡`碼位置預(yù)測來啟動多次譯碼過程,從而糾正前一次譯碼中出現(xiàn)的錯誤。SCL比特翻轉(zhuǎn)譯碼算法(SCL-Flipping)[4-5]可以看作是一種基于SCL譯碼的Post-Processing方法,但SCL-Flipping為達到理想性能需要進行的重新譯碼次數(shù)一般在10次以上,這不僅提高了譯碼復(fù)雜度,也無法滿足實際應(yīng)用對譯碼低時延的要求。文獻[6]提出了一種路徑移位(Shifted-Pruning)SCL譯碼方法,也是一種Post-Processing算法,其與比特翻轉(zhuǎn)不同的操作在于:采用路徑移位的方式來重新捕獲前一次譯碼中被淘汰的正確譯碼路徑,該算法的最大重新譯碼嘗試次數(shù)取決于關(guān)鍵位置集合(Critical Set)的大小。實驗結(jié)果表明,在重新譯碼次數(shù)相同的條件下,路徑移位譯碼算法的性能要優(yōu)于比特翻轉(zhuǎn)算法。在文獻[7-8]的Post-Processing處理中,利用了首輪譯碼過程中生成的信息來預(yù)測譯碼錯誤的位置,其性能雖然得到了提升,但是未能充分利用第一次譯碼過程中生成的信息,性能距離理論界限還有較大的差距。

近年來,鑒于深度學(xué)習(xí)在計算機視覺和自然語言處理中的發(fā)展,人們開始研究將深度學(xué)習(xí)應(yīng)用于提升極化碼SC或SCL譯碼性能的可能性。長短時記憶 (Long Short-Term Memory,LSTM) 網(wǎng)絡(luò)被用于SCL-Flipping的錯誤位置定位[9-10]。在文獻[11]中,提出了一種具有兩個可微分神經(jīng)計算機(Differentiable Neural Computer,DNC)的深度學(xué)習(xí)輔助SCL-Flipping算法,其中一個DNC用于對多個比特翻轉(zhuǎn)位置的排序,另一個DNC用于在比特翻轉(zhuǎn)譯碼嘗試中重新選擇錯誤比特位置。然而,由于上述方法需要多次重新譯碼嘗試,大大限制了其實際應(yīng)用。

本文提出了一種基于深度學(xué)習(xí)預(yù)測的極化碼路徑移位SCL算法。核心思路是利用深度神經(jīng)網(wǎng)絡(luò)準(zhǔn)確地預(yù)測SCL譯碼路徑首次丟失的錯誤節(jié)點位置,并在此處激活偏移量為L的路徑移位,以此來重新捕獲被淘汰的正確譯碼路徑。以碼率1/2、碼長128的極化碼為例,在SCL-32的基礎(chǔ)上,僅需要一輪額外的譯碼,其性能可以有效逼近該碼長的有限長碼性能界限。

1 極化碼、SCL譯碼及其Post-Processing

1.1 極化碼

通過上述編碼過程,極化碼可以實現(xiàn)信道極化的效果,將信息集中在部分位置上,使得在接收端進行解碼時更容易恢復(fù)出原始信息。同時,通過適當(dāng)選擇凍結(jié)比特的位置,可以在傳輸過程中對抗信道噪聲和干擾,提高通信系統(tǒng)的可靠性和性能。

1.2 SCL譯碼

(1)

對應(yīng)信息位的ui+1判決由對數(shù)似然比值決定,即:

(2)

而凍結(jié)比特位置的ui+1一般默認為0,無需判決。

與SC譯碼不同,SCL譯碼[12]不僅是保留一條路徑,而是動態(tài)維護一個大小為L的路徑列表。當(dāng)譯碼處于信息比特位置時,譯碼路徑進行分叉,可能會導(dǎo)致維護的譯碼路徑數(shù)量大于L。當(dāng)譯碼路徑數(shù)量大于L時,SCL譯碼器會根據(jù)最新的路徑度量來篩選出L條最優(yōu)路徑,該路徑度量值計算如下:

(3)

當(dāng)集合A中所有的位置都已被訪問過時,譯碼器會從存活下來的L條路徑中選擇路徑度量值最小的作為最佳譯碼路徑。對于CA-SCL譯碼器,只有通過CRC的路徑才能作為譯碼路徑,否則,視為譯碼失敗。

1.3 SCL譯碼的Post-Processing方法

CA-SCL譯碼器能夠通過CRC來判斷譯碼器是否譯碼成功,當(dāng)譯碼失敗時,可以采用Post-Processing方法啟動SCL再譯碼流程來提高譯碼性能。鑒于SCL譯碼的判決碼字是按比特節(jié)點順序譯出,因此SCL的Post-Processing方法是在上一次SCL譯碼過程中的可能錯誤位置作路徑修正從而再啟動一輪新的SCL譯碼,具體流程如圖1所示。圖中,(a)為一般Post-Processing流程,(b)為本文所提方案。

圖1 SCL譯碼的Post-Processing方法流程Fig.1 Post-Processing method flow for SCL decoding

首輪SCL譯碼將按照標(biāo)準(zhǔn)的譯碼流程執(zhí)行,隨后進行CRC。如果校驗通過,則譯碼成功,譯碼流程結(jié)束;否則,則認為本輪譯碼失敗。此時,對首輪譯碼所產(chǎn)生的中間過程信息進行分析,并根據(jù)譯碼置信度構(gòu)造關(guān)鍵位置集合,并從中取出第一位元素,然后開啟新的一輪譯碼。如圖1中(a)所示,在后續(xù)譯碼過程中,與第一輪譯碼不同的是,當(dāng)譯碼到達關(guān)鍵位置時,需要對該位譯碼結(jié)果做相應(yīng)調(diào)整。當(dāng)譯碼結(jié)果無法通過CRC時,無需再次構(gòu)造關(guān)鍵位置集合,只需要從首輪構(gòu)造的集合中按順序取出相應(yīng)元素。其他步驟均與首輪譯碼相同。

目前SCL譯碼主流的Post-Processing方法有比特翻轉(zhuǎn)和路徑移位兩種。比特翻轉(zhuǎn)是指在預(yù)測的錯誤位置處,對譯碼比特進行翻轉(zhuǎn);而路徑移位方法有所不同,路徑移位是指在當(dāng)前位置處不保留前L條路徑,而是保留第k～L+k條路徑,其中k表示路徑移位的大小。本文采用的Post-Processing方法即為路徑移位,并且k取值為L。

2 基于深度學(xué)習(xí)的SCL譯碼錯誤位置預(yù)測

2.1 SCL譯碼錯誤位置預(yù)測技術(shù)進展

目前,文獻中各種SCL譯碼的Post-Processing方法的主要差異是關(guān)鍵位置集合的選取[6-8]。文獻[6-7]采用了2L條路徑中的兩條關(guān)鍵路徑度量之差Δi來衡量當(dāng)前信息位可靠性的方法,即:

(4)

文獻[6-7]使用的方式有所不同,文獻[6]采用的是一種不依賴于實時信道的方式,通過多次模擬來統(tǒng)計Δi-Δi-1的大小,當(dāng)Δi-Δi-1<0時,則認為該比特位置i處譯碼置信度較低,故收集該比特位置作為關(guān)鍵位置集合的元素。但是該方法沒有利用信道的實時信息,因此,性能提升有限。而文獻[7]則直接利用Δi值來衡量信息位i的可靠性,Δi值越大,則認為該位置越可靠。因此,關(guān)鍵位置集合可以通過對Δi(i∈AA0)進行排序來確定,其中A0表示包含最小的lbL個信息位索引的集合。然而,當(dāng)正確路徑被淘汰時,后續(xù)的譯碼過程中容易出現(xiàn)錯誤傳播現(xiàn)象,這通常會導(dǎo)致該方法的準(zhǔn)確率降低。

文獻[8]提出信息位ui(i∈AA0)的一種譯碼置信度:

(5)

式中:α≥1用于緩解誤碼傳播效應(yīng)。當(dāng)α=1時,一旦SCL譯碼器在位置i1∈A處第一次淘汰了正確路徑,由于譯碼的錯誤傳播效應(yīng),后續(xù)的譯碼均會受到影響,下標(biāo)位置越靠后(即i>i1,i∈A)影響越大。為了減小因錯誤傳播帶來的估計偏差,式(5)中的α可以適當(dāng)增大。進一步地,Ei(α)值更小的信息比特下標(biāo)i更容易成為譯碼錯誤位置。因此,文獻[8]通過定位更小Ei(α)值的信息比特位置來構(gòu)造關(guān)鍵位置集合。實驗結(jié)果表明,與使用Δi的算法相比,使用Ei(α)來構(gòu)造關(guān)鍵位置集合的Post-Processing方法性能更加優(yōu)秀。

盡管現(xiàn)有的Post-Processing方法可以在標(biāo)準(zhǔn)SCL譯碼的基礎(chǔ)上獲得明顯的性能提升,但距離短碼的有限長理論界限仍存在相當(dāng)大的性能差距。因此,如何充分利用第一次SCL譯碼期間生成的路徑度量信息來準(zhǔn)確預(yù)測正確譯碼路徑首次丟失位置仍具挑戰(zhàn)性。

2.2 基于深度學(xué)習(xí)的錯誤位置預(yù)測

在采用SCL-32進行極化碼譯碼的過程中,當(dāng)正確路徑的路徑度量值大于第L條最佳路徑的路徑度量值時,表明在當(dāng)前信息比特索引下,正確的譯碼路徑將被淘汰,從而導(dǎo)致SCL譯碼失敗。

為了探究SCL譯碼路徑首次丟失的錯誤節(jié)點位置的概率分布,本文使用蒙特卡洛仿真的方式來收集SCL譯碼失敗的信息。(128,64+8,A)極化碼在Eb/N0=2 dB條件下, SCL譯碼器譯碼路徑首次淘汰的錯誤位置的概率分布如圖2所示。該實驗對傳輸全零碼字和隨機碼字兩種情況進行模擬,通過對5 000個譯碼錯誤的幀進行數(shù)據(jù)收集,可以總結(jié)出兩個結(jié)論:

(a) 全零碼字

(b) 隨機碼字

① 錯誤位置的總體概率分布幾乎與傳輸?shù)拇a字無關(guān);

② 錯誤位置的分布非常不均勻,大約有一半的信息比特位置更容易出現(xiàn)錯誤。

在64+8=72個信息比特索引中,有30個位置沒有監(jiān)測到錯誤,這意味著實際會發(fā)生錯誤的位置的個數(shù)要小于所有信息比特的數(shù)量。

ie=fθ(Γ)∈A,

(6)

式中:fθ(Γ)表示具有參數(shù)θ的深度神經(jīng)網(wǎng)絡(luò)。實驗中采用了修改版的ResNet-18作為網(wǎng)絡(luò)模型fθ(·),其輸入維度從H×W×C(高×寬×通道)調(diào)整為L×K×1,最終全連接層輸出維度為K。本文使用Adam優(yōu)化器進行模型的訓(xùn)練,完成預(yù)訓(xùn)練的模型fθ(·)可用于離線推理和預(yù)測。

2.3 基于深度學(xué)習(xí)預(yù)測的極化碼路徑移位SCL算法

使用深度學(xué)習(xí)方法預(yù)測譯碼錯誤位置后,可以采用Post-Processing方法進一步提高SCL譯碼性能。本文采用了譯碼路徑移位的方法[6],當(dāng)譯碼失敗時,該方法首先通過深度學(xué)習(xí)模型對路徑被淘汰的錯誤節(jié)點位置進行預(yù)測,并在該位置處重新選擇被丟棄的L條路徑,嘗試找回正確路徑。

如算法1所示,本文提出的基于深度學(xué)習(xí)預(yù)測的極化碼路徑移位SCL算法具體流程如下:當(dāng)首輪的SCL譯碼失敗(即CRC校驗未通過)時,啟動第二輪譯碼嘗試(如圖1(b)所示)。在這個過程中,將前一輪SCL譯碼所返回的路徑度量張量Γ輸入到預(yù)訓(xùn)練模型fθ(·)進行推理,從而得到正確譯碼路徑首次被淘汰的位置的預(yù)測值,并在第二輪SCL譯碼過程中對該位置進行路徑移位。需要注意的是,新一輪SCL譯碼在模型預(yù)測的位置處,之前被丟棄的L條路徑將被重新選擇,以便捕獲正確的譯碼路徑,從而改善SCL譯碼性能。

3 仿真結(jié)果

在仿真實驗中,主要考慮碼長N=128、碼率為1/2的極化碼,信息比特位置的集合A是由遺傳算法[13]搜索得到,極化碼譯碼采用CA-SCL譯碼器,其中8位循環(huán)冗余校驗的生成多項式為x8+x7+x6+x5+x4+x3+1。實驗中假定極化碼字采用二進制相移鍵控(Binary Phase Shift Keying, BPSK)調(diào)制,在傳輸過程中經(jīng)過加性高斯白噪聲(White Gaussian Noise,AWGN)信道。需要注意的是,實驗中涉及到的Post-Processing方法均在SCL-32譯碼器的基礎(chǔ)上實現(xiàn)。

3.1 首次錯誤位置預(yù)測的準(zhǔn)確率

為了收集用于深度學(xué)習(xí)模型fθ(·)訓(xùn)練的數(shù)據(jù),對極化碼的SCL譯碼進行了大量的仿真。當(dāng)SCL譯碼器譯碼失敗時,收集其路徑度量張量以及譯碼路徑首次淘汰的錯誤節(jié)點位置作為有標(biāo)簽數(shù)據(jù)。數(shù)據(jù)收集的信噪比Eb/N0為1.25～3 dB,每間隔0.25 dB取一次的數(shù)值。在每個信噪比點上采集了50 000組有標(biāo)簽數(shù)據(jù)用于構(gòu)建訓(xùn)練數(shù)據(jù)集,以及5 000組有標(biāo)簽數(shù)據(jù)用于測試模型性能。因此,訓(xùn)練數(shù)據(jù)集共有50k×((3-1.25)/0.25+1)=400k個樣本。模型的訓(xùn)練使用學(xué)習(xí)率為1×10-4的Adam優(yōu)化器,并根據(jù)訓(xùn)練進度逐漸降低學(xué)習(xí)率。在訓(xùn)練過程中,數(shù)據(jù)輸入的每個批次大小(batch size)設(shè)為1 024,最大訓(xùn)練迭代次數(shù)設(shè)為500。

圖3展示了已經(jīng)完成預(yù)訓(xùn)練的ResNet-18模型fθ(·)在不同信噪比下的預(yù)測精度。需要注意的是,經(jīng)過訓(xùn)練的模型的預(yù)測準(zhǔn)確性依賴于數(shù)據(jù)集收集的信噪比。如果模型工作的信噪比包含在訓(xùn)練數(shù)據(jù)集中,則其性能明顯優(yōu)于不包含在其中的信噪比。為了更加清晰明了,本文使用DL(w)和DL(w/o)來區(qū)分模型工作的信噪比是否包含在數(shù)據(jù)集收集的信噪比中。如圖3所示,DL(w)可以達到約99%的準(zhǔn)確性,而DL(w/o)的準(zhǔn)確性約為56%。

圖3 不同的Post-Processing方法首輪預(yù)測的準(zhǔn)確率Fig.3 Accuracy of initial prediction in different Post-Processing methods

現(xiàn)有Post-Processing方案的主要不同之處在于關(guān)鍵位置集合的構(gòu)建,關(guān)鍵位置集合的元素即為正確譯碼路徑首次被淘汰的位置,通常使用某種可靠性度量進行確定,例如式(4)或式(5)。根據(jù)圖3可以看出,基于深度學(xué)習(xí)預(yù)測的方法明顯優(yōu)于文獻[7-8]中提出的兩種方法。此外需要注意的是,上述兩種方法在第一輪預(yù)測時的準(zhǔn)確率都低于25%。

3.2 與現(xiàn)有Post-Processing方法的性能對比

圖4對CA-SCL譯碼器采用Δi方法[7]、Ei(α)的方法[8]以及本文提出的方法(Post-Processing-DL)進行了比較。所有Post-Processing方法均在列表大小為SCl-32譯碼器上實施。T表示最大重新解碼嘗試次數(shù)。需要強調(diào)的是,所提出的Post-Processing-DL只進行一輪重新解碼嘗試,即T=1,而文獻[7-8]中的后處理方案通常假定T≥1。

圖4 不同Post-Processing方案譯碼性能對比Fig.4 Comparison of decoding performance in different Post-Processing schemes

由圖4可以看出,當(dāng)訓(xùn)練數(shù)據(jù)集中存在該方法所工作的信噪比時(Post-Processing-DL(w)),該方法的表現(xiàn)顯著優(yōu)于其他方法。對于其他信噪比處,Post-Processing-DL(w/o)的性能與采用Ei(α)(T=5)的方法相近。此外,本文提出的Post-Processing-DL(w)方法的性能甚至比SCL-128的效果更好,并且非常接近該短碼的有限長理論界限[14]。

3.3 深度學(xué)習(xí)方法復(fù)雜度分析

基于深度學(xué)習(xí)輔助的Post-Processing會帶來相當(dāng)大的計算復(fù)雜性。由于深度學(xué)習(xí)模型前向推理過程需要進行大量的乘積累加運算,非深度學(xué)習(xí)方法在計算復(fù)雜性上具有明顯的優(yōu)勢。盡管使用ResNet-18 模型可以準(zhǔn)確預(yù)測錯誤位置,但不適合直接部署在可編程門陣列(Field Programmable Gate Array,FPGA)上。對于FPGA來說,更傾向于使用規(guī)模較小的模型。這個問題在文獻[15-16]中有廣泛討論。文獻[15]提出了SqueezeNet模型,在模型大小上有顯著縮減,但性能損失不大。

為了減少計算負擔(dān)并便于可能在FPGA上部署,實驗中使用相同的數(shù)據(jù)集訓(xùn)練了一個SqueezeNet模型。表1為ResNet-18和SqueezeNet之間的對比。其中,MACCs指的是網(wǎng)絡(luò)推理過程中的乘累加操作的數(shù)量,它以百萬次(M)為單位進行計量,用于衡量網(wǎng)絡(luò)推理的計算復(fù)雜度和性能。從表1中可以看出,通過使用SqueezeNet,模型的大小和復(fù)雜度顯著減小,而預(yù)測準(zhǔn)確率只有輕微的降低。

表1 ResNet-18和SqueezeNet預(yù)測準(zhǔn)確率及復(fù)雜度對比Tab.1 Comparison of prediction accuracy and complexity between ResNet-18 and SqueezeNet

4 結(jié)束語

本文提出了一種基于深度學(xué)習(xí)預(yù)測的極化碼路徑移位SCL算法。相較于已有的Post-Processing方案,所提出的方法采用深度神經(jīng)網(wǎng)絡(luò)來預(yù)測SCL譯碼路徑首次被淘汰的錯誤節(jié)點位置,神經(jīng)網(wǎng)絡(luò)模型采用預(yù)訓(xùn)練的方式,使用時可離線進行推理得出預(yù)測結(jié)果。使用神經(jīng)網(wǎng)絡(luò)來預(yù)測譯碼路徑首次被淘汰的錯誤節(jié)點位置可以實現(xiàn)高效的Post-Processing,基本上只需進行兩輪譯碼即可獲得較大的性能提升,這與其他方案形成鮮明對比。本文提出的算法應(yīng)用在SCL-32時,性能甚至比SCL-128表現(xiàn)更好。

本文所提出的算法雖然性能表現(xiàn)優(yōu)異,但其落地應(yīng)用仍存在一些值得進一步探討的問題,包括開發(fā)適用于FPGA部署的小規(guī)模錯誤節(jié)點預(yù)測神經(jīng)網(wǎng)絡(luò)模型,以及如何提高該模型泛化能力,使得在無訓(xùn)練樣本的信噪比范圍內(nèi)仍然能有效工作。