周湘貞

(鄭州升達(dá)經(jīng)貿(mào)管理學(xué)院 信息工程系, 鄭州 451191)

1 背景

時(shí)至今日，糾錯(cuò)碼技術(shù)已成為實(shí)現(xiàn)及時(shí)可靠通信的不可或缺的手段和方法。然而，糾錯(cuò)碼的軟判決技術(shù)卻一直存在適用范圍小、計(jì)算復(fù)雜度高等問(wèn)題，現(xiàn)有技術(shù)條件下難以在合理有限的時(shí)間內(nèi)得到較好的解決[1-2]。另外，一般的譯碼算法為串行處理，僅適合于低、中速的數(shù)字通信系統(tǒng)[3-4]。目前，數(shù)字通信和信息存儲(chǔ)系統(tǒng)正朝著高速度、高帶寬、高可靠性方向發(fā)展，這就對(duì)糾錯(cuò)碼技術(shù)提出了新的要求，譯碼問(wèn)題已成為糾錯(cuò)碼發(fā)展的一大瓶頸。

Berlekamp等[3]證明了一般糾錯(cuò)碼的譯碼問(wèn)題是一類NP( Non-deterministic Polynomial)復(fù)雜問(wèn)題，可等價(jià)為組合優(yōu)化問(wèn)題處理。智能算法(intelligent algorithm,IA)作為一種通過(guò)模仿自然世界的內(nèi)在自適應(yīng)優(yōu)化機(jī)制獲取解決復(fù)雜組合優(yōu)化問(wèn)題的信息的處理技術(shù)被引入到糾錯(cuò)碼技術(shù)中[4-6]。利用智能算法的自適應(yīng)優(yōu)化以及快速并行處理等機(jī)理解決糾錯(cuò)碼譯碼技術(shù)所面臨的困難具有重要的理論意義與實(shí)用價(jià)值。

本文在傳統(tǒng)硬判決的基礎(chǔ)上提出一種基于遺傳算法和神經(jīng)網(wǎng)絡(luò)智能算法的糾錯(cuò)譯碼方案，即遺傳神經(jīng)網(wǎng)絡(luò)譯碼(GND)方案。GND方案繼承了遺傳算法的并行、自優(yōu)化特性及神經(jīng)網(wǎng)絡(luò)的模式分類能力，在保證譯碼質(zhì)量的基礎(chǔ)上降低了傳統(tǒng)軟判決譯碼的復(fù)雜性，提高了譯碼速度。

2 遺傳算法(GA)和神經(jīng)網(wǎng)絡(luò)(NN)

2.1 遺傳算法

遺傳算法(GA)是J.Hollnad受生物進(jìn)化論啟發(fā)而提出的一種基于“適者生存”自然法則的高度并行、隨機(jī)和自適應(yīng)的優(yōu)化算法。它衍生于生物遺傳進(jìn)化機(jī)制,模擬基因重組與進(jìn)化的自然過(guò)程，進(jìn)行類似于自然選擇、配對(duì)交叉和變異的運(yùn)算，經(jīng)過(guò)多次重復(fù)迭代(即世代遺傳)得到最終優(yōu)化結(jié)果[7-9]。遺傳算法主要有以下特點(diǎn)：

1) 繼承自然進(jìn)化過(guò)程所固有的并行性，即同時(shí)有大量物種彼此獨(dú)立地通過(guò)自然選擇、交配和基因突變向前進(jìn)化。這一特性使其可同時(shí)對(duì)搜索空間的多個(gè)解進(jìn)行評(píng)估，極大地提升了解決問(wèn)題的速度；

2) 采用概率變遷規(guī)則來(lái)指導(dǎo)搜索，使個(gè)體不斷地改變，群體得以朝著最優(yōu)方向演化，具有啟發(fā)式搜索能力，解決問(wèn)題質(zhì)量高；

3) 采用自然進(jìn)化機(jī)制來(lái)表現(xiàn)復(fù)雜現(xiàn)象，能夠快速可靠地求解非常困難的問(wèn)題。

