基于矩陣格的BIBD-LDPC碼構(gòu)造方法

李 通，韓建萍，王光耀

（1.山西工程職業(yè)學(xué)院計(jì)算機(jī)信息系，太原，030032；2.山西能源學(xué)院電氣與動(dòng)力工程系，太原，030600；3.北京工業(yè)大學(xué)信息與通信工程學(xué)院，北京，100124）

引 言

LDPC碼在采用置信傳播算法譯碼時(shí)，具有逼近香農(nóng)限的優(yōu)異譯碼性能，然而在高信噪比區(qū)域的錯(cuò)誤平層問(wèn)題嚴(yán)重地限制了LDPC在某些特殊領(lǐng)域的應(yīng)用。一般地，陷阱集是造成錯(cuò)誤平層的主要原因，而基本陷阱集的危害在所有陷阱集中最為嚴(yán)重。

近年來(lái)，針對(duì)陷阱集對(duì)碼字構(gòu)造的危害，相關(guān)研究人員展開(kāi)了大量的研究。文獻(xiàn)[1]提出了采用Tanner圖覆蓋的方法來(lái)消除低密度奇偶校驗(yàn)（Low density parity check,LDPC）碼中的陷阱集，錯(cuò)誤平層有所改善，不過(guò)需要提前得知陷阱集的組合特性。Asvadi等基于環(huán)提升思想，通過(guò)消除LDPC碼中的短環(huán)進(jìn)而避免大部分陷阱集[2]。文獻(xiàn)[3,4]以漸進(jìn)邊增長(zhǎng)（Progressive edge growth,PEG）算法為基礎(chǔ)，在每次添加新邊時(shí)都會(huì)搜索是否會(huì)生成基本陷阱集，然而尋找陷阱集任務(wù)量過(guò)于龐大，雖然至今為止已經(jīng)有許多高效的搜索算法相繼出現(xiàn)[5-10]，仍然造成了計(jì)算機(jī)資源的浪費(fèi)。文獻(xiàn)[11]基于平衡不完全區(qū)組和循環(huán)置換矩陣提出一種高圍長(zhǎng)準(zhǔn)循環(huán)LDPC碼的構(gòu)造方法，可快速消除陷阱集，然而只適用于特定的碼長(zhǎng)或碼率。

鑒于此，本文摒棄常規(guī)的根據(jù)Tanner圖去除短環(huán)的方法，提出以矩陣格為基礎(chǔ)的（3，m）QC-LDPC碼的無(wú)陷阱集構(gòu)造方案。借助矩陣格中基本陷阱集與斜率之間的關(guān)系，將LDPC碼的構(gòu)造轉(zhuǎn)化為在矩陣格中建立新邊的問(wèn)題。仿真結(jié)果顯示其碼字性能好于常規(guī)的PEG碼，且適用于所有列重大于3的碼字。

1 矩陣格構(gòu)造法

矩陣整數(shù)格構(gòu)造法以平衡不完全區(qū)組設(shè)計(jì)[12]（Balanced incomplete block design，BIBD）為基礎(chǔ)。將一個(gè)參數(shù)為(v,k,λ)的BIBD定義為一個(gè)有序?qū)?V,B)，其中V是由v個(gè)元素組成的集合，V被分為b個(gè)子塊，所有的子塊構(gòu)成集合B。分塊的原理是：每個(gè)子塊中有k個(gè)點(diǎn)，V中的任意兩點(diǎn)確定λ個(gè)子塊，V中的任意一點(diǎn)存在于r個(gè)不同的子塊中，故稱(chēng)r為復(fù)制數(shù)（行重），滿(mǎn)足bk=vr，λ(v-1)=r(k-1)。特別地，本文取λ=1，k=3，此時(shí)(v,3,1)-BIBD被稱(chēng)為Steiner三重系統(tǒng)。

v=15當(dāng) 時(shí)，令V={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}，B是25個(gè)子塊的集合。

