一種低迭代次數的極化碼置信傳播譯碼算法*

王華華，石 丹，趙昊明

(重慶郵電大學 通信與信息工程學院，重慶 400065)

0 引 言

根據香農有噪信道編碼定理，存在可靠傳輸的最大信息速率即信道容量，采用合適的信道編碼方法可以達到信道容量[1]。2009年，Arikan教授[2]提出了一種極化碼編碼方法，并且證明極化碼能達到二進制離散無記憶信道的信道容量。其中的置信傳播(Belief Propagation，BP)譯碼算法，基本原理來源于因子圖與和積算法[3]。與SC(Successive Concellation)算法[4-5]相比，利用軟信息判決方法的BP譯碼算法[6]擁有更低的譯碼時延和更大的吞吐量。該算法本質的并行譯碼性質非常適合使用現場可編程門陣列(Field Programmable Gate Array,FPGA)實現并行譯碼，但原始BP譯碼算法的復雜度較高。為了減少了BP譯碼算法的計算復雜度，工程中常利用等誤差的線性近似函數來代替算法中的雙曲函數[7]。這種使用線性近似的方法同樣也能用在SC算法中，并且僅需乘法和加法操作，非常易于硬件實現。為了解決BP譯碼算法誤幀率(Frame Error Rate,FER)相對較大的問題，有學者提出了基于BP的比特翻轉譯碼算法[8]，采用預先構造關鍵集合的方式，對不能通過CRC校驗的碼塊利用CS集合進行比特翻轉，從而獲得更大的FER增益。在原始BP譯碼的基礎上引入信息糾正的策略同樣也能帶來可觀的FER增益[9]。一種基于G矩陣的早期終止方式[10]，在每一次迭代完成后，都將判決碼字比特和信息碼字比特進行判決，判決結果兩者一致就終止譯碼，從而減少BP譯碼的迭代次數和處理單元(Processing Element，PE)計算次數。近年來，有學者將深度學習引入到BP譯碼中，通過使用交叉熵損失函數與提出的交叉熵多損失函數對深度神經網絡譯碼器進行訓練,生成深度神經網絡譯碼器也能達到降低復雜度和時延，提高譯碼性能的效果。

本文提出一種低迭代次數極化碼BP譯碼算法，該算法能進一步減少BP譯碼過程的迭代次數，減少PE運算次數，從而降低極化碼譯碼器的譯碼時延和功耗。

1 極化碼

極化碼是迄今為止唯一被嚴格證明能達到信道容量的信道編碼方式[2]，通過信道聯合和信道分裂兩個步驟實現信道極化。當碼長N趨于無窮時，一部分信道趨于完全可靠，其對稱信道容量趨近于1；另一部分信道趨于完全噪聲，其對稱信道容量趨近于0。選k個最可靠的信道用于信息比特，另外N-k個信道固定為“0”，從而構成碼率為k/N的(N,k)極化碼。

1.1 極化碼編碼

Arikan基于二進制輸入離散無記憶信道(Binary-discrete Memoryless Channel，B-DMC)提出了極化碼的編碼方案，其步驟如下：

Step1 估計極化信道可靠性。使用巴氏參數Z(W)來衡量信道的可靠性，W為刪除概率ε=0.5的二進制刪除信道(Binary Erasure Channel，BEC)。利用公式計算各個子信道的巴氏參數：

(1)

(2)

式中：GN為生成矩陣，可利用公式(3)得到。

GN=BNF?n。

(3)

1.2 極化碼BP譯碼

圖1 置信傳播譯碼算法處理單元

PE的運算公式采用最小和近似簡化[8](見式(4))，其中最小和近似系數α=0.937 5。

(4)

(5)

(6)

2 低迭代次數極化碼置信傳播譯碼算法

圖2 CSFG與SC中的樹狀結構等價圖

本文提出一種低迭代次數極化碼BP譯碼算法，該算法能加快CSFG早期停止BP譯碼算法中子信道收斂，從而進一步降低譯碼器迭代次數。算法步驟如下：

Step1 根據Ac得到所有R1節點[4]索引關鍵集合(Critical Set，CS)，CS也是易錯比特集合。

Step2 在每次硬判決信息利用公式(4)向右運算的過程中，嘗試著對順序子信道進行凍結。利用公式(7)求得子信道的碼字序列估計值：

(7)

再利用公式(8)得到子信道信源序列估計值：

(8)

當子信道的碼字序列估計值中的比特滿足

(9)

(10)

已凍結的子信道在之后的迭代過程中將不再進行運算，相關PE也不再參與運算。但是在CSFG譯碼的過程中，會遇到含有信息比特的子信道由于對數似然比信息收斂較慢，經過了多次迭代仍然不能將其凍結的情況，這使得迭代次數增加，從而導致譯碼時延和譯碼功耗的增加。

Step3 對未能凍結的單個子信道i(i∈CS)進行flipcnt(i)自加計數，flipcnt(i)表示子信道i的迭代次數，當多次迭代后若flipcnt(i)>flipmax就利用公式(10)對未凍結的子信道進行比特翻轉：

(11)

式中：flipmax表示仿真中達到最少迭代次數時需要設置的最大比特翻轉迭代次數，可由公式(12)得到：

(12)

