一種新的LDPC碼編碼方法

王 健，劉紹華，楊仕平

(廣州海格通信集團股份有限公司，廣東廣州510663)

0 引言

LDPC［1］是目前信息領(lǐng)域和通信界最熱門的研究之一，也是現(xiàn)代編碼理論的典型代表。LDPC是一種線性分組碼，其校驗矩陣只含有很少量的1，其余元素均為0，即其校驗矩陣H是稀疏矩陣。LDPC碼的設(shè)計以校驗矩陣H的設(shè)計為核心考慮之一。應(yīng)用時需要先設(shè)計校驗矩陣H，再進行后續(xù)的編碼。校驗矩陣H對應(yīng)的Tanner圖中的環(huán)也稱為H的環(huán)。研究表明，好的LDPC碼應(yīng)避免校驗矩陣中含有短環(huán)，尤其應(yīng)該避免存在長度為4的環(huán)。

LDPC碼的編碼方法有2類:隨機化方法和結(jié)構(gòu)化方法。隨機化方法性能很好，但實現(xiàn)復(fù)雜度較高，常用的有pi旋轉(zhuǎn)方法［2］等;結(jié)構(gòu)化方法性能相對于隨機化方法會有損失，但實現(xiàn)相對容易，最常用的是準循環(huán)方法［3－5］(QC 方法)。除此之外，還有有限幾何碼［6］(EG和 PG)等。其中 IEEE 802．16e、DVB-S2等標準中的LDPC碼編碼的方法均采用了QC方法［7－12］。該方法是把索引矩陣中每個元素擴展成循環(huán)移位矩陣來構(gòu)造校驗矩陣，其缺點在于對索引矩陣敏感，索引矩陣必須精心設(shè)計，且階數(shù)通常比較大，否則性能會很差，所以設(shè)計起來比較困難。同時，引入雙對角子矩陣迭代編碼時，性能不佳，一般需引入準雙對角矩陣。與雙對角結(jié)構(gòu)相比，準雙對角結(jié)構(gòu)的編碼復(fù)雜度較高。因此，研究一種容易設(shè)計且編碼復(fù)雜度低、存儲空間小、性能佳的LDPC編碼方法具有很大的應(yīng)用價值。本文提出的LDPC碼的模循環(huán)方法編碼性能好，計算復(fù)雜度低，存儲空間小，而且很容易設(shè)計，能夠較廣泛地在實際中應(yīng)用。

1 方法論述

本文提出的模循環(huán)方法分2類討論:① 需要對素數(shù)求模運算，稱之為“素數(shù)模循環(huán)方法”;② 是對第1類的改進，不需要對素數(shù)求模，只需對2的冪次求模，稱之為“2冪模循環(huán)方法”。下面先后討論2種方法。

1．1 素數(shù)模循環(huán)方法

設(shè)q+1是素數(shù)，碼長N=qk，碼率 R=(kj)/k。下面構(gòu)造行重為k，列重為j的規(guī)則校驗矩陣H。首先設(shè)計索引矩陣A為:

按上述索引矩陣，把索引矩陣A中的每個數(shù)字axy擴展成為q階(0，1)方陣 Eaxy，每個 Eaxy在位置(i，iaxy(modq+1))，i=1，2，3，．．．q 處的元素均是1，其余位置的元素均是0。然后構(gòu)造校驗矩陣H如下:

由于 q+1 是素數(shù)，所以 (axy，2axy，3axy，．．．，qaxy)mod(q+1)是(1，2，3，……，q)的排列，從而Eaxy每行每列均只有1個1，即單位置換陣。這樣一來，便保證了校驗矩陣H是行重為k，列重為j的規(guī)則校驗陣。

下面討論如何設(shè)計索引矩陣可以保證校驗矩陣中無四環(huán)以及六環(huán)。主要體現(xiàn)為下述的定理1和定理2。在設(shè)計索引矩陣時，要滿足定理1的條件，從而使得校驗矩陣無四環(huán);定理2的條件盡可能滿足，使得校驗矩陣無六環(huán)。通常情況下，索引矩陣階數(shù)較小時，隨機產(chǎn)生的索引矩陣滿足定理1的條件的概率很大，滿足定理2的條件的概率較前者小，但只需要適當調(diào)整索引矩陣，便可滿足定理2的條件。

定理1:模循環(huán)方法校驗矩陣H中無四環(huán)的充要條件是:在索引矩陣 A 中，任何 i，j，s，t，有 aisajtajsait≠0(modq+1)。

下面的定理給出了校驗矩陣中無六環(huán)的充要條件。

定理2:校驗矩陣H中無六環(huán)的充要條件是:在索引矩陣 A 中，任何的下標 i，j，k，s，t，p，有asiatjapk－askatiapj≠0(modq+1)。

為了方便索引矩陣的設(shè)計，接下來給出一類特殊的索引矩陣，本文稱之為正交和索引矩陣。

設(shè) b=(b1，b2，．．．，bk)，c=(c1，c2，．．．，cj)。令索引矩陣 A=(axy)j×k中，axy=bx+cy。即

