基于拉丁方陣的準(zhǔn)循環(huán)LDPC碼構(gòu)造

陳集煒，趙澤茂，包建榮

(杭州電子科技大學(xué)通信工程學(xué)院，浙江杭州310018)

0 引言

低密度奇偶校驗(yàn)碼(Low-Density Parity-Check，LDPC)［1］。證明其具有逼近香農(nóng)限的好碼［2］。自此，LDPC碼開(kāi)始成為信道編碼的研究熱點(diǎn)。近年來(lái)對(duì)LDPC碼的構(gòu)造方法研究逐漸轉(zhuǎn)向準(zhǔn)循環(huán)(Quasi-Cyclic，QC)LDPC碼。QC-LDPC碼是結(jié)構(gòu)化LDPC碼的一類。該類LDPC碼性能優(yōu)良、編譯碼復(fù)雜度較非結(jié)構(gòu)化碼低而受到研究者的關(guān)注。QC-LDPC碼因其半結(jié)構(gòu)化分塊矩陣結(jié)構(gòu)，便于硬件實(shí)現(xiàn)，同時(shí)具有優(yōu)異的糾錯(cuò)性能，提出了一種LDPC碼編碼方法［3］。本文主要參考該LDPC碼的基于拉丁方陣的三元系構(gòu)造方法，提出了一種新的準(zhǔn)循環(huán)LDPC碼構(gòu)造方法。方法是一種“Block-in-Block”的結(jié)構(gòu)化構(gòu)造方法，基矩陣采用拉丁方陣的Block構(gòu)造思路，通過(guò)設(shè)定合適的移位系數(shù)，去除校驗(yàn)矩陣的6環(huán)。而且，它還可以構(gòu)造任意碼率、碼長(zhǎng)的QC-LDPC碼，也更易于實(shí)現(xiàn)。

1 基矩陣的構(gòu)造

1.1 基于拉丁方陣的構(gòu)造方法

Milenkovic所提的編碼算法利用斯坦納三元系(Steiner Triple System，STS)，基于等冪、對(duì)稱的拉丁方陣特性，并擁有結(jié)構(gòu)化的構(gòu)造［3］。Steiner三元系的定義:V是一個(gè)v元集合，B是V三元子集構(gòu)成的集族。如果V中任意兩個(gè)互異元素恰同時(shí)含在B的一個(gè)元中，則稱(V，B)為v階的Steiner三元系。拉丁方陣是一個(gè)m維方陣，其中每行每列都包含數(shù)集{1，2，…，m}。等冪的拉丁方陣是指拉丁方陣的(i，i)位置的元素為i，即方陣的主對(duì)角線上的元素為1，2，…，m的順序排列;對(duì)稱的拉丁方陣是指方陣的元素沿主對(duì)角線對(duì)稱。

STS的構(gòu)造方法具有嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)結(jié)構(gòu):拉丁方陣的維數(shù)為2m+1;對(duì)應(yīng)構(gòu)造的LDPC碼的校驗(yàn)節(jié)點(diǎn)數(shù)則為6m+3;對(duì)應(yīng)的三元集數(shù)目為(3m+1)(2m+1)=(v(v－1))/6。校驗(yàn)矩陣的每列擁有2m+1個(gè)矩陣塊，每行擁有m(2m+1)個(gè)矩陣塊。由拉丁方陣得來(lái)的三元集被分成類型1與類型2兩類［3］，第1類在LDPC碼的校驗(yàn)矩陣中為維數(shù)為3的單位矩陣I，第2類則為右移位一位的維數(shù)為3的單位矩陣

1.2 構(gòu)造方法性能分析

根據(jù)Steiner三元系定義，V中任意兩個(gè)互異元素只同時(shí)含在B的一個(gè)元中。故文獻(xiàn)3構(gòu)造的校驗(yàn)矩陣不存在4環(huán)。文獻(xiàn)3同時(shí)提出一種減小6環(huán)數(shù)目的方法:通過(guò)刪除擁有最大6環(huán)數(shù)的列，來(lái)減少6環(huán)的數(shù)目。該方法具有一定的改進(jìn)，但還存在不足。它僅是減小6環(huán)數(shù)，而不能完全去除6環(huán)。通過(guò)刪除列來(lái)減少6環(huán)的方法，無(wú)法構(gòu)造碼率靈活與性能優(yōu)異并重的LDPC碼。本文在該構(gòu)造方法引入QCLDPC碼的特性，改進(jìn)了該方法的不足。

