基于RA結構的多元LDPC碼編譯碼的實現(xiàn)

田曉燕，蔡鎖，張鎖良

(河北大學 電子信息工程學院，河北 保定 071002)

?

基于RA結構的多元LDPC碼編譯碼的實現(xiàn)

田曉燕，蔡鎖，張鎖良

(河北大學 電子信息工程學院，河北 保定 071002)

多元低密度奇偶校驗(low density parity check，LDPC)碼因具有比二元LDPC碼更好的糾錯性能、更強的抗突發(fā)錯誤能力及能與高階調(diào)制相結合等特點而引起廣泛關注．然而，多元LDPC碼的諸多優(yōu)點卻被其高復雜度的編譯碼算法所限制．基于RA結構，構造出了具有快速編碼算法的校驗矩陣，采用雙向遞歸流水線算法進行編碼，并利用改進的EMS算法進行譯碼，降低了算法的復雜度和運算量，有利于硬件的實現(xiàn)．在加性高斯白噪聲信道下，對GF(2)和GF(4)的LDPC碼進行了性能比較，同時對GF(4) LDPC碼在BPSK和4QAM調(diào)制下進行了對比．仿真結果證明了設計的正確性和可行性．

多元LDPC碼；重復累積碼；雙向遞歸快速流水算法；擴展最小和算法

低密度奇偶校驗(low density parity check，LDPC)碼由Gallager于1962年首次提出[1]，是一種具有稀疏校驗矩陣的線性分組碼．多元LDPC碼由Davey和MacKay在1998年提出[2]，作為二元LDPC碼在伽羅華域的擴展，其具有更好的糾錯性能、更高的抗突發(fā)錯誤能力及更適合與高階調(diào)制系統(tǒng)相結合等優(yōu)點．然而，多元LDPC碼的諸多優(yōu)點卻因受到編譯碼復雜度高的限制而在實際中很難進行應用．多元LDPC碼的構造方法分為隨機構造法和結構性構造法2大類，常見的有Gallager構造法、漸近邊增長(progressive edge-growth，PEG)算法、有限幾何構造法等．但這些構造法用于硬件實現(xiàn)復雜度較高，不利于流水處理．多元LDPC碼的譯碼算法有置信傳播(belief propagation，BP)算法、基于快速傅里葉變換的置信傳播(FFT-BP)算法和擴展最小和(extended min-sum，EMS)算法．這些算法的優(yōu)點是譯碼效果好，但是計算復雜度和運算量比較大．針對上述問題，本文基于RA(repeat accumulate)結構[3]，構造出具有快速編碼算法的多元準循環(huán)LDPC碼校驗矩陣，并利用雙向遞歸快速流水算法進行編碼[4-5]，編碼效率和吞吐量都得到了提高；同時采用經(jīng)過修正的EMS算法進行譯碼[6]，雖然譯碼效果有所下降，但降低了運算復雜度，利于硬件的實現(xiàn)．

1 多元LDPC碼構造

基于RA結構的多元LDPC碼由重復器、交織器、加權器、組合器和累加器組成[7]，編碼流程如圖1所示.

圖1 RA結構編碼系統(tǒng)Fig.1 Coding system of RA structure

設長為k的信息序列m=[m1,m2,…，mk]，經(jīng)重復器重復p次得

m1=m2=…=mp=[m1,m2,…，mk].

(1)

交織器由p個內(nèi)交織的序列π1,π2,π3,…，πp組成，對信息序列m1=m2=…=mp完成交織，交織后輸出序列B1,B2,…，Bp,將p個輸出進行復合得

].

(2)

將復合后的A=[e1,e2,…，ek×p]輸入到加權器、組合器模塊，加權序列為W=[w1,w2,…，wk×p]，組合器參數(shù)設為a，經(jīng)過加權、組合操作后輸出為

a.

(3)

經(jīng)過累加器計算kp/a個校驗位，設累加因子為α,β∈GF(q)，則累加運算為

p1=r1·α-1,pi=(pi-1·β+ri)·α-1,i=2,3,…，kp/a.

(4)

