基于量化修正的低復(fù)雜度LDPC譯碼算法*

杜立嬋，黃繹琿，王文靜，聶 晶，黎相成,3**

(1.南寧職業(yè)技術(shù)學(xué)院人工智能學(xué)院，廣西南寧 530008；2.廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西南寧 530004；3.廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣西南寧 530004)

現(xiàn)代通信系統(tǒng)自出現(xiàn)以來，實(shí)現(xiàn)更安全、更高效及更可靠的通信方式是人類一直以來追求的目標(biāo)。隨著信息技術(shù)的高速發(fā)展，特別是在深度學(xué)習(xí)和人工智能等領(lǐng)域取得的巨大進(jìn)步，大大加速了云計(jì)算、無人駕駛以及車聯(lián)網(wǎng)等新型技術(shù)的應(yīng)用。同時，對通信系統(tǒng)也提出了更高的可靠性、更小的時延以及更大的數(shù)據(jù)帶寬要求。信道編碼是通信系統(tǒng)中的基礎(chǔ)核心技術(shù)，(Low Density Parity Check,LDPC)譯碼作為優(yōu)秀的信道編碼方案，具有糾錯性能好且易于并行譯碼的特點(diǎn)，吸引了來自國內(nèi)外眾多研究者的關(guān)注。LDPC碼由Gallager[1,2]首次提出，但受限于當(dāng)時的硬件技術(shù)水平，其譯碼算法難以實(shí)現(xiàn)，在此后的30多年間基本被研究者忽略。到20世紀(jì)90年代中后期，隨著計(jì)算機(jī)及硬件技術(shù)的發(fā)展，特別是Mackay等[3-6]開展的系列研究，重新掀起了人們對LDPC碼的關(guān)注，圍繞LDPC碼的研究取得了大量實(shí)用的研究成果[7-11]。由于眾多研究者的努力，在2016年底，3GPP RAN1#86次會議決定將準(zhǔn)循環(huán)LDPC碼確定為5G-eMBB通信環(huán)境下大數(shù)據(jù)包(長碼)的信道編碼方案。

一般情況下，可以將LDPC碼的譯碼算法分為以下3個種類[12]：①軟判決譯碼算法，②硬判決譯碼算法，③基于可靠度的譯碼算法。軟判決譯碼算法主要為和積譯碼算法(SPA)與其改進(jìn)算法，在上述算法中性能最優(yōu)，但由于在算法中采用浮點(diǎn)數(shù)乘法以及對數(shù)運(yùn)算，其計(jì)算復(fù)雜度非常高。早期的硬判決算法主要有Gallager教授[1]的比特翻轉(zhuǎn)(BF)譯碼算法，以及Lin等[13]提出的一步大數(shù)邏輯譯碼(OSMLGD)算法。其中BF譯碼算法的核心思想為采用該比特參與運(yùn)算的校驗(yàn)和進(jìn)行判斷是否翻轉(zhuǎn)該位，而OSMLGD是首個類MLGD譯碼算法，兩者的計(jì)算復(fù)雜度都極低，由于采用信道的硬判決信息進(jìn)行譯碼，譯碼信息損失較大，所以譯碼性能較差。最近，Liu等[14]通過引入比特位自適應(yīng)閾值門限策略，避免了全局最大值搜索處理，實(shí)現(xiàn)了高吞吐量、低時延的BF譯碼算法，特別適合硬件實(shí)現(xiàn)。硬判決與軟判決譯碼算法均存在明顯的優(yōu)缺點(diǎn)，研究者們結(jié)合兩類算法的特點(diǎn)展開研究，提出了一類基于可靠度的譯碼算法，實(shí)現(xiàn)了性能與復(fù)雜度之間的均衡。例如，Huang等[15]提出基于可靠度的迭代大數(shù)邏輯譯碼(RBI-MLGD)算法，該算法對初始信道信息進(jìn)行量化處理，作為信道信息的可靠度量，在譯碼迭代過程中，通過在校驗(yàn)節(jié)點(diǎn)獲取外信息對變量節(jié)點(diǎn)的可靠度信息進(jìn)行更新處理，結(jié)合大數(shù)邏輯的處理策略實(shí)現(xiàn)譯碼性能的提升。此外，Chen等[16]在RBI-MLGD算法的基礎(chǔ)上提出了改進(jìn)的譯碼(MRBI-MLGD)算法，該算法的核心思想是在迭代譯碼信息更新過程中引入修正系數(shù)，同時，只在初始信道信息的基礎(chǔ)上進(jìn)行信息更新處理，提高了譯碼信息的迭代更新效率，以此實(shí)現(xiàn)了譯碼性能的提升。由于MLGD類算法具有低復(fù)雜度、低時延的特點(diǎn)，研究者一直對其開展相關(guān)研究。最近，Song等[17]針對多元LDPC譯碼算法，基于軟可靠度迭代IISRB-MLGD譯碼算法，提出了一種裁剪的CM-IISRB譯碼算法。該算法采用非飽和截切策略，在較低復(fù)雜度的情況下，實(shí)現(xiàn)了更優(yōu)的譯碼性能。

