一種適用于大數(shù)邏輯可譯LDPC 碼的自適應(yīng)譯碼算法*

張 凱，楊 勇

(西安烽火電子科技有限責(zé)任公司，西安710075)

1 引 言

低密度奇偶校驗(yàn)(Low Density Parity Check，LDPC)碼最早由Gallager 于1963年提出［1］，然而由于當(dāng)時的硬件條件限制，使得其在提出的30 多年里未得到學(xué)者的重視。20世紀(jì)90年代后期，由于Turbo碼［2］的發(fā)現(xiàn)使得學(xué)者重新對LDPC 碼進(jìn)行了研究?，F(xiàn)在LDPC 碼從理論上已被證明是一類非常接近香農(nóng)限的糾錯碼［3］。LDPC 碼的構(gòu)造主要可分為兩大類，一類是由計(jì)算機(jī)搜索得到的具有(類)隨機(jī)特性的LDPC 碼［4］，另一類是基于代數(shù)性質(zhì)而得到的具有循環(huán)(cyclic)或者準(zhǔn)循環(huán)(qusi－ cyclic)特性的LDPC 碼［5－6］。

LDPC 碼的譯碼算法可分為三類，分別是硬判決譯碼算法、基于概率域的譯碼算法和基于可靠度的譯碼算法。基于可靠度的譯碼算法主要有大數(shù)邏輯譯碼算法(Iterative Reliability－ Based Majority－Logic Decoding，IRB－MLGD)［7］和基于可靠度的迭代最小和譯碼算法(Reliability－Based Iterative Min－Sum Decoding，RBI－MSD)［8］。硬判決譯碼算法主要有一步大數(shù)邏輯譯碼(One－ Step Majority－Logic Decoding，OSMLGD)算法和比特翻轉(zhuǎn)(Bit－flipping，BF)譯碼算法?；诟怕视虻淖g碼算法(又稱軟判決譯碼算法)所處理的信息采用未經(jīng)判決的軟信息，具有較高的復(fù)雜度，常見的算法是和積譯碼算法(Sum－Product Algorithm，SPA)［9］。為了降低算法復(fù)雜度，文獻(xiàn)［10－11］詳細(xì)介紹了SPA 算法，同時將算法中計(jì)算雙曲正切(tanh)的積轉(zhuǎn)換為尋找最小值，從而大大降低了算法復(fù)雜度。雖然軟判決譯碼算法有著最優(yōu)的譯碼性能，但是從工程實(shí)踐的角度來看這種算法存在一定弊端:一方面軟判決譯碼器在譯碼前需要了解信道的質(zhì)量，即噪聲方差的大小;另一方面修正算法中所引入修正因子的最優(yōu)數(shù)值是與系統(tǒng)中所采用的LDPC 碼緊密相關(guān)的，最優(yōu)解通常是由仿真或密度進(jìn)化(Density Evolution，DE)［12］的方法獲得，這無疑限制了LDPC 碼在實(shí)際中的應(yīng)用。

針對上述弊端，文獻(xiàn)［13］提出了一種基于可靠度的自適應(yīng)譯碼算法，其譯碼性能不依賴于信道的噪聲方差。在譯碼前算法將所有的校驗(yàn)節(jié)點(diǎn)根據(jù)某種劃分準(zhǔn)則分為活動(active)節(jié)點(diǎn)集合和靜態(tài)(silent)節(jié)點(diǎn)集合，迭代譯碼的過程中僅活動節(jié)點(diǎn)參與信息的交換。然而，這種自適應(yīng)譯碼算法的不足之處在于一旦集合劃分完畢，算法不會隨著迭代譯碼的演進(jìn)而自適應(yīng)改變活動節(jié)點(diǎn)集合和靜態(tài)節(jié)點(diǎn)集合。因此這是一種靜態(tài)的自適應(yīng)。為了克服這一不足，本文提出了一種動態(tài)的自適應(yīng)譯碼算法。動態(tài)自適應(yīng)譯碼算法是一種基于整數(shù)可靠度的譯碼算法，其譯碼性能不依賴于信道噪聲方差，并且在迭代譯碼的過程中對每個校驗(yàn)節(jié)點(diǎn)分別引入不同的自適應(yīng)修正因子對外信息進(jìn)行自適應(yīng)修正。由于節(jié)點(diǎn)之間傳遞的是基于整數(shù)的可靠度信息，因此具有低復(fù)雜度，十分有利于硬件實(shí)現(xiàn)。仿真結(jié)果表明，本文提出的動態(tài)自適應(yīng)譯碼算法的性能與和積譯碼算法的性能相當(dāng)。

