（陸軍工程大學(xué)，江蘇 南京 210007）

0 引言

1998 年，Davey 和Mackay 在有限域GF(q)上提出一類多進(jìn)制LDPC（Nonbinary LDPC，NBLDPC）碼[1]。相較于二進(jìn)制LDPC 碼，多進(jìn)制LDPC 碼中的非零元素全部來自于有限域GF(q)，對符號信息直接進(jìn)行編譯，泛化了比特級錯誤，具有更強(qiáng)的糾錯能力，特別是中短碼長糾錯性能優(yōu)異，廣泛應(yīng)用于需要高可靠性的通信系統(tǒng)。

多元和積譯碼算法（Q-ary Sum Product Algorithm，QSPA）是多進(jìn)制LDPC 碼的一種典型譯碼算法，基于符號間的校驗約束關(guān)系，使用對數(shù)似然比作為外信息在兩類節(jié)點間反復(fù)迭代以實現(xiàn)正確譯碼，譯碼復(fù)雜度為O(q2)。隨著有限域階數(shù)q的增加，譯碼中消息向量的維度增加，運(yùn)算量迅速增加。為降低復(fù)雜度，Richardson 和Mackey 利用快速傅里葉變換提出FFT-QSPA[2]，旨在將校驗節(jié)點更新過程中的有限域乘積運(yùn)算變?yōu)楹唵蔚募訙p運(yùn)算，算法復(fù)雜度降低到O(qlog2q)。隨后，Declercq 提出擴(kuò)展最小和算法[3]，將長度為q的LLR 消息向量截短為nm。由于只考慮消息向量中固定的前nm個最大值，因此進(jìn)一步降低了譯碼復(fù)雜度。

文獻(xiàn)[4]匯總了多種關(guān)于校驗節(jié)點更新的方式，其中M-EMS 算法通過引入矩陣M和排序器S簡化了選取最大值的計算過程[5]?；跈z泡法產(chǎn)生了BC-EMS 算法，有效降低了校驗節(jié)點基本步驟中排序器S的長度，提高了搜索效率[6-7]。此外，提出了許多具有良好性能、較低譯碼復(fù)雜度的改進(jìn)EMS算法，包括T-EMS[8-9]、D-EMS 算法[10]和P-EMS算法[11]。其中，D-EMS 算法的主要思想是根據(jù)迭代次數(shù)分階段地動態(tài)改變截短長度，以降低復(fù)雜度。

EMS 算法中，截短長度nm越小，意味著譯碼復(fù)雜度越小，同時也帶來了較大的性能損失，是一個互相矛盾的問題。本文提出了一種動態(tài)EMS 算法，通過分析每次迭代完成后校驗節(jié)點的收斂性，有選擇地縮短下一次迭代時收斂性差的校驗節(jié)點消息向量的長度，以降低其對譯碼過程產(chǎn)生的影響。第2 節(jié)簡要介紹多進(jìn)制LDPC 碼的基本原理；第3節(jié)詳細(xì)描述標(biāo)準(zhǔn)EMS 譯碼算法的具體步驟；第4節(jié)提出新的動態(tài)EMS 算法，詳細(xì)描述了收斂度量值的計算方法以及校驗節(jié)點更新過程中的動態(tài)截短規(guī)則；第5 節(jié)分析所提譯碼算法的運(yùn)算復(fù)雜度；第6 節(jié)為性能仿真分析，分析對比不同條件下幾種譯碼算法的糾錯性能；最后總結(jié)全文。

1 多進(jìn)制LDPC 碼及EMS 譯碼算法原理

1.1 多進(jìn)制LDPC 碼

當(dāng)LDPC 碼校驗矩陣H中的所有元素為{α-∞,α0,α1,…,αq-2}∈GF(q)(q＞2)且遵循有限域下的運(yùn)算法則時，該碼字稱為多進(jìn)值LDPC（Nonbinary Low-Density Parity-check Codes，NB-LDPC）碼。當(dāng)q=2 時，即二進(jìn)制LDPC 碼。

多進(jìn)制準(zhǔn)循環(huán)LDPC 碼（Nonbinary Quasi-Cyclic LDPC，NB-QC-LDPC）的校驗矩陣具有準(zhǔn)循環(huán)特性，可以由多個循環(huán)移位矩陣分塊組成。每個循環(huán)移位矩陣具有循環(huán)右移特性，降低了編譯碼的復(fù)雜度，同時節(jié)省了存儲空間，因此在實際中獲得了廣泛應(yīng)用。循環(huán)右移位數(shù)存儲在基矩陣B中。假設(shè)一個定義在有限域GF(q)下多進(jìn)制QC-LDPC 碼的基矩陣B，大小為M×N，則可表示為：

