盧麗金,李世寶

(中國(guó)石油大學(xué)(華東)計(jì)算機(jī)與通信工程學(xué)院,青島 266580)

Arikan 首次提出極化碼 (Polar Code),且極化碼是人類已知的第一種能夠被嚴(yán)格證明達(dá)到信道容量的信道編碼方法[1].在串行抵消(SC)譯碼算法下,極化碼的復(fù)雜度低、譯碼結(jié)構(gòu)簡(jiǎn)單.然而,SC譯碼算法在碼長(zhǎng)為有限長(zhǎng)的配置下,糾錯(cuò)性能不理想.

為了提高極化碼的性能,引入置信度傳播[2,3]和線性規(guī)劃[4]算法,但,這兩種算法只適用于二進(jìn)制輸入刪除信道 (BEC).隨后,I.Tal 和 A.Vardy 等提出串行抵消列表(SCL)算法[5,6],其性能非常接近最大似然(ML)的糾錯(cuò)性能.為了進(jìn)一步提高極化碼的糾錯(cuò)能力,幾種解碼方法相繼被提出[7–9].其中,文獻(xiàn)[8]通過級(jí)聯(lián)循環(huán)冗余校驗(yàn)(CRC)碼,SCL譯碼能夠獲得比Turbo碼和LDPC 碼更好的性能,并記為 CA-SCL.然而,其復(fù)雜度與列表大小L呈正比關(guān)系.為了降低復(fù)雜度,提出一種自適應(yīng)的串行抵消列表(AD-SCL)譯碼[10],其復(fù)雜度不會(huì)隨著列表大小L的增大而增加.但是,在低信噪比下,AD-SCL會(huì)呈現(xiàn)明顯的高復(fù)雜度現(xiàn)象.AD-SCL總是把L的初始值設(shè)置為1.當(dāng)L=1譯碼失敗時(shí),ADSCL會(huì)將L更新為2L,并返回根節(jié)點(diǎn),重新進(jìn)行譯碼,直至L=Lmax.在信噪比較低的情況下,經(jīng)過基于L=1的譯碼后,往往還需要更新L值.這樣無(wú)疑是增加了復(fù)雜度.值得考慮的是,由小到大的更新L能夠帶來(lái)明顯的低平均譯碼復(fù)雜度,這一優(yōu)勢(shì)值得借鑒.如果L的初始值不固定為1,那么,就能夠解決現(xiàn)存的復(fù)雜度問題.因而,尋找L的最優(yōu)初始值是本文的研究關(guān)鍵.若L的最優(yōu)初始值的大小有l(wèi)種可能,則相當(dāng)于L的最優(yōu)初始值有l(wèi)種類別.在某一實(shí)驗(yàn)配置下,L的最優(yōu)初始值到底屬于哪一種類別,本文需要處理此問題.若在線階段采用傳統(tǒng)的追蹤記錄與概率統(tǒng)計(jì)方式來(lái)分類,需要進(jìn)行大量的數(shù)據(jù)存儲(chǔ)和計(jì)算,將會(huì)大幅度增加復(fù)雜度,且此處理方式不適用于離線操作.BP神經(jīng)網(wǎng)絡(luò)可以用作分類器[11,12]并實(shí)現(xiàn)快速、精確分類.若BP神經(jīng)網(wǎng)絡(luò)的訓(xùn)練和分類都是在線操作,也會(huì)大幅度增加復(fù)雜度,但可以離線訓(xùn)練BP神經(jīng)網(wǎng)絡(luò),在線時(shí)將數(shù)據(jù)輸入到已完成訓(xùn)練的BP神經(jīng)網(wǎng)絡(luò)模型中,輸出一個(gè)類別,且不會(huì)增加復(fù)雜度.因此,本文確定采用BP神經(jīng)網(wǎng)絡(luò)來(lái)尋找L的最優(yōu)初始值.

本文的主要工作是介紹極化編碼、極化譯碼與BP神經(jīng)網(wǎng)絡(luò)的相關(guān)原理,然后離線構(gòu)建并訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)以及在線尋找L的最優(yōu)初始值,最后提出一種基于BP神經(jīng)網(wǎng)絡(luò)的SCL譯碼算法.

