一種基于本原多項式的LDPC碼構建新算法?

蔡黎，代妮娜，戴閩魯，2

一種基于本原多項式的LDPC碼構建新算法?

蔡黎1，代妮娜1，戴閩魯1，2

（1.重慶三峽學院電信學院，重慶萬州404000；2.日本芝測株式會社，日本東京150000）

在分析傳統LDPC編碼方式的基礎上，提出一種基于本原多項式實現LDPC編碼的新方法。根據特定LDPC碼長選擇合適的本原多項式作為子矩陣，對子矩陣進行行列分解、組合，最終構建LDPC碼校驗矩陣H。仿真實驗結果和工程應用證明：新算法構建的LDPC碼在惡劣的通信環境下，誤碼率、誤幀率優于傳統Mackay-LDPC碼，具有較好的性能。

LDPC；本原多項式；矩陣分解；校驗矩陣

1 引言

低密度校驗（LDPC）碼是一種性能逼近Shannon容量極限的漸進好碼，編碼性能優越，其長碼性能在某些時刻甚至能夠超過Turbo碼［1］，目前已成為4G時代重點研究的通信編碼方式之一。

本原多項式是一種常見多項式，本質是四環循環編碼，因為循環算法的硬件電路實現容易，所以在傳統通信編碼技術中，經常用到本原多項式編碼。

如能將本原多項式循環算法易于硬件實現的優點與LDPC碼長碼時間性能良好的優勢相結合，則可能構建一種性能更優的LDPC碼。因此，本文提出一種基于本原多項式的LDPC構建新算法。

2 本原多項式

2.1 本原多項式的定義

一個n次不可約的多項式，如能整除1+Z2n-1，而不能整除其它1+Zl（l，2n-1），可稱此不可約多項式為本原多項式［1］。

設有2m個符號的域為伽羅華域GF（2m），有2m個符號的算法如下：從有兩個符號和一個m次多項式P（X）開始引入新符號，若P（X）=0，列出α的冪的表，在控制P（X）取值的情況下，α的冪一直到2m-2都可取得不同值（α2m-1除外），0，1，α，α2，…，α2m-2為2m個域元素的集合，因此，每個元素可以用1，α，α2，…，α2m-2之和表示。例如，當m=4，P（X）=x4+x+1，構建如下多項式集合：

集合中的元素α稱為域GF（2m）的本原元，若GF（2m）任一元素的冪能夠生成GF（2m）的全部非零元素，則稱它為本原的。

2.2 本原多項式的存在性

綜上，對任意m次既約多項式P（X），如可給出包含0和1在內的2m個不同符號的整表，則稱其為本原多項式［2］。同理，對于m次既約多項式P（X），

若P（β）=0，β是GF（2）m的一個本原元素，則稱此多項式是本原多項式。

對于任意正整數m，至少存在一個m次本原多項式。m次本原多項式的存在，為用其構造LDPC碼提供了理論依據。

3 本原多項式LDPC碼的構造

3.1 構造規則

LDPC碼是一種校驗矩陣為稀疏矩陣的編碼，LDPC碼定義為稀疏奇偶校驗矩陣H的零空間，即有H*CT=0，其中C是碼字序列。

本文提出如下的H矩陣的結構構造規則：

（1）設H矩陣每列含1的個數為較小的常數wc（wc≥3）；

（2）設H矩陣每行含1的個數為較小的常數wr（wr≥wc）；

（3）H矩陣任何兩列之間同為1的行數不超過1，H矩陣中不含四角為1的小方陣，即無4線循環［3］，最小圍線至少是6；

（4）wc和wr小于碼字長度N，行數M（Nwc／wr）N→∞，則wr／N=wc／M→0時，可證明以上規則構造的H矩陣是稀疏矩陣。

3.2 構造算法

本原多項式的核心優勢是利于循環，因此本構造算法仍然基于循環原理，結合矩陣的行列分解技術，易于硬件實現。具體構造步驟如下所述。

（1）根據實際應用系統標準中規定的碼長N和信息位數M，確定校驗矩陣H的參數：行數等于N -M，列數等于N。