2 構(gòu)造QC-LDPC碼

常見(jiàn)的QC-LDPC碼又稱為塊狀LDPC(Block-LDPC)碼。塊狀LDPC碼的校驗(yàn)矩陣H可表示如下所示。其中，I表示A×A的單位矩陣，又稱循環(huán)置換矩陣;pi，j是其循環(huán)移位系數(shù)。若pi，j=－1，代表I(－1)是一個(gè)A×A的全零矩陣;若pi，j≥0，則代表單位矩陣I右移pi，j位。QC-LDPC碼的校驗(yàn)矩陣H，可用簡(jiǎn)化的循環(huán)移位系數(shù)矩陣等價(jià)表示。矩陣P中的每個(gè)元素pi，j對(duì)應(yīng)校驗(yàn)矩陣H中的每個(gè)循環(huán)置換矩陣的循環(huán)移位系數(shù)。

QC-LDPC碼的校驗(yàn)矩陣H中所存在的長(zhǎng)度為2l的塊狀環(huán)路，可用循環(huán)移位系數(shù)等價(jià)表示為:pi1，j1其中，pia，ja與 pia+1，ja+1在校驗(yàn)矩陣 H 的同一行或者同一列;pia，ja與 pia+2，ja+2不一定在同一行或同一列;a的取值范圍為0≤a≤2l－2的任意值。

性質(zhì)一［4］QC-LDPC碼的校驗(yàn)矩陣H對(duì)應(yīng)的Tanner圖中存在一條長(zhǎng)為2l的環(huán)路的充要條件是:環(huán)路上各基矩陣節(jié)點(diǎn)的循環(huán)移位系數(shù)滿足:

而通過(guò)構(gòu)造合適的移位系數(shù)矩陣，可以優(yōu)化校驗(yàn)矩陣的環(huán)長(zhǎng)，去除短環(huán)，使環(huán)長(zhǎng)達(dá)到8環(huán)及以上。本算法構(gòu)造的基矩陣不包含4環(huán)，所以僅需刪去6環(huán)即可。

算法具體步驟如下:

(1)把生成的基矩陣Hb中的0元素置為－1，1元素置0，得到初始移位系數(shù)矩陣P0;

(2)初始移位系數(shù)矩陣P0的前3行的0元素保持不變，第4—6行的0元素，每行按正整數(shù)的順序賦值，即分別賦值為1，2，3，…，p(1≤p≤A)，前6行的－1元素保持不變;

(3)從第7行開(kāi)始，用式2檢測(cè)0元素與以上幾行的非零元素是否形成了小于8的短環(huán)。若沒(méi)有則保持不變，否則生成一個(gè)取值范圍為1≤p≤A的隨機(jī)數(shù)p替換0元素;

(4)新生成的移位矩陣若滿足式2，則產(chǎn)生另外一個(gè)不同的隨機(jī)數(shù)進(jìn)行替換，直至消去小于8環(huán)的短環(huán)。若在一定的次數(shù)內(nèi)無(wú)法消去短環(huán)，則退回前3行，重新選擇移位系數(shù);在允許的一定次數(shù)內(nèi)仍然無(wú)法消去短環(huán)，則退回前6行;并以此類推，直至得到矩陣P;

(5)將移位系數(shù)矩陣P的－1元素與非負(fù)元素分別用維數(shù)為A的全零矩陣OA與向右移位pi，j位的維數(shù)為A的單位矩陣替換，即得所需的校驗(yàn)矩陣H。

該移位系數(shù)構(gòu)造法與傳統(tǒng)的隨機(jī)構(gòu)造法不同處在于:因基矩陣是分塊的矩陣，在選擇移位系數(shù)的時(shí)，每塊可選擇相同的移位系數(shù)。

3 仿真及分析

3.1 性能仿真

根據(jù)上述編碼構(gòu)造原理，構(gòu)造了不同碼長(zhǎng)的LDPC碼，并與一些經(jīng)典的隨機(jī)構(gòu)造LDPC碼的誤碼性能進(jìn)行了仿真比較。仿真參數(shù)如下:信道為二元輸入高斯白噪聲信道;譯碼算法采用置信傳播(Belief-Propagation，BP)譯碼算法;最大迭代次數(shù)為50次;每個(gè)信噪比仿真誤碼達(dá)200個(gè)碼字時(shí)，仿真結(jié)束。

