基于結(jié)構(gòu)圖設(shè)計(jì)LDPC碼及其性能仿真

張凱　楊勇

摘 要： 提出了使用結(jié)構(gòu)圖設(shè)計(jì)列重為3的正則LDPC校驗(yàn)矩陣。所設(shè)計(jì)出的校驗(yàn)矩陣具有較大的圍長(zhǎng)，并且可以改變碼長(zhǎng)和碼率。這些碼可以很好的使用在通信和數(shù)據(jù)存儲(chǔ)領(lǐng)域。最后對(duì)這些設(shè)計(jì)出的LDPC碼進(jìn)行了計(jì)算機(jī)仿真，仿真的數(shù)據(jù)結(jié)果表明：設(shè)計(jì)出的碼在加性白高斯噪聲信道下比隨機(jī)產(chǎn)生的LDPC碼有著更為優(yōu)良的性能。

關(guān)鍵詞： 正則LDPC碼； 校驗(yàn)矩陣； 數(shù)據(jù)存儲(chǔ)； 計(jì)算機(jī)仿真

中圖分類號(hào)： TN911.72?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）01?0066?03

Abstract： The regular low?density parity?check （LDPC） check matrix with column weight j=3 designed with structure charts is proposed in this paper. The check matrix has large girth， can change code length and code rate. These codes may be used in the fields of communications and data storage. The computer simulation for LDPC codes that the authors designed was performed. The simulation results show that the designed codes have better bit?error?rate decoding performance and lower error floors in additive white Gaussian noise channels than those of LDPC codes generated randomly.

Keywords： regular LDPC code； check matrix； data storage； computer simulation

0 引 言

低密度奇偶校驗(yàn)碼（Low?Density Parity?Check codes，簡(jiǎn)稱LDPC碼）是一種近年來(lái)發(fā)現(xiàn)可逼近香農(nóng)限、糾錯(cuò)性能空前優(yōu)良的糾錯(cuò)碼，該碼是Gallager于1962年提出的一種基于稀疏校驗(yàn)矩陣的分組碼，亦稱Gallager碼[1]。由于受當(dāng)時(shí)的計(jì)算機(jī)仿真水平以及硬件實(shí)現(xiàn)能力的局限，LDPC碼的優(yōu)良性能一直未能被真正挖掘，以致被忽視了近40年。近年來(lái)，在Turbo碼研究獲得巨大成功的帶動(dòng)下，Mackay等人又重新研究了LDPC碼，發(fā)現(xiàn)采用和?積譯碼算法時(shí)[2]，其性能十分逼近香農(nóng)限，在譯碼復(fù)雜度低于Turbo碼的同時(shí)極具高速譯碼的潛力等特性，從而激起了人們對(duì)LDPC碼研究的熱潮。LDPC碼成為當(dāng)今信道編碼領(lǐng)域最矚目的熱點(diǎn)。

近年來(lái)在如何設(shè)計(jì)出較大圍長(zhǎng)的LDPC碼領(lǐng)域開(kāi)展了許多研究工作，Kou，Lin，and Fossorier，提出了有限幾何的方法構(gòu)造圍長(zhǎng)為6的LDPC碼[3]，Hu等學(xué)者在文獻(xiàn)[4]中提出了一種基于計(jì)算機(jī)搜索LDPC碼的構(gòu)造方法，稱為漸進(jìn)增邊（Progressive?Edge?Growth，PEG）構(gòu)造法。近年來(lái)又有學(xué)者提出了基于有限域構(gòu)造多元LDPC碼的方法[5]。本文提出了利用結(jié)構(gòu)圖設(shè)計(jì)性能優(yōu)良并且具有較大圍長(zhǎng)的LDPC碼的方法。

1 LDPC碼的結(jié)構(gòu)

LDPC碼最初是用一個(gè)稀疏的校驗(yàn)矩陣來(lái)定義的線性分組碼，校驗(yàn)矩陣[H]中所有元素值都為二進(jìn)制數(shù)，且每行及每列元素中1的個(gè)數(shù)遠(yuǎn)小于碼長(zhǎng)，因此稱之為低密度校驗(yàn)碼。LDPC碼有兩類，一類是正則LDPC碼，其校驗(yàn)矩陣中具有相同的行重和列重；另一類是非正則LDPC碼，這類碼的校驗(yàn)矩陣的行重和列重不盡相同。把一個(gè)[（N，K）]-LDPC碼定義為一個(gè)[M×N]的校驗(yàn)矩陣[H，]其中[K=N-M，]碼率為[R=kN；]若[H]為非滿秩矩陣，則[K>N-M，]其糾錯(cuò)能力也隨之下降。LDPC碼的校驗(yàn)矩陣[H]可以用二部圖來(lái)表示，假設(shè)二部圖[G]中有[N]個(gè)左節(jié)點(diǎn)（稱為信息節(jié)點(diǎn)）和[M]個(gè)右節(jié)點(diǎn)（稱為校驗(yàn)節(jié)點(diǎn)），則一個(gè)二部圖就可以生成一個(gè)長(zhǎng)為[N，]維數(shù)至少為[N-M]的線性分組碼。

