李春騰 ，蔣宇中 ，宮 燁 ，張百勇

(1.海軍工程大學(xué) 電子工程學(xué)院，湖北 武漢 430033；2.海軍工程大學(xué)，湖北 武漢 430033)

?

多進(jìn)制高斯信道下四進(jìn)制LDPC碼的實(shí)現(xiàn)

李春騰1，蔣宇中1，宮 燁1，張百勇2

(1.海軍工程大學(xué) 電子工程學(xué)院，湖北 武漢 430033；2.海軍工程大學(xué)，湖北 武漢 430033)

四進(jìn)制低密度校驗(yàn)碼( Low-Density Parity-Check Code，LDPC)具有較好的抗突發(fā)差錯性能。為了進(jìn)一步改善系統(tǒng)的性能并適當(dāng)降低其復(fù)雜度，在二進(jìn)制LDPC碼的基礎(chǔ)上，主要研究短碼長四進(jìn)制LDPC碼，并在原有串行譯碼算法的基礎(chǔ)上對其改進(jìn)，提出一種基于校驗(yàn)點(diǎn)準(zhǔn)確度的串行譯碼算法。仿真結(jié)果表明，在多進(jìn)制高斯信道條件下，對于短碼而言，改進(jìn)的串行譯碼算法性能要優(yōu)于串行譯碼算法，在誤碼率為10-2時，能獲得0.25 dB的編碼增益。

四進(jìn)制LDPC碼；多進(jìn)制高斯信道；譯碼算法；準(zhǔn)確度

0 引言

雖然香農(nóng)在1948年界定了信道編碼[1]的性能，但是在Turbo碼出現(xiàn)之前，大部分信道編碼算法都遠(yuǎn)遠(yuǎn)達(dá)不到香農(nóng)限。因此Turbo碼的出現(xiàn)標(biāo)志著加性高斯白噪聲(AWGN)信道下信道編碼開始接近香農(nóng)限。1995年，在Turbo碼的啟發(fā)下，Mackay和Neal重新發(fā)現(xiàn)了長時間被遺忘的低密度校驗(yàn)(LDPC)碼具有更加接近香農(nóng)限的性能。LDPC碼是Gallager[2]于1962 年提出的一類基于稀疏校驗(yàn)矩陣的線性分組糾錯碼。按照稀疏校驗(yàn)矩陣定義的LDPC碼，每個碼字滿足許多線性約束。Gallager提出了LDPC碼的構(gòu)造方法、迭代概率譯碼算法和理論分析。但是由于編譯碼的復(fù)雜度以及Reed-Solomon碼和級聯(lián)碼的出現(xiàn)，LDPC碼并沒有得到足夠的重視。

Turbo碼雖然在3G通信標(biāo)準(zhǔn)中占據(jù)主導(dǎo)地位，但是LDPC碼與它相比在某些方面有著明顯的優(yōu)勢：LDPC碼所采用的迭代概率譯碼算法是并行算法，可以實(shí)現(xiàn)并行操作，有利于硬件的實(shí)現(xiàn)；并且LDPC碼是根據(jù)稀疏校驗(yàn)矩陣定義的，所以其本身就有很好的抗突發(fā)差錯的性能，不需要引入交織器，減少了時延。這些優(yōu)勢使LDPC碼在信道條件較差的無線移動通信中展現(xiàn)了很大的應(yīng)用前景，適合于在未來的通信系統(tǒng)中實(shí)現(xiàn)。

多進(jìn)制LDPC碼是LDPC碼的一種特殊形式，有實(shí)驗(yàn)表明，其抗突發(fā)差錯性能相比于二進(jìn)制LDPC碼有較大程度的改善[3-4]。目前，對二進(jìn)制LDPC碼的編譯碼技術(shù)已基本成熟，對多進(jìn)制的研究也取得初步的成果，但都是基于二進(jìn)制AWGN信道下。本文將在多進(jìn)制AWGN信道下，根據(jù)二進(jìn)制LDPC碼中的編譯碼基礎(chǔ)，來實(shí)現(xiàn)四進(jìn)制LDPC碼的編譯碼并進(jìn)行相應(yīng)的性能分析。

1 四進(jìn)制LDPC碼的編碼

