劉寧慶，王 焜，孫浩偉

(1.哈爾濱工業(yè)大學(xué)通信技術(shù)研究所，150080哈爾濱，dulubleach@126.com; 2.中國海軍駐哈爾濱地區(qū)艦船配套軍事代表室，150046哈爾濱)

采用和積算法(S-PA)譯碼的低密度奇偶校驗(yàn)(Low-density Parity-check，LDPC)［1］碼呈現(xiàn)近似Shannon極限的誤碼率特性［2］，被認(rèn)為是應(yīng)用于電信領(lǐng)域的下一代差錯(cuò)控制碼.大周長(zhǎng)的校驗(yàn)矩陣能夠保證大的碼字最小距離，提高譯碼效率并改善LDPC碼的誤碼率特性［3］.采用PEG(Progressive Edge-growth)方法可高效地構(gòu)造大周長(zhǎng)校驗(yàn)矩陣［4-5］，卻增加了LDPC譯碼器硬件設(shè)計(jì)的復(fù)雜度.因此構(gòu)造大周長(zhǎng)且易于硬件實(shí)現(xiàn)的LDPC碼是目前的研究熱點(diǎn).

逐級(jí)構(gòu)造的思想被廣泛的應(yīng)用于構(gòu)造LDPC碼［6-8］以降低LDPC碼譯碼器硬件設(shè)計(jì)的復(fù)雜度.基于該思想，Jin Lu等［9-10］提出了一種以具有不同行(或列)移位系數(shù)的單位陣作為各級(jí)子矩陣的LDPC碼，即PS-LDPC(Partition-and-Shift LDPC)碼，并證明了處于同一級(jí)中的各個(gè)子矩陣之間形成閉合環(huán)的判決定理，且以該定理為基礎(chǔ)提出了可構(gòu)造任意周長(zhǎng)校驗(yàn)矩陣的方法.然而，這種構(gòu)造算法未提供在移位系數(shù)矩陣中尋找閉合環(huán)路的復(fù)雜過程的詳細(xì)步驟，且采用判斷隨機(jī)數(shù)是否滿足2t循環(huán)定理約束條件的方式篩選各子矩陣的移位系數(shù)，未獲得最佳移位系數(shù).

為此本文采用兩種可行的方法完成矩陣中找閉合環(huán)路的過程;并詳細(xì)的分析了子矩陣移位系數(shù)的選擇與可能形成的閉合環(huán)之間的關(guān)系，為PS-LDPC碼各子矩陣的移位系數(shù)的篩選提供了詳細(xì)的判斷準(zhǔn)則，有利于構(gòu)造具有更大周長(zhǎng)的PSLDPC校驗(yàn)矩陣.基于上述方法構(gòu)造的PS-LDPC譯碼器比傳統(tǒng)構(gòu)造法構(gòu)造的PS-LDPC碼獲得了更高的譯碼性能.

1 相關(guān)工作

PS-LDPC碼的基本原理［9］如圖1所示.1種LDPC碼可以由其Tanner圖描述，Vc表示所有m個(gè)校驗(yàn)節(jié)點(diǎn)的集合，Vb表示所有n個(gè)信息節(jié)點(diǎn)的集合.可將Vc和Vb分別劃分成Nb和Nc個(gè)大小均為p的子矩陣，其中m=Nc·p，n=Nb·p，且Nc≥j，Nb≥k，j、k分別表示校驗(yàn)矩陣的最大列重和行重.每個(gè)子矩陣中的元素被索引在0～p-1之間;在第α個(gè)校驗(yàn)節(jié)點(diǎn)子矩陣中的第Xc個(gè)校驗(yàn)節(jié)點(diǎn)在Tanner圖中與第β個(gè)信息節(jié)點(diǎn)子矩陣中第Xb個(gè)信息節(jié)點(diǎn)連接，且有Xb=，其中表示模為p的加法運(yùn)算.以這種形式表示的LDPC碼為準(zhǔn)循環(huán)LDPC碼的一種.如將校驗(yàn)矩陣H劃分成Nc×Nb個(gè)大小為p× p的子矩陣，每個(gè)子矩陣均為單位矩陣或其循環(huán)移動(dòng)矩陣，則校驗(yàn)矩陣H可由這些子矩陣的移位系數(shù)Sα，β表示，即移位矩陣S=［Sα，β］.一個(gè)(20，3，4)的校驗(yàn)矩陣的Tanner圖及其移位矩陣S如圖1所示.

圖1 (20，3，4)校驗(yàn)矩陣的移位矩陣S及Tanner圖

圖中S中的“*”代表零矩陣所對(duì)應(yīng)的系數(shù).

