周湘貞

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

1 背景

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

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

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

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

2.1 遺傳算法

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

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

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

3) 采用自然進化機制來表現(xiàn)復雜現(xiàn)象，能夠快速可靠地求解非常困難的問題。

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

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

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

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

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

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

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

3 GND譯碼方案

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

圖1 GND算法流程

3.1 譯碼方案模型

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

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

S=R·H′

(1)

根據(jù)最小距離譯碼準則和標準陣理論可知：碼字與最近可用碼字之間的漢明距離越大，則標準陣中其所對應的的陪首集重量越大，即可能含有的錯誤比特數(shù)越多，將其對應校正子作為輸入的神經(jīng)網(wǎng)絡的輸出值也越大。

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

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

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

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

(2)

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

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

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

T=rand[0,1]

(3)

步驟2個體適應度評價：

對遺傳算法個體的適應度進行評價

(4)

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

(5)

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

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

(6)

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

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

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

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

3.2 GND譯碼性能分析

3.2.1算法復雜度分析

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

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

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

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

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

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

表1 GND算法與Chase2、GPD算法復雜度對比情況

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

3.2.2誤比特性能分析

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

表3 默認參數(shù)值

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

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

4 結(jié)束語

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