可快速編碼的大圍長QC?LDPC碼構造

劉原華 何華

摘 要： 為保證LDPC碼在低編碼復雜度的同時，減少短環對其迭代譯碼性能的影響，提出一種可快速編碼的大圍長準循環LDPC碼構造方法。該方法將校驗矩陣分成兩部分，其中右半部分具有準雙對角線結構，使其可利用校驗矩陣直接進行快速編碼，有效降低了LDPC碼的編碼復雜度；左半部分通過逐個設置其循環置換子矩陣以確保當前矩陣中的短環數最少，有效避免了短環的出現，保證了大圍長的特性。仿真結果表明，與IEEE 802.16e中的LDPC碼相比，新方法構造的LDPC碼具有更大的圍長和更少的短環，在低編碼復雜度的基礎上獲得了更優的糾錯性能。

關鍵詞： LDPC碼； 準循環； 循環置換矩陣； 快速編碼； 校驗矩陣； 編碼復雜度

中圖分類號： TN911.22?34 文獻標識碼： A 文章編號： 1004?373X（2018）11?0001?04

Construction of quasi?cyclic LDPC codes with fast encoding and large girth

LIU Yuanhua， HE Hua

（School of Communication and Information Engineering， Xian University of Posts and Telecommunications， Xian 710121， China）

Abstract： A construction method of quasi?cyclic （QC） LDPC codes with fast encoding and large girth is proposed to reduce the effect of short cycles on the performance of iterative decoding while maintaining the low encoding complexity of LDPC codes. The check matrix is divided into two parts. The right part of the matrix has the quasi?dual?diagonal structure， which can perform the fast encoding directly， and reduce the encoding complexity of LDPC codes effectively. The circulant permutation sub?matrices are set one by one in the left part of the matrix to ensure the minimum number of short cycles， avoid the occurrence of short cycles， and guarantee the characteristic of large girth. The simulation results show that， in comparison with LDPC codes in IEEE 802.16e， the codes constructed with the new method have larger girth and less short cycles， and better error correction performance while maintaining the low encoding complexity.

Keywords： LDPC code； quasi?cycle； circulant permutation matrix； fast encoding； check matrix； encoding complexity

0 引 言

低密度奇偶校驗碼（LDPC）具有逼近Shannon限的糾錯性能[1?8]，近年來成為編碼領域的研究熱點，目前已得到廣泛應用。如歐洲數字視頻廣播標準（DVB_S2），中國地面數字電視廣播標準（DTMB），以及寬帶無線接入標準IEEE 802.16e均已采納LDPC碼作為信道糾錯編碼方式。

LDPC碼可分為隨機LDPC碼和結構化LDPC碼。雖然隨機構造法能獲得較大的圍長，設計出性能優異的LDPC碼，但由于缺乏一定的結構特性，編碼復雜度高，不利于硬件實現，且校驗矩陣的硬件存儲也較為復雜。而基于代數方法構造的結構化LDPC碼雖具有循環或準循環結構，編碼復雜度較低，但較難有效消除短環，導致LDPC碼迭代譯碼性能損失。于是不斷涌現出很多LDPC碼新的構造方法。文獻[1]提出一種不包含4環的準循環LDPC碼（QC?LDPC碼）構造方法，但該方法不能保證消除6環。文獻[3]基于原模圖構造出具有低編碼和譯碼復雜度的LDPC碼，但其未考慮校驗矩陣的奇異性。事實上，一般代數方法構造的QC?LDPC碼并不能保證校驗矩陣滿秩，即存在校驗矩陣的行相關問題，導致構造生成矩陣非常困難[1]。文獻[4]提出一種碼率為[12]時的最佳度分布的QC?LDPC碼構造方法，但其未考慮圍長對迭代譯碼性能的影響。為確保在低編碼復雜度的同時，減少短環對LDPC碼迭代譯碼性能的影響，本文提出一種基于漸進環增長算法來構造大圍長和線性編碼復雜度的QC?LDPC碼的方法。該方法利用漸進環增長算法有效避免了短環的產生，保證了大圍長的特性，同時，所構造校驗矩陣的右半部分具有準雙對角線結構，保證了校驗矩陣的奇異性，可直接利用校驗矩陣進行快速迭代編碼。與IEEE 802.16e標準中的LDPC碼相比，本文構造出的QC?LDPC碼具有更大的圍長和更少的短環，在相同的編碼復雜度下具有更優的糾錯性能。

1 基于循環置換矩陣的QC?LDPC碼

對于基于循環置換矩陣的QC?LDPC碼，其校驗矩陣[H]是由循環置換矩陣和零矩陣組成的矩陣陣列：

