無短環不規則QC_LDPC碼的快速編碼及聯合譯碼

劉蕾等

摘 要： 基于不規則部分并行結構設計了一種高吞吐量，低復雜度，碼長碼率可變且去除四環的低密度奇偶校驗LDPC碼及其譯碼結構實現方案，該編碼結構可針對不同碼長的不規則部分并行結構LDPC碼進行擴展，譯碼器采用縮放最小和定點（Sum?Min）算法實現譯碼，中間信息節點存儲器地址采用格雷碼編碼，降低動態功耗；采用Xilinx公司的Virtex?5 XC5VtX150T?ff1156FPGA芯片設計了一款碼長1 270，碼率[12]的不規則部分并行LDPC碼的編碼器和譯碼器。綜合結果表明：該編碼器信息吞吐量為2.52 Gb/s，譯碼器在10次迭代的情況下信息吞吐率達到44 Mb/s。

關鍵詞： 低密度奇偶校驗碼； 不規則碼； 部分并行結構； FPGA

中圖分類號： TN911.22?34 文獻標識碼： A 文章編號： 1004?373X（2015）17?0034?04

Fast coding and joint decoding of irregular QC_LDPC codes without short?cycle

LIU Lei1， SUN Shulong1， CHANG Liang2， LI Huawang2

（1. Shanghai Institute of Microsystem and Information Technology， Chinese Academy of Sciences， Shanghai 200050， China；

2. Shanghai Engineering Center for Microsatellites， Shanghai 200120， China）

Abstract： The low density parity check （LDPC） codes and the implementation scheme of the decoding structure were designed based on irregular semi?parallel structure. LDPC codes without four cycles have high throughput and low complexity， whose length and rate are variable. This coding structure can extend irregular semi?parallel LDPC codes with different code length. The decoder adopts Sum?Min algorithm to realize decoding. The memory address of middle information nodes applies Gray coding to reduce dynamic power consumption. Based on this structure， encoder and decoder of irregular semi?parallel LDPC codes were designed by using Xilinx Virtex?5 XC5VtX150T?ff1156 FPGA， whose code length is 1 270 bit and code rate is [12.] The comprehensive results show that the information throughput of this encoder can achieve 2.52 Gb/s and the information throughput rate of the decoder can reach 44 Mb/s in the case of 10 iterations.

Keywords： LDPC code； irregular code； semi?parallel structure； FPGA

0 引 言

低密度奇偶校驗碼（Low Desity Parity Check，LDPC）又被稱為Gallager碼，是Gallager在1960年提出的，LDPC碼在AWGN信道下具有非常好的性能，目前最好的仿真結果表明，隨機LDPC碼在AWGN白噪聲下距離Shannon限僅0.004 5 dB。LDPC碼是一類逼近Shannon限的隨機碼，其譯碼復雜度低，信息吞吐量大，靈活性高，可以避免Turbo碼類似的錯誤平層，且完全可并行實現，更適合高速的無線數據業務。LDPC面臨的最主要問題是它的編碼復雜度高，是碼長的O（[N2]），而Turbo碼的編碼復雜度與碼長線性相關?，F在結構化準循環LDPC碼是編碼結構的研究熱點，可以在譯碼性能保持的前提下，用來簡化編碼器的復雜度， 已經被業內廣泛采用，目前，由于結構化LDPC碼性能優越，已經被IEEE 802.16e，IEEE 802.11n，IEEE 802.3an和DVB?S.2等標準采用，并被廣泛應用于衛星通信，深空通信，光通信和下一代移動通信系統中。

為了在工程實踐中降低編譯碼器的復雜度，研究人員系統地研究了結構化LDPC碼的硬件實現技術，發現了一些制約LDPC碼的編碼器和譯碼器高速實現的因素，具體包括：編碼器如果直接由生成截止實現，工程復雜度過高；全并行譯碼器結構實現時內部聯系過多，運算單元過于復雜；對于串行結構，LDPC碼的高速并行特點很難發揮。