由此得碼字C=[m1,m2,…,mk,p1,p2,…，pkp/a],碼率為a/(a+p)．通過上述過程可以構造出校驗矩陣H=[H1H2]，其中H1的列重對應重復次數(shù)p，行重對應為組合參數(shù)a，非零元素分布由交織器參數(shù)決定，非零元素值由加權器決定．H2是由累加器決定的準雙對角線矩陣．

2 快速編碼算法

以碼率為1/2的四元準循環(huán)LDPC碼為例．設編碼碼組為C=[m1,m2,…,mk,p1,p2,…,pk]，則C×HT=0．H矩陣為k×2k維的校驗矩陣，設H=[H1H2]=[h1,h2,…，hk]T，H2的結構如圖2所示，其中hi為1×2k維行向量．進行C×HT運算時，表示為

[0,0,…,0].

(5)

圖2 校驗矩陣的右半部分
Fig.2 Right part of the check matrix

由于GF(4)中，加法運算2+3=1，所以對于H2，所有列相加即[1,0,…,0].di代表校驗矩陣中每一列中非零元素的和，所以上式可表示為

[m1,m2,…,mk,p1,p2,…,pk]×[d1,d2,…,dk,1,0,…,0]T=0，

(6)

從而得出校驗位p1的表達式

).

(7)

p2=(2·p1+r2)·2,pk=(3·p1+r1)·2，

(8)

p3=(3·p2+r3)·2,pk-1=(3·pk+rk)·2.

(9)

圖3 雙向遞歸快速編碼算法流程Fig.3 Flow chart of fast double-recursion pipeline method

求出p1以后，可以用p1求p2和pk，然后用p2和pk求p3和pk-1，依次類推直到求出所有的校驗位．這種雙向遞歸快速流水編碼算法大大加快了編碼速度，可在實際中使用．對一個k×2k維、碼率為1/2的具有RA結構的多元準循環(huán)LDPC碼，采用上述編碼算法的流程如圖3所示，其中i的初始值為k-1，j的初始值為3，r是1×2k維的行向量．

3 可實現(xiàn)的EMS算法

本文采用了經(jīng)過修正的EMS譯碼算法，使其利于硬件實現(xiàn)．首先計算初始化消息向量，對于一個GF(q)上的多元LDPC碼，其信息位每位可能值有q個，所以碼組中的每位需要用一組q維向量表示：

Lch=[Lch(0),Lch(1),…,Lch(k),…,Lch(q-1)].

(10)

對于碼組中的任意位的任意1個域元素k，其消息向量的算法為

|yi-ki|2+|yi-s0|2),k=0,1,2,…,q-1，

(11)

其中s0為調(diào)制中0值對應的星座點，ki表示域元素k向量表示的第i個比特對應的調(diào)制星座點，yi表示編碼碼組向量表示的第i個比特對應的星座點經(jīng)過高斯信道后接收到的值．

考慮到真正影響譯碼的是消息向量各元素之間的相對大小關系，所以對計算得到的消息向量全部減去消息向量中的最大值不影響譯碼結果．

設Lmax為向量Lch=[Lch(0),Lch(1),…,Lch(q-1)]的最大值，則經(jīng)過減法得到的初始消息向量為

Lch=[Lch(0)-Lmax,Lch(1)-Lmax,…,Lch(q-1)-Lmax].

(12)

對向量進行排序，生成域元素向量Qch，與Lch中消息值一一對應，之后所有運算都將在消息向量與域元素向量之間展開，且均在保留所有域元素消息的前提下進行．

3.1 變量節(jié)點更新和置換

找出校驗矩陣中每列的非零域元素，設更新運算中的單步運算子分別為消息向量A和I，相應的域元素向量為βA和βI，運算結果設為T，域元素向量為βT，運算如下：

T(i)=I(j)+A(k),

(13)

