QCLDPC碼編碼器的FPGA實(shí)現(xiàn)

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

2、，吞吐量約為228Mbit/s。關(guān)鍵字： QC-LDPC FPGA CCSDS 中圖分類號(hào): TN911 文獻(xiàn)標(biāo)識(shí)碼: 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低密度奇偶校驗(yàn)(Low Density Parity Check, LDPC)1碼是 Gallager在1962年提出的一種前向糾錯(cuò)編碼(FEC)，具有近香農(nóng)極限的誤碼性能、無(wú)錯(cuò)誤平層和譯碼速度快

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

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

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

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

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

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

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

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

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

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標(biāo)準(zhǔn)中QC-LDPC碼的編碼過程，提出一種基于生成矩陣的編碼算法，該算法充分利用了準(zhǔn)循環(huán)矩陣的特性，降低了編碼復(fù)雜度和資源消耗。在Xilinx xc4vsx55 FPGA上完成了編碼器的硬件設(shè)計(jì)。仿真結(jié)果表明，編碼器在占用資源較少的情況下，準(zhǔn)確地完成了編碼，編碼器吞吐速率達(dá)到228Mbit/s，滿足近地軌道通信中高吞吐量的要求。 參考文獻(xiàn)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 葉榮潤(rùn)，俞帆，王曉平基于CCSDS規(guī)范LDPC碼的FPGA實(shí)現(xiàn)J無(wú)線電工程，2011，41 (9):34-36YE Rong-run, YU Fan, WANG Xiao-ping. Implementation of CCSDS-LDPC Codes J. Radio Engine