FFT的实现[文献综述].doc

1、 1 本科毕业设计 (论文 )文献综述 电子信息 工程 FFT 的实现 摘要： 本文对 FFT 原理进行了介绍并且对算法的进行了分析，还对软件、软硬件、硬件的实现分别进行介绍，并说明了其优缺点。 关键词： FFT 算法，软件，软硬件，硬件实现。 1.引言 FFT 算法是 1965 年库利（ T.W.Cooley）和图基（ J.W.Tuky）在计算数学杂志发表了机器计算傅里叶级数的一种算法后，经过人们的改进， FFT 算法变的多种多样，按数据组合方式不同一般可以分为按时间抽取和按频率抽取，按数据抽取方式的不同又可以分为基 2，基 4 等 【 1】 。 FFT 的实现方法也多种多样，可以用软件或硬

2、件实现，也可以用软硬件结合的方式实现 【 2】 。 2.FFT 算法与 DFT算法的比较 DFT 是数字信号分析与处理中的一种重要变换，但直接计算 DFT 的计算量与变换区间长度 N 的平方成正比，当 N 较大时，计算量太大，所以直接用 DFT 算法进行谱分析和信号的实时处理是不切实际的。 设有一个有限长序列 )(nx ，其 N 点的 DFT 为 10 )()(NnknNWnxkX k=1,2,.,N-1 (1) 直接按（ 1）式计算 X（ k)的一个值需要 N 次复数乘法和（ N-1）次复数加法运算。当 N远大于 1 时， N 点的 DFT 乘法和加法运算均为 N2,如当 N=1024 时，

3、其总共要计算次数为 复数乘法 +复数加法 =N2+N(N-1)=2096128 次 这对于实时信号处理来说，将对处理设备的计算速度提出了难以实现的要求 【 3】 。 自从快速傅里叶变化算法（ FFT）提出后，为数字信号处理 技术应用于各种信号的实时处理创造了条件，这种算法使 DFT得运算效率提高了 1至 2个数量级。例如 N=1024，用 DIT-FFT2 算法实现变化。 复数乘法次数 = lbNN2 复数加法次数 = lbNN 则一共计算的次数为 lbNNlbNN 2 ，比直接 DFT 的运算次数大大减少，并且 N 越大时，优越性就越明显。 /离散傅立叶变换的快速算法即 FFT，可以将一个信

