基于Hoey序列的QC-LDPC碼構(gòu)造方法

朱繼華，梁夢(mèng)琪，胡瀟月，郭 喬，袁建國

(重慶郵電大學(xué) 光電信息感測(cè)與傳輸技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

基于Hoey序列的QC-LDPC碼構(gòu)造方法

朱繼華，梁夢(mèng)琪，胡瀟月，郭 喬，袁建國

(重慶郵電大學(xué) 光電信息感測(cè)與傳輸技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

基于Hoey序列提出了一種列重為3，并環(huán)長至少為8的準(zhǔn)循環(huán)低密度奇偶校驗(yàn)(quasi-cyclic low-density parity-check, QC-LDPC)碼的新穎構(gòu)造方法，該構(gòu)造方法能避免短環(huán)的產(chǎn)生，有較好的糾錯(cuò)性能，可通過改變參數(shù)值進(jìn)而改變碼長和碼率。對(duì)提出的構(gòu)造方法進(jìn)行了環(huán)長至少為8的證明，用Matlab搭建了通信系統(tǒng)的仿真模型，并在此模型基礎(chǔ)上對(duì)基于該構(gòu)造方法構(gòu)造的QC-LDPC(900,452)碼進(jìn)行了仿真分析，仿真平臺(tái)是在高斯白噪聲(additive white Gaussian noise, AWGN)信道下，調(diào)制方式為二進(jìn)制相移鍵控(binary phase shift keying, BPSK)調(diào)制，譯碼算法為和積算法(sum product algorithm, SPA)。仿真結(jié)果表明，當(dāng)誤碼率(bit error rate, BER)相同時(shí)，利用該構(gòu)造方法所構(gòu)造的QC-LDPC(900,452)碼的凈編碼增益(net coding gain, NCG)比基于等差數(shù)列(arithmetic progression sequence, APS)構(gòu)造的QC-LDPC(896,452)碼以及基于最大公約數(shù)(greatest common divisor, GCD)構(gòu)造的QC-LDPC(900,453)碼的NCG都提高了，且所有碼的碼率均為0.5。

準(zhǔn)循環(huán)低密度奇偶校驗(yàn)(QC-LDPC)碼；Hoey序列；誤碼率(BER)；凈編碼增益(NCG)

0 引 言

低密度奇偶校驗(yàn)(low-density parity-check,LDPC)碼作為一種基于稀疏奇偶校驗(yàn)矩陣的線性分組碼，易于進(jìn)行理論分析和研究，它的性能逼近香農(nóng)限，譯碼也比較簡(jiǎn)單且可實(shí)行并行操作，適合硬件的實(shí)現(xiàn)，是一種具有較好糾錯(cuò)性能的好碼[1-2]。準(zhǔn)循環(huán)低密度奇偶(quasi-cyclic low-density parity-check，QC-LDPC)碼是結(jié)構(gòu)化LDPC碼里最有潛力的一種分類，有較低的編譯碼復(fù)雜度并在硬件上容易實(shí)現(xiàn)，因此，近幾年對(duì)于QC-LDPC碼的研究成為了一個(gè)熱點(diǎn)[3-5]。

圍長是影響QC-LDPC碼性能的重要因素，在譯碼算法為和積算法(sum product algorithm,SPA)時(shí)，會(huì)因?yàn)槎汰h(huán)的存在損失一定的性能。比如，圍長為4時(shí)，相關(guān)節(jié)點(diǎn)的信息經(jīng)過2次迭代就能傳回給本身，如果消息是錯(cuò)誤的，那么就會(huì)得到錯(cuò)誤傳播，進(jìn)而導(dǎo)致譯碼產(chǎn)生錯(cuò)誤甚至不能進(jìn)行正確的譯碼，所以，關(guān)于QC-LDPC碼圍長的研究也變得尤為重要[6-9]。有很多方式來構(gòu)造圍長至少為8的QC-LDPC碼，包括直接構(gòu)造的方式[10]和消除短環(huán)的構(gòu)造方式[11]。直接構(gòu)造方式就是在構(gòu)造校驗(yàn)矩陣的時(shí)候就避免短環(huán)，消除短環(huán)構(gòu)造方式則是在構(gòu)造好校驗(yàn)矩陣的基礎(chǔ)上，采取其他的手段進(jìn)而消除短環(huán)，例如修飾技術(shù)。本文采取的是直接構(gòu)造的方式，在構(gòu)造校驗(yàn)矩陣的時(shí)候避免了四環(huán)、六環(huán)2種短環(huán)，所以，在譯碼的時(shí)候不會(huì)因?yàn)檫@2種短環(huán)的存在而損失一定的性能，進(jìn)而具有較好的糾錯(cuò)性能。

