一種聯(lián)合星座和伴隨式信息的迭代譯碼算法*

陳海強(qiáng)，王 璐，黃小栗，羅靈山，梁 奇，覃團(tuán)發(fā)，2，3

(1.廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，南寧530004;2.廣西高校多媒體通信與信息處理重點(diǎn)實(shí)驗(yàn)室(廣西大學(xué))，南寧530004;3. 廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點(diǎn)實(shí)驗(yàn)室培育基地(廣西大學(xué))，南寧530004)

1 引 言

伴隨式信息屬于二元域信號，能夠方便地從接收端的硬判決信息中提取，廣泛用于各類前向糾錯碼(Forward Error Correction，F(xiàn)EC)技術(shù)中。傳統(tǒng)的基于硬判決的低密度奇偶校驗(yàn)(Low Density Parity Check，LDPC)譯碼算法，例如比特翻轉(zhuǎn)算法(Bit Flipping，BF)［1］和一步大數(shù)邏輯譯碼(One Step Majority Logic Decoding，OSMLGD)算法［2］等都使用了伴隨式信息進(jìn)行譯碼設(shè)計(jì)。在硬判決譯碼的基礎(chǔ)上引入可靠度信息以及迭代譯碼，衍生了近年來頗受關(guān)注的基于可靠度的譯碼算法，這類算法能有效兼顧譯碼復(fù)雜度、收斂和譯碼性能。

典型的基于可靠度的譯碼算法包括加權(quán)一步大數(shù)邏輯(Weighted OSMLGD，WOSMLGD)譯碼［2］、加權(quán)比特翻轉(zhuǎn)算法以及它們的改進(jìn)版本等［3］。基于可靠度信息，引入適當(dāng)?shù)牡呗钥梢赃M(jìn)一步提高譯碼性能。相關(guān)的工作包括近年來由Huang 等人提出的基于可靠度的迭代大數(shù)邏輯譯碼算法(RBI－MLGD)［4］以及基于該算法的各種改進(jìn)算法，如WISRB－MLGD 算法［5］、MRBI－MLGD 算法［6］以及Ngatched［7］和Zhang［8］等人提出的修正算法等。基于可靠度的多元LDPC 譯碼算法近年來也得到了研究［9］。

上述幾種基于可靠度的譯碼算法都使用了一種特殊的外信息形式，需要結(jié)合當(dāng)前碼位信息和伴隨信息進(jìn)行提取。這個過程會產(chǎn)生額外的運(yùn)算操作，對于碼長較長、列重較大的大數(shù)邏輯可譯碼，會產(chǎn)生不可忽視的運(yùn)算開銷。此外，變量點(diǎn)的總外信息設(shè)計(jì)(偏移幅度/方向)是跟信源端的星座映射相關(guān)的，而上述幾種算法都沒有引入星座信息。基于此，本文聯(lián)合信號星座和伴隨式信息進(jìn)行譯碼設(shè)計(jì)。在校驗(yàn)節(jié)點(diǎn)，我們直接使用伴隨式信息進(jìn)行傳遞和處理;在變量節(jié)點(diǎn)，結(jié)合信源端的星座映射和伴隨式進(jìn)行總信息收集和處理。由于伴隨式信息是二元信息，因此本文的算法也屬于二元信息傳遞算法。理論分析和仿真實(shí)驗(yàn)結(jié)果表明，本文提出的算法在保持原RBI－MLGD 算法優(yōu)良譯碼性能的同時，具有更低的譯碼復(fù)雜度。

2 系統(tǒng)模型

信息序列u =(u0，u1，…，uk－1)∈Fk2經(jīng)編碼后得到碼字c=(c0，c1，…，cn－1)∈Fn2。c 經(jīng)調(diào)制后得到實(shí)數(shù)向量x =(x0，x1，…，xn－1)，其中xj=φS(cj)∈R是一個維的實(shí)數(shù)信號，其形式由具體的映射規(guī)則φS(·)決定，相應(yīng)的信號星座記為As{φS(cj)，cj∈F2}。對于二元域信號，可采用簡單的一維BPSK 映射。本文提出的算法將結(jié)合具體的 φS(·)函數(shù)對變量點(diǎn)譯碼策略進(jìn)行描述。假設(shè)信號x通過加性高斯白噪聲信道(Additive White Gaussian Noise Channel，AWGNC)傳輸，接收信號為y =(y0，y1，y2，…，yn－1)，yj=xj+nj，其中，ni～N(0，σ2)是高斯白噪聲的一個實(shí)現(xiàn)。接收信號y 經(jīng)量化處理得到q=(q0，q1，…，qn－1)。

3 RBI－MLGD 譯碼算法回顧

計(jì)算硬判決信息z=(z0，z1，…，zn－1)，其判決規(guī)則為

基于硬判決序列，可計(jì)算相應(yīng)的伴隨式信息向量s=zHT=(s0，s1，…，sm－1)，其中第i 個伴隨式計(jì)算如下:

