低復雜度LDPC碼信息瓶頸量化譯碼器設計

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

(1.西安電子科技大學 綜合業務網理論及關鍵技術國家重點實驗室，陜西 西安 710071；2.西安郵電大學 電子工程學院，陜西 西安 710121；3.阿里巴巴集團，浙江 杭州 311121)

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

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

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

近年來，對低密度校驗碼的信息瓶頸量化譯碼器的研究逐步深入，已經基本形成一套系統的設計方案。文獻[7]中由和積算法推導了信息瓶頸量化譯碼器，并研究了設計信噪比對信息瓶頸量化譯碼器性能的影響。文獻[8]中在數字信號處理器上實現了規則低密度校驗碼的信息瓶頸量化譯碼器，驗證了其吞吐量優于最小和譯碼器。文獻[9]中總結了規則低密度校驗碼的信息瓶頸量化譯碼器的設計流程，提供了一個通用的規則低密度校驗碼信息瓶頸量化譯碼器的設計框架，給出了尋找最佳設計信噪比的一種啟發式方法，分析了量化位寬和碼長對規則低密度校驗碼信息瓶頸量化譯碼器性能的影響。關于信息瓶頸方法在低密度校驗碼量化譯碼器中的更多應用可以進一步參考文獻[10-14]。

雖然信息瓶頸量化譯碼器在存儲空間、吞吐量以及譯碼性能方面都有很好的表現，但是仔細分析其譯碼過程，不難發現其局部節點運算中某些消息存在重復計算的現象，從而導致其查表次數與節點度數的平方成正比。為避免消息重復計算，筆者提出了一種基于前后向算法的信息瓶頸量化譯碼器優化設計方案。所提方案能有效地減少信息瓶頸量化譯碼器的查表次數，使得節點的查表次數從平方量級降低為線性量級。

1 信息瓶頸方法及其在低密度校驗碼量化譯碼器中的應用

1.1 信息瓶頸方法

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

圖1 信息瓶頸方法所研究的問題[10]

(1)

為了便于量化器實現，一個自然的要求就是給定一個觀測值y，可以找到與之對應的惟一的壓縮值t，即p(t|y)是一個確定性映射。這就意味著p(t|y)可以用某個函數t=f(y)來描述。

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

圖2 信息瓶頸算法[9]

下面將簡要回顧文獻[9]中原信息瓶頸量化譯碼器涉及的兩個環節：信道輸出信號的量化以及節點處局部運算的量化實現。

1.2 AWGN信道輸出信號的信息瓶頸量化處理

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

(2)

1.3 LDPC碼IB量化譯碼器設計

本節簡要回顧文獻[9]中的信息瓶頸量化譯碼器設計方法。信息瓶頸量化譯碼器只涉及無符號整數，它以信道輸出信號的量化值為輸入，并以查表操作替代校驗和變量節點的局部運算。

圖3 度5校驗節點拆分為3個度3校驗節點的串聯

(3)

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

類似校驗節點的信息瓶頸量化實現，變量節點的消息更新也可以利用信息瓶頸方法構造查找表來完成。具體實現方法不再贅述，可以參考文獻[9]。度為dv的變量節點每輪迭代需要進行dv(dv-1)+1次查表。

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

2 基于前后向算法的低密度校驗碼信息瓶頸量化譯碼器設計

2.1 基于前后向算法的信息瓶頸校驗節點操作

(4)

(5)

(6)

為便于讀者理解算法，下面以度7的校驗節點為例進行說明，如圖4所示。

(a) 前向查表過程

圖5 低密度校驗碼FB-IB量化譯碼器校驗節點輸出外信息

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

2.2 基于前后向算法的信息瓶頸變量節點操作

(a) 前向查表

3 復雜度分析及仿真結果

考慮一個規則低密度校驗碼，記其校驗節點度為dc，變量節點度為dv。表1對比了筆者提出的方案和文獻[9]的方案在一輪迭代過程中，局部運算各自需要的表格數目和查表次數。需要說明的是，兩種方案所用單張表格的大小相同，且只與譯碼器的量化位寬相關。當采用量化位寬為q比特時，無符號整數T取值空間的基數|T|=2q。

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

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

(a) 查表復雜度對比

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

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

4 結束語

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