在MRBI-MLGD譯碼算法中，由于引入了縮放因子，即采用了乘法修正系數(shù)，不可避免地增加了大量的浮點(diǎn)數(shù)乘法運(yùn)算，其譯碼復(fù)雜度隨著迭代次數(shù)的遞增而明顯增大。受MRBI-MLGD算法在譯碼迭代過程中引入縮放因子的啟發(fā)，本文提出了一種基于量化修正的低復(fù)雜度LDPC譯碼算法，該算法在對信道信息預(yù)處理時引入量化信息修正處理策略，從而避免在譯碼迭代過程中進(jìn)行譯碼信息修正處理操作，在保持譯碼性能的同時，較大幅度地降低了譯碼復(fù)雜度。基于上述算法思想，針對均勻和非均勻量化方案，本文具體實(shí)現(xiàn)了基于修正系數(shù)的均勻量化和基于列重信息修正的非均勻量化兩種譯碼方案設(shè)計(jì)，期望所提出的譯碼方案在降低譯碼復(fù)雜度的同時，還能保持一定的譯碼性能。

1 數(shù)字通信模型及相關(guān)定義

定義H=[hi,j]m×n(hi,j∈2)為一個稀疏矩陣，如矩陣H具有恒定的行重ρ，即每行非零元素個數(shù)，恒定的列重γ，即每列非零元素個數(shù)，則定義為規(guī)則LDPC碼。為方便接下來對本文算法進(jìn)行描述，定義以下兩個集合:①定義矩陣H中第i行非零列下標(biāo)集合Ni={j:0≤j≤n-1,hij≠0}；②定義矩陣H中第j列非零行下標(biāo)集合Mj={i:0≤i≤m-1,hij≠0}。設(shè)傳輸?shù)男畔⑿蛄袨榻?jīng)過LDPC編碼后可以得到碼字序列其中，滿足cHT=0。接下來對獲得的LDPC碼字序列c進(jìn)行調(diào)制，獲得發(fā)送的實(shí)數(shù)信號序列x=(x0,x1,…,xn-1)，可采用BPSK進(jìn)行調(diào)制，本文具體實(shí)現(xiàn)方法為xj=1-2cj。然后，把信號序列x經(jīng)過加性高斯白噪聲信道(AWGN)進(jìn)行傳輸，在接收端即可獲得一個接收信號序列y=(y0,y1,…,yn-1)，該序列由發(fā)送信號疊加一個高斯白噪聲信號，可以表示為yj=xj+nj，其中，nj為高斯白噪聲，且滿足nj～N(0，σ2)。

2 MRBI-MLGD算法描述

(1)

在獲得硬判決序列z后，可以計(jì)算其相應(yīng)的校驗(yàn)伴隨式s=zHT，其中，s=(s0,s1,…,sn-1)，實(shí)現(xiàn)計(jì)算方法如下：

(2)

式中，hi,j為校驗(yàn)矩陣H中的元素，符號⊕為模2加運(yùn)算，上標(biāo)k表示第k次迭代。如s=0則表示當(dāng)前判決碼字校驗(yàn)成功，可輸出碼字序列z=(z0,z1,…,zn-1)；如s≠0則表明校驗(yàn)失敗，繼續(xù)進(jìn)入迭代譯碼過程。接下來對具體的迭代譯碼過程進(jìn)行描述。

