多進(jìn)制LDPC碼編譯碼研究

陳志為

(中國(guó)電子科技集團(tuán)公司第20研究所,西安 710068)

?

多進(jìn)制LDPC碼編譯碼研究

陳志為

(中國(guó)電子科技集團(tuán)公司第20研究所,西安 710068)

摘要：低密度奇偶校驗(yàn)(LDPC)碼是當(dāng)前廣泛應(yīng)用的信道編碼方式。多進(jìn)制LDPC碼在各類(lèi)噪聲的干擾下，糾錯(cuò)性能仍然極好，是如今信道編碼學(xué)者重點(diǎn)研究方向。主要研究多進(jìn)制LDPC碼的編碼和譯碼方法，通過(guò)軟件仿真，分別對(duì)比不同編碼和譯碼方法的糾錯(cuò)性能，并分析造成糾錯(cuò)性能差異的原因。主要對(duì)一種由二進(jìn)制LDPC碼中元素替換得到的四進(jìn)制LDPC碼，通過(guò)軟件進(jìn)行仿真分析，并最終得到5/6碼率，采用16符號(hào)正交幅度調(diào)制(16QAM)方式的四進(jìn)制LDPC碼的編碼結(jié)構(gòu)。

關(guān)鍵詞：信道編碼；多進(jìn)制低密度奇偶校驗(yàn)碼；快速傅里葉變換-和積算法(FFT-SPA)譯碼

0引言

低密度奇偶校驗(yàn)(LDPC)碼[1]的概念由Gallarger博士于1962年在其論文中提出[2]，一并提出的還有最早的LDPC碼的編譯碼方法，稱(chēng)為古典方法。但是由于當(dāng)時(shí)落后的計(jì)算條件，學(xué)者并沒(méi)有對(duì)LDPC碼給予足夠的重視。Mackay和Neal[3]對(duì)LDPC碼進(jìn)行了深入研究，并在1995年發(fā)現(xiàn)，經(jīng)過(guò)改進(jìn)的LDPC碼譯碼算法，具有與Turbo碼相當(dāng)?shù)男阅?，甚至在碼長(zhǎng)比較長(zhǎng)時(shí)會(huì)超過(guò)Turbo碼。這個(gè)重大發(fā)現(xiàn)立刻在整個(gè)編碼界引發(fā)了重新研究LDPC碼的熱潮。2000年以后，經(jīng)過(guò)全世界學(xué)者們的共同努力，人們發(fā)現(xiàn)比起傳統(tǒng)的二進(jìn)制LDPC碼來(lái)，多進(jìn)制LDPC碼在同樣信噪比條件下的誤碼率更低[4]。但是，多進(jìn)制LDPC碼的更低誤碼率是建立在過(guò)高的編譯碼復(fù)雜度和硬件復(fù)雜度的基礎(chǔ)上，因此多進(jìn)制LDPC碼的發(fā)展遇到了前所未有的困難[5]。

本文針對(duì)多進(jìn)制LDPC碼的編譯碼算法進(jìn)行仿真研究，通過(guò)軟件仿真結(jié)果，說(shuō)明多進(jìn)制LDPC碼在編碼和譯碼算法不同時(shí)，其誤碼率性能也不同。再通過(guò)改變多進(jìn)制LDPC碼的碼長(zhǎng)和調(diào)制方式，來(lái)分析這些改變對(duì)碼字性能的影響。

1多進(jìn)制LDPC碼的構(gòu)造方法

多進(jìn)制LDPC碼可以通過(guò)對(duì)二進(jìn)制LDPC碼的校驗(yàn)矩陣中元素取值范圍的改變來(lái)構(gòu)造，由原來(lái)的FG(2)={0,1}變?yōu)镕G(2m)={0,1,…,2m-1}。因此在多進(jìn)制LDPC碼中，一個(gè)碼元表示的是一個(gè)以m個(gè)比特為總體的符號(hào)。本文采用IEEE 802.16e/D8中的構(gòu)造方式進(jìn)行二進(jìn)制LDPC碼校驗(yàn)矩陣H的構(gòu)造，再以邊緣熵最大為原則，對(duì)校驗(yàn)矩陣H中非零元素進(jìn)行有限域FG(q)的替換[6]，最終得到多進(jìn)制LDPC碼的校驗(yàn)矩陣H。IEEE802.16e/D8中LDPC碼具有準(zhǔn)循環(huán)的性質(zhì)，其校驗(yàn)矩陣H的結(jié)構(gòu)為：

