徐光憲，郭若蕾，陶志勇

(遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院，遼寧 葫蘆島 125105)

0 引言

在過去的60年中，信道編碼作為一種重要的糾錯和信道保護(hù)技術(shù)得到了廣泛的應(yīng)用。通過適當(dāng)?shù)木幋a方法，將精心設(shè)計(jì)的冗余添加到傳輸?shù)南⒅?，信道編碼可以顯著降低信道噪聲帶來的隨機(jī)或突發(fā)錯誤，從而為傳輸質(zhì)量提供強(qiáng)有力的保護(hù)。到目前為止，BCH碼[1]、Turbo碼[2]、LDPC碼[3]、Polar碼[4]等多種信道編碼已被廣泛采用和部署在無線通信、深空通信、固態(tài)驅(qū)動器等眾多通信和存儲系統(tǒng)中。

目前LDPC碼的譯碼方法主要采用的是BP迭代譯碼算法，它采用外信息迭代的方法來譯碼，其計(jì)算復(fù)雜度低，可實(shí)行完全的并行操作，適合硬件實(shí)現(xiàn)，具有高速譯碼的潛力；但是BP譯碼器與最大似然譯碼器相比，得到的譯碼結(jié)果較差，造成譯碼準(zhǔn)確性低，因此人們一直探索更接近最大似然譯碼算法的改進(jìn)譯碼算法。

隨著新興的人工智能時代的來臨，深度神經(jīng)網(wǎng)絡(luò)(deep neural network，DNN)[5]已經(jīng)成為最流行和最重要的人工智能技術(shù)。最近在信道碼的研究領(lǐng)域，已經(jīng)有不少的工作將深度學(xué)習(xí)的算法和信道編碼聯(lián)合起來設(shè)計(jì)信道碼的譯碼算法。文獻(xiàn)[5]中提出，利用加權(quán)BP(belief propagation)譯碼器，在高信噪比下，BP算法的譯碼性能可提高0.9 dB；但該方法的譯碼算法需要大量的乘法運(yùn)算，在一定程度上增加了譯碼的復(fù)雜度。Lougosch和Gross在文獻(xiàn)[5]的基礎(chǔ)上，提出一種改進(jìn)的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)[6]，與文獻(xiàn)[5]相比，主要的區(qū)別是使用偏移最小和算法代替和積算法，從而消除了使用乘法的需要，使參數(shù)量減少，復(fù)雜度降低。文獻(xiàn)[7]提出一種基于深度神經(jīng)網(wǎng)絡(luò)的信道解碼方法，結(jié)果表明，由所有可能的碼字訓(xùn)練的神經(jīng)網(wǎng)絡(luò)解碼器可以獲得最大的后驗(yàn)性能；但是由于二進(jìn)制碼字的指數(shù)型性質(zhì)，其復(fù)雜度很高。為了減少譯碼的復(fù)雜性，文獻(xiàn)[8]提出一種分離子塊的深度學(xué)習(xí)極化碼解碼網(wǎng)絡(luò)，該方法與傳統(tǒng)算法相比，算法時延大大降低。

上述的改進(jìn)譯碼器結(jié)構(gòu)主要考慮用神經(jīng)網(wǎng)絡(luò)(如文獻(xiàn)[9]的MLP、CNN、RNN)等來實(shí)現(xiàn)接近最大似然譯碼，但其譯碼性能仍有待提高。因此針對LDPC碼的BP譯碼器比最大似然譯碼器譯碼準(zhǔn)確性低，提出了基于遺傳算法改進(jìn)的LDPC碼譯碼器結(jié)構(gòu)。

1 LDPC譯碼原理和遺傳算法

1.1 LDPC碼

LDPC碼是一類前向糾錯性能良好的(N,K)線性分組碼，可由相應(yīng)的校驗(yàn)矩陣決定，其中，N代表碼長，其值和校驗(yàn)矩陣總列數(shù)大小相等，M代表校驗(yàn)序列長度，其值與校驗(yàn)矩陣總行數(shù)大小相等，K代表信息序列長度，K=N-M。對于校驗(yàn)矩陣，每行均與一個校驗(yàn)方程相互對應(yīng)，而每列均與碼字c=(c1,c2,…，cN)的一位相互對應(yīng)，且校驗(yàn)矩陣H和碼字c滿足關(guān)系：H·cT=0,如式(1)所示：