遺傳算法解決優(yōu)化問(wèn)題時(shí)，需要依據(jù)具體問(wèn)題設(shè)定GA參數(shù)，這些參數(shù)包括種群中個(gè)體的數(shù)量、交叉概率、變異概率、遺傳代數(shù)。

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

神經(jīng)網(wǎng)絡(luò)擅長(zhǎng)從復(fù)雜或不精確的數(shù)據(jù)中提取有意義的信息，可用來(lái)提取復(fù)雜的模式和檢測(cè)人類或其他計(jì)算機(jī)技術(shù)難以發(fā)現(xiàn)的趨勢(shì)。基于一定的學(xué)習(xí)算法，神經(jīng)網(wǎng)絡(luò)在學(xué)習(xí)過(guò)程中根據(jù)環(huán)境產(chǎn)生的數(shù)據(jù)對(duì)調(diào)整網(wǎng)絡(luò)的狀態(tài)。學(xué)習(xí)算法描述了神經(jīng)網(wǎng)絡(luò)如何根據(jù)訓(xùn)練數(shù)據(jù)對(duì)網(wǎng)絡(luò)的狀態(tài)進(jìn)行調(diào)整[10]。當(dāng)給定輸入時(shí)，受過(guò)訓(xùn)練的神經(jīng)網(wǎng)絡(luò)可以提供與目標(biāo)結(jié)果非常相似的預(yù)測(cè)。神經(jīng)網(wǎng)絡(luò)的特點(diǎn)包括[11-12]：

1) 自適應(yīng)學(xué)習(xí)：可以從給定的初始訓(xùn)練或經(jīng)驗(yàn)數(shù)據(jù)中學(xué)習(xí)如何完成任務(wù)。

2) 自組織：神經(jīng)網(wǎng)絡(luò)可以自行構(gòu)建自己的結(jié)構(gòu)或在學(xué)習(xí)過(guò)程中自行展示接收的信息。

3) 實(shí)時(shí)操作：人工神經(jīng)網(wǎng)絡(luò)計(jì)算可以并行運(yùn)行，特殊的硬件設(shè)備在設(shè)計(jì)和制作時(shí)都可以利用這種能力。

4) 容錯(cuò)性：一個(gè)網(wǎng)絡(luò)的局部破壞會(huì)導(dǎo)致相應(yīng)的性能退化。然而，神經(jīng)網(wǎng)絡(luò)即使主要部分受到損傷，網(wǎng)絡(luò)的一些能力仍可使用。

3 GND譯碼方案

本文對(duì)遺傳算法與神經(jīng)網(wǎng)絡(luò)算法進(jìn)行了融合，提出一種基于遺傳算法和神經(jīng)網(wǎng)絡(luò)智能算法的糾錯(cuò)譯碼方案，即遺傳神經(jīng)網(wǎng)絡(luò)譯碼(GND)方案。在GND譯碼方案中，將神經(jīng)網(wǎng)絡(luò)作為對(duì)遺傳算法優(yōu)化性能的補(bǔ)充加入遺傳算法的個(gè)體適應(yīng)度評(píng)估機(jī)制中，如圖1所示。以分組碼(n,k)為例，在適應(yīng)度評(píng)估機(jī)制中，神經(jīng)網(wǎng)絡(luò)充當(dāng)一個(gè)模式分類器的角色，它根據(jù)遺傳算法個(gè)體所代表的碼字與最近可用碼字之間的漢明距離對(duì)遺傳個(gè)體進(jìn)行分類，與最近碼字之間漢明距離相同的遺傳個(gè)體被分為一類。這一操作利用譯碼標(biāo)準(zhǔn)陣中碼字校正子與陪集首之間的一一對(duì)應(yīng)關(guān)系，通過(guò)神經(jīng)網(wǎng)絡(luò)將輸入的遺傳個(gè)體的校正子序列映射為與之對(duì)應(yīng)的陪集首的重量(陪集首的重量)來(lái)實(shí)現(xiàn)。神經(jīng)網(wǎng)絡(luò)得到的結(jié)果作為補(bǔ)償因子加入遺傳算法的評(píng)價(jià)機(jī)制中，以進(jìn)一步加強(qiáng)遺傳算法的優(yōu)化性能。

