一種快速編碼的半隨機(jī)LDPC碼構(gòu)造研究

陳超然等

摘 要： 低密度奇偶校驗(yàn)碼（LDPC碼）具有逼近Shannon限的優(yōu)異糾錯(cuò)性能，在信道編碼領(lǐng)域的應(yīng)用越來越廣泛，但是LDPC碼的編碼復(fù)雜性一直是制約其普遍應(yīng)用的突出問題。奇偶校驗(yàn)矩陣的結(jié)構(gòu)則直接決定著LDPC碼的編碼復(fù)雜度和譯碼性能。提出一種準(zhǔn)雙對(duì)角線結(jié)構(gòu)的半隨機(jī)LDPC碼奇偶校驗(yàn)矩陣的構(gòu)造方法，它具有IEEE 802.16e標(biāo)準(zhǔn)LDPC碼的優(yōu)異糾錯(cuò)性能和低編碼復(fù)雜度，同時(shí)在碼率、碼長、基礎(chǔ)校驗(yàn)矩陣和擴(kuò)展因子等設(shè)計(jì)方面更具靈活性，能更好地適應(yīng)工程實(shí)踐的需要。采用這種構(gòu)造方法，以（16 384，8 192）LDPC碼為例進(jìn)行快速迭代編碼，能夠獲得優(yōu)異的譯碼性能，可以用于實(shí)現(xiàn)高速率低復(fù)雜度的LDPC譯碼器設(shè)計(jì)。

關(guān)鍵詞： 低密度奇偶校驗(yàn)碼； 半隨機(jī)； 準(zhǔn)雙對(duì)角線； 快速編碼算法

中圖分類號(hào)： TN911.22?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）11?0034?04

Research on semi?random LDPC code structure for fast encoding

CHEN Chao?ran， ZHENG Lin?hua， XIANG Liang?jun， LI Hua

（College of Electronic Science and Engineering， National University of Defense Technology， Changsha 410073， China）

Abstract： Low density parity check （LDPC） code has excellent error correction performance which approaches to Shannon limits， and widely applied in the field of channel encoding. However， the encoding complexity of the LDPC code is the prominent problem which restricts its universal applications. The encoding complexity and decoding performance of LDPC code are determined by the parity check matrix structure directly. The construction method of semi?random LDPC code parity check matrix based on quasi dual?diagonal structure is proposed. It has excellent error correction performance and low encoding complexity of LDPC code fitting with IEEE 802.16e standard， more flexibility design in code rate， code length， basis check matrix， extended factor and so on， and better satisfies the demands of engineering practice. Taking （16384， 8192） LDPC code as an example to proceed fast iterative encoding， the excellent decoding performance is obtained with the proposed construction method. It can be used to realize LDPC decoders design of high speed and low complexity.

Keywords： low density parity check code； semi?random； quasi dual?diagonal； fast encoding algorithm

0 引 言

低密度奇偶校驗(yàn)碼（Low Density Parity Check Code，LDPC）是用稀疏校驗(yàn)矩陣或Tanner圖定義的線性分組碼。作為一種信道編碼技術(shù)，其性能優(yōu)異，構(gòu)造靈活，描述簡單，易于理論分析，是迄今為止最接近Shannon限的好碼。1962年，R.Gallager博士在他的論文中最先提出了LDPC碼，但是受限于當(dāng)時(shí)計(jì)算機(jī)處理能力和研究條件，沒能引起足夠關(guān)注。直到20世紀(jì)90年代中期，對(duì)LDPC碼理論的研究才開始復(fù)興，隨著超大規(guī)模集成電路的發(fā)展，LDPC碼的硬件實(shí)現(xiàn)逐漸成為現(xiàn)實(shí)。LDPC碼被公認(rèn)為未來通信系統(tǒng)中最重要的糾錯(cuò)編碼。

