基于FPGA的高速分裂基FFT算法实现

来源 :中国高新技术企业 | 被引量 : 0次 | 上传用户:zzhcom
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  摘要:快速傅里叶变换(FFT)是离散傅里叶变换(DFT)的快速算法,而分裂基FFT算法是所有FFT算法中一种效率较高的一种算法,有着广泛的应用。在高速的系统要求下,文章选择分裂基FFT算法作为实现高速FFT处理器的基本算法。文中设计采用了并行处理、流水线技术等有效的实现方法,在Virtex-5 FPGA平台上有着很好的效果,并且满足了高速的系统要求。结果显示,系统延时只有13个周期,并且在资源利用上面有很高的效率。
  关键词:FFT;分裂基算法;FPGA;Virtex-5;并行处理;流水线
  中图分类号:TN791文献标识码:A文章编号:1009-2374(2010)01-0011-03
  
  离散傅里叶变换(DFT)和卷积运算是两种基本和常用的信号处理方法。实际上,很多其他的算法比如滤波、频谱分析等,都能够通过DFT来实现。但是由于DFT算法过于复杂,Cooley 和Tukey在1965年最先提出了快速傅里叶变换 (FFT)算法来代替DFT。作为一个快速版本的DFT,FFT以及它的反变换IFFT,是数字信号频谱分析领域中的重要分析方法。现场可编程门阵列(FPGA)比普通的数字信号处理器(DSP)在实现FFT算法时有着很大的速度优势以及更高的效率。因此在实时信号处理领域,用FPGA做FFT运算比用DSP处理器有着更多的好处。文章介绍了一种基于Xilinx FPGA 的高速定点分裂基FFT算法的实现,此设计有较小的均方误差,并且当N等于16点时,系统时钟可以达到200Mhz,而数据延时只有13个周期。第一节介绍了FFT算法的选择,分裂基FFT算法的原理以及数据流图。第二节介绍了FFT处理器的FPGA设计。第三节介绍了设计的仿真、综合以及实现结果。最后第四节给出了此设计的结论。
  
  一、FFT算法选择及原理
  
  (一)选择算法
  自从Cooley和Tukey提出DIT-FFT(按时间抽取FFT)算法后,已经有很多种新的FFT算法被人们研究出来,包括DIF-FFT(按频率抽取FFT)算法等。总的来说,这些算法可以分为两类:第一类是FFT点数N 等于2m(m为任意自然数);另外一类是N 不等于2m。由于当N不等于2m时,我们可以在后面加上若干个0,使N等于2m,从而转化为第一种情况。所以我们常用的FFT都是属于第一类的。在第一类FFT算法中,包括基-2FFT、基-4FFT(N=4m)和基-8FFT(N=8m)等。从理论上讲,用较大的基数可以进一步减少运算次数,但程序(或硬件)都将变得复杂,因此大于8的基数没有多大实际意义。因此,实用中多采用基本形式的基-2或基-4FFT算法。
  1984年,P.Douhamel 和H.Hollmann将基-2和基-4分解柔和在一起,提出了一种分裂基FFT算法。其运算量比前几种算法都有所减少,运算流图却与基-2FFT很接近,程序也很容易实现,因此分裂基FFT是一种实用、高效的算法。文章将以分裂基FFT算法为研究对象,完成基于FPGA的高速FFT引擎的实现。
  (二)分裂基FFT算法原理
  分裂基算法的基本思路就是队偶序号序列实用基2算法,队基序号序列实用基4算法,这样就可将基2分解同基4分解组合在一起。算法的推导如下:
  在k0=0,1,2,3时用k表示k1,n表示n0,可得出:
  0≤k≤N/4-1
   将偶数序号项X(4k)和X(4k+2)合并可得出偶数号输出项为:
  0≤k≤N/4-1
  由此可见,一个N点的DFT可以分解为一个N/2点的DFT和两个N/4点的DFT,称其为L形蝶形运算,其第一次L形蝶形流图1所示。一个L形蝶形运算中只有两次乘旋转因子的运算,其余权威加减法运算。N/2点的DFTN/4点的DFT又可以继续进行L形蝶形运算,因此循此进行,最好可以分解为4点或2点DFT进行运算。
  下面以N=16时,说明完整的分裂基FFT运算流图。
  经过分析计算,得到16点分裂基FFT数据流图如图2所示:
  
  二、分裂基FFT算法的FPGA设计与实现
  
  (一)总体实现结构设计
  分裂基FFT算法以L形蝶形运算为核心,其中既包括基-2算法又包括基-4算法。所以分裂基FFT算法并不是对称的。由图2可以看到,16点复数FFT中X(0)和X(8)只需经过4级复数加法运算就可以得到,但是X(1)和X(9)要经过4级复数加减法运算,一级复数乘法运算。因此,文章设计了一种并行流水线分裂基FFT算法处理器。其总体结构图如图3所示:
  输入数据为32bits复数,包括16bits的实部和16bits的虚部。读入数据缓存后,开始进行L形蝶形运算,第一级L形蝶形运算得到的一个8点的FFT和两个4点FFT。4点FFT可以直接进行蝶形运算得到FFT结果。8点FFT数据再送入第二级L形蝶形运算单元,得到一个4点FFT和两个2点FFT,然后直接進行蝶形运算,得到FFT结果。最后再将FFT后的数据重新排列,就完成了整个FFT运算。
  (二)复数乘法器设计
  对于复数乘法单元的设计,常见的复数乘法方式为:
  (a+bj)(c+dj)=ac-bd+j(ad+bc),其中j为虚数单位。
  用这种方式,需要4次乘法运算,2次加减法运算。由于在FPGA设计中乘法单元的引入,特别是高位数的乘法器单元的引入将会消耗大量的资源,并影响运行的速度。所以我们采取了一下的复数乘法器的设计:
  (a+bj)(c+dj)=a(c+d)-(a+b)d+j[a(c+d)+(b-a)c]
  这种方式中,用到了3次乘法运算,5次加减法运算就完成了复数乘法运算,减少了乘法器的数量,增加了资源的利用率。
  (三)旋转因子查找表设计
  通过分析数据流图(图2),我们可以发现,某些蝶形运算可以简化为没有乘法器的运算,因为蝶形运算旋转因子W160=1,W21=-1,W41=j,W43=-j。有这些旋转因子的蝶形运算环节都可以通过加减法运算,和改变符号,调换实部虚部来实现。因此我们只需要存储以下5个蝶形运算旋转因子,W161,W162,W163,W166,W169。这样就节约了大量的存储空间,同时也节约了大量的乘法器单元。
  (四)错误分析
  浮点运算将会消耗很多FPGA的逻辑资源,相反的,尽管有限字长效应适当的存在,适当的数据转换可以防止数据的溢出,高效率的错误控制能够抑制圆周效应。在文章中采用了定点数运算。在定点数运算中,数据的错误由以下几个方面组成:
  1.乘法截取错误,两个16bits的数相乘,得到的结果是32bits,如果截取成31bits,那么一定会出现错误。如果数据小于1,那么结果就一定不会溢出。
  2.加减法溢出错误,两个16bits的数相加,得到的结果将会是一个17bits的数,这样我们必须丢弃1bit再进行下一级操作。事实上,只要将数据向低位移以为,就能够避免出现溢出。
  
  三、数据仿真与实现分析
  
  设计中采用了自顶向下的设计思路,各模块采用Verilog HDL硬件描述语言在ISE10.1软件环境下在Virtex-5平台上进行设计,用modelsim6.4仿真软件在系统时钟为200MHz的情况下进行仿真,系统综合在Synplify9.6.2中进行。结果显示消耗了2%的Slice单元,1% 的BlockRAM资源,最快时钟达到212.337Mhz。仿真图形如图4所示。仿真结果与MATLAB软件仿真的结果进行对比得出两者只有极其微小的差别,满足设计的要求。这说明系统若要扩展成1024点或2048点的FFT,只需要增加蝶形运算的层级就能够实现。
  仿真图形显示,由于采用了有效的措施来抑制错误和溢出,即便是输入最大的数,也没有出现溢出的情况。系统延时为13个时钟周期。
  
  四、结论
  
  经过验证,所采用的高速、并行、流水线、定点、分裂基FFT算法设计,能达到设计要求,并且控制实现简单可行。所有的模块均经过功能仿真,时序分析,得以实现。可以看出,随着FPGA性能的提高,利用其实现高速信号处理具有很大的可行性和实用性。
  
  参考文献
  [1]程佩青.数字信号处理教程[M].北京:清华大学出版社,2003.
  [2]Duhamel P.Algorithms meeting the lower bounds on the multiplicative complexity of length 2DFTs and their connection with practical algorithms[J].IEEE Trans.on ASSP,1990,38(9).
  [3]王世一.数字信号处理[M].北京:北京理工大学出版社,1997.
  [4]樊光辉,许茹,王德清.基于FPGA的高速流水线FFT算法实现[J].电子工程师,2008,34(3).
  [5]Zhao Tao,FU Feng-lin,WANG Xiao-hui,Design and implementation of FFT module based on the Stratix FPGA,International Electronic Elements,2006,(5).
  [6]Rong Yu,Zhu En,Design of high-performance FFT butterfly unit,JOURNAL OF SOUTHEAST UNIVERSITY(Natural Science Edition),2007,137(4).
  
  作者简介:刘星(1984-),男,河南郑州人,电子科技大学自动化工程学院硕士研究生,研究方向:基于FPGA的数字中频处理。
