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

張凱　楊勇

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

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

中圖分類號： TN911.72?34 文獻標識碼： A 文章編號： 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 引 言

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

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

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

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

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

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

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

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

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

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

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

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

假設[c=3p，p]是任意正整數(shù)。同樣，把這些校驗點平均分割成三個子集[X0，][X1]和[X2，]每個子集的元素個數(shù)都是[p。]將三個子集的元素縱向排列，并從下到上依次標號（如圖4所示）。在構(gòu)造的過程中，只考慮在不同子集之間出現(xiàn)的邊的情況。在這里要引入邊集合的概念，邊集合[Si]代表了在相鄰子集[Xi]和[Xmod（i+1，3）]之間所有的邊，可以看出集合[Ai∈Si]。在計算邊集合[Si]中每一條邊的斜度都是以校驗點集合[Xi]中的元素為參考點，可以證明在每一個集合[Si（i=0，1，2）]中的元素個數(shù)是相同的。為了避免在列重為3的高碼率LDPC碼中出現(xiàn)圍長為6的短環(huán)，就要在校驗點集合[Xi]中找到斜度對集合[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：假設三個斜度對[s0，s1，s2]分別屬于集合[A0，][A1，][A2，]且[Mod（s0+s1+s2，p）=0，]那么所有這些斜度對能夠構(gòu)造出[p]個三角形，且任意兩個三角形不共享同一條邊。

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

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

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

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

（3） 如果[B0]為空，跳轉(zhuǎn)至（9）； 否則在候選集[B0]中任意選取[s0k]作為集合[A0]的元素，并且將其從對應的候選集[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]的元素，設置[k=k+1，]跳轉(zhuǎn)至（3）；否則跳轉(zhuǎn)至（6）；

（9） 結(jié)束。

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

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

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

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

5 結(jié) 論

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

參考文獻

[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.