除了用校驗(yàn)矩陣表示LDPC碼外，還可用Tanner圖[10]進(jìn)行表示，Tanner圖是校驗(yàn)矩陣的圖形表示，可以直觀的表述信息元與碼字的關(guān)系。圖1是式(1)校驗(yàn)矩陣H的Tanner圖，方形c=(c1,c2,c3,c4,c5)為校驗(yàn)節(jié)點(diǎn)，校驗(yàn)節(jié)點(diǎn)表示校驗(yàn)方程，對應(yīng)H的行，圓形b=(b1,b2,…，b10)為變量節(jié)點(diǎn)，對應(yīng)H的列，ci和bj之間相連的邊表示H中值為1的元素，即第j行第i列元素hi,j=1，Tanner圖形象明了地表示了變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間的關(guān)系。

圖1 校驗(yàn)矩陣的Tanner圖表示Fig.1 Tanner graph representation of the check matrix

1.2 BP譯碼算法

BP譯碼算法可以在概率域或?qū)?shù)域進(jìn)行譯碼[11-13]。概率域譯碼的缺陷是存在大量的乘法，復(fù)雜度較高，將譯碼轉(zhuǎn)化到對數(shù)域中進(jìn)行，大量的乘法可以變?yōu)榧臃ㄟ\(yùn)算，從而減少運(yùn)算時間[14]。本文采用對數(shù)域的譯碼方法，首先定義對數(shù)似然比(likelihood rate，LLR)消息如下：

(2)

(3)

(4)

(5)

譯碼算法的具體過程如下：

步驟1 初始化，計(jì)算信道傳遞給變量節(jié)點(diǎn)的初始概率似然比消息L(Pi),i=1,2,…，n，對于變量節(jié)點(diǎn)i以及與其相鄰的校驗(yàn)節(jié)點(diǎn)j∈M(i)而言，在AWGN信道中得到變量節(jié)點(diǎn)傳遞給校驗(yàn)節(jié)點(diǎn)的初始消息為：

L(0)(qij)=L(Pi)

(6)

步驟2 迭代處理

1) 校驗(yàn)節(jié)點(diǎn)的消息處理，對所有的校驗(yàn)節(jié)點(diǎn)j以及與其相鄰的變量節(jié)點(diǎn)i∈N(j)，在第l次迭代中，計(jì)算變量節(jié)點(diǎn)傳向校驗(yàn)節(jié)點(diǎn)的消息：

(7)

2) 變量節(jié)點(diǎn)的消息傳遞，對所有的變量節(jié)點(diǎn)i以及與其相鄰的校驗(yàn)節(jié)點(diǎn)j∈M(i)，在第l次迭代中，計(jì)算校驗(yàn)節(jié)點(diǎn)傳向變量節(jié)點(diǎn)的消息：

(8)

步驟3 譯碼判決，對所有的變量節(jié)點(diǎn)計(jì)算硬判決消息：

(9)

(10)

步驟4 停止

1.3 遺傳算法

遺傳算法最早由美國密執(zhí)安大學(xué)的Holland教授提出，遵循適者生存、優(yōu)勝劣汰的原則，是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法[15]。遺傳算法以模擬一個人工種群的進(jìn)化開始，通過選擇、交叉和變異等機(jī)制，在每次迭代中保留一組候選個體，經(jīng)過重復(fù)迭代進(jìn)化后，使其適應(yīng)度達(dá)到近似最優(yōu)的狀態(tài)。適應(yīng)度展示了個體生存在環(huán)境中的能力。在每一代中，一些個體由于高適應(yīng)性而存活，一些個體因其較差的存活性能而被淘汰。

一般的遺傳算法都包含三個基本操作：復(fù)制、交叉和變異。復(fù)制是從一個舊種群中選擇生命力強(qiáng)的個體產(chǎn)生新種群的過程。交叉和變異的操作需要改變才能產(chǎn)生后代。交叉是在兩個選定的個體中交換部分基因來產(chǎn)生它們的后代。突變是改變了一個個體的部分基因，從而形成它的后代。這些動作的目的是保持更健康的個體或在種群中產(chǎn)生更健康的個體。經(jīng)過多次進(jìn)化，種群更傾向于適應(yīng)環(huán)境。

2 改進(jìn)的譯碼器

2.1 BP-CNN譯碼器

