基于fpga分布式算法实现的研究.doc

基于fpga分布式算法实现的研究.doc基于FPGA分布式算法实现的研究
【摘要】目前使用分布式算法是FPGA设计FIR数字滤波器常用的 结构，本文主要对基于FPGA分布式算法的三种常用实现结构进行了深入 的分析与研究，在此基础上，针对三种结构存在的缺陷与不足，提出了优 化改进方案，并分析了改进方案的优势，对设计数字滤波器具有一定参考 意义和实用价值。
【关键词】FPGA分布式算法（DA）查找表数字滤波器
一、引言
分布式算法（distributed arithmetic, DA）是在上个世纪70年代 初被首次提出的，但直到Xilinx公司发明FPGA（现场可编程门阵列，Field Programmable Gate Array）的查找表结构以后，DA算法才广泛应用在计 算乘积和之中。与传统算法相比，分布式算法可以极大地减少硬件电路规 模，很容易实现流水线处理，提高电路的执行速度。这种方法是目前比较 常用的基于FPGA设计FIR滤波器的方法。
分布式算法与传统的乘法器结构相比，因巧妙的利用ROM查找表将固 定系数的乘累加运算转化为查表操作，消除了消耗资源的乘法器，因此， 当数据的位宽比较小时，就实现FIR滤波器的速度而言，DA算法要明显比 乘累加运算快。但对于分布式算法的三种常用实现结构，不论是串行的、 串并结合，还是全并行流水结构来实现基于DA算法的滤波器，当阶N很 大时，需要的硬件资源很多，有时是不可能实现的，所以需要寻找一种改
进的实现结构来降低硬件资源的消耗。
二、分布式算法实现结构分析
DA算法能用多种的结构来实现，最简单、直观的方法如图1所示。
下面，仔细分析一下分布式算法的性能：首先，从图1中可以看出基 于DA算法的滤波器，不需要通用乘法器。其次，基于此种结构，由B为 输入数据的位宽，完成一次滤波需要B次累加，也即需要B个时钟周期来 完成一次运算，所以这种结构的滤波器对处理B较小的系统有比较明显的 优势。最后，因为此种结构的滤波器的查找表的大小有阶数N决定，共需 个LUT单元，又每个单元的位宽由系数的量化位宽决定，设系数量化位宽 是，所以每个单元位宽为（），则共需要（）*2N字节的查找表单元，也即 当N较大时，消耗太多的LUT单元，所以这种结构的不适合N比较大的情 况。下面再分析全并行（即速度最优化）DA算法的实现，其实质是图1的 一种变换形式，即将基于DA算法的LUT复制B份，而每一份的内容相同, 这样就可以同时对B份LUT进行查找，同时得到B个中间结果，再对这B 个结果采用加法器树相加，就构成了如图2结构的滤波器。
这种结构的DA算法完成滤波只需要一个时钟周期，然而，它必须消 耗更多的硬件资源，如设计N阶滤波器，输入变量为B个字节，则共需（） **B字节的RAM资源，当N更大时，消耗更多，且还要增加额外的寄存器 和加法器，所以我们可知，此种结构是以消耗硬件资源来换取高速度，显 然是很不经济的做法。
基于上图还有一种变换形式是介于上述两种实现结构之间，也即串并 结合的实现结构，这种结构是把DA算法的LUT复制C份，且2<=C<B,则
需B/C个时钟周期来算岀部分和，然后，再进行累加。
综上所述，不论是串行的、串并结合的还是全并行流水结构来实现基 于DA算法的滤波器，它们的每个查找树的大小均需（）*字节的RAM,并 且都有各自的缺点，即当