低復(fù)雜度LDPC碼信息瓶頸量化譯碼器設(shè)計(jì)

胡繼文，鄭慧娟，童 勝，白寶明，徐達(dá)人，王仲立

(1.西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071；2.西安郵電大學(xué) 電子工程學(xué)院，陜西 西安 710121；3.阿里巴巴集團(tuán)，浙江 杭州 311121)

低密度校驗(yàn)碼(Low-Density Parity-Check，LDPC)碼是一類性能優(yōu)異的信道編碼方案[1]。自上世紀(jì)90年代中期被重新發(fā)現(xiàn)以來(lái)，低密度校驗(yàn)碼得到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。目前，低密度校驗(yàn)碼已經(jīng)被國(guó)內(nèi)外多個(gè)通信標(biāo)準(zhǔn)采納，包括中國(guó)移動(dòng)多媒體廣播標(biāo)準(zhǔn)、WiMax、DVB-S2、IEEE 802.3以及最新的5G新空口等。在低密度校驗(yàn)碼的實(shí)用化進(jìn)程中，一個(gè)關(guān)鍵環(huán)節(jié)是高效低密度校驗(yàn)碼譯碼器的設(shè)計(jì)。特別是在高端芯片受制的場(chǎng)合下，可通過(guò)算法層面突破限制，研發(fā)低實(shí)現(xiàn)復(fù)雜度、高性能量化譯碼算法，這是一條值得嘗試的途徑。

低密度校驗(yàn)碼量化譯碼算法的設(shè)計(jì)涉及兩方面[2]：一是對(duì)接收信號(hào)以及迭代譯碼過(guò)程中所傳遞消息的量化；二是譯碼算法中變量/校驗(yàn)節(jié)點(diǎn)局部運(yùn)算的量化實(shí)現(xiàn)。消息的量化方案可以分為均勻量化和非均勻量化兩種[3]：均勻量化實(shí)現(xiàn)簡(jiǎn)單，但是一般需要較大的量化位寬才能保證譯碼器的性能；相對(duì)而言，優(yōu)化設(shè)計(jì)的非均勻量化方案在相同位寬條件下有望獲得更好的譯碼性能。量化位寬是量化算法的關(guān)鍵因素，它極大地影響了量化譯碼器的譯碼性能。一般而言，量化位寬越大，譯碼性能越好。然而，文獻(xiàn)[4]的研究表明，減少量化位寬可以帶來(lái)眾多好處：有效地減少存儲(chǔ)空間，降低譯碼器硬件實(shí)現(xiàn)規(guī)模，提升運(yùn)算速度，緩解現(xiàn)場(chǎng)可編程門陣列(FPGA)布線的擁塞問(wèn)題等。因此，在保證可接受的譯碼性能前提下，低位寬量化方案的優(yōu)化設(shè)計(jì)是量化譯碼器設(shè)計(jì)的關(guān)鍵問(wèn)題之一。對(duì)于量化譯碼器設(shè)計(jì)的另一方面，即變量/校驗(yàn)節(jié)點(diǎn)的局部運(yùn)算的量化實(shí)現(xiàn)，首先需要考慮的是譯碼算法的選擇。通常有兩種選擇，即和積算法和修正最小和算法。和積算法性能優(yōu)于修正最小和算法，但是它的運(yùn)算復(fù)雜度也更高。特別是和積算法的校驗(yàn)節(jié)點(diǎn)運(yùn)算涉及復(fù)雜的超越函數(shù)計(jì)算，不利于硬件實(shí)現(xiàn)。因此，許多硬件實(shí)現(xiàn)方案都以犧牲譯碼性能為代價(jià)選擇計(jì)算復(fù)雜度更低的修正最小和算法[5]。

