李萬(wàn)臣，高毓亮，齊 歡

(哈爾濱工程大學(xué)信息與通信工程學(xué)院，哈爾濱150001)

低密度奇偶校驗(yàn)(Low Density Parity Check，LDPC)碼是一種先進(jìn)的具有逼近香農(nóng)限的優(yōu)良性能信道編碼技術(shù).最初由Gallager發(fā)現(xiàn)，經(jīng)過(guò)數(shù)十年的沉寂，LDPC碼被重新重視，Hagenauer在文獻(xiàn)[1]中提出讓校驗(yàn)矩陣通過(guò)刪除不同的子矩陣來(lái)使碼編碼后的碼字得到不同的碼率.這種碼被稱作速率兼容刪除型卷積碼(RCPC).構(gòu)造出的RCPC碼解決了碼率可變的問題，使用刪除來(lái)改變碼率的思路也為后來(lái)糾錯(cuò)碼的發(fā)展提供了一條道路，例如速率1兼容低密度校驗(yàn)碼(RC－LDPC)[2]和速率兼容刪除型turbo碼(RCPT)[3].因?yàn)長(zhǎng)DPC的性能優(yōu)越、形式簡(jiǎn)潔、在實(shí)際應(yīng)用方面具有廣闊的前景，近些年來(lái)其備受關(guān)注，可以應(yīng)用于光纖通信、磁/光全存儲(chǔ)、衛(wèi)星數(shù)字視頻和音頻廣播、圖像壓縮傳輸?shù)?，而且DVB－S2的標(biāo)準(zhǔn)草案中也采用可LDPC碼，我們可以預(yù)想到，LDPC碼及相應(yīng)的速率兼容LDPC碼以其優(yōu)良的性能，也將給以后的無(wú)線移動(dòng)通信事業(yè)帶來(lái)巨大幫助.然而目前對(duì)于速率兼容LDPC碼的研究還很有限，在現(xiàn)有的對(duì)于速率兼容LDPC碼研究中往往也忽略了很多問題，致使LDPC碼的譯碼性能有待進(jìn)一步改善.

1 QC－LDPC和速率兼容LDPC碼

準(zhǔn)循環(huán)低密度奇偶校驗(yàn)碼(Quasi Cyclic Low Density Parity Check Code，QC－LDPC)碼是LDPC碼的一個(gè)重要子類，因?yàn)榫哂袦?zhǔn)循環(huán)形式的校驗(yàn)矩陣，所以QC－LDPC有較低的編解碼復(fù)雜度.又因?yàn)镼C－LDPC碼具有準(zhǔn)循環(huán)形式生成矩陣，所以我們可以使用移位寄存器來(lái)進(jìn)行編碼.但是QCLDPC碼中短環(huán)是不可避免的.所以在構(gòu)造校驗(yàn)矩陣時(shí)，能否使矩陣中的環(huán)合理分布且使girth值盡量增大對(duì)于碼字性能有很大的影響.

QC－LDPC需要較小的存儲(chǔ)空間并且有效降低了編解碼復(fù)雜度，因而對(duì)LDPC碼的發(fā)展具有重要意義.目前，林舒的研究小組QC－LDPC碼領(lǐng)域的深入研究中在利用有限幾何法，在對(duì)一般QCLDPC碼的復(fù)雜度及編碼方法進(jìn)行了全面分析的同時(shí)又構(gòu)造了眾多碼字[4]，引入了行列分解技術(shù)[5]，并且有二階域又有高階域碼字[6];Zhang小組和Vasic小組為了使得QC－LDPC碼中的最短環(huán)長(zhǎng)girth較大[7]都采用均衡不完全區(qū)組設(shè)計(jì)(Balanced Incomplete Block Design，BIBD)來(lái)對(duì)碼字進(jìn)行構(gòu)造.

RC－LDPC碼是Narayanan[8]首次提出的概念，為了滿足不同碼率的要求，在HARQ系統(tǒng)中，一般使用隨機(jī)刪除[9]方法來(lái)獲得RC－LDPC碼的刪除矩陣，這種方法的實(shí)質(zhì)是隨機(jī)選擇刪除的比特位置從而獲得高速率的LDPC碼.但是這種方法的缺點(diǎn)是在譯碼端需要知道刪除矩陣的位置，這就需要把這些刪除矩陣的位置發(fā)送給接收端，從而造成系統(tǒng)資源的浪費(fèi).在文獻(xiàn)[10]中主要介紹了用擴(kuò)展和刪除矩陣結(jié)合來(lái)構(gòu)造RC－LDPC的方法，在文獻(xiàn)[11]中主要介紹了使用順序刪除的方法來(lái)構(gòu)造RC－LDPC碼.這些構(gòu)造方法因?yàn)槭褂昧私Y(jié)構(gòu)確定的RC－LDPC碼.省去了額外開銷(刪除矩陣的傳輸)，便于硬件的實(shí)現(xiàn)，具有實(shí)際應(yīng)用意義.

