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

關(guān)鍵詞：LDPC； 迭代譯碼； 碼字； 二元對(duì)稱信道

中圖分類號(hào)：TN91134文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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

基金項(xiàng)目：教育部特色專業(yè)建設(shè)點(diǎn)項(xiàng)目(TS11772)；陜西省教育科學(xué)“十一五”規(guī)劃2010年立項(xiàng)課題（SGH10154)0引言

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

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

本文給出了一種基于Gallager A的改進(jìn)的2 b量化消息譯碼算法，其中一個(gè)比特表示消息符號(hào)，另一比特表示量化階。Tanner圖中的變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的消息更新規(guī)則考慮到了圖模型的結(jié)構(gòu)特征，其方法簡(jiǎn)單有效。仿真結(jié)果表明，改進(jìn)后的譯碼算法性能明顯優(yōu)于原算法。

1Gallager A 譯碼算法

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

r，otherwise 對(duì)于（3，4）規(guī)則LDPC碼而言，其譯碼規(guī)則可以采用查表法表示，校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)更新規(guī)則如圖1所示。

圖1Gad算法中校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)更新規(guī)則表圖1中，e0=ωc(e1，e2，e3)，m0=ωv(m1，m2，r)。

2改進(jìn)的離散字母表譯碼算法

2.1算法基本思想

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

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

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

圖3改進(jìn)的Gallager A譯碼算法中變量節(jié)點(diǎn)更新規(guī)則表采用本文提出的新穎的4階譯碼算法，經(jīng)一輪迭代后，環(huán)中變量節(jié)點(diǎn)集V的信息由-1翻轉(zhuǎn)為1，從而有效地實(shí)現(xiàn)了譯碼。

2.2改進(jìn)的兩比特階譯碼算法

根據(jù)算法分析結(jié)果，提出了4階離散字母表譯碼算法，變量節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)之間傳遞的消息長(zhǎng)度為2 b，其字母表可以表示為{11，10，00，01}。

輸入：校驗(yàn)矩陣H和信道接收向量R

輸出：估計(jì)碼字

具體算法步驟如下：

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

（2） while HT≠0 .and. i

(3) 由式(1)計(jì)算由校驗(yàn)節(jié)點(diǎn)到變量節(jié)點(diǎn)傳入的信息值。

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

（5） 計(jì)算變量節(jié)點(diǎn)軟判決值=∑dvj=1mj+R。

（6） 輸出判決結(jié)果=0，>0

1，<0

y，=0 。

（7） end while。

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

3實(shí)驗(yàn)結(jié)果與分析

為了便于比較分析，選擇了碼長(zhǎng)為n=96，碼率R=0.5的規(guī)則LDPC碼［9］，分別采用Gallager A、改進(jìn)的Gallager A和BP譯碼算法在Windows XP操作系統(tǒng)平臺(tái)下進(jìn)行仿真實(shí)驗(yàn)，三種算法的最大迭代次數(shù)I=100，如圖4所示。

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)

［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］.通信技術(shù)，2006(Z1):8690.

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

［6］劉向楠，趙洪林，張佳巖，等.一種改進(jìn)的LDPC碼譯碼算法研究［J］.科學(xué)技術(shù)與工程，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.

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

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