基于遺傳算法改進(jìn)的LDPC碼譯碼器結(jié)構(gòu)

徐光憲，郭若蕾，陶志勇

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

0 引言

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

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

隨著新興的人工智能時(shí)代的來(lái)臨，深度神經(jīng)網(wǎng)絡(luò)(deep neural network，DNN)[5]已經(jīng)成為最流行和最重要的人工智能技術(shù)。最近在信道碼的研究領(lǐng)域，已經(jīng)有不少的工作將深度學(xué)習(xí)的算法和信道編碼聯(lián)合起來(lái)設(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)算法相比，算法時(shí)延大大降低。

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

1 LDPC譯碼原理和遺傳算法

1.1 LDPC碼

LDPC碼是一類前向糾錯(cuò)性能良好的(N,K)線性分組碼，可由相應(yīng)的校驗(yàn)矩陣決定，其中，N代表碼長(zhǎng)，其值和校驗(yàn)矩陣總列數(shù)大小相等，M代表校驗(yàn)序列長(zhǎng)度，其值與校驗(yàn)矩陣總行數(shù)大小相等，K代表信息序列長(zhǎng)度，K=N-M。對(duì)于校驗(yàn)矩陣，每行均與一個(gè)校驗(yàn)方程相互對(duì)應(yīng)，而每列均與碼字c=(c1,c2,…，cN)的一位相互對(duì)應(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)方程，對(duì)應(yīng)H的行，圓形b=(b1,b2,…，b10)為變量節(jié)點(diǎn)，對(duì)應(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)化到對(duì)數(shù)域中進(jìn)行，大量的乘法可以變?yōu)榧臃ㄟ\(yùn)算，從而減少運(yùn)算時(shí)間[14]。本文采用對(duì)數(shù)域的譯碼方法，首先定義對(duì)數(shù)似然比(likelihood rate，LLR)消息如下：

(2)

(3)

(4)

(5)

譯碼算法的具體過(guò)程如下：

步驟1 初始化，計(jì)算信道傳遞給變量節(jié)點(diǎn)的初始概率似然比消息L(Pi),i=1,2,…，n，對(duì)于變量節(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)的消息處理，對(duì)所有的校驗(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)的消息傳遞，對(duì)所有的變量節(jié)點(diǎn)i以及與其相鄰的校驗(yàn)節(jié)點(diǎn)j∈M(i)，在第l次迭代中，計(jì)算校驗(yàn)節(jié)點(diǎn)傳向變量節(jié)點(diǎn)的消息：

(8)

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

(9)

(10)

步驟4 停止

1.3 遺傳算法

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

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

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

2.1 BP-CNN譯碼器

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

BP-CNN譯碼器結(jié)構(gòu)如圖2所示，首先通過(guò)信道編碼器將一組均勻分布的長(zhǎng)度為K的x比特編碼為長(zhǎng)度為N的二進(jìn)制碼字u，然后通過(guò)BPSK調(diào)制將碼字u映射到符號(hào)向量s，其次在接收端y被接收。通常在BP解碼前存在BPSK軟解調(diào)器，以計(jì)算所發(fā)送符號(hào)的對(duì)數(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ī)視覺(jué)為例，從圖像識(shí)別[16-17]、目標(biāo)檢測(cè)[18]等高級(jí)任務(wù)到圖像去噪[19]、圖像超分辨率[20]等低級(jí)任務(wù)，深度卷積神經(jīng)網(wǎng)絡(luò)在各種應(yīng)用中都得到了驗(yàn)證，表明CNN具有很強(qiáng)的局部特征提取能力，且其性能明顯優(yōu)于傳統(tǒng)方法。因此在模型中，將噪聲看作是一個(gè)特征，利用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譯碼算法中。由上述遺傳算法的過(guò)程可知，需要一個(gè)初始的種群，又由于BP譯碼算法是在Tanner圖上進(jìn)行消息傳遞的迭代譯碼算法，因此如圖4所示，可以把所有的變量節(jié)點(diǎn)作為一個(gè)整體，每個(gè)變量節(jié)點(diǎn)作為一個(gè)個(gè)體，變量節(jié)點(diǎn)傳遞給校驗(yàn)節(jié)點(diǎn)的消息作為基因，通過(guò)這種方式，遺傳算法改變了基因空間中的個(gè)體基因，從而導(dǎo)致個(gè)體空間中的相關(guān)個(gè)體得到改進(jìn)，進(jìn)而使整個(gè)種群變得越來(lái)越健康，從而譯碼性能可以得到提升。

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

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

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

