基于滑動矩形窗和準三對角線結(jié)構(gòu)的QC-LDPC碼

汪漢新，王芳，蘇開友，朱翠濤

中南民族大學(xué)電信學(xué)院，武漢 430074

◎信號處理◎

基于滑動矩形窗和準三對角線結(jié)構(gòu)的QC-LDPC碼

汪漢新，王芳，蘇開友，朱翠濤

中南民族大學(xué)電信學(xué)院，武漢 430074

針對IEEE 802.16e標準QC-LDPC碼的碼長和碼率有限，及其采用的準雙對角線結(jié)構(gòu)包含大量度為2的變量節(jié)點導(dǎo)致較高錯誤平層的缺陷，提出一種基于滑動矩形窗和準三對角線結(jié)構(gòu)的QC-LDPC碼的快速編碼算法，可以靈活地擴展碼長和碼率的范圍，改善糾錯性能，降低編碼復(fù)雜度，適合于變速率的自適應(yīng)傳輸系統(tǒng)。

準循環(huán)低密度奇偶校驗（QC-LDPC）碼；對角線結(jié)構(gòu)；度分布；編碼復(fù)雜度

1 引言

QC-LDPC碼結(jié)構(gòu)簡單，易于高效編碼，適合硬件實現(xiàn)，因此在通信領(lǐng)域得到廣泛的應(yīng)用，如移動寬帶無線接入標準IEEE 802.16e QC-LDPC碼[1-5]。然而標準QC-LDPC碼中的碼率和碼長數(shù)量有限，在IEEE 802.16e中只有1/2，2/3，3/4和5/6總共4種碼率，碼長也只有19種，最小為576，最大為2 304，步長為96，嚴重制約了LDPC碼的實際應(yīng)用范圍，不能滿足自適應(yīng)傳輸系統(tǒng)中碼長和碼率靈活變化的要求。另外，標準QC-LDPC碼通常采用準雙對角線的下三角結(jié)構(gòu)，編碼效率和誤碼性能不太高。雖然通過最大化ACE和最小誤碼率準則等算法對QC-LDPC碼的循環(huán)移位次數(shù)和度分布進行優(yōu)化可以提高糾錯性能，但是算法的復(fù)雜度較高，且無法連續(xù)對一系列不同碼長進行優(yōu)化[6-8]。另外，為實現(xiàn)快速編碼，學(xué)者們也相繼提出了幾種準雙對角線的改進結(jié)構(gòu)，如三對角線結(jié)構(gòu)、新下三角結(jié)構(gòu)和后向迭代結(jié)構(gòu)。然而三對角線結(jié)構(gòu)要求嚴格，不能靈活變化，新下三角結(jié)構(gòu)和后向迭代結(jié)構(gòu)包含大量度為2的變量節(jié)點，會導(dǎo)致較高的錯誤平臺，并且這些改進結(jié)構(gòu)的QC-LDPC碼大多碼長和碼率受限，達不到靈活變化的要求[9-13]。本文提出一種基于滑動矩形窗和準三對角線結(jié)構(gòu)的QC-LDPC碼的構(gòu)造方法，通過滑動矩形窗實現(xiàn)碼長和碼率的靈活變化，采用去對角線法實現(xiàn)優(yōu)化度分布，并通過調(diào)整準三對角線結(jié)構(gòu)的第三條對角線的位置來消除部分度為2的變量節(jié)點，達到降低錯誤平層的目的。

2 滑動矩形窗結(jié)構(gòu)

2.1 H b1矩陣的滑動矩形窗構(gòu)造法

LDPC碼由一組循環(huán)移位矩陣構(gòu)成，其校驗矩陣H的置換子矩陣的下標Sij構(gòu)成的矩陣Hs的結(jié)構(gòu)如式（1）：

其中，Sij(1≤i≤m，1≤j≤n)∈(-1，0，N)表示矩陣中第i行第j列置換矩陣的循環(huán)移位次數(shù)，-1表示零矩陣，0表示單位矩陣，正整數(shù)N表示單位矩陣的循環(huán)右移位矩陣；若擴展因子z表示置換矩陣的維數(shù)，則Hs擴展后的H矩陣大小為mz×nz。

在QC-LDPC碼的H矩陣的構(gòu)造中，最重要的是避免4環(huán)的存在，若循環(huán)移位次數(shù)Sij滿足式（2），且z滿足一定值時，則構(gòu)造的矩陣無4環(huán)。

