基于原模圖擴(kuò)展的QC-LDPC構(gòu)造方法

龔險(xiǎn)峰 陶孝鋒 邱樂(lè)德

（中國(guó)空間技術(shù)研究院西安分院，西安710000）（中國(guó)空間技術(shù)研究院，北京100094）

1 引言

在多數(shù)情況下，衛(wèi)星通信都屬于功率受限的通信系統(tǒng)，因而信道編碼技術(shù)在衛(wèi)星通信中占有舉足輕重的地位。低密度奇偶校驗(yàn)碼（LDPC）和Turbo碼一樣具有逼近Shannon門(mén)限的糾錯(cuò)性能，但與Turbo碼相比還有一些優(yōu)勢(shì)，比如：可以高度并行處理、更低的誤碼平層等。因此，LDPC引起了廣泛的關(guān)注，成為繼Turbo碼后信道編碼界的又一研究熱點(diǎn)。

校驗(yàn)矩陣從根本上決定了LDPC的糾錯(cuò)性能。國(guó)內(nèi)外學(xué)者提出多種校驗(yàn)矩陣構(gòu)造方法，其中基于原模圖的構(gòu)造方法具有許多優(yōu)點(diǎn)。由同一原模圖擴(kuò)展構(gòu)造的任意長(zhǎng)度的LDPC都具有類(lèi)似的結(jié)構(gòu)，其性能上限取決于原模圖，可以通過(guò)密度演進(jìn)算法或外部信息轉(zhuǎn)移圖分析計(jì)算門(mén)限值。對(duì)于原模圖設(shè)計(jì)，文獻(xiàn)[1]提出用模擬退火法優(yōu)化原模圖，文獻(xiàn)[2]構(gòu)造了大量性能逼近Shannon限的原模圖。但是，一個(gè)好的原模圖并非意味著所構(gòu)造出來(lái)的LDPC必然具有優(yōu)異的性能。實(shí)際上，擴(kuò)展方法不僅影響碼的性能，而且還決定了編譯碼器的硬件實(shí)現(xiàn)復(fù)雜度。因此，以降低譯碼門(mén)限和誤碼平層為目標(biāo)，本文提出了一種基于原模圖擴(kuò)展構(gòu)造QC-LDPC的方法。

2 原模圖與LDPC

LDPC是由稀疏奇偶校驗(yàn)矩陣定義的一種線(xiàn)性分組碼，其校驗(yàn)矩陣可以用圖來(lái)表示，稱(chēng)為T(mén)anner圖，如圖1所示。Tanner圖是一種雙向圖，由G＝｛（V，E）｝定義，其中V是節(jié)點(diǎn)的集合，（V＝Vb∪Vc），E是節(jié)點(diǎn)之間相連的邊的集合。對(duì)于維數(shù)為M×N的校驗(yàn)矩陣，Vb＝（v0，v1，…，vN-1）稱(chēng)為變量節(jié)點(diǎn)；Vc＝（c0，c1，…，cM-1）稱(chēng)為校驗(yàn)節(jié)點(diǎn)。

圖1 校驗(yàn)矩陣及其對(duì)應(yīng)的Tanner圖Fig.1 Parity check matrix and Tanner graph

圍長(zhǎng)是影響LDPC糾錯(cuò)性能的一個(gè)重要參數(shù)，雖然構(gòu)造一個(gè)最大可能?chē)L(zhǎng)的Tanner圖是一個(gè)非常難的組合問(wèn)題，但是構(gòu)造一個(gè)具有相對(duì)較大圍長(zhǎng)且計(jì)算復(fù)雜度較低的次優(yōu)算法還是存在的，漸進(jìn)邊增長(zhǎng)（PEG）算法是具有此性能的一個(gè)常用算法[3]。Tian等人發(fā)現(xiàn)，LDPC的誤碼平臺(tái)不完全由圍長(zhǎng)決定，更主要的是和環(huán)路的連通度有關(guān)，為此提出了近似環(huán)路外信息度（ACE）算法[4]。ACE算法和PEG算法相比，稍許損失了編碼增益，但降低了誤碼平層。ACE測(cè)度是用來(lái)度量環(huán)路連通性的參數(shù)，一個(gè)環(huán)的ACE測(cè)度定義為