此時(shí)(V,B)就是一個(gè)(15,3,1)-BIBD。如果BIBD中若干子塊將集合V中的所有點(diǎn)無(wú)重復(fù)地完全覆蓋，則將這些子塊的集合稱(chēng)為平行類(lèi)，如B中的每1列即為一個(gè)平行類(lèi)。相較于去除單個(gè)子塊，將平行類(lèi)中的子塊全部消除能夠構(gòu)造出更大圍長(zhǎng)的LDPC碼。

定義有序?qū)?V,B)所對(duì)應(yīng)的點(diǎn)塊關(guān)聯(lián)矩陣H=(hij)v×b。如果集合V中的第i個(gè)元素出現(xiàn)在B的第j個(gè)子塊中，則hij=1，否則hij=0。(15,3,1)-BIBD對(duì)應(yīng)的奇偶校驗(yàn)監(jiān)督矩陣H表示為

可以看出H為Gallager碼的奇偶校驗(yàn)矩陣，行重為r，列重為k，碼率。因?yàn)棣?1，所以集合V中的任意兩點(diǎn)僅出現(xiàn)在B中的唯一子塊內(nèi)，由BIBD得到的點(diǎn)塊關(guān)聯(lián)矩陣H所對(duì)應(yīng)的Tanner中不存在 4環(huán)[13]。

定義一個(gè)二元矩形整數(shù)格L={(x,y)：0≤x≤k-1,0≤y≤m-1}，其中m=v/k=5，整數(shù)格內(nèi)的矩形子集L如圖1所示：令lab(x,y)=m·x+y+1表示矩形格L內(nèi)所有的整數(shù)坐標(biāo)點(diǎn)，稱(chēng)為點(diǎn)標(biāo)簽，所以圖1中的整數(shù)點(diǎn)依次表示為1～15。點(diǎn)標(biāo)簽在y軸方向是周期循環(huán)的，故斜率為1的直線包括三元組 {1,7,13}，{2,8,14}，{3,9,15}，{4,10,11}，{5,6,12}。正好與B中的一個(gè)平行類(lèi)對(duì)應(yīng)，即塊B中的第2列，其他斜率的情況依次類(lèi)推。對(duì)于非整數(shù)及無(wú)窮大斜率的情況本文不作研究，于是斜率s滿(mǎn)足：0≤s≤m-1,s∈Z。構(gòu)造LDPC碼的問(wèn)題可視為在矩形格L指定合適的點(diǎn)集與一系列直線，從而構(gòu)造出高圍長(zhǎng)、低錯(cuò)誤平層的LDPC碼[14-16]。

從點(diǎn)(0,a)出發(fā)，每條斜率為s的直線經(jīng)過(guò)3個(gè)點(diǎn)，即是3個(gè)點(diǎn)的集合{(x,a+x·smodm)：0≤x≤2}，m組直線對(duì)應(yīng)m個(gè)斜率，線點(diǎn)關(guān)聯(lián)矩陣對(duì)應(yīng)LDPC碼的校驗(yàn)矩陣。定義斜率集Ψ={s1,s2,…,sm}，只要m滿(mǎn)足mod((si-sj)·c,m)≠0,?s1,s2∈Ψ,?c,i,j∈ [0,m-1]，則矩陣格L中的任意兩條直線至多有1個(gè)交點(diǎn)，對(duì)應(yīng)Tanner圖中的4環(huán)被消除。一般地，m為素?cái)?shù)，不過(guò)即使m為非素?cái)?shù)也能夠通過(guò)選取合適的斜率集構(gòu)造低錯(cuò)誤平層的LDPC碼。

2 陷阱集消除

因?yàn)榛诰仃嚫駱?gòu)造的LDPC碼不含四環(huán)，所以從環(huán)長(zhǎng)為6的情況開(kāi)始處理。圖 2（a）為一種描述（3，3）陷阱集的“三角狀態(tài)”，可以產(chǎn)生 6環(huán)。3條直線l0，l2，l4對(duì)應(yīng)的斜率分別為s0，s2和s4，相交于點(diǎn)p0，p1和p2。從p2出發(fā)到p0共有兩條路徑：一種是直達(dá)；另一種是經(jīng)過(guò)點(diǎn)p1，則點(diǎn)p0的y坐標(biāo)的兩種表達(dá)形式分別為(a+2s2modm)和(a+s0+s4modm)，所以所謂的“三角狀態(tài)”滿(mǎn)足