基于準雙對角線結(jié)構(gòu)的QC-LDPC碼的基本校驗矩陣Hb可表示為式（3）～式（5）。

其中，Hb1和Hb2分別為Hb矩陣中的信息比特部分和校驗比特部分；Hb1是無4環(huán)的稀疏矩陣，大小為mb×kb；Hb2是一個固定的雙對角線結(jié)構(gòu)的近似下三角矩陣，大小為mb×mb，矩陣中的0和-1分別表示單位矩陣和零矩陣，b(1)=b(m)=bm（bm為小于z的素數(shù)），b(r)=0。

根據(jù)式（2），由Hs矩陣可根據(jù)式（6）構(gòu)造無4環(huán)的Hb1，對應(yīng)的z值應(yīng)滿足式（7）。其中，1≤i≤m；hf為矩陣的第一行第一列元素的值；ct為第一行公差；rt為第一列公差；m和k分別為Hb1矩陣的行值和列值。

由于碼率R=k/(k+m)，因此只需改變m和k的值即可實現(xiàn)碼率和碼長的改變。例如當m=k=6時，則碼率R=1/2，最小碼長可達6×62=372，步長為12；若要得到R=1/3碼率，則在m不變的情況下，只需將k值變?yōu)?，在Hb1矩陣中相當于刪除其中3列，相應(yīng)的最小碼長為9×16=144，步長變?yōu)?；或者將m和k的值變?yōu)?和2，則相當于刪除其中2行和4列，最小碼長變?yōu)?×7= 42，步長為6?？梢钥闯?，無需重新構(gòu)造，只需刪除一定數(shù)量的行和列即可實現(xiàn)碼率和碼長的靈活變換靈活。同時通過修改hf、ct和rt的值，能構(gòu)造出不同z值和Hb1矩陣，其最終達到的效果也不盡相同，這三個值的選取可在誤碼率和迭代次數(shù)之間權(quán)衡。例如，當hf=1、ct=0、rt=1時，構(gòu)造得到6×6的矩陣如圖1中實線矩形窗覆蓋的矩陣。而當hf=3、ct=1、rt=2時，得到如圖1中虛線矩形窗矩陣。矩陣的變化在圖1中相當于實線矩形窗向右和向下各移一位到虛線矩形窗的位置，類似于矩形窗在Hs矩陣中滑動，因此稱為滑動矩形窗構(gòu)造法。

圖1 矩陣H s與滑動矩形窗

滑動矩形窗構(gòu)造Hb1矩陣的具體步驟如下：

（1）根據(jù)式（6）設(shè)計一個大小為m×k的矩形窗矩陣。

（2）根據(jù)擴展因子z，確定矩形窗在Hs中平移的位置。

（3）將滑動矩形窗覆蓋的元素作為Hb1矩陣，與m×m的固定結(jié)構(gòu)矩陣Hb2合并得到矩陣Hb。

采用滑動矩形窗構(gòu)造法，在構(gòu)造Hb1矩陣時，要求的z值更小，可以實現(xiàn)碼長和碼率靈活變化的QC-LDPC碼，非常適合于變速率的自適應(yīng)傳輸系統(tǒng)。

2.2 H b1矩陣的對角線優(yōu)化方法

在滑動矩形窗構(gòu)造方法中，若直接采用覆蓋的矩陣作為Hb1，則構(gòu)造出的QC-LDPC碼中的行和列的度數(shù)相同，相當于規(guī)則LDPC碼，誤碼率性能較差。因此本文通過去對角線優(yōu)化法，將矩陣修改成具有不同度數(shù)的矩陣，能進一步提高LDPC碼的糾錯性能。具體方法是，將滑動矩形窗構(gòu)造方法得到的Hb1矩陣中若干對角線元素用-1代替，即將這些位置的置換矩陣用零矩陣代替，實現(xiàn)度數(shù)分布的優(yōu)化。例如將圖1實線矩形框中的元素進行修改，得到如式（8）的H?b1矩陣，經(jīng)過和Hb2矩陣合并得到如式（9）的Hb矩陣。

通過滑動矩形窗構(gòu)造Hb1矩陣及其對角線優(yōu)化法，在實現(xiàn)碼長和碼率的靈活變化的同時，還可以提高QC-LDPC碼的誤碼率性能。