式中k為環(huán)路上變量節(jié)點(diǎn)的個(gè)數(shù)；di為變量節(jié)點(diǎn)i的度數(shù)。

圖1顯示了一個(gè)長(zhǎng)度為8的環(huán)（v2→c1→v8→c5→v4→c6→v6→c3→v2），其中v2、v4、v6和v8是環(huán)上的變量節(jié)點(diǎn)，該環(huán)路的ACE測(cè)度LACE為0。

原模圖類(lèi)似于節(jié)點(diǎn)數(shù)目較少的Tanner圖，但其上允許存在重邊。在擴(kuò)展構(gòu)造LDPC時(shí)，先將原模圖復(fù)制若干遍，將每個(gè)副本稱(chēng)為一個(gè)子圖，再將處于不同子圖中的邊進(jìn)行置換和擾序，使不同子圖相互連接起來(lái)，所得到的新Tanner圖可確定一個(gè)LDPC。在原模圖的擴(kuò)展過(guò)程中，邊置換方式的不同將決定所得新Tanner圖中環(huán)長(zhǎng)及環(huán)與周邊節(jié)點(diǎn)的連通性，從而影響LDPC糾錯(cuò)性能；另一方面，置換方式還將決定所得LDPC是隨機(jī)的還是結(jié)構(gòu)化的，從而影響編譯碼器的實(shí)現(xiàn)復(fù)雜度。

3 原模圖擴(kuò)展算法

對(duì)于節(jié)點(diǎn)間存在重邊的原模圖需要進(jìn)行兩步擴(kuò)展，第一步擴(kuò)展用于去除節(jié)點(diǎn)間的重邊，而第二步擴(kuò)展則是為了使最終的校驗(yàn)矩陣具有準(zhǔn)循環(huán)結(jié)構(gòu)。為方便敘述，下文中以1／2碼率的AR4JA原模圖[2]為例進(jìn)行說(shuō)明，其結(jié)構(gòu)如圖2所示。其中，黑實(shí)心圓代表變量節(jié)點(diǎn)，帶加號(hào)的圓代表校驗(yàn)節(jié)點(diǎn)，空心圓代表刪余的變量節(jié)點(diǎn)。該原模圖對(duì)應(yīng)的矩陣表達(dá)式為

圖2 碼率1／2AR4JA LDPC原模圖Fig.2 Protograph for rate 1／2 AR4JA LDPC

3.1 算法1——原模圖的PEG去重邊擴(kuò)展

第一步擴(kuò)展目的是去除節(jié)點(diǎn)間的重邊，基本思想是先將原模圖擴(kuò)展L（L大于等于最大重邊數(shù)）倍，然后進(jìn)行邊置換操作。為了繼承原模圖的性能特性，邊置換只能發(fā)生在同一節(jié)點(diǎn)擴(kuò)展出來(lái)的L個(gè)節(jié)點(diǎn)（變量節(jié)點(diǎn)或者校驗(yàn)節(jié)點(diǎn)）之間。由于L不小于原模圖中的最大重邊數(shù)，只要置換得當(dāng)就能保證擴(kuò)展出來(lái)的的Tanner圖中不再存在重邊。在擴(kuò)展過(guò)程中采用PEG算法，使局部圍長(zhǎng)最大化。但是，與原PEG算法不同的是，擴(kuò)展過(guò)程中要受到上述約束條件的制約。

假設(shè)基矩陣的行數(shù)和列數(shù)分別為M和N，Hs1為第一步擴(kuò)展后的矩陣。原模圖的第一步擴(kuò)展算法描述如下：

初始化：基矩陣行號(hào)i＝0；基矩陣列號(hào)j＝1；擴(kuò)展倍數(shù)計(jì)數(shù)s＝1；Hs1＝0；對(duì)矩陣Hs1的變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)進(jìn)行編號(hào) （分別為1～LN和1～LM）。

1）如果i＝M且s≠L，則i＝1、s＝s＋1，跳到第2）步；如果i＝M且s＝L，則i＝1、j＝j(luò)＋1、s＝1，跳到第2）步；如果i≠M(fèi)，則i＝i＋1，跳到第2）步；如果i＝M、j＝N且s＝L，跳到第6）步。

