基于改進(jìn)PEG算法的多元LDPC碼設(shè)計(jì)

沙巖　王輝　李娜娜　朱婷婷

【摘 要】如何構(gòu)造高性能的LDPC碼是LDPC研究領(lǐng)域的關(guān)鍵技術(shù)。本文利用改進(jìn)的PEG算法構(gòu)造出多元LDPC碼，使其既能保持碼字的性能，又能降低編碼復(fù)雜度。實(shí)驗(yàn)結(jié)果表明PEG編碼的LDPC碼的性能明顯優(yōu)于隨機(jī)編碼的碼字，并且改進(jìn)的PEG算法能大大降低編碼復(fù)雜度，使其更加實(shí)用。

【關(guān)鍵詞】低密度奇偶校驗(yàn)；信道編碼；PEG算法

中圖分類號： TN911.2 文獻(xiàn)標(biāo)識碼： A 文章編號： 2095-2457（2018）12-0041-003

DOI：10.19694/j.cnki.issn2095-2457.2018.12.018

Multivariate LDPC code design based on improved PEG algorithm

SHA Yan WANG Hui LI Na-na ZHU Ting-ting

（School of Medical Informatics，Xuzhou Medical University，Xuzhou 221004，China）

【Abstract】How to construct high - performance LDPC code is a key technology in LDPC research field. In this paper， the improved PEG algorithm is used to construct the multivariate LDPC code， which can not only maintain the performance of code word， but also reduce the coding complexity. The experimental results show that the performance of the LDPC code of PEG encoding is better than that of random code words， and the improved PEG algorithm can greatly reduce the coding complexity and make it more practical.

【Key words】Low-density parity-check； Channel Coding； PEG algorithm

0 引言

低密度奇偶校驗(yàn)碼是（LDPC）近年發(fā)展起來的一種糾錯(cuò)碼[1]，隨著理論研究越來越成熟，它被日益廣泛的應(yīng)用于各種通信系統(tǒng)中[2-3]，尤其是在大數(shù)據(jù)容量通信應(yīng)用非常廣泛[4]。LDPC的構(gòu)造方法種類多樣，LDPC碼的一個(gè)子集對應(yīng)一種方法，這些子集在硬件復(fù)雜度和譯碼性能上各有優(yōu)勢，所以可根據(jù)實(shí)際需求選擇不同的子集[5]。LDPC碼的諸多優(yōu)點(diǎn)使它在數(shù)字視頻廣播、下一代移動(dòng)通信、深空通信等多個(gè)領(lǐng)域的越來越多的應(yīng)用， 比如我國的數(shù)字電視地面廣播傳輸系統(tǒng)（CDTV-T）[6]。

PEG算法是目前構(gòu)造低碼率下中短碼長LDPC碼的最好構(gòu)造方法之一[7]。LDPC碼一種常用的表示方法是二分圖，也稱為Tanner圖。該算法通過依次在已有Tanner圖上添加邊來構(gòu)造最終的Tanner圖，每次添加邊時(shí)都盡可能減少對已有Tanner圖的圍長的影響。它不但適用于正則LDPC碼的構(gòu)造，也適用于非正則LDPC碼的構(gòu)造[7]。

在校驗(yàn)矩陣構(gòu)造方面，基于PEG算法的構(gòu)造方法能使環(huán)長最大化，進(jìn)而有效降低誤碼平層，并且相應(yīng)的校驗(yàn)矩陣H很穩(wěn)定，不必像隨機(jī)編碼中，要通過計(jì)算機(jī)搜尋最佳的H[8]。

本文利用改進(jìn)的PRG算法構(gòu)造出的LDPC碼的性能優(yōu)異，明顯優(yōu)于隨機(jī)編碼的碼字，并且相應(yīng)的校驗(yàn)矩陣H很穩(wěn)定，不必像隨機(jī)編碼中，要通過計(jì)算機(jī)搜尋最佳的校驗(yàn)矩陣H。

1 LDPC碼的傳統(tǒng)編碼算法

LDPC碼是一種特殊的線性分組碼，所以它也適用于通用碼字生成方法[9]。碼字x可以通過信息位s與生成矩陣G相乘得到，具體如公式（1）所示：

x=s·G（1）

如果給出校驗(yàn)矩陣H，生成矩陣G可以利用H和G之間的正交性通過高斯消元來得到。生成矩陣G的形式為G=[I，P]。H=[p1，p2]，可以得到公式（2）：

P=P-12·P1（2）

可以驗(yàn)證HGT=0，由于在生成矩陣G中存在單位矩陣I，因此通過公式（1）生成的碼字是系統(tǒng)碼的形式，即碼字中所有校驗(yàn)位緊接在所有信息位之后，校驗(yàn)位與信息位是分開的。假如x=[s，c]，其中c為校驗(yàn)位信息，那么根據(jù)公式（1）和公式（2）可以得到公式（3）：