2 一種基于樹結(jié)構(gòu)展開的Tanner圖短環(huán)計(jì)數(shù)算法

LDPC碼的校驗(yàn)矩陣H具有稀疏的特性.并且對(duì)應(yīng)于每一個(gè)校驗(yàn)矩陣H都有惟一的一個(gè)雙向圖(或稱Tanner圖(圖1)[12].Tanner圖是一種雙向圖)與其一一對(duì)應(yīng).在Tanner圖中VB=(b1，b2…，bn)稱為變量節(jié)點(diǎn)，其對(duì)應(yīng)的是校驗(yàn)矩陣的列，Vc=(c1，c2，…，cn)是Tanner圖的校驗(yàn)節(jié)點(diǎn)，其對(duì)應(yīng)LDPC碼校驗(yàn)矩陣的行.Tanner圖中的環(huán)是指從某點(diǎn)出發(fā)又回到這一點(diǎn)為一個(gè)閉合回路，環(huán)長(zhǎng)是指著這個(gè)閉合回路中的邊的個(gè)數(shù)，在這個(gè)校驗(yàn)矩陣中最短環(huán)的值稱為此矩陣的girth.

圖1 Tanner圖

在Tanner圖中將某一變量節(jié)點(diǎn)按樹結(jié)構(gòu)展開，變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)依次分層排列.當(dāng)在Tanner圖中展開層中某一變量節(jié)點(diǎn)或者檢驗(yàn)節(jié)點(diǎn)出現(xiàn)的次數(shù)大于等于兩次時(shí)那么就構(gòu)成了環(huán).如圖2所示.

圖2 樹形結(jié)構(gòu)中的短環(huán)

展開層第三層的變量節(jié)點(diǎn)v5出現(xiàn)的次數(shù)大于兩次，那么我們可以看出v1，c2，v5，c2構(gòu)成了一條閉合回路.環(huán)長(zhǎng)為4.如果一個(gè)從變量節(jié)點(diǎn)展開的環(huán)長(zhǎng)度為2k，其中一個(gè)分支的長(zhǎng)度為2k－m，那么我們只需把另一個(gè)支路展開到m層這個(gè)環(huán)就可以形成.為了使展開層數(shù)最少，我們令m=k，也即把兩個(gè)分支都展至第k層.所以，在Tanner圖中我們只需要把變量節(jié)點(diǎn)展開到第k層就可以對(duì)長(zhǎng)度為2k的短環(huán)進(jìn)行計(jì)數(shù).對(duì)所展開到的第k層上的相同節(jié)點(diǎn)兩個(gè)為一組的進(jìn)行環(huán)的統(tǒng)計(jì).為了防止重復(fù)展開，在對(duì)某一節(jié)點(diǎn)展開時(shí)，該節(jié)點(diǎn)的父節(jié)點(diǎn)不出現(xiàn)在其子節(jié)點(diǎn)中.

假設(shè)v1，v2，…，vn是Tanner圖G的n個(gè)變量節(jié)點(diǎn)，我們使用C2K(G)表示在Tanner圖G中長(zhǎng)度為2k的環(huán)的個(gè)數(shù)，節(jié)點(diǎn)展開支第k層時(shí)能夠構(gòu)成環(huán)的總數(shù)，也即相同節(jié)點(diǎn)之間兩兩組合在一起的數(shù)目記為C2k(vi).我們把Tanner圖G以變量節(jié)點(diǎn)vi(1≤i≤n)為根節(jié)點(diǎn)展開到第k，假設(shè)在第k層上出現(xiàn)了m個(gè)不同的節(jié)點(diǎn)，它們出現(xiàn)的次數(shù)分別是t1，t2…，tmi，那么將Tanner圖G按樹形結(jié)構(gòu)依次展開到第k層后，所得到的環(huán)長(zhǎng)為2k的環(huán)的總個(gè)數(shù)為

3 速率兼容LTE－QC－LDPC碼的構(gòu)造