3 準三對角線結(jié)構(gòu)

3.1 H b2矩陣的準三對角線構(gòu)造法

QC-LDPC碼大多采用準雙對角線的近似下三角結(jié)構(gòu)，為了進一步提高編碼效率和誤碼率性能，需要對準雙對角線結(jié)構(gòu)的Hb2矩陣進行優(yōu)化?，F(xiàn)有文獻中對Hb2的優(yōu)化主要有三對角線結(jié)構(gòu)、新下三角結(jié)構(gòu)和反向迭代結(jié)構(gòu)。在三對角線結(jié)構(gòu)中，有三條對角線元素不為-1，其中一條元素為0，另外兩條為自然數(shù)，這兩條對角線元素的值需要滿足一定的條件，因此碼長和碼率受到限制；在新下三角結(jié)構(gòu)中，除第一列有三個元素不為-1外，其余列中有兩個元素不為-1；在反向迭代結(jié)構(gòu)中，兩條對角線位置元素為0，其余位置為-1；并且在新下三角結(jié)構(gòu)和反向迭代結(jié)構(gòu)中，度數(shù)為2的變量節(jié)點占了絕大部分，會導(dǎo)致較高的錯誤平層。針對這些結(jié)構(gòu)的缺點，本文提出一種準三對角線結(jié)構(gòu)的H?b2矩陣的構(gòu)造方法，如式（10）。其中，r(i)∈0，r(1)和r(l)分別表示第三條對角線的起始和終止位置，H?b2矩陣的元素只有0和-1，且只有三條對角線上的元素為0；要滿足無4環(huán)的條件，r(1)的行值應(yīng)不小于3。

從式（10）可以看出，與三對角線結(jié)構(gòu)相比，準三對角線結(jié)構(gòu)具有靈活調(diào)整第三條對角線位置的優(yōu)點，并且隨著H?b2矩陣維數(shù)的增加，第三條對角線可供選擇的位置也隨之增加；與新下三角結(jié)構(gòu)和后向迭代結(jié)構(gòu)相比，準三對角線結(jié)構(gòu)能夠消除一部分度為2的變量節(jié)點。由于第三條對角線位置選擇的不同，其度分布也不同，因此可以通過合適地選擇第三條對角線位置來優(yōu)化QC-LDPC碼的度分布，從而提高誤碼率性能。

根據(jù)滑動矩形窗構(gòu)造法，取m=9、k=9構(gòu)造Hb1，并采用準三對角線構(gòu)造法構(gòu)造Hb2，合并后得到Hb矩陣如圖2。其中，斜線表示的第三條對角線有6種可供選擇，當?shù)谌龡l對角線取其中的某一種，則該對角線上的元素-1由元素0代替。

圖2 基于滑動矩形窗和準三對角線結(jié)構(gòu)的H b矩陣

3.2 基于準三對角線結(jié)構(gòu)的QC-LDPC碼的快速編碼算法

基于滑動矩形窗和準三對角線結(jié)構(gòu)的QC-LDPC碼的快速編碼算法步驟如下：

步驟1將信息比特s和校驗比特p分段，每段長度為z，碼字序列c如式（11）。

其中，kb=k/z；mb=m/z。

步驟2根據(jù)校驗矩陣方程H·cT=0得：

其中，cr為?b2矩陣中r(1)的行值；Zb1(i，j)為矩陣?b1第i行第j列的置換矩陣。

步驟3由步驟2得到的 p=[p1p2… pmb]，再加上信息比特s，最終得到編碼碼字c。

在準雙對角線結(jié)構(gòu)中，p1的計算式為：

顯然，式（12）中的計算量要小于式（14），由此可知，準三對角線結(jié)構(gòu)編碼算法的計算復(fù)雜度低于準雙對角線結(jié)構(gòu)，更適合于硬件實現(xiàn)。表1給出了準三對角線和準雙對角線結(jié)構(gòu)編碼算法的p1運算量比較，其中LDPC碼的碼率為1/2、碼長為n、擴展因子為z。

表1 兩種結(jié)構(gòu)編碼算法的p1運算量比較

4 基于滑動矩形窗和準三對角線結(jié)構(gòu)QC-LDPC碼的仿真