（2）在域GF（2m-1）上選擇合適的本原多項式P（X）。本原多項式中系數為1的項的個數與矩陣行重wr相等。m和wr須滿足m=N／wr，且都為正整數。因為m越大，在GF（2m-1）中找尋本原多項式的運算就越復雜，所以計算時一般將m的取值范圍控制在約定的范圍內，以盡量減少循環次數。

（3）將P（X）的向量形式進行m-1次右循環得到m×m的子矩陣H′，再進行列分解，設列分解因子t=wr，得到列分解后的wr個m×m矩陣H′i1（i=1，2，…，wr），對H′i1進行列組合得到m×N矩陣H″1。

（4）若N-M＜m，則需要重新選擇本原多項式；若N-M＞m，則需要重新選擇本原多項式進行行擴展，此多項式來自伽羅華域GF（2m2-1），且m2＜m，m2=N-M-m，返回到第三步循環；若N-M=m，H″1即為所求的校驗矩陣H，結構應如圖1所示。

基本算法流程圖如圖2所示。

3.3 構造實例

設有伽羅華域GF（27）的本原多項式，表達式為P（X）=1+X3+X7，寫成0、1的序列向量為（1，0，0，1，0，0，0，1），該向量經過m=7次循環移位得到8× 8矩陣H′7：

H′7校驗矩陣的行重、列重為3，當且僅當列分解因子t=3時，才有w1=w2=w3=1，H′7能分解成3個8×8的子矩陣，子矩陣行重、列重都為1。可將分解后的子矩陣看作3個單位矩陣的隨機變化排列結果，對H′7進行分解，得到新的8×24矩陣H7，H7行重、列重分別為3、1。

利用檢驗校驗矩陣是否有4環的方法進行檢驗，可得矩陣H7沒有Girth=4的環［4］。

同理，用上述方法也可得到利用其它本原多項式循環矩陣經過分解的子矩陣。多個這樣的子矩陣進行組合就可以得到任意行重、列重的規則LDPC碼校驗矩陣［5］。

在組合得到LDPC碼校驗矩陣的過程中，若選擇本原多項式P（X）=1+X+X6生成循環矩陣與H7組合，則需對多項式的向量進行填充處理，具體算法是在向量末尾加0補充至8項，再分解可得七階本原多項式相似矩陣H6：

將H6和H7進行物理組合，得校驗矩陣H：

顯然，組合方法能夠將校驗矩陣H擴展為行重為3、列重為2的稀疏矩陣，矩陣無girth=4的環。

若需增加此校驗的行重，則可選取階數小于7的本原多項式進行橫向組合，方法與上類似。

4 性能分析

4.1 仿真分析

將碼率同為1／3、矩陣格式為（16，24，2）的采用傳統Mackay算法構建的Mackay-LDPC碼和用上述算法構造的本原LDPC碼進行對比仿真實驗。

實驗采用常用的硬判決譯碼方式進行譯碼，在單輸入單輸出（Single-input Single-output，SISO）AWGN信道環境中進行信號傳輸，主要對比參數為誤碼率（BER）和誤幀率（FER），用Matalab7.0仿真得到的結果如圖3所示。

觀察圖3，以信噪比（SNR）等于8 dB為分界線，當SNR＜8 dB時，本原LDPC碼與Mackay-LDPC碼的誤碼率、誤幀率性能相差不大；當SNR＞8 dB時，本原LDPC碼的誤碼率性能、誤幀率性能則優于Mackay-LDPC碼，約大于0.5 dB。

實驗證明：在誤碼率相同且SNR較小環境下，通過新算法得到的基于本原多項式的LDPC碼性能更優，更能適應惡劣的通信環境。

4.2 工程應用分析

上述算法已經在中國移動多媒體廣播（China Mobile Multimedia Broadcasting，CMMB）系統中投入工程應用。在實驗系統中分別使用本原LDPC碼和Mackay-LDPC碼，采用同一計算時間對同一路徑路測，統計路測結果文件得到表1。