對于編碼過程而言，類比于二進(jìn)制LDPC碼的編碼過程，四進(jìn)制中用到的是具有近似系統(tǒng)形式的H矩陣的快速編碼[5]。已知一個碼字U，奇偶校驗(yàn)矩陣為H。編碼之前的信息源為S。假設(shè)編碼后S位于U的后部，校驗(yàn)位C位于U的前部，即U=[C|S]。下面對矩陣H進(jìn)行分解，即H=[A|B]，而后對A進(jìn)行行變換，使其成為可逆矩陣，這樣得到的矩陣A是一個M×M大小的，B是一個M×(N-M)大小的矩陣。因此可以得到：

U·HT=0；

(1)

利用上述分解，進(jìn)而可以得到：

AC+BS=0。

(2)

通過上式在四元伽羅華域中的運(yùn)算，就可以得到校驗(yàn)位，將校驗(yàn)位和信息位合并就得到編碼之后的碼字。

最初得到的矩陣H往往達(dá)不到矩陣A可逆的要求，因此需要對矩陣H進(jìn)行行列交換，這樣可以保證在絕大多數(shù)的情況下可以將矩陣H轉(zhuǎn)換成可逆矩陣A和B矩陣的乘積。這里對矩陣H進(jìn)行行交換，相當(dāng)于交換了校驗(yàn)點(diǎn)的位置，并不會影響矩陣H的編碼結(jié)果，而列交換相當(dāng)于對碼字的順序進(jìn)行重新排列，在編碼結(jié)束后按照交換的順序進(jìn)行反變換，就可得到原矩陣H對應(yīng)的編碼后的碼字。

2 四進(jìn)制LDPC碼的譯碼

2.1 洪水譯碼算法

對于譯碼過程，同樣類比于二進(jìn)制的譯碼過程，用到的也是信度傳播[6](Belief-propagation，BP)算法[7-8]。對于四進(jìn)制BP算法而言，其和二進(jìn)制的過程大體一致，主要包括初始化、校驗(yàn)點(diǎn)更新、量點(diǎn)更新和判決。該算法中心思想就是利用校驗(yàn)方程得到變量滿足四元域的約束關(guān)系，通過迭代運(yùn)算來進(jìn)行糾錯。為了使譯碼過程更容易理解，先引入如下變量：

代表矩陣H的行重(每行非零元素的個數(shù))，代表矩陣H的列重(每列非零元素的個數(shù))，a代表四元域中的某個元素(用數(shù)值0、1、2、3來代表四元域中的4個元素)；

m代表矩陣H的校驗(yàn)方程的個數(shù)(即行數(shù))，n代表矩陣H的變量的個數(shù)(即列數(shù))；

N(m)，與第m個校驗(yàn)點(diǎn)相鄰的所有變量；M(n)，與第n個分量相鄰的所有校驗(yàn)點(diǎn)；N(m) ，與第m個校驗(yàn)點(diǎn)相鄰的除了第n個分量之外的其他所有分量；M(n)m，與第n個分量相鄰的除了第m個校驗(yàn)點(diǎn)之外的其他所有校驗(yàn)點(diǎn)。

(1) 初始化

可得初始化概率為：

(3)

(2) 校驗(yàn)點(diǎn)更新

這相當(dāng)于校驗(yàn)點(diǎn)的計(jì)算過程，注意四進(jìn)制的運(yùn)算要滿足上述四元域的運(yùn)算法則。假設(shè)矩陣H中的第一個校驗(yàn)方程為3x3⊕2x5⊕3x7=0，利用全概率公式可以得到滿足其約束條件的4個條件概率的相加：

(4)

(3) 變量點(diǎn)更新

這一步工作是變量點(diǎn)的計(jì)算，看作是重復(fù)節(jié)點(diǎn)的計(jì)算。

(5)

(4) 判決

最后得到后驗(yàn)概率為：

(6)

得到后驗(yàn)概率后，對每一個變量點(diǎn)選擇概率最大的那個，將其所對應(yīng)的a的值就作為該變量節(jié)點(diǎn)的最后譯碼結(jié)果。這樣就得到了一個新的碼字序列vhat，如果vhat·HT=0，則譯碼成功，否則就轉(zhuǎn)到第二步，繼續(xù)進(jìn)行迭代直至達(dá)到預(yù)設(shè)的最大迭代次數(shù)。

2.2 串行譯碼算法