2）令e＝Hbase（i，j），如果e≠0，則執(zhí)行第3）步；否則，跳到第1）步。

3）從矩陣Hs1編號(hào)為（i-1）L＋1～iL的校驗(yàn)節(jié)點(diǎn)中，選擇一個(gè)行重最小的與變量節(jié)點(diǎn)（j-1）L＋s相連。執(zhí)行第4）步。

4）e＝e-1。如果e＞0，則執(zhí)行第5）步；否則，跳到第1）步。

5）對(duì)矩陣Hs1對(duì)應(yīng)的Tanner圖從變量節(jié)點(diǎn)（j-1）L＋s進(jìn)行分層展開(kāi)[3]，直到展開(kāi)圖中校驗(yàn)節(jié)點(diǎn)停止增長(zhǎng)或者展開(kāi)圖中已經(jīng)包含校驗(yàn)節(jié)點(diǎn)（i-1）L＋1～iL，展開(kāi)終止。如果展開(kāi)終止時(shí)，展開(kāi)圖中包含了編號(hào)（i-1）L＋1～iL的全部校驗(yàn)節(jié)點(diǎn)，則從其中選擇一個(gè)最后新加入到展開(kāi)圖且行重最小的節(jié)點(diǎn)與變量節(jié)點(diǎn)（j-1）L＋s相連；否則，從編號(hào)為（i-1）L＋1～iL且沒(méi)有加入展開(kāi)圖的校驗(yàn)節(jié)點(diǎn)中，選擇一個(gè)行重最小的與變量節(jié)點(diǎn)（j-1）L＋s相連。跳到第4）步。

6）輸出矩陣Hs1，程序終止。

盡管在第一步擴(kuò)展中采用了PEG算法，但由于擴(kuò)展倍數(shù)較小，矩陣Hs1對(duì)應(yīng)Tanner圖中仍然存在大量的小環(huán)，且擴(kuò)展出來(lái)的矩陣是非結(jié)構(gòu)化的。

3.2 算法2——基于環(huán)檢測(cè)和ACE測(cè)度的準(zhǔn)循環(huán)擴(kuò)展

為了得到準(zhǔn)循環(huán)結(jié)構(gòu)的LDPC，需要對(duì)Hs1進(jìn)行第二步擴(kuò)展。本算法用維數(shù)為V×V（V取決于碼長(zhǎng)和第一步擴(kuò)展倍數(shù)L）的零矩陣、置換矩陣（單位矩陣及其移位矩陣）分別替換矩陣Hs1中的元素0和1。在擴(kuò)展過(guò)程中，采用PEG算法思想，使局部圍長(zhǎng)最大化。只要置換矩陣的偏移量取值得當(dāng)，就能消除原矩陣Hs1中的短環(huán)。舉例：假設(shè)對(duì)矩陣Hs1進(jìn)行倍數(shù)為3的準(zhǔn)循環(huán)擴(kuò)展，對(duì)于Hs1對(duì)應(yīng)Tanner圖中的一個(gè)長(zhǎng)度為4的短環(huán)，根據(jù)置換矩陣偏移量取值的不同，擴(kuò)展過(guò)程中可能存在多種替換方式，圖3為其中兩種可能情況。在圖3（a）中，替換矩陣Hs1中4個(gè)元素1的置換矩陣偏移量分別為0-1-2-1，擴(kuò)展后的矩陣中依然存在長(zhǎng)度為4的短環(huán)；在圖3（b）中，置換矩陣偏移量分別為0-1-1-1，擴(kuò)展后得到1個(gè)長(zhǎng)度為12的環(huán)路。文獻(xiàn)[5]中給出了一般結(jié)論：

定理 假設(shè)矩陣Hs1對(duì)應(yīng)Tanner圖中存在長(zhǎng)度為k的一條封閉路徑：（m1，n1）→（m2，n1）→（m2，n2）→ … → （mk，nk）→ （m1，nk），其中1≤i≤k，（mi，ni）為Hs1中的某個(gè)非零元素。經(jīng)準(zhǔn)循環(huán)擴(kuò)展后，路徑上非零元素對(duì)應(yīng)置換矩陣的偏移量依次為s1→s2→…→sk-1→sk。如果滿(mǎn)足條件