所以只需指定合適的3條直線，使其斜率不滿(mǎn)足式（1），就可以避免6環(huán)的出現(xiàn)[17]。

（4，4）陷阱集是生成8環(huán)的主要原因，其結(jié)構(gòu)共有6種，如圖2（b—g）所示，稱(chēng)之為“四邊形狀態(tài)”，此時(shí)所構(gòu)造的正則（3，m）LDPC碼的圍長(zhǎng)為8；圖2（h）表示的是矩陣格中（8，0）陷阱集的結(jié)構(gòu)，由一個(gè)（4，4）陷阱集（實(shí)線所示）經(jīng)翻轉(zhuǎn)后（虛線所示）形成，此時(shí)LDPC碼的圍長(zhǎng)為6或8。為了消除碼中的（8，0）陷阱集，同式（1）推導(dǎo)方式類(lèi)似，所選取的斜率應(yīng)滿(mǎn)足

圖1 m=5和k=3時(shí)的矩陣網(wǎng)格示意圖Fig.1 Matrix grid schematic diagram when m=5 and k=3

圖2 4種陷阱集在矩形格中的表示圖Fig.2 Representing graph in rectangle lattice of four trapping sets

與式（1）的推導(dǎo)方式類(lèi)似，能夠消除6種（4，4）陷阱集結(jié)構(gòu)的斜率需分別滿(mǎn)足

所以只需找到合適的斜率集{s0,s1,s2,s3,s4}滿(mǎn)足式（3），便可避免所有（4，4）陷阱集的出現(xiàn)，使所構(gòu)造的正則（3，m）LDPC碼圍長(zhǎng)至少為10。然而，經(jīng)過(guò)計(jì)算發(fā)現(xiàn)，為了消除更多的（4，4）陷阱集結(jié)構(gòu)，除了式（3）中的第3個(gè)不等式，其他不等式均可同時(shí)成立，也就是說(shuō)圖2（d）的這種陷阱集結(jié)構(gòu)無(wú)法避免，所構(gòu)造出的LDPC碼圍長(zhǎng)至多為8。

從文獻(xiàn)[15]中可發(fā)現(xiàn)，（4，4）陷阱集產(chǎn)生的危害性比較大的陷阱集有（5，3）和（6，4）陷阱集，所以接下來(lái)問(wèn)題可轉(zhuǎn)化為如何消除這兩個(gè)陷阱集。

如果陷阱集TS2的結(jié)構(gòu)中包含TS1陷阱集，或者說(shuō)TS2由TS1擴(kuò)展而來(lái)，則稱(chēng)TS1為T(mén)S2的父類(lèi)（TS2為T(mén)S1的子類(lèi)）。為了便于闡述各種陷阱集之間的父子關(guān)系，引入了點(diǎn)線表示法。如圖3就是由父類(lèi)（4，4）陷阱集生成的子類(lèi)（5，3）和（6，4）陷阱集的點(diǎn)線表示圖，其中直線代表變量節(jié)點(diǎn)，空心圓代表度為“2”的校驗(yàn)節(jié)點(diǎn)，實(shí)心圓代表度為“1”的校驗(yàn)節(jié)點(diǎn)，則一個(gè)(α，β){i}陷阱集的點(diǎn)線表示圖由α條直線和β個(gè)實(shí)心圓構(gòu)成，系數(shù)為i。每條直線上有3個(gè)圓，表明該變量節(jié)點(diǎn)與3個(gè)校驗(yàn)節(jié)點(diǎn)相鄰，即對(duì)應(yīng)的校驗(yàn)矩陣H列重為3。a、b、c分別表示圖1中直線x=0，x=1，x=2上校驗(yàn)節(jié)點(diǎn)的橫坐標(biāo)，有a≠ b≠ c，a,b,c∈ {0,1,2}，每條線上的a，b，c均不相同。若在度為“1”的校驗(yàn)節(jié)點(diǎn)a，b之間連接一條線，則這兩個(gè)節(jié)點(diǎn)的度數(shù)變?yōu)椤?”，為保證校驗(yàn)矩陣H的列重不變，在新線上添加一個(gè)度為“1”的校驗(yàn)節(jié)點(diǎn)，則（4，4）陷阱集就生成了其子類(lèi)（5，3）{1}陷阱集，在矩陣格中表示如圖2（i）所示。由于添加新線的原則是不能改變?cè)瓐D的圍長(zhǎng)，而如果連接兩個(gè)度為“1”的校驗(yàn)節(jié)點(diǎn)a或b則會(huì)引入6環(huán)，圍長(zhǎng)會(huì)從8減小到6，矩陣格中表現(xiàn)為添加的新線斜率為無(wú)窮大，僅存在理論研究意義。