圖1 GND算法流程

3.1 譯碼方案模型

以分組碼(n,k)為例， GND譯碼的實(shí)現(xiàn)過(guò)程如下：

1) 訓(xùn)練神經(jīng)網(wǎng)絡(luò)：GND譯碼中需要用到的神經(jīng)網(wǎng)絡(luò)如圖2所示，其作為一個(gè)分類器由3層網(wǎng)絡(luò)構(gòu)成，即輸入層、隱含層和輸出層。輸入層由n-k個(gè)神經(jīng)元組成，輸出層有1個(gè)神經(jīng)元，隱含層包括(2/3)(n-k+t+1)個(gè)神經(jīng)元，其中k為碼的信息位個(gè)數(shù)，t為該碼的最大糾錯(cuò)個(gè)數(shù)。這一操作按照以下步驟實(shí)現(xiàn)：將校正子序列作為輸入訓(xùn)練模式，與其對(duì)應(yīng)的錯(cuò)誤模式的重量w作為目標(biāo)輸出，使之輸入一個(gè)校正子便能得到對(duì)應(yīng)的錯(cuò)誤圖樣的重量w(w=1,2,3…,n),校正子S可以根據(jù)遺傳算法個(gè)體所代表的碼字R和碼的校驗(yàn)矩陣H得到，即：

S=R·H′

(1)

根據(jù)最小距離譯碼準(zhǔn)則和標(biāo)準(zhǔn)陣?yán)碚摽芍捍a字與最近可用碼字之間的漢明距離越大，則標(biāo)準(zhǔn)陣中其所對(duì)應(yīng)的的陪首集重量越大，即可能含有的錯(cuò)誤比特?cái)?shù)越多，將其對(duì)應(yīng)校正子作為輸入的神經(jīng)網(wǎng)絡(luò)的輸出值也越大。

圖2 神經(jīng)網(wǎng)絡(luò)分類器

2) 使用遺傳算法優(yōu)化得到一個(gè)與傳輸序列更似然的碼字：

步驟1種群初始化：生成2t個(gè)n位的二進(jìn)制向量作為初始種群。

對(duì)于種群的第1個(gè)個(gè)體成員P1：將匹配濾波器輸出的硬判決序列R(r1,r2,…,rn)設(shè)置為種群的第1個(gè)個(gè)體。

(2)

其中：Q(q1,q2,…,qn)為接收到的未經(jīng)匹配濾波器硬判決量化的實(shí)數(shù)序列。

對(duì)于種群的其他2t-1個(gè)個(gè)體成員Pi:將由隨機(jī)產(chǎn)生的均勻二進(jìn)制修正序列T(t1,t2,…,t2t-1)和硬判決序列R相加得到，即

Pi=mod(R+T,2), 2≤i≤2t

T=rand[0,1]

(3)

步驟2個(gè)體適應(yīng)度評(píng)價(jià)：

對(duì)遺傳算法個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)

(4)

其中：λ(P,Q)為相關(guān)函數(shù)，用來(lái)計(jì)算遺傳體Pi和接收實(shí)數(shù)序列Q之間的歐氏距離。個(gè)體與接收的實(shí)屬序列越相似，則λ的值越大。

(5)

Weight(Error class(Indiv.)) 為神經(jīng)網(wǎng)絡(luò)的輸出結(jié)果，它作為一個(gè)補(bǔ)償因子，代表遺傳個(gè)體所對(duì)應(yīng)碼字的最可能的錯(cuò)誤圖樣的重量。遺傳個(gè)體所含錯(cuò)誤比特?cái)?shù)越少，Weight(Error class(Indiv.))的值就越小，最終fitness的值就會(huì)越大。要得到penalty，需要先利用式(1)計(jì)算待評(píng)估遺傳個(gè)體的校正子序列S，再將S輸入神經(jīng)網(wǎng)絡(luò)。

