LDPC码译码算法的C语言FPGA编程实现

28卷 第1期2011年1月微电子学与计算机MICROELECTRONICS &COM PU TERV 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-03The Implement of LDPC Decoding AlgorithmBased on FPGA Programming in CZHANG 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 rM 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 PGA1 引言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 库功能,Impulse C 语言可用来描述高度并行的应用,具有最小的软件编程复杂度,同时具有用标准C 开发环境下编译和调试的能力.这些库函数用来在进程之间进行流和信号的数据通信,还可以将进程分配到目标编程平台的实际硬件资源上.本次设计中多个进程之间的相互通信和同步主要通过数据流方式完成.例如读取待译码数据的一段程序如下:for (i =0;i<N;i++){#pr agma CO PIP EL IN Eif (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 ogr 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.74Db9-20.920.610.700.71Db9-30.920.590.680.70Db9-40.890.550.680.70Db9-50.890.550.710.704 结束语文中选用Db9基函数的小波变换方法,对多组多光谱源图像进行了1~5层小波分解的图像融合实验.在融合规则上,均采用细节分量上选两幅图像中的最大值,近似分量上取两幅图像的平均值的融合规则;然后利用图像评价指标信息熵、标准差、互信息和综合指标对图像融合的结果进行了评价.评价结果表明,对多光谱图像和Db9小波基函数,图像融合在一层小波分解下可以获得较好的性能.参考文献:[1]覃征,鲍复民,李爱国,等.多传感器图像融合及其应用综述[J],微电子学与计算机,2004,21(2):1-5.[2]Gemma P iella,A da ptive Wavelaets.A pplicatio ns to image 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 fusionscheme 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].Bethlehem,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,etal.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 basedon 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 FPGA 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 nearShannon 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-checkco de deco der[J].Jo ur na l of So lid-State Circuits,2002, 37(3):404-412.作者简介:张 培 女,(1979-),硕士研究生,讲师,工程师.研究方向为电子与通信技术.陶志福 男,(1972-),博士,讲师.研究方向为电子与通信技术.周昌雄 男,(1965-),博士,教授.研究方向为图像处理技术.汪一鸣 女,(1956-),博士,教授,博士生导师.研究方向为多媒体通信和无线通信.179。

准循环LDPC码的编译码技术研究与FPGA实现低密度奇偶校验码(Low-Density Parity-Check Codes),凭借着逼近Shannon极限的优异纠错性能,得到了信道编码学术界的广泛关注,并应用到了多范围领域中。

低密度奇偶校验码是一种特殊的线性分组码,它的特殊性表现在校验矩阵具有的稀疏性,而这一特点正是它能呈现较好性能的根本原因。

自LDPC码被重新认识以来,怎样构造实用型的好码,发展高效率且实用的LDPC码编译码技术,逐渐成为了学者研究LDPC码理论的一个热点。

QC-LDPC码使硬件实现变得较为容易,因此对准循环LDPC码的研究具有重要的理论价值和现实意义。

论文介绍了LDPC码的基本理论知识和QC-LDPC码的特性,对已有LDPC码的随机构造法和结构化构造方法进行了分析研究。

在实例构造中采用了准循环构造法,对其中参数的选择和限定做了详尽的阐述,并对索引矩阵不同参数组合构造出的检验矩阵的性能做了Matlab仿真,选出了最优的参数组合。

然后介绍三种译码方法包括BP算法,对数域的Log-BP算法和最小和算法,并在这三种方法下对构造出的准循环LDPC码进行了Matlab仿真,做出了对比分析,在FPGA实现中选用了便于硬件实现的最小和算法。

最后在FPGA实现中,设计了适合上述构造的QC-LDPC码的编码方法,设计实现了串行译码器,并对整个系统进行了Model Sim仿真,完成了FPGA实现,对译码结果进行了分析,达到了预期的目标。

LDPC码译码算法研究和FPGA实现的开题报告
标题：LDPC码译码算法研究和FPGA实现
摘要：
LDPC码是一种近年来广泛应用于通信领域的误差纠正编码技术，其具有低复杂度和好的纠错性能等优点，因此在Wi-Fi、蓝牙等无线通信标准中得到广泛采用。

在本课题中，我们将研究LDPC码在信道编码中的应用以及LDPC码的译码算法。

同时，我们还将通过FPGA实现译码算法，优化编码器和译码器的设计，提升算法的实时性和效率。

本文主要研究内容包括：
1. LDPC码的基本原理和编码方式。

2. LDPC码的译码算法，包括1. Min-Sum译码、2. SPA译码和
3. 消息传递译码等算法。

3. FPGA实现LDPC码译码算法的设计，优化编码器和译码器的结构和流程，提升算法的实时性和效率。

4. 对比不同译码算法和FPGA实现的效果，分析其性能和优缺点。

通过本次研究，可以深入掌握LDPC码的基本原理和译码算法，并通过对FPGA实现的优化，提升算法的实时性和效率，在通信领域的应用中发挥重要的作用。

关键词：LDPC码、译码算法、FPGA实现、通信。

基于FPGA的LDPC码编译码研究及硬件实现如今信息化的发展越来越迅速,对信息传输的要求也越来越高,高速的传输效率带来更大的误码概率,因此在保证传输效率的条件下选择一种纠错性能好的编译码技术是移动通信技术发展的关键。

本文选择性能接近香农极限的LDPC(低密度奇偶校验)码作为纠错码实现QPSK(正交相移键控)调制方式下的自发自收通信系统。

LDPC码在中长码的条件下,有着极为优越的译码性能,现已广泛应用于DVB-S2、4G通信系统和卫星通信中,同时成为了5G中长码编码方案。

本文首先概述了LDPC码编码和译码的发展历程和应用现状,然后重点研究了LDPC码的编译码算法。

对于编码算法,根据硬件实现复杂程度,选择了易于实现的QC(准循环)LDPC 编码算法,QC-LDPC编码算法校验矩阵子矩阵具有循环特征,编码时存储量和运算量较低。

对于译码算法,首先介绍了BP(置信传播)算法及其改进的LLR(对数似然比)BP译码算法,这两种算法有着较好的译码性能,但却不利于硬件实现,然后重点研究了最小和译码算法,以及这种算法在性能上的两种改进算法归一化最小和算法和带偏移量的最小和算法。

最后利用Matlab软件对LDPC码译码算法、码长、码率以及迭代次数等参数进行仿真,分析各参数对系统误码率性能的影响,确定选择归一化最小和译码算法实现译码功能。

然后根据确定的参数,在FPGA中实现了LDPC码的编译码器的设计,同时为了实现完整的通信系统,在FPGA中设计实现了QPSK调制解调系统。

接着,使用modusim软件对实现过程进行分模块的仿真验证,证明了算法的正确性。

最后介绍了实验室自研的SDR(软件定义无线电)平台,并且利用该平台对整个通信系统进行测试验证,通过实现LDPC编译码下的QPSK调制解调信号的自发自收功能,计算不同信噪比情况下的误码率,证明了译码性能达到指标要求,验证了系统实现的正确性。