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

劉原華 何華

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

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

中圖分類號(hào)： TN911.22?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

低密度奇偶校驗(yàn)碼（LDPC）具有逼近Shannon限的糾錯(cuò)性能[1?8]，近年來(lái)成為編碼領(lǐng)域的研究熱點(diǎn)，目前已得到廣泛應(yīng)用。如歐洲數(shù)字視頻廣播標(biāo)準(zhǔn)（DVB_S2），中國(guó)地面數(shù)字電視廣播標(biāo)準(zhǔn)（DTMB），以及寬帶無(wú)線接入標(biāo)準(zhǔn)IEEE 802.16e均已采納LDPC碼作為信道糾錯(cuò)編碼方式。

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

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

對(duì)于基于循環(huán)置換矩陣的QC?LDPC碼，其校驗(yàn)矩陣[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]的零空間即碼長(zhǎng)為[N=nq]的QC?LDPC碼。每個(gè)循環(huán)置換矩陣均可由其維數(shù)[q]和循環(huán)移位次數(shù)[aij]唯一確定，因此[H]所需的存儲(chǔ)空間非常小，只需存儲(chǔ)如下[m×n]大小的矩陣[Hb]即可：

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

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

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

2.1 漸進(jìn)環(huán)增長(zhǎng)算法

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

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

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

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

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

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

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

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

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

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

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

for j=2 to n

for i=1 to [dv（j）]

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

if i=1

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

的取值。

else

對(duì)于每個(gè)[l

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

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

if存在多個(gè)取值對(duì)應(yīng)無(wú)4環(huán)

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

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

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

else顯示失敗并退出

end

end

end

end

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

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

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

將QC?LDPC碼的校驗(yàn)矩陣及其基矩陣分成兩部分：[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}]中隨機(jī)選取，第1列的元素[x]在[Hb2]的第[r]行，可以證明[H2]滿秩[8]。根據(jù)[Hb1]每列的度分布參數(shù)，利用漸進(jìn)環(huán)增長(zhǎng)算法逐列構(gòu)造[Hb1，]以確保當(dāng)前矩陣中的短環(huán)數(shù)最少。

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

2.3 快速編碼算法

對(duì)于糾錯(cuò)碼的系統(tǒng)碼，可將碼字向量分為兩部分[c=[s p]]，其中第一部分[s=[s1 s2 … sk]]為信息向量；第二部分[p= [p1 p2 … pm]]為校驗(yàn)向量。對(duì)于QC?LDPC碼的系統(tǒng)碼來(lái)說(shuō)，碼字向量每一部分的子向量[si]和[pi]的長(zhǎng)度均為[q]。由校驗(yàn)關(guān)系[H?cT=0]可得，[H1?sT=H2?pT]。將校驗(yàn)矩陣的左半邊矩陣的基矩陣[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）展開(kāi)可得到包含[m]個(gè)等式的方程組，將各式相加可得求解校驗(yàn)向量第一個(gè)子向量如下：

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

然后將式（3）中的[m]個(gè)等式逐個(gè)迭代可得計(jì)算校驗(yàn)向量其余子向量[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]]?？梢钥闯觯摼幋a算法與IEEE 802.16e標(biāo)準(zhǔn)中編碼算法的復(fù)雜度相同。

3 仿真結(jié)果

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

圖1顯示了碼長(zhǎng)為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糾錯(cuò)性能。

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

[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] 周水紅，端木春江，黃志亮，等.高性能準(zhǔn)循環(huán)LDPC碼構(gòu)造方法的改進(jìn)[J].計(jì)算機(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] 劉蕾，孫書(shū)龍，常亮，等.無(wú)短環(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] 張軼，達(dá)新宇，蘇一棟.任意列重大圍長(zhǎng)QC?LDPC碼的確定性構(gòu)造[J].電子學(xué)報(bào)，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.