該碼字中的[N]個(gè)碼字分別表示[N]個(gè)信息節(jié)點(diǎn)的數(shù)值（0或1），則一個(gè)碼組向量[x=（x1，x2，…，xn）]滿足這樣一個(gè)條件：任一校驗(yàn)節(jié)點(diǎn)的相鄰信息節(jié)點(diǎn)的數(shù)值和為0，如圖1所示。二部圖中的信息節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)之間的連線稱為邊（edge）。若第[j]個(gè)信息節(jié)點(diǎn)與第[i]個(gè)校驗(yàn)節(jié)點(diǎn)有邊相連接，則校驗(yàn)矩陣中的[H（i，j）=1，]否則為0。

2 LDPC碼的結(jié)構(gòu)圖

構(gòu)造的LDPC碼是基于幾何圖形的結(jié)構(gòu)圖，這里首先給出設(shè)計(jì)時(shí)所要用到的幾個(gè)定義，將校驗(yàn)節(jié)點(diǎn)[Ci（i=1，2，…，M）]作為集合[X，]對(duì)于列重為3的LDPC碼的校驗(yàn)矩陣每一列都構(gòu)成了一個(gè)由集合[X]中三個(gè)非元素組成的列三角，把這些由三角形所構(gòu)成的圖形叫做結(jié)構(gòu)圖，如圖2所示。

利用結(jié)構(gòu)圖可以很容易地判斷在LDPC校驗(yàn)矩陣[H]中是否存在短環(huán)。圍長(zhǎng)為4的短環(huán)是由在兩點(diǎn)間存在兩條連接線所構(gòu)成，圍長(zhǎng)為6的短環(huán)恰好構(gòu)成了一個(gè)三角形。如圖2所示，[△C2C4C6] 就構(gòu)成了一個(gè)圍長(zhǎng)為6的短環(huán)。為了將它和列三角區(qū)分開(kāi)來(lái)，把類似于[△C2C4C6]的三角形稱作循環(huán)三角。

圖3給出了一些可能存在的情況，在圖3中[△abf，][△bcd，][△def]都屬于列三角，而[△bdf]屬于循環(huán)三角，因?yàn)閇△bdf]的每一條邊都和其他的三角形所共用。對(duì)于圍長(zhǎng)為8的LDPC碼的結(jié)構(gòu)圖也有類似的定義，只是它的短環(huán)是由四邊形構(gòu)成的。在這里還要介紹有關(guān)斜 度以及可聯(lián)接斜度的概念。假設(shè)把校驗(yàn)點(diǎn)集合[X={a1，a2，…，ap，b1，b2，…，bp，c1，c2，…，cp}]分成三個(gè)子集[X0={a1，a2，…，ap}，][X1={b1，b2，…，bp}]和[X2={c1，c2，…，cp}，]把它們縱向排列，并從下到上依次標(biāo)明順序，如圖4所示。連接校驗(yàn)點(diǎn)[ai∈X0]和[bj∈X1]之間邊的斜度定義為[s=j-i。]在圖4中[a1]和[b5]之間的斜度為[s=+4，][b5]和[c4]之間的斜度為[s=-1。]

可聯(lián)接斜度是指，兩條斜度之間有著共同的校驗(yàn)點(diǎn)，這樣可以引入第三條斜度從而構(gòu)成三角形。例如，對(duì)于圖4中的[a1，b5]、[b5，c4]兩條斜度就構(gòu)成了可聯(lián)斜度，但是[a1，b5]、[b4，c3]就不能構(gòu)成可聯(lián)斜度，因?yàn)閮蓷l斜度之間沒(méi)有共同的校驗(yàn)點(diǎn)。把有著共同的校驗(yàn)點(diǎn)的斜度對(duì)所構(gòu)成的集合稱為可聯(lián)接斜度對(duì)集合[A。]

