一種基于奇偶并行譯碼架構的高吞吐量譯碼器設計

云飛龍，朱宏鵬，呂晶，杜　鋒

(中國人民解放軍理工大學，江蘇 南京 210001)

?

一種基于奇偶并行譯碼架構的高吞吐量譯碼器設計

云飛龍，朱宏鵬，呂晶，杜鋒

(中國人民解放軍理工大學，江蘇 南京 210001)

針對具有準循環結構的LDPC碼，設計了一種高吞吐量譯碼器。該譯碼器利用并行分層迭代譯碼算法，通過校驗矩陣同一列循環因子對應的變量節點之間的數據傳遞更新，實現迭代譯碼，不僅有效降低了譯碼時間，同時也省去了變量節點處理單元，另外為了進一步提高吞吐量，針對同一列循環因子都為奇數或偶數的基礎矩陣，提出了一種奇偶并行譯碼架構，該架構一次可同時并行處理2個奇偶變量節點的值，有效節省了一半的譯碼時間，可將吞吐量提高一倍左右。最后基于Xilinx公司Virtex6系列的xc6vsx475t芯片實現了上述譯碼器設計，碼字采用(3200,1600)LDPC碼，經ISE軟件環境下布局布線后，結果表明，當迭代次數為15時，譯碼器吞吐量可達300 Mbps，該研究成果具有重要的實用價值。

并行分層;高吞吐量;QC-LDPC;奇偶并行譯碼

0　引　言

LDPC碼(Low-Density Parity-Check Code)[1]是一類具有稀疏校驗矩陣的線性分組碼，不僅有逼近Shannon極限的良好性能，而且具有譯碼復雜度低、結構靈活、易于在FPGA上實現等特點，另外，其譯碼算法在理論上可實現全并行架構，具有高速譯碼的潛能，因此成為近年來編碼界的研究熱點。

在高速譯碼領域，由于全并行架構[2]資源消耗巨大，在實際設計中，往往采用部分并行架構[3]。Zhang K[4]等人提出了一種并行分層譯碼算法(PLDA)，該算法不僅省去了變量節點處理單元(VNU)，減少資源消耗，而且可減少譯碼時間，能有效地提高譯碼吞吐量。本文基于PLDA算法，對文獻[4]中的架構進行改進，提出了一種奇偶并行譯碼架構，該架構可同時處理奇偶2個變量節點，能將譯碼時間縮短一半，可進一步提高譯碼吞吐量，同時本文也給出了實現該架構矩陣需滿足的條件，最后在FPGA上實現，驗證了其架構的可行性，表明其吞吐量可達300Mb/s。

1　準循環LDPC碼及其譯碼算法

1.1準循環LDPC碼

準循環LDPC碼[5]是結構化LDPC碼的重要分類，由于其校驗矩陣有規律可循,因此編譯碼比一般的LDPC碼相對簡便。

給定兩個常數c和t，且c≤t，準循環LDPC碼的奇偶校驗矩陣由c×t的大小均為z×z的循環矩陣陣列組成，校驗矩陣一般形式為：

(1)

式中，Pc,t是z×z的循環移位矩陣或者0矩陣。當Pc,t重量為1或0時，稱為I型準循環LDPC碼，否則稱為II型準循環LDPC碼。本文所指的矩陣是I型準循環LDPC碼。

針對I型準循環LDPC，定義mb×nb的基礎矩陣H′，c=mb×z，t=nb×z,矩陣形式如下式所示，其中，smb,nb為-1～(z-1)之間的整數，稱為循環移位因子。

(2)

校驗矩陣H可由mb×nb的基礎矩陣H′擴展得到。基礎矩陣中對應的元素值為-1時，將其擴展為z×z的全0矩陣，若為其它值s，則將其擴展為z×z的單位陣循環右移s次。

1.2譯碼算法

算法采用修正的最小和譯碼算法[6]，它是由BP算法[7-8]演化而來，由于其易于硬件實現，因此被廣泛采用，算法如下：

(2)校驗節點更新：更新校驗節點Cm向變量節點Vn，n∈B(m)傳輸的信息，B(m)表示與校驗節點Cm相連接的變量節點集合；

(3)

(4)

(5)

(6)

(5)通過校驗矩陣H和序列Wk的模2相乘可以得到第k次迭代的校驗子序列Sk，如果有Sk=θ(θ為全0序列)，則終止迭代，最后的輸出序列W=Wk；

Sk=WkHTmod2

(7)

若校驗式(7)不能完全滿足，同時迭代次數k達到最大迭代次數限制，則終止迭代，譯碼失敗，否則繼續迭代處理，k=k+1，跳轉到第2步。

2　奇偶并行譯碼架構設計