表1說明：當網絡覆蓋范圍小、發射端功率或信號強度正常、滿足仿真條件SNR＜8 dB時，采用兩種不同的編碼方式得到的通信質量相近；當通信覆蓋范圍增大、通信環境惡化或發射端輸出功率增大，滿足仿真條件SNR＞8 dB時，基于本原多項式的LDPC碼的通信質量則優于Mackay-LDPC碼。

實際通信應用與仿真實驗結論一致。

5 結論

（1）新算法能夠通過對階數為m的本原多項式進行循環、矩陣分解得到（m+1）×t（m+1）的校驗矩陣；

（2）仿真和工程應用證明新算法構造方式簡單，計算復雜度低，能夠在通信惡劣的通信環境中取得較好的質量；

（3）新算法性能真實可靠，已經在CMMB系統投入商用，運行穩定。

由于可供選擇的本原多項式非唯一，可深入探討選擇最優本原多項式的算法，使其性能進一步提高。

［1］鄧炯.幾種LDPC碼的性能比較［J］.電訊技術，2009，49（5）：82-85. DENG Jiong.Performance Comparison for Several Kinds of LDPC Codes［J］.Telecommunication Engineering，2009，49（5）：82-85.（in Chinese）

［2］Yu Kou，Lin S，Marc P，etal.Low-Density Parity-Check Codes Based on Finite Geometrics：A Rediscovery and New Results［J］.IEEETransactionson Information Theory，2010，47（7）：2711-2736.

［3］Lan L，Zeng L，Tai Y.Construction of Quasi-Cyclic LDPC Codes for AWGN and Binary Erasure Channels：A Finite Field Approach［J］.IEEE Transactions on Information Theory，2007，53（7）：2429-2458.

［4］Jun Heo.Analysisof scaling soft information on low density parity check code［J］.Electronics Letters，2003，39（1）：325-326.［5］Lan Lan，Yin Yu Tai，Behshad.New Constructions Quasicyclic LDPC Codes Based on Special Classes of BIBD′s for the AWGN and Binary Erasure Channels［J］.IEEE Transactions on Communications，2008，56（1）：39-48.

CAILi was born in Wanzhou，Chongqing，in 1981.He received the M.S.degree in 2010.He is now a lecturer.His research concerns communication and control technology.

Email：wdjyzd＠126.com

代妮娜（1983—），女，重慶人，2008年獲工學碩士學位，現為講師，主要研究方向為通信與信號處理；

DAINi-na was born in Chongqing，in 1983.She received the M.S.degree in 2008.She is now a lecturer.Her research direction is communication and signal processing.

戴閩魯（1954—），男，遼寧沈陽人，1998年獲工學博士學位，現為教授，主要研究方向為無線通信技術。

DAIMin-lu was born in Shenyang，Liaoning Province，in 1954.He received the Ph.D.degree in 1998.He is now a professor.His research direction iswireless communication technology.

A New LDPC Code Construction Algorithm Based on Prim itive Polynom ial

CAILi1，DAINi-na1，DAIMin-lu1，2
（1.Electronic and Information Engineering College，Chongqing Three Gorges University，Wanzhou 404000，China；2.ShibaSoku Co.，Ltd.，Tokyo 150000，Japan）

A new LDPC（Low Density Parity Check）code constructed by primitive polynomial is proposed based on analysis of traditional LDPC.The appropriate primitive polynomials are selected as the sub-matrixes by the length of the specific LDPC.Then thematrixes are decomposed and combined to construct the check matrix. The simulation and engineering applications prove that the performance of LDPC code constructed by proposed algorithm is better than that of Mackay-LDPC.The BER（Bit Error Rate）and FER（Frame Error Rate）are both lower in the bad communication environment.

LDPC；primitive polynomial；matrix decomposition；checkmatrix

The Science and Technology Research Program of Chongqing Education Commission（KJ111112）；Young Fund Projects of Chongqing Three Gorges University（10QN-32）

TN911.22

A

10.3969／j.issn.1001-893x.2011.10.011

蔡黎（1981—），男，重慶萬州人，2010年獲工學碩士學位，現為講師，主要研究方向為通信與控制技術；

1001-893X（2011）10-0051-04

2011-06-23；

2011-08-15

重慶市教委科技研究項目（KJ111112）；重慶三峽學院青年基金資助項目（10QN-32）