該算法同上述譯碼算法的過程類似，其中更新步驟的運(yùn)算以及判決步驟和洪水譯碼[9-10]算法一樣。區(qū)別在于洪水譯碼算法在譯碼的過程中，要等校驗(yàn)節(jié)點(diǎn)全部更新完之后，變量節(jié)點(diǎn)才開始更新；而串行譯碼算法[11-12]則是每更新完一個校驗(yàn)節(jié)點(diǎn)或者變量節(jié)點(diǎn)，就對其相鄰的所有變量節(jié)點(diǎn)或校驗(yàn)節(jié)點(diǎn)進(jìn)行更新，這樣能夠使之后要更新的節(jié)點(diǎn)及時利用到相鄰節(jié)點(diǎn)的最新信息，從而加快收斂速度。

該算法的具體步驟如下：

2：for任意一個校驗(yàn)點(diǎn)m

3：for集合N(m)中任意一個n

5：for集合M(n)m中任意一個m′

7：endfor

8：endfor

9：endfor

10：ifvhat·HT=0未被滿足且未達(dá)到預(yù)設(shè)的最大迭代次數(shù)，則返回第2步

11：end if

2.3 改進(jìn)串行譯碼算法

上節(jié)所提到的串行譯碼算法在每次迭代時都是按照校驗(yàn)節(jié)點(diǎn)的排列順序進(jìn)行更新，并沒有對其更新的優(yōu)先級進(jìn)行區(qū)分。下面提出一種基于校驗(yàn)節(jié)點(diǎn)準(zhǔn)確度的串行譯碼算法對信息的更新順序進(jìn)行排列。

在四元域中，信號在經(jīng)過多進(jìn)制AWGN信道之后，由于受到高斯白噪聲的影響，在接收端收到的值可能是四元域中的任意一個元素，概率值越大意味著取該元素值的可能性越大，但并不能保證取最大概率值的那個域元素就是之前發(fā)送的那個值，因此，在每次迭代運(yùn)算中都要作比較，如果相同，則進(jìn)行下一個；如果不同，則稱之為錯誤碼位，并找到其對應(yīng)的變量節(jié)點(diǎn)。如果該變量節(jié)點(diǎn)的最大概率與次最大概率值相差很大，則說明該變量節(jié)點(diǎn)的準(zhǔn)確度很低，對誤碼性能的影響很大，需要優(yōu)先更新其相鄰的校驗(yàn)節(jié)點(diǎn)。因此定義準(zhǔn)確度V_A為錯誤碼位對應(yīng)的變量節(jié)點(diǎn)的次最大概率與最大概率之差。校驗(yàn)節(jié)點(diǎn)相鄰的所有變量節(jié)點(diǎn)對其準(zhǔn)確度都有影響，但是其中準(zhǔn)確度最低的對其影響最大。因此，校驗(yàn)節(jié)點(diǎn)的準(zhǔn)確度M_A定義為與其相鄰的變量節(jié)點(diǎn)的準(zhǔn)確度的最小值。

該算法的具體步驟如下：

2:for 集合N(m)中任意一個n

3：if pn,max對應(yīng)的域元素不等于編碼后對應(yīng)的碼字中的那一位

4：將該變量節(jié)點(diǎn)加入集合C中

5：end if

6:end for

7：for 集合C中的變量節(jié)點(diǎn)nc

8：計(jì)算該變量節(jié)點(diǎn)的準(zhǔn)確度V_A=pnc,sub_max-pnc,max

9：end for

10：for 除了集合C之外的其他變量節(jié)點(diǎn)

11：其準(zhǔn)確度置為0

12：end for

13：for 集合M(n)中任意一個m

14：計(jì)算校驗(yàn)節(jié)點(diǎn)的準(zhǔn)確度M_A等于與其相鄰的變量節(jié)點(diǎn)的V_A的最小值

15：end for

16：校驗(yàn)節(jié)點(diǎn)按準(zhǔn)確度的升序進(jìn)行排列

17：for集合M(n)中任意一個m

18： for集合N(m)中任意一個n

20： for集合M(n)m中任意一個m′

22： end for

23： end for

24：end for

25：if vhat·HT=0未被滿足且未達(dá)到預(yù)設(shè)的最大迭代次數(shù)，則返回第2步

26：end if

2.4 算法分析