由于LDPC一般采用置信傳播BP算法，如果有短環(huán)存在會(huì)影信息傳播的獨(dú)立性，使譯碼反復(fù)迭代，譯碼的收斂速度變慢從而影響譯碼性能.而在QC－LDPC碼中短環(huán)的存在是不可避免的[13].要想構(gòu)造出性能優(yōu)良的LDPC碼，必須考慮短環(huán)的問題.在傳統(tǒng)RA碼中串行輸出是其很大的一個(gè)缺點(diǎn)，這影響了碼字的吞吐量，從而影響碼字的性能，為了克服串行輸出這一缺點(diǎn)出現(xiàn)了基于單次擴(kuò)展的可以并行輸出的重復(fù)累積碼，這種方法其實(shí)就是QC－LDPC碼與RA碼的結(jié)合，其校驗(yàn)矩陣H具有如式(1)所示的形式這種結(jié)構(gòu)可以實(shí)現(xiàn)校驗(yàn)比特的并行計(jì)算，數(shù)據(jù)吞吐量得到大幅度提高.

式(2)中0表示單位矩陣，－1表示全零矩陣.hij為置換矩陣.

式(2)所示矩陣具有稀疏特性并且包含有準(zhǔn)循環(huán)結(jié)構(gòu)，所以它是QC－LDPC的一種.雖然這種RA碼具有良好性能，但是其左半部分并不是完全下三角結(jié)構(gòu)，這就使得它無(wú)法進(jìn)行線性時(shí)間編碼.從而導(dǎo)致了在構(gòu)造速率兼容碼時(shí)，這種RA碼無(wú)法進(jìn)行結(jié)構(gòu)擴(kuò)展.

本文在IEEE 802.16e[14]國(guó)際標(biāo)準(zhǔn)的基礎(chǔ)上將其中的一列刪除，在最右側(cè)補(bǔ)上一列，即得到與原結(jié)構(gòu)相比基本沒有性能損失的、并且具有完全下三角形式的矩陣，即可線性時(shí)間編碼的母碼.其結(jié)構(gòu)如式(3)所示.這種形式的矩陣通過(guò)順序增加或者刪除其中的行和列很容易的就可以得到信道所需要的碼率實(shí)現(xiàn)速率兼容[15]，再用生成樹的方法尋找其中的短環(huán)，刪除部分六環(huán)，構(gòu)造了一種優(yōu)化六環(huán)的LTE－QC－LDPC碼，很好提高了碼字的譯碼性能.

將上文所示的結(jié)構(gòu)展成具體的矩陣如表1所示，碼率為1/2，分塊校驗(yàn)矩陣大小為12×24，子塊是擴(kuò)展因子為48的48×48的方陣.數(shù)字代表循環(huán)移位的次數(shù)，具體的校驗(yàn)矩陣在表1中給出.對(duì)其進(jìn)行短環(huán)檢測(cè)并且去除一部分六環(huán)，以至于不刪除太多信息節(jié)點(diǎn).

表1校驗(yàn)矩陣

4 實(shí)驗(yàn)仿真與分析

為驗(yàn)證本文優(yōu)化方法的有效性和先進(jìn)性，這里執(zhí)行了一系列仿真實(shí)驗(yàn).所有仿真實(shí)驗(yàn)均在Intel Pentium(R)CPU 2.20GHz、2G內(nèi)存的計(jì)算機(jī)上進(jìn)行，編程環(huán)境為Matlab7.1.表1為應(yīng)用樹形結(jié)構(gòu)短環(huán)檢測(cè)表1所得到四環(huán)、六環(huán)和八環(huán)的個(gè)數(shù).

表1 檢測(cè)矩陣中各長(zhǎng)度環(huán)的個(gè)數(shù)

由于短環(huán)對(duì)采用置信傳播BP算法影響較大，使譯碼重復(fù)迭代，譯碼的收斂速度變慢，本文重點(diǎn)對(duì)長(zhǎng)度為六的短環(huán)進(jìn)行處理.又由于六環(huán)點(diǎn)數(shù)太多，全部去除會(huì)帶來(lái)較大的信息損失，所以本文主要去掉形狀如圖3所示的六環(huán)進(jìn)行刪除.

圖3 六環(huán)結(jié)構(gòu)

在AWGN信道下使用BP譯碼算法對(duì)上述幾種碼字進(jìn)行性能仿真.圖4是未去六環(huán)TE－QCLDPC碼與802.16e中規(guī)定的RA碼的誤碼性能比較圖.從圖4中可以看出沒有經(jīng)過(guò)六環(huán)處理的LTE－QC－LDPC碼在誤碼性能上沒有比802.16e中規(guī)定的RA碼優(yōu)越.兩個(gè)誤碼性能相差很小.

圖4 未去六環(huán)的LTE-QC-LDPC碼和802.16eRA碼誤碼率性能對(duì)比