但是，LDPC碼編碼復(fù)雜度高的不利因素一直制約著它的普遍應(yīng)用。如何尋找低復(fù)雜度的編碼方法，減少對(duì)硬件存儲(chǔ)空間的需求，一直是LDPC碼應(yīng)用研究的重要問題。隨著學(xué)者們對(duì)LDPC碼結(jié)構(gòu)化構(gòu)造方法的深入研究，其編碼復(fù)雜度和所需的存儲(chǔ)空間都有了大幅的降低。如IEEE 802.16e標(biāo)準(zhǔn)和DVB?S2標(biāo)準(zhǔn)的LDPC碼通過在構(gòu)造校驗(yàn)矩陣時(shí)引入特定的編碼結(jié)構(gòu)以此降低編碼的復(fù)雜度。只要引入的特定結(jié)構(gòu)中無四環(huán)或無低碼重碼，就不會(huì)影響碼的性能。IEEE 802.16e標(biāo)準(zhǔn)的LDPC碼是一種準(zhǔn)循環(huán)LDPC碼，可用[12，][23，][34]和[56]四種碼速率，實(shí)現(xiàn)碼長范圍為576～230 4 b、間隔步長為96 b的編碼方案。其每一種碼速率都對(duì)應(yīng)不同的編碼矩陣，記為基礎(chǔ)校驗(yàn)矩陣[Hb，]尺寸為[mb×nb。]其中，[nb]都為24，[mb]并不相同。奇偶校驗(yàn)矩陣[H]由基礎(chǔ)校驗(yàn)矩陣[Hb]擴(kuò)展而成。與一般準(zhǔn)循環(huán)構(gòu)造方法不同，IEEE 802.16e標(biāo)準(zhǔn)LDPC碼的奇偶校驗(yàn)矩陣右半部分具有準(zhǔn)雙對(duì)角線的結(jié)構(gòu)，編碼復(fù)雜度更低。DVB?S2標(biāo)準(zhǔn)的LDPC碼則采用簡單的雙對(duì)角線子矩陣實(shí)現(xiàn)迭代編碼。由于雙對(duì)角線子矩陣結(jié)構(gòu)可能會(huì)產(chǎn)生低重碼字，將帶來一定的誤碼率損傷，而采用準(zhǔn)雙對(duì)角線結(jié)構(gòu)則會(huì)避免出現(xiàn)這種情況，譯碼性能更加優(yōu)異。

本文提出一種采用準(zhǔn)雙對(duì)角線結(jié)構(gòu)來構(gòu)造半隨機(jī)LDPC碼奇偶校驗(yàn)矩陣的方法，在IEEE 802.16e標(biāo)準(zhǔn)LDPC碼的基礎(chǔ)上，對(duì)基礎(chǔ)矩陣[Hb]和擴(kuò)展因子[z]的大小不作任何具體限制，可以更加靈活地實(shí)現(xiàn)不同碼率和碼長組合的編碼設(shè)計(jì)。采用這種方法構(gòu)造出的是一種混合結(jié)構(gòu)的奇偶校驗(yàn)矩陣，矩陣的左半部分是隨機(jī)構(gòu)造的基礎(chǔ)矩陣，能夠確保編碼的優(yōu)異性能；矩陣右半部分采用準(zhǔn)雙對(duì)角線結(jié)構(gòu)，確保了編碼的低復(fù)雜度。這種構(gòu)造方法面向快速迭代編碼，可以不經(jīng)高斯消元由校驗(yàn)矩陣[H]直接編碼，在大碼長高速率的情況下具有更好的譯碼性能。本文以（16 384，8 192）LDPC碼為例進(jìn)行驗(yàn)證，并給出快速編碼算法，以期在LDPC譯碼器設(shè)計(jì)中實(shí)現(xiàn)低復(fù)雜度和高速率。

1 準(zhǔn)雙對(duì)角線結(jié)構(gòu)校驗(yàn)矩陣的構(gòu)造方法

定義LDPC碼的奇偶校驗(yàn)矩陣[H]大小為[m×n]，信息比特長度[k=n-m。]定義基礎(chǔ)校驗(yàn)矩陣[Hb]大小為[mb×nb，][Hb]中的元素對(duì)應(yīng)于[H]的子矩陣[P，]則[H]可以表示為：

[H=P0，0P0，1P0，2???P0，nb-2P0，nb-1P1，0P1，1P1，2???P1，nb-2P1，nb-1P2，0P2，1P2，2???P2，nb-2P2，nb-1??????Pmb-1，0Pmb-1，1Pmb-1，2???Pmb-1，nb-2Pmb-1，nb-1]