2.1并行分層迭代算法

假設一個QC-LDPC碼校驗矩陣HQC-LDPC，同一列有2,5,8三個移位循環因子，則并行分層迭代算法(PLDA)如圖1所示。

圖1　PLDA算法示意

圖1中，帶框的8,2,5表示循環因子對應的循環子矩陣，CNU表示一個校驗節點處理單元。8對應的循環子矩陣數據經CNU模塊處理完后，傳遞更新給5對應的循環子矩陣，5對應的循環子矩陣數據處理完后，傳遞更新給2對應的循環子矩陣，2對應的循環子矩陣數據處理完后，又傳遞更新給8對應的循環子矩陣。而在時序上，3個循環子矩陣是并列處理的。

上述可概括為：每一行變量節點處理完后傳遞更新給循環因子較小的行，而循環因子最小的一行傳遞更新給最大的一行，即8→5→2→8。該算法不僅省去了變量節點處理模塊(VNU)，且減少了一半譯碼時間，同時由于采用分層譯碼算法原理，在相同迭代次數條件下，與上文的最小和譯碼算法相比，能達到更低的誤碼率，換句話說，可減少迭代次數。

需注意的是，為了實現該算法，校驗矩陣同一列循環因子每2個的差值必須大于每行處理的時鐘周期數，不然無法完成一次完整的迭代。文獻[4]通過對循環因子添加一個偏移量有效的解決了該問題。

2.2奇偶并行譯碼架構

假設上述矩陣HQC-LDPC每一個循環因子對應一個10×10階單位循環矩陣，則PLDA算法具體表示如圖2所示。

圖2　PLDA算法具體示意

圖2中，循環因子8對應的10個變量節點處理完后，傳遞更新給循環因子5對應的10個變量節點，循環因子5對應的10個變量節點處理完后，傳遞更新給循環因子2對應的10個變量節點，循環因子2對應的10個變量節點處理完后，又傳遞更新給循環因子8對應的10個變量節點，重復上述步驟，直到迭代終止，實現一次完整的譯碼算法。

在文獻[4]的PLDA算法中，一次讀取一個數據，針對上述矩陣HQC-LDPC，一次迭代則需要10個時鐘周期，為了提高吞吐量，我們對此進行改進，將上述結構拆分成奇偶兩半，拆分后的PLDA算法示意圖如圖3所示。

圖3　改進后的PLDA算法示意

圖3中，將原來的一個完整的10×10階單位循環矩陣，拆分成2個奇偶數對應的5×5階矩陣，2組奇偶數對應的矩陣分別各自獨立的采用PLDA算法。就譯碼架構來說，在同一時刻譯碼器可同時并行處理2個變量節點，節省譯碼器一半的時間，有效提高了譯碼吞吐量，然而這種架構的缺點是，在存儲器資源消耗上，原來一個循環因子對應一塊RAM資源，現在一個循環子矩陣拆分成2個獨立的奇偶數矩陣，此時相當于1個循環因子變成了2個循環因子，因此存儲器RAM資源增加了一倍，這種架構是通過犧牲存儲資源來換取高吞吐量。

為了節省RAM存儲資源，同時又能在同一時刻譯碼器同時并行處理2個變量節點，可以將一個循環因子對應的變量節點的值存儲到同一塊RAM中，同一時刻讀取連續的2個奇偶數，這樣就可以實現上述架構的思想原理。以圖2中變量節點8和9為例，我們可將循環因子8對應的變量節點的值全部存儲到一塊RAM中，讀取位寬是2個變量節點的量化位寬，即一個地址讀取2個數據，此時一次可同時讀取變量節點8和9，送入CNU模塊處理，處理完后的數據送給循環因子5對應的變量節點8和9，后面的處理操作亦是如此。然而這種架構存在的問題是，同一列循環因子如果既有奇數，也有偶數，那么就會使得地址訪問不協調。如圖2中，循環因子8是偶數，就存儲器RAM來說，變量節點8和9位于同一地址，而循環因子5是奇數，變量節點8和9分別位于存儲器RAM的2個地址內，同一個時鐘周期無法全部讀取，最終不能有效地完成譯碼。因此這種架構要求在矩陣設計的時候，同一列循環因子必須都為奇數或者偶數，這樣才能保證并行處理的2個奇偶數據位于RAM的同一地址內，而不會造成地址訪問不協調問題，同時為了奇偶對稱，循環因子擴展矩陣的階數z必須為偶數，如下面的矩陣H，該矩陣是一個16×32基礎校驗矩陣，每一列的循環因子或者為偶數，或者為奇數，該矩陣可實現上述奇偶并行譯碼架構。

3　譯碼器的FPGA實現