令添加的新線lx的斜率為sx，則可推導(dǎo)出避免（5，3）{1}陷阱集應(yīng)滿(mǎn)足

圖3 （4，4）陷阱集生成（5，3）與（6，4）陷阱集的點(diǎn)線圖表示Fig.3 Line-point graph representation of(4,4)trapping set to(5,3)and(6,4)trapping sets

從文獻(xiàn)[15]可得，一旦(5,3){1}陷阱集被消除，則其子類(lèi)陷阱集(6,0)，(6,2){1}和(8,4){1}也隨之被消除。同樣地，(6,2){1}的兩個(gè)子類(lèi)陷阱集(7,1){1}和(8,2){1}也將不會(huì)出現(xiàn)，此時(shí)所有的（7，3）陷阱集只能由（6，4）陷阱集衍生而來(lái)。只要消除了（6，4）陷阱集，則所有的（7，3），（8，0），（8，2）陷阱集也被一并清除，那么圖3中的陷阱集基本都可以被避免，極大地提高所構(gòu)造的正則（3，m）LDPC碼的圍長(zhǎng)，具備優(yōu)異的錯(cuò)誤平層特性。

（6，4）陷阱集的點(diǎn)線表示如圖3所示，同（4，4）陷阱集生成（5，3）陷阱集的方法類(lèi)似，只需在（6，4）陷阱集的點(diǎn)線表示圖中添加一條新線便可得到（7，3）陷阱集。對(duì)于(6,4){1}陷阱集，由一個(gè)8環(huán)和兩個(gè)10環(huán)構(gòu)成。若在兩個(gè)度為“1”的校驗(yàn)節(jié)點(diǎn)b(1)與b(2)之間或c(1)與c(2)之間建立新邊，則對(duì)應(yīng)矩陣格中的斜率為無(wú)窮大；若在b(1)與c(2)之間或b(2)與c(1)之間建立新邊，則生成（8，0）陷阱集；若在b(1)與c(1)之間建立新邊，則生成（5，3）陷阱集從而引入更多的子陷阱集；若在b(2)與c(2)之間建立新邊，則會(huì)生成（3，3）陷阱集，將圍長(zhǎng)縮小到6，嚴(yán)重影響碼字的性能。同樣地，對(duì)于(6,4){2}陷阱集，由兩個(gè)8環(huán)和一個(gè)12環(huán)構(gòu)成。若在兩個(gè)度為“1”的校驗(yàn)節(jié)點(diǎn)a(1)與a(2)之間或b(1)與b(2)之間建立新邊，則對(duì)應(yīng)矩陣格中的斜率為無(wú)窮大；若在a(1)與b(1)之間或a(2)與b(2)之間建立新邊，會(huì)衍生出（8，0）陷阱集；若在a(1)與b(2)之間或a(2)與b(1)之間建立新邊，會(huì)衍生出（3，3）陷阱集，所構(gòu)造的LDPC碼中包含6環(huán)。如果在（6，4）陷阱集中添加新邊時(shí)能夠滿(mǎn)足上述約束條件，就可以避免出現(xiàn)所有的（7，3）陷阱集，從而消除其衍生的大量陷阱集。

通過(guò)分析陷阱集之間的父子結(jié)構(gòu)關(guān)系，可以摒棄以往暴力搜索陷阱集的手段，采用高效的陷阱集搜索方案。首先搜索出對(duì)碼字性能影響最大的陷阱集，然后查找該陷阱集中的度為“1”的校驗(yàn)節(jié)點(diǎn)是否在其子圖外存在共享的變量節(jié)點(diǎn)，若存在，則將變量節(jié)點(diǎn)添加至該陷阱集中即可得到一個(gè)新的陷阱集；若不存在則繼續(xù)搜索。

