低密度奇偶校驗(yàn)碼的低復(fù)雜度迭代譯碼算法

杜偉，沈金科，李亞

中國電子科技集團(tuán)公司第二十八研究所，江蘇 南京 210007

低密度奇偶校驗(yàn)(low-density parity-check,LDPC)碼是一類由稀疏校驗(yàn)矩陣定義的線性碼[1]。由于其優(yōu)秀的糾錯(cuò)性能，LDPC 碼近年來引發(fā)了學(xué)術(shù)界的廣泛興趣[2-3]。在碼長較長的條件下，LDPC 碼采用基于置信傳播(belief propagation,BP)準(zhǔn)則的迭代譯碼算法在充分迭代的條件下可以達(dá)到接近信道容量的糾錯(cuò)性能。但是，這類譯碼算法的復(fù)雜度相對(duì)較高，從而不適合于譯碼復(fù)雜度受限的領(lǐng)域。為此，學(xué)術(shù)界提出了一些低復(fù)雜度的譯碼算法，其中迭代大數(shù)邏輯(iterative majority-logic decoding, IMLGD) 譯碼算法是一類重要的算法[4]。

IMLGD 譯碼算法根據(jù)接收序列確定碼字每個(gè)比特的初始置信度，然后采用大數(shù)邏輯譯碼[5]的思想，對(duì)碼字比特的置信度進(jìn)行迭代更新，直到所有校驗(yàn)方程均滿足或者達(dá)到預(yù)先設(shè)定的最大迭代次數(shù)。與傳統(tǒng)基于置信傳播(belief propagation,BP)準(zhǔn)則的譯碼算法相比，迭代大數(shù)邏輯譯碼算法極大地降低了譯碼復(fù)雜度，但糾錯(cuò)性能有了一定下降。為此，文獻(xiàn)[6-7]提出了一種類Turbo 的迭代更新方案。通過選擇恰當(dāng)?shù)臋?quán)重因子，該方案相對(duì)原始迭代大數(shù)邏輯算法獲得了性能提升。對(duì)于特定的LDPC 碼，上述權(quán)重因子是通過預(yù)先進(jìn)行大量搜索得到的，因此通用性較差。

針對(duì)這一問題，本文提出了一種改進(jìn)迭代大數(shù)邏輯譯碼算法。該算法利用校驗(yàn)矩陣各行的置信度對(duì)譯碼迭代過程中的信息進(jìn)行修正。仿真結(jié)果表明，提出的改進(jìn)迭代大數(shù)邏輯譯碼算法在增加很少復(fù)雜度下，性能獲得了改善。此外，提出的算法具有低復(fù)雜度的特征。與文獻(xiàn)[6-7]提出的改進(jìn)方案相比，提出的算法具有更好的通用性。

1 系統(tǒng)描述

1.1 LDPC 碼

假定二元(n,k)LDPC 碼C由m×n的校驗(yàn)矩陣H定義，其中，n和k分別為碼C的碼長和維數(shù)，m≥n-k。假定矩陣H的第j行第i列元素為hji，對(duì)于H的第i列(1 ≤i≤n)，記

對(duì)于H的第j行(1 ≤j≤m)，記

若M(i)=γ(1 ≤i≤n)，且N(j)=ρ(1 ≤j≤m)，則H定義的LDPC 碼稱為(γ,ρ)-規(guī)則LDPC 碼。

1.2 迭代大數(shù)邏輯算法

假定LDPC 碼C的碼字c=(c1,c2,···,cn)在信道上發(fā)送，經(jīng)過二進(jìn)制相移鍵控(binary phase shift keying, BPSK)調(diào)制后得到雙極性序列y=(y1,y2,···,yn)，其中

序列y在加性高斯白噪聲(additive white Gaussian noise, AWGN)信道下發(fā)送。接收端解調(diào)后得到的序列為r=(r1,r2,···,rn)，則有

式中ni～N(0,σ2)為信道噪聲。

假定q=(q1,q2,···,qn)是根據(jù)接收序列r量化得到的初始置信度序列，z=(z1,z2,···,zn)是根據(jù)接收序列得到的硬判決序列。序列z的伴隨式為

將s寫成向量的形式s=(s1,s2,···,sm)，則sj的計(jì)算方法為

當(dāng)且僅當(dāng)s=0 時(shí)，硬判決序列z是碼C的碼字。

對(duì)于第j個(gè)校驗(yàn)方程和任意i∈N(j)，定義為第i個(gè)比特從第j個(gè)校驗(yàn)方程獲得的外信息。

對(duì)于第i個(gè)比特，將其參與的校驗(yàn)方程獲得的外信息進(jìn)行求和得到總外信息。