式中r是滿(mǎn)足上述條件的最小正整數(shù)，則擴(kuò)展后的準(zhǔn)循環(huán)矩陣中必存在長(zhǎng)度為rk的環(huán)。

圖3 不同置換矩陣擴(kuò)展出來(lái)的校驗(yàn)矩陣Fig.3 Parity-check matrices based on different permutation matrices

對(duì)于給定的擴(kuò)展因子V，要確定矩陣Hs1中非零元素對(duì)應(yīng)置換矩陣的偏移量使QC-LDPC圍長(zhǎng)最大化是非常困難的。這里仍然采用PEG算法思想，逐個(gè)搜索每個(gè)置換矩陣的局部最優(yōu)偏移量，同時(shí)對(duì)環(huán)路計(jì)算ACE測(cè)度，從環(huán)長(zhǎng)和環(huán)的連通性?xún)煞矫鎸?duì)環(huán)路進(jìn)行約束。由于大環(huán)對(duì)碼性能影響較小，為了降低搜索算法的時(shí)間復(fù)雜度，可以預(yù)設(shè)一個(gè)最大搜索路徑長(zhǎng)度Kmax，當(dāng)路徑長(zhǎng)度超過(guò)該值后便停止繼續(xù)搜索；用Hs2記錄第二步擴(kuò)展后的矩陣，其各元素初始值預(yù)置為-1；用矩陣Hs＿temp記錄矩陣Hs1中已經(jīng)完成準(zhǔn)循環(huán)擴(kuò)展的部分，其各元素初始值預(yù)設(shè)為0。第二步擴(kuò)展算法描述如下：

初始化 行號(hào)i＝1，列號(hào)j＝1；定義數(shù)組A和Β分別記錄不同偏移量下的最小環(huán)長(zhǎng)和最小環(huán)路ACE測(cè)度。

1）逐列從上到下搜索矩陣Hs1，同時(shí)行號(hào)i（1≤i≤ML）、列號(hào)j（1≤j≤NL）也相應(yīng)地變化。如果已經(jīng)搜索完畢，則跳到第5）步；否則，執(zhí)行第2）步。

2）若i＝1或j＝1，則Hs2（i，j）＝δ、Hs＿temp（i，j）＝Hs1（i，j），其中δ為 [0，V-1]范圍內(nèi)取值的隨機(jī)整數(shù)（δ也可以取一個(gè)固定的值），然后跳到第1）步；否則，令Hs＿temp（i，j）＝Hs1（i，j）、v＝0、A[v]＝∞、B[v]＝∞，然后執(zhí)行第3）步。

3）令Hs2（i，j）＝v。在矩陣Hs＿temp對(duì)應(yīng)的Tanner圖上，搜索從校驗(yàn)節(jié)點(diǎn)i、變量節(jié)點(diǎn)j往下延伸的所有路徑，用變量k記錄每條路徑的長(zhǎng)度（對(duì)于每條路徑，當(dāng)k＞Kmax或者路徑無(wú)法繼續(xù)延伸后停止）。如果沒(méi)有止于校驗(yàn)節(jié)點(diǎn)i的封閉路徑，直接跳到第4）步；否則，對(duì)于每條止于校驗(yàn)節(jié)點(diǎn)i的封閉路徑，按照公式（3）計(jì)算準(zhǔn)循環(huán)擴(kuò)展后的環(huán)路長(zhǎng)度p并按照公式（1）計(jì)算其ACE測(cè)度值q。如果p＜A[v]，令A(yù)[v]＝p；如果q＜B[v]，令B[v]＝q。搜索完成后，執(zhí)行第4）步。

4）如果v＜V-1，則令v＝v＋1，跳到第3）步；否則，對(duì)數(shù)組A進(jìn)行排序，得到A中最大值對(duì)應(yīng)的序號(hào)t（若A中存在多個(gè)相同的最大值，則比較對(duì)應(yīng)數(shù)組Β中的元素，選擇數(shù)值大的元素對(duì)應(yīng)的序號(hào)），令Hs2（i，j）＝t，跳到第1）步。

5）輸出矩陣Hs2。

