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

一種基于本原多項(xiàng)式的LDPC碼構(gòu)建新算法?

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

（1.重慶三峽學(xué)院電信學(xué)院，重慶萬(wàn)州404000；2.日本芝測(cè)株式會(huì)社，日本東京150000）

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

LDPC；本原多項(xiàng)式；矩陣分解；校驗(yàn)矩陣

1 引言

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

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

如能將本原多項(xiàng)式循環(huán)算法易于硬件實(shí)現(xiàn)的優(yōu)點(diǎn)與LDPC碼長(zhǎng)碼時(shí)間性能良好的優(yōu)勢(shì)相結(jié)合，則可能構(gòu)建一種性能更優(yōu)的LDPC碼。因此，本文提出一種基于本原多項(xiàng)式的LDPC構(gòu)建新算法。

2 本原多項(xiàng)式

2.1 本原多項(xiàng)式的定義

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

設(shè)有2m個(gè)符號(hào)的域?yàn)橘ち_華域GF（2m），有2m個(gè)符號(hào)的算法如下：從有兩個(gè)符號(hào)和一個(gè)m次多項(xiàng)式P（X）開(kāi)始引入新符號(hào)，若P（X）=0，列出α的冪的表，在控制P（X）取值的情況下，α的冪一直到2m-2都可取得不同值（α2m-1除外），0，1，α，α2，…，α2m-2為2m個(gè)域元素的集合，因此，每個(gè)元素可以用1，α，α2，…，α2m-2之和表示。例如，當(dāng)m=4，P（X）=x4+x+1，構(gòu)建如下多項(xiàng)式集合：

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

2.2 本原多項(xiàng)式的存在性

綜上，對(duì)任意m次既約多項(xiàng)式P（X），如可給出包含0和1在內(nèi)的2m個(gè)不同符號(hào)的整表，則稱其為本原多項(xiàng)式［2］。同理，對(duì)于m次既約多項(xiàng)式P（X），

若P（β）=0，β是GF（2）m的一個(gè)本原元素，則稱此多項(xiàng)式是本原多項(xiàng)式。

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

3 本原多項(xiàng)式LDPC碼的構(gòu)造

3.1 構(gòu)造規(guī)則

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

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

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

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

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

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

3.2 構(gòu)造算法

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

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

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

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

（4）若N-M＜m，則需要重新選擇本原多項(xiàng)式；若N-M＞m，則需要重新選擇本原多項(xiàng)式進(jìn)行行擴(kuò)展，此多項(xiàng)式來(lái)自伽羅華域GF（2m2-1），且m2＜m，m2=N-M-m，返回到第三步循環(huán)；若N-M=m，H″1即為所求的校驗(yàn)矩陣H，結(jié)構(gòu)應(yīng)如圖1所示。

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

3.3 構(gòu)造實(shí)例

設(shè)有伽羅華域GF（27）的本原多項(xiàng)式，表達(dá)式為P（X）=1+X3+X7，寫成0、1的序列向量為（1，0，0，1，0，0，0，1），該向量經(jīng)過(guò)m=7次循環(huán)移位得到8× 8矩陣H′7：

H′7校驗(yàn)矩陣的行重、列重為3，當(dāng)且僅當(dāng)列分解因子t=3時(shí)，才有w1=w2=w3=1，H′7能分解成3個(gè)8×8的子矩陣，子矩陣行重、列重都為1?？蓪⒎纸夂蟮淖泳仃嚳醋?個(gè)單位矩陣的隨機(jī)變化排列結(jié)果，對(duì)H′7進(jìn)行分解，得到新的8×24矩陣H7，H7行重、列重分別為3、1。

利用檢驗(yàn)校驗(yàn)矩陣是否有4環(huán)的方法進(jìn)行檢驗(yàn)，可得矩陣H7沒(méi)有Girth=4的環(huán)［4］。

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

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

將H6和H7進(jìn)行物理組合，得校驗(yàn)矩陣H：

顯然，組合方法能夠?qū)⑿ｒ?yàn)矩陣H擴(kuò)展為行重為3、列重為2的稀疏矩陣，矩陣無(wú)girth=4的環(huán)。

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

4 性能分析

4.1 仿真分析

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

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

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

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

4.2 工程應(yīng)用分析

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

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

實(shí)際通信應(yīng)用與仿真實(shí)驗(yàn)結(jié)論一致。

5 結(jié)論

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

（2）仿真和工程應(yīng)用證明新算法構(gòu)造方式簡(jiǎn)單，計(jì)算復(fù)雜度低，能夠在通信惡劣的通信環(huán)境中取得較好的質(zhì)量；

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

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

［1］鄧炯.幾種LDPC碼的性能比較［J］.電訊技術(shù)，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年獲工學(xué)碩士學(xué)位，現(xiàn)為講師，主要研究方向?yàn)橥ㄐ排c信號(hào)處理；

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—），男，遼寧沈陽(yáng)人，1998年獲工學(xué)博士學(xué)位，現(xiàn)為教授，主要研究方向?yàn)闊o(wú)線通信技術(shù)。

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—），男，重慶萬(wàn)州人，2010年獲工學(xué)碩士學(xué)位，現(xiàn)為講師，主要研究方向?yàn)橥ㄐ排c控制技術(shù)；

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

2011-06-23；

2011-08-15

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