多進制LDPC碼編譯碼研究

陳志為

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

?

多進制LDPC碼編譯碼研究

陳志為

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

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

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

0引言

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

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

1多進制LDPC碼的構造方法

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

(1)

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

校驗矩陣H由基矩陣Hb進行矩陣擴展而形成。首先分別將基矩陣Hb中的0和1替換成-1和矩陣的循環(huán)右移的次數，得到的矩陣記為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)表示由單位矩陣經過p(x,kb)次右循環(huán)得到的矩陣。

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

(4)

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

(5)

(6)

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

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

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

(7)

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

(8)

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

(1) 初始概率計算

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

(9)

那么有：

(10)

(11)

(2) 轉置

(12)

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

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

(13)

(14)

根據部分和的定義，有:

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

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

(15)

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

(16)

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

(17)

(18)

(4) 逆轉置

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

(19)

(20)

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

后驗概率為:

(21)

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

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

(22)

(23)

(24)

(25)

4仿真結果及分析

將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碼。在調制時采用BPSK方式，噪聲為AWGN信道，采用FFT-SPA算法進行譯碼，仿真結果如圖1所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

5結束語

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

多進制LDPC碼在高碼率和高調制階數的條件下，有比二進制LDPC碼更好的糾錯性能,但算法復雜度過高，導致實現時硬件復雜，是目前制約多進制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