(1)

式中:Pp(i,j)為z×z維矩陣，是全零矩陣或者由單位矩陣循環(huán)移位而來(lái)的矩陣，p(i,j)為單位矩陣循環(huán)右移次數(shù)。特別地，p(i,j)為-1時(shí)，代表Pp(i,j)為零矩陣。

校驗(yàn)矩陣H由基矩陣Hb進(jìn)行矩陣擴(kuò)展而形成。首先分別將基矩陣Hb中的0和1替換成-1和矩陣的循環(huán)右移的次數(shù)，得到的矩陣記為Hbm。再分別將矩陣Hbm中的-1和0擴(kuò)展為z×z維零矩陣和單位矩陣，其余的元素?cái)U(kuò)展為循環(huán)移位矩陣，這樣就可以得到最終的校驗(yàn)矩陣H。

(2)

式中：hb(0)=hb(mb-1)=l，0≤l≤z，hb(i)=0，0

采用串行編碼方法，將信息序列分成kb組，表示成u=[u(0),u(1),…,u(kb-1)]，u中的每一個(gè)元素u(i)均為z維的列向量。校驗(yàn)矩陣Hbm在進(jìn)行編碼的時(shí)候，同樣可以將校驗(yàn)序列v分成mb組z維的列向量，即v=[v(0),v(1),…,v(mb-1)]。具體的編碼過(guò)程為：

(1) 初始化，確定v(0)

把校驗(yàn)矩陣Hbm逐行相加，有：

(3)

式中：1≤x≤mb-2，Pp(x,kb)表示由單位矩陣經(jīng)過(guò)p(x,kb)次右循環(huán)得到的矩陣。

從而可以得到v(0)，即：

(4)

(2) 遞歸計(jì)算，求v(i)的值

(5)

(6)

用這個(gè)方法就可以計(jì)算得到所有校驗(yàn)比特v(i)，i=1,2,…,mb-2的值。

2多進(jìn)制LDPC碼的快速傅里葉變化-和積算法(FFT-SPA)譯碼

假設(shè)采用二進(jìn)制相移鍵控(BPSK)的調(diào)制方式，在加性高斯白噪聲(AWGN)信道中傳播。由于在多進(jìn)制LDPC碼中，每個(gè)符號(hào)可以取到的值范圍是0,1,2,…,q-1，那么需要將每個(gè)符號(hào)變?yōu)槎M(jìn)制后，進(jìn)行0→1，1→-1的映射。假設(shè)接收到的信號(hào)為yi，發(fā)送的信號(hào)為xi，ni是零均值、方差為σ2的高斯白噪聲，于是有：

(7)

高斯白噪聲ni的概率密度函數(shù)(PDF)為：

(8)

多進(jìn)制LDPC碼的FFT-SPA譯碼算法[7]具體步驟如下：

(1) 初始概率計(jì)算

假設(shè)編碼前每個(gè)符號(hào)出現(xiàn)概率相等，那么經(jīng)轉(zhuǎn)換的二進(jìn)制序列中，0和1仍然是等概率的。以二進(jìn)制形式來(lái)表示a=[a0a1…ap-1]，ai∈{0,1}，i=0,1,…,q-1。由于每個(gè)比特在傳輸中是相互獨(dú)立的，那么：

(9)

那么有：

(10)

(11)

(2) 轉(zhuǎn)置

(12)

式中：Hmn為校驗(yàn)矩陣H中第m行第n列的元素。

定義2個(gè)部分和的值，分別為：

(13)

(14)

根據(jù)部分和的定義，有:

頸椎軸性癥狀（axial symptoms,AS）評(píng)價(jià)采用四分法：優(yōu)，術(shù)后無(wú)頸部不適癥狀；良，癥狀出現(xiàn)在勞累或受涼時(shí)，癥狀較輕，對(duì)生活工作影響不大，休息或臥位可緩解，無(wú)需服用止痛藥物；可，癥狀出現(xiàn)較為頻繁，但每年不超過(guò)約3個(gè)月，頸部可有壓痛痙攣，服用止痛藥物緩解；差，癥狀出現(xiàn)很頻繁，超過(guò)3個(gè)月，頸部疼痛僵硬、麻木癥狀嚴(yán)重，止痛藥物效果不佳。其中“優(yōu)”和“良”定義為無(wú)軸性癥狀，“可”和“差”定義為有軸性癥狀【4】。

