LDPC碼性能研究與分析

張連連 郭 偉 吉高卿 戴澤華

(1.河北建筑工程學(xué)院電氣工程學(xué)院，河北 張家口 075000;2.張家口市交通運(yùn)輸局，河北 張家口 075000)

LDPC碼性能研究與分析

張連連1郭 偉1吉高卿1戴澤華2

(1.河北建筑工程學(xué)院電氣工程學(xué)院，河北 張家口 075000;2.張家口市交通運(yùn)輸局，河北 張家口 075000)

1/2碼率的二元LDPC碼在AWGN信道下是距Shannon極限最近的糾錯(cuò)碼.在matlab中采用隨機(jī)構(gòu)造法構(gòu)造校驗(yàn)矩陣及軟判決譯碼對(duì)LDPC進(jìn)行了設(shè)計(jì)實(shí)現(xiàn)，并分析了三種不同形式的校驗(yàn)矩陣對(duì)LDPC碼性能的影響，得出近似下三角形式校驗(yàn)矩陣的編碼方法優(yōu)于其他兩種.

LDPC；誤碼率；軟判決譯碼；校驗(yàn)矩陣

0 前 言

低密度奇偶校驗(yàn)碼(Low Density Parity Check Code，LDPC碼)[1]于1962年由Gallagar提出，經(jīng)過Mackey、Spielman和Wiberg[2]等人的研究發(fā)現(xiàn)LDPC碼具有全并行迭代譯碼結(jié)構(gòu)、便于硬件實(shí)現(xiàn)、性能優(yōu)越等優(yōu)點(diǎn)，因此LDPC在深空通信、光纖通信、衛(wèi)星數(shù)字視頻和音頻廣播等領(lǐng)域等得到了廣泛應(yīng)用[3].本文研究了LDPC的隨機(jī)構(gòu)造法構(gòu)造校驗(yàn)矩陣及軟判決譯碼，分析了校驗(yàn)矩陣的多種變換方法，對(duì)不同校驗(yàn)矩陣對(duì)LDPC的性能影響進(jìn)行了研究.

1 LDPC的編碼算法

二元LDPC碼是一種低密度線性分組碼，其校驗(yàn)矩陣H具有稀疏性的特點(diǎn)，即H中大部分為“0”，數(shù)量很少的元素為“1”.正則LDPC碼的定義由Gallager給出，H應(yīng)滿足以下條件：每一行有ρ個(gè)“1”，ρ為該行的行重；每一列有γ個(gè)“1”，γ為該列的列重；任意兩行或者兩列不會(huì)有兩處或兩處以上在相同的位置有“1”；ρ和γ遠(yuǎn)遠(yuǎn)小于碼長(zhǎng).LDPC的編碼步驟概括如下：

(1)低密度校驗(yàn)矩陣構(gòu)造的LDPC碼由校驗(yàn)矩陣確定，編碼時(shí)需先構(gòu)造一個(gè)校驗(yàn)矩陣.假設(shè)已經(jīng)構(gòu)造了一個(gè)校驗(yàn)矩陣H,從碼字空間中選出一組可用碼字作為所需構(gòu)造的LDPC碼.

(2)通過高斯消元將校驗(yàn)矩陣H轉(zhuǎn)化為形式：H=[,I]，I為單位矩陣，方便在譯碼時(shí)確定信息比特位置.

(3)利用校驗(yàn)矩陣得到生成矩陣G=[I,P].

(4)得到編碼輸出碼字C=xG=[x,xp]，即信息序列x乘以生成矩陣G.

校驗(yàn)矩陣H是LDPC的重要特性，H不同則碼字集合也不同，因此校驗(yàn)矩陣對(duì)LDPC碼的構(gòu)造尤為重要.H構(gòu)造時(shí)先生成一個(gè)的全0矩陣，然后隨機(jī)地將每列中的γ個(gè)0置換成1，每行當(dāng)中的ρ個(gè)0置換成1.為保證LDPC碼的正確性同時(shí)需避免以下兩種情況：一是避免出現(xiàn)長(zhǎng)度為4的環(huán)，否則可能導(dǎo)致消息在兩組點(diǎn)之間的反復(fù)傳遞.二是避免比特節(jié)點(diǎn)所連接的校驗(yàn)方程過于集中，否則會(huì)導(dǎo)致LDPC碼錯(cuò)誤.

2 LDPC的譯碼算法

置信傳播算法(Belief Propagation Algorithm)是LDPC軟判決譯碼的一種迭代概率譯碼算法，各個(gè)節(jié)點(diǎn)之間傳遞的信息是概率或置信信息.每一輪迭代都需要對(duì)碼字中各個(gè)比特關(guān)于接收碼字和信道參數(shù)的后驗(yàn)概率進(jìn)行估算，因此BP譯碼算法是一種逐比特最大后驗(yàn)概率算法，具體步驟分為初始化、迭代過程和譯碼判決三部分[4].

2.1 初始化

通過公式(2-1)計(jì)算信道傳遞給變量節(jié)點(diǎn)的初始概率，對(duì)每一個(gè)節(jié)點(diǎn)和與其相鄰的校驗(yàn)節(jié)點(diǎn)j∈C(i)，變量節(jié)點(diǎn)傳向校驗(yàn)節(jié)點(diǎn)的初始消息通過公式(2-2)、(2-3)設(shè)定.

(2-1)

(2-2)

(2-3)

2.2 迭代過程

通過迭代步驟，對(duì)每一比特的后驗(yàn)概率進(jìn)行精確的估算.