文獻(xiàn)［9］提出的2t循環(huán)定理指出如果一個(gè)校驗(yàn)矩陣H的移位矩陣S中一個(gè)長(zhǎng)度為2t的閉合環(huán)路上的頂點(diǎn)Sα1，β1，Sα2，β2，…，Sα2t，β2t滿足

則這個(gè)循環(huán)移動(dòng)矩陣S對(duì)應(yīng)的校驗(yàn)矩陣中將沿著這個(gè)閉合環(huán)路形成長(zhǎng)度為2t閉合環(huán)路.PS-LDPC碼循環(huán)移動(dòng)矩陣S的構(gòu)造即通過考察各個(gè)長(zhǎng)度為2t'的閉合環(huán)路是否滿足2t循環(huán)定理來避免循環(huán)的產(chǎn)生(此處及后文所指的滿足2t循環(huán)定理均指，即不會(huì)構(gòu)成長(zhǎng)度為2t的循環(huán)).文獻(xiàn)［10］中詳盡的描述了校驗(yàn)矩陣的構(gòu)造法則，本文不予贅述.

2 移位系數(shù)的選擇

文獻(xiàn)［10］提出的獲取PS-LDPC碼校驗(yàn)矩陣H中子矩陣的移位系數(shù)的方法是合理的，但構(gòu)造效率可進(jìn)一步提高.下面提出一種改進(jìn)的確定某子矩陣的移位系數(shù)的方法.如圖2所示的4個(gè)6× 6的單位矩陣的循環(huán)移動(dòng)矩陣，根據(jù)2t循環(huán)定理規(guī)定的運(yùn)算準(zhǔn)則可知:

故由這4個(gè)移位系數(shù)組成的長(zhǎng)為4的閉合環(huán)路在監(jiān)督矩陣中不會(huì)形成長(zhǎng)為4的循環(huán).然而，由圖可知這4個(gè)移位系數(shù)對(duì)應(yīng)的子矩陣可形成長(zhǎng)為12的環(huán).此時(shí)的循環(huán)路徑以2t循環(huán)定理的運(yùn)算準(zhǔn)則可表示為

本文將不重復(fù)的閉合環(huán)路形成上的環(huán)稱為一次環(huán)，而在多次重復(fù)的閉合環(huán)路上形成的環(huán)稱為多次環(huán).對(duì)于p≠1的PS-LDPC類碼，多次環(huán)的形成不可避免，但可以采取措施保證其長(zhǎng)度最大化.

圖2 長(zhǎng)為4×3的循環(huán)示例

考察類似情況，可得到如下結(jié)論:滿足2t循環(huán)定理的閉合環(huán)路(長(zhǎng)度為2t)上的頂點(diǎn)(不同的移位系數(shù))，形成長(zhǎng)為L(zhǎng)的閉合環(huán)路，其中

式中:p為每個(gè)子矩陣的行/列數(shù);φ(x，y)表示x和y的最大公約數(shù);

因此在規(guī)定某個(gè)子矩陣的移位系數(shù)時(shí)，應(yīng)盡量選擇可使sump(ls2t)與p的最大公約數(shù)較小的移位系數(shù).當(dāng)sump(ls2t)=p/2時(shí)為最不利的情況，此時(shí)循環(huán)的長(zhǎng)度為4t.然而采用文獻(xiàn)［10］的構(gòu)造方法構(gòu)造PS-LDPC碼的校驗(yàn)矩陣時(shí)，可縮減一次判斷移位系數(shù)是否滿足4t長(zhǎng)度閉合環(huán)路上的2t循環(huán)定理的過程.

基于上述思想，改進(jìn)文獻(xiàn)［10］中提出的移位矩陣的構(gòu)造方法.以周長(zhǎng)為g的校驗(yàn)矩陣H作為基底產(chǎn)生矩陣，構(gòu)造PS-LDPC碼校驗(yàn)矩陣的移位矩陣S的改進(jìn)方法如改進(jìn)算法1所述.