基于Hoey序列，本文提出了當(dāng)列重為3時(shí)，圍長至少為8的構(gòu)造方法。此外，構(gòu)造了列重為3，碼率為0.5的QC-LDPC(900,452)碼并對(duì)其性能進(jìn)行了仿真，仿真結(jié)果表明，其具有較好的糾錯(cuò)性能。

1 Hoey序列的定義

Hoey序列Ai(i=0,1,2,…)是一類特殊的整數(shù)序列，有如下特點(diǎn)[12]：Ai中每個(gè)元素均為非負(fù)整數(shù)且不相同；Ai是一個(gè)遞增序列；Ai中相鄰2個(gè)元素之差也是一個(gè)遞增序列；Ai中任意2個(gè)元素之和均不相同。

對(duì)于i=0,1,…,49,Ai中前20個(gè)元素為0,1,3,7,12,20,30,44,65,80,96,122,147,181,203,251,289,360,400,474。

2 Girth-8的成立條件

定理[5]令(a1,a2,…,a2l-1,a2l)是指數(shù)矩陣E(H)中的序列，其中，ai和ai+1在同一行或者在同一列，而ai和ai+2在不同行且不同列，若存在最小正整數(shù)r使(1)式成立，則序列(a1,a2,…,a2l-1,a2l)使校驗(yàn)矩陣H中存在長度為2lr的環(huán)。

(1)

(1)式中，P是指數(shù)矩陣E(H)的擴(kuò)展因子。

假設(shè)指數(shù)矩陣E(H)的大小為J×L,其中，J是指數(shù)矩陣的列重，L是指數(shù)矩陣的行重。根據(jù)定理不存在girth-4的條件是令0≤i

(E(i,t)+E(j,s))-(E(i,s)+E(j,t))=0modP

(2)

而(2)式不成立則可推導(dǎo)為(3)，(4)式。

(E(i,t)+E(j,s))-(E(i,s)+E(j,t))≠0

(3)

P≥|(E(i,t)+E(j,s))-(E(i,s)+E(j,t))|+1

(4)

不存在girth-6的條件：令0≤i

(5)

同樣(5)式不成立可推導(dǎo)為(6)，(7)式。

綜上所述，指數(shù)矩陣E(H)滿足(3)，(4)式，則其不存在girth-4；指數(shù)矩陣E(H)滿足(6)，(7)式，則其不存在girth-6。

3 基于Hoey序列的QC-LDPC碼的構(gòu)造方法

3.1 列重為3的QC-LDPC碼構(gòu)造方法

首先構(gòu)造一個(gè)指數(shù)矩陣E(H)，其維數(shù)為3×L。它的第1行為全0元素，第2行和第3行元素依次從上到下錯(cuò)位排列，第2行和第3行元素分別為Ai(i=0,1,2,…)序列中的A0,A1,A3,…,A2L-3和A2,A4,A6,…,A2L-1。也就是說 ，第2行元素(除去第1個(gè)元素A0)為序列中排列序號(hào)為奇數(shù)的元素；第3行元素(除去最后1個(gè)元素A2L-1)為排列序號(hào)為偶數(shù)的元素。指數(shù)矩陣E(H)的構(gòu)造為

(8)

