一種基于遺傳算法和神經網絡的硬判決譯碼方案

周湘貞

(鄭州升達經貿管理學院 信息工程系, 鄭州 451191)

1 背景

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

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

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

2 遺傳算法(GA)和神經網絡(NN)

2.1 遺傳算法

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

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

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

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

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

2.2 神經網絡

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

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

2) 自組織：神經網絡可以自行構建自己的結構或在學習過程中自行展示接收的信息。

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

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

3 GND譯碼方案

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

圖1 GND算法流程

3.1 譯碼方案模型

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

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

S=R·H′

(1)

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

圖2 神經網絡分類器

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

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

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

(2)

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

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

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

T=rand[0,1]

(3)

步驟2個體適應度評價：

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

(4)

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

(5)

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

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

(6)

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

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

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

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

3.2 GND譯碼性能分析

3.2.1算法復雜度分析

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

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

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

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

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

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

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

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

3.2.2誤比特性能分析

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

表3 默認參數值

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

圖3 GND譯碼算法性能仿真結果

4 結束語

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