一维离散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
离散傅立叶变换及其快速算法_理学_高等教育_教育专区...信号变换概述信号是数字信号处理领域中最基本、最重要...·如果 X 是向量,则此傅立叶变换即变成一维傅立叶...
数字信号处理实验报告6_离散傅里叶变换及其快速算法... %对信号进行快速 Fourier 变换 %求得 Fourier 变换...则此傅立叶变换即变成一维傅立叶变 换 fft; 〃如果...
离散傅里叶变换及其快速算法 概述 ? 傅里叶变换实现了时域到时域到频域的转换,在连续信号 和离散信号处理技术领域有广泛的应用。 ? 为利用计算机计算傅里叶变换,...
离散Fourier变换的算法分析研究_物理_自然科学_专业资料 暂无评价
实验一MATLAB软件简介 数字信号处理 实验三 离散... 数字信号处理实验五 离散...变换即变成一维傅立叶变换 fft; ·如果 X 是矩阵,则是计算该矩阵的二维快速...
快速傅立叶变换算法概述_理学_高等教育_教育专区。傅立叶变换《现代电子技术》 ...PFA 算法就是采用了 Good 映射, 将长度 为 N = N 1 3 N 2 的一维 D ...
算法 上述FFT算法流图也可以用于离散傅里叶 逆变换(Inverse Discrete Fourier ...j 2π M 二维离散傅里叶变换可通过两次一维离散傅里叶 变换来实现: 1)作...
第二章 离散傅立叶变换及其快速算法0_工学_高等教育_教育专区。数字信号处理...x(n)与 的关系可描述为: 数学表示: RN(n)为矩形序列。 符号((n))N 是...
快速FFT变换 快速FFT变换 1 FFT 第二章 离散傅里叶变换及快速算法 快速傅里...二维离散傅里叶变换可通过两次一维离散傅里叶变换来实现: 二维离散傅里叶变换可...
离散傅里叶变换(()*) ;算术傅里叶变换(,)*) ;快速傅里叶变换())*) ...就可以计算出序列的 ( 中的 , ( , 7/0$ 算法描述如下 (采用 $,] [ "...
热门文档