1、水平過程

對(duì)所有的校驗(yàn)節(jié)點(diǎn)j和與其相鄰的變量節(jié)點(diǎn)j∈R(j)，第l次迭代時(shí)，通過公式(2-4)、(2-5)計(jì)算變量節(jié)點(diǎn)傳向校驗(yàn)節(jié)點(diǎn)的消息，其中l(wèi)為迭代次數(shù).

(2-4)

(2-5)

2、垂直過程

(2-6)

(2-7)

2.3 譯碼判決

通過公式(2-8)、(2-9)對(duì)所有變量節(jié)點(diǎn)計(jì)算硬判決消息，其中Ki是校正因子，使得Qi(0)+Qi(1)=1.

(2-8)

(2-9)

若Qi(1)>Qi(0)，則ci=1，否則ci=0，得出對(duì)發(fā)送碼字的一個(gè)估計(jì)c=[c1,c2,…，cn].計(jì)算伴隨式S=cHT，如果S=0，則譯碼成功，結(jié)束迭代過程；否則跳轉(zhuǎn)到迭代過程繼續(xù)進(jìn)行迭代譯碼.若迭代次數(shù)達(dá)到預(yù)先設(shè)定的最大次數(shù)仍未成功，則宣告失敗，終止迭代.

3 H矩陣變換方法對(duì)性能的影響

在matlab對(duì)LDPC的編譯碼過程進(jìn)行了設(shè)計(jì)實(shí)現(xiàn)，采用了傳統(tǒng)的高斯消元法、基于下三角形式校驗(yàn)矩陣以及基于近似下三角形式校驗(yàn)矩陣的編碼方法對(duì)LDPC碼誤碼率進(jìn)行分析和比較.對(duì)列重為4的校驗(yàn)矩陣H進(jìn)行變換，將其分別變換為G=[I P]、下三角、近似下三角形式，如圖3-1(a)、(b)、(c)所示.

圖3.2 三種編碼方式LDPC碼的誤碼性能對(duì)比

由圖3-1(a)、(b)、(c)可以明顯看出，高斯消元轉(zhuǎn)換為G=[I P]的過程破壞了H的稀疏性，P中可能出現(xiàn)較多的短環(huán)而影響LDPC碼的性能；轉(zhuǎn)換成下三角形式以及近似下三角形式的H矩陣仍具有稀疏性的特點(diǎn)，其仿真編碼時(shí)間比傳統(tǒng)編碼要少.

通過分析仿真時(shí)長(zhǎng)發(fā)現(xiàn)，列重較小時(shí)三種編碼方式除編碼時(shí)間的差別外其LDPC碼的誤碼率差別并不大；隨著列重的增大，H矩陣并不一定能夠通過高斯消元轉(zhuǎn)換成G=[I P]的形式，所以基于下三角形式以及近似下三角形勢(shì)H矩陣的LDPC碼誤碼性能漸漸優(yōu)于傳統(tǒng)編碼方.觀察圖3.2可以看出基于下三角形式編碼方法以及基于近似下三角形式編碼方法在同一信噪比的情況下，二者均優(yōu)于G=[I P]的編碼方法，且隨著信噪比的提高優(yōu)勢(shì)愈加明顯.近似下三角形式校驗(yàn)矩陣的編碼方法要優(yōu)于下三角矩陣但是這種優(yōu)勢(shì)并不是特別明顯.

[1]R.G.Gallager.Low-Density Parity-Check Codes[J].IRE Transaction On Information Theory,1962

[2]R.M.Tanner.A Recursive Approach to Low Complexity Codes[J].IEEE Transactions on Information.Theory,Sept.1981,V27:533～547

[3]王鵬.LDPC碼的編譯碼原理及編碼設(shè)計(jì)[D].西安電子科技大學(xué),2004年1月

[4]唐啟榮.LDPC編碼的研究與硬件實(shí)現(xiàn)[D].北京郵電大學(xué),2007年3月

[5]Xiali Yan,Wenquan Feng,Qi Zhao and Hongbo Zhao.Modified Log-BP decoding algorithm combined with PSO for Low-Density Parity Check Codes.2010 3rdInternational Conference on Advanced Computer Theory and Engineering(ICACTE2010), V2:443～447

ResearchandAnalysisonthePerformanceofLDPCCodes

ZHANGLian-lian1，GUOWei1，JIGao-qing1，DAIZe-hua2

(1.Hebei Institute of Architecture and Civil Engineering,Hebei Zhangjiakou 075000；2.Xhhangjiakou Transportation Bueau,Hebei Zhangjiakou 075000)

The performance of half of the binary bit-rate LDPC codes in AWGN channel is the latest error-correcting codes to the Shannon Limit.In MATLAB,the LDPC was designed and implemented by using the random construction method to construct the verification matrix and soft decision decoding,and the effect of three different forms of check matrix is analyzed on the performance of LDPC codes.it is concluded that the approximate lower triangular form of check matrix coding method is better than the other two.

LDPC;bit error rate;soft decision decoding;parity check matrix

2017-03-29

2014河北建筑工程學(xué)院科研基金項(xiàng)目，項(xiàng)目名稱：三網(wǎng)融合技術(shù)在建筑電視網(wǎng)中的應(yīng)用，項(xiàng)目編號(hào)：Y201415

張連連(1984-)，女，講師，從事信息與通信工程研究.

10.3969/j.issn.1008-4185.2017.03.015

TN911.22

A