在實(shí)際通信系統(tǒng)中，由于濾波、過采樣和信道衰落等因素，信道有時在噪聲樣本中表現(xiàn)出相關(guān)性，如果譯碼器沒有設(shè)計(jì)成處理噪聲相關(guān)，那么信道碼在傳輸?shù)倪^程中不具備令人滿意的性能。針對信道噪聲中存在相關(guān)性解碼問題，本文引用CNN來去除傳統(tǒng)BP譯碼器在譯碼中的估計(jì)誤差，從而得到更準(zhǔn)確的噪聲估計(jì)。

BP-CNN譯碼器結(jié)構(gòu)如圖2所示，首先通過信道編碼器將一組均勻分布的長度為K的x比特編碼為長度為N的二進(jìn)制碼字u，然后通過BPSK調(diào)制將碼字u映射到符號向量s，其次在接收端y被接收。通常在BP解碼前存在BPSK軟解調(diào)器，以計(jì)算所發(fā)送符號的對數(shù)似然比：

(11)

(12)

圖2 BP-CNN譯碼器結(jié)構(gòu)Fig.2 The structure of BP-CNN decoder

CNN是一種多層前饋神經(jīng)網(wǎng)絡(luò)，其基本結(jié)構(gòu)包括：輸入層、卷積層、池化層、全連接層和輸出層。以計(jì)算機(jī)視覺為例，從圖像識別[16-17]、目標(biāo)檢測[18]等高級任務(wù)到圖像去噪[19]、圖像超分辨率[20]等低級任務(wù)，深度卷積神經(jīng)網(wǎng)絡(luò)在各種應(yīng)用中都得到了驗(yàn)證，表明CNN具有很強(qiáng)的局部特征提取能力，且其性能明顯優(yōu)于傳統(tǒng)方法。因此在模型中，將噪聲看作是一個特征，利用CNN在解碼中恢復(fù)出真實(shí)的信道噪聲。如圖3所示，將CNN每一層的輸入改為一維向量。詳細(xì)的參數(shù)設(shè)置列于表1。

圖3 CNN結(jié)構(gòu)Fig.3 The structure of CNN

表1 CNN的參數(shù)

2.2 GABP-CNN譯碼器

BP-CNN譯碼器結(jié)構(gòu)比傳統(tǒng)的BP譯碼器結(jié)構(gòu)在譯碼性能上有所提升，但還有進(jìn)步的空間。因此在BP-CNN譯碼器結(jié)構(gòu)的基礎(chǔ)上，提出一種基于遺傳算法改進(jìn)的譯碼器結(jié)構(gòu)，稱為GABP-CNN(genetic algorithm belief propagation-convolutional neural network)譯碼器。

GABP-CNN譯碼器旨在將遺傳算法引入到BP譯碼算法中。由上述遺傳算法的過程可知，需要一個初始的種群，又由于BP譯碼算法是在Tanner圖上進(jìn)行消息傳遞的迭代譯碼算法，因此如圖4所示，可以把所有的變量節(jié)點(diǎn)作為一個整體，每個變量節(jié)點(diǎn)作為一個個體，變量節(jié)點(diǎn)傳遞給校驗(yàn)節(jié)點(diǎn)的消息作為基因，通過這種方式，遺傳算法改變了基因空間中的個體基因，從而導(dǎo)致個體空間中的相關(guān)個體得到改進(jìn)，進(jìn)而使整個種群變得越來越健康，從而譯碼性能可以得到提升。

圖4 圖1的基因表述Fig.4 Gene expression of fig.1

在Tanner圖中，不同的個體的信息不能直接交換，因?yàn)榛蚺c個體的關(guān)系非常密切，所以這里不能使用遺傳算法中的交叉操作。為了充分利用遺傳算法的優(yōu)勢，在每次BP迭代過程中都使用復(fù)制和變異來形成新的一代。

由于在第l次BP迭代結(jié)束時，用于試探譯碼的信息L(qi)表示該基因的可靠性。因此|L(qi)|的值越大，qi就越有可能是1或0。因此，定義它為衡量個體對環(huán)境的生存能力，即適應(yīng)度：

Fitness=|L(qi)|

(13)

由于基因操作直接作用于BP譯碼，因此該算法不能直接給出單個個體與基因的變異概率，需要通過選擇參數(shù)和變異參數(shù)來實(shí)現(xiàn)基因操作，下面給出變異參數(shù)m(λ)和選擇參數(shù)s(λ)的定義。

設(shè)定

(14)