1 相關(guān)原理

1.1 極化編碼與極化譯碼

1.1.1 極化編碼

信道極化將一個(gè)二進(jìn)制輸入無(wú)記憶信道的一組獨(dú)立的時(shí)隙看作一組相互獨(dú)立的信道,通過信道分割、信道合并操作引入相關(guān)性.當(dāng)參與信道極化的信道(時(shí)隙)數(shù)足夠多時(shí),所得到的極化信道的信道容量會(huì)出現(xiàn)極化現(xiàn)象,即一部分信道的容量將會(huì)趨于1、其余趨于0.在信道極化的基礎(chǔ)上,只需要在一部分容量趨于1的信道上傳輸信息比特,而在剩下的容量趨于1的信道以及容量趨于0的信道上傳輸對(duì)收發(fā)端都己知的固定比特.

用符號(hào)W:X→Y來(lái)表示一個(gè)B-DMC信道,其中X和Y分別表示該信道的輸入、輸出符號(hào)集合,X={0,1}.信道轉(zhuǎn)移函數(shù)被定義為W(y|x),其中x∈X,y∈Y.那么,對(duì)稱信道容量表示為

其中,β =W(y|x),β0=W(y|0),β1=W(y|1).通過對(duì)信道W的N次占用(即信道W的N個(gè)可用時(shí)隙),能夠得到N個(gè)獨(dú)立的具有相同信道特性的B-DMC信道,然后對(duì)這N個(gè)信道進(jìn)行信道變換,在各個(gè)獨(dú)立的信道之間引入相關(guān)性,將會(huì)得到信道轉(zhuǎn)移概率函數(shù)

1.1.2 極化譯碼

當(dāng)談及SC譯碼時(shí),似然比(LLR)[13]和路徑度量尤為重要.一般地,LLR 的計(jì)算如下

其中,yi是通過AWGN信道獲得的接收信號(hào).LLR的遞歸計(jì)算方式為

以及

與傳統(tǒng)的SC譯碼一樣,SCL譯碼仍然是從譯碼樹的根節(jié)點(diǎn)開始,逐層依次向葉子節(jié)點(diǎn)層進(jìn)行路徑搜索.然而,與傳統(tǒng)的SC譯碼不同的是,SCL譯碼用路徑度量來(lái)估計(jì)每一條路徑的可靠性;此外,SCL的每一層譯碼將會(huì)把L條最有可能的路徑保存下來(lái).那么,的路徑度量的計(jì)算公式為

1.2 BP神經(jīng)網(wǎng)絡(luò)

因強(qiáng)大的學(xué)習(xí)能力,神經(jīng)網(wǎng)絡(luò)吸引著眾多學(xué)者[14].BP神經(jīng)網(wǎng)絡(luò)是神經(jīng)網(wǎng)絡(luò)中的一種,本質(zhì)上是一種前饋神經(jīng)網(wǎng)絡(luò).BP神經(jīng)網(wǎng)絡(luò)主要涉及三部分:準(zhǔn)備樣本、搭建結(jié)構(gòu)及訓(xùn)練網(wǎng)絡(luò).

在準(zhǔn)備樣本階段,主要是整理訓(xùn)練集和測(cè)試集.在搭建結(jié)構(gòu)階段,主要是設(shè)置參數(shù).在訓(xùn)練網(wǎng)絡(luò)階段,基于監(jiān)督學(xué)習(xí),首先計(jì)算輸出層和隱藏層的輸出值;然后計(jì)算輸出層和隱藏層的誤差項(xiàng);在此基礎(chǔ)上,通過設(shè)定一個(gè)學(xué)習(xí)率來(lái)設(shè)置參數(shù)更新的大小,并不斷迭代調(diào)整權(quán)值和偏置項(xiàng),最終完成訓(xùn)練.特別強(qiáng)調(diào)的是,偏置項(xiàng)可以是固定的,也可以設(shè)置成同權(quán)值相關(guān)的.

2 基于BP神經(jīng)網(wǎng)絡(luò)的SCL譯碼算法