譯碼器系統框圖如圖4所示，主要包括輸入控制模塊、譯碼模塊以及輸出控制模塊。譯碼器采用上述矩陣H，碼字采用(3200,1600)LDPC碼(階數z為100，是偶數)，接收到的譯碼信息采用6 bit量化，同時譯碼器迭代次數設為15次。

圖4　譯碼器系統框

輸入模塊主要是對信道似然比信息(LLR)存儲器進行初始化，初始化為接收到的量化譯碼信息，同時對外信息存儲器也進行初始化操作，初始化數據為0。需注意的是，在輸入控制模塊中，對信道似然比信息存儲器(RAMLLR)的寫入順序操作與循環因子大小有關，假設循環因子是8，則RAMLLR對應的初始化操作如圖5所示，0地址存入的數據是循環因子8對應的變量節點的值，1地址存入的數據是第9個變量節點的值，2地址存入的數據是第10個變量節點的值……后面地址按順序依次存入對應的數據，因此不同的循環因子對應不同的輸入控制模塊，總共有107個循環因子，則對應107塊RAMLLR及其相應的輸入控制模塊，而外信息存儲器(RAM外信息)的初始化與循環因子無關，因此只需一個輸入控制模塊即可對應107塊RAM外信息。其中，對RAMLLR和RAM外信息的初始化操作在a端口完成。

圖5　RAMLLR初始化示意

輸出模塊主要將最后一次譯碼迭代數據的符號位送入寄存器，每一列循環因子對應一個位寬為100的寄存器，總共需要16個這樣的寄存器，即對應校驗矩陣的前16列信息位，最后通過并串轉換模塊將1600個信息位按比特依次輸出。

圖4中，中間虛線框的譯碼模塊是譯碼器的核心部分。在譯碼過程中，對RAMLLR進行讀取時，每次讀取一個地址，2個數據，位寬為12，讀取的數據送入2個并列的CNU模塊，對RAM外信息讀取操作與對RAMLLR的操作一樣，讀取的數據也送入2個并列的CNU模塊。每一行的LLR值通過2個CNU模塊處理完后，經數據交換網絡，傳遞更新給其對應的另一行，而外信息處理完后，原路返回，更新上一次迭代的值。數據交換網絡由并行分層譯碼算法的傳遞規則決定：每一行變量節點處理完后傳遞更新給循環因子較小的行，而循環因子最小的一行傳遞更新給最大的一行。其中，在譯碼時對RAMLLR和RAM外信息的讀取和更新操作都在b端口完成。由于對RAMLLR的譯碼讀取寫入操作，循環因子對其的影響在初始化的時候已經消除，而RAM外信息完全不受循環因子的影響，因此可采用同一個模塊對所有的RAMLLR和RAM外信息進行讀取寫入操作，有效降低了資源消耗。

整個譯碼器的譯碼過程概括如下：

(1)初始化：將接收到的3 200位編碼信息進行6比特量化，并送入對應的RAMLLR，對其初始化，同時對RAM外信息也進行初始化，初始化數據為0，每塊RAMLLR和RAM外信息的a端口深度為100，位寬為6。

(2)譯碼：初始化完成后，分別讀取RAMLLR和RAM外信息對應的數據，進行譯碼迭代，一次讀取2組數據，分別送入2個并列的CNU模塊，CNU模塊處理完后返回2組新的數據，新的外信息值直接原路返回，更新本行上一次迭代的值，而LLR值則通過數據交換網絡傳遞更新給其對應的其他行，對RAMLLR和RAM外信息的譯碼讀取寫入操作在b端口完成，其深度為50，位寬為12。

(3)譯碼輸出：當迭代次數達到15后，停止譯碼，將譯碼數據輸出，基礎校驗矩陣的前16列，每一列對應一個位寬為100的寄存器，用于存放譯碼數據的符號位，寄存器再通過并串轉換，將譯碼數據按比特輸出。同時，由于譯碼數據位于16個寄存器中，因此可對RAMLLR里面的數據進行修改，此時可對下一幀數據進行初始化操作，而不用等上一幀數據完全譯碼輸出，能有效減少譯碼等待時間。

4　仿真結果及其資源消耗

4.1性能仿真

針對本文上述矩陣H，圖6給出了采用BPSK調制后的誤碼率性能。

圖6　誤碼率性能仿真比較

從圖6中可看出，相同迭代次數條件下，5 bit量化性能最差，而6 bit與7 bit性能比較接近，因此綜合考慮性能和資源消耗，選擇6 bit量化。

同時從圖6中也看出，相同量化位寬條件下，15次迭代與20迭代性能相比，相差不大，但是15次迭代比20次迭代吞吐量更高，因此綜合考慮后，選擇迭代次數為15。

