1、QC-LDPC碼編碼器的FPGA實現(xiàn)謝勇 姚遠程 秦明偉(西南科技大學信息工程學院 四川綿陽 621010) 摘要：準循環(huán)低密度奇偶校驗(QC-LDPC)碼具有優(yōu)異的糾錯性能，已被納入空間數(shù)據(jù)系統(tǒng)咨詢委員會(CCSDS)的近地軌道通信標準。分析了QC-LDPC碼的特點，提出一種基于生成矩陣 的編碼方法。該方法利用循環(huán)矩陣特性簡化生成矩陣的存儲模式，減少了資源消耗;同時利用循環(huán)移位寄存器和累加器實現(xiàn)矩陣乘法，降低了編碼算法復雜度。在Xilinx xc4vsx55 FPGA上, 采用VHDL語言實現(xiàn)了CCSDS標準中(8176,7154)LDPC編碼器的設(shè)計。仿真結(jié)果表明，設(shè)計的編碼器資源占用較少

2、，吞吐量約為228Mbit/s。關(guān)鍵字： QC-LDPC FPGA CCSDS 中圖分類號: TN911 文獻標識碼: AFPGA Implementation for Encoder of QC-LDPC Codes Xie Yong, Yao Yuan-cheng, Qin Ming-wei(School of Information Engineering, Southwest University of Science and Technology, Mianyang 621010, Sichuan, China)Abstract: QC-LDPC code possesses exc

3、ellent property of error correction, and has been included in the Near-earth orbit communication standard which is proposed CCSDS. This paper analyses the properties of QC-LDPC and proposes an encoding method based on generator matrix. This encoding method simplifies the storage pattern of generator

4、 matrix through circulant matrix property, thus lessens the resource consumption. Also, it realizes the matrix multiplication by the utilization of cycle shift register and accumulator, and then reduces the complexity of encryption algorithm. Based on Xilinx xc4vsx55 FPGA, use VHDL language, the des

5、ign of (8176, 7154) LDPC encoder in the CCSDS standard is realized. Simulation results show that this encoder occupies less resource, and has a throughput about 228Mbit/s.Key words: QC-LDPC; FPGA; CCSDS低密度奇偶校驗(Low Density Parity Check, LDPC)1碼是 Gallager在1962年提出的一種前向糾錯編碼(FEC)，具有近香農(nóng)極限的誤碼性能、無錯誤平層和譯碼速度快

6、等優(yōu)點，但其校驗矩陣具有隨機性，編碼較為復雜。QC-LDPC碼是一種基于幾何構(gòu)造的LDPC碼2，繼承了LDPC碼的優(yōu)點，同時降低了編譯碼復雜度，可實現(xiàn)性強，已被IEEE802.11n (WLAN)、IEEE802.16e (WiMAX)和CCSDS等多個通信標準采用。為推進LDPC碼的實際應(yīng)用，國內(nèi)外開展了大量LDPC碼編譯碼器的研究工作，主要選擇大規(guī)模集成電路作為其實現(xiàn)方案，文獻3-6給出了幾種有效的LDPC碼編碼算法。本文根據(jù)CCSDS標準中QC-LDPC碼的特點，提出一種適合在FPGA上實現(xiàn)的編碼器結(jié)構(gòu)，在滿足標準數(shù)據(jù)吞吐量的前提下，簡化了編碼過程，降低了硬件資源消耗。1. CCSDS標

7、準中的LDPC碼 在2011年8月最新發(fā)布的CCSDS 131.0-B-2藍皮書標準中7，推薦(8176,7154)LDPC碼作為近地軌道通信的信道編碼方式，其碼長為8176bit，碼率為7/8。(8176,7154)LDPC碼是一種準循環(huán)LDPC碼，因其校驗矩陣具有循環(huán)特性而得名。校驗矩陣H的維數(shù)是1022x8176，由2行16列的511x511的子矩陣Ai,j構(gòu)成。校驗矩陣H的結(jié)構(gòu)如下式(1)所示： (1)式(1)中Ai,j是一個循環(huán)矩陣，它的每一行由其上一行向右循環(huán)移位1位構(gòu)成，第一行是最后一行的循環(huán)移位。Ai,j的行重和列重都是2，因此校驗矩陣H的行重為32，列重為4，即每行有32個1