2 基本概念與符號定義

LDPC 碼可以由一個稀疏的奇偶校驗(yàn)矩陣Η=(hi，j)m×n來定義，同時也可以用一個Tanner 圖來表示［14］。Tanner 圖是一個包含了兩種不同節(jié)點(diǎn)的二分圖，它們分別稱為變量節(jié)點(diǎn)(variable node)Vj(0≤j ＜n)和校驗(yàn)節(jié)點(diǎn)(check node)Ci(0 ≤i ＜m)。其中，變量節(jié)點(diǎn)與校驗(yàn)矩陣Η 的列相對應(yīng)，校驗(yàn)節(jié)點(diǎn)與矩陣Η 的行相對應(yīng)。當(dāng)對應(yīng)校驗(yàn)矩陣Η 的元素hi，j為1 時，Tanner 圖中第i 個校驗(yàn)點(diǎn)與第j 個變量點(diǎn)相連。對于任意LDPC 碼的校驗(yàn)矩陣，定義如下兩個下標(biāo)集合:

對矩陣Η 中的每一行i，定義

Ni={j:0≤j≤n－1，hi，j=1};

對矩陣Η 中的每一列j，定義

Mj={i:0≤i≤m－1，hi，j=1}。

3 自適應(yīng)RBI－MSD 譯碼算法

LDPC 譯碼算法中通常會引入一個修正因子來修正變量或校驗(yàn)節(jié)點(diǎn)所接收的信息，例如偏移/歸一化的BP 算法和RBI－MSD 算法。一般地，這個修正因子的數(shù)值在迭代的過程中恒定不變。為了實(shí)現(xiàn)自適應(yīng)譯碼算法，不同的校驗(yàn)節(jié)點(diǎn)應(yīng)該具有不同的修正因子，且修正因子的數(shù)值應(yīng)隨著迭代次數(shù)的增加而動態(tài)改變。下面分別介紹自適應(yīng)譯碼算法在變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)主要的計(jì)算。

(1)變量節(jié)點(diǎn):每個變量節(jié)點(diǎn)將與其相連的校驗(yàn)節(jié)點(diǎn)傳送來的信息作為輸入信息進(jìn)行處理，并將處理后的外信息(extrinsic message)回傳至相應(yīng)的校驗(yàn)節(jié)點(diǎn)。

(2)校驗(yàn)節(jié)點(diǎn):第i 個校驗(yàn)節(jié)點(diǎn)將與其相連的變量節(jié)點(diǎn)傳送來的信息作為輸入信息進(jìn)行處理，并用修正因子α(k)i將外信息進(jìn)行修正，而后回傳至相應(yīng)的變量節(jié)點(diǎn)。其中，符號α(k)i表示在第k 次迭代過程中第i 個校驗(yàn)節(jié)點(diǎn)的修正因子。顯然，自適應(yīng)譯碼算法的性能極大地依賴于自適應(yīng)修正因子α(k)i。本文的主要工作就是在不犧牲譯碼性能的前提下，給出自適應(yīng)因子的選取準(zhǔn)則。方便起見，我們以RBI－MSD 算法為例給出自適應(yīng)RBI－ MSD 譯碼算法。