假定迭代大數(shù)邏輯算法在第k次迭代碼元比特置信度構(gòu)成的向量為R(k)，相應(yīng)的硬判決結(jié)果為z(k)，按照式(3)計(jì)算每個(gè)比特的總外信息，構(gòu)成向量對(duì)R(k)進(jìn)行更新：

利用更新后的置信度對(duì)每個(gè)比特進(jìn)行重新判決。

2 修正迭代大數(shù)邏輯譯碼算法

迭代大數(shù)邏輯譯碼算法具有計(jì)算過程簡單、復(fù)雜度低的優(yōu)點(diǎn)。但是，與LDPC 碼基于BP 準(zhǔn)則的譯碼算法相比，迭代大數(shù)邏輯譯碼算法的糾錯(cuò)性能有了一定下降。文獻(xiàn)[6-7]提出了一種類Turbo 的迭代更新方案，獲得了性能提升。但是，上述方案需要通過預(yù)先進(jìn)行大量搜索選擇權(quán)重因子，通用性較差。為了克服這一問題，本節(jié)提出一種利用接收序列直接進(jìn)行修正的方法。

2.1 算法描述

由式(1)~式(3)可以看出，矩陣H的各行在總外信息的計(jì)算中的貢獻(xiàn)是相同的。但是在實(shí)際中，每個(gè)比特受到信道噪聲干擾的影響是不同的，因此可靠性是不同的，進(jìn)而導(dǎo)致各校驗(yàn)方程的可靠性是不同的。如果在迭代過程中考慮各校驗(yàn)方程的可靠性，將可靠性低的校驗(yàn)方程的外信息賦予較小權(quán)重，可靠性高的校驗(yàn)方程的外信息賦予較大權(quán)重，相應(yīng)對(duì)外信息的貢獻(xiàn)進(jìn)行修正，則可以預(yù)期獲得性能提升。為此，本文采用文獻(xiàn)[8]中給出的校驗(yàn)方程可靠性的計(jì)算方法，提出了一種修正迭代大數(shù)邏輯譯碼算法(modified iterative majority-logic decoding，MIMLGD)。

由編碼理論可知，對(duì)每個(gè)比特，其對(duì)應(yīng)的接收值ri的絕對(duì)值是其可靠度的一種量度[8]， |ri|越大，則相應(yīng)的硬判決結(jié)果zi的可靠性越高；反之，可靠性越低。對(duì)于給定的校驗(yàn)方程，其可靠性由校驗(yàn)比特中可靠性最低的比特決定。

對(duì)于第j個(gè)校驗(yàn)方程，定義

由于wj刻畫了校驗(yàn)方程的可靠性，因此，將wj作為式(2)計(jì)算的外信息的權(quán)重，對(duì)外信息進(jìn)行加權(quán)修正。第i個(gè)比特的總外信息計(jì)算公式為

假定在第k次迭代各比特的總外信息構(gòu)成向量提出的MIMLGD 算法利用η(k)對(duì)R(k)進(jìn)行更新：

最后，根據(jù)式(4)對(duì)更新后的置信度進(jìn)行硬判決。若判決結(jié)果z(k+1)為碼字或者達(dá)到預(yù)先設(shè)定的最大迭代次數(shù)，則退出迭代過程，否則進(jìn)入下一次迭代。提出的MIMLGD 算法流程如圖1 所示。

圖1 MIMLGD 算法流程

2.2 復(fù)雜度分析

由2.1 節(jié)的分析可知，提出的MIMLGD 算法相對(duì)于IMLGD 算法增加的運(yùn)算包括式(5)的權(quán)重計(jì)算和式(6)的加權(quán)計(jì)算。對(duì)于由m×n的校驗(yàn)矩陣H定義的(γ,ρ)-規(guī)則LDPC 碼，表1 列出了MIMLGD 算法相對(duì)于IMLGD 算法增加的運(yùn)算及次數(shù)。

表1 MIMLGD 算法增加的運(yùn)算及次數(shù)

從表1 可以看出，MIMLGD 算法相對(duì)于IMLGD 算法增加的運(yùn)算復(fù)雜度與校驗(yàn)方程數(shù)目呈線性關(guān)系。此外，增加的比較運(yùn)算和乘法運(yùn)算無論采用軟件方式還是硬件方式都易于實(shí)現(xiàn)。因此，提出的MIMLGD 算法具有低復(fù)雜度的特征。

3 仿真結(jié)果與分析

