文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > 一维离散Fourier变换快速算法概述
侵权投诉

一维离散Fourier变换快速算法概述

一维离散Fourier变换快速算法概述

138

内蒙古科技与经济          2003年第10期 

一维离散Fourier变换快速算法概述

侯志萍

(北京科技大学应用科学学院数力系,北京 100083)

  摘 要:在数字信号处理中,离散Fourier变换是一种很重要的数学工具,它的应用十分广泛。本文介绍了几种一维离散Fourier变换的快速算法,并对它们的计算复杂度进行了分析。

关键词:离散傅立叶变换、快速Fourier变换算法、DFT、FFT

  中图分类号:G642  文献标识码:A  文章编号:6921(20030138—031 引言

2

r),DFT的运算量从o(N)log2N),开创了离散Fourier变换的一个新

离散Fourier变换(DFT)具,性系统的分析、、机械振动等方面的分析研究中都得到了广泛的应用。随着数字电子计算技术的发展,在这些应用领域内借助于数字计算机来进行DFT运算,可以实现某种数据的事后处理或系统的仿真研究。特别是在六十年代中期出现了离散Fourier变换的快速算法(FFT)以后,这种数学工具的应用领域就从事后处理扩展到实时处理,直至扩展到成为某些无线电电子系统、电子测量分析系统中的一个组成部分,并在其中起着极为重要的作用。FFT的算法有很多,也已经发展的比较完善。本文主要介绍一维FFT的几种主要算法,并对其中几个常用算法的运算量进行了分析,从而得出一些结论,可以在实际应用当中作为一种有用的参考或指导。

N-1

一维N点DFT的定义为:X(k)=

nk

WN,(k=0,1,…,N-1)

N-1

n=0

∑x(n)

-nkN

其逆变换(IDFT)为:x(n)=(n=0,1,…,N-1)

N

k=0

∑X(k)W

,

其中WN=e-j=

j2Π N

称为复数域上的N阶单位根,

-1为虚数单位。

由DFT和IDFT定义知,若直接按离散傅立叶

变换的定义来计算N点DFT,需要N2次复数乘法和N(N-1)次复数加法运算,当N较大时,运算量是很大的。

2 快速Fourier变换算法211 Cooldy-Tukey算法

1965年,Cooley和Tukey提出了DFT的一种快速算法—快速傅立叶变换FFT(FastFourier

时代。它的基本思想是利用WN的周期性和对称性,使长序列的DFT分解为更小点数的DFT,利用这些小的DFT的计算来代替大的DFT的计算,从而达到提高效率的目的。

如果用Mi和Ai表示Ni点DFT所需的复乘和复加次数,则有:

M=N2M1+N1M2+N; A=N2A1+N1A2,当N1点和N2点DFT直接计算时,则有:

M=N(N1+N2+1); A=N(N1+N2-2)

其中:M,A表示计算N点DFT所需的总的复数乘法和复数加法次数。

可以看出,Cooley-Tukey算法的运算量明显

2

小于直接计算N1×N2点的二维DFT所需的N21N2次乘法和N1N2(N1N2-1)次加法的运算量。212 基-2FFT算法

21211 时间抽取法(DIT)。这种算法是将N=2t(t>1)点的输入序列x(n)按照其下标分成偶数和奇数前后两个N 2点序列,从而使计算一个N点

2点DFT。依此下去,共进DFT分解为计算两个N

行t(t=log2N)次分解,直到最终分解成2点DFT运算的组合时为止。由于它在实际应用中,输出下标与时间变量有关,而DIT是将输入时间序列分为偶数和奇数下标的序列,输出向量分为前后两个N 2点序列,因而称为时间抽取法。

这种递归算法的复运算量为:

M=log2N; A=Nlog2N

2

21212 频率抽取法(DIF)。DIF算法是对于任意一个N=2t(t>1)点长序列的DFT运算,将频域上的输出序列X(k)按照k的奇偶性分解成偶数和奇数序列,从而把一个N点DFT分解成两个N 2点

k

2次与旋转因子WN的乘法以及DFT,这需要做N

第1页

你可能喜欢

  • 快速傅里叶变换原理
  • FFT快速傅里叶变换
  • 离散傅立叶变换
  • 傅里叶分析
  • 乘法快速算法
  • 快速算法数学
  • 快速排序算法

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email