令c=(c0，c1，…，cn－1)是待傳送的碼字向量。假設(shè)采用的調(diào)制方式為BPSK，則調(diào)制后的向量為x=(x0，x1，…，xn－1)，其中xi=2ci－1。經(jīng)高斯信道疊加噪聲后得到向量y =(y0，y1，…，yn－1)。為了降低算法的復(fù)雜度和計(jì)算量，我們令不同節(jié)點(diǎn)之間交換的信息都是整數(shù)的可靠度信息。因此，在接收端需要將接收到的實(shí)數(shù)信息進(jìn)行量化，使其轉(zhuǎn)換成整數(shù)化的可靠度信息。

令Δ ＞0、b ＞1 是在量化過程中需要用到的兩個參數(shù)，其中Δ 是量化區(qū)間間隔長度，b 是量化比特位數(shù)。接收到的數(shù)值yj(0≤j ＜n)經(jīng)截?cái)嗵幚砗蟊痪鶆蛄炕介g隔為Δ 的2b－1 個小區(qū)間中的某個區(qū)間，每個區(qū)間可以用b 個比特來表示。假設(shè)量化后的序列為q=(q0，q1，…，qn－1)，其中qj是一個取值在［－(2b－1)，+(2b－1)］范圍內(nèi)的整數(shù)。這里需要說明的是，在量化的過程中，凡是超過量化范圍的接收值，一律進(jìn)行截?cái)嗵幚?。也就是說，如果超出量化范圍，那么就令|qj| =(2b－1)。接收值yj(0≤j ＜n)的量化函數(shù)定義如下:

式中，符號［x］表示將數(shù)值x 向0 方向取整。直觀地講，接收信號的幅度越大，量化結(jié)果的絕對值也越大。因此，量化值qj能夠反比特信息的可信度。

(2)校驗(yàn)節(jié)點(diǎn)信息處理:校驗(yàn)節(jié)點(diǎn)Ci(0≤i ＜m)接收到與其相連的變量節(jié)點(diǎn)發(fā)送的信息，則從校驗(yàn)節(jié)點(diǎn)Ci(0≤i ＜m)向變量節(jié)點(diǎn)Vj傳送的外信息計(jì)算如下:

式中，符號sec_min(x)表示向量x 中次小的數(shù)值。

(3)變量節(jié)點(diǎn)信息處理:變量節(jié)點(diǎn)Vj(0≤j ＜n)的和外信息(total extrinsic information)計(jì)算如下:

用于變量節(jié)點(diǎn)信息更新的準(zhǔn)則為

并將更新后的可靠度傳送給與其相連的校驗(yàn)節(jié)點(diǎn)。

基于上述三個主要步驟，我們可以將自適應(yīng)RBI－MSD 譯碼算法歸納如下:

Step 1 輸入:接收向量y，量化函數(shù)參數(shù)Δ、b 和譯碼最大迭代次數(shù)Imax;

Step 2 初始化:根據(jù)式(1)將接收向量y 量化為整數(shù)可靠度向量q;設(shè)置迭代次數(shù)標(biāo)識k=0;設(shè)置初始可靠度信息R(0)j=qj(0≤j ＜n);

Step 3 迭代:當(dāng)k ＜Imax時，執(zhí)行以下步驟:

(3)對于每個校驗(yàn)節(jié)點(diǎn)Ci(0≤i ＜m)，根據(jù)式(3)得到自適應(yīng)修正因子，并根據(jù)式(2)計(jì)算傳送至變量節(jié)點(diǎn)的外信息;

(5)對于每個變量節(jié)點(diǎn)Vj(0 ≤j ＜n)，根據(jù)式(5)更新其可靠度信息，并將更新后的可靠度信息傳送至相鄰的變量節(jié)點(diǎn);

(6)迭代次數(shù)標(biāo)識k=k+1;

Step 4 輸出:將硬判決向量z(k)作為譯碼器的輸出。

為了更加清楚地說明自適應(yīng)RBI－MSD 譯碼算法的流程，圖1給出了算法流程圖。