從(8)式中可看到，指數(shù)矩陣E(H)有2個(gè)特點(diǎn)：除第1行元素外，它的每行、每列都是遞增數(shù)列以及它的第3行中兩元素之差的絕對(duì)值是大于第2行中與其同列的兩元素之差的絕對(duì)值，這是由Hoey序列中相鄰2個(gè)元素之差是一個(gè)遞增序列這一特點(diǎn)得到。

然后對(duì)所構(gòu)造的指數(shù)矩陣E(H)進(jìn)行填充，E(H)中的0元素用P×P的單位矩陣替換，Ai則用相應(yīng)的單位矩陣右循環(huán)移位Ai位所得到的矩陣進(jìn)行替換，最終構(gòu)成校驗(yàn)矩陣H。其中，P的取值為P≥max(A2L-1,A2L-2+A2L-3-A2-A2L-5,A2L-1+A1-A4-A0)+1，校驗(yàn)矩陣H的構(gòu)造為

(9)

(9)式中：I0表示單位矩陣；IAi則表示單位矩陣右循環(huán)移位Hoey序列中的Ai位所得到的矩陣。從(9)式可看出，通過改變行重L和擴(kuò)展因子P的值，可以改變QC-LDPC碼的碼長及碼率。

3.2 環(huán)長至少為8的性質(zhì)證明

為了證明H對(duì)應(yīng)的Tanner圖中的環(huán)長至少為8，要依次證明Tanner圖中沒有g(shù)irth-4和girth-6。

3.2.1 不存在girth-4的性質(zhì)證明

對(duì)于girth-4，只有一種形式，其中，0≤it(s

證明：如果girth-4是存在第1行與第2行之間或第1行與第3行之間，如圖1a所示，且由指數(shù)矩陣E(H)的定義可知，第1行元素為全0元素，所以，(3)，(4)式可推導(dǎo)為(10)，(11)式：

E(j,s)-E(j,t)≠0

(10)

P≥|E(j,s)-E(j,t)|+1

(11)

又由Hoey序列Ai中每個(gè)元素均為非負(fù)整數(shù)且不相同的特點(diǎn)可知(10)式是成立的。在指數(shù)矩陣中除第1行元素外，每行、每列都是遞增數(shù)列，所以

|E(j,s)-E(j,t)|

(12)

而在指數(shù)矩陣中,E(j,s)的最大值為A2L-1，所以

|E(j,s)-E(j,t)|+1

(13)

則(11)式可推導(dǎo)為

P≥A2L-1+1

(14)

而上面所提出的構(gòu)造方法中P的取值滿足(14)式，所以，(11)式成立。

如果girth-4是存在第2行與第3行之間，girth-4如圖1b所示，那么由Hoey序列Ai中任意2個(gè)元素之和均不相同的特點(diǎn)可知，(3)式是成立的。同樣，因?yàn)橹笖?shù)矩陣E(H)中除第1行元素外，每行、每列都是遞增數(shù)列，所以，E(i,s)>E(i,t)，從而可得到

(E(i,t)+E(j,s))-(E(i,s)+E(j,t))

(15)

由指數(shù)矩陣的第3行中兩元素之差的絕對(duì)值大于第2行中與其同列的兩元素之差的絕對(duì)值這一特點(diǎn)可得

(E(j,s)-E(j,t))-(E(i,s)-E(i,t))>0

(16)

所以，可推導(dǎo)出(17)式

(17)

而在指數(shù)矩陣中,E(j,s)的最大值為A2L-1，所以

(18)

則(4)式也可推導(dǎo)為(14)式。上面所提出的構(gòu)造方法中P的取值滿足(14)式，所以，(4)式成立。

證畢。

綜上所述，本文提出列重為3的QC-LDPC碼的構(gòu)造方法是不存在girth-4的。

圖1 girth-4的形式Fig.1 Types of girth-4

3.2.2 不存在girth-6的性質(zhì)證明

對(duì)于girth-6，有6種存在形式，如圖2所示。其中，i=0,k=1,j=2，0≤s,t,r≤L-1，在下面的證明中，假設(shè)s