其主旨意思為：找到A中與I對應域元素相同的消息值相加，得到的T即為更新單步運算的結果，其對應的域元素為βT，且βT必為0至q-1之間的1個域元素．將所有的q個值全部運算完畢，接下來將得到的消息向量進行降序排列，域元素向量也需要對應的改變．最后將除搜索到的非零域元素位置的其他位置和初始消息的消息向量及域元素向量做上述運算，作為搜索到位置的消息、域元素更新值．至此完成對一個校驗矩陣位置的填充，直到所有變量節(jié)點更新完成．變量節(jié)點向校驗節(jié)點傳遞信息時會用到置換運算：將變量節(jié)點更新得到的域元素乘以校驗矩陣對應位置的值．

3.2 校驗節(jié)點更新和反置換

校驗節(jié)點的更新是譯碼過程中運算最復雜且時間最長的．首先，找出校驗矩陣中每一行的非零元素位置，其單步運算的運算子仍定義為I和A，運算結果設為B，與其相關的域元素向量為βI、βA和βB，運算如下：

(14)

其主旨意思為：將2個消息向量中對應域元素相加相同的消息值后，從這樣一組值中找到最大值，作為消息值B(i)，將域元素相加得到的值作為βB，且βB必為0至q-1之間的1個域元素．依照此法，將剩下的域元素及其對應的消息值算出，再將算出的消息值降序排列，域元素向量對應改變，單步運算完成．接下來將除搜索到的非零域元素位置的其他位置做上述運算，直到所有校驗節(jié)點更新完畢．當校驗節(jié)點向變量節(jié)點傳遞信息時會用到反置換：將校驗節(jié)點更新得到的域元素除以校驗矩陣對應位置的值．

3.3 譯碼判決輸出

采用3.1步驟中的運算，將校驗矩陣中每一列所有非零位置和對應初始消息的消息向量及域元素向量做運算，因為更新后的消息向量都經(jīng)過降序處理，所以域元素向量的第1個元素即可能性最高的域元素，把域元素向量的第1個元素作為判決輸出，若譯碼結果滿足C×HT=0，則譯碼完成，否則繼續(xù)以上步驟．其流程如圖4所示.

4 性能分析

用隨機產(chǎn)生的信息位分別對(60×120)RA結構四元準循環(huán)LDPC碼以及(120×240)二元LDPC碼進行了仿真，調(diào)制方式為BPSK，通過加性高斯白噪聲信道，譯碼最大迭代次數(shù)設置為20次，幀長為150 000幀．得出誤碼率的性能曲線如圖5所示.

從圖5中可以看出，在相同碼長的條件下四元LDPC碼整體的誤碼率要比二元的好，這就是多進制LDPC碼引起人們關注的原因．

對于多元LDPC碼，在編碼完成后，碼組將被輸入調(diào)制系統(tǒng)中．下面對4QAM與BPSK 2種不同調(diào)制下的譯碼性能進行了比較[8]，如圖6所示.

采用4QAM調(diào)制時，誤碼率隨信噪比的增加，降低速度比較快，整體表現(xiàn)出較好的譯碼性能．相比于BPSK調(diào)制，它的誤碼率同時達到10-5量級，4QAM相比于BPSK，可提供1 dB的編碼增益．在實際信息傳輸中，采用4QAM的高階調(diào)制時對信道環(huán)境的要求更低，并且能夠更好的控制誤碼．

本文設計的具有RA結構的多元準循環(huán)LDPC碼不僅具有多元碼型自身所特有的抗突發(fā)錯誤特性，并且可以采用雙向遞歸快速算法進行編碼，能進行流水處理．同時采用改進的EMS算法進行譯碼，降低了譯碼復雜性，便于硬件的實現(xiàn)．此外，RA結構的LDPC碼自身具有交織特性，使其抗突發(fā)錯誤與糾錯的特性進一步提高．本文討論的RA結構多元LDPC碼具有比較大的研究和工程應用價值．

圖4 EMS譯碼算法流程Fig.4 Flow chart of EMS decoding algorithm

圖5 LDPC碼性能比較Fig.5 Performance comparison of LDPC

圖6 RA結構不同調(diào)制下的性能比較Fig.6 Performance comparison of RA structure with different modulations

[1] GALLAGER R G.Low-density parity-check codes [J].IRE Trans Information Theory,1962,8(1):21-28.