[H=Ia11Ia12…Ia1nIa21Ia22…Ia2n????Iam1Iam2…Iamn]

式中：[aij∈{-1，0，1，2，…，q-1}]；[Iaij]為[q×q]的循環置換矩陣，可由單位陣[I]每行向右循環移位[aij]位得到。[H]的零空間即碼長為[N=nq]的QC?LDPC碼。每個循環置換矩陣均可由其維數[q]和循環移位次數[aij]唯一確定，因此[H]所需的存儲空間非常小，只需存儲如下[m×n]大小的矩陣[Hb]即可：

[Hb=a11a12…a1na21a22…a2n????am1am2…amn]

式中：[Hb]稱為矩陣[H]的基矩陣，將[Hb]中的每個元素[aij]用[q×q]的循環置換矩陣[Iaij]代替，即可得到矩陣[H，]此操作稱為矩陣擴展。

2 校驗矩陣的構造

2.1 漸進環增長算法

LDPC碼的迭代置信傳播（BP）譯碼算法是基于無環圖的最優譯碼算法，以消息的獨立性假設為前提，而LDPC碼校驗矩陣中的短環將會導致其迭代譯碼時的消息不滿足獨立性假設，具有一定的相關性，并且環長越短、短環數量越多，消息的相關性越嚴重，越影響迭代譯碼的性能。因此，設計LDPC碼時必須盡量避免短環（尤其是4環6環）的出現。本文利用漸進環增長算法使得構造出的QC?LDPC碼包含盡量少的短環，具有較大的圍長。

二進制矩陣[H=（hij）M×N]中長為[2k]的環由滿足如下條件的[2k]個[hij=1]的位置構成：

1） 任意相鄰兩個[hij=1]的位置均在[H]的同一行或者同一列；

2） 每個[hij=1]的位置均互不相同。

循環置換矩陣的每行每列有且僅有一個元素為1，因此對于基于循環置換矩陣的QC?LDPC碼來說，環中任意兩個相鄰的[hij=1]的位置必定處在同一行塊或者同一列塊的循環置換矩陣中。因此，可以由基矩陣[Hb]中的元素構成的序列[（a1，a2，…，a2k）]來表示大矩陣[H]中長為[2k]的環，其中[ai∈Hb，1≤i≤2k]，[ai≠-1]，任意相鄰元素[ai]和[ai+1]均在[Hb]的同一行或者同一列，[ai]和[ai+2]在不同行且不同列。文獻[2]研究了[H]中長為[2k]的環的存在條件，滿足定理1。

定理1[2]：對于基矩陣[Hb]中的序列[（a1，a2，…，a2k）]，其中[ai]和[ai+1]在同一行或者同一列，[ai]和[ai+2]在不同行且不同列，若滿足如下等式：

[i=12k（-1）iai≡0modq] （1）

則該序列使矩陣[H]產生長為[2k]的環。

事實上，滿足上述條件的序列[（a1，a2，…，a2k）]將使[H]中產生[q]個長為[2k]的環。對于基于循環置換矩陣的QC?LDPC碼來說，只需設計一個維數很小的基矩陣[Hb，]然后通過矩陣擴展即可得到所需的稀疏大矩陣[H]，將其作為QC?LDPC碼的校驗矩陣。通過選取適當元素來構造[Hb，]使其不滿足式（1）的條件，便可以避免甚至消除短環的出現，即可通過構造很小的基矩陣[Hb]來獲得具有少量短環的大矩陣[H，]在很大程度上減小了構造QC?LDPC碼的復雜度。另一方面，為統計短環的數量，也只需要對基矩陣[Hb]中的元素根據式（1）進行測試，就很容易統計出大矩陣[H]中的短環數目。

下面給出構造基矩陣[Hb]的漸進環增長算法，對于非規則QC?LDPC碼來說，將[m]行[n]列的基矩陣[Hb]的第[j]列重記為[dv（j）]，漸進環增長算法構造[Hb]的具體步驟如下：

首先將[Hb]的每個元素初始化為-1， 對于[Hb]的第1列，隨機選取[dv（1）]個位置，對于選取的每個位置，從集合[{0，1，2，…，q-1}]中隨機選取一個數值作為該位置元素的取值。[Hb]其余元素的設置方法如下：

for j=2 to n

for i=1 to [dv（j）]

選擇當前矩陣第j列中行重最小的行，記為第[ki]行

if i=1

從集合[{0，1，2，…，q-1}]中隨機選取一個數值作為[Hb（k1，j）]

的取值。

else