圖2 girth-6的6種形式Fig.2 Six types of girth-6

證明：第1行元素都為0，所以，對(duì)于第1種girth-6形式，(6)，(7)式分別可推導(dǎo)為

(E(j,s)+E(k,r))-(E(j,r)+E(k,t))≠0

(19)

(20)

同樣，由Hoey序列Ai中任意2個(gè)元素之和均不相同的特點(diǎn)可得到(19)式是成立的，其他4種girth-6的證明與其一樣。但是要滿足(7)式成立，這里需將girth-6的6種形式分類討論。

對(duì)于1，2，5，6這4種girth-6的形式，它們的證明是一樣的，如圖3所示。只證明第1種girth-6，其形式見圖3a。

圖3 girth-6的3種形式Fig.3 Three types of girth-6

因?yàn)橹笖?shù)矩陣E(H)中除第1行元素外，每行、每列都是遞增數(shù)列，第3行中兩元素之差的絕對(duì)值大于第2行中與其同列的兩元素之差的絕對(duì)值。所以，根據(jù)第1個(gè)特點(diǎn)以及結(jié)合以上2個(gè)特點(diǎn)可以分別推出

E(k,r)>E(k,t)

(21)

(E(j,r)-E(j,s))-(E(k,r)-E(k,t))>0

(22)

從而可推導(dǎo)出

有數(shù)據(jù)顯示，在美國每天就有5億支吸管被遺棄（這意味著每人每天大約1.5支的消耗量）。有專門負(fù)責(zé)清理海灘垃圾的環(huán)保組織在一項(xiàng)研究中聲稱，美國各地的海灘上每年廢棄的吸管大約有75億支之多。

(23)

而在指數(shù)矩陣中,E(j,r)的最大值為A2L-1，所以

(24)

則(20)式可推導(dǎo)為(14)式，上面，所提出的構(gòu)造方法P的取值滿足(14)式，所以(20)式成立，進(jìn)而(7)式也成立。

對(duì)于3，4這2種girth-6的形式，首先將(7)式分別轉(zhuǎn)化成(25)、(26)式：

由于指數(shù)矩陣E(H)中的第3行中兩元素之差的絕對(duì)值大于第2行中與其同列的兩元素之差的絕對(duì)值，那么，2種形式的證明都用到取極限值的方法，將第3行中差值的絕對(duì)值取到最大，如圖3b，圖3c所示，這樣就使(25)、(26)式中P的最小值取到最大，分別為A2L-1+A1-A4-A0+1、A2L-2+A2L-3-A2-A2L-5+1，所以，可推導(dǎo)出

P≥A2L-1+A1-A4-A0+1

(27)

P≥A2L-2+A2L-3-A2-A2L-5+1

(28)

上面所提出的構(gòu)造方法中P的取值滿足(27)，(28)式，則(7)式成立。

證畢。

綜上所述，本文提出列重為3的QC-LDPC碼的構(gòu)造方法是不存在girth-6的。

4 仿真及性能分析

首先利用本文的構(gòu)造方法構(gòu)造一個(gè)QC-LDPC碼，列重為J=3，行重L=6，其指數(shù)矩陣為

(29)

P的選值為

所以本文選取P=150，則碼長為900，則校驗(yàn)矩陣為

(30)

(30)式中：I0表示單位矩陣；IAi則表示單位矩陣右循環(huán)移位Hoey序列中的Ai位所得到的矩陣，單位矩陣的大小為150×150，最終可得到行重為6，列重為3，碼率為0.5的QC-LDPC(900, 452)碼。

本文對(duì)所構(gòu)造的QC-LDPC(900, 452)碼進(jìn)行仿真時(shí)的仿真環(huán)境具體如下：仿真工具為Matlab，仿真平臺(tái)是在高斯白噪聲(additive white Gaussian noise, AWGN)信道下，調(diào)制方式為二進(jìn)制相移鍵控(binary phase shift keying,BPSK)調(diào)制，譯碼算法為SPA算法。迭代次數(shù)取16次，因?yàn)殡m隨著迭代次數(shù)的增加，其糾錯(cuò)性能逐漸變好，但當(dāng)?shù)螖?shù)由16增加到32時(shí)，其糾錯(cuò)性能只是稍有改善。因而綜合考慮譯碼復(fù)雜度及譯碼性能，本文在對(duì)QC-LDPC碼進(jìn)行仿真時(shí)選取迭代次數(shù)為16。