3 算法描述

對(duì)于一(v,k,λ)-BIBD中的有序列(V,B)，若集合B中的所有子塊能夠按照其對(duì)應(yīng)矩形格中斜率分為m個(gè)平行類(lèi)，則稱(chēng)該設(shè)計(jì)為可分解的，每個(gè)平行類(lèi)稱(chēng)為可分解類(lèi)。令B(s)為一可分解類(lèi)，對(duì)應(yīng)于某一斜率s；B'為由一系列可分解類(lèi)的集合，對(duì)應(yīng)于斜率集Ψ，表示為B'=∪s∈ΨB(s)，Ψ'為不可分解類(lèi)所對(duì)應(yīng)斜率組成的集合。算法設(shè)計(jì)的原則是：集合Ψ應(yīng)含有盡量多的元素s，這直接影響LDPC碼的圍長(zhǎng)，要求圍長(zhǎng)大于10。

如果直接采用暴力搜索的方式尋找(15,3,1)-BIBD所對(duì)應(yīng)矩陣格中的最大Ψ，整個(gè)搜索算法的復(fù)雜度為v的指數(shù)級(jí)，可行性不大。鑒于此，本文提出一種多項(xiàng)式算法來(lái)生成最大斜率集Ψ，算法步驟包括斜率的選取、判斷、再判斷和剔除，確保只有滿(mǎn)足式（2，3）約束條件的斜率才能添加進(jìn)Ψ中。令函數(shù)κ(Ψ,m)表示所選取的斜率是否滿(mǎn)足上述約束，g(V,B)表示有序?qū)?V,B)對(duì)應(yīng)LDPC的圍長(zhǎng)，則算法偽代碼如下所示。

構(gòu)造正則（3，m）LDPC碼的多項(xiàng)式算法流程

（1）初始化s=0，Ψ ={s}，B'=B(s)，Ψ '={1,2,…，m-1}

（7） B'=B'∪ B(s)

（8） else ifκ(Ψ,m)為真

（9） Ψ=Ψ ∪{s}

（10） Ψ'=Ψ'{s}

（11） elseΨ'=Ψ'{s}

（12） end if

（13） end if

（14）end while

4 復(fù)雜度分析

本文多項(xiàng)式算法構(gòu)造出的BIBD-LDPC碼對(duì)應(yīng)的校驗(yàn)矩陣包含|Ψ|×|Ψ|個(gè)單位矩陣，每行有m個(gè)單位循環(huán)子矩陣，每列有k個(gè)單位循環(huán)子矩陣，每個(gè)單位循環(huán)子矩陣的內(nèi)部元素決定其循環(huán)移位次數(shù)和在校驗(yàn)矩陣中的相對(duì)位置。因此，該算法占用的存儲(chǔ)量bit，只需存儲(chǔ)每個(gè)子矩陣的移位次數(shù)與相對(duì)位置即可。而當(dāng)LDPC碼采用隨機(jī)構(gòu)造法時(shí)，需要存儲(chǔ)校驗(yàn)矩陣中每一個(gè)具體元素的值，總體存儲(chǔ)空間bit，存儲(chǔ)量大大增加。綜上所示，本文的優(yōu)化算法節(jié)省了大量的系統(tǒng)存儲(chǔ)資源，從而為編譯碼空留出更多的運(yùn)行存儲(chǔ)空間，提高編譯碼效率與性能。

5 仿真結(jié)果及分析

為了驗(yàn)證本文算法的有效性，選用3種相等碼長(zhǎng)、碼率的PEG[18]構(gòu)造碼進(jìn)行性能仿真實(shí)驗(yàn)并比較。仿真條件為：信號(hào)經(jīng)BPSK調(diào)制后在AWGN信道中傳輸，設(shè)置最大譯碼迭代次數(shù)為30次，每個(gè)信噪比點(diǎn)的譯碼幀數(shù)為1 000幀，最小錯(cuò)誤幀為20幀，譯碼方案均采用對(duì)數(shù)域BP算法。為了在保證較小量化損耗的同時(shí)改善誤碼性能，仿真實(shí)驗(yàn)均采用中等碼率的LDPC碼。