對于每個[l

[q-1}]中的元素，并根據定理1統計每個取值對應的當前矩

陣4環的數量。

if存在多個取值對應無4環

統計其中每個元素對應的6環數量，對6環數最少的元 素統計其對應的8環數量。選擇8環數最少的元素作為

[Hb（ki，j）]的取值。若存在多個元素對應最少的8環，則隨

機選擇其中一個作為[Hb（ki，j）]的取值。

else顯示失敗并退出

end

end

end

end

可以看出，漸進環增長算法通過逐個設置基矩陣的元素以確保當前矩陣中的短環數最少，可有效避免短環的出現，從而保證迭代譯碼的性能。通過適當選取[m，n]和[q]的取值，可以構造出各種碼長和碼率的QC?LDPC碼。對于給定的行重和列重，該方法也可設計出對應的規則QC?LDPC碼。

2.2 可快速編碼的大圍長QC?LDPC碼構造

在構造LDPC碼時還需考慮其編碼復雜度問題。一般的編碼方法是先由校驗矩陣獲得生成矩陣，再根據生成矩陣進行編碼，其運算復雜度與碼長的平方成正比。為解決編碼復雜度問題，使其更易于硬件實現，IEEE 802.16e標準中采用具有特殊結構的QC?LDPC碼，其校驗矩陣的右半部分具有準雙對角線結構，可以在保證校驗矩陣滿秩的同時直接利用校驗矩陣進行快速迭代編碼，具有較低的編碼復雜度。由此，提出具有類似結構的校驗矩陣的設計方法，進而獲得可實現低編碼復雜度的大圍長QC?LDPC碼。

將QC?LDPC碼的校驗矩陣及其基矩陣分成兩部分：[H=[H1 H2]]，[Hb=[Hb1 Hb2]]，其中[H1]的維數為[mq×kq]，[H2]的維數為[mq×mq]，且[H2]的基矩陣具有式（2）的形式，其中[a1，a2，…，am，x]的取值從集合[{0，1，2，…，q-1}]中隨機選取，第1列的元素[x]在[Hb2]的第[r]行，可以證明[H2]滿秩[8]。根據[Hb1]每列的度分布參數，利用漸進環增長算法逐列構造[Hb1，]以確保當前矩陣中的短環數最少。

[Hb2=a1a2-1a2a3?a3a4-1-1a4?x??-1?am-2?-1am-2am-1-1am-1ama1am] （2）

2.3 快速編碼算法

對于糾錯碼的系統碼，可將碼字向量分為兩部分[c=[s p]]，其中第一部分[s=[s1 s2 … sk]]為信息向量；第二部分[p= [p1 p2 … pm]]為校驗向量。對于QC?LDPC碼的系統碼來說，碼字向量每一部分的子向量[si]和[pi]的長度均為[q]。由校驗關系[H?cT=0]可得，[H1?sT=H2?pT]。將校驗矩陣的左半邊矩陣的基矩陣[Hb1]第i行第j列的元素記為[Hb1（i，j）]，則：

[Ia1Ia2I-1Ia2Ia3?Ia3Ia4I-1I-1Ia4?Ix??I-1?Iam-2?I-1Iam-2Iam-1I-1Iam-1IamIa1Iam?p1p2?pm=IHb1（1，1）IHb1（1，2）…IHb1（1，k）IHb1（2，1）IHb1（2，2）…IHb1（2，k）????IHb1（m，1）IHb1（m，2）…IHb1（m，k）?s1s2?sk （3）]

將式（3）展開可得到包含[m]個等式的方程組，將各式相加可得求解校驗向量第一個子向量如下：

[p1=I-1x?i=1mj=1kIHb1（i，j）?sj] （4）

然后將式（3）中的[m]個等式逐個迭代可得計算校驗向量其余子向量[pi]的迭代公式：

[pi=I-1ai?j=1kIHb1（i-1，j）?sj+Iai-1?pi-1， i=2，3，…，r，r+2，r+3，…，m] （5）

[pr+1=I-1ar+1?j=1kIHb1（r，j）?sj+Iar?pr+Ix?p1] （6）

從而得到碼字向量[c=[s p]]。可以看出，該編碼算法與IEEE 802.16e標準中編碼算法的復雜度相同。

3 仿真結果

下面在加性高斯白噪聲信道（AWGN）下采用BPSK調制方式，對利用新方法構造的QC?LDPC碼和IEEE 802.16e標準中的QC?LDPC碼的糾錯性能進行仿真比較，采用置信傳播（BP）譯碼算法，譯碼算法的最大迭代次數均設為100次。