3 利用結(jié)構(gòu)圖設(shè)計(jì)LDPC碼

為了設(shè)計(jì)出圍長(zhǎng)為8的LDPC碼，必需排除圍長(zhǎng)為4和6的短環(huán)出現(xiàn)的可能。只要使每一條邊屬于惟一的一個(gè)列三角，那么就可以避免圍長(zhǎng)為4的短環(huán)出現(xiàn)，在結(jié)構(gòu)圖中可以很容易的實(shí)現(xiàn)。所以現(xiàn)在的問(wèn)題是如何排除圍長(zhǎng)為6的短環(huán)出現(xiàn)。

假設(shè)[c=3p，p]是任意正整數(shù)。同樣，把這些校驗(yàn)點(diǎn)平均分割成三個(gè)子集[X0，][X1]和[X2，]每個(gè)子集的元素個(gè)數(shù)都是[p。]將三個(gè)子集的元素縱向排列，并從下到上依次標(biāo)號(hào)（如圖4所示）。在構(gòu)造的過(guò)程中，只考慮在不同子集之間出現(xiàn)的邊的情況。在這里要引入邊集合的概念，邊集合[Si]代表了在相鄰子集[Xi]和[Xmod（i+1，3）]之間所有的邊，可以看出集合[Ai∈Si]。在計(jì)算邊集合[Si]中每一條邊的斜度都是以校驗(yàn)點(diǎn)集合[Xi]中的元素為參考點(diǎn)，可以證明在每一個(gè)集合[Si（i=0，1，2）]中的元素個(gè)數(shù)是相同的。為了避免在列重為3的高碼率LDPC碼中出現(xiàn)圍長(zhǎng)為6的短環(huán)，就要在校驗(yàn)點(diǎn)集合[Xi]中找到斜度對(duì)集合[Ai，]使得盡可能多的構(gòu)建出列三角，不出現(xiàn)循環(huán)三角。

定理1：在結(jié)構(gòu)圖中任何列三角或循環(huán)三角都是由處在不同集合[Si（i=0，1，2）]中的邊所構(gòu)成，邊的斜度分別為[s0，][s1，][s2，]且滿足[Mod（s0+s1+s2，p）=0。]

定理2：假設(shè)三個(gè)斜度對(duì)[s0，s1，s2]分別屬于集合[A0，][A1，][A2，]且[Mod（s0+s1+s2，p）=0，]那么所有這些斜度對(duì)能夠構(gòu)造出[p]個(gè)三角形，且任意兩個(gè)三角形不共享同一條邊。

例如，對(duì)于[p=2]來(lái)說(shuō)，在引入所有的斜度后只能構(gòu)成2個(gè)三角形，如圖5所示。在圖5（a）中如果再將點(diǎn)[a1，b2，c2]互相連接構(gòu)成三角形，那么在[△a1b2c2]與[△a1b1c2]之間有共同邊[a1c2，]它將引入圍長(zhǎng)為4的短環(huán)。在圖5（b）中如果再將點(diǎn)[a1，b1，c2]互相連接構(gòu)成三角形，那么新引入的三角形會(huì)在結(jié)構(gòu)圖上附加[△a2b1c2，]由于附加三角形的存在，它會(huì)構(gòu)成圍長(zhǎng)為6的短環(huán)，因?yàn)閇△a2b1c2]的三條邊分別和另外的3個(gè)三角形所共享。

有了以上兩條定理和先決條件，現(xiàn)在就可以構(gòu)造圍長(zhǎng)為8的LDPC碼。定義[B]為所有斜度對(duì)集合，并且把[Bi]稱作集合[Ai]的候選集。構(gòu)造過(guò)程如下：

（1） 初始化，令[Ai=Φ，i=0，1，2；]

（2） 在候選集[Bi（i=0，1）]中，分別選取一組斜度對(duì)[si1，] 令[s21=Mod（-s01-s11，p）]。將[si1]作為集合[Ai]的元素，并且將其從對(duì)應(yīng)的集合[Bi（i=0，1，2）]中刪除。設(shè)置[k=2；]

（3） 如果[B0]為空，跳轉(zhuǎn)至（9）； 否則在候選集[B0]中任意選取[s0k]作為集合[A0]的元素，并且將其從對(duì)應(yīng)的候選集[B0]中刪除；

（4） 如果存在某一數(shù)值[j][（1≤j≤k-1），]使得[sl∈A2，]則將[s0k]從集合[A0]中刪除，跳轉(zhuǎn)至（3）。在這里[sl=][Mod（-s0k-s1j，p）；]