對(duì)于不存在重邊的原模圖，不需要進(jìn)行第一步擴(kuò)展，直接對(duì)原模圖進(jìn)行第二步擴(kuò)展便能得到QC-LDPC。對(duì)于矩陣Hs2中的任意元素，若Hs2（i，j）＝-1，則用V×V的零矩陣替代；否則，用偏移量為Hs2（i，j）、維數(shù)為V×V的置換矩陣替代，由此得到QC-LDPC校驗(yàn)矩陣。

4 性能仿真

利用上述算法，基于AR4JA原模圖構(gòu)造了兩個(gè)QC-LDPC，碼率都為0.5，碼長(zhǎng)分別為2 048和8 192。為了降低搜索算法的時(shí)間復(fù)雜度，最大搜索路徑長(zhǎng)度設(shè)置為16。仿真條件：加性高斯白噪聲信道（AWGN）和乘譯碼算法（SPA），最大迭代次數(shù)為200。在CCSDS 131.1-O-2深空通信標(biāo)準(zhǔn)中，采用的便是AR4JA原模圖擴(kuò)展構(gòu)造的QC-LDPC，具有優(yōu)異的性能[6]。圖4中給出了性能仿真曲線(xiàn)，可以看出誤碼率為10-6時(shí)，兩個(gè)碼的譯碼門(mén)限分別為1.3dB和1.9dB，與CCSDS 131.1-O-2標(biāo)準(zhǔn)上的相同碼率、碼長(zhǎng)的碼性能基本一致（標(biāo)準(zhǔn)上對(duì)應(yīng)碼性能分別為1.2dB和1.9dB）。

圖4 誤碼性能仿真Fig.4 BER versus SNR simulation results

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

經(jīng)過(guò)參數(shù)優(yōu)化得到的原模圖，為構(gòu)造性能優(yōu)異的LDPC創(chuàng)造了前提條件，但其最終性能仍然受制于擴(kuò)展算法。本文提出了一種基于原模圖擴(kuò)展構(gòu)造QC-LDPC的方法，在擴(kuò)展過(guò)程中，以環(huán)長(zhǎng)和環(huán)路ACE測(cè)度最大化為目標(biāo)，通過(guò)搜索算法規(guī)避連通性差的短環(huán)。由于參數(shù)優(yōu)化是依次進(jìn)行的，所述算法在環(huán)長(zhǎng)和ACE測(cè)度方面不是全局最優(yōu)的，但具有局部最優(yōu)性。仿真結(jié)果表明，采用該方法構(gòu)造的LDPC，在譯碼門(mén)限和錯(cuò)誤平層兩方面都具有良好的表現(xiàn)，證明了所述算法的有效性。同時(shí)，所構(gòu)造的LDPC具有準(zhǔn)循環(huán)結(jié)構(gòu)，適于工程實(shí)現(xiàn)。但是，在準(zhǔn)循環(huán)擴(kuò)展過(guò)程中，參數(shù)優(yōu)化次序?qū)Υa性能的影響，仍然是一個(gè)需要進(jìn)一步研究的問(wèn)題。

[1]THORPE JEREMY.Analysis and design of protograph based LDPC codes and ensembles [D].Pasadena：California Institute of Technology，2005.

[2]DARIUSH DIVSALAR，SAMUEL DOLINAR，CHRISTOPHER R JONES，et al.Capacity-approaching protograph codes[J].IEEE Journal on Selected Aeras in Communications，2009，27 （6）：876-888.

[3]HU XIAOYU，ELEFTHERIOU EVANGELOS，DIETER MICHAEL ARNOLD.Progressive edge-growth tanner graphs[C].IEEE GlobeCom，2001，2：995-1001.

[4]TIAN TAO，JONES R CHRISTOPHER，VILLASENOR D JOHN，et al.Selective avoidance of cycles in irregular LDPC code construction [J].IEEE Transactions on Communications，2004，52（8）：1242-1247.

[5]SEHO MYUNG，KYEONGCHEOL YANG，JAEVOEL KIM.Quasi-cyclic LDPC codes for fast encoding [J].IEEE Transactions on Information Theory，2005，51（8）：1788-1793.

[6]THE CONSULTATIVE COMMITTEE FOR SPACE DATA SYSTEMS.Low density parity check codes for use in near-earth and deep space applications [S].CCSDS 131.1-O-2，Orange Book，Issue 2，Washington，DC，2007.