第03章离散傅里叶变换及其快 速算法 邹江 zhujiang@public.wh.hb.cn
第03章 离散傅里叶变换及其快 速算法 邹江 zoujiang@public.wh.hb.cn
3.5快速傅里叶变换(FFT) 351DFT的计算量 离散傅里叶变换在实际应用中是非常重要的,利用它可以计算信 号的频谱、功率谱和线性卷积等。但是,如果使用定义式(3.20)来 直接计算DFT,当N很大时,即使使用高速计算机,所花的时间也 太多。因此,如何提高计算DFT的速度,便成了重要的研究课题 1965年库利( Cooley和图基( Tukey)在前人的研究成果的基础上提出了 快速计算DFT的算法,之后,又出现了各种各样快速计算DFT的方 法,这些方法统称为快速傅里叶变换( Fast Fourier Transform),简称为 FFT. FFT的出现,使计算DFT的计算量减少了两个数量级,从而成 为数字信号处理强有力的工具。 快速傅里叶变换(F「T)是离散傅里叶变换(OFT)的快速算法。它是 DSP领域中的一项重大突破,它考虑了计算机和数字硬件实现的约 束条件、研究了有利于机器操作的运算结构,使DFT的计算时间缩 短了1~2个数量级,还有效地减少了计算所需的存储容量,FT技术 的应用极大地推动了DSP的理论和技术的发展
3. 5 快速傅里叶变换(FFT) 3.5.1 DFT的计算量 离散傅里叶变换在实际应用中是非常重要的，利用它可以计算信 号的频谱、功率谱和线性卷积等。但是，如果使用定义式(3.20)来 直接计算DFT，当N很大时，即使使用高速计算机，所花的时间也 太多。因此，如何提高计算DFT的速度，便成了重要的研究课题。 1965年库利 (Cooley)和图基(Tukey)在前人的研究成果的基础上提出了 快速计算DFT的算法，之后，又出现了各种各样快速计算DFT的方 法，这些方法统称为快速傅里叶变换(Fast Fourier Transform)，简称为 FFT。FFT的出现，使计算DFT的计算量减少了两个数量级，从而成 为数字信号处理强有力的工具。 快速傅里叶变换(FFT)是离散傅里叶变换(DFT)的快速算法。它是 DSP领域中的一项重大突破，它考虑了计算机和数字硬件实现的约 束条件、研究了有利于机器操作的运算结构，使DFT的计算时间缩 短了1~2个数量级，还有效地减少了计算所需的存储容量，FFT技术 的应用极大地推动了DSP的理论和技术的发展
在导出FFT算法之前,首先来估计一下直接计算DFT所需的计算量 DFT的定义 ∑x(n)W,0≤k≤N-1 X(R)=DFT[x(n)]=3 m= 0, 其它 「∑x()W*,0≤n≤N-1 x(n)= IDFT[X(k)] 其 其中 e =cos(2π/N)-jsin(2π/N
DFT的定义 在导出FFT算法之前，首先来估计一下直接计算DFT所需的计算量。 其中
将DFT定义式展开成方程组 X(0)=x(0)w°+x(1)Wg1+…+x(N-1)W-1 X(1)=x(0)Wk°+x(1)Wk+…+x(N-1)Wk-1 X(2)=x(0)W3+x(1)W3+…+x(N-1)W3w-1) ⅹ(N-1)=x(0)WN-10+x(1)W-11+…+x(N-1)W-1) 将方程组写成矩阵形式 X(0) WWl W(N-1) 「x(0) X(1) W 1·0 l·1 W 1·(N-1) x(1) X(N-1 W-1)0WA-1)1…W-1)( x(N-1) 用向量表示 X-W
将DFT定义式展开成方程组 将方程组写成矩阵形式 用向量表示
用复数表示 Wx={RewW]·Rex-Im[W]·Im[x]} j{Re[W]·Im[x]+Re[x]·Im[w] 从矩阵形式表示可以看出,由于计算一个X(k)值需要N次复乘法和 (N-1)次复数加法,因而计算N个X(k)值,共需№次复乘法和N(N-1)次 复加法。每次复乘法包括4次实数乘法和2次实数加法,每次复加 法包括2次实数加法,因此计算N点的DFT共需要4N2次实数乘法和 (2N2+2N(N-1)次实数加法。当N很大时,这是一个非常大的计算量。 N=8 FF算法主要利用了W的两个性质: 2x (1)对称性,即 N Re 2)周期性,即(m)*=∥n (N-nk k=0 N k=1 k=2 W=Wr为任意整数 图3.14W的特性
从矩阵形式表示可以看出，由于计算一个X(k)值需要N次复乘法和 (N-1)次复数加法，因而计算N个X(k)值，共需N 2次复乘法和N(N-1)次 复加法。每次复乘法包括4次实数乘法和2次实数加法，每次复加 法包括2次实数加法，因此计算N点的DFT共需要4N2次实数乘法和 (2N2+2N·(N-1))次实数加法。当N很大时，这是一个非常大的计算量。 FFT算法主要利用了WN k的两个性质： (1)对称性，即 (2)周期性，即 用复数表示： r为任意整数