一種基于深度學習預測的極化碼路徑移位SCL譯碼算法

田 浩,吳曉富,張索非

(1.南京郵電大學 通信與網絡技術國家工程研究中心,江蘇 南京 210003;2.南京郵電大學 物聯網學院,江蘇 南京 210003)

0 引言

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

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

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

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

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

1.1 極化碼

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

1.2 SCL譯碼

(1)

對應信息位的ui+1判決由對數似然比值決定,即:

(2)

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

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

(3)

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

1.3 SCL譯碼的Post-Processing方法

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

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

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

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

2 基于深度學習的SCL譯碼錯誤位置預測

2.1 SCL譯碼錯誤位置預測技術進展

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

(4)

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

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

(5)

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

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

2.2 基于深度學習的錯誤位置預測

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

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

(a) 全零碼字

(b) 隨機碼字

① 錯誤位置的總體概率分布幾乎與傳輸的碼字無關;

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

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

ie=fθ(Γ)∈A,

(6)

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

2.3 基于深度學習預測的極化碼路徑移位SCL算法

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

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

3 仿真結果

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

3.1 首次錯誤位置預測的準確率

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

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

圖3 不同的Post-Processing方法首輪預測的準確率Fig.3 Accuracy of initial prediction in different Post-Processing methods

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

3.2 與現有Post-Processing方法的性能對比

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

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

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

3.3 深度學習方法復雜度分析

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

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

表1 ResNet-18和SqueezeNet預測準確率及復雜度對比Tab.1 Comparison of prediction accuracy and complexity between ResNet-18 and SqueezeNet

4 結束語

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

本文所提出的算法雖然性能表現優異,但其落地應用仍存在一些值得進一步探討的問題,包括開發適用于FPGA部署的小規模錯誤節點預測神經網絡模型,以及如何提高該模型泛化能力,使得在無訓練樣本的信噪比范圍內仍然能有效工作。