由于極化碼能夠達(dá)到信道容量,因此它的譯碼技術(shù)受到了極大關(guān)注.近年來(lái),各種譯碼方法應(yīng)運(yùn)而生,如 SC,SCL,CA-SCL,AD-SCL 等.為了降低低信噪比下的平均譯碼復(fù)雜度,綜合考慮性能及AD-SCL對(duì)L進(jìn)行由小到大更新時(shí)所帶來(lái)的低平均譯碼復(fù)雜度,若L的初始值不固定為1,那么,就能夠解決低信噪比下的復(fù)雜度問題.因而,尋找L的最優(yōu)初始值是本文的研究關(guān)鍵.

假設(shè)令Lmax=32,則L的最優(yōu)初始值有6種情況:1,2,4,8,16,32.當(dāng)尋找L的最優(yōu)初始值時(shí),可以看作是簡(jiǎn)單的分類問題.在某一信噪比和某一似然比下對(duì)應(yīng)著哪個(gè)L值,則相對(duì)應(yīng)的L值即為尋找的L的最優(yōu)初始值.若用普通的計(jì)算來(lái)尋找L的最優(yōu)初始值,需要大量的數(shù)據(jù)存儲(chǔ)和概率統(tǒng)計(jì),從而導(dǎo)致復(fù)雜度呈上升趨勢(shì).而BP神經(jīng)網(wǎng)絡(luò)具有任意復(fù)雜的模式分類能力和優(yōu)良的多維函數(shù)映射能力,可以離線操作和準(zhǔn)確處理分類問題,因此,其技術(shù)適用于尋找L的最優(yōu)初始值.

本文研究主要分2個(gè)階段來(lái)進(jìn)行:離線階段和在線階段,具體的系統(tǒng)框圖如圖1所示.觀察圖1,離線階段主要是構(gòu)建并訓(xùn)練BP神經(jīng)網(wǎng)絡(luò);在線階段首先是尋找L的最優(yōu)初始值,其次是完成譯碼.對(duì)于圖1的整個(gè)系統(tǒng)框圖,首先執(zhí)行離線操作,完成虛框中的各項(xiàng)任務(wù),包括收集數(shù)據(jù)、構(gòu)建BP神經(jīng)網(wǎng)絡(luò)及訓(xùn)練BP神經(jīng)網(wǎng)絡(luò),得到一個(gè)訓(xùn)練好的BP神經(jīng)網(wǎng)絡(luò)模型;然后啟動(dòng)在線操作,從極化編碼開始,將碼字發(fā)送到信道中,得到接收信號(hào),并根據(jù)接收信號(hào)來(lái)計(jì)算似然比,一旦完成似然比的計(jì)算,系統(tǒng)會(huì)激活已完成訓(xùn)練的BP神經(jīng)網(wǎng)絡(luò)模型,將似然比及與該似然比相對(duì)應(yīng)的信噪比輸入到BP神經(jīng)網(wǎng)絡(luò)模型中,得到一個(gè)值,即為L(zhǎng)的最優(yōu)初始值,最后執(zhí)行譯碼操作.

2.1 構(gòu)建與訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)

綜合考慮網(wǎng)絡(luò)訓(xùn)練復(fù)雜度及極化碼譯碼復(fù)雜度,確定在離線階段完成BP神經(jīng)網(wǎng)絡(luò)的構(gòu)建與訓(xùn)練.需要注意的是,此處理方式不會(huì)影響極化碼譯碼復(fù)雜度和性能.

2.1.1 樣本數(shù)據(jù)的準(zhǔn)備及預(yù)處理

采用BP神經(jīng)網(wǎng)絡(luò)方法建模的首要和前提條件是有足夠多典型性好和精度高的樣本.為此,建模的關(guān)鍵是收集并選取樣本數(shù)據(jù);在此基礎(chǔ)上,隨機(jī)選取其中的75%的數(shù)據(jù)作為訓(xùn)練樣本,剩余的25%數(shù)據(jù)作為測(cè)試樣本;最后,通過預(yù)處理將樣本數(shù)據(jù)轉(zhuǎn)換為數(shù)值數(shù)據(jù).本文采用的預(yù)處理手段是歸一化處理,其線性轉(zhuǎn)換算法的形式如下:

其中,smin為輸入向量S的最小值,smax為輸入向量S的最大值,zr是節(jié)點(diǎn)r的輸出值.