式中，記號⊕表示模2 加運(yùn)算。RBI－MLGD 算法主要由三個步驟組成。

(1)校驗(yàn)節(jié)點(diǎn)信息處理

在譯碼過程中，使用了一種特殊的外信息。第i個校驗(yàn)節(jié)點(diǎn)Ci傳遞給第j 個變量節(jié)點(diǎn)Vj的外信息σi，j計(jì)算如下:

式中，0≤i≤m－1，0≤j≤n－1。

(2)變量節(jié)點(diǎn)信息處理

基于上述外信息，可計(jì)算與第j 個變量節(jié)點(diǎn)Vj相對應(yīng)的總外信息

式中，0≤j≤n－1。

(3)迭代更新

令R(k)j表示第k 次迭代過程中變量節(jié)點(diǎn)Vj的信息可靠度，其迭代更新規(guī)則為

式中，0≤j≤n－1。注意，初始的可靠度設(shè)置為接收信號的量化信息，即R(0)j=qj。

4 聯(lián)合星座和伴隨式的算法設(shè)計(jì)

由上述譯碼過程可知，外信息與伴隨式信息以及當(dāng)前碼位信息存在如下關(guān)系:

在當(dāng)前伴隨式si正確的條件下，校驗(yàn)節(jié)點(diǎn)回傳到變量節(jié)點(diǎn)的外信息σi，j取值正好與zj的取值相一致。相應(yīng)地，在變量節(jié)點(diǎn)的總外信息處理和設(shè)計(jì)時，也需要使用與當(dāng)前硬判決信號zj調(diào)制方向一致的修正偏移處理。對于RBI－MLGD 算法，其發(fā)送端星座映射為φS(cj)=1－2cj，則可靠度修正應(yīng)設(shè)計(jì)為φS(σij)=1－2σij，偏移方向與發(fā)送端映射規(guī)則一致，偏移幅度為1 個單位。然而，在實(shí)際應(yīng)用中發(fā)送端的調(diào)制模式與信號星座的映射規(guī)則φS(.)具有多種形式。例如，當(dāng)發(fā)送端映射規(guī)則改為φS(cj)=2cj－1 或其他形式時，則上述RBI－MLGD 算法基于1－2σij的修正偏移操作正好相反(其修正方向與當(dāng)前信號星座信息不相符)。對于多元調(diào)制的信號星座圖，其映射規(guī)則會更加復(fù)雜?；诖耍瑸榱朔奖闼惴枋?，本節(jié)聯(lián)合具體的星座信息對譯碼算法進(jìn)行描述和設(shè)計(jì)。此外，我們注意到，根據(jù)σi，j的定義，校驗(yàn)節(jié)點(diǎn)回傳到變量節(jié)點(diǎn)的外信息都是不一樣的，需要單獨(dú)計(jì)算，這必然會引入運(yùn)算消耗，增加譯碼復(fù)雜度。因此，本文將不用外信息σi，j而改用伴隨式信息進(jìn)行算法設(shè)計(jì)。

(1)校驗(yàn)節(jié)點(diǎn)信息處理

第i 個校驗(yàn)節(jié)點(diǎn)Ci傳遞給第j 個變量節(jié)點(diǎn)Vj的信息直接使用與Ci對應(yīng)的伴隨式信息si。與使用外信息σi，j不一樣，這時從Ci傳遞出來的信息都是一樣的，不需要其他額外的計(jì)算。

(2)變量節(jié)點(diǎn)信息處理

相應(yīng)地，變量節(jié)點(diǎn)也使用伴隨式信息進(jìn)行總信息的收集和處理，第j 個變量節(jié)點(diǎn)Vj收集到的譯碼信息設(shè)計(jì)如下:

式中，0≤j≤n－1。

(3)迭代更新

令R(k)j表示第k 次迭代過程中變量節(jié)點(diǎn)Vj的信息可靠度，則迭代更新規(guī)則更改為

值為σi，j=zj，5 個外信息取值為σi，j=，則(1－2zj)。因此，本文提出的算法在變量點(diǎn)的處理與RBI－MLGD 算法是一致的，但本文在校驗(yàn)節(jié)點(diǎn)不使用外信息，避免了相應(yīng)的計(jì)算操作，降低了譯碼復(fù)雜度。

5 復(fù)雜度分析和實(shí)驗(yàn)仿真

5.1 譯碼復(fù)雜度