4、号变换到频域。有些信号在时域上是很难看出什么特征的，但是如果变换到频域之后，就很容易看出特征了。这就是很多信号分析采用 FFT 变换的原因 【 1】 。 3.基 2FFT算法原理 基 2FFT算法分为两种：时域抽取法 FFT（简称 DIT-FFT）；频域抽取法 FFT（简称 DIF-FFT）。 （ 1） 时域抽取法基 2FFT（ DIT-FFT） )2()(1 rxrx r=0,1,2,.,N/2-1 (1) )12()(2 rxrx r=0,1,2,.,N/2-1 (2) 则 x(n)的 DFT 为 12/0)12(12/02 )12()2()( NrrkNNrkrN WrxWrxkX 12

5、/02212/021 )()( NrkrNkNNrkrN WrxWWrx 由于旋转因子 kNW 具有明显的周期性， kr 2/kr2/2kr222 NNjNjkrN WeeW 故 12/0 2/22/12/0 1 )()(NrkrNkNkrNNr WrxWWrxkX ）（)()( 21 kXWkX kN k=1,2,.,N-1 (3) 其中 X1(k)和 X2(k)为 x1(r)和 x2（ r）的 N/2 点的 DFT: 2/112/0 2/11 )()()( NNrkrN rxD F TWrxkX 3 2/212/0 2/2 )()(2)( NNrkrN rxD F TWrxkX 这样，就将

6、 N 点的 DFT 分解为两个 N/2 点的 DFT。计算一个 N/2 点的 DTF 需要（ N/2） 2次复数乘法和 N/2(N/2-1)次复数加法。可见经一次分解，就是运算减少将近一半。以此类推当 N 分解成 N/2 个 2 点的 DFT时，总得计算次数为 复数乘法次数 +复数加法次数 = lbNNlbNN 2 （ 2） 频域抽取法 FFT（ DIF-FFT） 如图 1（ DIT-FFT），图 2（ DIF-FFT）所示 图 1 DIT-FFT 图 2 DIF-FFT 可以看出 DIF-FFT 于 DIT-FFT 算法类似，每级共有 N/2 个蝶形运算，所以两种算法的运算次数也相同。不同的

7、是 DIF-FFT 算法输入序列为自然顺序，而输出为倒序。另外蝶形运算也稍有不同， DIT-FFT 蝶形先乘后加，而 DIF-FFT 蝶形先加后成 【 5】 。 除此外还有其他算法如插值快速傅立叶变换算法、 实时谐波分析算法 【 6】 等等。 4.FFT的实现 4 （ 1） FFT 的软件实现： FFT 可以通过软件实现，如在 PC 机上完成，而不再需要专门的硬件。软件的实现 FFT算法，在精度上难以满足较高的要求，在速度上也很难满足 实时性比较高的场合。但对于提高系统的可靠性和缩短开发周期都是十分有利的，而且成本较低。如在 Lab VIEW 虚拟平台的重采样技术的实现 【 7】 。 （ 2）

8、 FFT 算法软硬件协同设计 FFT 算法软硬件协同实现，其各种性能和成本间于软件实现和硬件实时之间。适合用于一般工业要求的系统，还可以制成便携式 FFT 处理系统 【 7】 。这种方式的实现不仅可以满足要求较高场合，开发周期也相对较短。 如基于 Nios 的 FFT 算法软硬件协同设计： 1.建立 Nios嵌入式处理器系统 利用 Quartus 建立项目工程 ， 再用 SOPCBuider 创 建 Nios 组件模型，生成硬件描述文件，锁定引脚后进行综合与适配，生成 Nios 硬件系统下载文件；然后建立 Nios 嵌入式系统，从 SOPC Builder 组件栏中加入所需的组件 ，完成 Ni

9、os硬件系统的设计。 2.利用 DSP Builder 生成复数乘法模块 在系统设计中，利用 DSP Builder 或者 VHDL 设计并生成复数乘法器、整数乘法器、浮点乘法器等硬件模块。在 Quartus环境中对上述文件做一些修正后，在 SOPC Builder 窗口中将它们定制为相应的指令，并可设定或修改执行该指令的时钟周期。 根据 复数运算，设 2 个复数为 a+bj 和 c+dj，则乘法表述为： jcbdadbcadjcbja )*()*()(*)( （ 4） 用 DSP Builder中 SOPCLibrary中 Custom Ins-truction中的 Dataal、 Data

10、bl和 Resultl 模块实现复数乘法模型 （如图 3）所示： 图 3 复数乘法模型 5 3.在 Nios 中加入复数乘法指令 在 SOPC 中加入加入该设计作为指令执行模块。最后再将整个项目重新编译一次，锁定引脚后，再下载到目标器 件中。 软硬件实现也有其缺点，如软硬件要相互对应，在硬件实现后，软件要协调进行验证，如果在此时发现了错误，就不得不重新来过，这样既费时又费成本。在设计成可携带式 FFT采样处理系统时，其能耗制约了其硬件、软件的设计和选择。 （ 3） FFT硬件实现 硬件实现 FFT 的优势就在在于其极好的实时性和很高的精度。如基于 Virtex II 系列FPGA 设计的处理器

11、实现高速 FFT 运算。 FPGA(现场可编程门阵列 )是一种具有大规模可编程门阵列的器件，不仅具有 ASIC(专用集成电路 )快速的特点，更具有很好的系统实现的灵活性。因此， FPGA 为高速 FFT 算法的实现提供了一个很好的平台。 在 FPGA 设计中，为提高系统的运行速度，而将指令分为几个子操作，每个子操作由不同的单元完成，这样，每一级的电路结构得到简化，从而减少输入到输出间的电路延时，在较小的时钟周期内就能够完成这一级的电路功能。在下一个时钟周期到来时，将前一级的结果锁存为该级电路的输入，这样逐级锁存，由最后一级完成最终结果的输出。 基于 FPGA 的 FFT 算法硬件实现 的 系

12、统框图 如（图 4）所示： 图 4 系统框图 其中，地址产生单元生成 RAM 读写地址，使能信号以及相关模块的启动、控制信号，是系统的控制核心； 4 点蝶形运算单元的最后一级输出不是顺序的；旋转因子产生单元生成复乘运算中的旋转因子的角度数据；旋转因子 ROM 中预置了每一级运算中所需的旋转因子。 6 通过地址产生与时序控制，旋转因子产生 可以完成 FFT 蝶形运算。 Virtex II 系列 FPGA 设计的处理器有以下 3 个特点： (1) 利用内部块 RAM 存取速度快的性能特点采用“双蝶形”结构并行处理，使处理速度提高一倍； (2) 采用了块浮点算法不仅可以解决精度问题，且硬 件实现的结

13、构和控制都很简单； (3)利用 FPGA 具有的可以进行模块化的设计、易于扩展的特点，此处理器还能在对数据实现FFT 运算前对数据进行去直流分量、加窗处理， FFT 运算后进行求模平方运算，这几种处理在数字信号处理中常常是必要的，因此在一个芯片内实现是有意义的。硬件实现也有其不足如：依靠硬件作滤波抽取的方法存在以下几个缺点： (1)硬件设备的价格较为昂贵： (2)使用不灵活，针对不同的故障诊断情况，变化分析频率需要重新采集数据，实时性不强； (3)体积、重量较大，不易携 带。 5.总结 FFT 的实现方法多种多样，可以用软件实现，但计算速度很慢，一般用于离线处理，还可以用软、硬件结合的方式实现

14、，如用单片机或 DSP 实现，在速度不高的情况可以实现在线实时处理，但是在高速的场合仍然不能满足要求，故在实时性很高的情况下，则要求硬件实现。 参考文献 【 1】程佩青 .数字信号处理教程【 M】，北京：清华大学出版社， 2001. 【 2】王世一 .数字信号处理（修订版）【 M】 .京理工大学出版社 .2005.123-162. 【 3】李猛、李红 .快速傅里叶变换 FFT 在数字信号处理器 DSP 上的实现【 J】 .2007.01 【 4】曲丽荣 .短时傅里叶变化在数字信号处理中的应用【 J】 .科技资讯 .2007.27. 【 5】吕京建 . BOL System Inc. 从嵌入式系

15、统的可靠性与可信性看 Y2K 问题 . 【 6】易立强，广继顺 .一种基于 FFT 的实时谐波分析算法【 J】 .电力系统及其自动化学报 .2007.01. 【 7】潘玉宝，张志新，马孝江，基于 LabVl EW 平台的 重采样技术的软件实现平【 J】连理工大学振动工程研究所 【 8】宋琼。朱 e-*，牛宝良基 2快速傅里叶变换引入的不确定度估算叨计量学报 2004，7 25(3)： 281-283 【 9】朱晓勇，丁康离散频谱校正方法的综合比较闭信号处理， 2001， 1“ 1)： 91 97 【 10】 Yin G， Eynde F， SanSen W A high-speed CMOS comparator with8 一 bit resolution lJ IEEEjssc， 1990， 27(12)： 208 211 【 11 】 Ahnoff M Extended-Precision Complex Radlx-2 FFT IFFT Implemented 013 TMS320C62x Literature Number ： SPRA696A Copyright2001 Texas Instruments Application ReportZ 2001