其他文献
研究了网络节点容量资源限制下的复杂网络传输问题。通过构建带有节点容量限制的复杂网络传输流量模型,分析三种节点容量分配方式:平均分配节点容量,根据节点度分配节点容量,
1前言糖尿病肾病(diabetic nephropathy,DN)是糖尿病(diabetes mellitus,DM)常见的微血管并发症,也是糖尿病致死、致残的主要原因之一。糖尿病肾病的主要临床表现为蛋白尿、水肿、高
目的 探析无创正压通气治疗慢性阻塞性肺疾病(chronic obstructive pulmonary disease,COPD)急性加重期呼吸衰竭的临床疗效.方法 选取2017年3月~2017年12月我院收治的COPD急
目的比较为力苏、吗丁啉及莫沙必利治疗胃肠动力障碍性疾病的有效性及安全性。方法选择各种原因引起的胃肠道动力障碍患者28例口服为力苏,32例口服多潘立酮,22例口服莫沙比利,比
利用自制的锐钛矿相TiO2纳米粉体为反应底物,在浓碱条件下,采用水热方法制备了长度100~200 nm,直径约10 nm的TiO2纳米管。通过研究碱种类及浓度、水热反应温度、反应时间及清洗方
本文对23例60~79岁的患肝、肾囊肿的老年病人采用B超或X线监视下经皮穿刺注射无水酒精的硬化疗法。其中肝囊肿16例(男5,女11),平均年龄69岁,肾囊肿7例(男6,女1),平均64.5岁。
目的探讨正常压力性脑积水的发病机理、手术指征及手术时机。方法23例正常压力性脑积水采用侧脑室-腹腔分流术治疗。结果随访6个月,术前症状消失或明显改善14例,好转5例,效果不
高压架空输电线路基本上都暴露在野外,容易受天气、地形等自然条件的影响。其中雷击造成的跳闸事故在全部跳闸故障中占比超过30%。寻求更有效的输电线路防雷措施,是致力于电
为了提高路径寻优算法的效率和实时性,本文实现了一种名为DPO-AC的基于蚁群思想的动态路径寻优算法(the ant colony algorithm with dynamic path optimization),在改进蚁群算
摘要:文章通过天花板水电站碾压混凝土双曲拱坝工程实践,对碾压混凝土生产、入仓方式、仓面规划、碾压、层间结合、变态混凝土施工、夏季温度控制等方面进行技术总结,为今后碾压混凝土施工积累宝贵经验。  关键词:天花板水电站;双曲拱坝;碾压混凝土;施工技术  中图分类号:TV544 文献标识码:A 文章编号:1009-2374(2011)31-0094-03  一、工程概