綜上所述，基于性能更優(yōu)的和積算法來(lái)設(shè)計(jì)低位寬高性能的低密度校驗(yàn)碼量化譯碼器是具有實(shí)際應(yīng)用價(jià)值的。近年來(lái)，已有一些學(xué)者將起源于信息論和機(jī)器學(xué)習(xí)領(lǐng)域的信息瓶頸(Information-Bottleneck，IB)[6]方法成功地應(yīng)用于低密度校驗(yàn)碼的量化譯碼器設(shè)計(jì)當(dāng)中，獲得了很好的效果[7-14]。基于信息瓶頸方法的低密度校驗(yàn)碼量化譯碼器設(shè)計(jì)，以互信息為度量對(duì)消息(包括接收信號(hào)和迭代譯碼中傳遞的消息)進(jìn)行量化處理，將所有消息都用無(wú)符號(hào)整型數(shù)進(jìn)行表示，從而便于實(shí)際硬件實(shí)現(xiàn)。特別是在消息的量化過(guò)程中，以互信息最大化為優(yōu)化目標(biāo)。從保留信息量的角度看，基于信息瓶頸方法的量化方案是最佳的。此外，在校驗(yàn)節(jié)點(diǎn)消息更新的過(guò)程中，復(fù)雜的函數(shù)運(yùn)算也通過(guò)信息瓶頸方法簡(jiǎn)化為簡(jiǎn)單的查表操作，從而大大地簡(jiǎn)化了運(yùn)算復(fù)雜度。需要特別說(shuō)明的是，在查找表的構(gòu)建過(guò)程中，信息瓶頸方法以使得查表所得無(wú)符號(hào)整型數(shù)消息和其所代表的編碼比特的互信息最大化為優(yōu)化目標(biāo)[7]，因此所構(gòu)造的查找表在信息論意義下也是最佳的。由上所述，低密度校驗(yàn)碼的信息瓶頸量化譯碼器是基于最佳的和積譯碼算法為基礎(chǔ)設(shè)計(jì)的，并且在消息量化和節(jié)點(diǎn)量化實(shí)現(xiàn)兩個(gè)方面均以互信息最大化為優(yōu)化目標(biāo)，是一種信息最佳量化譯碼器設(shè)計(jì)方法。這也就很好地解釋了其譯碼性能的優(yōu)異性。實(shí)際上，仿真結(jié)果表明基于信息瓶頸方法的4 bit低密度校驗(yàn)碼量化譯碼器能夠獲得比未量化和積譯碼0.1 dB的優(yōu)異性能。

近年來(lái)，對(duì)低密度校驗(yàn)碼的信息瓶頸量化譯碼器的研究逐步深入，已經(jīng)基本形成一套系統(tǒng)的設(shè)計(jì)方案。文獻(xiàn)[7]中由和積算法推導(dǎo)了信息瓶頸量化譯碼器，并研究了設(shè)計(jì)信噪比對(duì)信息瓶頸量化譯碼器性能的影響。文獻(xiàn)[8]中在數(shù)字信號(hào)處理器上實(shí)現(xiàn)了規(guī)則低密度校驗(yàn)碼的信息瓶頸量化譯碼器，驗(yàn)證了其吞吐量?jī)?yōu)于最小和譯碼器。文獻(xiàn)[9]中總結(jié)了規(guī)則低密度校驗(yàn)碼的信息瓶頸量化譯碼器的設(shè)計(jì)流程，提供了一個(gè)通用的規(guī)則低密度校驗(yàn)碼信息瓶頸量化譯碼器的設(shè)計(jì)框架，給出了尋找最佳設(shè)計(jì)信噪比的一種啟發(fā)式方法，分析了量化位寬和碼長(zhǎng)對(duì)規(guī)則低密度校驗(yàn)碼信息瓶頸量化譯碼器性能的影響。關(guān)于信息瓶頸方法在低密度校驗(yàn)碼量化譯碼器中的更多應(yīng)用可以進(jìn)一步參考文獻(xiàn)[10-14]。