P(αm(n-1)+βm(n+1)+Hmna=0)=

(15)

(a) 對(duì)轉(zhuǎn)置后的序列作FFT，有：

(16)

(b) 將FFT變換后的序列相乘，有：

(17)

(18)

(4) 逆轉(zhuǎn)置

逆轉(zhuǎn)置是將轉(zhuǎn)置運(yùn)算的結(jié)果還原，相當(dāng)于對(duì)有限域FG(q)上所有的元素除以Hmn。于是就有：

(19)

(20)

(6) 計(jì)算后驗(yàn)概率，進(jìn)行判決

后驗(yàn)概率為:

(21)

3多進(jìn)制LDPC碼的對(duì)數(shù)似然比(LLR)-FFT-SPA譯碼算法

可以將多進(jìn)制LDPC碼的譯碼算法通過(guò)對(duì)數(shù)運(yùn)算擴(kuò)展到對(duì)數(shù)域[8]，這樣就把譯碼時(shí)的乘法運(yùn)算變成了加法運(yùn)算。定義對(duì)數(shù)似然比的形式如下：

(22)

(23)

(24)

(25)

4仿真結(jié)果及分析

將IEEE 802.16e中的二進(jìn)制LDPC碼(nb=24，kb=12，z=96，碼長(zhǎng)N=2 304，碼率R=1/2=0.5)的校驗(yàn)矩陣H中非零元素進(jìn)行有限域FG(q)的替換，得到碼長(zhǎng)N=1 192的四進(jìn)制LDPC碼。在調(diào)制時(shí)采用BPSK方式，噪聲為AWGN信道，采用FFT-SPA算法進(jìn)行譯碼，仿真結(jié)果如圖1所示。

圖1　LDPC碼性能對(duì)比(0.5碼率)

由圖1可以看出四進(jìn)制LDPC碼的性能與原二進(jìn)制碼沒(méi)有太大變化，僅僅在瀑布區(qū)下降速度更快。四進(jìn)制的LDPC碼比二進(jìn)制的LDPC碼擁有更大的編譯碼復(fù)雜度，但性能上沒(méi)有提升，主要是由于以最大邊緣熵原則進(jìn)行非零元素替換得到的矩陣個(gè)數(shù)眾多，此矩陣并不是使其能達(dá)到最優(yōu)性能的矩陣。

改變以上條件下的參數(shù)，使kb=4，其他參數(shù)均不變，得到的是碼長(zhǎng)為N=1 152，碼率為R=5/6=0.833 3的四進(jìn)制LDPC碼。在BPSK調(diào)制方式下，經(jīng)過(guò)AWGN信道，仿真結(jié)果如圖2所示。

圖2　LDPC碼性能對(duì)比(0.833 3碼率)

編碼速率由0.5提高到0.833 3，四進(jìn)制LDPC碼的誤碼率曲線已經(jīng)在二進(jìn)制LDPC碼的左邊較遠(yuǎn)的距離了。當(dāng)誤碼率為10-5左右時(shí)，四進(jìn)制LDPC碼的信噪比約為2.80 dB，而二進(jìn)制LDPC碼的信噪比約為2.92 dB，性能提高約為0.12 dB。在實(shí)際應(yīng)用中，0.12 dB的性能提升幾乎感覺(jué)不到，但是多進(jìn)制LDPC在高碼率的情況下，其優(yōu)勢(shì)可見(jiàn)一斑。

如果采用16符號(hào)正交調(diào)幅(16QAM)的調(diào)制方式，重新對(duì)上面的四進(jìn)制LDPC碼進(jìn)行仿真，仿真結(jié)果如圖3所示。

圖3　LDPC碼性能對(duì)比(0.833 3碼率，16QAM調(diào)制)

通過(guò)仿真結(jié)果可以看出，在碼率提高到0.833 3之后，同時(shí)采用16QAM的高階調(diào)制方式，多進(jìn)制LDPC碼的誤碼率曲線性能顯著。在誤碼率為10-5左右時(shí)，四進(jìn)制LDPC碼的信噪比約為6.3dB，二進(jìn)制LDPC碼的信噪比約為7.1dB，二者差值約為0.8dB。通過(guò)與之前的仿真結(jié)果進(jìn)行對(duì)比，說(shuō)明多進(jìn)制LDPC碼在高碼率、高階調(diào)制方式的情況下，性能要比二進(jìn)制LDPC碼優(yōu)越得多。

