资源预览内容
第1页 / 共24页
第2页 / 共24页
第3页 / 共24页
第4页 / 共24页
第5页 / 共24页
第6页 / 共24页
第7页 / 共24页
第8页 / 共24页
第9页 / 共24页
第10页 / 共24页
亲,该文档总共24页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
本科毕业设计(论文)外文参考文献译文及原文学 院 自动化学院 专 业 电子信息科学与技术 年级班别 2009 级(2)班 学 号 3109001230 学生姓名 钟小洲 指导教师 夏益民 2013 年 6 月目 录基于 FPGA 采用流水线加法器图的高速度低复杂度 FIR 滤波器 .11 绪论 .12 流水线加法器图 .33 使用二进制整数线性规划最小化流水线操作 .44 结果 .6结论 .9致谢 .9参考文献 .9High Speed Low Complexity FPGA-based FIR Filters Using Pipelined Adder Graphs .111 INTRODUCTION.122 PIPELINING OF ADDER GRAPHS.133 OPERATION MINIMIZED PIPELINING USING BINARY INTEGER LINEAR PROGRAMMING.154 RESULTS .17CONCLUSION.20ACKNOWLEDGMENT.21REFERENCES .210基于 FPGA 采用流水线加法器图的高速度低复杂度 FIR 滤波器马丁库姆和彼得齐夫德国卡塞尔大学数码科技集团Email: kumm, zipfuni-kassel.de摘 要本文介绍了基于 FPGA 的高速度、低复杂度的 FIR 滤波器的方法。其实现可分为两部分。首先,一个加法器图是使用现有的多个常数乘法(MCM)算法获得。该加法器图说明所需的乘数模块滤波只使用了加法或者减法和移位运算。其次,执行特定的FPGA-specific 联合调度和流水线优化,使得在使用最小的性能损失时能获得最大的速度。FPGA-specific 的特征体现在优化过程中,包括通过复制稍后阶段的加法器来减少流水线寄存器。优化作为二进制整数线性规划(bilp)问题被制定。它表明在 HCUB MCM 算法中流水线操作所产生的数字比使用割集定时的 as-soon-as-possible(ASAP)调度平均减少了 29.1%。由生成 VHDL 代码所得的综合结果显示,该方法在资源复杂性方面(减少 54.1%的平均水平) ,优于最近提出的加法/ 移位方法,有竞争力的表现是(平均速度是加法/移位方法的 88.2%) 。1 绪论有限单位脉冲响应滤波器(FIR)是数字信号处理(DSP )中的一个关键的应用。它由于严格的线性相位、稳定性以及高通量被用于许多数字信号处理系统。如今,现场可编程门阵列(FPGA)常常被用于滤波器的应用,因为它们提供高达几兆赫兹的实时信号处理时比特定应用集成电路(ASIC)能提供更多的灵活性。目前,许多研究已经完成了硬件实施有效的滤波器。FIR 滤波器在转置形式中的结构如图 1 所示。这种结构是比直接形式有利的,因为延迟元件(z1)可以被用来作1为流水线寄存器结构的加法器(加法器在虚线方框内) 。在专用集成电路设计中,乘法的几个常数通常是简化为加法,减法以及移位。发现最小配置 adders1(转变被认为是免费的)的问题被称为多个常数乘法(MCM)问题1 -6 。优化问题是 NP 完全问题 6 ,并成为近二十年来一个活跃的研究课题。MCM 算法可以被分为公共子表达式消除法(CSE) 1 3和图形的方法 4 6。CSE 方法试图确定共同模式的系数,而图的方法试图以一个自下而上的方式构建系数的值。基于图的方法更为复杂(在运行时) ,但数字的表示是独立的 3,通常能找到比 cse-based 方法 6更好的解决方案。一个领先的 MCM 启发式在质量和运行方面的优化结果是 HCUB 算法 6,这比以前的以图形为基础的方法 BH 4,BHM 和 RAG-n 5更优。HCUB 的实现是开源的 7。在最近的一个版本中,加法器的总深度(AD)可以是有限的,这是从输入到输出的加法阶段的最大数。这就导致了较短的关键路径,而加法器的资源只是略有增加。基于 FPGA的高效数字滤波器的实现必须考虑结构的特征。这些都是特定的算术部件,如全加器和嵌入式乘法器以及查找表(LUTs)和触发器(FF) 。分布式算法一直是最受青睐的实现滤波器的方法,因为查找表和加法器的使用,完全匹配 FPGA 的体系结构。不过meyer-baese 8等人表示,基于 FPGA 的并行分布式算法的实现比一个基于 RAG-n 算法 5的流水线加法器图的实现需要多出平均 71%的资源。类似的结果也取得了添加/ 移位方法的提出者 mirzaei 等人的认同,这里用到了 CSE 方法与 FPGA-specific 成本函数。一个查找表和触发器减少 58.7%和 25%可以实现,分别相对于并行执行,这两种方法的性能几乎是相同的。这就表明 2,该加法器图中,HCUB 比起 CES 方法一方面导致了一个较低的资源使用率(减少 72%查找表和 11%触发器) ,但另一方面,导致业绩不佳(下降 68%) ,例如流水线和 FPGA-specific 的特点的使用在算法中是不考虑的。图 1 转置形式的 FIR 滤波器2在这项工作中,一种新的方法被用来产生流水线乘法器模块且能够使用较少的资源。它是基于加法器图的方法,例如通过 MCM 算法,进一步优化 fpga-specific 调度定时。2 流水线加法器图2.1 利用割集定时的流水线起点是由 MCM 算法得到的一个加法器定时图。一个例子如图 2(a )所示,从而实现一个乘法模块常数系数设置 C= 480,512, 846,1020 。这个例子贯穿于本文算法的验证。本图需要四个加法器,使用 HCUB 算法计算。除了输入结点外的所有节点以圆圈表示,相当于加法器或者减法器。每个节点的值和实现这个节点的因数相等。输出节点是无圈的。所有边的权值是移位的因数。例如,节点 15 实现了将输入 x 移位4 位和减去未移位的输入:15x=24x20x。流水线有向无环图,如加法器图,很容易利用割集定时来进行(CSR) 9。这个实现最复杂的系数的例子有一个 3 级的 AD(423 节点) 。因此,一些流水线的阶段设置为三(没有输入/输出寄存器) 。CSR 后的一个可能的流水线加法器结构如图 2(b)所示。每个节点被画为一个盒子,包括一个寄存器,即是一个纯寄存器(一个输入)或者存储加法器(两个输入) 。假设每次加法计算的时间相同,如图 2(b) ,如果输入和输出已经存储,最大时钟频率的结构可以是原来结构的约三倍以上,共有 11 个额外的寄存器用于流水图,比起没有流水线结构的四个加法器的结构,这将是一个巨大的费用。仔细看看流水线结构,它揭示了通过使用不同的调度,一些寄存器可以被淘汰。例如,系数 255 取决于输入节点 1,这也可在流水线的阶段 2 实现,因此它可以搬到阶段 3,这样可以节省 2 个寄存器。2.2 FPGA 架构的流水线应用于现代 FPGA 的基本逻辑元素至少包括一个查找表(LUT ) ,具有快速进位链的全加器(FA)逻辑和一个可选的输出触发器(FF) 。这些元素是所有现代 FPGA 的共同点,即使 FPGA 硬件厂商将他们组织在不同的单位。以下将包含一个查找表,全加器和触发器的单元称为基本逻辑元素(BLE) 。加法器通常为纹波进位加法器,其每个位在 FPGA 上需要一个 FA 或者一个 BLE 来实现。因此,一位加法器或者减法器需3要 N 个 BLE。此外,实现一个 N 位加法器所需的 BLE 个数等于实现一个 N 位存储加法器的个数。因此,一个加法器的流水线可无额外费用地实现。一个 N 位寄存器需要N 个 BLE。为了简化,利用该模型并假设每个边缘的字长相同,很明显,如图 2(b)中的每个节点需要大约相同的硬件资源。因此,如果系数在最后阶段重新计算,图 2(b)中流水线阶段 2 中
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号