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

王華華，石 丹，趙昊明

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

0 引 言

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

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

1 極化碼

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

1.1 極化碼編碼

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

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

(1)

(2)

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

GN=BNF?n。

(3)

1.2 極化碼BP譯碼

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

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

(4)

(5)

(6)

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

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

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

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

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

(7)

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

(8)

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

(9)

(10)

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

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

(11)

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

(12)

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

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

Step1 根據(jù)Ac得到所有R1節(jié)點易錯比特集合CS，當執(zhí)行后轉(zhuǎn)Step 2。

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

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

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

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

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

3 仿真與分析

圖4 最大比特翻轉(zhuǎn)迭代次數(shù)圖

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

圖5 極化碼譯碼性能

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

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

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

圖7 處理單元歸一化平均計算次數(shù)

4 結 論

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