Fitness=|L(qi)|

(13)

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

設(shè)定

(14)

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

(15)

可得：

(16)

(17)

(18)

式(16)—式(18)中，m和n分別是每列和每行中1的平均個(gè)數(shù)。選擇參數(shù)用作選擇器，它被用來(lái)決定哪些個(gè)體生存下來(lái)，哪些個(gè)體在下一代中減少或改變。突變參數(shù)用于選擇所選個(gè)體中的哪些基因進(jìn)行突變，并決定突變的方向。這樣，選擇和突變參數(shù)都是衡量個(gè)體及其基因可靠性的指標(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，編程語(yǔ)言為python，框架為Tensorflow。為了評(píng)估GABP-CNN譯碼器的譯碼性能，通過(guò)蒙特卡洛方法進(jìn)行實(shí)驗(yàn)。選取碼長(zhǎng)為576,碼率為3/4的LDPC碼作為訓(xùn)練數(shù)據(jù)，奇偶校驗(yàn)矩陣來(lái)自文獻(xiàn)[16]。該數(shù)據(jù)經(jīng)過(guò)高斯信道傳輸?shù)玫?，信噪比的范圍?～5 dB，選取150個(gè)碼字作為min-batch的大小(每個(gè)SNR分配30個(gè)碼字)。測(cè)試數(shù)據(jù)是經(jīng)過(guò)編碼，BPSK調(diào)制并在高斯信道上傳輸后得到的隨機(jī)二進(jìn)制信息。使用標(biāo)準(zhǔn)正態(tài)分布中的隨機(jī)值初始化神經(jīng)網(wǎng)絡(luò)的權(quán)重。

性能評(píng)價(jià)指標(biāo)為比特錯(cuò)誤率(bit error rate，BER)，BER是在一個(gè)時(shí)間間隔內(nèi)由錯(cuò)誤比特?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)制的并通過(guò)加性高斯白噪聲信息傳輸，設(shè)置碼長(zhǎng)為310，碼率為1/2，迭代次數(shù)為50的BP譯碼器和BP-CNN譯碼器的誤碼性能和信噪比的關(guān)系。從圖中我們可以看出改進(jìn)的譯碼器性能要優(yōu)于BP譯碼器。在誤碼率為10-4時(shí)可以提高解碼性能3.5 dB。

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

3.2.2GABP-CNN譯碼器性能分析

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

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

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

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

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

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

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

一定的改善。

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

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

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

圖8 碼長(zhǎng)對(duì)譯碼性能的影響Fig.8 The effect of code length on decoding performance

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

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

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

由對(duì)比可以看出，相同條件下GABP-CNN譯碼器較傳統(tǒng)BP譯碼器運(yùn)行時(shí)間略多，但是在圖10的仿真過(guò)程過(guò)程中可以看出，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譯碼中來(lái)獲得最優(yōu)的變量節(jié)點(diǎn)以提高其譯碼性能。仿真實(shí)驗(yàn)結(jié)果表明，與標(biāo)準(zhǔn)的BP譯碼器相比，本文提出的GABP-CNN譯碼器可以獲得更好的糾錯(cuò)性能，同時(shí)通過(guò)訓(xùn)練具有損失函數(shù)的深度神經(jīng)網(wǎng)絡(luò)可以獲得較低的誤碼率性能，尤其是在高信噪比環(huán)境下譯碼性能有較大的提升；但是改進(jìn)的譯碼器結(jié)構(gòu)在提高譯碼性能的情況下，系統(tǒng)運(yùn)行時(shí)間上較傳統(tǒng)BP譯碼器略多。因此，如何調(diào)整各種參數(shù)，保證譯碼性能提高的同時(shí)盡量減少系統(tǒng)的運(yùn)行時(shí)間，是下一步重要的研究方向。