圖1顯示了碼長為2 304，碼率分別為[12，23]以及[34]的QC?LDPC碼的BER性能比較。為增大可比性，本文所提方法構造碼的度分布與IEEE 802.16e中相同碼率碼的度分布完全相同，循環置換子矩陣的參數均為[q=96]。由仿真結果可以看出，與IEEE 802.16e中的碼相比，新方法構造的各種碼率的QC?LDPC碼具有略優的BER糾錯性能。

表1給出了碼長為2 304的新方法構造碼與IEEE 802.16e中碼的短環統計結果?？梢钥闯觯a率為[12]和[23]時，新方法構造的QC?LDPC碼圍長均為8，而相同碼率的IEEE 802.16e碼的圍長均為6；[34]碼率的新方法構造碼的圍長為6，而該碼率的IEEE 802.16e碼的圍長為4。統計結果顯示，與同碼長、同碼率的IEEE 802.16e中的碼相比，新方法構造的QC?LDPC碼具有更大的圍長和更少的短環。

4 結 語

本文研究了基于循環置換矩陣的QC?LDPC碼構造方法，提出一種可快速編碼的大圍長QC?LDPC碼構造方法。校驗矩陣具有準雙對角線結構，可利用校驗矩陣直接進行簡單快速編碼，降低了硬件實現復雜度。利用漸進環增長算法逐個設置校驗矩陣左半部分基矩陣的元素以確保當前矩陣中的短環數最少，有效避免了短環的出現。同時給出了簡單快速編碼的具體實現方法。仿真結果表明，與IEEE 802.16e標準中的LDPC碼相比，新方法構造出的QC?LDPC碼具有更大的圍長和更少的短環，在低編碼復雜度的基礎上獲得了更優的糾錯性能。

參考文獻

[1] ZHAO Y， XIAO Y. The necessary and sufficient condition of a class of quasi?cyclic LDPC codes without girth four [J]. IEICE transactions on communications， 2009， 92（1）： 306?309.

[2] FOSSORIER M P C. Quasi?cyclic low?density parity?check codes from circulant permutation matrices [J]. IEEE transactions on information theory， 2004， 50（8）： 1788?1793.

[3] DIVSALAR D， DOLINAR S， JONES C. Short protograph?based LDPC codes [C]// Proceedings of IEEE 2007 MIL Conference. [S.l.]： IEEE Press， 2007： 1387?1392.

[4] 周水紅，端木春江，黃志亮，等.高性能準循環LDPC碼構造方法的改進[J].計算機工程，2010，36（1）：277?279.

ZHOU S H， DUANMU C J， HUANG Z L， et al. Improvement of high?performance quasi?cyclic LDPC code construction method [J]. Computer engineering， 2010， 36（1）： 277?279.

[5] ZHANG L， LIN S， ABDEL?GHAFFAR K， et al. Quasi?cyclic LDPC codes on cyclic subgroups of finite fields [J]. IEEE transactions on communications， 2011， 59（9）： 2330?2336.

[6] LIU Y， ZHANG M， FAN J. Quasi?cyclic LDPC codes with high?rate and low error floor based on Euclidean geometries [J]. Journal of China Universities of Posts and Telecommunications， 2012， 19（2）： 96?99.

[7] LIU K， HUANG Q， LIN S， et al. Quasi?cyclic LDPC codes： construction and rank analysis of their parity?check matrices [C]// Proceedings of 2012 Information Theory and Applications Workshop. San Diego， CA： IEEE， 2012： 227?233.

[8] 朱磊基，汪涵，施玉松，等.QC?LDPC碼基矩陣構造方法[J].現代電子技術，2012，35（5）：68?70.

ZHU L J， WANG H， SHI Y S， et al. Construction methods of basis matrix for QC?LDPC code [J]. Modern electronics technique， 2012， 35（5）： 68?70.

[9] 劉蕾，孫書龍，常亮，等.無短環不規則QC_LDPC碼的快速編碼及聯合譯碼[J].現代電子技術，2015，38（17）：34?37.

LIU L， SUN S L， CHANG L， et al. Fast coding and joint decoding of irregular QC?LDPC codes without short?cycle [J]. Modern electronics technique， 2015， 38（17）： 34?37.

[10] 張軼，達新宇，蘇一棟.任意列重大圍長QC?LDPC碼的確定性構造[J].電子學報，2016，44（8）：1814?1819.

ZHANG Y， DA X Y， SU Y D. Deterministic construction of QC?LDPC codes for any column weight with a large girth [J]. Acta electronica sinica， 2016， 44（8）： 1814?1819.