式中：flip∈{1,2,…,tmax}表示子信道翻轉時所需的迭代次數，當子信道迭代次數達到flip時，進行比特翻轉。公式(12)表示在不同碼長N和不同信噪比RSN情況下，遍歷所有flip使得平均迭代次數最少的flip，其中tercnt表示一次譯碼所需的迭代次數(譯碼錯誤時，當次tercnt為tmax)，Simcnt為仿真次數，設置為105次。可將仿真中得到的flipmax存入一張以N和RSN為索引的最大比特翻轉迭代次數表中，在譯碼過程中，直接通過查表得到flipmax。

低迭代次數極化碼BP譯碼算法偽代碼如下：

Step1 根據Ac得到所有R1節點易錯比特集合CS，當執行后轉Step 2。

Step4 ifi+2n-j>frozcnt(j)，if第k個信道滿足公式(9)子信道凍結條件時，轉Step 5，else轉Step 6 endif endif。/*跳過第k個子信道前面已經凍結的信道，并判斷第k個子信道是否凍結*/

Step6 ifj=n，t++ endif；ift>tmax，結束譯碼，elsifj=n且子信道索引i∈CS時轉Step 7，else轉Step 8 endif。/*R向右是否運算到最后一級，迭代次數t=t+1，當t>tmax結束譯碼，否則不結束譯碼，判斷不能凍結的子信道索引i是否在易錯比特集合CS中*/

Step8 iffrozcnt(j+1)<2·frozcnt(j)，frozcnt(j+1)=2·frozcnt(j)；k=0。當執行后轉Step 3 endif。/*下一級已凍結信道的最大位置索引frozcnt(j+1)至少是frozcnt(j)的兩倍。k清零后進入下一狀態嘗試對子信道凍結*/

圖3為本文提出譯碼算法的部分譯碼流程，圖3(a)～(b)中j狀態包含8個信道，這8個信道是原信道的子信道。嘗試著對j狀態的兩個子信道進行凍結，發現k=2子信道不滿足凍結條件；對k=1子信道凍結后進入j+1狀態，嘗試對未凍結的j+1狀態中k=1子信道進行凍結。從圖3(c)中發現，其不滿足子信道凍結條件，且該子信道中信息比特索引i∈CS，則flipcnt(i)自加1，重新開始下一次迭代運算；當多次迭代后flipcnt(i)>flipmax，則對其進行比特翻轉。從圖3(d)中發現，經過多次迭代，j狀態中k=2子信道滿足凍結條件，至此j狀態的所有子信道凍結完畢，則對整個j狀態進行凍結并得到j狀態信源序列估計值譯碼結果。

圖3 低迭代次數極化碼BP譯碼算法部分譯碼流程圖

3 仿真與分析

圖4 最大比特翻轉迭代次數圖

圖5為極化碼譯碼性能仿真圖，仿真中所有算法迭代公式均采用α=0.937 5的最小和近似系數進行近似運算。本文所提出的低迭代次數極化碼BP譯碼算法在不同信噪比情況下采用圖4中最佳flipmax，在信噪比較低時(小于2 dB)其FER性能與G矩陣早期停止譯碼相似，但仍然存在微小的信噪比增益(0.03～0.06 dB)；在信噪比較大時(大于2 dB)其FER性能與CSFG接近，但FER略高于后者(0.01～0.03 dB)；在3 dB情況下，FER比G矩陣早期停止譯碼低約0.11 dB。圖中基于BP的譯碼算法與基于SC的譯碼算法在性能上存在差距，但FER性能沒有惡化。

圖5 極化碼譯碼性能

圖6為(1 024,512)極化碼平均迭代次數仿真圖，其中本文所提出的低迭代次數極化碼BP譯碼算法采用圖4中不同信噪比所對應最佳的flipmax。仿真結果表明，本文所提出的算法比G矩陣早期停止譯碼和基于連通子因子圖的早期停止BP譯碼平均迭代次數都少，這意味著更快的譯碼速率和更低的譯碼時延，在信噪比為3 dB時比tmax=40的傳統BP譯碼減少了約53%，比G矩陣早期停止譯碼減少了約27%，比基于連通子因子圖的早期停止BP譯碼減少了約14%。

圖6 (1 024,512)極化碼平均迭代次數

圖7為(1 024,512)的極化碼處理單元歸一化平均計算次數。仿真結果表明，隨著信噪比的增加和迭代次數的減少，后3種算法的PE歸一化平均計算次數也相應地減少，其中低迭代次數極化碼BP譯碼算法的PE歸一化平均計算次數最低。在信噪比為3 dB時，其處理單元歸一化平均計算次數比tmax=40的傳統BP譯碼減少了約68%，比G矩陣早期停止譯碼減少了約50%，比基于CSFG的早期停止譯碼算法減少約10%。由此可以看出，本文提出的算法在低功耗譯碼方面也表現出了不錯的性能。

圖7 處理單元歸一化平均計算次數

4 結 論

本文提出了一種低迭代次數極化碼譯碼算法，能有效減少譯碼時延，降低處理單元功率消耗，從而降低譯碼器功率消耗。所提的并行譯碼算法可運用在對功耗要求較高的大規模機器類型通信，以及對時延要求較高的超可靠低延遲通信等5G場景下的極化碼譯碼中。