這種改進(jìn)構(gòu)造方法保證了每確定1個(gè)子矩陣的移位系數(shù)時(shí)，使經(jīng)過該子矩陣的循環(huán)的長(zhǎng)度最大化.其中Lmint表示起始且終止于Sr的所有長(zhǎng)為2t'的閉合環(huán)路形成的最短的循環(huán)長(zhǎng)度，亦即Sr取某個(gè)值時(shí)，在終始于它的所有2t'長(zhǎng)的閉合環(huán)路上出現(xiàn)的最不理想情況;LMIN則表示在長(zhǎng)度從g到gc-2的所有閉合環(huán)路上出現(xiàn)的最不理想情況(最短循環(huán));選取最大LMIN對(duì)應(yīng)的值為Sr保證最短循環(huán)長(zhǎng)度的最大化.每添加1個(gè)Sr記錄這個(gè)Sr對(duì)應(yīng)的最大LMIN(記為max(LMIN))，構(gòu)造完畢所得校驗(yàn)矩陣的周長(zhǎng)g'即為最小的max(LMIN).若需要再下一級(jí)構(gòu)造，則以此次構(gòu)造的校驗(yàn)矩陣作為下一級(jí)的移位矩陣，并以g'為起始考察的閉合環(huán)路長(zhǎng)度，至需要的周長(zhǎng)，按改進(jìn)的方法在原校驗(yàn)矩陣“1”的位置添加最優(yōu)的Sr值.

這種改進(jìn)構(gòu)造法則使得構(gòu)造過程更有目的性，避免了t'=r·t時(shí)出現(xiàn)的sump(ls2t)≠0而sump(ls2t')=0的情況，因而避免重新選擇Sr的需要.因此，改進(jìn)的構(gòu)造法無論從校驗(yàn)矩陣的譯碼性能亦或構(gòu)造效率上都有明顯的進(jìn)步.

此外，可采用不同的方法構(gòu)造未指定周長(zhǎng)的最上級(jí)矩陣(PS-LDPC碼中可理解為未添加移位系數(shù)Sα，β前的基底移位矩陣S)，如以上提出的PS-LDPC碼改進(jìn)構(gòu)造法或PEG構(gòu)造法.PEG方法構(gòu)造的矩陣具有更優(yōu)的周長(zhǎng)特性，因此最上級(jí)矩陣可以采用PEG矩陣.參照第3部分介紹的尋找定長(zhǎng)的閉合環(huán)的方法，可獲取此最上級(jí)矩陣的周長(zhǎng)g，再根據(jù)上面提出的構(gòu)造法完成周長(zhǎng)至少為gc的校驗(yàn)矩陣的構(gòu)造.

3 閉合環(huán)路查找方法

在矩陣中尋找閉合環(huán)路是繁瑣的過程，本文提出一種直觀的尋找長(zhǎng)為2t閉合環(huán)路的方法，通過改變某些參數(shù)，可尋找矩陣中經(jīng)過某節(jié)點(diǎn)的不同歷經(jīng)范圍內(nèi)的閉合環(huán)路.

設(shè)hi，j為大小為m×n的矩陣H中的元素，欲尋找歷經(jīng)H矩陣的所有經(jīng)過hi，j且長(zhǎng)為2t的閉合環(huán)路，可用1個(gè)2t元矢量CP表示長(zhǎng)為2t的閉合環(huán)路的邊軌跡.CP的偶數(shù)元表示Tanner圖中連接到同一個(gè)校驗(yàn)節(jié)點(diǎn)的2個(gè)信息節(jié)點(diǎn)作為閉合環(huán)路的2個(gè)頂點(diǎn)時(shí)，這2個(gè)信息節(jié)點(diǎn)的列數(shù)差;CP的奇數(shù)元表示Tanner圖中連接到同1個(gè)信息節(jié)點(diǎn)的兩個(gè)校驗(yàn)節(jié)點(diǎn)作為閉合環(huán)路的2個(gè)頂點(diǎn)時(shí)，這2個(gè)校驗(yàn)節(jié)點(diǎn)的行數(shù)差.因此CP的每一元表示了閉合環(huán)路的1條邊歷經(jīng)的行數(shù)或列數(shù).圖3為6元矢量CP的示意圖.

圖3 長(zhǎng)為6的閉合環(huán)路及6元矢量CP示例

此外對(duì)于歷經(jīng)矩陣H的閉合環(huán)路，以上對(duì)CP各元參數(shù)的限制應(yīng)與H的尺寸相關(guān)，不超出H的行列范圍，故另加限制條件如下:

1)偶數(shù)元取值范圍為(1-n，-1)∪(1，n-1)，奇數(shù)元取值范圍為(1-m，-1)∪(1，m-1);

2)對(duì)于任意偶數(shù)x＜2t，且k為偶數(shù)有

3)對(duì)于任意奇數(shù)y＜2t，且k為奇數(shù)有

4)對(duì)于k為奇數(shù)或偶數(shù)，均有

經(jīng)以上限制條件，可保證長(zhǎng)度為2t的閉合環(huán)路歷經(jīng)H且終始于hi0，j0.閉合環(huán)路上的頂點(diǎn)可表示為hiz，jz，z(1≤z≤t)表示自hi0，j0后歷經(jīng)的第z個(gè)頂點(diǎn).對(duì)于hi，j不全為1的情況，需考察hiz，jz是否為0，hiz，jz是0則舍棄該CP.