c=s·P-12·P1（3）

這種編碼方式具體有以下步驟：

（1）利用高斯消元法求出P2的逆矩陣，然后計(jì)算P=P-12P1，其中H=[P1，P2]，P1為m×（n-m）階矩陣，P2為m×m階的矩陣；

（2）將碼字x分成信息位s和校驗(yàn)位c，根據(jù)c=s·P-12·P1計(jì)算出校驗(yàn)位信息；

（3）將算出的校驗(yàn)位放在信息位后面，生成碼字x。

然而這種算法存在缺陷。當(dāng)用高斯消元求逆再算出生成矩陣G時(shí)，G就不再是稀疏矩陣了。當(dāng)碼長較長時(shí)，存儲(chǔ)生成矩陣G需要消耗很大的資源；同時(shí)，進(jìn)行編碼運(yùn)算時(shí)需要巨大的運(yùn)算量和存儲(chǔ)量來計(jì)算校驗(yàn)位，編碼吞吐量很很大程度的降低。

2 利用PEG改進(jìn)算法構(gòu)造LDPC碼

LDPC碼的最大的缺點(diǎn)就是其編碼復(fù)雜度比較高，針對這個(gè)問題，許多學(xué)者都進(jìn)行了研究。如Richardson和Urbanke提出了一種基于近似下三角矩陣的有效編碼方法[10]。

PEG算法可以構(gòu)造出LDPC碼，但是PEG算法的編碼復(fù)雜度與碼長成正比，本文對PEG算法進(jìn)行改進(jìn)，使得構(gòu)造出的LDPC碼既保持碼字的性能，又能降低編碼復(fù)雜度。

為便于描述，LDPC碼的校驗(yàn)矩陣為H={hij}（0≤i

若已知邊的度分布函數(shù)λ（x）=∑iλixi-1和ρ（x）=∑i ρi xi-1，則可求出變量節(jié)點(diǎn)的度分布函數(shù) （x）=∑ xi、校驗(yàn)節(jié)點(diǎn)的度分布函數(shù) （x）=∑ xi，并按照該分布隨機(jī)給各個(gè)變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)分配度數(shù)，變量節(jié)點(diǎn)記為Ds={d ，d ，…d }、校驗(yàn)節(jié)點(diǎn)記為Dc={d ，d ，…d }，其中d （d ）表示變量節(jié)點(diǎn)sj（校驗(yàn)節(jié)點(diǎn)ci）的度數(shù)，通常集合Ds和Dc按照升序排列，即有d ≤d ≤…≤d ，和d ≤d ≤…≤d ；同時(shí)，將邊的集合根據(jù)變量節(jié)點(diǎn)集Vs表示為E=E ∪E ∪…E ，其中E ={E ，0≤k≤d -1}表示所有與變量節(jié)點(diǎn)sj相連的邊構(gòu)成的集合，E 為與變量節(jié)點(diǎn)sj相連的第k條邊。定義N 為當(dāng)前Tanner圖中所有與變量節(jié)點(diǎn)sj之間的最短路徑長度（所經(jīng)過的邊的個(gè)數(shù)）不超過2l+1的校驗(yàn)節(jié)點(diǎn)構(gòu)成的集合，并用N =Vc＼N 表示校驗(yàn)節(jié)點(diǎn)集中除去N 后剩下的集合。

改進(jìn)的PEG算法可以總結(jié)如下：

（1）添加邊E →（ci，sj），其中ci為當(dāng)前Tanner圖中度數(shù)最小的校驗(yàn)節(jié)點(diǎn)

（2）添加E →（ci，sj），其中k

（3）若 l∈N，使得N ≠φ，且N =φ，ci則為集合N 中度數(shù)最少的校驗(yàn)節(jié)點(diǎn)。

改進(jìn)的PEG算法舉例如下：

令校驗(yàn)矩陣H為（6，3）線性分組碼，則校驗(yàn)位長m=6-3=3。設(shè)變量節(jié)點(diǎn)度分布為[1，2，1，1，2，2]。

（1）首先對變量節(jié)點(diǎn)s1連線，連至校驗(yàn)節(jié)點(diǎn)c1，見圖1。

（2）對s2連線，s2度數(shù)為2，第一條邊首先連在前面圖中度數(shù)最小的校驗(yàn)節(jié)點(diǎn)，即c1，第二條邊在連在其余校驗(yàn)節(jié)點(diǎn)隨機(jī)選擇c2，見圖2