圖1 自適應(yīng)RBI－MSD 譯碼算法流程圖Fig.1 Flow chart of the adaptive RBI_MSD decoding algorithm

4 性能仿真與分析

4.1 仿真實(shí)驗(yàn)1

考慮一個基于有限域特性構(gòu)造的(961，721)規(guī)則QC－LDPC 碼［6］，它是大數(shù)邏輯可譯碼，對應(yīng)的校驗(yàn)矩陣Η 的行數(shù)與列數(shù)都是961，其行重和列重均為30。為了比較算法之間的性能，仿真的量化參數(shù)與文獻(xiàn)［8］中設(shè)置的一致，Δ =1/64，b =8，原始RBI－MSD 算法的修正系數(shù)為0.25。最大迭代次數(shù)設(shè)置為50，傳輸信道為高斯信道，調(diào)制方式為二進(jìn)制相移鍵控(Binary－ Phase－ Shift－ Key，BPSK)。仿真結(jié)果如圖2和圖3所示，為了便于比較不同算法之間的性能，圖中同時給出了原始RBI－MSD 譯碼算法和SPA 譯碼算法的性能高曲線。

圖2 (961，721)自適應(yīng)譯碼算法性能曲線Fig.2 Error performances of the(961，721)

圖3 (961，721)自適應(yīng)譯碼算法迭代次數(shù)Fig.3 Average iteration number of the(961，721)

從圖2和圖3中可以看到:

(1)自適應(yīng)RBI－MSD 算法的譯碼性能非常接近SPA 算法的譯碼性能;

(2)結(jié)合自適應(yīng)修正因子，自適應(yīng)RBI－ MSD算法的性能相比于原始RBI－MSD 算法的性能基本無損耗;

(3)自適應(yīng)RBI－MSD 算法的收斂速度與原始RBI－MSD 算法的收斂速度相當(dāng)。例如，在Eb/N0=4.0 dB時，原始RBI－MSD 算法和自適應(yīng)RBI－MSD算法的平均迭代次數(shù)分別為2.123 和2.567 次。

4.2 仿真實(shí)驗(yàn)2

考慮一個基于有限幾何特性構(gòu)造的(4095，3367)規(guī)則循環(huán)LDPC 碼［5］。對應(yīng)的校驗(yàn)矩陣Η 的行數(shù)與列數(shù)都是4095，其行重和列重均為64。其余參數(shù)設(shè)置同仿真1。

仿真結(jié)果如圖4和圖5所示，為了便于比較不同算法之間的性能，圖中同時給出了原始RBI－MSD 譯碼算法和SPA 譯碼算法的性能曲線。

圖4 (4095，3367)自適應(yīng)譯碼算法性能曲線Fig.4 Error performances of the(4095，3367)

圖5 (4095，3367)自適應(yīng)譯碼算法迭代次數(shù)曲線Fig.5 Average iteration number of the(4095，3367)

從圖4和圖5中可以看到:

(1)自適應(yīng)RBI－MSD 譯碼算法的性能非常接近于SPA 算法和原始RBI－MSD 譯碼算法。例如，在誤碼率BER=10－5時自適應(yīng)RBI－MSD 譯碼算法的性能與SPA 算法的性能之間僅有0.1 dB;

(2)自適應(yīng)RBI－MSD 算法的收斂速度與原始RBI－MSD 算法的收斂速度相當(dāng)。例如，在Eb/N0=4.0 dB時，原始RBI－MSD 算法和自適應(yīng)RBI－MSD 算法的平均迭代次數(shù)分別為3.23 和4.92 次。

5 結(jié) 論