① 計(jì)算外信息。

(3)

式中，符號Nij表示除了當(dāng)前j列的其他列的序號集合。

② 計(jì)算總外信息。

(4)

③ 更新可靠度。

(5)

3 基于量化修正的譯碼算法設(shè)計(jì)

基于以上分析，為降低譯碼復(fù)雜度，本文提出了通過在信道信息初始預(yù)處理時引入量化修正處理，在迭代過程中不再使用信息修正操作，實(shí)現(xiàn)譯碼復(fù)雜度的降低。針對均勻和非均勻量化方案，本文提出了兩種量化修正方案，一種為基于修正系數(shù)的均勻量化譯碼方法，具體地，該方法通過在量化函數(shù)中引進(jìn)修正系數(shù)，避免在譯碼迭代中引進(jìn)浮點(diǎn)乘法運(yùn)算，在保持譯碼性能的前提下，實(shí)現(xiàn)了譯碼迭代過程中計(jì)算復(fù)雜度的明顯下降；另一種為基于列重γ與量化比特b的改進(jìn)型非均勻量化方案，在對3-4 bits極低量化比特的情況下，也能保持較優(yōu)秀的譯碼性能，同時，其算法復(fù)雜度和硬件資源消耗也大為降低，該方案可用于硬件資源遭受限制的場景。

3.1 基于修正系數(shù)的均勻量化及譯碼方案設(shè)計(jì)

由譯碼判決信息規(guī)則和量化原理可知，在不改變信道信息可靠度極性的情況下，不會影響LDPC碼字的判決，因此，可以對可靠度值進(jìn)行縮放處理。為了避免在迭代譯碼過程中引入乘法修正運(yùn)算，降低迭代譯碼過程的計(jì)算復(fù)雜度，本文提出的算法1為在對信道信息量化預(yù)處理時引入修正系數(shù)β，對量化值進(jìn)行預(yù)修正處理。具體計(jì)算方法如下：

(6)

式中，b為量化比特位數(shù)，Δ為量化間隔。采用修正系數(shù)β對量化值進(jìn)行修正，通過修正處理，使信道初始可靠度值與譯碼迭代過程中的譯碼信息更新在數(shù)值上相適配，從而實(shí)現(xiàn)更有效的譯碼信息更新，獲得譯碼性能的提升。其中，β值可以通過仿真搜索獲得。

此外，在MRBI-MLGD算法中變量節(jié)點(diǎn)信息更新策略式(5)修改如下：

(7)

對本文提出的算法1——基于修正系數(shù)的均勻量化方案及LDPC譯碼算法具體實(shí)現(xiàn)步驟描述如下。

步驟1:輸入。

最大迭代次數(shù)Imax，接收信號向量y，修正系數(shù)β，量化參數(shù)b和Δ。

步驟2:初始化。

按式(6)對接收信號y進(jìn)行量化得到qj，將迭代次數(shù)k置0，對0≤j≤n-1，令初始可靠度

步驟3:迭代過程。對k

① 按式(1)計(jì)算硬判決序列z(k)；

② 按式(2)計(jì)算校驗(yàn)和s(k)，如果s(k)=0，則執(zhí)行步驟4；

⑥ 迭代次數(shù)k=k+1。

步驟4:輸出。

輸出硬判決序列z(k)。

3.2 基于列重修正的非均勻量化及譯碼方案設(shè)計(jì)

qj=

(8)

本量化設(shè)計(jì)方案也是采用在量化預(yù)處理階段對信道信息進(jìn)行相應(yīng)處理，因此，其譯碼迭代時可靠度的更新規(guī)則采用式(7)進(jìn)行。

對本文提出的算法2——基于列重修正的非均勻量化及LDPC譯碼算法具體實(shí)現(xiàn)步驟描述如下。

步驟1:輸入。

最大迭代次數(shù)Imax，接收信號向量y，修正系數(shù)β，量化參數(shù)b和Δ。

步驟2:初始化。

按式(8)對接收信號y進(jìn)行量化得到qj，將迭代次數(shù)k置0，對0≤j≤n-1，令初始可靠度

步驟3:迭代過程。對k

① 按式(1)計(jì)算硬判決序列z(k)；

② 按式(2)計(jì)算校驗(yàn)和s(k)，如果s(k)=0，則執(zhí)行步驟4；