從仿真結(jié)果可以看出，因?yàn)槿コ瞬糠至h(huán)，使得誤碼性能曲線收斂速度加快，在誤碼率在時(shí)大約提高了0.12 dB.在誤碼率為10時(shí)，大約提高了0.16 dB，由此可見，經(jīng)過(guò)六環(huán)優(yōu)化LTE－QC－LDPC碼性能比未經(jīng)六環(huán)優(yōu)化的LTE－QC－LDPC碼和802.16e中規(guī)定的RA碼有明顯提高，這證明去六環(huán)的LTE－QC－LDPC碼是一種性能優(yōu)良的好碼.

圖5 誤碼性能對(duì)比仿真圖

5 結(jié)語(yǔ)

針對(duì)現(xiàn)有的LTE－QC結(jié)構(gòu)的LDPC碼中存在大量的短環(huán)影響譯碼性能的問題，本文使用了生成樹的方法對(duì)校驗(yàn)矩陣進(jìn)行了短環(huán)檢測(cè)，并在盡量減少對(duì)原始信息丟失的前提下，對(duì)其中一種形狀的六環(huán)進(jìn)行刪除，得到了經(jīng)過(guò)六環(huán)優(yōu)化后的校驗(yàn)矩陣，仿真結(jié)果表明，所得到的校驗(yàn)矩陣在誤碼性能方面跟802.16e中規(guī)定的RA碼誤碼率性能比較時(shí)，性能有所提高，說(shuō)明經(jīng)過(guò)六環(huán)優(yōu)化后的碼字是一種一種性能優(yōu)良的好碼.

[1]HAGENAUER J.Rate－compatible punctured convolutional codes(RCPC codes)and their applications[J].IEEE Trans.on Communications，1988，36(4):389－400.

[2]LIJ，NARAYANA K.Rate－compatible low density parity check codes for capacity approaching ARQ scheme in packet data communications[C]//IEEE CIIT，US Virgin Islands，2002:201－206.

[3]ROWITCH N，MILSTEIN L B.On the performance of hybrid FEC/ARQ systems using rate compatible punctured turbo(RCPT)codes[J].IEEE Trans.on Communications，2000，48(6):948－959.

[4]Z.L，L.CHEN.Efficient Encoding of Quasi－Cyclic Low－Density Parity－Check Codes[C]//IEEE Trans.Communications，[S.l.]:[s.n.]，2006，54(2):71－81.

[5]JUN X，LEI C.Construction of Regular and Irregular LDPC Codes:Geometry Decomposition and Masking[J].IEEE Trans.Information Theory，2007，53(3):121－134.

[6]LING Q Z，LAN L.Construction of Nonbinary Cyclic，Quasi－Cyclic and Regular LDPC Codes:A Finite Geometry Approach[C]//IEEE Trans.Communications，[S.l.]:[s.n.]，2008，56:378－387.

[7]VASIC B，MILENKOVICO.Combinatorial Constructions of Low－Density Parity－Check Codes for Iterative Decoding[J].IEEE Trans.Information Theory，2004，50(6):1156－1176.

[8]RICHARDSON T，URBANKE R.The capacity of low－density Parity－check codes under message－passing Decoding[J].IEEE Transactions on information Theory，2001(2):599－618.

[9]王繼康，周荷琴.刪余低密度奇偶校驗(yàn)碼的分析與設(shè)計(jì)[J].電子與信息學(xué)報(bào)，2007，29(9):2149－2153.

[10]YAZDANIM，BANILHASHWMIA.On construction of ratecompatible low－density parity－check codes[C]//IEEE Comm.Letters，[S.l.]:[s.n.]，2004，8(3):159－161.

[11]袁東風(fēng)，張海剛.LDPC碼理論與應(yīng)用[M].北京:人民郵電出版社，2008:64－66.

[12]TANNER R M.a recursive approach to Low Complexity Codes[J].IEEE Transactions On information Theory，1981，27:533－547.

[13]KYEONGCHEOL Y.Quasi－Cyclic LDPC Codes for Fast Encoding[J].IEEE Transactions on information theory，2005，51(8):167－179.

[14]RASHIDPOUR，JAMALI S H.Low－density parity－check codes with simple irregular semi－random parity－check matrix finite－length applications[C]//14th IEEE Proceedings on Personal，Indoor and Mobile Radio Communications，[S.l.]:[s.n.]，2003:439－443.

[15]李 煒，趙旦峰，錢晉希.MSK系統(tǒng)中迭代相位同步補(bǔ)償方法[J].哈爾濱商業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2011，27(4):602－604，608.