雖然信息瓶頸量化譯碼器在存儲(chǔ)空間、吞吐量以及譯碼性能方面都有很好的表現(xiàn)，但是仔細(xì)分析其譯碼過(guò)程，不難發(fā)現(xiàn)其局部節(jié)點(diǎn)運(yùn)算中某些消息存在重復(fù)計(jì)算的現(xiàn)象，從而導(dǎo)致其查表次數(shù)與節(jié)點(diǎn)度數(shù)的平方成正比。為避免消息重復(fù)計(jì)算，筆者提出了一種基于前后向算法的信息瓶頸量化譯碼器優(yōu)化設(shè)計(jì)方案。所提方案能有效地減少信息瓶頸量化譯碼器的查表次數(shù)，使得節(jié)點(diǎn)的查表次數(shù)從平方量級(jí)降低為線性量級(jí)。

1 信息瓶頸方法及其在低密度校驗(yàn)碼量化譯碼器中的應(yīng)用

1.1 信息瓶頸方法

信息瓶頸方法于1999年由TISHBY等[6]學(xué)者提出，它起源于信息論和機(jī)器學(xué)習(xí)領(lǐng)域，是一種適用于數(shù)據(jù)壓縮的通用信息理論框架。信息瓶頸方法通過(guò)引入相關(guān)變量X，實(shí)現(xiàn)對(duì)觀測(cè)變量Y進(jìn)行數(shù)據(jù)壓縮，從而得到壓縮變量T，如圖1所示。為此，信息瓶頸方法引入了兩個(gè)目標(biāo)：一是使互信息I(T；Y)最小化，即盡可能簡(jiǎn)潔地表示Y；二是最大化互信息I(T；X)，即盡可能讓壓縮變量T保留更多關(guān)于X的信息。變量X與變量Y通常是相關(guān)的，比如可以將Y看成是X經(jīng)過(guò)信道傳輸后得到的觀測(cè)值，它們的聯(lián)合概率密度記為p(x，y)。變量T是由Y壓縮而來(lái)的，即X→Y→T構(gòu)成馬爾可夫鏈。變量Y和T之間的壓縮關(guān)系可以描述為Y到T的某種映射[9]，用概率論語(yǔ)言描述，這種映射可以表示為T與Y之間的條件概率分布p(t|y)。注意，上述壓縮問(wèn)題是一個(gè)雙目標(biāo)優(yōu)化問(wèn)題。為了便于求解，可以固定T取值空間的基數(shù)|T|，從而將所考慮的問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題，即在給定|T|的前提下，尋找可以使得互信息I(T；X)最大化的映射p(t|y)[9]：

圖1 信息瓶頸方法所研究的問(wèn)題[10]

(1)

為了便于量化器實(shí)現(xiàn)，一個(gè)自然的要求就是給定一個(gè)觀測(cè)值y，可以找到與之對(duì)應(yīng)的惟一的壓縮值t，即p(t|y)是一個(gè)確定性映射。這就意味著p(t|y)可以用某個(gè)函數(shù)t=f(y)來(lái)描述。

信息瓶頸算法是信息瓶頸方法的具體實(shí)現(xiàn)。如圖2所示，在輸入聯(lián)合概率分布p(x，y)和T取值空間的基數(shù)|T|時(shí)，信息瓶頸算法會(huì)優(yōu)化出確定性映射p(t|y)，以使互信息I(T；X)最大化[9]。自信息瓶頸方法提出之后，出現(xiàn)了適用于不同應(yīng)用的多種信息瓶頸算法[9]。文獻(xiàn)[9]給出了一種低復(fù)雜度的信息瓶頸算法，稱為專用序貫信息瓶頸算法。由于該算法只優(yōu)化量化區(qū)間的邊界，其計(jì)算復(fù)雜度很低。在下面的信道輸出量化和低密度校驗(yàn)碼信息瓶頸量化譯碼器的構(gòu)造過(guò)程中，都采用了該算法。由于篇幅受限，這里就不再贅述，有興趣的讀者可參考文獻(xiàn)[9]。

圖2 信息瓶頸算法[9]

下面將簡(jiǎn)要回顧文獻(xiàn)[9]中原信息瓶頸量化譯碼器涉及的兩個(gè)環(huán)節(jié)：信道輸出信號(hào)的量化以及節(jié)點(diǎn)處局部運(yùn)算的量化實(shí)現(xiàn)。

1.2 AWGN信道輸出信號(hào)的信息瓶頸量化處理