⑥ 迭代次數(shù)k=k+1。

步驟4:輸出。

輸出硬判決序列z(k)。

4 譯碼復(fù)雜度和性能仿真分析

4.1 譯碼復(fù)雜度

本文提出的基于量化修正的譯碼算法復(fù)雜度主要由以下幾個部分組成：

① 式(1)計(jì)算硬判決z(k)時，需要進(jìn)行n次邏輯運(yùn)算；

② 式(2)計(jì)算校驗(yàn)和s(k)時，需要m(ρ-1)=nγ-m次邏輯運(yùn)算(其中ρ為行重，mρ=nγ為校驗(yàn)矩陣H的非零因子的個數(shù))；

同時，本文對RBI-MLGD、MRBI-MLGD及經(jīng)典的SPA算法進(jìn)行了復(fù)雜度分析。詳細(xì)的復(fù)雜度對比情況如表1所示。

表1 單次譯碼迭代計(jì)算復(fù)雜度比較Table 1 Comparison table of computational complexity of single decoding iteration

其中，BO為二進(jìn)制操作，AO為加法運(yùn)算，RM為實(shí)數(shù)乘法，Log為對數(shù)運(yùn)算。從表1可以看出，本文提出的改進(jìn)算法與原始的RBI-MLGD算法復(fù)雜度基本一致，本算法相比MRBI-MLGD算法，省掉了譯碼迭代過程中可靠度更新時的實(shí)數(shù)乘法計(jì)算，將會明顯降低譯碼迭代過程中的復(fù)雜度。為直觀地看出單次計(jì)算復(fù)雜度的數(shù)值情況，下面對具體的LDPC碼單次計(jì)算復(fù)雜度進(jìn)行數(shù)值計(jì)算。

表2 2(1 023,781)規(guī)則循環(huán)LDPC碼單次迭代計(jì)算復(fù)雜度Table 2 2 ( 1 023, 781 ) single iteration computational complexity of regular cyclic LDPC codes

表2 2(1 023,781)規(guī)則循環(huán)LDPC碼單次迭代計(jì)算復(fù)雜度Table 2 2 ( 1 023, 781 ) single iteration computational complexity of regular cyclic LDPC codes

算法名稱Nameofalgorithm單次迭代運(yùn)算量NumberofoperationsperiterationBOAORMLogProposed6547232736RBI MLGD6547232736MRBI MLGD65472327361023SPA1964161023

表3 2(255,175)規(guī)則循環(huán)LDPC碼單次迭代計(jì)算復(fù)雜度Table 3 2 ( 255, 175) single iteration computational complexity of regular cyclic LDPC codes

表3 2(255,175)規(guī)則循環(huán)LDPC碼單次迭代計(jì)算復(fù)雜度Table 3 2 ( 255, 175) single iteration computational complexity of regular cyclic LDPC codes

算法名稱Nameofalgorithm單次迭代運(yùn)算量NumberofoperationsperiterationBOAORMLogProposed81604080RBI MLGD81604080MRBI MLGD81604080255SPA24480255

4.2 譯碼性能

根據(jù)上文的算法描述，繼續(xù)通過計(jì)算機(jī)仿真的方法，對提出的譯碼算法進(jìn)行仿真實(shí)驗(yàn)，考察其譯碼性能。

實(shí)驗(yàn)1：實(shí)驗(yàn)采用基于歐式幾何方法構(gòu)造的2(1 023,781)規(guī)則循環(huán)LDPC碼[18]進(jìn)行仿真實(shí)驗(yàn)，其仿真參數(shù)采用以下設(shè)置：① 對均勻量化，量化比特b=8 bit，量化間隔Δ=0.015 6；② 對MRBI-MLGD譯碼算法，設(shè)置縮放因子α=3.1；③ 對算法1，設(shè)置修正系數(shù)β=0.322 58；④ 對算法2采用非均勻量化，設(shè)置量化比特b=4 bit，r=0.88。所有算法中，最大仿真迭代次數(shù)均設(shè)置為Imax=30。譯碼BER性能仿真曲線如圖1所示。

