LDPC編譯碼算法的仿真分析?

詹平紅 李紅星 尹愛(ài)兵

（1.陸軍炮兵防空兵學(xué)院 合肥 230000）（2.安徽新華學(xué)院 合肥 230000）

1 引言

通信目的在于傳輸信息，通信系統(tǒng)的作用將信息由信源傳送到信宿。在信息傳輸?shù)倪^(guò)程中，不可避免會(huì)受到信道中的噪聲的干擾，從而導(dǎo)致了可靠性的降低。所以，如何提高系統(tǒng)的可靠性，在設(shè)計(jì)系統(tǒng)時(shí)可以合理的選擇調(diào)制制度，解調(diào)方式以及發(fā)送功率等，在仍不能滿足要求時(shí)，可以考慮差錯(cuò)控制了，信道編碼的作用就是進(jìn)行差錯(cuò)控制。信道編碼的實(shí)現(xiàn)原理就是對(duì)傳輸?shù)男畔⒋a元按一定的規(guī)則加入監(jiān)督碼元，組成抗干擾編碼。從而提高系統(tǒng)的可靠性。

LDPC碼是一類可以提高系統(tǒng)可靠性的信道編碼技術(shù)，是一種低密度的線性分組糾錯(cuò)碼，可以用非常稀疏的校驗(yàn)矩陣H或二分圖來(lái)描述，在基于置信傳播的迭代譯碼條件下具有逼近Shannon極限的性能［1～2］。根據(jù)校驗(yàn)矩陣H行列中1的數(shù)目是否相同，可以將LDPC碼分為正則LDPC碼和非正則LDPC碼。本文主要研究的是正則LDPC碼。

Gallager最早給出了正則LDPC碼的定義，具體來(lái)講正則LDPC碼的校驗(yàn)矩陣H滿足下列三個(gè)條件:

1）H矩陣的每行“1”的個(gè)數(shù)是相等；

2）H矩陣的每列“1”的個(gè)數(shù)是相等；

3）與碼長(zhǎng)和H矩陣的行數(shù)相比，和都很小。

LDPC碼往往具有較大規(guī)模的校驗(yàn)矩陣，校驗(yàn)矩陣的構(gòu)造不同，LDPC碼的性能和編譯碼的復(fù)雜度也不相同。研究者提出了各種降低復(fù)雜度的編譯碼算法［7］，使得LDPC碼在通信領(lǐng)域的使用成為可能。

2 LDPC編碼算法

LDPC編碼是以校驗(yàn)矩陣H為前提，再由校驗(yàn)矩陣獲得生成矩陣，生成矩陣再產(chǎn)生不同的碼字［3～4］。因此，設(shè)計(jì)校驗(yàn)矩陣H也是LDPC碼編碼的關(guān)鍵。

LDPC碼校驗(yàn)矩陣H的一般構(gòu)造步驟如下:首先生成一個(gè)的全0矩陣，然后隨機(jī)地將每列中的j個(gè)0置換成1，每行當(dāng)中的k個(gè)0置換成1。但是置0還置1的過(guò)程中，有兩種情況是必須要避免的:一種情況是在H矩陣構(gòu)造時(shí)要避免4環(huán)以及短環(huán)的存在。小循環(huán)會(huì)對(duì)系統(tǒng)性能帶來(lái)不良的影響，導(dǎo)致消息在兩組點(diǎn)之間的反復(fù)傳遞，難以得到更新，與迭代譯碼的思想初衷相違背，是必須清除的一種結(jié)構(gòu)。另一種情況就是比特節(jié)點(diǎn)所連接的校驗(yàn)方程過(guò)于集中，如果這些特節(jié)點(diǎn)都出錯(cuò)時(shí)，校驗(yàn)方程都不能檢測(cè)出錯(cuò)誤的存在。對(duì)于計(jì)算機(jī)仿真最簡(jiǎn)單最實(shí)用的是代數(shù)構(gòu)造法［5］。

假設(shè)要生成一個(gè)無(wú)4環(huán)的規(guī)則（n，j，k）LDPC碼的校驗(yàn)矩陣Hm×n。當(dāng)j＜m時(shí)，其中j為列重，m為校驗(yàn)節(jié)點(diǎn)的個(gè)數(shù):

采用以下步驟獲得H矩陣:

1）選取 k個(gè)素?cái)?shù) p1，p2，…，pk且 p1＞p2＞…＞pk＞2；（pi，m）=1，i=1，2，……k；2p1+2p2+2p3＜m

2）把m個(gè)校驗(yàn)節(jié)點(diǎn)編號(hào)為0，1，…，（m-1），依次均勻地放在一個(gè)圓上。

3）隨機(jī)選取一個(gè)校驗(yàn)節(jié)點(diǎn)i，以pi為步長(zhǎng)順時(shí)針移動(dòng)（m-1）次，連同節(jié)點(diǎn)i共計(jì)依次走過(guò)m各點(diǎn)，記為posi。把跑遍的點(diǎn)依次排列組成一個(gè)序列pos，完成了一輪操作。

