低密度奇偶校驗碼的低復雜度迭代譯碼算法

杜偉，沈金科，李亞

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

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

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

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

1 系統描述

1.1 LDPC 碼

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

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

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

1.2 迭代大數邏輯算法

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

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

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

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

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

當且僅當s=0 時，硬判決序列z是碼C的碼字。

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

對于第i個比特，將其參與的校驗方程獲得的外信息進行求和得到總外信息。

假定迭代大數邏輯算法在第k次迭代碼元比特置信度構成的向量為R(k)，相應的硬判決結果為z(k)，按照式(3)計算每個比特的總外信息，構成向量對R(k)進行更新：

利用更新后的置信度對每個比特進行重新判決。

2 修正迭代大數邏輯譯碼算法

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

2.1 算法描述

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

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

對于第j個校驗方程，定義

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

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

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

圖1 MIMLGD 算法流程

2.2 復雜度分析

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

表1 MIMLGD 算法增加的運算及次數

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

3 仿真結果與分析

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

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

表2 碼長255 的LDPC 碼的平均迭代次數dB

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

仿真2考慮文獻[6]中的(961,721)準循環LDPC 碼。該碼為(30,30)-規則LDPC 碼，采用基于有限域的方法[9-14]構造。圖3 給出了各種譯碼算法的BER 性能曲線。可以看出，提出的MIMLGD 算法的性能優于原始的IMLGD[15-18]算法。例如，在BER 為10-4的條件下，MIMLGD 算法相對于IMLGD 算法獲得了約0.2 dB 的增益。此外，MIMLGD 算法和TIMLGD 算法的性能差距在0.1 dB 以內。表3 給出了各種譯碼算法在不同SNR 下的ANI 數值。可以看出，提出的MIMLGD算法具有較快的收斂速度。

表3 碼長961 的LDPC 碼的平均迭代次數dB

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

4 結束語

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