式中：{α-∞,α0,α1,…,αq-2} ∈GF(q)(q＞2)；指數(shù)bm,n代表循環(huán)右移位數(shù)，規(guī)定每個循環(huán)移位矩陣中的非零值相同。因此，校驗矩陣H可將基矩陣中的每個元素替換為一個p×p的循環(huán)移位矩陣得到：

式中：當(dāng)bm,n=0 時，對應(yīng)單位矩陣，其中非零元素全為αbm,n；當(dāng)bm,n=-∞時，對應(yīng)全零矩陣；其他情況下，按照移位值循環(huán)右移，且非零元素全部為αbm,n。

一個碼長為pN的符號序列c=(c0,c1,…,cN-1)與校驗方程運(yùn)算可以得到校驗和s=(s0,s1,…,sM-1)。當(dāng)s=0 時，說明序列c滿足LDPC 編碼規(guī)則，視為正確符號序列。

1.2 擴(kuò)展最小和算法

對于多進(jìn)制LDPC 碼而言，每個符號位對應(yīng)了q個域元素，EMS 算法更新時只利用LLR 消息向量中前面最大的nm個值及其對應(yīng)域元素進(jìn)行迭代，同時結(jié)合前向后向算法加快算法計算速度，但計算量也很大。

基于有限域GF(q),q=2p，假設(shè)符號序列c=(c0,c1,…,cN-1)采用BPSK 調(diào)制方式，在二進(jìn)制高斯白噪聲（Additive White Gaussian Noise，AWGN）信道上傳輸，其中第j個符號可用二進(jìn)制比特序列表示，即。對接收到的符號序列z=(z0,z1,…,zN-1)進(jìn)行譯碼時，通常利用對數(shù)似然比（Log-Likelihood Ratio，LLR），即：

由于有限域GF(q)中包括q個域元素，因此消息向量包含q個LLR 值。

下面介紹EMS 算法中的變量定義。令Uvp表示變量節(jié)點v傳遞給置換節(jié)點p的消息向量；表示Uvp對應(yīng)的域元素向量；Vcp表示校驗節(jié)點c傳遞給置換節(jié)點p的消息向量；表示Vcp對應(yīng)的域元素向量；N(m)表示與校驗節(jié)點m相連的所有校驗節(jié)點；M(n)表示與變量節(jié)點n相連的所有變量節(jié)點；nm表示截短長度。譯碼過程中所有的運(yùn)算均是有限域運(yùn)算。

用Tanner 圖可以很好地解釋EMS 譯碼過程，Tanner 圖中v表示一個變量節(jié)點對應(yīng)校驗矩陣中一列，c表示一個校驗節(jié)點對應(yīng)校驗矩陣中一行，校驗矩陣中的非零元素表示兩類節(jié)點之間存在連接邊并作為連接邊的標(biāo)簽值即置換節(jié)點。通過將外信息在兩類節(jié)點之間反復(fù)迭代實現(xiàn)正確判決，因此EMS算法的譯碼流程如圖1 所示。

圖1 EMS 算法的譯碼示意

EMS 算法的具體步驟如下所述。

（1）初始化。將信道初始消息Lv降序排列，并將Lv中前nm項賦值給Uvp。

（2）置換。將各項與相鄰置換節(jié)點p相乘，完成對消息向量的置換。

（3）校驗節(jié)點的更新過程。假設(shè)對于校驗節(jié)點c而言，接收到來自相鄰變量節(jié)點的消息后，利用前向后向算法完成更新。其中，對于每個運(yùn)算單元，記輸入消息向量分別為I和A，長度為nm，輸出V，對應(yīng)的域元素向量記為IQ、AQ和VQ。經(jīng)過式（6）的計算，得到由校驗節(jié)點到置換節(jié)點的消息向量Vcpi[k]：

式中，i表示與該校驗節(jié)點相連的第i個變量節(jié)點，⊕表示有限域運(yùn)算。經(jīng)過運(yùn)算后得到維度為q的消息向量V。為避免不斷迭代引起的數(shù)值溢出，經(jīng)排序截短后進(jìn)行歸一化處理：

式中，i∈{0,…,dc-1}，k∈{0,…,nm-1}。

（4）逆置換。將VQcv各項與相鄰置換節(jié)點p相除，完成對消息向量的逆置換。