（3）對s3連線，在第二步中c2度數(shù)最小，所以s3第1個(gè)校驗(yàn)節(jié)點(diǎn)選擇c2，見圖3。

（4）對s4連線，度數(shù)最小的是c1、c2，所以第一個(gè)校驗(yàn)節(jié)點(diǎn)選擇c2，見圖4。

（5）對s5連線，度數(shù)最小的校驗(yàn)節(jié)點(diǎn)是c1，s5所以首先連至c1，第二節(jié)點(diǎn)連至c3，見圖5。

（6）對s6連線，校驗(yàn)節(jié)點(diǎn)度數(shù)最小的是c3，所以首先連至c3，再以s6為根節(jié)點(diǎn)展開，s6另一條邊連至c2構(gòu)成一個(gè)環(huán)，見圖6。

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

如果定義中的域不限于二元域就可以得到多元域GF（q）上的LDPC碼，q為碼元數(shù)。多進(jìn)制LDPC碼的二部圖類似于二進(jìn)制LDP碼，只是變量節(jié)點(diǎn)有q種取值，并且，校驗(yàn)節(jié)點(diǎn)的約束更復(fù)雜。令q=2p，這樣我們可以用p位二進(jìn)制比特來傳輸一個(gè)q進(jìn)制符號。當(dāng)H是一個(gè)大的稀疏矩陣時(shí)，我們通過高斯消去得到生成矩陣G進(jìn)而產(chǎn)生碼字。

由圖7可知：碼長為200、碼率為1/2的4元基于PEG改進(jìn)算法構(gòu)造的LDPC在誤符號率為10-3時(shí)比隨機(jī)碼長為200性能好0.6dB左右。碼長為400、碼率為1/2的4元基于PEG改進(jìn)算法構(gòu)造的LDPC在誤符號率為10-3時(shí)比隨機(jī)碼長為400性能好0.1dB左右?？梢娀赑EG改進(jìn)算法構(gòu)造的4元LDPC碼性能于遠(yuǎn)優(yōu)于沒有采用糾錯(cuò)編碼而直接傳輸?shù)姆椒āＰ阅軆?yōu)勢會(huì)隨著碼長的增長而削弱。

4 結(jié)語

本文利用PEG改進(jìn)算法構(gòu)造了LDPC碼。實(shí)驗(yàn)結(jié)果表明改進(jìn)的PEG算法構(gòu)造的多元LDPC碼具有優(yōu)秀的性能。下一步的研究方向是進(jìn)一步改進(jìn)PEG算法，降低編碼復(fù)雜度。

【參考文獻(xiàn)】

[1]Kaufman T， Wigderson A. Symmetric LDPC codes and local testing[J]. Combinatorica， 2016， 36（1）：91-120.

[2]Lyu Y， Hong S， Wang L， et al. Reliability Oriented Decoding Strategy for LDPC Codes Based D-JSCC System[J]. IEEE Communications Letters， 2017， PP（99）：1-1.

[3]Zhang S， Yang F， Tang L， et al. Joint design of QC-LDPC codes for coded cooperation system with joint iterative decoding[J].International Journal of Electronics， 2016， 103（3）：384-405.

[4]Chen C，Wang L，Liu S.The Design of Protograph LDPC Codes as Source Codes in a JSCC System[J].IEEE Communications Letters，2018，PP（99）：1-1.

[5]黃勝，龐曉磊，賈雪婷，等.基于盧卡斯數(shù)列的大圍長QC-LDPC碼構(gòu)造方法[J].電子科技大學(xué)學(xué)報(bào)， 2016，45（2）：174-178.

[6]童龍文， 黃少俊. 基于地面數(shù)字電視的信息推送系統(tǒng)[J]. 電視技術(shù)， 2017， 41（7）：15-18.

[7]He X， Zhou L，Du J.A New Multi-Edge Metric-Constrained PEG Algorithm for Designing Binary LDPC Code with Improved Cycle-Structure[J].IEEE Transactions on Communications， 2017， PP（99）：1-1.

[8]Frost J，Dhanda A，Ratcliffe J，et al.PTU-098 Improving PEG Completion Rates：Adoption of an Algorithm to Maximise Success：An 18 Month Single-Centre Review[J].Gut，2016，65（Suppl 1）：A103.1-A103.

[9]陶雄飛， 王躍東， 柳盼. 基于變量節(jié)點(diǎn)更新的LDPC碼加權(quán)比特翻轉(zhuǎn)譯碼算法[J]. 電子與信息學(xué)報(bào)， 2016， 38（3）：688-693.

[10]Richardson T J， Shokrollahi M A， Urbanke R L. Design of capacity-approaching irregular low-density parity-check codes[J].IEEE Transactions on Information Theory， 2002， 47（2）：619-637.