采用C语言FPGA技术实现LDPC码译码算法
28卷 第1期2011年1月
微电子学与计算机
MICROELECTRONICS &COM PU TER
V ol.28 N o.1Januar y 2011
收稿日期:2009-11-09;收稿日期:2010-01-15
基金项目:国家自然科学基金项目(60970058);江苏省现代企业信息化应用支撑软件工程技术研发中心开放基金项目
(SX 200906)
采用C 语言FPGA 技术实现LDPC 码译码算法
张 培1,2,陶志福2,周昌雄2,汪一鸣3
(1江苏省现代企业信息化应用支撑软件工程技术研发中心,江苏苏州215104;
2苏州职业大学,江苏苏州215104;3苏州大学,江苏苏州215021)
摘 要:针对L DP C 码(L ow Densit y Pa rity Check Co des)译码算法的特点和最新一代I mpulse C 语言的并行编程技术,提出一种对L DP C 码译码器进行F PGA (Field P ro gr ammable Gate A rr ay)设计与实现的便捷新方案,以获得译码速率和硬件资源消耗的平衡.在XC2V 2000芯片上实现了一种码率1/2,码长2500的(3,6)LD PC 码译码器.实验表明当最大迭代次数为10次,主频50M H z 时,译码速率可达10M bps.关键词:低密度奇偶校验码;译码算法;Im pulse C 语言;并行;现场可编程门阵列
中图分类号:T N911.22 文献标识码:A 文章编号:1000-7180(2011)01-0173-03
The Implement of LDPC Decoding Algorithm
Based on FPGA Programming in C
ZHANG Pei 1,2,TA O Zhi fu 2,ZHOU Chang x iong 2,WANG Yi ming 3
(1Jiangsu Pro vince Suppor t Softw are Eng ineering R&D Center fo r
M o der n I nfo rmatio n T echnolog y A pplicatio n in Enterpr ise,Suzhou 215104,China;
2Suzhou Vo cational U niversit y,Suzho u 215104,China;3Suzhou U niver sity,Suzhou 215021,China)Abstract:In or der to obtain the balance o f the decoding rat e and the hardw are co nsumpt ion,a new method to imple ment L DPC deco ding alg or ithm is pro posed.F or the char acteristics of the decoding algo rithm,this metho d is based on an up-to-date par allel t echnique fr om Impulse C prog ramm ing t o har dw are implementation.A decoder fo r a family of (3,6)LDP C Co des w ith a co de r ate of 0.5and a block size o f 2500bits is implemented o n X ilinx V ir tex2XC2V 2000.By perfor ming max imum 10decoding iterat ions,the decoder can achiev e a max imum bit thro ug hput o f 10M bps.
Key words:L DP C;deco ding alg or ithm;Impulse C;parallel;F PGA
1 引言
FPGA 提供了大量的高度并行的可配置硬件资源,同时高性能FPGA 加速软件的应用在通信技术、科学计算等领域的需求正在迅速增长.LDPC 码是目前最逼近香农限的一类纠错码,其译码复杂度低,且可实行并行操作,非常适合于FPGA 的并行计算.
Im pulse C 是一种类似C 语言的描述硬件需求
的语言,并且能够很好地与VH DL(硬件描述语言)相融合.设计者只需要用该语言描述要实现的硬件行为,在设计平台的支持下,就可以在FPGA 上实现所要求的硬件.Impulse C 编程模型[1]实际上是一种面向流的、对软硬件划分和软硬件过程协同的设计方法.通过将Impulse C 语言编译导入现有设计流程,设计者能够迅速创建和评估不同的软硬件划分策略,迅速建立工作产品原型.因此,这种设计方法既简化了硬件设计过程,又为软件设计人员提
微电子学与计算机
2011年
供了一种可行的硬件设计途径.
文中采用这种适用于高度并行FPGA 平台的新的、基于Im pulse C 语言的程序模型和技术,给出了一种对LDPC 码译码器进行FPGA 设计与实现的便捷新方案.
2 LDPC 译码器的Impulse C 设计
信道编码的译码算法是决定编码性能和应用前景的一个重要因素.尤其是在长码的条件下,译码算法的复杂度决定了编码的前途.LDPC 码的译码复杂度与码长成线性关系,克服了长码长时所面临的巨大译码计算复杂度问题,使得长编码分组的应用成为可能.虽然为了适应不同的情况,先后出现了多种改进的LDPC 码译码算法,但算法的关键仍然是变量节点和校验节点之间的信息传递[2]
.为了在译码性能和复杂度之间达到更好的平衡,同时基于硬件实现方面的考虑,本设计选择采用最小和算法MSA(M in Sum Alg orithm )
[3]
,该算法的基本流程
如图1所示.从而避免了进行复杂的计算和查表,复杂度得到了明显降低,而且译码性能也较好,适合硬件实现
.
图1 译码算法流程图
Im pulse C 开发平台包括函数库、编译器和调试工具.Impulse C 库包括了设置和管理多个独立过程的功能,它可以通过数据流、信号和可选的共享存储资源相连接
[4]
.使用Impulse C 库功能,Im
pulse C 语言可用来描述高度并行的应用,具有最小的软件编程复杂度,同时具有用标准C 开发环境下编译和调试的能力.这些库函数用来在进程之间进行流和信号的数据通信,还可以将进程分配到目标编程平台的实际硬件资源上.本次设计中多个进程之间的相互通信和同步主要通过数据流方式完成.例如读取待译码数据的一段程序如下:
for (i =0;i {#pr agma CO PIP EL IN E if (co _str eam _r ead (InDataF ,&nSample,sizeo f (flo at ))==co _er r_no ne); IF _SIM (samplesr ead++); L c[i]=nSample}由于流水线技术允许循环的多重迭代并行执行,这里使用了CO PIPELINE 流水线指令.假设N 取1,若不使用流水线,处理100个数据需要200个时钟周期.现在使用流水线后,将产生一个二级流水线.当第一个数据被读进来以后,第一级立刻开始读取第二个数据,与此同时,第二级使用刚读进来的数据进行计算.这样只需要101个周期就能处理100个输入数据了.可见,以数据流的形式来读取数据和输出数据,应用程序可以一边从外部接收数据,一边处理数据,效率更高,也能大大简化硬件软件系统的设计和调试.如果一个应用程序具有设计良好的流接口,那么当它被映射到实际硬件和软件时,就能高效运行. 构造规则(3,6)LDPC 码,取125 250的校验矩阵,将经过A GWN(高斯白噪声)信道后的数据作为译码前数据,每次读取一组250比特数据进行译码,共读取十次.在Co Developer 开发平台环境下进行桌面仿真,桌面仿真结果如图2所示.结果包含一个生产者测试进程,一个代表LDPC 码译码算法的Impulse C 进程,和一个消费者测试进程.生产者测试进程读取数据,然后送给译码算法的Impulse C 进程,最后消费者测试进程接收Impulse C 译码后的数据流. 3 LDPC 译码器的FPGA 实现 虽然Gallag er 曾经提出了LDPC 码解码方法 和示意性的硬件电路原理图,但是由于当时科技水 平有限,硬件条件受到限制,LDPC 码并没有得到重视和推广,FPGA 的出现为此提供了一个很好的解决方案.本设计中,将Impulse C 编写的进程编译成FPGA 硬件时主要采取的步骤如图3所示.在C 分析阶段,编译器首先确定应用中的硬件和软件进程.在循环展开阶段,编译器将相应的循环转化为等价的并行语句,最后生成可仿真H DL 文件. 从软件到硬件编译器的过程是实现快速开发的关键,它保证了应用程序直接编译到FPGA.本设计所生成的H DL 文件的底层模块描述了原来用co_process_config 声明的硬件进程,顶层实体引用了包含LDPC 译码器实际功能的底层实体,这些功能是 174 第1期张培,等:采用C 语言F PG A 技术实现L DPC 码译码算法 图2 桌面仿真结果 图3 Impulse C 到F PGA 硬件的优化步骤 用寄存器传输级(RT L)代码表示的.实际上,硬件生成器把每一个进程当作一个独立的状态机来实现.在LDPC 译码算法的状态机中,共有195个状态,分别描述译码算法的初始化和迭代部分,以及用来驱动状态机的时钟逻辑. 由于Xilinx 的Virtex2芯片XC2V2000片内资源丰富,无需外部缓冲就可实现高速数据采集,而且适合进行浮点运算和数据存储操作,所以选用XC2V2000 4 bf957实现本次设计.生成的LDPC 码译码器模块如图4所示.当时钟频率为50M H z,迭代次数为10次,本设计耗费了5493个LUT (查找表),译码速率为10M bps,功耗为 367mW. 图4 LDP C 码译码器模块 衡量译码器性能的两个关键因素分别是译码速度和硬件复杂度,较高的译码速度往往是以更大的资源消耗为代价的.如何做到既能以较快的速度进行译码,又能使硬件开销不会太大,从而找到译码速率和资源消耗之间的平衡是硬件设计过程中必须要考虑的问题.采用传统硬件描述方法,文献[5]采用部分并行结构给出了一个吞吐量为54M bit/s 的LDPC 码译码器FPGA 芯片,是译码速率和资源消耗很好的一种折中,但由于构造方法的限制,现有的大多数LDPC 码并不适合采用部分并行结构.文献 [6]实现了译码速率为1M bps 的LDPC 码译码器,耗费了3039个LU T.文献[7]中的LDPC 译码器速率达到1Gbit/s,却也是以增加极高的芯片复杂度为代价的.与上述相同功能的传统硬件描述方法对比,在本设计中,由于Impulse C 库可以有效地利用Stream s C 编译器提供的 流式编程!方法,芯片内部并行译码结构采用流水线结构,降低了逻辑单元的使用量,硬件规模相对较小;同时,有些系统并不要求很高的译码速率,例如第三代移动通信系统要求达到的最高译码速率为l0M bps,因而本设计得到的译码器速率能够满足实际工程的需要,同时资源消耗也较低. 4 结束语 文中基于通过C 语言在混合软/硬件平台上直接实现FPGA 软件应用的设计理念,创建实现了一个面向数据流的LDPC 译码硬件算法,体现了Im pulse C 语言FPGA 编程技术的优势,为软件工程 师从C 到开发基于FPGA 的嵌入式硬件系统提供了一种快捷的新思路.下一步的研究方向是面向FPGA 性能,增加语句级并行,进一步优化Impulse C 代码,以达到使用高度并行平台实现低成本高性能计算的目的.参考文献: [1]Dav ide P ellerin,Sco tt T hibault.Pr at ical F PG A pr o gr amming in C[M ].Boston:P rentice Hall P T R,2007:19-51. (下转第179页) 175 第1期邢素霞:多光谱图像融合中小波分解层数研究 表4 Q与分解层的关系 Q A组B组C组D组 Db9-10.920.610.710.74 Db9-20.920.610.700.71 Db9-30.920.590.680.70 Db9-40.890.550.680.70 Db9-50.890.550.710.70 4 结束语 文中选用Db9基函数的小波变换方法,对多组多光谱源图像进行了1~5层小波分解的图像融合实验.在融合规则上,均采用细节分量上选两幅图像中的最大值,近似分量上取两幅图像的平均值的融合规则;然后利用图像评价指标信息熵、标准差、互信息和综合指标对图像融合的结果进行了评价.评价结果表明,对多光谱图像和Db9小波基函数,图像融合在一层小波分解下可以获得较好的性能. 参考文献: [1]覃征,鲍复民,李爱国,等.多传感器图像融合及其应用 综述[J],微电子学与计算机,2004,21(2):1-5. [2]Gemma P iella,A da ptive Wavelaets.A pplicatio ns to im age fusio n and compression[D].Bethlehem,Philadel phia,L ehigh U niver sity,2003.[3]Zhang Z,Blum R.A r egio n-based imag e fusion scheme fo r concealed weapon detection[C]//Pr oceed ing s of the31st Annual Conference on Info rmation Sci ences and Systems.Balt imor e,M ary land,1997:168 -173. [4]Z hang Z.Investig ations o f imag e fusion[D].Bethle hem,P hiladelphia,L ehig h U niversit y,1999. [5]傅鹂,王丹,吕海翠.一种基于提升小波变换的图像融合 新算法[J].微电子学与计算机,2009,26(4):64-67. [6]胡俊峰,唐彩银,巩萍.基于小波变换的CT/SP ECT图 像融合最佳层数选取[J].研究论著,2009,24(3):10- 12. [7]李炜,陈晓辉,毛海杰.小波阈值消噪算法中自适应确定 分解层数研究[J].计算机仿真,2009,26(3):311 -314. [8]李树涛,王耀南,龚理专.多聚焦图像融合中最佳小波分 解层数的选取[J].系统工程与电子技术,2002,24(6): 45-49. [9]Zheng Yufeng,Edva rd A Essock,Br uce C H ansen,et al.A new met ric based on ex tended spatial f requency and its applicatio n to DWT based fusion algo rithms[J]. Info rmation Fusion,2007(8):177-192. 作者简介: 邢素霞 女,(1975-),博士,讲师.研究方向为信号处理. (上接第175页) [2]李刚,黑勇,仇玉林.一种准循环L DP C解码器的设计与 实现[J].微电子学与计算机,2008,25(7):52-55. [3]张仲金,高明伦,沙金,等.基于自身可信度的低复杂度 L DPC码位翻转解码算法[J].微电子学与计算机, 2008,25(7):92-94. [4]A nt ola A Santambrog io,F racassi M D,G otti M,et al. A no vel ha rdw ar e/softw are codesign methodolog y based on dynamic reconfig uratio n w it h impulse C and codevel oper[C]//3rd Southern Conference on Pr og rammable L og ic.M ar del Plata,A r gentina,2007:221-224. [5]Zhang T,Par hi K K.A54M BP S(3,6)-reg ular FP GA L DP C decoder[C]//IEEE SI PS.Canada:Br itish Columbia,2002:127-132. [6]L evine B,T ay lor R,Schmit H.Implementation of near Shannon limit err or-co rr ect codes using reconfig urable hardwar e[C]//IEEE Sy mp.O n FCCM.Lo s A lamit os, 2000:217-226. [7]Andrew J Blanksby,Chr is J H ow land.A690-mW1- G b/s1024-b,rate-1/2low-densit y parit y-check co de deco der[J].Jo ur na l of So lid-State Circuits,2002, 37(3):404-412. 作者简介: 张 培 女,(1979-),硕士研究生,讲师,工程师.研究方向为电子与通信技术. 陶志福 男,(1972-),博士,讲师.研究方向为电子与通信技术. 周昌雄 男,(1965-),博士,教授.研究方向为图像处理技术. 汪一鸣 女,(1956-),博士,教授,博士生导师.研究方向为多媒体通信和无线通信. 179