采用快速迭代編碼算法，BPSK調(diào)制，LLR BP譯碼[14-15]，迭代次數(shù)20次，在AWGN信道下對基于滑動矩形窗和準三對角線結(jié)構(gòu)的QC-LDPC碼進行仿真，同時和IEEE802.16e標準QC-LDPC碼進行比較。

表2給出了m=6，k取不同的值時使用滑動矩形窗構(gòu)造QC-LDPC碼的參數(shù)。從中可以看到碼率范圍從1/7到5/8，且碼長按照不同的步長從42到816變化，碼長和碼率的變化非常靈活，因此可以滿足自適應(yīng)傳輸系統(tǒng)的需求。

表2 滑動矩形窗構(gòu)造QC-LDPC碼的參數(shù)

圖3是在相同碼率的情況下，不同度數(shù)的基本校驗矩陣在對角線優(yōu)化方法前后的性能對比。可以看出在度數(shù)不大于6時，優(yōu)化后的性能改善不大，但當度數(shù)大于6時，對角線優(yōu)化方法的性能優(yōu)勢明顯，QC-LDPC碼的誤碼率性能得到較大的提高。

圖3 對角線優(yōu)化前后的誤碼率性能比較

表3給出了滑動矩形與文獻[13]和802.16e標準QC-LDPC碼的各項指標的數(shù)據(jù)比較?？梢钥闯?，802.16e標準的LDPC碼的碼率只有4種，碼長以96為步長從576到2 304共19種，文獻[13]的碼率從1/4到3/4，最小碼長為336，步長為4到9。而滑動矩形窗QC-LDPC碼，其碼率沒有限制，且最小碼長為42，步長為4，結(jié)構(gòu)化的設(shè)計和改進的算法，可實現(xiàn)碼率、碼長的靈活變化，提高可用QC-LDPC碼的范圍，更適合于變速率的自適應(yīng)傳輸系統(tǒng)。

表3 滑動矩形窗與802.16e標準QC-LDPC碼的參數(shù)對比

根據(jù)圖2中的Hb矩陣，選擇不同的第三條對角線，對構(gòu)造的QC-LDPC碼進行誤碼性能分析。其中仿真幀數(shù)為300，碼長為1 152，碼率為1/2，擴展因子z=64，仿真結(jié)果如圖4?？梢钥闯?，第三條對角線選擇II或III的誤碼性能最好，VI的誤碼性能最差，這是由于第三條對角線的不同，得到的LDPC碼的度分布也不同。隨著碼長的增加，準三對角線結(jié)構(gòu)的第三條對角線的選擇更多，度分布的變化更靈活，接近好的度分布的機會也越大，因此準三對角線結(jié)構(gòu)具有更加的靈活性。

圖4 不同的第三條對角線的QC-LDPC碼誤碼性能

基于滑動矩形窗和準三對角線結(jié)構(gòu)QC-LDPC碼和IEEE802.16e標準LDPC碼在不同碼長情況下的誤碼性能比較結(jié)果如圖5。其中，碼長取576、960和1 152三種，仿真幀數(shù)分別為1 000、500和300，碼率為1/2?？梢钥闯?，在碼長為576時，基于滑動矩形窗和準三對角線結(jié)構(gòu)的QC-LDPC碼的誤碼性能較差，但在碼長為960和1 152時，其性能接近于802.16e標準LDPC碼，甚至在高信噪比時，其性能還要好于標準LDPC碼。

5 結(jié)束語

圖5 基于滑動矩形窗和準三對角線結(jié)構(gòu)QC-LDPC碼和802.16e LDPC碼的誤碼性能比較

本文提出的基于滑動矩形窗和準三對角線結(jié)構(gòu)的QC-LDPC碼的構(gòu)造方法以及快速迭代編碼算法，設(shè)計簡單且易于硬件實現(xiàn)，具有更低的計算復(fù)雜度，誤碼性能在低信噪比時接近802.16e標準QC-LDPC碼，在高信噪比時甚至要好于802.16e標準QC-LDPC碼，并且可實現(xiàn)碼率、碼長的靈活變化，提高可用QC-LDPC碼的范圍，更適合于變速率的自適應(yīng)傳輸系統(tǒng)。

[1]Fossorier M P C.Quasi-cyclic low density parity check codes from circulant permutation matrices[J].IEEE Trans on Info Theory，2004，50（8）：1788-1793.