[2] DAVEY M C,MACKAY D J C.Low density parity check codes over GF(q) [J].IEEE Commun Lett,1998,2(6):165-167.

[3] JOHNSO S J,WELLER S R.Combinatorial interleavers for systematic regular repeat-accumulate codes [J].IEEE Transactions on Communications,2008,56(8):1201-1206．

[4] 袁瑞佳，白寶明，童勝．10 Gbps LDPC編碼器的FPGA設計[J]．電子與信息學報，2011，33(12)：2942-2947.DOI：10.3724/SP.J.1146.2010.01338. YUAN R J,BAI B M,TONG S.FPGA-based design of LDPC encoder with throughput over 10 Gbps [J].Journal of Electronics & Information Technology,2011,33(12):2942-2947.DOI:10.3724/SP.J.1146.2010.01338.

[5] 張博，林偉，劉春元，等．突發(fā)錯誤信道下的多元LDPC碼設計與性能分析[J]．通信學報，2013，34(7)：98-104.DOI：10.3969/j.issn.1000-436x.2013.07.011. ZHANG B,LIN W,LIU C Y,et al.On the designand performance of nonbinary LDPC codes on burst errorchannels [J].Journal on Communications,2013,34(7):98-104.DOI:10.3969/j.issn.1000-436x.2013.07.011.

[6] ZHAO S C,LU Z F,MA X,et al.A variant of the EMS decoding algorithm for nonbinary LDPC Codes [J].IEEE Communications Letters,2013,17(8):1640-1643.

[7] 張紅泰，劉宏立，劉述剛．基于滿二叉樹的RA碼交織器設計[J]．計算機工程與科學，2015，37(4)：699-703.DOI：10.3969/J.issn.1007-130X.2015.04.012. ZHANG H T,LIU H L,LIU S G.Interleaver design for RA codes based on full binary tree [J].Computer Engineering & Science,2015,37(4):699-703.DOI:10.3969/J.issn.1007-130X.2015.04.012.

[8] 呂巖，李勁．通用PSK和QAM解調(diào)接收機[J]．河北大學學報(自然科學版)，2013，33(2)：204-209.DOI：10.3969/j.issn.1000-1565.2013.02.017. LU Y,LI J.Universal PSK and QAM demodulation receiver [J].Journal of Hebei University(Natural Science Edition),2013,33(2):204-209.DOI:10.3969/j.issn.1000-1565.2013.02.017.

(責任編輯：王蘭英)

Encoder and decoder realization of non-binary LDPC codes based on RA structure

TIAN Xiaoyan,CAI Suo,ZHANG Suoliang
(College of Electronic and Information Engineering,Hebei University,Baoding 071002,China)

Compared with binary LDPC codes,non-binary codes have better error correction performance,stronger burst-error-correcting capability,can also combine with higher-order modulations,which attracted a wide-spread attentiaon.However the advantages of non-binary LDPC codes are limited by the high complexity of encoding and decoding algorithm.Based on repeat accumulate structure,a check matrix with fast algorithm was constructed.By using fast double-recursion pipeline method and improved EMS decoding algorithm,complexity and calculation of the algorithm were reduced,which are beneficial for the realization of the hardwares.On Gaussian channel,the BER of GF(2) and GF(4) LDPC codes are compared,and the modulation performance of BPSK and 4QAM are compared for GF(4) LDPC.Simulation results prove the validity and feasibility of the design.

non-binary LDPC codes;repeat accumulate codes;fast double-recursion pipeline method;EMS algorithm

2016-04-28

河北省自然科學基金資助項目(F2011201045)

田曉燕(1980—),女,河北衡水人,河北大學講師,主要從事信道編譯碼與信息處理方向的研究. E-mail:458664731@qq.com

張鎖良(1966—),男,河北藁城人,河北大學教授,主要從事高速數(shù)據(jù)通信方向的研究.E-mail:zhangsl@hbu.cn

10.3969/j.issn.1000-1565.2017.03.015

TN919

A

1000-1565(2017)03-0316-06