基于FPGA并行分布式算法的FIR滤波器的实现

© 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved.
250
黑 龙 江 科 技 学 院 学 报 第 16 卷
一个高阶滤波器的输出 。在实际应用中 , 当系数 增大时 ,可以采用级联或串并结合的方式来减小 设计规模 。 ALTERA 公司的 FELEX10K系列芯片具有查找 [2] 表结构 ,利用其实现采用全局并行的 F IR 数字滤 波器 , 也即将输入 x ( n ) 经过不同的延迟后同时进 行处理 。下面采用该系列芯片来实现一个长度为 4 [3 ] 的 F IR 滤波器 , 其结构如图 3 所示 (虚线为流水 线寄存器 ) 。
0
+ xB - 2 [ 0 ] 2
B - 1
B - 2
+…+
x0 [ 0 ] 2 ) + c[ 1 ] ( xB - 1 [ 1 ] 2 xB - 2 [ 1 ] 2
B - 2
+
+ … + x0 [ 1 ] 2 ) + … +
B - 1
0
c[N - 1 ] ( xB - 1 [N - 1 ] 2 xB - 2 [N - 1 ] 2

© 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved.
第 4期
赵金宪 ,等 : 基于 FPGA 并行分布式算法的 F IR 滤波器的实现
249
于程序顺序执行 ,其执行速度必然不快 。 FPGA 有 着规整的内部逻辑阵列和丰富的连线资源 , 特别 适合于数字信号处理任务 , 相对于串行运算为主 导的通用 D SP 芯片来说 , 其并行性和可扩展性更 好 。但长期以来 , FPGA 一直被用于系统逻辑或时 序控制上 , 很少有信号处理方面的应用 。其原因 主要是 FPGA 中缺乏 实现 乘法 运算 的有 效结 构 。 现在这个问题得到了解决 ,使 FPGA 在数字信号处 理方面有了长足的发展 。
据的每一对应位产生的部分积预先进行相加 , 形成 相应的部分积 ,然后再对各个部分积累加形成最终 结果 ,而传统算法是所有乘积已经产生之后再相加 完成乘加运算的 。传统算法的实现如图 1 所示 。与 传统串行算法相比 , DA 算法可极大地减少硬件电 路的规模 ,提高电路的执行速度 。其实现如图 2 (虚 线为流水线寄存器 )所示 。
( c[ 0 ] xB - 2 [ 0 ] + c[ 1 ] xB - 2 [ 1 ] + … +
B - 2
( c[ 0 ] x0 [ 0 ] + c[ 1 ] x0 [ 1 ] + … + c[N - 1 ] x0 [N - 1 ] ) 2 。
从以上推导可以发现 , DA 算法是一种以实现 乘加运算为目的的运算方法 。它与传统算法实现乘 加运算的区别在于 , 执行部分积运算的先后顺序不 同 。DA 算法在实现乘加功能时 , 首先将各输入数
[ 1 ] UW E MEYER BAESE. 数字信号处理的 FPGA 实现 [M ]. 北
设滤波器的三个系数分别为 : c[ 0 ] = - 2, c[ 1 ] = 3, c[ 2 ] = 1, 输入为 4 位 (包含符号位 ) , 采用 Verilog
HDL 语言对该 F I R 数字滤波器进行描述 ,并在 EDA

式中 , xb [ n ]表示 x [ n ]的第 b位 , x [ n ]即为 x 的第 n 次采样 。而内积 y 可以表示为
N-1 B-1 b
y =
n Hale Waihona Puke 0∑c[ n ] ・ ∑x
b =0 B - 1
[ k ] ・2 。
b
重新分别求和 , 其结果为
y = c[ 0 ] ( xB - 1 [ 0 ] 2
Abstract: This paper discusses a method to design the F I R filter on FPGA , on the basis of parallel2 distributed arithmetic method, using ROM based LUT . The designing file of F I R digital filter is described w ith Verilog HDL and passes the experim ental si m ulation and tim ing analysis in MAX + PlusII . The result of sim ulation p roves that this method is feasible, efficient, and is capable of overcom ing the disadvantage of soft w are and hardware techniques available for i m p lem entation which suffers from the failure to meet the dem and for a real2tim e and flexible requirement for signal p rocessing in the same ti m e. The method not only fulfils the real2ti m e requirement, but also show s greater flexibility . The paper studies some p rac2 tical p roblem s as to how to op tim ize the utilization per cent of the hardware and im p rove to the computed speed. Key words: F I R digital filter; DA ( distribute arithmetic ) ; FPGA; Verilog HDL
第 16 卷 第 4期
2006 年 7 月
黑 龙 江 科 技 学 院 学 报 Journal of Heilongjiang Institute of Science & Technology
Vol . 16 No. 4 July 2006
文章编号 : 1671- 0118 ( 2006 ) 04- 0248- 03
1 分布式运算原理
[1] 分布式算法 ( distributed arithmetic, DA ) 早在 1973 年就已经被 C roisie 提出 ,但由于它特别适合用 FPGA 来实现 , 故直到 FPGA 出现以后 , 才被广泛的 应用在 FPGA 中计算乘积和 。笔者采用分布式算法
设计 F IR 滤波器 ,并对其进行了改进 。 一个线性时不变网络的输出可以表示为
3 结束语
文中介绍了将乘法转化为查表运算的分布式算 法 ,并利用 A ltera 的 FELEX10K系列器件实现了一 个 4 位 F IR 滤波器 。尽管长度为 4 的 F IR 对大多数 实际应用来讲太短了 , 但是它可以很容易地扩展到 更高阶 ,并且具有编缉时间比较短的优点 ,系统运行 速度为 42119 MHz, 寄存器属性为 106138 MHz。这 些指标明显优于串行分布式算法 。 参考文献 :
FI R filte r’ s rea liza tio n on the ba sis of pa ra lled DA a rithm e tic using FPGA
ZHAO J inx ian, WU S an, WAN G N a ifei
(College of Electrical and Information Engineering, Heilongjiang Institute of Science and Technology, Harbin 150027, China)
B - 2
+
0 + … + x0 [N - 1 ] 2 ) =
( c[ 0 ] xB - 1 [ 0 ] + c[ 1 ] xB - 1 [ 1 ] + … + c[N - 1 ] xB - 1 [N - 1 ] ) 2 c[N - 1 ] xB - 2 [N - 1 ] ) 2
0
B - 1
+ +…+
N-1
y = ∫ c, x
=
n =0
∑c[ n ] ・x [ n ]
=
c[ 0 ]x[ 0 ] + c[ 1 ]x [ 1 ] + … + c[N - 1 ]x[N - 1 ]。 进一步假设系数 c [ n ]是已知常数 , x [ n ]是变
量 。无符号 DA 系统假设变量 x [ n ]的表达式为
B-1
x[n ] =
b =0
∑
xb [ n ] × 2 , xb [ n ] ∈ [ 0, 1 ],
b
2 基于并行 DA 算法的 F IR 滤波器的 FPGA 设计
当系统对速度的要求不高时 , 可以采用图 2 所 示的串行移位的设计方法 。在这种算法中 , 总是计 算具体位 b在一个步骤中通过所有系数的乘积和 。 这种计算只需要一个小表和一个附带移位器的累加 器即可 。这种结构的 F IR 滤波器占用的面积很小 , 处理的速度也较低 。为了使处理速度达到最优 , 往 往采用并行式结构 。这种 DA 结构的改进以增加额 外的 LUT、 寄存器和加法器为代价来提高速度 。 一个 N 阶乘积和计算的基本 DA 结构接收 N 个字中每个字内的一位 。如果每个字中有两个位得 以接收 , 则计算速度就可以从根本上翻倍 。在这种 完全流水线式字并行结构中 , 必须为向量 xb [ n ]的 每一位提供一个单独的 ROM (具有相同的内容 ) 。 如果将输入位宽加倍 , 就需两倍的 LUT、 寄存器和加 法器 , 这样 , 最大速度的代价是非常昂贵的 。如果系 数 N 的数量限制在 4 个或 8 个 , 这一改进就有了吸 引人的性能 。 由于 F IR 滤波器都是线性 滤波 器 , 这就 意味 着低阶滤波器输出的集合可以相加 , 并由此定义