改進的離散字母表迭代譯碼算法研究

摘要：為了優化LDPC迭代譯碼性能和降低算法復雜度，提出了一種改進的基于Gallager A算法的2 b離散字母表迭代譯碼算法。在每一輪迭代中，Tanner圖上的校驗節點與變量節點之間所傳遞的消息有1 b表示符號值，另1 b反映碼字結構特性，其中變量節點更新規則是通過查表法來實現的。在二元對稱信道下針對列重為3的規則LDPC碼做了仿真實驗，仿真結果表明該算法性能明顯優于原算法，并且具有較低的復雜度。

關鍵詞：LDPC； 迭代譯碼； 碼字； 二元對稱信道

中圖分類號：TN91134文獻標識碼：A文章編號：1004373X(2012)04000403

Research on improved discrete alphabet iterative decoding algorithm

GUO Junjun1， WU Daiwen2

(1. Department of Computer， Shaanxi Post Telecommunication College， Xianyang 712000， China;

2. Department of Media Engineering， Weinan Teacher's University， Weinan 714000， China)

Abstract： To optimize the performance of iterative decoding for LDPC code and reduce the complexity of algorithms， a novel 2bit discrete alphabet iterative decoding algorithm based on Gallager A algorithm is presented in this paper. In every iteration， messages transmitted between check nodes and variable nodes in Tanner graph has two bits: one denotes the value of message and another indicates the characteristic of codeword， in which the update rules for variable nodes are realized by the lookup map table (LUMT). A simulation experiment for 3leftregular LDPC codes on binary symmetric channel (BSC) was conducted. The simulation results show that the performance of the proposed algorithm with lower computational complexity is more significant than that of the original algorithm.

Keywords： LDPC; iterative decoding; codeword; BSC

收稿日期：20110910

基金項目：教育部特色專業建設點項目(TS11772)；陜西省教育科學“十一五”規劃2010年立項課題（SGH10154)0引言

LDPC(LowDensity ParityCheck)碼是Gallager在20世紀60年代首次提出的［1］，它和Turbo碼都屬于重要的現代糾錯編碼技術。由于LDPC碼具有較好的距離特性和較低的譯碼復雜度，以及在AWGN信道上逼近信息論的理論極限：香農限［23］，因此，近年來引起國內外編碼界廣泛的關注［48］。

傳統的基于消息傳遞的迭代譯碼算法包括Gallager A/B算法和置信傳播(BP)譯碼算法，其本質上是消息或置信度沿著Tanner圖的邊在校驗節點與信息節點之間不斷更新，逐次逼近正確解。Gallager A/B算法復雜度低，執行速度快，但譯碼性能較差，而置信傳播或和積譯碼算法譯碼性能好。但是，BP譯碼算法復雜度高，存在錯誤平層現象，這是因為BP譯碼算法是一種貝葉斯推理問題(BIP)的求解方法，每輪迭代中計算量大，且在有環的Tanner圖上存在邊緣概率重疊和干擾現象，故其解是次優的。上述這些譯碼算法都具有通用性和普遍性的特點，沒有充分考慮實用碼字的結構特性。

本文給出了一種基于Gallager A的改進的2 b量化消息譯碼算法，其中一個比特表示消息符號，另一比特表示量化階。Tanner圖中的變量節點和校驗節點的消息更新規則考慮到了圖模型的結構特征，其方法簡單有效。仿真結果表明，改進后的譯碼算法性能明顯優于原算法。

1Gallager A 譯碼算法

Richardson等人在文獻［4］中提到Gallager A算法，在迭代譯碼過程中沿著Tanner邊傳遞的消息來自離散的有限消息字母表M={-1，1}，假定從BSC信道中接收(dc，dv)規則LDPC碼的二元序列值{yi}i=0，1，2，…，N－1經BPSK調制（ri=1－2yi）后輸入到譯碼器。Gallager A譯碼算法可以表示為Gad=f(ωc，ωv，R，p)。其中函數ωc(e1，e2，…，edc－1)指的是由校驗節點到變量節點更新規則的映射。相應地，函數ωv(m0，m1，m2，…，mdv－1，r)是由變量節點到校驗節點規則的映射。R和p分別表示調制后的接收向量和信道參數。每一輪譯碼結束后，采用如下判決規則：=－r，m1=m2=m3=－r

r，otherwise 對于（3，4）規則LDPC碼而言，其譯碼規則可以采用查表法表示，校驗節點和變量節點更新規則如圖1所示。

圖1Gad算法中校驗節點和變量節點更新規則表圖1中，e0=ωc(e1，e2，e3)，m0=ωv(m1，m2，r)。

2改進的離散字母表譯碼算法

2.1算法基本思想

Gallager A譯碼算法是基于大數原則進行判決的，糾錯能力可以突破碼字距離的限制。但對于Tanner圖中存在特殊的環狀子結構時，會導致譯碼失敗，如圖2(a)所示的6環子結構中，如果環上變量節點信息最初是錯誤的，而從環外進入的信息全部是正確的，經過若干輪迭代譯碼后，變量節點集V={v1，v2，v3}中判決結果依然保持原值，迭代譯碼陷入僵局［9］。