通過模擬一次BP迭代來定義選擇參數(shù)和變異參數(shù)，設(shè)：

(15)

可得：

(16)

(17)

(18)

式(16)—式(18)中，m和n分別是每列和每行中1的平均個數(shù)。選擇參數(shù)用作選擇器，它被用來決定哪些個體生存下來，哪些個體在下一代中減少或改變。突變參數(shù)用于選擇所選個體中的哪些基因進(jìn)行突變，并決定突變的方向。這樣，選擇和突變參數(shù)都是衡量個體及其基因可靠性的指標(biāo)。

3 實(shí)驗(yàn)驗(yàn)證

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

實(shí)驗(yàn)環(huán)境使用Ubuntu64位操作系統(tǒng)，內(nèi)存為32 GB，CPU為Intel Core i7-6850k，GPU為GeForce GTX Titan-X，編程語言為python，框架為Tensorflow。為了評估GABP-CNN譯碼器的譯碼性能，通過蒙特卡洛方法進(jìn)行實(shí)驗(yàn)。選取碼長為576,碼率為3/4的LDPC碼作為訓(xùn)練數(shù)據(jù)，奇偶校驗(yàn)矩陣來自文獻(xiàn)[16]。該數(shù)據(jù)經(jīng)過高斯信道傳輸?shù)玫?，信噪比的范圍?～5 dB，選取150個碼字作為min-batch的大小(每個SNR分配30個碼字)。測試數(shù)據(jù)是經(jīng)過編碼，BPSK調(diào)制并在高斯信道上傳輸后得到的隨機(jī)二進(jìn)制信息。使用標(biāo)準(zhǔn)正態(tài)分布中的隨機(jī)值初始化神經(jīng)網(wǎng)絡(luò)的權(quán)重。

性能評價指標(biāo)為比特錯誤率(bit error rate，BER)，BER是在一個時間間隔內(nèi)由錯誤比特?cái)?shù)與傳送總比特?cái)?shù)的比值，定義為：

(19)

式(19)中，A是待譯碼的碼字的數(shù)量，acc是能夠正確譯碼的碼字?jǐn)?shù)量。

3.2 實(shí)驗(yàn)分析

本文提出的GABP-CNN譯碼器是在BP-CNN譯碼器的基礎(chǔ)上進(jìn)行改進(jìn)的，因此先證明BP-CNN譯碼器比傳統(tǒng)BP譯碼器的有效性，再進(jìn)而證明GABP-CNN譯碼器在其基礎(chǔ)上譯碼性能的提升。

3.2.1BP-CNN譯碼器性能分析

圖5給出了使用BPSK調(diào)制的并通過加性高斯白噪聲信息傳輸，設(shè)置碼長為310，碼率為1/2，迭代次數(shù)為50的BP譯碼器和BP-CNN譯碼器的誤碼性能和信噪比的關(guān)系。從圖中我們可以看出改進(jìn)的譯碼器性能要優(yōu)于BP譯碼器。在誤碼率為10-4時可以提高解碼性能3.5 dB。

除了糾錯性能之外，BP-CNN譯碼器還減少了平均迭代次數(shù)，簡化了解碼器的復(fù)雜性，如圖6所示。我們的性能分析和與相關(guān)工作的比較表明，盡管BP-CNN譯碼器中CNN的訓(xùn)練需要大量的數(shù)據(jù)，一定程度上增加了譯碼器的復(fù)雜性，但是可以通過強(qiáng)大的計(jì)算設(shè)備來滿足，在BP和BP-CNN譯碼器整體復(fù)雜度相當(dāng)?shù)那闆r下，BP-CNN譯碼器的10次迭代與BP譯碼器的50次迭代的效果幾乎一樣，所以進(jìn)一步證明了BP-CNN譯碼器能簡化復(fù)雜性，提高譯碼性能。

3.2.2GABP-CNN譯碼器性能分析

首先對碼長為310，碼率分別為1/2，2/3的LDPC碼進(jìn)行譯碼仿真，編碼后的信息采用BPSK，調(diào)制后的信息進(jìn)入AWGN信道，最大迭代次數(shù)設(shè)為20次，得到的仿真結(jié)果如圖7所示。

圖5 兩種譯碼器的譯碼性能對比 Fig.5 The comparison of decoding performance of the two decoders

圖6 兩種譯碼器的復(fù)雜度對比Fig.6 The comparison of the complexity of the two decoders