對q元LDPC碼的串行改進(jìn)算法進(jìn)行復(fù)雜度分析。假設(shè)校驗(yàn)矩陣H是m行n列，行重為dc，列重為dv。為了方便分析和比較算法的復(fù)雜度，從初始化準(zhǔn)則、譯碼準(zhǔn)則、停止準(zhǔn)則3個方面對其進(jìn)行分析。并且認(rèn)為該算法的初始化以及停止準(zhǔn)則和串行算法一樣，每次迭代時信息更新的內(nèi)容以及傳遞次數(shù)也與串行算法大致相同，不同的是該算法信息更新的順序卻在不斷發(fā)生變化，這就涉及到為獲取節(jié)點(diǎn)準(zhǔn)確度而增加額外計(jì)算量去選擇要更新的節(jié)點(diǎn)，因此，與串行譯碼算法相比，改進(jìn)串行譯碼算法增加了節(jié)點(diǎn)準(zhǔn)確度的運(yùn)算。準(zhǔn)確度的獲取需要先比較最大概率對應(yīng)的值與發(fā)送的是否相同，如果不相同，再進(jìn)行最大概率與次最大概率的差值運(yùn)算，如果相同，則準(zhǔn)確度置為0。所以，對于每個變量節(jié)點(diǎn)而言，最多需要n(q-1)+n+n(q-2)次實(shí)數(shù)比較和一次實(shí)數(shù)加法運(yùn)算。對于校驗(yàn)節(jié)點(diǎn)的準(zhǔn)確度，需要找到相鄰變量節(jié)點(diǎn)中準(zhǔn)確度最低的，因此每個校驗(yàn)節(jié)點(diǎn)需要dc-1次實(shí)數(shù)比較，而后還要根據(jù)校驗(yàn)節(jié)點(diǎn)的準(zhǔn)確度對其進(jìn)行升序排列，因此需要O(mlog(m))次實(shí)數(shù)比較。

3 仿真結(jié)果與分析

實(shí)驗(yàn)1中采用(72，2，3)四進(jìn)制碼，碼率為1/3，信源發(fā)送出的消息經(jīng)信源編碼之后經(jīng)過四進(jìn)制LDPC編碼，再將編碼后的碼字通過多進(jìn)制高斯信道，引入加性高斯白噪聲，在接收端經(jīng)過四進(jìn)制LDPC譯碼，將從噪聲中提取出來有用的信息轉(zhuǎn)換成經(jīng)信道之前所編的碼字，將其與之前的碼字作對比，并進(jìn)行誤碼率分析；另一種情況,信源發(fā)出的信號經(jīng)過信源編碼之后不經(jīng)過LDPC編碼直接經(jīng)過多進(jìn)制高斯信道，引入加性高斯白噪聲，采用碼長為N=80 000。從圖1可看到，在信噪比為0時，沒有LDPC編譯碼的誤碼性能要優(yōu)于有LDPC編譯碼的，在低信噪比的情況下，沒有LDPC編譯碼的誤碼性能與有四進(jìn)制LDPC編譯碼的性能相差不大；隨著信噪比的逐漸提高，有LDPC編譯碼的誤碼性能要明顯優(yōu)于沒有LDPC編譯碼，這說明LDPC碼對通信系統(tǒng)的可靠性起著重要的作用。這是由于LDPC譯碼算法中引入了迭代運(yùn)算，通過變量之間的約束關(guān)系使得判決更加準(zhǔn)確，從而達(dá)到糾錯的目的。

圖1 GF(4)上LDPC碼的誤碼率分析對比

實(shí)驗(yàn)2采用GF(4)上的四元LDPC碼，該碼長為48，碼字的信息位為16，碼率為1/3，最大迭代次數(shù)為5，在多進(jìn)制高斯信道下對不同的譯碼算法的進(jìn)行誤碼率分析。校驗(yàn)矩陣的行重為3，列重為2。從圖2可看出，洪水譯碼算法的性能曲線是最差的。在低信噪比區(qū)域，改進(jìn)串行譯碼算法的性能要明顯優(yōu)于串行譯碼算法，隨著信噪比的提高，改進(jìn)串行譯碼算法的性能略優(yōu)于串行譯碼算法。當(dāng)誤碼率為10-2dB時，改進(jìn)串行譯碼算法相比于洪水譯碼算法能獲得0.6 dB的編碼增益，與串行譯碼算法相比，能獲得約0.25 dB的編碼增益。這是由于在低信噪比區(qū)域，受高斯白噪聲影響較大，導(dǎo)致錯碼的位數(shù)相對較多，而改進(jìn)串行譯碼算法在每次迭代時，會根據(jù)節(jié)點(diǎn)的狀態(tài)來優(yōu)先對準(zhǔn)確度最差的節(jié)點(diǎn)進(jìn)行更新，即優(yōu)先糾正錯誤的碼位，從而避免造成差錯傳播。隨著信噪比的提高，錯碼的位數(shù)越來越少，因此改進(jìn)串行譯碼算法的信息更新順序和串行譯碼算法的大致相同，從而二者的性能也近乎相同。