圖2Tanner圖模型上的譯碼結構子圖為了進一步提高譯碼性能，在此基礎上提出改進的算法。其基本思想在于：既然有害的Tanner圖子結構中并不孕育著糾錯信息，可以充分利用子圖結構，借助外界進入的信息糾正錯誤，使其變量節點的值翻轉。令M={-2，-1，1，2}，校驗節點更新函數參照最小和譯碼算法實現。ωc(e1，e2，…，edc－1)=

∏dc－1j=1sign(mj)minj∈(1，2，…，dc－1)(mj)(1)變量節點更新是進入的信息和信道接收值r求和后量化映射到M空間。ωv(m0，m1，…，mdv－1，r)=ψ(∑dv－1j=1mj+r)(2)式（2）可以表示成如圖3所示的映射規則表。

圖3改進的Gallager A譯碼算法中變量節點更新規則表采用本文提出的新穎的4階譯碼算法，經一輪迭代后，環中變量節點集V的信息由-1翻轉為1，從而有效地實現了譯碼。

2.2改進的兩比特階譯碼算法

根據算法分析結果，提出了4階離散字母表譯碼算法，變量節點與校驗節點之間傳遞的消息長度為2 b，其字母表可以表示為{11，10，00，01}。

輸入：校驗矩陣H和信道接收向量R

輸出：估計碼字

具體算法步驟如下：

（1） 初始化， ωv(m0，m1，…，mdv－1，R)=R。

（2） while HT≠0 .and. i

(3) 由式(1)計算由校驗節點到變量節點傳入的信息值。

（4） 由查找映射表函數LuMT(m0，m1，R)或LuMT(m1，m0，R)在表2中得到返回值m0作為變量節點到校驗節點傳入的信息值。

（5） 計算變量節點軟判決值=∑dvj=1mj+R。

（6） 輸出判決結果=0，>0

1，<0

y，=0 。

（7） end while。

以上算法適用于BSC信道下，列重dv=3的規則LDPC碼。采用該算法，可以譯出Gallager A算法不能正確譯碼的特殊Tanner環結構，圖1(b)表明了在兩輪迭代譯碼后6環上的信息傳遞情形。

3實驗結果與分析

為了便于比較分析，選擇了碼長為n=96，碼率R=0.5的規則LDPC碼［9］，分別采用Gallager A、改進的Gallager A和BP譯碼算法在Windows XP操作系統平臺下進行仿真實驗，三種算法的最大迭代次數I=100，如圖4所示。

圖4(96，48)規則LDPC碼在BSC信道下性能仿真圖由上圖仿真結果可知，在信道轉移概率P較大部分，Gallager A和本文提出的改進譯碼算法性能比較接近，而隨著P的減小，改進的譯碼算法明顯優于原算法。事實上，它們與BP譯碼算法的性能還有一定的差距。

4結語

本文所提出的兩比特離散字母表迭代譯碼算法是對原有的Gallager A算法的改進，其仿真性能優于Gallager A算法。目前，該算法只針對在BSC下列重為3的規則LDPC碼。因此，設計和實現在不同信道下的不規則LDPC碼的離散字母表迭代譯碼規則是今后的研究方向。

參考文獻

［1］GALLAGER R G. Lowdensity paritycheck codes \\[J\\]. IRE Trans. on Inf. Theory， 1962， 8 (1): 2128.

［2］MACKAY D J C， NEAL R M. Near Shannon limit performance of low density parity check codes \\[J\\]. Electronics Letters， 1996， 32 (18): 16451646.

［3］WIBERG N. Codes and decoding on general graphs \\[C\\]// Proceedings of 1995 IEEE International Symposium on Information Theory. Sweden: IEEE， 1995: 468478.

［4］李廣森，吳曉棟.LDPC碼編譯碼原理及性能仿真［J］.通信技術，2006(Z1):8690.

［5］張謹，蘇廣川.LDPC比特翻轉譯碼算法的分析與改進［J］.計算機應用，2006(7):17301731.

［6］劉向楠，趙洪林，張佳巖，等.一種改進的LDPC碼譯碼算法研究［J］.科學技術與工程，2011(24):58175822.

［7］DECLERCQ D， DANJEAN L， LI E， et al. Finite alphabet iterative decoding (FAID) of the (155，64，20) Tanner code \\[C\\]// Processing of 6th Int. Symp. on Turbo Codes and Iterative Information. \\[S.l.\\]: ISTC， 2010: 1115.

［8］曹建林.LDPC的硬判決譯碼研究［J］.電子與封裝，2006(12):3133.

［9］RICHARDSON T J， SHOKROLLAHI M A， URBANKE R L. Design of capacityapproaching irregular lowdensity paritycheck codes \\[J\\]. IEEE Trans. on Inf. Theory， 2001， 47 (2): 619637.

［10］MACKAY D J C. Encyclopedia of sparse graph codes \\[EB/OL\\]. \\[20051201\\].http://www.inference.phy.cam.ac.uk/mackay/codes/data.html.

作者簡介: 郭軍軍男，1978年出生，陜西橫山人，碩士研究生，講師。主要從事信息安全、LDPC編碼研究工作。

吳代文男，1979年出生，湖南衡陽人，碩士研究生，講師。主要從事信息論、教育信息技術研究工作。