本文算法的譯碼復(fù)雜度主要由以下幾個方面產(chǎn)生:第一，根據(jù)公式(1)，需要n 次邏輯操作計(jì)算硬判決序列;第二，根據(jù)公式(2)，需要m(ρ－1)次邏輯操作計(jì)算伴隨式序列;第三，計(jì)算修正的總信息需要n(γ－1)次整數(shù)加法運(yùn)算和n 次邏輯運(yùn)算;第四，計(jì)算變量節(jié)點(diǎn)的可靠度迭代更新需要n 次整數(shù)加法。綜上所述，完成本文算法的一次迭代產(chǎn)生的總運(yùn)算量為mρ +2n－m =nγ +2n－m 次邏輯運(yùn)算以及nγ 次整數(shù)加法運(yùn)算(mρ=nγ 是H 中非零元個數(shù))。表1給出了本文算法一次迭代產(chǎn)生的計(jì)算量。由表可見，與RBI－MLGD 算法相比，本文算法每次迭代可節(jié)省mρ－n =n(γ－1)次邏輯操作，降低了譯碼復(fù)雜度。

表1 算法每次迭代的運(yùn)算量比較Table 1 Computational complexities required per iteration

5.2 譯碼性能

由前面的分析可知，本文算法在迭代更新過程中對可靠度信息的處理(偏移幅度/方向)效果是一致的。因此，理論上本文算法的性能應(yīng)該與RBI－MLGD 一致，不會有任何性能損失。為了方便比較，本文仍然使用文獻(xiàn)［4］中基于有限域方法構(gòu)造的(961，721)規(guī)則準(zhǔn)循環(huán)LDPC 碼以及基于二維Euclidean 幾何方法構(gòu)造的(4095，3367)規(guī)則循環(huán)LDPC 碼作為仿真例子。同時，量化參數(shù)、最大迭代次數(shù)等仿真參數(shù)都與文獻(xiàn)［4］保持一致。仿真結(jié)果見圖1～4。由圖可見，本文算法保持了RBI－MLGD算法優(yōu)良的譯碼誤碼率(Bit Error Rate，BER)性能以及快速的譯碼收斂速度，相應(yīng)的曲線幾乎是重疊的(細(xì)微差別來自于仿真中所用到的隨機(jī)序列)。

圖1 (961，721)LDPC 碼性能Fig.1 Performances of the(961，721)LDPC code

圖2 (961，721)LDPC 碼收斂速率Fig.2 Decoding convergence rate of the(961，721)LDPC code

圖3 (4095，3367)LDPC 碼性能Fig.3 Performances of the(4095，3367)LDPC code

圖4 (4095，3367)LDPC 碼收斂速率Fig.4 Decoding convergence rate of the(4095，3367)LDPC code

6 結(jié)束語

本文聯(lián)合信號星座和伴隨式信息，提出了一種基于可靠度的迭代大數(shù)邏輯譯碼算法。在校驗(yàn)節(jié)點(diǎn)，譯碼算法直接使用伴隨式信息進(jìn)行傳遞和處理;在變量節(jié)點(diǎn)，結(jié)合信源端的星座映射和伴隨式進(jìn)行可靠度信息的偏移方向和偏移幅度設(shè)計(jì)。由于本文算法使用了伴隨式信息，避免了迭代過程中頻繁的外信息計(jì)算操作。仿真結(jié)果表明，本文提出的算法在保持優(yōu)良譯碼性能以及快速譯碼速度的同時，具有更低的譯碼復(fù)雜度。此外，我們指出兩點(diǎn):一是在譯碼過程中引入信號映射信息使得算法具有更好的普適性，但系統(tǒng)并不會因此得到額外的性能增益;二是與RBI－MLGD 算法一樣，本文算法僅對列重較大的LDPC 碼有效，對于隨機(jī)構(gòu)造的小列重碼，其譯碼性能有待進(jìn)一步提高。

［1］ Gallager R G. Low density parity check codes［J］. IEEE Transactions on Information Theory，1962，8(1):21－28.

［2］ 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(2):2711－2736.

［3］ 劉原華，張美玲. LDPC 碼的改進(jìn)迭代比特翻轉(zhuǎn)譯碼算法［J］.電訊技術(shù)，2012，52(4):488－491.LIU Yuanhua，ZHANG Meiling.An improved iterative bit－flipping decoding algorithm for Low－density Parity－check Codes［J］. Telecommunication Engineering，2012，52(4):488－491.(in Chinese)

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

［5］ Chen C Y，Huang Q，Kang J Y，et al.A binary messagepassing decoding algorithm for LDPC codes［C］ //Proceedings of 47th Annual Allerton Conference. Illinois:IEEE，2009:424－430.

［6］ 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.

［7］ Ngatched T M N，Alfa A S，Cai J. An improvement on the soft reliability－ based iterative majority－ logic decoding algorithm for LDPC codes［C］ //Proceedings of 2010 IEEE Global Telecommunications Conference. Miami:IEEE，2010:1－5.

［8］ Zhang K，Chen H，Ma X. Adaptive decoding algorithms for LDPC codes with redundant check nodes［C］//Proceedings of 2012 IEEE International Symposium on Information Theory(ISIT). Gothenburg:IEEE，2012:175－179.

［9］ Ma X，Zhang K，Chen H，et al.Low complexity X－EMS algorithms for non－binary LDPC codes［J］. IEEE Transactions on Communications，2012，60(1):9－13.