8、，每列有4個1。 利用線性分組碼的校驗矩陣和生成矩陣的正交性，推導出(8176,7154)LDPC碼的生成矩陣G。生成矩陣G具有系統(tǒng)循環(huán)結(jié)構(gòu)，維數(shù)是7154x8176，其形式如下： (2)式(2)中，矩陣左邊部分是一個7154x7154的單位陣，右邊部分是2行14列的511x511的循環(huán)子矩陣Bi,j。由循環(huán)矩陣的定義可知，通過生成向量bi,j (即Bi,j的第一行元素)的循環(huán)移位可得到矩陣Bi,j，因此存儲生成矩陣簡化為存儲其生成向量，可以節(jié)約大量的存儲資源。2. 編碼器設(shè)計 分析CCSDS標準中(8176,7154)LDPC碼的結(jié)構(gòu)，其生成矩陣具有系統(tǒng)循環(huán)特性，很適合于硬件實現(xiàn)。因此本文提

9、出基于生成矩陣的編碼方式，其編碼算法的推導如下式：(3)其中為輸入信息系列；為式(2)中單位矩陣；為式(2)中的循環(huán)矩陣；為校驗系列；編碼后的碼字由輸入信息系列和校驗系列兩部分組成。由上式(3)可知，(8176,7154)LDPC碼的編碼實際上就是計算校驗系列。 根據(jù)上節(jié)的定義，(8176,7154)LDPC碼的碼字為8176bit，信息系列為7154bit，校驗系列為1022bit。以511bit為單位進行分塊，可將信息系列分為14塊，即，其中第i個信息塊為；校驗系列分為2塊，即，其中第j個校驗塊為。進一步推導可得第一個校驗塊為： (4)式(4)中第i項為： (5)對于,表示循環(huán)右移位?；?/p>

10、上文的理論推導，在設(shè)計編碼器時生成矩陣G的存儲簡化為生成向量bi,j的存儲，這樣原本需要1022x8176個存儲空間，現(xiàn)在只需要511x28個存儲空間。本文利用FPGA內(nèi)部豐富的Block RAM資源存儲生成向量bi,j，方便后續(xù)快速讀取。校驗系列的計算由SRAA (shift-register-adder-accumulator)電路實現(xiàn)，SRAA電路利用移位寄存器和累加電路為核心實現(xiàn)向量與矩陣的乘法，極大地減少了運算量和資源消耗，有利于編碼器的硬件實現(xiàn)。SRAA硬件結(jié)構(gòu)如下圖1所示。圖1 SRAA電路結(jié)構(gòu)Fig 1 SRAA circuit structure圖1中，循環(huán)移位寄存器實現(xiàn)生成

11、向量bi,j的循環(huán)右移，AND門實現(xiàn)式(5)中的乘法，XOR門實現(xiàn)式(5)中的加法，寄存器存儲中間累加運算結(jié)果及最終輸出的校驗系列。SRAA電路的主要工作過程如下：1） 首先硬件電路初始化，寄存器B1清零。從ROM對應(yīng)地址0中讀取循環(huán)矩陣的生成向量并存入循環(huán)移位寄存器A1中，接著信息塊的第1位進入編碼電路，通過與門實現(xiàn)乘法，再由異或門相加后去更新寄存器B1中的值。2） 在下一個時鐘到來時，信息塊m1的第2位m1(2)進入電路與循環(huán)移位寄存器A1循環(huán)右移1位得到的向量相乘，與門陣列輸出為，經(jīng)異或門累加后，寄存器B1中的值變?yōu)椤?） 重復步驟(2)直到信息塊m1的第511位m1(511)進入編碼器

