基于改進PEG算法的多元LDPC碼設計

沙巖　王輝　李娜娜　朱婷婷

【摘 要】如何構造高性能的LDPC碼是LDPC研究領域的關鍵技術。本文利用改進的PEG算法構造出多元LDPC碼，使其既能保持碼字的性能，又能降低編碼復雜度。實驗結果表明PEG編碼的LDPC碼的性能明顯優于隨機編碼的碼字，并且改進的PEG算法能大大降低編碼復雜度，使其更加實用。

【關鍵詞】低密度奇偶校驗；信道編碼；PEG算法

中圖分類號： TN911.2 文獻標識碼： 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 引言

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

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

在校驗矩陣構造方面，基于PEG算法的構造方法能使環長最大化，進而有效降低誤碼平層，并且相應的校驗矩陣H很穩定，不必像隨機編碼中，要通過計算機搜尋最佳的H[8]。

本文利用改進的PRG算法構造出的LDPC碼的性能優異，明顯優于隨機編碼的碼字，并且相應的校驗矩陣H很穩定，不必像隨機編碼中，要通過計算機搜尋最佳的校驗矩陣H。

1 LDPC碼的傳統編碼算法

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

x=s·G（1）

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

P=P-12·P1（2）

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

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

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

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

（2）將碼字x分成信息位s和校驗位c，根據c=s·P-12·P1計算出校驗位信息；

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

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

2 利用PEG改進算法構造LDPC碼

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

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

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

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

改進的PEG算法可以總結如下：

（1）添加邊E →（ci，sj），其中ci為當前Tanner圖中度數最小的校驗節點

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

（3）若 l∈N，使得N ≠φ，且N =φ，ci則為集合N 中度數最少的校驗節點。

改進的PEG算法舉例如下：

令校驗矩陣H為（6，3）線性分組碼，則校驗位長m=6-3=3。設變量節點度分布為[1，2，1，1，2，2]。

（1）首先對變量節點s1連線，連至校驗節點c1，見圖1。

（2）對s2連線，s2度數為2，第一條邊首先連在前面圖中度數最小的校驗節點，即c1，第二條邊在連在其余校驗節點隨機選擇c2，見圖2

（3）對s3連線，在第二步中c2度數最小，所以s3第1個校驗節點選擇c2，見圖3。

（4）對s4連線，度數最小的是c1、c2，所以第一個校驗節點選擇c2，見圖4。

（5）對s5連線，度數最小的校驗節點是c1，s5所以首先連至c1，第二節點連至c3，見圖5。

（6）對s6連線，校驗節點度數最小的是c3，所以首先連至c3，再以s6為根節點展開，s6另一條邊連至c2構成一個環，見圖6。

3 仿真與結果分析

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

由圖7可知：碼長為200、碼率為1/2的4元基于PEG改進算法構造的LDPC在誤符號率為10-3時比隨機碼長為200性能好0.6dB左右。碼長為400、碼率為1/2的4元基于PEG改進算法構造的LDPC在誤符號率為10-3時比隨機碼長為400性能好0.1dB左右。可見基于PEG改進算法構造的4元LDPC碼性能于遠優于沒有采用糾錯編碼而直接傳輸的方法。性能優勢會隨著碼長的增長而削弱。

4 結語

本文利用PEG改進算法構造了LDPC碼。實驗結果表明改進的PEG算法構造的多元LDPC碼具有優秀的性能。下一步的研究方向是進一步改進PEG算法，降低編碼復雜度。

【參考文獻】

[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]黃勝，龐曉磊，賈雪婷，等.基于盧卡斯數列的大圍長QC-LDPC碼構造方法[J].電子科技大學學報， 2016，45（2）：174-178.

[6]童龍文， 黃少俊. 基于地面數字電視的信息推送系統[J]. 電視技術， 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]陶雄飛， 王躍東， 柳盼. 基于變量節點更新的LDPC碼加權比特翻轉譯碼算法[J]. 電子與信息學報， 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.