表1表示的是譯碼時(shí)的不同算法所需各種運(yùn)算量的對(duì)比。

表1　多進(jìn)制LDPC碼譯碼算法運(yùn)算量對(duì)比

接下來(lái)對(duì)比FFT-SPA和LLR-FFT-SPA2種譯碼算法。選取Mackay構(gòu)造的基于有限域FG(4)上的四進(jìn)制LDPC碼，其參數(shù)為K=3 000，N=9 000，R=K/N=1/3，dc=4，dv=3。圖4所示為2種譯碼算法的性能對(duì)比。

圖4　四進(jìn)制LDPC譯碼算法性能仿真比較

通過(guò)仿真結(jié)果可以看出，采用LLR-FFT-SPA算法的誤碼率曲線與之前的FFT-SPA算法的曲線大部分重合。在誤碼率為10-5左右時(shí)，2條曲線相差不到0.01dB，說(shuō)明LLR-FFT-SPA算法在硬件復(fù)雜度大大降低的同時(shí)，只犧牲了不到0.01dB左右的性能，是一個(gè)好的算法。

5結(jié)束語(yǔ)

本文根據(jù)IEEE802.16e/D8中的二進(jìn)制LDPC碼，通過(guò)元素替換構(gòu)造得到四進(jìn)制LDPC碼，比相應(yīng)的二進(jìn)制LDPC碼性能有較大的提升，是一種在實(shí)際應(yīng)用中可行的碼字。

多進(jìn)制LDPC碼在高碼率和高調(diào)制階數(shù)的條件下，有比二進(jìn)制LDPC碼更好的糾錯(cuò)性能,但算法復(fù)雜度過(guò)高，導(dǎo)致實(shí)現(xiàn)時(shí)硬件復(fù)雜，是目前制約多進(jìn)制LDPC碼發(fā)展的最大阻礙，也是在未來(lái)研究中需重點(diǎn)攻克的難題。

參考文獻(xiàn)

[1]GALLAGERRG.LowDensityParityCheckCodes[M].Cambridge,MA:MITPress,1963.

[2]SHANNONCB.Amathematicaltheoryofcommunication[J].TheBellSystemTechnicalJournal,1948,27(3):379-423.

[3]MACKAYD,NealR.Nearshannonlimitperformanceoflow-densityparitycheckcodes[J].ElectronicsLetters,1996,3(6):457-458.

[4]DAVEYMC,MACKAYD.Low-densityparitycheckcodesoverGF(q)[J].IEEECommunicationsLetters,1998,2(6):165-167.

[5]CALDERBANK A R.The art of signaling:fifty years of coding theory[J].IEEE Transactions on Information Theory,1998,44(6):2561-2595.

[6]DECLERCQ D,FOSSORIER M.Decoding algorithms for nonbinary LDPC codes over GF(q)[J].IEEE Transactions on Communications,2007,55(4):633-643.

[7]HAN G J,GUAN Y L,HUANG X M.Check node reliability-based scheduling for BP decoding of non-binary LDPC codes[J].IEEE Transactions on Communications,2013,61(3): 877-885.

[8]DAVEY M C.Error-correction Using Low Density Parity Check Codes[D].Cambridge CB2 1TN,UK:University of Cambridge,UK,1999.

Research into Encoding and Decoding of Non-Binary LDPC Codes

CHEN Zhi-wei

(The 20th Research Institute of CETC，Xi'an 710068)

Abstract:Low density parity check (LDPC) code is a channel encoding mode commonly used at present.Non-binary (NB)-LDPC codes have great error correcting performance under various noises jamming，is an important research direction of channel encoding researchers.This paper mainly studies the encoding and decoding methods of NB-LDPC codes,compares the error correcting performance of different encoding and decoding methods through software simulation,and analyzes the reason leading to the difference of error correcting performance,mainly performs simulation analysis to 4-ary LDPC codes that are gained by replacing elements in binary LDPC,finally gains the encoding structure of 4-ary LDPC codes with the code ratio of 5/6 by using 16-quadrature amplitude modulation (16QAM) mode.

Key words:channel encoding；non-binary low density parity check code；fast Fourier transform-sum-product algorithm decoding

收稿日期:2016-02-23

中圖分類(lèi)號(hào)：TN919.3

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：CN32-1413(2016)02-0053-05

DOI:10.16426/j.cnki.jcdzdk.2016.02.014