12、，運算完成后寄存器B1中存儲的結(jié)果是m1B1,1。4） 從ROM的地址1中讀取循環(huán)矩陣B2,1的生成向量b2,1存入循環(huán)移位寄存器A1，信息塊m2的511位信息依次進入電路，與b2,1的循環(huán)移位結(jié)果進行運算，運算完成后寄存器B1中值變?yōu)椤?） 重復上面過程，直到信息系列M的最后一位進入電路，運算結(jié)束后寄存器B1中存儲的值是，由上式(5)可知，B1中的結(jié)果就是511位的校驗信息P1。本文中通過兩個SRAA電路級聯(lián)實現(xiàn)校驗塊P1、P2并行計算，提高了編碼速率。編碼器先輸出信息序列，接著輸出校驗系列，最終編碼結(jié)果為碼字。3. FPGA實現(xiàn)與仿真根據(jù)本文提出的編碼器結(jié)構(gòu)，基于FPGA實現(xiàn)(8176,7

13、154)LDPC碼的編碼器。FPGA芯片選用Xilinx 公司的xc4vsx55，在ISE10.1平臺上完成編碼器的VHDL硬件描述、編譯綜合和布局布線。在 ModelsimSE6.5 上進行時序仿真，圖2是SRAA電路的仿真波形，圖3是(8176,7154)LDPC碼的單幀編碼仿真波形。圖2中，mes是輸入的待編碼信息，rom/addr是ROM的讀地址，bij是存儲在ROM中的生成向量，移位寄存器regA每個時鐘對bij循環(huán)右移1位。在一個時鐘周期內(nèi)，當前輸入信息與寄存器regA中當前值相乘后，再與寄存器regB中上一個時鐘的值相加，相加的結(jié)果即是寄存器regB的當前值 。每個生成向量從進入

14、SRAA電路到完成計算需要511個時鐘。圖3中，編碼器依次從ROM中讀取生成向量，送入SRAA電路進行校驗位運算。直到第14個生成向量進入電路完成運算后，結(jié)束一幀信息的編碼，開始輸出校驗信息。P1、P2是511位的校驗塊輸出，最終輸出的校驗信息Parity由P1和P2的連接組成。SRAA電路完成一個生成向量的運算需要511個時鐘，則完成校驗位的計算需要511x14=7154個時鐘。按照系統(tǒng)時鐘為200Mhz、碼長為8176bit計算，編碼器吞吐量約為228Mbit/s，滿足CCSDS標準要求。將編碼器輸出的校驗信息與Matlab計算出的校驗信息作比較，發(fā)現(xiàn)兩者數(shù)據(jù)完全相同，證明本文設(shè)計的編碼器

15、工作正常。綜合后的FPGA資源使用情況如下表1：表1 編碼器資源使用情況Table 1 Resource use condition of encoder資源類型使用數(shù)目使用率Slices269710%Slice flip flops31166%4 input LUTs43618%Block RAMs165%圖2 SRAA電路仿真波形Fig 2 Simulation waveform of SRAA circuit 圖3 單幀8176bit編碼器仿真波形Fig 3 Simulation waveform of single frame 8176bit encoder 4.結(jié)論本文分析了CCSD

16、S標準中QC-LDPC碼的編碼過程，提出一種基于生成矩陣的編碼算法，該算法充分利用了準循環(huán)矩陣的特性，降低了編碼復雜度和資源消耗。在Xilinx xc4vsx55 FPGA上完成了編碼器的硬件設(shè)計。仿真結(jié)果表明，編碼器在占用資源較少的情況下，準確地完成了編碼，編碼器吞吐速率達到228Mbit/s，滿足近地軌道通信中高吞吐量的要求。 參考文獻1 Gallager R G. Low-density parity-check codes J. IRE Trans. Inform. Theory, 1962, 8: 21-28.2 Kou Y, Lin S, Fossorier, et al. Low

17、- density parity-check codes based on finite geometries: a rediscovery and new results J. IEEE Transactions on Information Theory, 2001, 47(7): 2711- 2736.3 Li Zong-wang, Chen Lei, Lin Shu, et al. Efficient encoding of quasi-cyclic low-density parity-check codesJ. IEEE Transactions on Communications

18、, 2006, 54(1): 71-81.4 Wang Zhong-feng and Cui Zhi-qiang. Low-complexity high-speed decoder design for quasi-cyclic LDPC codes J. IEEE Transactions on Very Large Scale Integration System, 2007, 15(1): 104-114.5 葉榮潤，俞帆，王曉平基于CCSDS規(guī)范LDPC碼的FPGA實現(xiàn)J無線電工程，2011，41 (9):34-36YE Rong-run, YU Fan, WANG Xiao-ping. Implementation of CCSDS-LDPC Codes J. Radio Engine