碼C1為本文算法基于斜率集{0,1,4,9,11}所構(gòu)造的BIBD-LDPC碼，碼長(zhǎng)為225，碼率為0.4；碼C2為本文算法基于斜率集{0,1,4,9,11,23}所構(gòu)造的BIBD-LDPC碼，碼長(zhǎng)為504，碼率為0.5。由圖4可以看出，碼C1、碼C2同與之相同碼長(zhǎng)、碼率的PEG碼相比，有效地降低了誤碼率，在高信噪比區(qū)域效果更為明顯。對(duì)于碼C1，當(dāng)SNR≥3.5 dB后，能夠穩(wěn)定獲得約0.25 dB的編碼增益，這是由于在構(gòu)造碼時(shí)消除了（5，3），（6，4），（7，3）和（8，2）陷阱集。對(duì)于碼 C2，與之對(duì)應(yīng)的 PEG 碼在信噪比約為2.5 dB時(shí)就表現(xiàn)出明顯的錯(cuò)誤平層，碼C2在整個(gè)譯碼信噪比區(qū)域可以得到0.1～0.25 dB編碼增益。當(dāng)SNR=3.5 dB時(shí)，誤碼率由原先的10-5數(shù)量級(jí)降到了10-6數(shù)量級(jí)，有效地降低了錯(cuò)誤平層。

當(dāng)k=3，m=53時(shí)，搜索出的最大斜率集為{0,1,3,4,9,10,12,13}，由此構(gòu)造出的碼C3,C4的碼率均為0.5。在圖5（a,b）中，碼C3,C4分別與其同碼長(zhǎng)同碼率的Mackay碼、Gallager碼作性能比較。由圖5（a）可得，當(dāng)1.75 dB≤SNR≤2.25 dB時(shí)，碼C3可以獲得約0.2 dB的編碼增益，雖然在高信噪比區(qū)域也出現(xiàn)了錯(cuò)誤平層現(xiàn)象，但是比Mackay碼的錯(cuò)誤平層要低；由圖5（b）可看出，在SNR≥2.5 dB的中高信噪比區(qū)域，碼C4能夠穩(wěn)定獲得約0.23 dB的編碼增益，尤其是在SNR=3.75 dB時(shí)，誤碼率由原先的10-6數(shù)量級(jí)降到了10-7數(shù)量級(jí)，誤碼性能提升了一個(gè)數(shù)量級(jí)。

綜上所述，采用本文碼字構(gòu)造算法所構(gòu)造的列重為3的LDPC碼，相較于PEG碼、Mackay碼與Gallager碼，性能有著明顯的提升，尤其是在高信噪比區(qū)域。

圖4 碼C1，C2與其對(duì)應(yīng)PEG碼的誤碼性能比較Fig.4 Comparison of error-performance for C1，C2 and its corresponding PEG codes

圖5 碼C3，C4與其對(duì)應(yīng)LDPC碼的誤碼性能比較Fig.5 Comparison of error-performance for C3，C4 and its corresponding LDPC codes

6 結(jié)束語(yǔ)

本文從改進(jìn)LDPC碼的拓?fù)浣Y(jié)構(gòu)出發(fā)，將LDPC碼的構(gòu)造轉(zhuǎn)化為在矩陣格中建立新邊的問(wèn)題。若新邊的斜率滿(mǎn)足文中的陷阱集約束條件，并且圍長(zhǎng)不小于10，則將該斜率添加入斜率集。繼續(xù)添加新邊并判斷，直至得到一個(gè)基數(shù)盡可能大的斜率集，以此消除大多數(shù)的陷阱集。仿真實(shí)驗(yàn)結(jié)果表明，本文算法所構(gòu)造的正則（3，m）LDPC碼的圍長(zhǎng)不小于10，錯(cuò)誤平層有所降低，該算法對(duì)于列重大于3的校驗(yàn)矩陣依然適用。