一種快速編碼的半隨機LDPC碼構造研究

陳超然等

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

關鍵詞： 低密度奇偶校驗碼； 半隨機； 準雙對角線； 快速編碼算法

中圖分類號： TN911.22?34 文獻標識碼： A 文章編號： 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 引 言

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

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

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

1 準雙對角線結構校驗矩陣的構造方法

定義LDPC碼的奇偶校驗矩陣[H]大小為[m×n]，信息比特長度[k=n-m。]定義基礎校驗矩陣[Hb]大小為[mb×nb，][Hb]中的元素對應于[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]是一個[z×z]大小的循環單位矩陣，或是一個[z×z]大小的全零矩陣。[Hb]中的元素擴展后得到[H。]此處，[n=nb×z，][m=mb×z，][z]表示擴展因子。擴展時，將[Hb]中的“1”用一個[z×z]大小的循環單位矩陣[Pi，j]替換，將[Hb]中的“0”用一個[z×z]大小的全零矩陣[Pi，j]替換。

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

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

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

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

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

2 快速迭代編碼算法

利用上述構造方法中LDPC碼基礎校驗矩陣[Hb]的準雙對角線結構，直接由校驗矩陣[H]進行迭代編碼，可以簡化編碼復雜度，具體步驟描述如下：

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

[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，]校驗位向量為[p，]則[c=sp]。

將[sT]和[pT]進行分段，每段長度為[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] 根據校驗等式[H?cT=0]，可得[H2?pT=H1?sT。]定義基礎校驗矩陣[Hb]的子矩陣[Hb1]中位于[i，j]位置的元素為[Hb1i，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]各個分量[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]

對于選定的（16 384，8 192）LDPC碼，其奇偶校驗矩陣[H]為[16 384×8 192]的準循環矩陣，由8×16個1 024×1 024的循環子矩陣構成，每個子矩陣是單位循環移位矩陣或全零矩陣。

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

然后，由[pi]的迭代公式依次計算出[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，]完成編碼。

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

3 譯碼性能仿真

在對準雙對角線結構LDPC碼的構造方法和快速迭代編碼算法描述的基礎上，本節主要通過系統仿真驗證采用這種構造方法的LDPC碼的糾錯性能，為下一步譯碼器的硬件設計提供理論依據。

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

由圖2可以看出，IEEE 802.16e標準LDPC碼的誤碼率性能要遠遠好于DVB?S2標準LDPC碼，采用準雙對角線結構能獲得更加優異的誤碼性能。

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

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

4 結 語

本文介紹了一種采用準雙對角線結構構造半隨機LDPC碼奇偶校驗矩陣的方法，并以（16 384，8 192）LDPC碼為例完成了快速迭代編碼。通過對IEEE 802.16e標準LDPC碼編碼方法的改進，增強了譯碼器設計的靈活性，確保了低編碼復雜度和高譯碼性能。最后，基于歸一化最小和譯碼算法進行了仿真驗證，得到了理想的譯碼性能。通過本文的研究，以期在下一步LDPC譯碼器硬件實現中獲得更優異的譯碼性能和更低的譯碼復雜度。

參考文獻

[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碼基礎與應用[M].北京：人民郵電出版社，2009.

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

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

[6] 張仲明.高速數傳中LDPC碼關鍵技術研究[D].長沙：國防科學技術大學，2009.

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

[8] 張慶林，文思群，胡旭洋，等.基于CCSDS標準的LDPC編譯碼應用技術研究[J].計算機光盤軟件與應用，2013（15）：65?66.

[9] 孫鈺林，吳增印，王菊花.CCSDS中LDPC碼編碼器的FPGA設計與實現[J].空間電子技術，2011（3）：30?34.

[10] 蘭天.一種CCSDS深空標準的LDPC碼高效實現[J].飛行器測控學報，2012（6）：41?46.