（5）變量節(jié)點的更新過程。假設(shè)此刻變量節(jié)點為v、度為dv，則當(dāng)接收到相鄰所有變量節(jié)點傳遞過來的消息時，利用前向后向算法可以得到由變量節(jié)點v傳遞給校驗節(jié)點c的消息向量：

式中，i表示與該變量節(jié)點相連的第i個校驗節(jié)點。運(yùn)算中保證在相同域元素下進(jìn)行運(yùn)算，隨后在降序截短后進(jìn)行歸一化處理。

（6）判決譯碼。每次迭代完成需要計算消息向量Ut，將最大值對應(yīng)的域元素判定為該變量節(jié)點位置的取值：

硬判決序列經(jīng)式（2）計算校驗和為0 時，則譯碼成功；否則，返回繼續(xù)譯碼，直到達(dá)到最大迭代次數(shù)時停止迭代。

由于消息截短造成的信息缺失會降低譯碼的正確率，因此與QSPA 算法相比性能有所下降。在步驟（3）和步驟（5）兩類節(jié)點更新過程中使用了前向后向算法（如圖2 所示），其中多次調(diào)用運(yùn)算單元，在此采用一種復(fù)雜度較低的算法搜索最大值。

如圖2 所示，黑色方塊表示一個兩輸入單輸出的處理單元。整個校驗節(jié)點的更新過程是一個并行結(jié)構(gòu)，可以加快迭代的速度。處理單元的具體運(yùn)算過程，如圖3 所示。

圖2 前向后向過程

圖3 處理單元過程

由圖3 可知，每一個處理單元由矩陣M和排序器S共同作用搜索最大值。I和A是兩個長度為nm的消息向量，用IQ和AQ表示對應(yīng)域元素向量。用一個大小為nm×nm的矩陣M保存M[j,p]=A[j]+I[p]，用MQ保存MQ[j,p]=AQ[j]⊕IQ[p]。將一個nm的排序器S初始化為M矩陣的第一列，隨后查找搜索排序器S中的最大值Smax以及對應(yīng)的行，如果不屬于BQ，則將Smax加入B，保存到BQ中，同時選擇同一行中下一列的值替換，直到搜索得到全部nm個元素。要求輸出的B要滿足降序排列，BQ中所有域元素保持唯一。

2 基于校驗節(jié)點收斂性的改進(jìn)動態(tài)EMS 算法

在EMS 譯碼過程中，nm越大，消息向量信息損失越小，譯碼性能越好，但復(fù)雜度越高；nm越小，消息向量信息損失越大，譯碼復(fù)雜度降低，但譯碼性能損失越大。因此，需對nm進(jìn)行優(yōu)化，在譯碼復(fù)雜度和譯碼性能之間進(jìn)行合理折衷。

對于收斂差的節(jié)點，可以適當(dāng)減小截短長度，以降低它在下次迭代過程中對其他消息產(chǎn)生的影響；反之，不變?；诖?，提出了一種新的動態(tài)EMS 算法（New Dynamic EMS，ND-EMS）。變量節(jié)點的收斂性可以利用校驗和以及Vpv共同計算：

硬判決序列與校驗方程在有限域下相乘得到一組校驗和，當(dāng)校驗和s=0 時，說明譯碼正確，反之存在錯誤。式（10）結(jié)合校驗和來衡量第n個變量節(jié)點收斂程度En。En為正數(shù)時，大概率不滿足所有校驗條件；反之，則大概率滿足。對于同一個變量節(jié)點中的消息向量來說，如果最大LLR 值遠(yuǎn)大于其余值，以后可以基本維持最大值對應(yīng)域元素不變，式（11）簡化為消息向量中最大值與次大值之差越大[12]。在此設(shè)定一個長度為N的標(biāo)記向量Tn：

由于校驗節(jié)點的更新過程是EMS 譯碼算法中運(yùn)算復(fù)雜度較高的步驟，因此本文主要考慮校驗節(jié)點的收斂性，減小其截短長度，以降低運(yùn)算復(fù)雜度。一個校驗節(jié)點與多個變量節(jié)點相連，因此將集合N(m)的所有變量節(jié)點可靠度量相加，則校驗節(jié)點的收斂度量值為：

通常，Em是[0,dc]之間的整數(shù)，Em越大表示第m個校驗方程中包含可能不收斂的符號數(shù)量越多，說明該校驗節(jié)點大概率也是不準(zhǔn)確的。因此，在下一次迭代時按式（14）改變截短長度：