4）依次取素?cái)?shù)pa，a=2，3，…，k，重復(fù)第三步。

5）將pos中的mxk個(gè)元素按每j個(gè)一組進(jìn)行劃分，每組對(duì)應(yīng)一個(gè)變量節(jié)點(diǎn) xi與 eji，eji+1，…，eji+j-1相連，完成了無(wú)4環(huán)規(guī)則LDPC碼的H構(gòu)造。

代數(shù)構(gòu)造法中k個(gè)參數(shù)的選取方法，先獲取一張適當(dāng)大小的素?cái)?shù)表，并將表中的素?cái)?shù)從小到大排列，從素?cái)?shù)表中劃去大于m/2的素?cái)?shù)，并將與m不互素的數(shù)從表中劃去，然后選定兩個(gè)較小的素?cái)?shù)q1，q2，計(jì) 算l1=2q2+q1，l2=2q2-q1，l3=2q1+q2，l3=2q1-q2如果li為素?cái)?shù)，將其從素?cái)?shù)表中劃去，從素?cái)?shù)表中選定下一個(gè)較小的素?cái)?shù)，作為q3，然后從已選定的素?cái)?shù)中再選取一個(gè)作為q，令q2=q3，q1=q，再計(jì)算一次li，如果為表中的素?cái)?shù)，又將其從表中劃去，重復(fù)這一過(guò)程，直到選定k個(gè)素?cái)?shù)為止。

以規(guī)則（486，3，9）LDPC碼為例，首先用上述方法選取9個(gè)素?cái)?shù)，再有代數(shù)構(gòu)造法確定校驗(yàn)矩陣H，利用spy（H）畫出矩陣H中非零元素的分布情況。

圖1 矩陣H中非零元素的空間分布

通過(guò)高斯消元法使校驗(yàn)矩陣H消元［6］，獲得具有近似下三角矩陣的特殊形式如圖2所示。

圖2 近似下三角矩陣H

3 LDPC譯碼算法

LDPC碼有硬判決和軟判決的兩種譯碼方式，前者的計(jì)算相對(duì)簡(jiǎn)單，譯碼更快，對(duì)硬件設(shè)備要求也較小，但是譯碼性能較差；后者利用了更多接收到的信息，計(jì)算相對(duì)復(fù)雜，譯碼更慢，對(duì)設(shè)備要求較高，但譯碼性能更好。

這里采用的是軟判決譯碼方式，最常用的軟判決譯碼算法是和積譯碼算法，又稱置信傳播（Belief Propagation，BP）算法［7～14］。BP算法是充分利用接收到的信道信息，將信道信息轉(zhuǎn)化成可能是0和1的概率信息，這些概率信息在節(jié)點(diǎn)之間不斷傳遞，由迭代算法計(jì)算概率信息，將節(jié)點(diǎn)信息進(jìn)行更新，這樣就可以在接收端判決信號(hào)。通過(guò)多次迭代計(jì)算使得譯碼結(jié)果更加精準(zhǔn)，誤碼率更低。

BP算法具體過(guò)程包括先驗(yàn)概率初始化，檢驗(yàn)節(jié)點(diǎn)想變量節(jié)點(diǎn)發(fā)送校驗(yàn)消息，變量節(jié)點(diǎn)向校驗(yàn)節(jié)點(diǎn)發(fā)送變量消息，計(jì)算似然值進(jìn)行譯碼判決，最后，利用校驗(yàn)矩陣H，與譯碼所得碼字x，判斷是否滿足

如滿足，則譯碼成功，否則進(jìn)行下一輪的信息更新計(jì)算。直到達(dá)到最大迭代次數(shù)，則結(jié)束迭代。

4 仿真與實(shí)現(xiàn)

Matlab是一種用于算法開(kāi)發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計(jì)算的高級(jí)計(jì)算語(yǔ)言的應(yīng)用軟件，是實(shí)現(xiàn)通信算法仿真的一個(gè)良好平臺(tái)。但LDPC碼的編譯碼涉及到大量的上快速地實(shí)現(xiàn)LDPC編譯碼算法，是軟件部分的關(guān)鍵。根據(jù)LDPC編譯碼的基本原理，需要大量的循環(huán)及迭代運(yùn)算，直接用Matlab的M語(yǔ)言實(shí)現(xiàn)仿真速度較慢，如何有效地利用Matlab平臺(tái)實(shí)現(xiàn)編譯碼算法，軟件編碼部分在H矩陣構(gòu)造時(shí)采用了上述的代數(shù)迭代法，譯碼部分采用BP算法，并在通信過(guò)程中隨機(jī)加入每幀的錯(cuò)誤，譯碼之后的得到錯(cuò)誤bit數(shù)，LDPC碼的可靠性用誤比特率（BER）來(lái)衡量［15～16］。