從圖1可以看出，在中高信噪比區(qū)域，算法1與MRBI-MLGD算法擁有幾乎相同的譯碼性能，而相較于RBI-MLGD算法具有約0.3 dB的性能增益，與SPA譯碼算法僅有約0.6 dB的譯碼性能差距；算法2由于采用了較低的量化比特，譯碼性能稍差于算法1，但仍然明顯優(yōu)于RBI-MLGD算法。

圖1 對2(1 023,781)LDPC碼的譯碼BER性能比較Fig.1 BER performance comparison of 2(1 023,781) LDPC code

圖2 對2(1 023,781)LDPC碼的譯碼平均迭代次數(shù)比較Fig.2 Comparison of decoding average iterations of 2(1 023,781) LDPC code

實(shí)驗(yàn)2：實(shí)驗(yàn)采用2(255,175)規(guī)則循環(huán)LDPC碼[18]進(jìn)行仿真實(shí)驗(yàn)，其仿真參數(shù)采用以下設(shè)置：① 對均勻量化，量化比特b=8 bit，量化間隔Δ=0.015 6；② 對MRBI-MLGD譯碼算法，設(shè)置修正系數(shù)α=7.0；③ 對算法1，設(shè)置修正系數(shù)β=0.143；④對算法2采用非均勻量化，設(shè)置量化比特b=4 bit，r=0.88。所有算法中，最大仿真迭代次數(shù)均設(shè)置為Imax=30。譯碼BER性能仿真曲線如圖3所示。

從譯碼性能曲線(圖3)可以看出，算法1在中信噪比范圍區(qū)間與MRBI-MLGD算法幾乎具有相同的譯碼性能，同時優(yōu)于RBI-MLGD譯碼算法近0.4 dB的譯碼性能。與SPA譯碼算法具有約0.7 dB的性能差距；算法2在量化比特b=4 bit的情況下，仍實(shí)現(xiàn)了與MRBI-MLGD算法幾乎相近的譯碼性能，同時，與SPA算法有約0.7 dB的性能差距。而在高信噪比區(qū)域，本文算法仍具有較優(yōu)異的譯碼性能，出現(xiàn)了譯碼性能曲線明顯優(yōu)于MRBI-MLGD算法的趨勢。

圖3 對2(255,175) LDPC碼的譯碼BER性能比較Fig.3 BER performance comparison of 2(255,175) LDPC code

從譯碼平均迭代次數(shù)曲線(圖4)可以看出，算法1的譯碼迭代收斂速度明顯高于RBI-MLGD譯碼算法，與MRBI-MLGD算法保持了一致的迭代收斂速度。此外，在較高信噪比時，其譯碼收斂速度幾乎接近SPA算法。算法2在量化比特較低的情況下，仍然實(shí)現(xiàn)了較高的譯碼收斂速度，收斂速度性能與算法1一致。

圖4 對2(255,175) LDPC碼的譯碼平均迭代次數(shù)比較Fig.4 Comparison of decoding average iterations of 2(255,175) LDPC code

5 結(jié)束語

本文在對信道信息進(jìn)行量化預(yù)處理時，通過引入量化修正的信息處理策略，提出了基于量化修正的低復(fù)雜度LDPC譯碼算法。該算法避免了在譯碼迭代過程中進(jìn)行信息修正處理操作，較大幅度地降低了譯碼復(fù)雜度，同時保持了較好的譯碼性能。本文具體實(shí)現(xiàn)了算法1為一種基于修正系數(shù)的均勻量化方案及譯碼算法設(shè)計(jì)；算法2為一種基于列重修正的非均勻量化方案及譯碼算法設(shè)計(jì)。其中，算法1通過在信道信息量化預(yù)處理時，在量化函數(shù)中引入修正系數(shù)，避免在譯碼迭代中的浮點(diǎn)乘法運(yùn)算，實(shí)現(xiàn)了譯碼迭代過程中計(jì)算復(fù)雜度的明顯下降；算法2通過在非均勻量化預(yù)處理時引入列重γ信息，實(shí)現(xiàn)了信道信息量化可靠度值與列重γ相適配的比擬關(guān)系，在迭代過程中獲得更高效的譯碼信息傳遞和更新。仿真結(jié)果表明，在保持譯碼性能的情況下，本設(shè)計(jì)有效地降低了譯碼復(fù)雜度。