4.2資源消耗情況

在Xilinx公司的FPGA上實現了譯碼器設計，FPGA采用Virtex6系列xc6vsx475t芯片。資源消耗情況見表1。

表1　譯碼器資源利用

在ISE環境下布局布線后，結果表明最高時鐘頻率可達169.112 MHz，迭代15次后，吞吐量可達300 Mb/s。

吞吐量計算公式如下：

(8)

在式(8)中，ninformation是LDPC編碼幀包含的信息位，fmax是譯碼器能達到的最高時鐘頻率，nClk是譯碼器迭代一次消耗的主時鐘周期數，nIter是譯碼器迭代的次數。

5　結　語

本文針對具有準循環結構的LDPC碼，設計了一種奇偶并行譯碼架構，該架構利用并行分層迭代譯碼算法，有效地省去了變量節點處理單元，降低了硬件資源消耗，同時該架構并行處理奇偶2個變量節點，能省去一半的譯碼時間，可進一步提高吞吐量，最后通過性能仿真、分析以及硬件實現，表明在6 bit量化以及15次迭代的情況下，譯碼器性能優越，同時我們在FPGA硬件上進行了實現，結果表明其吞吐量可達300 Mb/s，該研究成果具有重要實用價值，可應用于高速數字通信領域。

[1]Gallager R G. Low-Density Parity-Check Codes[J]. Information Theory, IRE Transactions on,1962,8(1):21-28.

[2]Sivakumar S. VLSIImplementation of Encoder and Decoder for Low Density Parity Check Codes[D].Houston :Texas A&M University, 2001.

[3]Hocevar D E. A Reduced Complexity Decoder Architecture via Layered Decoding of LDPC Codes[C]//IEEE Workshop on Signal Processing Systems. USA, 2004,107-112.

[4]ZHANG K, HUANG X and WANG Z. High-Throughput Layered Decoder Implementation for Quasi-Cyclic LDPC Codes[J].Selected Areas in Communications, IEEE Journal on, 2009, 27(6):985-994.

[5]Fossorier M P C. Quasi-Cyclic Low-Density Parity-Check Codes from Circulant Permutation Matrices[J]. Information Theory, IEEE Transactions on. 2004, 50(8):1788-1793.

[6]姜明.低密度奇偶校驗碼譯碼算法及其應用研究[D]. 南京: 東南大學, 2006.

JIANG Ming. Decoding Algorithm and Applied Research of Low-Density Parity-Check Code[D] .Nanjing: Southeast University, 2006. (in China)

[7]CHEN J, Dholakia A, Eleftheriou E, et al .Reduced-Complexity Decoding of LDPC Codes[J]. Communications, IEEE Transactions on,2005,53(8):1288-1299.

[8]陳燕，蔡燦輝.LDPC碼的譯碼算法研究[J].通信技術，2008，41(12):87-91.

CHEN Yan and CAI Can-hui. Research on the LDPC Decoding Algorithm [J].Communications Technology,2008,41(12):87-91.

云飛龍(1990—)，男，碩士，主要研究方向為信道編碼；

朱宏鵬(1982—)，男，博士，主要研究方向為信道編碼；

呂晶(1965—)，男，教授，主要研究方向為衛星通信；

杜鋒(1990—)，男，碩士，主要研究方向為衛星通信。

A High-Throughput Decoder based on Architecture of Decoding Odd and Even in Parallel

YUN Fei-long，ZHU Hong-peng，LV Jing， DU Feng

(PLA University of Science and Technology,Nanjing Jiangsu 210001,China)

In connection with QC-LDPC, a high-throughput decoder is designed, which could, with parallel layered decoding algorithm, could enable the variable nodes of the same column circulating factors to correspondingly transmit and update data with each other and realize iterative decoding, thus reducing the decoding time and saving the variable-node disposing unit and the resource. In addition, a new architecture of decoding odd and even in parallel to increase the throughput is proposed and applied to the basic matrix where all of the same columns circulating factors are odd or even. This architecture could decode two variable nodes in parallel, thus to save half time and double the throughput. Finally, the decoder design is implemented on basis of Xilinx Virtex6 xc6vsx475t, and (3200, 1600) LDPC. After the ISE software layout and wiring, the experiment result indicates that the throughput could reach 300Mbps at 15 iterations. This achievement is of important practical value.

parallel layered; high-throughput; QC-LDPC; decoding odd and even in parallel

10.3969/j.issn.1002-0802.2016.03.003

2015-10-11；

2016-01-19Received date:2015-10-11；Revised date：2015-01-19

國家自然科學基金(No.91338201)

TN911.22

A

1002-0802(2016)03-0264-06

Foundation：National Natual Science Foundation of China(No.91338201)