步驟3自然選擇：基于輪盤賭選擇法或其他選擇方法從初始種群中選擇優(yōu)秀的個(gè)體參與遺傳，個(gè)體被選擇參與遺傳的概率由其適應(yīng)度決定。適應(yīng)度越高，被選中的概率越大。一般地，第i個(gè)個(gè)體被選中的概率為

(6)

步驟4配對(duì)交叉：被選中的個(gè)體將隨機(jī)進(jìn)行配對(duì)，通過(guò)將自身部分元素(碼元)與對(duì)方交叉產(chǎn)生新個(gè)體。配對(duì)交叉的方法有多種，最常見的有單點(diǎn)交叉和多點(diǎn)交叉。本研究中選擇單點(diǎn)交叉，交叉概率設(shè)為0.9。

步驟5遺傳變異：針對(duì)隨機(jī)選擇過(guò)程d中產(chǎn)生的新個(gè)體，對(duì)其進(jìn)行變異處理(將個(gè)體的某位元素(碼元)翻轉(zhuǎn)，即由0→1或1→0)，本研究中的變異概率設(shè)置為0.025。

步驟6遺傳終止：遺傳將在遺傳世代數(shù)達(dá)到預(yù)設(shè)值時(shí)終止，此時(shí)種群中適應(yīng)度最高的個(gè)體將被輸出；若未達(dá)到預(yù)設(shè)值則跳轉(zhuǎn)步驟1繼續(xù)遺傳過(guò)程，本研究中遺傳世代數(shù)設(shè)置為20。

3) 將遺傳算法輸出的最佳序列輸入硬判決糾錯(cuò)譯碼器進(jìn)行譯碼，得到最終譯碼結(jié)果。

3.2 GND譯碼性能分析

3.2.1算法復(fù)雜度分析

GND算法的計(jì)算開銷主要包括遺傳算法模塊的優(yōu)化、神經(jīng)網(wǎng)絡(luò)的分類和硬判決譯碼器的糾錯(cuò)，其中遺傳算法模塊所占比例最大。就神經(jīng)網(wǎng)絡(luò)部分而言，只要網(wǎng)絡(luò)被訓(xùn)練好，在其使用模式時(shí)只需簡(jiǎn)單的加乘法和權(quán)累加運(yùn)算，計(jì)算開銷非常小。本研究按照整個(gè)譯碼過(guò)程中所需的加法和乘法計(jì)算量對(duì)譯碼算法的復(fù)雜度進(jìn)行評(píng)估。以線性分組碼BCH(n，k，dh，t)為例，其中dh為分組碼的最小漢明距離，t為分組碼的最大糾錯(cuò)個(gè)數(shù)。

1) 遺傳算法優(yōu)化模塊：遺傳算法需要進(jìn)行g(shù)en代遺傳，每代中有2(dh/2-1)個(gè)個(gè)體需要被處理，每次處理將執(zhí)行(n-1)次加法和n次乘法，最終需要執(zhí)行2(dh/2-1)·gen·(n-1)次加法操作和2(dh/2-1)·gen·n次乘法操作；

2) 神經(jīng)網(wǎng)絡(luò)分類模塊:本研究中的神經(jīng)網(wǎng)絡(luò)分類器共有(2/3)(n-k+t+1)個(gè)隱單元。一個(gè)已經(jīng)訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)在使用模式時(shí)，每個(gè)隱單元需執(zhí)行(n-k-1)次加法和(n-k)次乘法，輸出單元執(zhí)行(2/3)(n-k+t+1)-1次加法和(2/3)(n-k+t+1)次乘法。因此，對(duì)于一個(gè)輸入，在整個(gè)譯碼過(guò)程中，神經(jīng)網(wǎng)模塊需進(jìn)行{(2/3)(n-k+t+1)+n-k-2}·gen·2t次加法運(yùn)算以及{(2/3)(n-k+t+1)+n-k}·gen·2t次乘法運(yùn)算。