針對以上問題，本文提出了一種高吞吐量，低復雜度并且碼速、碼率可擴展的非奇異子矩陣的不規則部分并行編碼、譯碼結構，構造了性能優良、結構合理的部分并行譯碼實現的結構化LDPC碼校驗矩陣，并采用Xilinx公司的Virtex?5 XC5VtX150T?ff1156 FPGA芯片設計了一款碼長1 270，碼率[12]的不規則部分并行LDPC碼的編碼器和譯碼器，實驗結果表明，該編碼器可以實現數據吞吐率2.51 Gb/s，譯碼器在采用10次迭代的情況下，信息吞吐量達到44 Mb/s。

1 不規則QC碼快速編碼

文獻[1]指出，規則QC碼的校驗矩陣是奇異的，如果將校驗矩陣分成兩個子矩陣即[H=[Ha Hb]，]則無法得到奇異的子矩陣[Ha或Hb，]參考802.16e中的LDPC碼的設計，可以獲得快速編碼的不規則QC編碼的LDPC校驗矩陣的子矩陣。

結構化LDPC碼的奇偶校驗矩陣[H]是[M×N]維的矩陣，由[mb×nb]的標準循環移位矩陣構成，其中[M=mb×z，][N=nb×z，][H]矩陣的形式如式（1）：

[H=[HaHb]=I1Ia…Iak-1Ix1I0…0IbIab…Iak-1b0II…0Ib2Iab2…Iak-1b2Ix20II…?????????Ibk-1Iabk-1…Iak-1bk-1Ix300…I] （1）