稱這類索引矩陣為正交和索引矩陣。下面的定理3給出了如何設(shè)計正交和索引矩陣可以使得校驗矩陣無四環(huán)，這個條件使用起來非常方便，所以在實際應(yīng)用中可優(yōu)先考慮使用正交和模版。

定理 3:若 b=(b1，b2，．．．，bk)，c=(c1，c2，．．．，cj)滿足對任何的s，t，有 bs－ bt≠0(modq+1)，及cs－ct≠0(modq+1)，則正交和索引矩陣A對應(yīng)的校驗矩陣H無四環(huán)。

接下來給出應(yīng)用素數(shù)模循環(huán)方法構(gòu)造校驗矩陣H的流程。

設(shè)q+1是素數(shù)，碼長N=qk，碼率R=(k－j)/k，目標是構(gòu)造行重為k，列重為 j的規(guī)則校驗矩陣H。

首先，設(shè)計j行 k列的索引矩陣A，須滿足定理1的條件(若采用正交和索引矩陣，則須滿足定理3的條件)，定理2的條件盡量滿足;把索引矩陣A中的每個元素按素數(shù)模循環(huán)方法擴展成為q階子方陣;由jk個子方陣構(gòu)造校驗矩陣H。

1．2 2冪模循環(huán)方法

在素數(shù)模循環(huán)方法中，需要對素數(shù)求模運算，這樣實現(xiàn)起來相對困難，2冪模循環(huán)方法作為對素數(shù)模循環(huán)方法的繼承和改進，克服了這一缺點，只需計算加法，乘法以及對2的冪次求模，實現(xiàn)起來相對容易。下面給出2冪模循環(huán)方法的描述。

設(shè)E為2m×2m的單位陣，a是一個奇數(shù)，定義E(a)如下:

令 g(i，a)≡ (2i－ 1)a(mod2m+1)，E(a)中第 i行的1的位置(縱坐標)是(g(i，a)+1)/2，即E(a)中的1的位置為(i，(g(i，a)+1)/2)。可以證明E(a)是單位置換陣。

設(shè)碼長N=k2m，碼率R=(k－j)/k。下面構(gòu)造行重為k，列重為j的規(guī)則校驗矩陣H。首先設(shè)計索引矩陣A為:

可以證明定理1對于上述的構(gòu)造方法仍然是成立的。對于正交和索引矩陣，只要令 b=(b1，b2，．．．，bk)，c=(c1，c2，．．．，cj)中 bi全是奇數(shù)，ci全是偶數(shù)(或者中bi全是偶數(shù)，ci全是奇數(shù))，于是得到全是奇數(shù)的索引矩陣，且定理3對應(yīng)于下述的定理4，即滿足條件的正交和索引矩陣對應(yīng)的校驗陣無四環(huán)。

定理4:對于2 冪模循環(huán)方法，若 b=(b1，b2，．．．，bk)，c=(c1，c2，．．．，cj)滿足對任何的 i，j，s，t，則有:(bi－bj)(cs－ct)≠0(mod2m+1)。

則正交和索引矩陣A對應(yīng)的校驗矩陣H無四環(huán)。

接下來給出應(yīng)用2冪模循環(huán)方法構(gòu)造校驗矩陣H的流程。

設(shè)碼長N=k2m，碼率 R=(k－j)/k，目標是構(gòu)造行重為k，列重為j的規(guī)則校驗矩陣H。

首先，設(shè)計j行k列的索引矩陣A(要求A種元素全是奇數(shù))，須滿足定理1的條件(若采用正交和索引矩陣，則須滿足定理4的條件)，定理2的條件盡量滿足。接著，把索引矩陣 A中的每個元素按2冪模循環(huán)方法擴展成為2m階子方陣。最后，由jk個子方陣構(gòu)造校驗矩陣H。

2 可快速編碼的模循環(huán)方法

在模循環(huán)方法的實際應(yīng)用中，可采用雙對角結(jié)構(gòu)進行編碼，雙對角結(jié)構(gòu)的引入可降低計算復(fù)雜度，加快編碼速度。研究表明，雙對角結(jié)構(gòu)的引入通常會損傷碼的性能，對QC方法而言，雙對角結(jié)構(gòu)的確會對其性能造成較大影響。仿真表明，雙對角結(jié)構(gòu)對本文提出的模循環(huán)方法影響不大，模循環(huán)方法采用雙對角結(jié)構(gòu)仍然性能優(yōu)異。下面是引入雙對角結(jié)構(gòu)的模循環(huán)方法的描述。校驗矩陣的結(jié)構(gòu)為:

式中，

對于矩陣Hp，采用本文的素數(shù)模循環(huán)方法或2冪模循環(huán)方法生成即可。在下面給出的仿真中，本文的方法采用的便是雙對角結(jié)構(gòu)。

本文提出的模循環(huán)方法的索引矩陣通常只需要很小的階數(shù)，設(shè)計起來非常容易，而且模循環(huán)方法對于索引矩陣不敏感，甚至隨機的產(chǎn)生索引矩陣都能達到很好的性能;而IEEE 802．16e標準中使用的準循環(huán)方法，通常需要設(shè)計較大的索引矩陣，且對索引矩陣較敏感，需要精心設(shè)計索引矩陣，否則性能不好，所以設(shè)計起來比較困難。