這里考慮BPSK調(diào)制以及AWGN信道。編碼比特b∈{0，1}經(jīng)過(guò)BPSK調(diào)制后，映射成符號(hào)x=-2b+1，然后將x在AWGN信道上傳遞，在接收端得到接收信號(hào)y=x+n，n～N(0，σ2)。接收信號(hào)y和發(fā)送信號(hào)x的聯(lián)合概率分布為

(2)

1.3 LDPC碼IB量化譯碼器設(shè)計(jì)

本節(jié)簡(jiǎn)要回顧文獻(xiàn)[9]中的信息瓶頸量化譯碼器設(shè)計(jì)方法。信息瓶頸量化譯碼器只涉及無(wú)符號(hào)整數(shù)，它以信道輸出信號(hào)的量化值為輸入，并以查表操作替代校驗(yàn)和變量節(jié)點(diǎn)的局部運(yùn)算。

圖3 度5校驗(yàn)節(jié)點(diǎn)拆分為3個(gè)度3校驗(yàn)節(jié)點(diǎn)的串聯(lián)

(3)

綜上所述，在每輪迭代中，一個(gè)度為dc的校驗(yàn)節(jié)點(diǎn)需要的查找表數(shù)目為(dc-2)。與之相連的dc條邊都需要產(chǎn)生外信息，每條邊涉及(dc-2)次查表操作，該節(jié)點(diǎn)共需要進(jìn)行的查表次數(shù)為dc(dc-2)。這意味著查表次數(shù)與校驗(yàn)節(jié)點(diǎn)度數(shù)的平方成正比。這對(duì)于dc取值較大的LDPC碼而言是不利的。

類似校驗(yàn)節(jié)點(diǎn)的信息瓶頸量化實(shí)現(xiàn)，變量節(jié)點(diǎn)的消息更新也可以利用信息瓶頸方法構(gòu)造查找表來(lái)完成。具體實(shí)現(xiàn)方法不再贅述，可以參考文獻(xiàn)[9]。度為dv的變量節(jié)點(diǎn)每輪迭代需要進(jìn)行dv(dv-1)+1次查表。

值得一提的是，每輪迭代后，可以對(duì)變量節(jié)點(diǎn)取值做硬判決。由于對(duì)數(shù)似然比的分布是對(duì)稱的，且其排序和離散消息取值的排序是一致的，只需要將變量節(jié)點(diǎn)的后驗(yàn)離散消息與|T|/2比較即可。

2 基于前后向算法的低密度校驗(yàn)碼信息瓶頸量化譯碼器設(shè)計(jì)

2.1 基于前后向算法的信息瓶頸校驗(yàn)節(jié)點(diǎn)操作

(4)

(5)

(6)

為便于讀者理解算法，下面以度7的校驗(yàn)節(jié)點(diǎn)為例進(jìn)行說(shuō)明，如圖4所示。

(a) 前向查表過(guò)程

圖5 低密度校驗(yàn)碼FB-IB量化譯碼器校驗(yàn)節(jié)點(diǎn)輸出外信息

由式(4)和式(5)可知，前向和后向查表共需要2(dc-2)次。為剩余(dc-2)條邊生成外信息時(shí)，每生成一個(gè)外信息需要一次查表，所以輸出外信息的過(guò)程需要(dc-2)次查表。因此，基于前后向算法的校驗(yàn)節(jié)點(diǎn)操作需要的查表次數(shù)為3(dc-2)，而原信息瓶頸量化譯碼器中一個(gè)度dc的校驗(yàn)節(jié)點(diǎn)需要dc(dc-2)次查表操作[9]，即查表次數(shù)從度數(shù)的平方量級(jí)降低到線性量級(jí)。顯然，校驗(yàn)節(jié)點(diǎn)度數(shù)越大，降低的查表次數(shù)越可觀。因此，該方法在高碼率低密度校驗(yàn)碼上具有較好的實(shí)用價(jià)值。

2.2 基于前后向算法的信息瓶頸變量節(jié)點(diǎn)操作

(a) 前向查表

3 復(fù)雜度分析及仿真結(jié)果