（5） 如果[B1]為空，跳轉(zhuǎn)至9； 否則令[B′1=B1；]

（6） 如果[B′1]為空，則從集合[A0]中刪除[s0k，]跳轉(zhuǎn)至（3）。否則在[B′1]中任意選取[s1k，]將其作為集合[A1]的元素，并從集合[B′1]中刪除；

（7） 如果存在某一數(shù)值[j][（1≤j≤k-1）]，使得[sl∈A2]，則將[s1k]從集合[A1]、[B1]中刪除，跳轉(zhuǎn)至（6）；

（8） 令[s2k=Mod（-s0k-s1k，p）]，如果[s2k∈B2，]則將[s2k]從集合[B2]中刪除，并把它作為[A2]的元素，設(shè)置[k=k+1，]跳轉(zhuǎn)至（3）；否則跳轉(zhuǎn)至（6）；

（9） 結(jié)束。

集合[Ai]就是我們想要尋找的，它的維數(shù)是[Ns=k-1。]在以上的過(guò)程中，因?yàn)?個(gè)列三角是由不同斜度的邊所構(gòu)成，所有斜度構(gòu)成的列三角數(shù)目是[p]個(gè)，所以LDPC碼的碼長(zhǎng)就是[n=Ns×p，]碼率是[r=Ns×p-3pNs×p=][Ns-3Ns。]如果想要獲得不同的碼率，可以通過(guò)尋找斜度對(duì)來(lái)改變[Ns]的值。從上述關(guān)系可以得到碼長(zhǎng)和碼率之間的關(guān)系：[n=3p（1-r），]如圖6所示。例如，可以選取[p=77，]通過(guò)上述方法，可以得到碼長(zhǎng)為1 155，碼率為0.8的LDPC碼。

4 仿真結(jié)果與分析

用上述方法構(gòu)造出LDPC碼和用隨機(jī)方法構(gòu)造出的等長(zhǎng)等碼率的LDPC碼進(jìn)行比較，并在加性高斯白噪聲（AWGN）信道模型中進(jìn)行計(jì)算機(jī)仿真，譯碼時(shí)采用迭代次數(shù)為50的和?積算法，調(diào)制方式為BPSK，仿真結(jié)果如圖7所示。

圖7中所使用的由兩種方法構(gòu)造出的LDPC具有相同的碼長(zhǎng)6 690和相同的碼率0.9。當(dāng)信噪比小于4.1 dB時(shí)，兩種碼的性能基本上沒(méi)有任何區(qū)別，但是在信噪比大于4.1 dB時(shí)，采用結(jié)構(gòu)圖法構(gòu)造出的LDPC碼的優(yōu)勢(shì)就逐漸顯現(xiàn)出來(lái)。可以看到在誤碼率為[10-6]時(shí)，采用結(jié)構(gòu)圖法構(gòu)造出的LDPC碼可以獲得0.2 dB增益。

5 結(jié) 論

本文詳細(xì)介紹了如何利用結(jié)構(gòu)圖來(lái)構(gòu)造列重為3的正則LDPC碼。構(gòu)造出的碼具有可變的碼率和碼長(zhǎng)，所以它可以廣泛地應(yīng)用到各種領(lǐng)域，如通信和數(shù)據(jù)存貯等。在高信噪比條件下，這些由結(jié)構(gòu)圖產(chǎn)生的碼性能明顯地優(yōu)于隨機(jī)產(chǎn)生的LDPC碼，并且有著更低的錯(cuò)誤平層。

參考文獻(xiàn)

[1] GALLAGER R G. Low?density parity check codes [M]. Cambridge， MA： MIT Press， 1963.

[2] MACKAY D J C， NEAL R M. Good codes based on very sparse matrices [J]. Lecture Notes in Computer Science， 1995， 1025： 110?111.

[3] KOU Yu， LIN Shu， FOSSORIER M P C. Low?density parity?check codes based on finite geometries [J]. IEEE Transactions on Inform Theory， 2001， 47（7）： 2711?2736.

[4] HU X Y， ELEFTHERIOU E， ARNOLD D. Regular and irregular progressive edge?growth tanner graphs [J]. IEEE Transactions on Inform Theory， 2005， 51（1）： 386?398.

[5] ZENG LQ， LAN L， TAI YY， et al. Constructions of nonbinary quasi?cyclic LDPC codes： A finite field approach [J]. IEEE Transactions on Commun， 2008， 56（4）： 545?554.