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

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

?

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

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

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

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

四進制LDPC碼；多進制高斯信道；譯碼算法；準確度

0 引言

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

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

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

1 四進制LDPC碼的編碼

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

U·HT=0；

(1)

利用上述分解，進而可以得到：

AC+BS=0。

(2)

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

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

2 四進制LDPC碼的譯碼

2.1 洪水譯碼算法

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

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

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

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

(1) 初始化

可得初始化概率為：

(3)

(2) 校驗點更新

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

(4)

(3) 變量點更新

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

(5)

(4) 判決

最后得到后驗概率為：

(6)

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

2.2 串行譯碼算法

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

該算法的具體步驟如下：

2：for任意一個校驗點m

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

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

7：endfor

8：endfor

9：endfor

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

11：end if

2.3 改進串行譯碼算法

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

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

該算法的具體步驟如下：

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

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

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

5：end if

6:end for

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

8：計算該變量節(jié)點的準確度V_A=pnc,sub_max-pnc,max

9：end for

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

11：其準確度置為0

12：end for

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

14：計算校驗節(jié)點的準確度M_A等于與其相鄰的變量節(jié)點的V_A的最小值

15：end for

16：校驗節(jié)點按準確度的升序進行排列

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未被滿足且未達到預(yù)設(shè)的最大迭代次數(shù)，則返回第2步

26：end if

2.4 算法分析

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

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

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

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

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

圖2 四進制LDPC碼不同譯碼算法的誤碼率分析

4 結(jié)束語

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

[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] 吳曉麗，孟 濤．一種改進的多進制 LDPC 碼的譯碼算法[J]．空軍工程大學(xué)學(xué)報(自然科學(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

李春騰，蔣宇中，宮 燁，等.多進制高斯信道下四進制LDPC碼的實現(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