2.1.2 神經(jīng)網(wǎng)絡(luò)的訓(xùn)練

基于監(jiān)督學(xué)習(xí),利用反向傳播算法來(lái)訓(xùn)練網(wǎng)絡(luò).假設(shè)每個(gè)訓(xùn)練樣本為(S,g),向量S是訓(xùn)練樣本的特征,g是樣本的目標(biāo)值.

本文取網(wǎng)絡(luò)所有輸出層節(jié)點(diǎn)的誤差平方和作為目標(biāo)函數(shù):

其中,En表示樣本n的 誤差.在此基礎(chǔ)上,運(yùn)用隨機(jī)梯度下降優(yōu)化方法對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化.經(jīng)過優(yōu)化之后,能分別得到輸出層的誤差項(xiàng)、隱藏層的誤差項(xiàng)以及權(quán)重的更新方法.對(duì)于輸出層節(jié)點(diǎn)r,誤差項(xiàng)的計(jì)算為

其中,δr是節(jié)點(diǎn)r的誤差項(xiàng),zr是節(jié)點(diǎn)r的輸出值,gr是樣本對(duì)應(yīng)于節(jié)點(diǎn)r的目標(biāo)值.對(duì)于隱藏層節(jié)點(diǎn),誤差項(xiàng)的計(jì)算為

其中,ar是節(jié)點(diǎn)r的輸出值,ωkr是節(jié)點(diǎn)r到它的下一層節(jié)點(diǎn)k的連接權(quán)重,δk是節(jié)點(diǎn)r的下一層節(jié)點(diǎn)k的誤差項(xiàng).由此,更新每個(gè)連接上的權(quán)重:

其中,ωjr是節(jié)點(diǎn)r到節(jié)點(diǎn)j的權(quán)重,η是一個(gè)學(xué)習(xí)速率常數(shù),δj是節(jié)點(diǎn)j的誤差項(xiàng),sjr是節(jié)點(diǎn)r傳遞給節(jié)點(diǎn)j的輸入.由于偏置項(xiàng)的輸入值永遠(yuǎn)為1,故偏置項(xiàng)的計(jì)算為

根據(jù)上述訓(xùn)練規(guī)則,不斷修正 ωjr與 ωrb,則可完成訓(xùn)練.

2.2 基于BP神經(jīng)網(wǎng)絡(luò)的SCL譯碼算法

為了降低平均譯碼復(fù)雜度,本文提出了一種基于BP神經(jīng)網(wǎng)絡(luò)的SCL(BNN-SCL)譯碼算法.BNNSCL譯碼算法包括兩個(gè)階段:離線構(gòu)建并訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)模型階段與在線譯碼階段.在第2.1節(jié)中,已經(jīng)完成BP神經(jīng)網(wǎng)絡(luò)模型的構(gòu)建與訓(xùn)練,對(duì)應(yīng)地,即已完成圖1系統(tǒng)框圖中虛框的操作.因此,在本節(jié)中主要介紹的是在線階段的譯碼操作,即從圖1的得到接收信號(hào)開始介紹.根據(jù)接收信號(hào)來(lái)計(jì)算似然比,一旦完成似然比的計(jì)算,系統(tǒng)會(huì)激活已完成訓(xùn)練的BP神經(jīng)網(wǎng)絡(luò)模型,將似然比及與該似然比相對(duì)應(yīng)的信噪比輸入到BP神經(jīng)網(wǎng)絡(luò)模型中,得到一個(gè)值,即為L(zhǎng)的最優(yōu)初始值.此時(shí),譯碼端將會(huì)進(jìn)行初始化,將L初始化為L(zhǎng)的最優(yōu)初始值.BNN-SCL算法與現(xiàn)存的譯碼算法不同,L的初始值的大小不固定為1.

為詳細(xì)了解譯碼端進(jìn)行初始化之后的操作,本文給出具體的后續(xù)操作步驟,即本文提出的降低平均譯碼復(fù)雜度的SCL譯碼算法在譯碼端的具體步驟如下:

1)對(duì)L進(jìn)行初始化,將L初始化為L(zhǎng)的最優(yōu)初始值;

