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

王華華，石 丹，趙昊明

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

0 引 言

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

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

1 極化碼

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

1.1 極化碼編碼

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

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

(1)

(2)

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

GN=BNF?n。

(3)

1.2 極化碼BP譯碼

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

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

(4)

(5)

(6)

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

圖2 CSFG與SC中的樹狀結(jié)構(gòu)等價(jià)圖

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

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

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

(7)

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

(8)

當(dāng)子信道的碼字序列估計(jì)值中的比特滿足

(9)

(10)

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

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

(11)

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

(12)

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

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

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

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

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

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

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

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

3 仿真與分析

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

圖5為極化碼譯碼性能仿真圖，仿真中所有算法迭代公式均采用α=0.937 5的最小和近似系數(shù)進(jìn)行近似運(yùn)算。本文所提出的低迭代次數(shù)極化碼BP譯碼算法在不同信噪比情況下采用圖4中最佳flipmax，在信噪比較低時(shí)(小于2 dB)其FER性能與G矩陣早期停止譯碼相似，但仍然存在微小的信噪比增益(0.03～0.06 dB)；在信噪比較大時(shí)(大于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中不同信噪比所對(duì)應(yīng)最佳的flipmax。仿真結(jié)果表明，本文所提出的算法比G矩陣早期停止譯碼和基于連通子因子圖的早期停止BP譯碼平均迭代次數(shù)都少，這意味著更快的譯碼速率和更低的譯碼時(shí)延，在信噪比為3 dB時(shí)比tmax=40的傳統(tǒng)BP譯碼減少了約53%，比G矩陣早期停止譯碼減少了約27%，比基于連通子因子圖的早期停止BP譯碼減少了約14%。

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

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

圖7 處理單元?dú)w一化平均計(jì)算次數(shù)

4 結(jié) 論

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