再將QC-LDPC(900, 452)碼與同碼率的基于等差數(shù)列構(gòu)造[6]的QC-LDPC(896,452)碼、基于最大公約數(shù)構(gòu)造[7]的QC-LDPC(900,453)碼進(jìn)行對(duì)比分析，如圖4所示。從圖4可知，在誤碼率為10-5時(shí)，本文所構(gòu)造的QC-LDPC(900,452)碼與基于等差數(shù)列構(gòu)造的QC-LDPC(896,452)碼以及基于最大公約數(shù)構(gòu)造的QC-LDPC(900,453)碼的編碼增益分別為0.66 dB和2.64 dB。

圖4 QC-LDPC(900,452)碼與其他碼的糾錯(cuò)性能仿真圖Fig.4 Comparison graph of the error correction performances among the QC-LDPC(900,452) code and the other codes

5 結(jié) 論

本文提出了一種基于Hoey序列構(gòu)造QC-LDPC碼的新穎方法，能避免四環(huán)、六環(huán)2種短環(huán)的產(chǎn)生，在譯碼時(shí)不會(huì)因這2種短環(huán)的存在而損失一定的性能，因此具有較好的糾錯(cuò)性能，并可通過改變參數(shù)L的值進(jìn)而改變碼長和碼率，但本文只提出了列重為3的構(gòu)造方法，所以，相較于列重較大的構(gòu)造方法，碼率的選擇不夠全面，因?yàn)閷?duì)于相同的行重，隨著列重的增加，碼率的選擇也會(huì)增加，爭(zhēng)取在以后的研究中完善這一點(diǎn)，提出列重較大的構(gòu)造方法。另外，構(gòu)造了列重為3的QC-LDPC(900,452)碼，仿真結(jié)果表明，它的糾錯(cuò)性能優(yōu)于同碼率的基于等差數(shù)列構(gòu)造的QC-LDPC碼以及基于最大公約數(shù)構(gòu)造的QC-LDPC碼。

[1] HUANG Qin, DIAO Qiuju, LIN Shu, et al. Cyclic and Quasi-Cyclic LDPC Codes on Constrained Parity-Check Matrices and Their Trapping Sets[J]. IEEE Transactions on Information Theory, 2012, 58(5):2648-2671.

[2] 袁建國，劉飛龍，楊松.一種光通信中基于LDPC碼的新穎級(jí)聯(lián)碼[J].半導(dǎo)體光電，2014,35(2):293-295,299. YUAN Jianguo, LIU Feilong, YANG Song. A Novel Concatenated Code Based on LDPC Codes for Optical Communications[J]. Semiconductor Optoelectronics, 2014, 35(2):293-295, 299.

[3] LI Juane, LIU Keke, LIN Shu, et al. Algebraic Quasi-Cyclic LDPC Codes: Construction, Low Error-Floor, Large Girth and a Reduced-Complexity Decoding Scheme[J]. IEEE Transactions on Communications, 2014, 62(8): 2626-2637.

[4] 翟云云,包小敏,鄧倫治,等.基于QC-LDPC碼的信息協(xié)調(diào)協(xié)議[J].西南大學(xué)學(xué)報(bào):自然科學(xué)版,2013,35(9):161-165. QU Yunyun. BAO Xiaomin, DENG Lunzhi, et al. An Information Reconciliation Protocol Based QC-LDPC cade[J]. Journal of Southwest University: Natural Science Edition, 2013, 35(9): 161-165.

[5] 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.

[6] ZHANG Yi, DA Xinyu. Construction of girth-eight QC-LDPC codes from arithmetic progression sequence with large column weight[J]. IET Electronics Letters , 2015, 51(16):1257-1259.