式中：[Pi，j]是一個(gè)[z×z]大小的循環(huán)單位矩陣，或是一個(gè)[z×z]大小的全零矩陣。[Hb]中的元素?cái)U(kuò)展后得到[H。]此處，[n=nb×z，][m=mb×z，][z]表示擴(kuò)展因子。擴(kuò)展時(shí)，將[Hb]中的“1”用一個(gè)[z×z]大小的循環(huán)單位矩陣[Pi，j]替換，將[Hb]中的“0”用一個(gè)[z×z]大小的全零矩陣[Pi，j]替換。

通常循環(huán)單位矩陣[Pi，j]都是由單位矩陣簡單地循環(huán)右移得到的，不同的循環(huán)右移矩陣可以用不同的移位步數(shù)來表示，得到歸一化的基礎(chǔ)校驗(yàn)矩陣[Hbm，]其大小和二進(jìn)制基礎(chǔ)校驗(yàn)矩陣[Hb]相同。[Hb]中每一個(gè)“0”用“[-1]”替代，表示一個(gè)[z×z]的全零矩陣；其中的每一個(gè)“1”用一個(gè)非負(fù)整數(shù)的循環(huán)移位次數(shù)[Pi，j]表示。這樣歸一化的基礎(chǔ)校驗(yàn)矩陣[Hbm]可以直接擴(kuò)展為奇偶校驗(yàn)矩陣[H。]

[Hb]可以分成兩部分，寫成[Hb=[Hb1Hb2]]的形式。其中：[Hb1]表示系統(tǒng)比特部分，尺寸為[mb×kb，][kb=nb-mb；][Hb2]表示校驗(yàn)比特部分，尺寸為[mb×mb。][Hb2]可以進(jìn)一步分解為兩部分，[hb]有奇數(shù)的重量，[H′b2]是一個(gè)雙對(duì)角線結(jié)構(gòu)，第[i]行第[j]列的矩陣元素滿足[i=j]和[i=j+1]時(shí)為“1”，其他時(shí)候均為“0”。

[Hb2=hbH′b2=hb0hb1?hbm-110111??1101]