[2]Tanner R M.A recursive approach to low com p lexity codes[J].IEEE Trans on Info Theory，1981，27（5）：533-548.

[3]Zhang Fan，Mao Xuehong，Zhou Wuyang.Girth-10 LDPC codes based on 3-D cyclic lattices[J].IEEE Trans on Vehicular Technology，2008，57（2）：1049-1060.

[4]Kim S，Chung H.On the girth of Tanner（3，5）quasicyclic LDPC codes[J].IEEE Trans on Info Theory，2006， 52（4）：1739-1744.

[5]Wang Yige，D raper S C，Yedidia J S.Hierarchical and high girth QC LDPC codes[J].IEEE Trans on Info Theory，2013，59（7）：4553-4583.

[6]Kang J，F(xiàn)an P，Cao Z.Flexible construction of irregular partitioned LDPC codes with low error floors[J].IEEE Communications Letters，2005，9（6）：534-536.

[7]M yung S，Yang K.Lifting methods for quasi-cyclic LDPC codes[J].IEEE Communications Letters，2006，10（6）：489-491.

[8]Sharon E，Lisyn S.Constructing LDPC codes by error m inim ization progressive edge grow th[J].IEEE Trans on Communications，2008，56（3）：359-368.

[9]彭立，朱光喜.QC-LDPC碼的置換矩陣循環(huán)移位次數(shù)設(shè)計[J].電子學(xué)報，2010，38（4）：786-790.

[10]郭銳，胡方寧，劉濟林.一種低差錯平底線性復(fù)雜度的QC-LDPC碼構(gòu)造方法[J].電路與系統(tǒng)學(xué)報，2011，16（6）：87-93.

[11]韓輝，劉磊，詹磊.一種碼率碼長靈活變化的QC-LDPC碼[J].無線通信技術(shù)，2009，18（4）：1-4.

[12]Xu Y，Wei G.On the construction of quasi-systematic block-circulant LDPC codes[J].IEEE Commun Letters，2007，11（11）：886-888.

[13]Wai M，F(xiàn)rancis C，Chi K.A class of QC-LDPC codes with low encoding complexity and good error performance[J].IEEE Commun Letters，2010，14（2）：169-171.

[14]張民強，李存華.基于可信度信息的改進加權(quán)比特翻轉(zhuǎn)算法[J].計算機工程與應(yīng)用，2012，48（31）：112-114.

[15]佟寧寧，趙旦峰，吳宇平.一種改進的LDPC碼的EBF構(gòu)造算法的研究[J].計算機工程與應(yīng)用，2012，48（23）：32-35.

WANG Hanxin,WANG Fang,SU Kaiyou,ZHU Cuitao

College of Electronics and Information Engineering,South-Central University for Nationalities,Wuhan 430074,China

QC-LDPC codes with slide rectangular window and quasi tri-diagonal structure are proposed, the more flexible code lengths and code rates of QC-LDPC codes are expanded by using slide rectangular window in the base check matrix, the degree distribution is optimized by the optimal diagonal method. The error floors of QC-LDPC codes are lower by using quasi tri-diagonal structure which appropriately selects the location of the third diagonal in the base check matrix to partly eliminate variable nodes of degree-2. Simulation results show the proposed QC-LDPC codes can not only flexibly expandthe code lengths and code rates but also reduce the encoding complexity and improve the BER performance compared to quasi dual-diagonal structure in IEEE 802. 16e QC-LDPC codes, they are available and suitable for the adaptive transmission systems and hardware implementation.

Quasi-Cyclic Low-Density Parity-Check（QC-LDPC）codes; diagonal structure; degree distribution; encoding complexity

WANG Hanxin,WANG Fang,SU Kaiyou,et al.QC-LDPC codes with slide rectangular window and quasi tri-diagonal structure.Computer Engineering and Applications,2014,50（17）：186-190.

A

TP301

10.3778/j.issn.1002-8331.1310-0449

國家自然科學(xué)基金（No.61072075）；中央高?；究蒲袠I(yè)務(wù)費專項資金重點項目（No.CZZ13001）；湖北省自然科學(xué)基金（No.2013CFB448）。

汪漢新（1966—），男，副教授，研究方向：信息與編碼、無線通信技術(shù)。E-mail：w anghx8888@163.com

2013-11-01

2014-02-20

1002-8331（2014）17-0186-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-03-03,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1310-0449.htm l