[7] ZHANG Guohua,RONG Sun,WANG Xinmei.Construction of Girth-Eight QC-LDPC Codes from Greatest Common Divisor[J].IEEE Communications Letters,2013,17(2):369-372.

[8] ZHANG Jiahua, ZHANG Guohua. Deterministic Girth-Eight QC-LDPC Codes with Large Column Weight[J]. IEEE Communications Letters, 2014, 18(4):656-659.

[9] WANG Juhua, ZHANG Guohua. Coset-based QC-LDPC codes without small cycles[J]. IET Electronics Letters, 2014 50(22):1597-1598.

[10] YANG L, LIU H. Code construction and FPGA implementation of a low-error-floor multi-rate low-density parity-check code decoder[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2006, 53(4): 892-904.

[11] WANG Y, YEDIDIA J S. Construction of high-girth QC-LDPC codes[C]//Turbo Codes and Related Topics, IEEE 5th International Symposium on. Lausanne, Switzerland: IEEE Press, 2008:180-185.

[12] GE X, XIA S T. Structured non-binary LDPC codes with large girth[J]. IET Electronics Letters, 2007, 43(22): 1220-1221.

(編輯：劉 勇)

s：The National Natural Science Foundation of China (61472464); The Natural Science Foundation of Chongqing Science and Technology Commission (cstc2015jcyjA0554)； The Undergraduate Science Research Training Project for Chongqing University of Posts and Telecommunications in 2016 (A2016-61).

Novel construction method of QC-LDPC codes based on Hoey sequences

ZHU Jihua, Liang Mengqi, HU Xiaoyue, Guo Qiao, Yuan Jianguo
(Chongqing Key Laboratory of Photoelectronic Information Sensing and Transmitting Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China)

A novel construction method of quasi-cyclic low-density parity-check(QC-LDPC) codes with girth of at least eight and the column weight of the constructed QC-LDPC code is 3 based on Hoey sequence is proposed. The novel construction method can avoid short-girth and has better error-correction performance. Moreover, the code length and the code rate can be adjusted by selecting different parameters. Firstly, the girth of at least eight in the proposed novel construction method is proved, and then the simulation model of communication system is established by Matlab program. And based on the model, the QC-LDPC(900,452) code constructed by the proposed construction method is emulated and analyzed. The simulation environments are addictive white Gaussian noise(AWGN) channel, binary phase shift keying(BPSK) modulation method and the decoding algorithm of the sum product algorithm(SPA). The simulation results show when the bit error rate (BER) is the same, the net coding gain(NCG) of the QC-LDPC(900,452) code is more than those of the QC-LDPC(896,452) code constructed by the construction method based on the arithmetic progression sequence(APS) and the QC-LDPC(900,453) code constructed by the construction method based on the greatest common divisor(GCD). Furthermore, all the codes have the same code rate of 50%.

quasi-cyclic low-density parity-check(QC-LDPC)code;Hoey sequence;bit error rate(BER);net coding gain(NCG)

2015-12-08

2016-10-15 通訊作者：袁建國 yuanjg@cqupt.edu.cn

國家自然科學(xué)基金(61472464)；重慶市基礎(chǔ)與前沿研究計(jì)劃項(xiàng)目(cstc2015jcyjA0554);2016年重慶郵電大學(xué)大學(xué)生科研訓(xùn)練計(jì)劃項(xiàng)目(A2016-61)

10.3979/j.issn.1673-825X.2017.03.009

TN911

A

1673-825X(2017)03-0341-05

朱繼華(1978-)，男，重慶人，講師，碩士，主要研究方向?yàn)楣怆娖骷肮馔ㄐ畔到y(tǒng)。E-mail: zhujh@cqupt.edu.cn 。

梁夢(mèng)琪(1991-)，女，重慶人，碩士研究生，主要研究方向?yàn)橥ㄐ畔到y(tǒng)中FEC編譯碼技術(shù)。E-mail: 1194685995@qq.com。