圖2 四進(jìn)制LDPC碼不同譯碼算法的誤碼率分析

4 結(jié)束語

在二進(jìn)制LDPC編譯碼的基礎(chǔ)上，重點(diǎn)研究了在多進(jìn)制信道下的四進(jìn)制LDPC碼，并提出一種基于校驗(yàn)節(jié)點(diǎn)準(zhǔn)確度的串行譯碼算法，對信息的更新按照準(zhǔn)確度由低到高的順序進(jìn)行，從而在一定程度上改善了誤碼性能。另外，本文對構(gòu)造的矩陣H進(jìn)行了簡化，限制了其行重為3，從而列重也被限制，也使得列重這一重要的參數(shù)沒有參與最佳化過程，因而誤碼性能會受到一定的影響，這一點(diǎn)有待改進(jìn)。

[1] 孟德香，梁紅玉，吳偉陵.基于同步時間拓展處理的信道編碼[J],無線電工程，2004,34(3):7-9.

[2] Gallager R.Low- Density Parity- Check Codes [M].Cambridge,Masscahusetts:MIT Press,1963.

[3] Davey M C,Mackay D J C.Low Density Parity Check Codes over GF(q)[J].IEEE Communication Letter.,1998,2:165-167.

[4] Davey M C,Mackay D J C.Low Density Parity Check Codes over GF(q)[C]∥in Proc.IEEE Inform.Theory workshop 1998:70-71.

[5] McEliece J R.The Theory of Information and Coding [M].New York:Cambridge University Press,2002.

[6] Kschischang F R,Frey B J.Iterative Decoding of Compound Codes by Probability Propagation in Graphical Models [J].IEEE Journal on Selected Areas in Communications,1998,16(2):219-230.

[7] Kschischang F R,Frey B J,Loeliger H.Factor Graphs and the Sum-product Algorithm [J].IEEE Transactions on Information Theory,2001,47(2):498-519.

[8] GuilloudF,Boutillon E,Tousch J,et al.Generic Description and Synthesis of LDPC Decoders[J].Communications IEEE Transactions on,2007,55(11):2084-2091.

[9] 吳曉麗，孟 濤．一種改進(jìn)的多進(jìn)制 LDPC 碼的譯碼算法[J]．空軍工程大學(xué)學(xué)報(bào)(自然科學(xué)版)，2009，11(4)：73-77．

[10]Tian Tao,Jones C,Villasenor J D,et al.Construction of Ireegular LDPC Codes with Low Error Floors[C]∥ Proceedings of ICC,2003,5:3125-3129.

[11]張小花.LDPC碼的譯碼算法研究[D].太原：太原理工大學(xué)，2012.

[12]岳 田,裴保臣.LDPC碼的幾種譯碼算法比較[J].無線電通信技術(shù),2006,32(4):24-26.

Implementation of 4-ary LDPC Codes under Non-binary AWGN Channel

LI Chun-teng1,JIANG Yu-zhong1,GONG Ye1,ZHANG Bai-yong2

(1.College of Electronic Engineering,Naval Univ.of Engineering,Wuhan Hubei 430033,China;2.Naval Univ.of Engineering,Wuhan Hubei 430033,China)

4-ary LDPC(Low-Density Parity-Check)Code has better performance of resistance to burst errors.To improve performance and reduce the complexity of algorithm,this paper mainly about the research of 4-ary LDPC codes with a short code length based on binary LDPC codes.Based on the layer belief propagation,this paper proposes serial decoding algorithm based on the accuracy of check node.Under non-binary AWGN channel,in terms of a short code length,simulation results show that the performance of improved serial decoding algorithm is better than layer belief propagation,it can achieve 0.25dB performance gain at the symbol error rate of 10-2.

4-ary LDPC；non-binary AWGN channel；decoding algorithm；accuracy

10.3969/j.issn.1003-3114.2016.06.22

李春騰，蔣宇中，宮 燁，等.多進(jìn)制高斯信道下四進(jìn)制LDPC碼的實(shí)現(xiàn)[J].無線電通信技術(shù),2016,42(6):86-90.

2016-07-07

李春騰(1992—)，男，碩士碩士生，主要研究方向：通信理論與技術(shù)。蔣宇中(1963—)，男，教授，博士生導(dǎo)師，主要研究方向：通信信號處理、低頻大氣噪聲。

TN911.22

A

1003-3114(2016)06-86-5