程序中仿真參數(shù)設(shè)置，LDPC碼長(zhǎng)為486，列重為3，行重9，信噪比為10dB的情況下進(jìn)行了仿真實(shí)驗(yàn)。仿真程序包括編碼程序和譯碼程序。編碼主程序又包括構(gòu)造H矩陣、信道編碼程序及主程序；譯碼程序包括載波同步、信道譯碼及主程序。譯碼是驗(yàn)證LDPC編碼的關(guān)鍵，譯碼主程序?qū)崿F(xiàn)的功能是載入載波同步模塊輸出的數(shù)據(jù)及譯碼時(shí)需要的預(yù)處理數(shù)據(jù)。部分譯碼程序如下所示。

xxw=324； %源信息數(shù)據(jù)矩陣

m=162； %H矩陣列數(shù)

n=486； %H矩陣行數(shù)

Es=2；

r=2/3；

M=1；

Eb=Es/（r*M）；%Eb代表平均到每個(gè)比特上的信號(hào)能量

liezhong=3； %列重

hangzhong=9； %行重

snr=10； %信噪比

sigma=sqrt（Eb/（3*10^（snr/10）））；

ber1=0；

ber2=0；

t=1；

while t＜61

hanglieH=size（H）；

hangH=hanglieH（1）；

lieH=hanglieH（2）；

ncol=zeros（liezhong，lieH）；

nrow=zeros（hangH，hangzhong）；

lie1wei=find（H）；

for a=1:lieH

for b=1:liezhong

ncol（b，a）=（lie1wei（（a-1）*liezhong+b）-（a-1）*

hangH）；

end

end

hang1wei=find（H'）；

for a=1:hangH

for b=1:hangzhong

nrow（a，b）=（hang1wei（（a-1）*hangzhong+b）-（a-1）*lieH）；

end

end

xyuan=outx1（2，:）；

quweishu=5；

demodz（1，:）=ryuan（2，（quweishu+1）:（quweishu+756））；

for k=1:t

demodz（1，k）=-demodz（1，k）；

end

decode； %調(diào)用解碼程序

for i=1:756

if demodz（1，i）＞0 %將接收到的數(shù)據(jù)進(jìn)行判

斷

demodz（1，i）=0； %如果數(shù)據(jù)大于0判斷為0

else demodz（1，i）=1； %如果數(shù)據(jù)小于0判斷

為1

end

end

decode_out=decoded（1，1:504）；

save decode_out decode_out

noe10=sum（abs（demodz-xyuan））； %譯碼前誤碼個(gè)

數(shù)

noe20=sum（abs（decode_out-s））； %譯碼后誤碼個(gè)

數(shù)

nod10=length（xyuan）； %編碼后碼元個(gè)數(shù)

nod20=length（s）； %編碼前碼元個(gè)數(shù)ber10=noe10/nod10；

ber20=noe20/nod20；

fprintf（'%d %d %f %f %e %e '，t，k，noe10，noe20，ber10，ber20）；

t=k+1；

ber1（t-1）=ber10；

ber2（t-1）=ber20；

end

z=1:60；

figure；

semilogy（10。^z）；

semilogy（ber1，'-rd'）；

hold on；

semilogy（ber2，'-bv'）；

title（'LDPC碼譯碼性能曲線'）；

ylabel（'BER'）；

xlabel（'Random Errors'）；

legend（'未經(jīng)信道譯碼的誤碼率'，'經(jīng)信道譯碼后的誤碼率'）；

運(yùn)行結(jié)果如圖3所示。

圖3 LDPC誤碼性能仿真分析

仿真程序運(yùn)行結(jié)果可知，編碼前的數(shù)據(jù)矩陣s，其長(zhǎng)度為324bit，編碼效率達(dá)到m/n=2/3，編碼效率是比較高，從上圖的誤碼性能分析可以看出規(guī)則的LDPC（486，3，9）碼編譯碼性能也是比較優(yōu)越的，當(dāng)每幀含隨機(jī)錯(cuò)誤小于等于25bit時(shí)可以完全糾錯(cuò)；只有當(dāng)每幀含隨機(jī)錯(cuò)誤較大，在45bit時(shí)才會(huì)出現(xiàn)越譯碼錯(cuò)誤越多的現(xiàn)象。

5 結(jié)語(yǔ)

LDPC碼是迄今為止發(fā)現(xiàn)的最接近香農(nóng)限的信道編碼之一，作為一種優(yōu)秀的信道編碼，在現(xiàn)代通信和數(shù)據(jù)傳輸系統(tǒng)中將擁有廣闊的應(yīng)用前景。本文主要研究利用Matlab仿真平臺(tái)實(shí)現(xiàn)LDPC編譯碼的算法，其中包括校驗(yàn)矩陣的構(gòu)造、編譯碼的實(shí)現(xiàn)，并在噪聲干擾下對(duì)其誤碼性能的進(jìn)行了仿真，驗(yàn)證了LDPC碼在編譯算法上獲得的優(yōu)越性能。