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

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

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

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

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

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

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

1 引言

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

本原多項式是一種常見多項式，本質是四環(huán)循環(huán)編碼，因為循環(huán)算法的硬件電路實現(xiàn)容易，所以在傳統(tǒng)通信編碼技術中，經(jīng)常用到本原多項式編碼。

如能將本原多項式循環(huán)算法易于硬件實現(xiàn)的優(yōu)點與LDPC碼長碼時間性能良好的優(yōu)勢相結合，則可能構建一種性能更優(yōu)的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的一個本原元素，則稱此多項式是本原多項式。

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

3 本原多項式LDPC碼的構造

3.1 構造規(guī)則

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

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

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

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

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

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

3.2 構造算法

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

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

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

（3）將P（X）的向量形式進行m-1次右循環(huán)得到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，返回到第三步循環(huán)；若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），該向量經(jīng)過m=7次循環(huán)移位得到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環(huán)的方法進行檢驗，可得矩陣H7沒有Girth=4的環(huán)［4］。

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

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

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

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

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

4 性能分析

4.1 仿真分析

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

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

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

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

4.2 工程應用分析

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

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

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

5 結論

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

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

（3）新算法性能真實可靠，已經(jīng)在CMMB系統(tǒng)投入商用，運行穩(wěn)定。

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

［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年獲工學碩士學位，現(xiàn)為講師，主要研究方向為通信與信號處理；

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年獲工學博士學位，現(xiàn)為教授，主要研究方向為無線通信技術。

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年獲工學碩士學位，現(xiàn)為講師，主要研究方向為通信與控制技術；

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

2011-06-23；

2011-08-15

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