可快速編碼的大圍長(zhǎng)QC

可快速編碼的大圍長(zhǎng)QC-LDPC碼構(gòu)造劉原華;何華【摘要】Aconstructionmethodofquasi-cyclic(QC)LDPCcodeswithfastencodingandlargegirthisproposedtoreducetheeffectofshortcyclesontheperformanceofiterativedecodingwhilemaintainingthelowencodingcomplexityofLDPCcodes.Thecheckmatrixisdividedintotwoparts.Therightpartofthematrixhasthequasi-dual-diagonalstructure,whichcanperformthefastencodingdirectly,andreducetheencodingcomplexityofLDPCcodeseffectively.Thecirculantpermutationsub-matri-cesaresetonebyoneintheleftpartofthematrixtoensuretheminimumnumberofshortcycles,avoidtheoccurrenceofshortcycles,andguaranteethecharacteristicoflargegirth.Thesimulationresultsshowthat,incomparisonwithLDPCcodesinIEEE802.16e,thecodesconstructedwiththenewmethodhavelargergirthandlessshortcycles,andbettererrorcorrectionperformancewhilemaintainingthelowencodingcomplexity.%為保證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é)果表明，與IEEE802.16e中的LDPC碼相比，新方法構(gòu)造的LDPC碼具有更大的圍長(zhǎng)和更少的短環(huán)，在低編碼復(fù)雜度的基礎(chǔ)上獲得了更優(yōu)的糾錯(cuò)性能.【期刊名稱】《現(xiàn)代電子技術(shù)》【年（卷），期】2018（041）011【總頁(yè)數(shù)】4頁(yè)（P1-4）【關(guān)鍵詞】LDPC碼;準(zhǔn)循環(huán);循環(huán)置換矩陣;快速編碼;校驗(yàn)矩陣;編碼復(fù)雜度【作者】劉原華;何華【作者單位】西安郵電大學(xué)通信與信息工程學(xué)院，陜西西安710121;西安郵電大學(xué)通信與信息工程學(xué)院，陜西西安710121【正文語(yǔ)種】中文【中圖分類】TN911.22-340引言低密度奇偶校驗(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)IEEE802.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］提出一種碼率為1/2時(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)行快速迭代編碼。與IEEE802.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)置換矩陣和零矩陣組成的矩陣陣列：式中：aiju{-1,0,12...,q-1}；Iaij為qxq的循環(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ǔ)如下mxn大小的矩陣Hb即可：式中：Hb稱為矩陣H的基矩陣，將Hb中的每個(gè)元素aij用qxq的循環(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)MxN中長(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)，其中aieHb,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在不同行且不同列，若滿足如下等式：則該序列使矩陣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,12...,q-1｝中隨機(jī)選取一個(gè)數(shù)值作為該位置元素的取值。Hb其余元素的設(shè)置方法如下：可以看出，漸進(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)，IEEE802.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=[H1H2],Hb=[Hb1Hb2],其中H1的維數(shù)為mqxkq,H2的維數(shù)為mqxmq,且H2的基矩陣具有式（2）的形式，其中a1,a2,...,am,x的取值從集合｛0,12...,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ù)最少。2.3快速編碼算法對(duì)于糾錯(cuò)碼的系統(tǒng)碼，可將碼字向量分為兩部分c=[sp],其中第一部分s=[s1s2...sk]為信息向量；第二部分p=[p1p2...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），則：將式（3）展開可得到包含m個(gè)等式的方程組，將各式相加可得求解校驗(yàn)向量第—個(gè)子向量如下：然后將式（3）中的m個(gè)等式逐個(gè)迭代可得計(jì)算校驗(yàn)向量其余子向量pi的迭代公式：從而得到碼字向量c=[sp]?？梢钥闯?，該編碼算法與IEEE802.16e標(biāo)準(zhǔn)中編碼算法的復(fù)雜度相同。3仿真結(jié)果下面在加性高斯白噪聲信道（AWGN）下采用BPSK調(diào)制方式，對(duì)利用新方法構(gòu)造的QC-LDPC碼和IEEE802.16e標(biāo)準(zhǔn)中的QC-LDPC碼的糾錯(cuò)性能進(jìn)行仿真比較，采用置信傳播（BP）譯碼算法，譯碼算法的最大迭代次數(shù)均設(shè)為100次。圖1顯示了碼長(zhǎng)為2304，碼率分別為1/2,2/3以及3/4的QC-LDPC碼的BER性能比較。為增大可比性，本文所提方法構(gòu)造碼的度分布與IEEE802.16e中相同碼率碼的度分布完全相同，循環(huán)置換子矩陣的參數(shù)均為q=96。由仿真結(jié)果可以看出，與IEEE802.16e中的碼相比，新方法構(gòu)造的各種碼率的QC-LDPC碼具有略優(yōu)的BER糾錯(cuò)性能。圖1新方法構(gòu)造碼與IEEE802.16e碼的BER性能Fig.1BERperformanceofstructuredcodesandcodesinIEEE802.16e表1給出了碼長(zhǎng)為2304的新方法構(gòu)造碼與IEEE802.16e中碼的短環(huán)統(tǒng)計(jì)結(jié)果?？梢钥闯?，碼率為1/2和2/3時(shí)，新方法構(gòu)造的QC-LDPC碼圍長(zhǎng)均為8，而相同碼率的IEEE802.16e碼的圍長(zhǎng)均為6；3/4碼率的新方法構(gòu)造碼的圍長(zhǎng)為6，而該碼率的IEEE802.16e碼的圍長(zhǎng)為4。統(tǒng)計(jì)結(jié)果顯示，與同碼長(zhǎng)、同碼率的IEEE802.16e中的碼相比，新方法構(gòu)造的QC-LDPC碼具有更大的圍長(zhǎng)和更少的短環(huán)。表1碼長(zhǎng)為2304的新方法構(gòu)造碼與IEEE802.16e碼的短環(huán)數(shù)量Table1Shortcyclesofconstructedcodeswithlength2304andcodesinIEEE802.16eR=23IEEE802.16e碼本文碼IEEE802.16e碼本文碼00004800364811525798436556861747216730884結(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é)果表明，與IEEE802.16e標(biāo)準(zhǔn)中的LDPC碼相比，新方法構(gòu)造出的QC-LDPC碼具有更大的圍長(zhǎng)和更少的短環(huán)，在低編碼復(fù)雜度的基礎(chǔ)上獲得了更優(yōu)的糾錯(cuò)性能。參考文獻(xiàn)【相關(guān)文獻(xiàn)】ZHAOY,XIAOY.Thenecessaryandsufficientconditionofaclassofquasi-cyclicLDPCcodeswithoutgirthfour[J].IEICEtransactionsoncommunications,2009,92(1):306309.FOSSORIERMPC.Quasi-cycliclow-densityparity-checkcodesfromcirculantpermutationmatrices[J].IEEEtransac-tionsoninformationtheory,2004,50(8):17881793.DIVSALARD,DOLINARS,JONESC.Shortprotograph-basedLDPCcodes[C]//ProceedingsofIEEE2007MILConference.[S.l.]:IEEEPress,2007:1387-1392.周水紅，端木春江，黃志亮，等.高性能準(zhǔn)循環(huán)LDPC碼構(gòu)造方法的改進(jìn)[J].計(jì)算機(jī)工程，2010,36(1):277-279.ZHOUSH,DUANMUCJ,HUANGZL,etal.Improvementofhigh-performancequasi-cyclicLDPCcodeconstructionmethod[J].Computerengineering,2010,36(1):277-279.ZHANGL,LINS,ABDEL-GHAFFARK,etal.Quasi-cyclicLDPCcodesoncyclicsubgroupsoffinitefields[J].IEEEtransactionsoncommunications,2011,59(9):2330-2336.LIUY,ZHANGM,FANJ.Quasi-cyclicLDPCcodeswithhigh-rateandlowerrorfloorbasedonEuclideangeometries[J].Jour-nalofChinaUniversitiesofPostsandTelecommunications,2012,19(2):96-99.LIUK,HUANGQ,LINS,etal.Quasi-cyclicLDPCcodes:constructionandrankana