式中，nm2=nm-Δ，Δ 表示減少量。校驗節(jié)點m接收到的所有消息向量都做相同截短處理。下文用(nm1,nm2)表示本文算法。

因此，基于校驗節(jié)點收斂性的動態(tài)EMS 算法步驟描述如下。

（1）初始化。所有變量節(jié)點初始消息向量的長度依然保持為q，暫不進(jìn)行截短處理。

（2）校驗節(jié)點更新。依據(jù)校驗節(jié)點的收斂度量值Em計算校驗節(jié)點的收斂值，見式（13），并根據(jù)式（14）對每個校驗節(jié)點設(shè)置不同的截短長度，其更新過程與標(biāo)準(zhǔn)EMS 算法相同。

（3）變量節(jié)點更新。變量節(jié)點的截短長度與初始設(shè)定nm相同，不隨迭代進(jìn)行發(fā)生改變，其更新過程與標(biāo)準(zhǔn)EMS 算法相同。

（4）譯碼判決。計算消息向量Ut進(jìn)行硬判決，硬判決序列利用式（2）檢驗。校驗和為0 時，則譯碼成功；否則，返回繼續(xù)譯碼，并根據(jù)式（10）利用校驗和計算下一輪的En，直到達(dá)到最大迭代次數(shù)時停止迭代。

3 復(fù)雜度分析

整個校驗節(jié)點更新過程中，矩陣M、排序器S以及輸出消息向量B都與nm有關(guān)，搜索時間與nm成正比，因此減小截短長度一定程度上可以降低復(fù)雜度。

隨著迭代的進(jìn)行，消息向量中的最大值逐漸在少數(shù)幾個符號之間變換?；诖耍墨I(xiàn)[10]提出了一種動態(tài)EMS 算法。最初設(shè)為nm1，當(dāng)?shù)螖?shù)達(dá)到Is時，截短長度由nm1變?yōu)閚m2，其中nm1＜nm2，用(nm1,nm2,Is)表示，使得譯碼運(yùn)算復(fù)雜度降低。但在較低信噪比時，受噪聲的影響，每次都可能需要多次迭代才能完成譯碼。因此，D-EMS 算法按照迭代次數(shù)Is縮短長度可以獲得更低的復(fù)雜度，但對于較高信噪比，由于噪聲的影響減弱，使得迭代次數(shù)少于Is時就已經(jīng)結(jié)束譯碼，那么截短長度可能不會發(fā)生變化，則不會降低復(fù)雜度。

設(shè)定迭代I次，D-EMS 算法的參數(shù)為(nm1,nm2,Is)，在前Is次迭代中使用nm1，后I-Is次迭代中使用nm2，用表示平均每次迭代的長度為：

本文所提改進(jìn)D-EMS算法在一次譯碼過程中，用N1和N2分別表示校驗節(jié)點采用不同的截短長度nm1和nm2的數(shù)目，則表示平均每次迭代的長度為：

表1 列舉了幾種算法平均在一次校驗節(jié)點更新過程中的運(yùn)算復(fù)雜度，不包括置換和逆置換過程，令σ=dc-2。

表1 一次校驗節(jié)點更新的運(yùn)算復(fù)雜度

對于FFT-QSPA 而言，進(jìn)行一次長度為N的快速傅里葉變換（FFT）需要實數(shù)加法次數(shù)NlogN，乘法次數(shù)。由于完成一個校驗節(jié)點的更新需要進(jìn)行一次正變換和一次逆變換，因此需要乘以2。假設(shè)校驗節(jié)點度為dc，輸出到某一變量節(jié)點的值由除自己以外其他變量節(jié)點運(yùn)算得到，因此需執(zhí)行(dc-1)次FFT，每次FFT 的長度是q。此外，在正變換和逆變換之間需要進(jìn)行一次乘法，實際上進(jìn)行乘法q(dc-1)次，故共進(jìn)行(dc-1)2qlogq+q(dc-1)次實數(shù)乘法。

在EMS 算法中，因為使用對數(shù)似然比，所以不涉及實數(shù)乘法，且在譯碼前已生成q×q的MQ矩陣，校驗節(jié)點中只需要從中選擇nm×nm即可，故不涉及有限域運(yùn)算。假設(shè)校驗節(jié)點度為dc，需要進(jìn)行3(dc-2)次運(yùn)算單元。每次需要計算LLR 值之和的M矩陣共進(jìn)行次實數(shù)加法。隨后搜索最大值時，搜索排序器最大值的運(yùn)算量為nm-1，搜索BQ中是否重復(fù)需要nm次，因此進(jìn)行2nm-1 次實數(shù)比較。

