陳志為

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

?

多進制LDPC碼編譯碼研究

陳志為

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

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

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

0引言

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

本文針對多進制LDPC碼的編譯碼算法進行仿真研究，通過軟件仿真結(jié)果，說明多進制LDPC碼在編碼和譯碼算法不同時，其誤碼率性能也不同。再通過改變多進制LDPC碼的碼長和調(diào)制方式，來分析這些改變對碼字性能的影響。

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

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

(1)

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

校驗矩陣H由基矩陣Hb進行矩陣擴展而形成。首先分別將基矩陣Hb中的0和1替換成-1和矩陣的循環(huán)右移的次數(shù)，得到的矩陣記為Hbm。再分別將矩陣Hbm中的-1和0擴展為z×z維零矩陣和單位矩陣，其余的元素擴展為循環(huá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中的每一個元素u(i)均為z維的列向量。校驗矩陣Hbm在進行編碼的時候，同樣可以將校驗序列v分成mb組z維的列向量，即v=[v(0),v(1),…,v(mb-1)]。具體的編碼過程為：

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

把校驗矩陣Hbm逐行相加，有：

(3)

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

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

(4)

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

(5)

(6)

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

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

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

(7)

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

(8)

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

(1) 初始概率計算

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

(9)

那么有：

(10)

(11)

(2) 轉(zhuǎn)置

(12)

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

定義2個部分和的值，分別為：

(13)

(14)

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

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

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

(15)

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

(16)

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

(17)

(18)

(4) 逆轉(zhuǎn)置

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

(19)

(20)

(6) 計算后驗概率，進行判決

后驗概率為:

(21)

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

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

(22)

(23)

(24)

(25)

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

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

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

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

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

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

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

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

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

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

表1表示的是譯碼時的不同算法所需各種運算量的對比。

表1　多進制LDPC碼譯碼算法運算量對比

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

圖4　四進制LDPC譯碼算法性能仿真比較

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

5結(jié)束語

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

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

參考文獻

[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

中圖分類號：TN919.3

文獻標識碼：A

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

DOI:10.16426/j.cnki.jcdzdk.2016.02.014