式中：[hb]有固定的[hb0=1，][hbmb-1=1]及[hbj=1，][0

下面，選定[12]碼率的（16 384，8 192）LDPC碼采用上述準(zhǔn)雙對(duì)角線結(jié)構(gòu)構(gòu)造出它的奇偶校驗(yàn)矩陣[H。]首先設(shè)定擴(kuò)展因子[z=1 024，]則基礎(chǔ)校驗(yàn)矩陣[Hb]的尺寸為[8×16，]即[mb=8，][nb=16。]其中的元素為[1 024×1 024]的循環(huán)單位矩陣或全零矩陣。將[Hb]中的所有元素進(jìn)行[z×z]矩陣的替換，就得到[12]碼率（16 384，8 192）LDPC碼的奇偶校驗(yàn)矩陣[H，]如圖1所示。

2 快速迭代編碼算法

利用上述構(gòu)造方法中LDPC碼基礎(chǔ)校驗(yàn)矩陣[Hb]的準(zhǔn)雙對(duì)角線結(jié)構(gòu)，直接由校驗(yàn)矩陣[H]進(jìn)行迭代編碼，可以簡化編碼復(fù)雜度，具體步驟描述如下：

首先，將奇偶校驗(yàn)矩陣[H]的基礎(chǔ)校驗(yàn)矩陣寫成[Hb=[Hb1Hb2]]的形式。定義其中的矩陣[Zq，]即若[q]為非負(fù)整數(shù)，[Zq]是大小為[z×z]的置換矩陣，由單位矩陣右移[q]位得到，若[q]為[-1]，則[Zq]為全零矩陣。其中[Hb2]除第一列外，其余部分是雙對(duì)角線結(jié)構(gòu)。

[Hb1=ZHb1（1，1）ZHb1（1，2）…ZHb1（1，kb）ZHb1（2，1）ZHb1（2，2）…ZHb1（2，kb）????ZHb1（mb，1）ZHb1（mb，2）…ZHb1（mb，kb）]

[Hb2=Zh（1）Z0Z-1Z0Z0Z-1?Z0Z0Z-1Z0?Zh（r）??Z-1?Z0?Z0Z0Z-1Z-1Z0Z0Zh（mb）Z0]

定義編碼器輸出行向量為[c，]其長度為[n=k+m，]信息位向量為[s，]校驗(yàn)位向量為[p，]則[c=sp]。

將[sT]和[pT]進(jìn)行分段，每段長度為[z]，則有：

[sT=[sT1sT2…sTkb]pT=[pT1pT2…pTmb]]

其中，

[si=si-1z+1si-1z+2…sizT，i=1，2，…，kb] [pi=pi-1z+1pi-1z+2…pizT，i=1，2，…，mb] 根據(jù)校驗(yàn)等式[H?cT=0]，可得[H2?pT=H1?sT。]定義基礎(chǔ)校驗(yàn)矩陣[Hb]的子矩陣[Hb1]中位于[i，j]位置的元素為[Hb1i，j，]根據(jù)[Zq]的定義和[Hb2]的形式可得：

[Zh1Z0Z-1Z0Z0Z-1?Z0Z0Z-1Z0?Zhr??Z-1?Z0?Z0Z0Z-1Z-1Z0Z0ZhmbZ0?p1p2?pmb]

[=ZHb11，1ZHb11，2…ZHb11，kbZHb12，1ZHb12，2…ZHb12，kb????ZHb1mb，1ZHb1mb，2…ZHb1mb，kb?s1s2?skb]

展開后可以推得：

[p1=（Zh（1）+Zh（r）+Zh（mb））-1?i=1mbj=1kbZHb1（i，j）?sTj]

將[p1]代回到上式，可得：

[p2=j=1kbZHb1（1，j）?sj+Zh（1）?p1]

以此方法類推，可得出求[p]各個(gè)分量[pi]的迭代公式：

[pr+1=pr+j=1kbZHb1（r，j）?sTj+Zh（r）?p1pi=pi-1+j=1kbZHb1（i-1，j）?sTj，i=3，4，…，r，r+2，r+3，…，mb]

對(duì)于選定的（16 384，8 192）LDPC碼，其奇偶校驗(yàn)矩陣[H]為[16 384×8 192]的準(zhǔn)循環(huán)矩陣，由8×16個(gè)1 024×1 024的循環(huán)子矩陣構(gòu)成，每個(gè)子矩陣是單位循環(huán)移位矩陣或全零矩陣。

首先，將待編碼的大小為1×8 192的信息向量[s]分成8個(gè)1×1 024的子向量[s=s1…s8。]

然后，由[pi]的迭代公式依次計(jì)算出[p1～p8，]如下面的式子所示，由此得出[p=p1…p8。]

[p1=i=18j=18ZHb1（i，j）?sTjp2=j=18ZHb1（1，j）?sj+Zh（1）?p1p3=p2+j=18ZHb1（2，j）?sTjp4=p3+j=18ZHb1（3，j）?sTjp5=p4+j=18ZHb1（4，j）?sTj+Zh（4）?p1p6=p5+j=18ZHb1（5，j）?sTjp7=p6+j=18ZHb1（6，j）?sTjp8=p7+j=18ZHb1（7，j）?sTj]

最后，組合[s]和[p，]得到碼字[c，]完成編碼。

由于在編碼的過程中只涉及到向量的移位運(yùn)算和加法運(yùn)算，故在存儲(chǔ)校驗(yàn)矩陣[H]時(shí)不需要存儲(chǔ)整個(gè)矩陣，只需存儲(chǔ)一個(gè)[8×16]的基礎(chǔ)校驗(yàn)矩陣[Hb，]簡化了編碼復(fù)雜度。

3 譯碼性能仿真

在對(duì)準(zhǔn)雙對(duì)角線結(jié)構(gòu)LDPC碼的構(gòu)造方法和快速迭代編碼算法描述的基礎(chǔ)上，本節(jié)主要通過系統(tǒng)仿真驗(yàn)證采用這種構(gòu)造方法的LDPC碼的糾錯(cuò)性能，為下一步譯碼器的硬件設(shè)計(jì)提供理論依據(jù)。

首先，通過仿真對(duì)采用準(zhǔn)雙對(duì)角線結(jié)構(gòu)的IEEE 8.2.16e標(biāo)準(zhǔn)LDPC碼和采用簡單的雙對(duì)角線結(jié)構(gòu)的DVB?S2標(biāo)準(zhǔn)LDPC碼的誤碼性能進(jìn)行分析比較。選取碼長為16 200、碼率為[12]的LDPC碼，采用歸一化最小和（NMS）算法進(jìn)行譯碼，設(shè)置最大迭代次數(shù)為15次，歸一化因子[α]取0.85。性能仿真圖如圖2所示。

由圖2可以看出，IEEE 802.16e標(biāo)準(zhǔn)LDPC碼的誤碼率性能要遠(yuǎn)遠(yuǎn)好于DVB?S2標(biāo)準(zhǔn)LDPC碼，采用準(zhǔn)雙對(duì)角線結(jié)構(gòu)能獲得更加優(yōu)異的誤碼性能。

以下仿真主要以本文選取的（16 384，8 192）LDPC碼為例進(jìn)行誤碼性能的分析驗(yàn)證。

從圖3可以看出，在誤比特率為[10-6]時(shí)，采用準(zhǔn)雙對(duì)角線結(jié)構(gòu)的（16 384，8 192）LDPC碼的性能與無編碼時(shí)相比有9.5 dB的增益，具有優(yōu)異的誤碼率性能。同時(shí)，與圖2的結(jié)果對(duì)比可知，本文所描述的LDPC碼構(gòu)造方法與IEEE 802.16e標(biāo)準(zhǔn)中的構(gòu)造方法具有同樣優(yōu)異的誤碼率性能，而且能夠在實(shí)際設(shè)計(jì)中增加靈活性，為LDPC譯碼器硬件實(shí)現(xiàn)提供了更多的設(shè)計(jì)方案。

4 結(jié) 語

本文介紹了一種采用準(zhǔn)雙對(duì)角線結(jié)構(gòu)構(gòu)造半隨機(jī)LDPC碼奇偶校驗(yàn)矩陣的方法，并以（16 384，8 192）LDPC碼為例完成了快速迭代編碼。通過對(duì)IEEE 802.16e標(biāo)準(zhǔn)LDPC碼編碼方法的改進(jìn)，增強(qiáng)了譯碼器設(shè)計(jì)的靈活性，確保了低編碼復(fù)雜度和高譯碼性能。最后，基于歸一化最小和譯碼算法進(jìn)行了仿真驗(yàn)證，得到了理想的譯碼性能。通過本文的研究，以期在下一步LDPC譯碼器硬件實(shí)現(xiàn)中獲得更優(yōu)異的譯碼性能和更低的譯碼復(fù)雜度。

參考文獻(xiàn)

[1] RICHARDSON T J， URBANKE R L. The capacity of low density parity check codes under message passing decoding [J]. IEEE Transactions on Information Theory， 2001， 47（2）： 599?618.

[2] KOU Yu， LIN Shu， FOSSORIER M P C. Low?density parity?check codes based on finite geometries： a rediscovery and new results [J]. IEEE Transactions on Information Theory， 2001， 47（7）： 2711?2736.

[3] 賀鶴云.LDPC碼基礎(chǔ)與應(yīng)用[M].北京：人民郵電出版社，2009.

[4] 肖揚(yáng).Turbo與LDPC編解碼及其應(yīng)用[M].北京：人民郵電出版社，2010.

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

[6] 張仲明.高速數(shù)傳中LDPC碼關(guān)鍵技術(shù)研究[D].長沙：國防科學(xué)技術(shù)大學(xué)，2009.

[7] 雷菁，高永強(qiáng)，王建輝，等.基于串行消息傳遞機(jī)制的QC?LDPC碼快速譯碼算法研究[J].電子與信息學(xué)報(bào)，2008，30（12）：2938?2942.

[8] 張慶林，文思群，胡旭洋，等.基于CCSDS標(biāo)準(zhǔn)的LDPC編譯碼應(yīng)用技術(shù)研究[J].計(jì)算機(jī)光盤軟件與應(yīng)用，2013（15）：65?66.

[9] 孫鈺林，吳增印，王菊花.CCSDS中LDPC碼編碼器的FPGA設(shè)計(jì)與實(shí)現(xiàn)[J].空間電子技術(shù)，2011（3）：30?34.

[10] 蘭天.一種CCSDS深空標(biāo)準(zhǔn)的LDPC碼高效實(shí)現(xiàn)[J].飛行器測控學(xué)報(bào)，2012（6）：41?46.