考慮一個(gè)規(guī)則低密度校驗(yàn)碼，記其校驗(yàn)節(jié)點(diǎn)度為dc，變量節(jié)點(diǎn)度為dv。表1對(duì)比了筆者提出的方案和文獻(xiàn)[9]的方案在一輪迭代過(guò)程中，局部運(yùn)算各自需要的表格數(shù)目和查表次數(shù)。需要說(shuō)明的是，兩種方案所用單張表格的大小相同，且只與譯碼器的量化位寬相關(guān)。當(dāng)采用量化位寬為q比特時(shí)，無(wú)符號(hào)整數(shù)T取值空間的基數(shù)|T|=2q。

表1 每輪迭代兩種方案各自需要的表格數(shù)目和查表次數(shù)

筆者考查了802.3 an標(biāo)準(zhǔn)中的碼率約為0.84的(2 048，1 723)低密度校驗(yàn)碼[17]來(lái)驗(yàn)證所提方案。該碼的校驗(yàn)節(jié)點(diǎn)度數(shù)dc=32，變量節(jié)點(diǎn)度數(shù)dv=6。按照表1的結(jié)論對(duì)比了該碼使用文獻(xiàn)[9]方案和所提方案設(shè)計(jì)的信息瓶頸譯碼器在單個(gè)節(jié)點(diǎn)更新消息時(shí)需要進(jìn)行的查表次數(shù)，見(jiàn)圖7(a)。從理論分析的角度可以看出，筆者所提的FB-IB量化譯碼器的查表次數(shù)遠(yuǎn)遠(yuǎn)低于原始圖7 兩種IB 譯碼器的性能對(duì)比方案。圖7(b)比較了軟件仿真5 000幀碼字所需譯碼時(shí)間，驗(yàn)證了所提方案的有效性，其中仿真軟件為Visual Studio 2017，編程語(yǔ)言為C語(yǔ)言。

(a) 查表復(fù)雜度對(duì)比

圖8對(duì)比了(2 048，1 723)低密度校驗(yàn)碼在不同量化譯碼算法下的性能。這里的仿真條件如下：BPSK調(diào)制下的AWGN信道，最大迭代次數(shù)為50。圖8中floatSPA為雙精度和積譯碼器，Qm.f量化SPA譯碼器使用的是來(lái)自文獻(xiàn)[3]的均勻量化方案，其中m表示消息整數(shù)位使用的比特?cái)?shù)，f表示消息小數(shù)位使用的比特?cái)?shù)。信息瓶頸為文獻(xiàn)[9]的方案，F(xiàn)B-IB為筆者所提方案。由圖8可知，所提的4 bit FB-IB譯碼器與原4 bit信息瓶頸譯碼器的性能大致相當(dāng)，且都明顯優(yōu)于6 bit均勻量化低密度校驗(yàn)譯碼器。當(dāng)誤碼率為10-6時(shí)，所提4 bit FB-IB譯碼器以及原4 bit信息瓶頸譯碼器與雙精度SPA譯碼器的譯碼性能差距不到0.1 dB。

圖8 (2 048，1 723)LDPC碼在不同譯碼算法下的性能比較

4 結(jié)束語(yǔ)

筆者提出了一種基于前后向算法的低復(fù)雜度LDPC碼信息瓶頸量化譯碼器設(shè)計(jì)方案。該方案充分地利用了前向查表和后向查表產(chǎn)生的中間結(jié)果，有效地減少了查表次數(shù)。筆者以增加少量的空間復(fù)雜度為代價(jià)，所提設(shè)計(jì)方案可以將譯碼器的查表次數(shù)從平方量級(jí)降低到線性量級(jí)，更加適用于校驗(yàn)節(jié)點(diǎn)度數(shù)較大的高碼率LDPC碼。仿真結(jié)果表明，所提前后向信息瓶頸量化譯碼器的性能與原信息瓶頸量化譯碼器的性能相當(dāng)，量化位寬為4 bit就可逼近未量化譯碼器的性能，驗(yàn)證了所提前后向信息瓶頸譯碼器的有效性。