3) 硬判決譯碼器模塊：以BCH的BM譯碼算法為例，其每次硬判決譯碼需要執(zhí)行(2nt+2t2-t)次加法運(yùn)算和(2nt+2t2)次乘法運(yùn)算。

若將硬判決量化視為加法運(yùn)算，則GND算法與Chase2、GPD算法復(fù)雜度對(duì)比情況見表1。以BCH(31,16，7,3)碼為例，采用GND譯碼的復(fù)雜度見表2。表2中還給出了傳統(tǒng)軟判決譯碼Chase2和文獻(xiàn)[13]的一種基于遺傳算法的GPD譯碼方案的復(fù)雜度對(duì)比。

分析表2數(shù)據(jù)可知：3種譯碼中GND譯碼的計(jì)算開銷量最小，其次是GPD譯碼，軟判決Chase2的計(jì)算量最大。這是由于在譯碼過(guò)程中，Chase2和GPD算法利用額外的軟信息產(chǎn)生候選序列，而GND直接對(duì)解調(diào)器的濾波器輸出進(jìn)行處理，不借用軟信息生成候選空間。由此可看出：GND算法是一種復(fù)雜度相對(duì)較低，可操作性強(qiáng)的譯碼方法。

表1 GND算法與Chase2、GPD算法復(fù)雜度對(duì)比情況

表2 BCH(31,16)的GND算法與Chase2、GPD算法復(fù)雜度對(duì)比情況

3.2.2誤比特性能分析

本文在仿真模擬時(shí)使用BCH(31,16)作為譯碼對(duì)象，參數(shù)設(shè)置見表3。為進(jìn)行性能對(duì)比,同時(shí)模擬了MLD最佳譯碼算法。文獻(xiàn)[13]中的GPD譯碼、Chase2軟判決譯碼以及BM硬判決譯碼的誤比特性能見圖3。圖3中，R代表接收調(diào)制器的匹配濾波器輸出,BER表示誤碼率，SNR(dB)表示信噪比。

表3 默認(rèn)參數(shù)值

分析圖3可知：各種譯碼算法通過(guò)對(duì)解調(diào)器的匹配濾波器輸出結(jié)果R采取不同的處理方法都能不同程度地降低接收序列的誤碼率。例如，圖3中誤碼率為10-4時(shí)，BM硬判決譯碼在匹配濾波器的輸出結(jié)果基礎(chǔ)上可多獲得約1.5 dB的增益，GND算法約為2 dB， Chase2算法約為2.4 dB，GPD譯碼約為2.6 dB，MLD譯碼約為3.8 dB。由此可知：GND譯碼擁有較好的糾錯(cuò)性能，接近傳統(tǒng)的軟判決譯碼。GND譯碼雖然不如Chase2和文獻(xiàn)[11]中的GPD算法獲得的增益大，但如前文分析，由于不需要利用信道統(tǒng)計(jì)概率軟信息生成搜索空間，GND算法復(fù)雜度相對(duì)Chase2軟譯碼和GPD譯碼降低很多，其實(shí)用性更強(qiáng)。綜合來(lái)看，GND算法在譯碼復(fù)雜度和譯碼糾錯(cuò)性之間取得了較好的折衷，是一種優(yōu)異的新型譯碼方法。

圖3 GND譯碼算法性能仿真結(jié)果

4 結(jié)束語(yǔ)

本文提出了一種基于遺傳算法和神經(jīng)網(wǎng)絡(luò)的糾錯(cuò)碼硬判決譯碼(GND)方案。GND譯碼方案在傳統(tǒng)硬判決譯碼器的基礎(chǔ)上利用引入神經(jīng)網(wǎng)絡(luò)的遺傳算法對(duì)解調(diào)器的匹配濾波器的硬判決輸出序列做進(jìn)一步優(yōu)化，恢復(fù)出可信性較高的傳輸信息，從而提高硬判決譯碼器的糾錯(cuò)性能。由理論分析與仿真結(jié)果可知：本文提出的GND算法是一種譯碼復(fù)雜度較低、糾錯(cuò)性能較好和實(shí)用性較強(qiáng)的譯碼方案。