袁建國,李媛媛,梁夢琪,尚曉娟,王 永
(重慶郵電大學(xué)光通信與網(wǎng)絡(luò)重點實驗室,重慶 400065)
利用完備差集構(gòu)造QC-LDPC碼*
袁建國**,李媛媛,梁夢琪,尚曉娟,王 永
(重慶郵電大學(xué)光通信與網(wǎng)絡(luò)重點實驗室,重慶400065)
針對準(zhǔn)循環(huán)低密度奇偶校驗(QC-LDPC)碼中循環(huán)置換矩陣的移位次數(shù)的確定問題,提出了一種利用組合設(shè)計中完備差集(PDF)構(gòu)造QC-LDPC碼的新穎方法。當(dāng)循環(huán)置換矩陣的維度大于一定值時,該方法所構(gòu)造的規(guī)則QC-LDPC碼圍長至少為6,具有靈活選擇碼長和碼率的優(yōu)點,且所需的存儲空間更少,降低了硬件實現(xiàn)的復(fù)雜度。仿真結(jié)果表明:在誤碼率為10-5時,所構(gòu)造的碼率為3/4的PDF-QC-LDPC(3136,2352)與基于最大公約數(shù)(GCD)構(gòu)造的GCD-QC-LDPC(3136,2352)碼和基于循環(huán)差集(CDF)構(gòu)造的CDF-QC-LDPC(3136,2352)碼相比,其凈編碼增益(NCG)分別有0.41 dB和0.32 dB的提升;且在碼率為4/5時,所構(gòu)造的PDF-QC-LDPC(4880,3584)碼比GCD-QC -LDPC(4880,3584)碼和CDF-QC-LDPC(4880,3584)碼的NCG分別改善了0.21 dB和0.13 dB。
準(zhǔn)循環(huán)低密度校驗碼;循環(huán)置換矩陣;完備差集;凈編碼增益
低密度奇偶校驗(Low-Density Parity-Check,LDPC)碼是一種性能逼近香農(nóng)限的線性分組碼,具有編譯碼實現(xiàn)復(fù)雜度低、易于硬件實現(xiàn)的優(yōu)點[1]。由于在相同的碼的參數(shù)下,LDPC碼的結(jié)構(gòu)不同,編譯碼復(fù)雜度也不同,同時性能也有所差異。因此,如何構(gòu)造編譯碼簡單、性能優(yōu)異的LDPC碼是LDPC碼的研究熱點之一。
LDPC碼的構(gòu)造主要分為隨機構(gòu)造和結(jié)構(gòu)化構(gòu)造兩大類。隨機碼結(jié)構(gòu)靈活且糾錯性能優(yōu)異,但是碼的生成矩陣及校驗矩陣的結(jié)構(gòu)沒有確定的形式,因此編譯碼的復(fù)雜度很高,硬件實現(xiàn)存在一定難度[2-3]。而結(jié)構(gòu)碼是由代數(shù)、組合數(shù)學(xué)和有限幾何等方法構(gòu)造的[4-6],循環(huán)碼或準(zhǔn)循環(huán)低密度奇偶校驗(Quasi-Cyclic Low-Density Parity-Check,QC-LDPC)碼都屬于結(jié)構(gòu)碼。由于結(jié)構(gòu)碼的校驗矩陣存在循環(huán)特性,因此編譯碼復(fù)雜度大大降低,尤其是QC -LDPC碼的編碼可以利用簡單移位寄存器實現(xiàn)編碼,硬件實現(xiàn)容易,因此受到了廣泛的關(guān)注和研究。文獻[4]中基于有限域構(gòu)造出了兩個性能優(yōu)異的1/2碼率的中短碼,但是由于使用了掩模矩陣和度分布對技術(shù),校驗矩陣的描述變得比較復(fù)雜,且結(jié)構(gòu)變得不規(guī)則,因而在一定程度上提高了硬件實現(xiàn)的復(fù)雜度。文獻[5]提出了一種基于有限仿射平面的QC-LDPC碼,但該構(gòu)造方法對碼率及碼長具有嚴(yán)格的限制且有較大的冗余度。文獻[6-7]則利用組合數(shù)學(xué)中的均衡不完全區(qū)組設(shè)計構(gòu)造出了具有準(zhǔn)循環(huán)結(jié)構(gòu)的LDPC碼,但該方法構(gòu)造的碼字的碼長仍受限制。基于此,本文利用組合數(shù)學(xué)中的完備差集,結(jié)合另一種代數(shù)構(gòu)造方法循環(huán)置換矩陣構(gòu)造法[8],提出了一種新穎的方法構(gòu)造QC-LDPC碼,該方法具有所需存儲空間少、能夠靈活選擇碼長及碼率的優(yōu)點,且所構(gòu)造的碼字具有良好的糾錯性能。
定義1 設(shè)v是一個正整數(shù),對于一個加法群Zv={0,1,…,v-1},取Zv中的t個子集,每個子集包含k個元素,t個子集表示為Di={di1,di2,…,dik},di1<di2<…<dik,i=1,2,…,t,Zv中的每個非零元素在差集運算dim-dinmod v的結(jié)果中都出現(xiàn)λ次,其中m≠n,且m、n=1,2,…,k,則定義這樣的集合Di為一組t-(v,k,λ)循環(huán)差集(Cyclic Difference Family,CDF)[9]。
由定義1引出完備差集的定義如下∶
定義2 對于t-(v,k,λ)-CDF,當(dāng)λ=1且v=k(k-1)t+1時,差集dim-dinmod v的前(v-1)/2個結(jié)果稱為前項差,剩余的(v-1)/2個結(jié)果稱為后項差。若t-(v,k,1)-CDF的后項差中的元素恰為Zv的前(v-1)/2個元素構(gòu)成的子集{1,2,…,(v-1)/2}中的取值,稱這樣循環(huán)差集Di為完備差集(Perfect Difference Family,PDF)[8]。Di'為Di對應(yīng)的負(fù)集,即Di'中每個元素的值等于v減去Di中對應(yīng)位置元素的值[10]。其中∶t為循環(huán)差集中基塊數(shù);v稱為完備差集的模;k稱為循環(huán)差集的大小;λ為Zv中的元素在子集Di中出現(xiàn)的次數(shù)。
例1 取t=4,k=4,則v=12×4+1=49,選取加法群Z49中一組4-(49,4,1)-PDF,Di={di1,di2,…,dik},i=1,2,3,4,Di的具體值如下∶
D1={0,5,22,24},后項差為5,22,17,24,19;
D2={0,7,13,23},后項差為7,13,6,23,16;
D3={0,3,14,18},后項差為3,14,11,18,15;
D4={0,1,9,21},后項差為1,9,8,21,20,12。
對應(yīng)的負(fù)集為
D1'={0,44,27,25},后項差為44,27,32,25,30,47;
D2'={0,42,36,26},后項差為42,36,43,26,33,39;
D3'={0,46,35,31},后項差為46,35,38,31,34,45;
D4'={0,48,40,28},后項差為48,40,41,28,29,37。
由例1可以看出∶Di及Di'中除0元素外各不相同;Di中元素的后項差為Zv的前(v-1)/2個元素構(gòu)成的子集{1,2,…,(v-1)/2}中的取值;Di'中元素的后項差為Zv的后(v-1)/2個元素構(gòu)成的子集{(v-1)/2+1,…,v-1}中的取值,滿足完備差集的定義。
性質(zhì)1 對于Zv={0,1,…,v-1}中的一組λ=1的t-(v,k,1)-PDF,Di={di1,di2,…,dik},i=1,2,…,t,Di中元素各不相同,Zv={0,1,…,v-1}中的元素在所有子集Di中僅出現(xiàn)1次,Di中任意兩個元素的模差運算dim-dinmod v結(jié)果各不相同。
定理1 (k(k-1)t+1,k,1)-PDF存在滿足的條件[11-12]∶
(1)(6t+1,3,1)-PDF存在,當(dāng)t≡0或1 mod 4時;
(2)(12t+1,4,1)-PDF存在,當(dāng)t=1,4≤t≤1 000時;
(3)(20t+1,5,1)-PDF存在,當(dāng)t=6,8,10時;
(4)PDF不存在,當(dāng)k≥6時。
3.1QC-LDPC碼的構(gòu)造
QC-LDPC碼是一類高度結(jié)構(gòu)化的特殊的LDPC碼,其奇偶校驗矩陣H可用單位矩陣的循環(huán)移位矩陣和全零矩陣來表示,形式如(1)所示[8]∶
式中∶pij∈{0,1,2,…,p}表示單位矩陣向右循環(huán)移位的次數(shù);當(dāng)pij=0時,Q(0)表示一個p×p的全零矩陣;pij≠0時,Q(pij)表示一個p×p的循環(huán)移位矩陣。定義H的準(zhǔn)循環(huán)基矩陣P,P中的元素對應(yīng)H中單位矩陣循環(huán)移位的次數(shù),如式(2)所示∶
當(dāng)P確定后,對應(yīng)的校驗矩陣也隨之確定。
定理2 考慮Di={di1,di2,…,dik}為加法群Zv={0,1,…,v-1}中的一組t-(v,k,1)-PDF。其中∶i=1,2,…,t;di1<di2<…<dik;Di'為Di對應(yīng)的負(fù)集。定義k×k的循環(huán)矩陣Pi和Pi'的第一行分別為Di和Di'中的元素,余下每一行都是上一行向左循環(huán)移一位得來,I為一個k×k的單位矩陣。2k×2tk的基矩陣P定義為式(3)所示的形式∶
用p×p的循環(huán)矩陣和零矩陣分別去置換P中的非零元素和零元素得H矩陣。當(dāng)p≥2v時,該方法所構(gòu)造的H對應(yīng)的Tanner圖中無四環(huán)。
3.2圍長分析
取P中的一個2×2的子矩陣X如式(4)所示∶式中∶dt+s和dt'+s分別為P中第s行中的第t列及t'列的元素;同理dt+s'和dt'+s'分別為P中的第s'行中的第t列及t'列的元素;1<s<s'<k;1<t<t'<k。由于P中的零元素是用全零矩陣去替換,所以當(dāng)X中有零元素時,不會構(gòu)成四環(huán)。故以下討論的均為X中不含有0元素的情況。
下面分情況去說明P中無四環(huán)存在。
(1)當(dāng)X中的元素均來自完備差集或其負(fù)集時,X的形式如式(4),假設(shè)存在四環(huán),則式(5)成立∶
根據(jù)PDF的定義,dt+s≠dt'+s,dt+s≠dt+s',dt+s'≠dt'+s',dt'+s≠dt'+s',且dt+s-dt+s'≠dt'+s-dt'+s'。當(dāng)dt+s-dt+s'>0時,若dt+s'-dt'+s'>0,因為p≥2v,所以dt+sdt+s'<v<p,dt+s'-dt'+s'<v<p,因此等式(5)不成立;若dt+s'-dt'+s'<0,則dt+s=dt'+s',dt+s'=dt'+s,式(5)改寫為2dt+s=2dt'+smod p,由于2dt+s≠2dt'+s,且2dt+s<p,2dt'+s<p,因此等式(5)不成立。
(2)由于0元素不參與構(gòu)成四環(huán),X中的元素分別來自完備差集或其負(fù)集和單位矩陣中的1元素,X的形式如式(6)和式(7)所示∶
對于式(6),假設(shè)不存在四環(huán),則式(8)成立∶
由于p≥2v,所以0<dt+s-1<v,1-dt'+s'modp>v,因此式(8)不成立。
對于式(7)無四環(huán)的證明情況與式(6)相似。
綜上所述,該方法所構(gòu)造的H中不存在四環(huán)。
3.3該構(gòu)造方法的優(yōu)勢分析
由于基矩陣的大小為2k×2tk,則該方法構(gòu)造的H大小為2kp×2tkp,則碼率為R≥(t-1)/t。由此可知∶可根據(jù)t的不同取值去靈活選擇碼率;同時,當(dāng)k和p取不同值時,碼長n=2tkp的取值也不同。表1給出了t和k取不同值時該方法所構(gòu)造的碼長及碼率的數(shù)值分析。
表1 碼長及碼率的數(shù)值分析Tab.1 The numerical analysis of code-length and rate-code
另外,本文基于完備差集提出的QC-LDPC碼的構(gòu)造方法與大多數(shù)構(gòu)造QC-LDPC碼的方法相似,首先利用完備差集的特殊性質(zhì)靈活構(gòu)造其基矩陣P,然后再利用零矩陣和循環(huán)置換矩陣將基矩陣擴展為其校驗矩陣H。而本文構(gòu)造的基矩陣P是由k×k的循環(huán)矩陣和k×k的單位排列構(gòu)造的,循環(huán)矩陣中的每一行元素都是由上一行元素向左循環(huán)移一位得來的,且單位矩陣的引入減少了基矩陣中的非零項的存在。因此,該方法構(gòu)造的QC-LDPC碼的儲存復(fù)雜度僅考慮對基矩陣P中的循環(huán)矩陣的首行的元素及單位矩陣中的1元素的存儲,然后可利用線性移位寄存器實現(xiàn)編碼,相對于一般QCLDPC碼而言很大程度上降低了H矩陣所需要的存儲空間。相應(yīng)地,這也一定程度上降低了硬件實現(xiàn)的復(fù)雜度。
由于碼的綜合性能與碼長及碼率均有關(guān)系,碼長越長,糾錯性能越好,但引入的時延也越大。因此,為滿足實際通信系統(tǒng)實時性對時延的要求及對信息傳輸?shù)目煽啃砸?,本文?gòu)造的均為中短碼長的碼字。另外,就碼率而言,碼率越小,糾錯性能越好,但冗余度也越高,比如當(dāng)碼率為1/2時,冗余度高達50%。因此綜合考慮糾錯性能和冗余度因素,本文構(gòu)造的兩種碼字的碼率分別為3/4和4/5。
本文采用在加性白噪聲高斯(AWGN)信道下、二進制相移鍵控(BPSK)調(diào)制、和積算法(SPA)迭代譯碼的仿真環(huán)境下進行仿真,迭代次數(shù)取30次。因為雖隨著迭代次數(shù)的增加,其糾錯性能逐漸變好,但當(dāng)?shù)螖?shù)超過30時,其性能提升不大,而迭代次數(shù)越多譯碼時間越長,因而考慮譯碼時間及譯碼性能的折衷,本文在對QC-LDPC碼進行仿真時選取迭代次數(shù)為30。
首先利用例1中4-(49,4,1)-PDF,根據(jù)式(3)構(gòu)造一個8×32的基矩陣P,選取p為98,再利用式(1)構(gòu)造出碼率為3/4的規(guī)則QC-LDPC(3136,2352)碼,記為PDF-QC-LDPC(3136,2352)碼。從圖1可看出,當(dāng)誤碼率為10-5時,在碼率同為3/4的條件下,本文所構(gòu)造的PDF-QC-LDPC(3136,2352)碼與文獻[13]GCD-QC-LDPC(3136,2352)碼相比具有0.41 dB左右的凈編碼增益(Net Coding Gain,NCG)改善,比文獻[10]的CDF-QC-LDPC(3136,2352)碼NCG提高了0.32 dB左右。
圖1 碼率為3/4的PDF-QC-LDPC(3136,2352)碼與其他碼的性能比較Fig.1 The comparison of the error correction performances between the PDF-QC-LDPC(3136,2352)code and other codes at the code-rate of 3/4
為了進一步說明本文所構(gòu)造的碼字的性能的優(yōu)越性,利用5-(61,4,1)-PDF,根據(jù)式(3)構(gòu)造一個8×40的基矩陣P,取p為122,再利用式(1)構(gòu)造出碼率為4/5的PDF-QC-LDPC(4880,3584)碼。從圖2可看出,當(dāng)誤碼率為10-5時,在碼率同為4/5的條件下,所構(gòu)造的PDF-QC-LDPC(4880,3584)碼與文獻[13]的GCD-QC-LDPC((4880,3584)碼相比具有0.21 dB的NCG的改善,比文獻[10]的CDFQC-LDPC(4880,3584)碼NCG提高了0.13 dB。
圖2 碼率為4/5的PDF-QC-LDPC(4880,3584)碼與其他碼的性能比較Fig.2 The comparison of the error correction performances between the PDF-QC-LDPC(4880,3584)code and other codes at the code-rate of 4/5
本文基于完備差集和循環(huán)置換矩陣提出了一種新穎的構(gòu)造QC-LDPC碼的方法。該方法構(gòu)造的QC-LDPC碼除了具有所需存儲空間少、易于硬件實現(xiàn)的優(yōu)勢外,還在避免短環(huán)的同時,在高信噪比區(qū)域具有較快的收斂速度。仿真結(jié)果表明∶在對應(yīng)的同等條件下,本文所構(gòu)造的PDF-QC-LDPC碼的糾錯性能優(yōu)于文獻[13]基于最大公約數(shù)構(gòu)造的GCDQC-LDPC碼以及文獻[10]中基于循環(huán)差集構(gòu)造的CDF-QC-LDPC碼;除此之外,通過選取不同的參數(shù),還可以靈活選擇所需的碼長和碼率,為實際通信系統(tǒng)中應(yīng)用QC-LDPC碼提供了一種選擇方案。
本文所提出的構(gòu)造方法中僅無四環(huán)的存在,由于環(huán)長是影響LDPC碼譯碼性能的重要因素,因此在以后的研究過程中,可在該算法的基礎(chǔ)上進一步深入探討與改進,以期消除六環(huán)的存在,進一步提高碼字的糾錯性能。
[1] MACKEY D J C,NEAL R M.Near Shannon limit performance of low-density parity-check codes[J].Electronics Letters,1996,33(6)∶1645-1646.
[2] JIANG X,XIA X G,LEEM H.Efficient progressive edge -growth algorithm based on chinese remainder theorem[J].IEEE Transactions on Communications,2014,62(2)∶442-451.
[3] 鄭丹玲,穆攀,田凱,等.利用遺傳算法構(gòu)造QC-LDPC碼[J].電訊技術(shù),2015,55(4)∶355-359.
ZHENG Danlin,MU Pan,TIAN Kai,et al.Construction of QC-LDPC codes with genetic algorithm[J].Telecommunication Engineering,2015,55(4)∶355-359.(in Chinese)
[4] LAN L,SHU L.Construction of quasi-cyclic LDPC codes for AWGN and binary erasure channels∶a finite field approach[J].IEEE Transactions on Communications,2007,53(7)∶2429-2458.
[5] KAMIYA N.High-rate quasi-cyclic low-density parity-check codes derived from finite affine planes[J].IEEE Transactions on Information Theory,2007,53(4)∶1444-1459.
[6] VASIC B,MILENKOVIC O.Combinatorial constructions of low-density parity-check codes for iterative decoding[J].IEEE Transactions on Information Theory,2004,50(6)∶1156-1176.
[7] AMMAR B,HONARY B,KOU Y,et al.Construction of low density parity-check codes based on balanced incomplete block designs[J].IIEEE Transactions on Information Theory,2004,50(6)∶1257-1268.
[8] 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.
[9] PARK H,HONG S,NO J S,et al.Construction of highrate regular quasi-cyclic LDPC codes based on cyclic difference families[J].IEEE Transactions on Communications,2013,61(8)∶3108-3113.
[10] ESMAEILI M,JAVEDANKHERAD M.4-cycle free LDPC
codes based on difference sets[J].IEEE Transactions on Communications,2012,60(12)∶3579-3586.
[11] GE G N,MIAO Y,SUN X W.Perfect difference families,perfect difference matrices,and related combinatorial structures[J].Journal of Combinatorial Designs,2010,18(6)∶415-449.
[12] IBRAHEEM S M,ELRAZZAK M M A,ELDINS M S,et al. A class of structured quasi-cyclic LDPC codes based on planar difference families[C]//Proceedings of 2013 International Conference on Advanced Technologies for Communications.Ho Chi Minh City∶IEEE,2013∶614-619.
[13] ZHANG J H,ZHANG G H.Deterministic girth-eight QC-LDPC codes with large column weight[J].IEEE Communications Letters,2014,18(4)∶656-659.
袁建國(1968—),男,重慶人,2007年于重慶大學(xué)獲工學(xué)博士學(xué)位,現(xiàn)為教授、碩士生導(dǎo)師,主要研究方向為光通信系統(tǒng)、信道編碼技術(shù);
YUAN Jianguo was born in Chongqing,in 1968.He received the Ph.D.degree from Chongqing University in 2007.He is now a professor and also the instructor of graduate students.His research concerns optical communication systems and channel coding technologies.
Email∶yyyyjg@126.com
李媛媛(1992—),女,四川人,碩士研究生,主要研究方向為通信系統(tǒng)中FEC編譯碼技術(shù);
LI Yuanyuan was born in Sichuan Province,in 1992.She is now a graduate student.Her research concerns forward error correction(FEC)encoding/decoding technologies for communication systems.
Email∶liyuanyax@163.com
梁夢琪(1991—),女,重慶人,碩士研究生,主要研究方向為通信系統(tǒng)中FEC編譯碼技術(shù);
LIANG Mengqi was born in Chongqing,in 1991.She is now a graduate student.Her research concerns FEC encoding/ decoding technologies for communication systems.
Email∶1194685995@qq.com
尚曉娟(1991—),女,安徽人,碩士研究生,主要研究方向為通信系統(tǒng)中FEC編譯碼技術(shù);
SHANG Xiaojuan was born in Anhui Province,in 1991. She is now a graduate student.Her research concerns FEC encoding/decoding technologies for communication systems.
Email∶1390115692@qq.com
王 永(1977—),男,四川自貢人,教授、碩士導(dǎo)師,主要研究方向為信息安全與FEC編譯碼技術(shù)。
WANG Yong was born in Zigong,Sichuan Province,in 1977.He is now a professor and also the instructor of graduate students.His research concerns information security and FEC encoding/decoding technologies.
Email∶wangyong_cqupt@163.com
Constructing QC-LDPC Codes by Using Perfect Difference Families
YUAN Jianguo,LI Yuanyuan,LIANG Mengqi,SHANG Xiaojuan,WANG Yong
(Key Laboratory of Optical Communication and Networks,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)
∶For the problem of determining shift times of the circulant permutation matirx(CPM)in quasi-cyclic low-density parity-check(QC-LDPC)codes,a novel construction method based on the perfect difference family(PDF)among combinatorial mathematics is proposed.When the dimension of the CPM exceeds a certain particular value,the girth of the Tanner graph of QC-LDPC codes constructed by this method is at least six,and the proposed algorithm has high flexibility with respect to the design of code-length and coderate.In addition,it has less requirement about storage space,so the complexity of the hardware implementation is reduced.The simulation results show that the net coding gain(NCG)of the PDF-QC-LDPC(3136,2352)code with the code-rate of 3/4 is respectively improved 1.15 dB and 0.58 dB than those of the GCD -QC-LDPC(3136,2352)code based on the greatest common divisor(GCD)and the CDF-QC-LDPC(3136,2352)code based on the cyclic difference family(CDF)at the bit error rate(BER)of 10-5.In addition,the NCG of the proposed PDF-QC-LDPC(4880,3584)code is improved 0.21 dB and 0.13 dB than those of the GCD-QC-LDPC(4880,3584)code and the CDF-QC-LDPC(4880,3584)code with the same conditions correspondingly with the code-rate of 4/5 and the BER of 10-5.
∶quasi-cyclic low-density parity-check code;circulant permutation matirx;perfect difference family;net coding gain
The National Natural Science Foundation of China(61472464);Chongqing Research Program of Basic Research and Frontier Technology(cstc2015jcyjA0554)
TN911.22
A
1001-893X(2016)05-0471-05
10.3969/j.issn.1001-893x.2016.05.001
袁建國,李媛媛,梁夢琪,等.利用完備差集構(gòu)造QC-LDPC碼[J].電訊技術(shù),2016,56(5)∶471-475.[YUAN Jianguo,LI Yuanyuan,LIANG Mengqi,et al.Constructing QC-LDPC codes by using perfect difference families[J].Telecommunication Engineering,2016,56(5)∶471-475.]
2015-12-25;
2016-04-12Received date:2015-12-25;Revised date:2016-04-12
國家自然科學(xué)基金資助項目(61472464);重慶市基礎(chǔ)與前沿研究計劃項目(cstc2015jcyjA0554)
**通信作者:yyyyjg@126.comCorresponding author:yyyyjg@126.com