仿真1 用本算法分別構(gòu)造碼長(zhǎng)為480bit、990bit，碼率都為1/2的LATIN QC-LDPC碼，每個(gè)移位矩陣的大小分別為16×16與33×33，校驗(yàn)矩陣列重為3;同時(shí)構(gòu)造對(duì)照的參數(shù)相同的PEG-LDPC碼，進(jìn)行局部圍長(zhǎng)仿真比較，得仿真結(jié)果如圖1所示。

仿真2 用本算法分別構(gòu)造碼長(zhǎng)為480bit、990bit，碼率都為1/2的LATIN QC-LDPC碼，每個(gè)移位矩陣的大小分別為16×16與33×33，校驗(yàn)矩陣列重為3;同時(shí)構(gòu)造對(duì)照的參數(shù)相同的PEG-LDPC碼，進(jìn)行誤碼率仿真比較。仿真結(jié)果如圖2所示。

圖1 局部圍長(zhǎng)仿真

圖2 誤碼率仿真對(duì)比圖

3.2 仿真結(jié)果分析

PEG算法一直被認(rèn)為是二元有限碼長(zhǎng)下次優(yōu)的LDPC碼構(gòu)造方法［5］，故采用PEG算法與本算法對(duì)比具較強(qiáng)說(shuō)服力。圖1中的仿真結(jié)果表明，當(dāng)碼長(zhǎng)為480bit時(shí)，LATIN QC-LDPC碼平均圍長(zhǎng)與PEG算法構(gòu)造的碼字基本相等;而當(dāng)碼長(zhǎng)為990bit時(shí)，LATIN QC-LDPC碼因?yàn)槠銪lock-in-Block的結(jié)構(gòu)，平均圍長(zhǎng)不變，而PEG算法構(gòu)造的碼字的平均圍長(zhǎng)則大大大于Block-in-Block的結(jié)構(gòu)。

圖2中的仿真結(jié)果也表明了在碼長(zhǎng)為990bit時(shí)，PEG-LDPC碼的誤碼性能稍優(yōu)于LATIN QC-LDPC碼:在誤碼率為10－5的數(shù)量級(jí)時(shí)，PEGPC-LDPC碼比LATIN QC-LDPC碼只有約0.1dB的增益;但在碼長(zhǎng)為480bit時(shí)，本算法構(gòu)造的LATIN QC-LDPC碼性能優(yōu)于PEG-LDPC碼。且在誤碼率為10－6數(shù)量級(jí)時(shí)，LATIN QC-LDPC碼比PEGPC-LDPC碼約有0.15dB的增益。PEG-LDPC碼是隨機(jī)構(gòu)造的碼字，而本文構(gòu)造的LDPC碼是“Block-in-Block”的結(jié)構(gòu)，具有準(zhǔn)循環(huán)特性，更易于硬件實(shí)現(xiàn)。

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

本文參考了拉丁方陣及Steiner三元系LDPC編碼構(gòu)造法，提出了一種QC-LDPC碼的構(gòu)造方法。仿真結(jié)果表明，本算法在構(gòu)造的短碼與PEG算法構(gòu)造的碼字相比，性能更好，且在誤碼率為10－6數(shù)量級(jí)時(shí)無(wú)明顯的誤碼平底。同時(shí)，本算法所構(gòu)造的QC-LDPC碼，作為一種結(jié)構(gòu)化構(gòu)造的編碼方法，非常有利于實(shí)際通信系統(tǒng)的硬件實(shí)現(xiàn)。

［1］ Gallager R G.Low density parity check codes［M］.Cambridge:MIT Press，1963:21 －28.

［2］ Mackay D J C，Neal R M.Near Shannon limit performance of low-density parity-check codes［J］.Electronics Letters，1996，32(18):1 645 －1 646.

［3］ Milenkovic O，Laendner S.Analysis of the cycle-structure of LDPC codes based on Latin squares［C］.Paris:Proc of IEEE International Conf on，2004:777 －781.

［4］ Myung S，Yang K，Kim J.Quasi-cyclic LDPC codes for fast encoding［J］.IEEE Trans on inf Theory，2005，51(8):2 894 －2 901.

［5］ Hu Xiao-Yu，Evangelos Eleftheriou，Dieter M Arnold.Regular and irregular progressive edge-growth tanner graphs［J］.IEEE Trans Comm，2005，51(1):386 －398.