快速編碼算法，令信息比特[S=[s1s2s3…sk]，]結構化LDPC碼根據結果可以分為信息序列和校驗序列，由信息序列[S]可以得到校驗序列[Vm×1，]其中[si，][i≤k]是一個[Z]維的列向量，編碼后的輸出[C=[SV]；]根據校驗方程，[HaSΤ+HbVΤ=0]。[Ix1+Ix2+Ix3?VT1=i=1kj=1kHi，jSTj，]設中間變量[T（i）=i=1kHi，j?STj，]根據[Vi]計算[Vi+1，][Vi+1=Vi+T（i），i

2 LDPC譯碼算法選擇

LDPC碼譯碼算法分為基于置信傳播的BP算法以及在此基礎上衍生出的LLR BP算法，另一類譯碼算法基于比特翻轉（BF）算法，由于比特翻轉過程損失了信道軟信息，譯碼性能較差，BP算法涉及大量非線性運算，復雜度較高。本文采用一種改進的基于BP原理的歸一化最小和積算法實現LDPC的譯碼，即Normalized MSA。算法描述如下：

（1） 初始化。將變量節點傳向校驗節點的信息初始化概率為：

[L0Qij=2yiσ2] （2）

式中：[yi]為接收到的信號；[σ2]為噪聲方差。

（2） 校驗節點更新。在第[i]次迭代時，更新與校驗節點[j]相鄰的變量節點[i∈Rj]傳給校驗節點的信息。

[LlRji=i∈Rjisgn（Ll-1（Qij））?minQijα] （3）

式中：[Rji]為除了變量節點[i]外所有與校驗節點[j]相鄰的變量節點的集合。

（3） 變量節點更新。在第[i]次迭代時，更新與變量節點[i]相鄰的校驗節點傳給變量節點的信息：

[Ll（Qij）=L0Qij+j∈CijLlRji] （4）

式中：[Cij]為除了校驗節點[j]外所有與變量節點[i]相鄰的校驗節點的集合。

（4） 譯碼判決。

[Ll（Qij）=L0Qij+j∈CijLlRji] （5）

則：

[Ci=0，if LlQij>01，else] （6）

（5） 結束。增加迭代次數，把譯碼結果代入[HΤ?C=0]進行校驗，如果等式成立或已經超過最大迭代次數，輸出譯碼結果，否則返回步驟（2）。

3 LDPC碼編碼器實現

針對上文提出的編譯碼算法，選擇[H]矩陣中對應的系數[a=2，][b=5，][z=127，][x1=x2=x3=0，]得到快速編碼的不規則QC碼，采用文獻[2]提出的四環檢測定理，首先從圖1觀察[O=HΤH]矩陣，除主對角線元素以外的其他元素都不大于1，所以校驗矩陣不存在四環。

結構化矩陣采用[m]路準并行編碼結構，硬件編碼器按照快速編碼算法計算序列的[V=Vim×1，]信息序列分成[k]組，每組[z=127 ]b，輸入到編碼信息存儲器EM中，根據[Ha]移位矩陣將信息循環移位中間變量存儲在EM中，首先對每組移位塊完全異或，[m]組中間序列再經過異或陣列得到校驗序列[V1，]采用流水線同時進行，編碼器通過循環移位寄存器完成，如圖2所示。流水線設計極大地提高了編碼器的信息吞吐率。

對于不同編碼長度和編碼速率，通過改變[z]值和移位規則，利用以上LDPC編碼器架構就可以得到不同碼長，碼率以及不同并行度的LDPC碼的編碼，而且可以通過打孔自適應地實現不同碼率，因此，以上結構LDPC碼具有很好的靈活性。

4 譯碼器結構設計

本文設計的LDPC譯碼器總體結構如圖3所示。

變量節點處理模塊完成變量節點信息更新和譯碼輸出判決，接收的數據一方面來自初始信道似然信息，另一方面是校驗節點傳遞給變量節點的迭代信息，本文變量節點采用10組并行處理，每組127 b，這樣在127個時鐘周期完成所有變量的軟信息更新，每個變量節點的更新輸出是所有與之相連的校驗節點傳遞過來的迭代信息和初始信道似然信息的和，再減去其自身的內信息，去所有信息之后最高位作為判決輸出。

檢驗節點處理模塊主要是更新校驗節點到變量節點的信息，也是在127個時鐘周期內完成所有校驗節點一輪更新，更新后的輸出作為下次變量節點更新的外信息。

從譯碼算法中可以看出，存儲器地址時刻在變換，由于數字電路的動態功耗正比于芯片信號變換頻率，因此本譯碼器存儲器地址采用格雷碼編碼，這樣信號每個周期只會翻轉一位，大大降低了系統的動態功耗。

5 仿真與實現

本文通過大量的仿真，在信噪比低的環境下，置信傳播譯碼算法譯碼性能優于位比特翻轉算法。在對信息吞吐率，譯碼性能綜合要求高的場合，采用BP算法具有明顯的優勢，同時對比定點化BP方案和浮點BP算法，定點化BP算法以最小的性能損失換取芯片復雜度的大幅度降低，然后分析仿真定點化不同位格式，確定采用最小和積置信傳播算法作為LDPC的譯碼方案，縮放最小和算法的定點化格式為（8[∶]3），即量化位寬為8 b，其中最高的1 b表示符號，2 b表示整數位，5 b表示小數位，并得到[α=1.25，]圖4給出了在AWGN 信道下，采用BPSK調制，碼長1 270，固定10次迭代，[12]碼率條件下，置信傳播算法、最小和算法定點、縮放最小和算法定點及其不同定點格式，以及位翻轉算法的誤碼率性能曲線。由仿真結果可知，縮放最小和算法定點的性能已經非常接近置信傳播算法浮點的性能。

圖4 不同譯碼算法的誤碼率性能曲線

基于上述編碼器和譯碼器的結構，通過硬件描述語言實現了碼長1 270，碼率[12]的不規則結構化LDPC編碼譯碼電路。通過ISE 14.7進行綜合，布局布線，在Xilinx公司的Virtex?5 XC5VtX150T?ff1156FPGA芯片上實現，編碼器最大時鐘頻率為332 MHz，編碼器信息吞吐率達到2.52 Gb/s，譯碼器的時鐘最大頻率為78 MHz，譯碼器在10次迭代后的信息吞吐率達到44 Mb/s，這對于碼長為1 270 b的LDPC譯碼器是很快的。

編碼器采用127 b準并行結構，輸入比特根據校驗矩陣均等切割，每組劃分127 b，切割5組，編碼器中組合邏輯完全由移位和異或構成，BLOCK RAM用于對輸入、輸出緩存進行時序調節，在跨時鐘域場合用來解決讀/寫時序的邏輯膠合，本文不僅從系統層面用戶角度采用輸入、輸出FIFO解決時序問題，用戶甚至可以直接改變編碼器移位矩陣設置不同的碼長、碼率，具有很強的可擴展性。編碼器綜合報表如表1所示。

譯碼器同樣采用輸入、輸出FIFO與外部用戶進行交互，數據流同樣以1 270 b為一幀，譯碼開始前首先按編碼順序將序列進行均等切割，每127 b為一組，譯碼開始時，信道根據輸入比特初始化，初始化完成后譯碼狀態機進入校驗節點和變量節點軟信息更新狀態，直到變量節點判別后得出的譯碼序列滿足校驗方程或者迭代次數超過最大值，輸出譯碼序列，完成本幀數據的譯碼，譯碼結果存入緩沖器，等待用戶讀取。譯碼器資源消耗如表2所示。

6 結 語

本文根據IEEE 802.16e中LDPC碼的設計規則，提出了一種無短環、高速、部分并行、準循環，不規則LDPC編碼器和譯碼器結構，碼長1 270 b，碼率[12，]該LDPC編碼器采用移位和異或操作完成編碼，同時采用流水線結構提高時鐘頻率，可以通過打孔和參數設置進行擴展，采用對數域縮放最小和定點算法對LDPC碼進行譯碼，采用8 b量化，1 b符號位，2 b整數位，5 b小數位，縮放系數[α=1.25，]中間信息節點存儲器地址采用格雷碼編碼，降低動態功耗，通過硬件描述語言設計相應的編碼、譯碼電路，用ISE 14.7進行綜合，布局布線，在Xilinx公司的Virtex?5 XC5VtX150T?ff1156FPGA芯片上實現，編碼器最大時鐘頻率為332 MHz，編碼器信息吞吐率達到2.52 Gb/s，譯碼器的時鐘最大頻率為78 MHz，譯碼器在10次迭代后的信息吞吐率達到44 Mb/s，這對于碼長1 270 b的LDPC譯碼器來說是很快的，針對信息吞吐率，譯碼性能要求高，可擴展性強，從與外部通信使用便利的角度出發，該編譯碼結構體現出明顯的優勢。

參考文獻

[1] ZHANG L， HUANG Q， LIN S， et al. Quasi?cyclic LDPC codes： An algebraic construction， rank analysis， and codes on Latin squares [J]. IEEE Transactions on Communications， 2010， 58（11）： 3126?3139.

[2] 肖揚，徐丹.準循環LDPC好碼設計[J].系統工程與電子技術，2009，31（5）：1011?1016.

[3] GALLAGER R G. Low?density parity?check codes [M]. Cambridge： MIT Press， 1963.

[4] 徐娟，姚如貴，李路，等.優化稀疏LU分解LDPC編碼算法研究[J].西安電子科技大學學報，2015（2）：127?132.

[5] MA Kexiang， LIU Yi， HU Jianhua， et al. Low complexity decoding algorithm for LDPC codes and design of key circuits [J]. Journal of Xidian University， 2013， 40（6）： 6?12.

[6] FALSAFAIN H， ESMAEILI M. A new construction of structured binary regular LDPC codes based on steiner systems with parameter [J]. IEEE Transactions on Communications， 2012， 60（1）： 74?80.

[7] COSTELLO D J， FORNEY G D. Channel coding： the road to channel capacity [J]. Proceedings of the IEEE， 2007， 95（6）： 1150?1177.

[8] IEEE LAN/MAN Standards Committee. IEEE Standard 802.11n. Wireless LAN medium access control （MAC） and physical layer （PHY） specifications： Amendment 4： Enhancements for higher throughputs improvement [S]. New York： IEEE LAN/MAN Standards Committee， 2007.

[9] 袁瑞佳，白寶明，童勝.10 Gbps LDPC編碼器的FPGA設計[J].電子與信息學報，2011，33（12）：2492?2497.

[10] 張洋，王秀敏，陳豪威.基于FPGA的低密度奇偶校驗碼編碼器設計[J].浙江大學學報：工學版，2011，45（9）：1582?1586.

[11] CCSDS. CCSDS 131.1.1?0?2. Low density parity check codes for use in near?earth and deep space application [S]. Washington， DC： CCSDS， 2007.

[12] XIAO Y， KIM K. Good encodable irregular quasi?cycle LDPC codes [C]// 2008 11th IEEE Singapore International Conference on Communication Systems. Guangzhou： IEEE， 2008： 1291?1296.