對于計算復(fù)雜度而言，考慮常用的1/2碼率的情形，設(shè)碼長為n，本文的2冪模循環(huán)方法采用雙對角結(jié)構(gòu)時，乘法的計算次數(shù)為2n次，加法計算次數(shù)是2．5n次，對2的冪次求模可直接移位實現(xiàn)。且模循環(huán)方法只需設(shè)計并儲存4×4的索引矩陣。IEEE 802.16e標準中采用的準循環(huán)LDPC碼，編碼時乘法次數(shù)約為11．6n次，加法次數(shù)約為10．6n次，需要設(shè)計并儲存12×24的矩陣。所以本文的方法計算復(fù)雜度較低，存儲量較小。

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

下面的仿真條件均為碼長2 048(其中IEEE 802.16e標準的碼長是2 016)，碼率1/2，采用BPSK調(diào)制以及歸一化BP譯碼算法，歸一化因子為0．8，加入白噪聲信道。

本文的2冪模循環(huán)方法和pi旋轉(zhuǎn)編碼均引入雙對角結(jié)構(gòu)，即校驗矩陣H=［HpHd］，Hd是雙對角矩陣。pi旋轉(zhuǎn)編碼Hp由隨機置換陣旋轉(zhuǎn)而得，屬于半隨機方法。本方法中Hp則由如下索引矩陣A生成:

各種LDPC碼編碼方法的性能比較如圖1所示，本文的2冪模循環(huán)方法與IEEE 802．16e標準相比性能接近，但本方法只需計算乘法4 096次，加法5 120次，而 IEEE 802．16e標準需計算乘法約23 340次，加法約21 370次，所以本文方法的計算復(fù)雜度低得多。

圖1 各種LDPC碼編碼方法的性能比較

與其他方法相比，本文方法性能均占優(yōu)。在10－5量級，本文方法可以比pi旋轉(zhuǎn)方法性能好約0.1 dB，比PG和OOC方法好約0.3 dB，比EG方法好約0.7dB，且本方法存儲空間小，編碼復(fù)雜度低，較為實用。

上述仿真中本文的2冪模循環(huán)方法所設(shè)計的LDPC碼的校驗矩陣無四環(huán)和六環(huán)，使得迭代譯碼時信息交換充分，且校驗矩陣構(gòu)造方法極大的降低了校驗矩陣各行的相關(guān)性，從而使得性能較好。

4 結(jié)束語

提出了一類新的LDPC碼的編碼方法——模循環(huán)方法，并給出了2類模循環(huán)方法:① 素數(shù)模循環(huán)方法;②2冪模循環(huán)方法。其中2冪模循環(huán)方法實現(xiàn)起來更加簡單。提出的模循環(huán)方法簡化了設(shè)計流程，在實際的工程實現(xiàn)當中，能夠在保持良好性能的同時，可以大大降低計算復(fù)雜度，并且占用的存儲量較小，比較實用。

［1］ GALLAGER R G．Low-density Parity check Codes［M］．MA:MIT Press，1963．

［2］ 張忠培，史治平，王傳丹．現(xiàn)代編碼理論與應(yīng)用［M］．北京:國防工業(yè)出版社，2007．

［3］ MAC P C．Quasi-cyclic Low-density Parity-check Codes From Circulant Permutation Matrices［J］．IEEE Transactions on Information Theory，2004，50(8):1 788－1 792．

［4］ 肖 揚，徐 丹．準循環(huán)LDPC好碼設(shè)計［J］．系統(tǒng)工程與電子技術(shù)，2009，31(5):1 011－1 016．

［5］ MYUNG S，YANG K C，KIM J．Quasi-cyclic LDPC Codes for Fast Encoding［J］．IEEE Transactions on Information Theory，2005，51(8):2 894－2 901．

［6］ KOU Y，LIN S，F(xiàn)OSSORIER M．Low Density Parity Check Codes Based on Finite Geometries:A Rediscovery and New Results［J］．IEEE Transactions Information Theory，2001，47(10):2 711－2 736．

［7］ 肖 揚．Turbo與LDPC編解碼及其應(yīng)用［M］．北京:人民郵電出版社，2010．

［8］ IEEE P802．16e/D8．IEEE Standard for Local and Metropolitan area networks Part 16:Air Interface for Fixed and Mobile Broadband Wireless Access Systems［S］，2005．

［9］ DVB-S2．Standard Draft ETSI EN 302 307 V1．1．1［S］，2004．

［10］ XIAO Y，KIM K．Good Encodable Irregular Quasi-cyclic LDPC Codes［C］ ∥11th IEEE Singapore International Conference on Communication Systems(ICCS 2008)，2008:1 291－1 296．

［11］ CCSDS131．1．1 － 0 － 2．Low Density Parity Check Codes for Use in Near-earth and Deep Space Applications［S］，2007．

［12］GB20600．數(shù)字電視地面廣播標準［S］，2006．