當(dāng)z為奇數(shù)時(shí)，iz=i0+∑CP［k］，(k=1，3，…，z);jz=j0+∑CP［k］，(k=2，4，…，z-1).

當(dāng)z為偶數(shù)時(shí)，iz=i0+∑CP［k］，(k=1，3，…，z-1);jz=j0+∑CP［k］，k=2，4，…，z.

通過考察限制條件1)～4)獲得的滿足條件的矢量CP即為欲尋找的閉合環(huán)路起始于hi，j的邊軌跡，進(jìn)而獲得閉合環(huán)路上的元素.

4 性能仿真

分別以改進(jìn)構(gòu)造算法和文獻(xiàn)［10］提出的傳統(tǒng)構(gòu)造法(g＞8)構(gòu)造一列重1≤j≤3，行重7≤k≤9的，1 200×3 600的非規(guī)則PS-LDPC碼.仿真考查不同的信噪比下通過AWGN信道時(shí)這2種碼的誤比特率(BER).仿真結(jié)果如圖5所示.

圖4 AWGN信道下的BER性能比較

由圖4的仿真結(jié)果可知，改進(jìn)構(gòu)造法構(gòu)造的PS-LDPC碼具有更優(yōu)的譯碼性能，為4.5 dB信噪比時(shí)的譯碼性能可媲美傳統(tǒng)PS-LDPC碼Eb/No(信噪比)在5.5 dB以上時(shí)的譯碼性能.這也說明這樣的校驗(yàn)矩陣H具有更大的周長(zhǎng)和碼字最小距離.

5 結(jié)論

本文通過對(duì)傳統(tǒng)PS-LDPC碼構(gòu)造算法的分析，發(fā)現(xiàn)了傳統(tǒng)構(gòu)造算法在計(jì)算效率上的不足.并針對(duì)這個(gè)問題提出了改進(jìn)算法.此外，本文介紹了一種在監(jiān)督矩陣中查找閉合環(huán)路的方法，確保改進(jìn)的構(gòu)造算法可高效實(shí)現(xiàn).最后通過對(duì)改進(jìn)算法構(gòu)造的PS-LDPC碼的誤碼率特性仿真可知:

1)改進(jìn)的PS-LDPC碼構(gòu)造算法改善了校驗(yàn)矩陣的周長(zhǎng)特性;

2)改進(jìn)算法提高了校驗(yàn)矩陣的構(gòu)造效率;

3)AWGN信道下BER性能更優(yōu).

此外本文提出的閉合環(huán)尋找方法可應(yīng)用在其他LDPC校驗(yàn)矩陣的構(gòu)造算法中.

［1］GALLAGER R.Low-density parity-check codes［J］. IEEE Transactions on Information Theory，1962，8 (1):21-28.

［2］MACKAY D J C.Good error-correcting codes based on very sparse matrices［J］.IEEE Transactions on Information Theory，1999，45(2):399-431.

［3］MACKAY D J C，NEAL R M.Near shannon limit performance of low density parity check codes［J］.Electronics Letters，1997，33(6):457-458.

［4］HU X Y，ELEFTHERIOU E，ARNOLD D M.Progressive edge-growth Tanner graphs［C］//IEEE Global Telecommunications Conference，2001.GLOBECOM'01:IEEE. Piscataway:IEEE，2001，2(25-29):995-1001.

［5］HU X Y，ELEFTHERIOU E，ARNOLD D M.Regular and irregular progressive edge-growth tanner graphs［J］.IEEE Transactions on Information Theory，2005，51(1):386-398.

［6］ZHANG Tong，PARHI K K.An FPGA implementation of(3，6)regular low density-parity check-code decoder［J］.EURASIP Journal on Applied Signal Processing，2003，6:530-542.

［7］LIAO E，ENGLING Y，NIKOLIC B.Low-density parity-check code constructions for hardware implementation［C］//IEEE International Conference on Communications.Piscata way:IEEE，2004，5:2573-2577.

［8］LI Z W，VIJAYA KUMAR B V K.A class of good quasi-cyclic low-density parity check codes based on progressive edge growth graph［J］.IEEE Commun Lett，2004，2:1990-1994.

［9］LU J，MOURA J M F.Partition-and-Shift LDPC Codes［J］.IEEE Transactons on Magnetics，2005，41(10): 2977-2979.

［10］LU J，MOURA J M F.Structured LDPC codes for highdensity recording:Large girth and low error floor［J］. IEEE Transactions on Magnetics，2006，42(2):208-213.