2)執(zhí)行SCL譯碼算法,并對(duì)其譯碼候選路徑進(jìn)行CRC校驗(yàn);

3)如果有一條或多于一條的候選路徑通過CRC校驗(yàn),則輸出一條最有可能的路徑,并退出譯碼;否則,跳到 4).

4)將L更新為2L,并判斷更新之后的L是否大于Lmax.若不大于Lmax,則跳回 2);否則,退出譯碼.

為輔助理解,圖2給出了基于BP神經(jīng)網(wǎng)絡(luò)的SCL譯碼算法在譯碼端的流程圖.

圖2 BNN-SCL 譯碼算法在譯碼端的流程圖

3 實(shí)驗(yàn)結(jié)果與分析

本文的仿真實(shí)驗(yàn)包括2個(gè)部分:離線部分和在線部分.現(xiàn)將各部分主要涉及的參數(shù)、配置列出.離線部分,將輸入層、隱藏層及輸出層的節(jié)點(diǎn)數(shù)分別設(shè)置為2、300、6,采用全連接方式來(lái)搭建網(wǎng)絡(luò),并將激活函數(shù)設(shè)置為sigmoid函數(shù),網(wǎng)絡(luò)訓(xùn)練的目標(biāo)誤差設(shè)為0.01,顯示中間結(jié)果的周期設(shè)為50,最大迭代次數(shù)設(shè)為500,學(xué)習(xí)率設(shè)為0.01.在線部分的參數(shù)、配置如下所示.

根據(jù)實(shí)驗(yàn)的數(shù)值結(jié)果來(lái)分析新提出算法的誤比特率(BER)和復(fù)雜度.在本文的仿真實(shí)驗(yàn)中,所涉及的譯碼方案的碼長(zhǎng)和碼率分別配置為N=1024,R=0.5.根據(jù)文獻(xiàn)[15]構(gòu)造極化碼,極化碼級(jí)聯(lián)一個(gè)長(zhǎng)度為16比特的CRC.

圖3給出不同譯碼算法下的BER性能比較,其中列表譯碼的列表大小分別配置為4和32.對(duì)于ADSCL和BNN-SCL譯碼算法,均將最大搜索寬度設(shè)置為L(zhǎng)max=32.通過已完成訓(xùn)練的BP神經(jīng)網(wǎng)絡(luò)來(lái)尋找的L的最優(yōu)初始值被運(yùn)用于仿真實(shí)驗(yàn)中.從圖3中可以看出,CA-SCL、AD-SCL及BNN-SCL的曲線是重疊的.與CA-SCL和AD-SCL類似,經(jīng)過適當(dāng)配置,BNN-SCL也能夠獲得非常接近ML譯碼的性能.

圖4給出不同譯碼算法下的平均復(fù)雜度比較,其中列表譯碼的列表大小為32.對(duì)于AD-SCL和BNNSCL譯碼算法,均將最大搜索寬度設(shè)置為L(zhǎng)max=32.如圖4所示,在高信噪比下,BNN-SCL譯碼的復(fù)雜度非常接近SC譯碼的復(fù)雜度.此外,與AD-SCL譯碼算法相比,在 0～1.25 dB 下,BNN-SCL 能夠顯著降低平均復(fù)雜度,例如,在SNR=0.75時(shí),BNN-SCL 能夠降低約26.1%的復(fù)雜度.

圖3 不同譯碼算法下的BER性能比較

4 結(jié)語(yǔ)

為了降低復(fù)雜度,提出一種基于BP神經(jīng)網(wǎng)絡(luò)的SCL譯碼算法.綜合考慮現(xiàn)存算法的優(yōu)點(diǎn),通過在離線階段完成訓(xùn)練的BP神經(jīng)網(wǎng)絡(luò)來(lái)尋找L的最優(yōu)初始值,以改變L的初始值總是設(shè)置為1的現(xiàn)狀;在此基礎(chǔ)上,設(shè)計(jì)一種改進(jìn)的SCL譯碼算法,最終降低復(fù)雜度.實(shí)驗(yàn)結(jié)果表明,與 AD-SCL 譯碼算法相比,在 0～1.25 dB 下,BNN-SCL能夠顯著降低平均復(fù)雜度且保持譯碼性能不變.