论文部分内容阅读
摘要:快速傅里叶变换(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的数字中频处理。
关键词: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的数字中频处理。