本文給出了適用于大數(shù)邏輯可譯LDPC 碼的自適應(yīng)準(zhǔn)則，并以RBI－MSD 算法為例詳細(xì)描述了自適應(yīng)RBI－MSD 譯碼算法。原算法中對每個校驗(yàn)節(jié)點(diǎn)引入相同的修正因子，而在自適算法中對每個校驗(yàn)節(jié)點(diǎn)分別引入了不同的自適應(yīng)修正因子來修正校驗(yàn)節(jié)點(diǎn)發(fā)送的外信息，其中修正因子通過算法自適應(yīng)獲得。通過對基于有限域特性和有限幾何特性構(gòu)造出的不同類型的大數(shù)邏輯可譯LDPC 碼進(jìn)行譯碼，可以看到自適應(yīng)RBI－MSD 譯碼算法對于大數(shù)邏輯可譯LDPC 碼的普適性。提出的自適應(yīng)算法具有復(fù)雜度低、可并行運(yùn)算、全整數(shù)的信息傳遞等優(yōu)點(diǎn)，十分有利于工程實(shí)現(xiàn)。同時，該自適應(yīng)譯碼算法也為快速、高效、可靠的譯碼奠定了理論基礎(chǔ)，更為今后該方面課題的研究提供了借鑒。

［1］ Gallager R G. Low－ density parity－ check codes［M］.Cambridge:MIT Press，1963.

［2］ 肖創(chuàng)創(chuàng)，郭榮海，李際平，等. 直升機(jī)衛(wèi)星通信系統(tǒng)中Turbo 碼外交織器設(shè)計(jì)與仿真［J］.電訊技術(shù)，2014，54(4):486－490.XIAO Chuangchuang，GUO Ronghai，LI Jiping，et al. Design and Simulation of Turbo Codes Interleaver in Helicopter Communication System［J］. Telecommunication Engineering，2014，54(4):486－490.(in Chinese)

［3］ Richardson T，Shokrollahi A，Urbanke R.Design of capacity－approaching low－density parity－check codes［J］.IEEE Transactions on Information Theory，2001，47(2):619－637.

［4］ Hu X Y，Eleftheriou E，Arnold D. Regular and irregular progressive edge－growth tanner graphs［J］.IEEE Transactions on Information Theory，2005，51(1):386－398.

［5］ Kou Y，Lin S，F(xiàn)ossorier M P C. Low－ density parity－check codes based on finite geometries:A discovery and new results［J］. IEEE Transactions on Information Theory，2001，47(7):2711－2736.

［6］ Lan L，Zeng L Q，Tai Y，et al.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.

［7］ Huang Q，Kang J Y，Zhang L，et al.Two reliability－based iterative majority－ logic decoding algorithms for LDPC codes［J］. IEEE Transactions on Communications，2009，57(12):3597－3606.

［8］ Chen H，Zhang K，Ma X，et al.Comparisons between reliability－based iterative min－sum and majority logic decoding algorithms for LDPC codes［J］.IEEE Transactions on Communications，2011，59(7):1766－1771.

［9］ Kschischang F R，F(xiàn)rey B J，Loeliger H A. Factor graphs and the sum－ product algorithm［J］. IEEE Transactions on Information Theory，2001，47(2):498－519.

［10］ Wiberg N，Loeliger H A，Kotter R. Codes and iterative decoding on general graphs［J］. Eoropean Transactions on Telecommunications，1995，35(6):513－526.

［11］ Chen J，Dholakia A，Eleftheriou E.Reduced－complexity decoding of LDPC codes［J］. IEEE Transactions on Communications，2005，53(8):1288－1299.

［12］ Richardson T，Urbanke R. The capacity of low density parity－check codes under message－passing decoding［J］.IEEE Transactions on Information Theory，2001，47(2):599－618.

［13］ Zhang K，Chen H，Ma X. Adaptive decoding algorithms for LDPC codes with redundant check nodes［C］//Proceedings of 2012 International Symposium on Turbo Codes and Iterative Information Processing.Gothenburg，Sweden:IEEE，2012:175－179.

［14］ Tanner R M. A recursive approach to low complexity codes［J］. IEEE Transactions on Information Theory，1981，27(5):533－547.