圖7 碼率對譯碼性能的影響Fig.7 The effect of code rate on decoding performance

圖7給出了BP-CNN譯碼器和GABP-CNN譯碼器的誤碼率曲線的仿真結(jié)果。通過曲線可以看出，當(dāng)誤碼率達(dá)到10-3時，在碼率為1/2和2/3下，GABP-CNN相對于BP-CNN的性能增益分別約為0.03 dB和0.02 dB。在低信噪比下，兩種譯碼器的性能相近，但在高信噪比下，GABP-CNN譯碼器相比于BP-CNN譯碼器表現(xiàn)出來更好的性能。

接著給出碼率為1/2，迭代次數(shù)為20，碼長為310和630的LDPC碼在不同信道條件下的譯碼糾錯性能，得到不同碼長下的誤碼率仿真結(jié)果，如圖8所示。

由圖8可以看出，GABP-CNN譯碼器性能優(yōu)于BP-CNN譯碼器。當(dāng)誤碼率為10-4時，在310和630比特碼長下，GABP-CNN相對于BP-CNN的誤碼率性能增益分別約為0.002 dB和0.000 3 dB，而且隨著誤碼率的下降性能差異會更明顯。所以加入遺傳算法改進(jìn)的譯碼器在較高信噪比下對誤碼率有

一定的改善。

然后給出碼長為310，碼率為1/2，迭代次數(shù)分別為5，10和20次的LDPC碼在不同信道條件下的譯碼糾錯性能，得到不同迭代次數(shù)下誤比特率與信道中信噪比的關(guān)系圖，如圖9所示。

從圖9中可以看出，迭代次數(shù)越大，誤碼率越低，譯碼性能也越好。相較于BP算法和BP-CNN算法，改進(jìn)后的P-BP-CNN算法隨著信噪比的增加可帶來一定的性能增益。在0～1 dB的范圍內(nèi)，即小信噪比范圍，提出的算法對誤碼率的改進(jìn)不大，但隨著信噪比的增大，LDPC碼的誤碼率得到了明顯的改善，證明所提出的結(jié)構(gòu)對提升譯碼性能是有貢獻(xiàn)的。

最后給出傳統(tǒng)BP譯碼器、BP-CNN譯碼器與GABP-CNN譯碼器在碼長為310，碼率為1/2，迭代次數(shù)為20的情況下系統(tǒng)誤碼率以及運(yùn)行時間如圖10和表2所示。

圖8 碼長對譯碼性能的影響Fig.8 The effect of code length on decoding performance

圖9 迭代次數(shù)對譯碼性能的影響Fig.9 The effect of the number of iterations on decoding performance

圖10 不同譯碼器的譯碼性能對比Fig.10 The comparison of decoding performance of different decoders

表2 不同譯碼器的運(yùn)行時間

由對比可以看出，相同條件下GABP-CNN譯碼器較傳統(tǒng)BP譯碼器運(yùn)行時間略多，但是在圖10的仿真過程過程中可以看出，GABP-CNN譯碼器的譯碼性能最優(yōu)。

4 結(jié)論

本文在傳統(tǒng)BP譯碼器的基礎(chǔ)上，提出了基于遺傳算法改進(jìn)的譯碼器結(jié)構(gòu)，該結(jié)構(gòu)是在引入卷積神經(jīng)網(wǎng)絡(luò)去除BP譯碼器的噪聲估計(jì)的基礎(chǔ)上，將遺傳算法應(yīng)用到BP譯碼中來獲得最優(yōu)的變量節(jié)點(diǎn)以提高其譯碼性能。仿真實(shí)驗(yàn)結(jié)果表明，與標(biāo)準(zhǔn)的BP譯碼器相比，本文提出的GABP-CNN譯碼器可以獲得更好的糾錯性能，同時通過訓(xùn)練具有損失函數(shù)的深度神經(jīng)網(wǎng)絡(luò)可以獲得較低的誤碼率性能，尤其是在高信噪比環(huán)境下譯碼性能有較大的提升；但是改進(jìn)的譯碼器結(jié)構(gòu)在提高譯碼性能的情況下，系統(tǒng)運(yùn)行時間上較傳統(tǒng)BP譯碼器略多。因此，如何調(diào)整各種參數(shù)，保證譯碼性能提高的同時盡量減少系統(tǒng)的運(yùn)行時間，是下一步重要的研究方向。