為了驗(yàn)證提出的MIMLGD 算法，本節(jié)分別選擇文獻(xiàn)[3]和文獻(xiàn)[6]中給出的2 組LDPC 碼進(jìn)行仿真。這2 組LDPC 碼的校驗(yàn)矩陣具有較大的列重，非常適合于迭代大數(shù)邏輯譯碼算法。此外，對(duì)傳統(tǒng)基于BP 準(zhǔn)則的和–積算法(sum-product algorithm, SPA)[8]和文獻(xiàn)[6-7]中提出的類Turbo改進(jìn)迭代大數(shù)邏輯譯碼算法(turbo iterative majority-logic decoding, TIMLGD)也進(jìn)行了仿真，以進(jìn)行比較。TIMLGD 算法的修正因子采用文獻(xiàn)中的數(shù)值。所有算法的最大迭代次數(shù)Kmax均設(shè)置為30。對(duì)于各種迭代大數(shù)邏輯算法，初始置信度序列q采用文獻(xiàn)[5]中給出的均勻量化方案，量化位寬6 bit，量化間隔?=1/16。對(duì)于式(5)中的權(quán)重wj，采用6 bit 量化，其中2 bit 整數(shù)部分，4 bit 小數(shù)部分。

仿真1考慮文獻(xiàn)[3]中的(255,175)循環(huán)LDPC 碼。該碼為(16,16)-規(guī)則LDPC 碼，采用基于有限幾何的方法[3]構(gòu)造。圖2 給出了各種譯碼算法在不同信噪比(signal to noise ratio, SNR)下的比特出錯(cuò)概率(bit error ratio，BER)性能曲線。可以看出，提出的MIMLGD 算法的性能優(yōu)于原始的IMLGD 算法。特別地，在SNR 較高的區(qū)域，MIMLGD 算法的性能也優(yōu)于TIMLGD 算法。例如，在BER 為10-4的條件下，MIMLGD 算法相對(duì)于IMLGD 算法和TIMLGD 算法分別獲得了約0.2 和0.1 dB 的增益。表2 給出了各種譯碼算法在不同SNR 下平均迭代次數(shù)(average number of iterations, ANI)數(shù)值?？梢钥闯?，提出的MIMLGD算法具有較小的ANI 數(shù)值，這表明其具有很快的收斂速度。

表2 碼長255 的LDPC 碼的平均迭代次數(shù)dB

圖2 碼長255 的LDPC 碼的BER 性能

仿真2考慮文獻(xiàn)[6]中的(961,721)準(zhǔn)循環(huán)LDPC 碼。該碼為(30,30)-規(guī)則LDPC 碼，采用基于有限域的方法[9-14]構(gòu)造。圖3 給出了各種譯碼算法的BER 性能曲線?？梢钥闯?，提出的MIMLGD 算法的性能優(yōu)于原始的IMLGD[15-18]算法。例如，在BER 為10-4的條件下，MIMLGD 算法相對(duì)于IMLGD 算法獲得了約0.2 dB 的增益。此外，MIMLGD 算法和TIMLGD 算法的性能差距在0.1 dB 以內(nèi)。表3 給出了各種譯碼算法在不同SNR 下的ANI 數(shù)值?？梢钥闯?，提出的MIMLGD算法具有較快的收斂速度。

表3 碼長961 的LDPC 碼的平均迭代次數(shù)dB

圖3 碼長961 的LDPC 碼的BER 性能

4 結(jié)束語

LDPC 碼傳統(tǒng)基于BP 準(zhǔn)則的迭代譯碼不適合于譯碼復(fù)雜度受限的場(chǎng)合，因此設(shè)計(jì)性能良好的低復(fù)雜度譯碼算法具有重要意義。本文基于LDPC 碼的迭代大數(shù)邏輯譯碼算法提出了一種低復(fù)雜度譯碼算法。相對(duì)于迭代大數(shù)邏輯算法，提出的算法增加的復(fù)雜度與校驗(yàn)矩陣的行數(shù)呈線性關(guān)系，增加的運(yùn)算操作易于采用軟件或者硬件實(shí)現(xiàn)，具有低復(fù)雜度的特征。對(duì)于典型LDPC 碼的仿真結(jié)果表明，提出的修正迭代大數(shù)邏輯譯碼算法相對(duì)于迭代大數(shù)邏輯譯碼算法具有更好的性能。例如，在誤比特率10-4的條件下，提出的修正迭代大數(shù)邏輯譯碼算法相對(duì)于迭代大數(shù)邏輯譯碼算法獲得了約0.2 dB 的增益。此外，該算法避免了對(duì)于特定的LDPC 碼搜索修正因子，具有良好的通用性，是實(shí)際應(yīng)用的良好選擇。