劉原華 何華

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

關(guān)鍵詞： LDPC碼； 準循環(huán)； 循環(huán)置換矩陣； 快速編碼； 校驗矩陣； 編碼復(fù)雜度

中圖分類號： 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]，近年來成為編碼領(lǐng)域的研究熱點，目前已得到廣泛應(yīng)用。如歐洲數(shù)字視頻廣播標準（DVB_S2），中國地面數(shù)字電視廣播標準（DTMB），以及寬帶無線接入標準IEEE 802.16e均已采納LDPC碼作為信道糾錯編碼方式。

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

1 基于循環(huán)置換矩陣的QC?LDPC碼

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

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

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

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

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

2 校驗矩陣的構(gòu)造

2.1 漸進環(huán)增長算法

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

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

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

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

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

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

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

則該序列使矩陣[H]產(chǎn)生長為[2k]的環(huán)。

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

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

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

for j=2 to n

for i=1 to [dv（j）]

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

if i=1

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

的取值。

else

對于每個[l

[q-1}]中的元素，并根據(jù)定理1統(tǒng)計每個取值對應(yīng)的當前矩

陣4環(huán)的數(shù)量。

if存在多個取值對應(yīng)無4環(huán)

統(tǒng)計其中每個元素對應(yīng)的6環(huán)數(shù)量，對6環(huán)數(shù)最少的元 素統(tǒng)計其對應(yīng)的8環(huán)數(shù)量。選擇8環(huán)數(shù)最少的元素作為

[Hb（ki，j）]的取值。若存在多個元素對應(yīng)最少的8環(huán)，則隨

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

else顯示失敗并退出

end

end

end

end

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

2.2 可快速編碼的大圍長QC?LDPC碼構(gòu)造

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

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

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

2.3 快速編碼算法

對于糾錯碼的系統(tǒng)碼，可將碼字向量分為兩部分[c=[s p]]，其中第一部分[s=[s1 s2 … sk]]為信息向量；第二部分[p= [p1 p2 … pm]]為校驗向量。對于QC?LDPC碼的系統(tǒng)碼來說，碼字向量每一部分的子向量[si]和[pi]的長度均為[q]。由校驗關(guān)系[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標準中編碼算法的復(fù)雜度相同。

3 仿真結(jié)果

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

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

表1給出了碼長為2 304的新方法構(gòu)造碼與IEEE 802.16e中碼的短環(huán)統(tǒng)計結(jié)果。可以看出，碼率為[12]和[23]時，新方法構(gòu)造的QC?LDPC碼圍長均為8，而相同碼率的IEEE 802.16e碼的圍長均為6；[34]碼率的新方法構(gòu)造碼的圍長為6，而該碼率的IEEE 802.16e碼的圍長為4。統(tǒng)計結(jié)果顯示，與同碼長、同碼率的IEEE 802.16e中的碼相比，新方法構(gòu)造的QC?LDPC碼具有更大的圍長和更少的短環(huán)。

4 結(jié) 語

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

參考文獻

[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] 周水紅，端木春江，黃志亮，等.高性能準循環(huán)LDPC碼構(gòu)造方法的改進[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碼基矩陣構(gòu)造方法[J].現(xiàn)代電子技術(shù)，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] 劉蕾，孫書龍，常亮，等.無短環(huán)不規(guī)則QC_LDPC碼的快速編碼及聯(lián)合譯碼[J].現(xiàn)代電子技術(shù)，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碼的確定性構(gòu)造[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.