可見，一次校驗節(jié)點更新的運(yùn)算復(fù)雜度與截短長度成正比。所以，減小截短長度可以有效降低部分運(yùn)算復(fù)雜度。

4 仿真結(jié)果

針對一個碼率為0.5、碼長為84 符號（504 bit）的64 進(jìn)制的多進(jìn)制QC-LDPC 碼，利用本文所提ND-EMS 算法，設(shè)定4 種情況（32，16）、（32，24）、（16，8）和（16，12），并與文獻(xiàn)[10]中的D-EMS對比，設(shè)定為（32，16，10）和（32，16，5）這2種情況。采用FFT-QSPA算法、EMS算法以及D-EMS算法在BPSK-AWGN 信道下進(jìn)行譯碼，誤幀率曲線如圖4 所示。所有算法的最大迭代次數(shù)設(shè)定為50 次。

圖4 EMS 算法性能與截短長度的關(guān)系

圖4 中對比了截短長度為64、32 和16 時，標(biāo)準(zhǔn)EMS 算法與FFT-QSPA 的糾錯性能。可知，截短長度nm與糾錯性能成正比。nm越大，糾錯性能逼近FFT-QSPA。在FER=10-4的條件下，nm=64 時的糾錯性能與FFT-QSPA 相差小于0.1 dB；nm=32 時，相差僅有0.1 dB；nm=16 時，相差約0.4 dB。

由圖5 可知，本文ND-EMS（32，16）和NDEMS（32，24）的糾錯性能與標(biāo)準(zhǔn)EMS（32）相近，在FER=10-5時性能與FFT-QSPA 基本相同。NDEMS（16，8）和ND-EMS（16，12）性能逼近標(biāo)準(zhǔn)EMS（16），幾乎沒有損失，甚至可以達(dá)到文獻(xiàn)[10]中D-EMS（32，16，5）的糾錯性能。

圖5 性能曲線對比

相同條件下，上述4 種情況中，ND-EMS（32，16）和ND-EMS（16，8）利用更短的截短長度實現(xiàn)了更低的復(fù)雜度，同時不損失性能。

在一定信噪比下，記錄每一幀完成譯碼下的迭代次數(shù)，如果無法正確譯碼，則記錄最大迭代次數(shù)，最后平均迭代次數(shù)等于所有幀的迭代次數(shù)之和除以總幀數(shù)。從圖6 可知，ND-EMS（32，24）的平均迭代次數(shù)與標(biāo)準(zhǔn)EMS 算法基本相同，ND-EMS（32，16）略高，但兩者均少于文獻(xiàn)[10]中的D-EMS 算法，并隨信噪比增大差距減小，可見降低截短長度后不會增加迭代次數(shù)。同樣，對于ND-EMS（16，8）和ND-EMS（16，4）情況類似。

圖6 平均迭代次數(shù)對比

圖7 記錄每一幀使用不同長度消息向量的次數(shù)并計算nm2所占比例。比例越大，說明整個過程使用nm2的次數(shù)越多，復(fù)雜度改善的程度越大。可以明顯看出，與文獻(xiàn)[10]相比，本文的4 種方式都使用了更多長度為nm2的消息向量完成譯碼。

圖8 記錄了不同信噪比下算法的平均截短長度，可知改進(jìn)算法的平均截短長度均小于標(biāo)準(zhǔn)EMS算法。對于同樣設(shè)定nm2=16 條件，本文改進(jìn)算法具有更低的平均截短長度，尤其在較高信噪比時，效果明顯。

圖7 使用nm2 的次數(shù)占總數(shù)的比例對比

圖8 平均截短長度對比

5 結(jié)語

針對EMS 算法譯碼復(fù)雜度較高的問題，折衷譯碼性能和譯碼復(fù)雜度之間的關(guān)系，提出了一種新的動態(tài)EMS算法，旨在用更短的消息向量完成譯碼。根據(jù)校驗節(jié)點收斂程度不同，縮短收斂性差的校驗節(jié)點，以減少其對下次迭代的影響。仿真結(jié)果表明，所提算法在使用較短消息向量進(jìn)行譯碼時，基本不會造成性能的損失，同時具有較低的平均截短長度，降低了EMS 算法中校驗節(jié)點的譯碼復(fù)雜度。