FFT算法是基于可以将一个长度为N的序列的离散傅里叶变换 逐次分解为较短的离散傅里叶变换来计算这一基本原理的。这 原理产生了许多不同的算法,但它们在计算速度上均取得了 大致相当的改善。 在本章中我们集中讨论两类基本的FFT算法。 第一类称为按时间抽取( Decimation -in-Tme)的基2FFT算法, 的命名来自如下事实:在把原计算安排成较短变换的过程中 序列x(n)通常看作是一个时间序列)可逐次分解为较短的子序列 第二类称为按频率抽取( Decimation-in-Frequency)的基2FFT算法 在这类算法中是将离散傅里叶变换系数序列X(k)分解为较短的 子序列。 前面两种算法特别适用于N等于2的幂的情况。 对于N为合数的情况,本章也将介绍两种处理方法
FFT算法是基于可以将一个长度为N的序列的离散傅里叶变换 逐次分解为较短的离散傅里叶变换来计算这一基本原理的。这 一原理产生了许多不同的算法，但它们在计算速度上均取得了 大致相当的改善。 在本章中我们集中讨论两类基本的FFT算法。 第一类 称为按时间抽取(Decimation-in-Time)的基2FFT算法，它 的命名来自如下事实：在把原计算安排成较短变换的过程中， 序列x(n)(通常看作是一个时间序列)可逐次分解为较短的子序列。 第二类称为按频率抽取(Decimation-in-Frequency)的基2FFT算法， 在这类算法中是将离散傅里叶变换系数序列X(k)分解为较短的 子序列。 前面两种算法特别适用于N等于2的幂的情况。 对于N为合数的情况，本章也将介绍两种处理方法
3.5.2时间抽选基2F算法(库里一图基算法) 这种算法简称为时间抽选FFT算法,其基本出发点是,利用旋 转因子WN的对称性和周期性,将一个大的DFT分解成一些逐次 变小的DFT来计算。 分解过程遵循两条规则: ①对时间进行偶奇分解; ②对频率进行前后分解。 设N=2M,M为正整数。为了推导方便,取N=23=8,即离散时间 信号为 x(n)={x(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7)} 按照规则(1),将序列x(n)分为奇偶两组,一组序号为偶数,另一 组序号为奇数,即 x(0),x(2),x(4),x(6)|x(1),x(3),x(5),x(7) 分别表示为: g(r)=x(2r)偶数项 N 0,1 h2(r)=x(2r+1)—奇数项 2
3. 5. 2 时间抽选基2FFT算法(库里—图基算法) 这种算法简称为时间抽选FFT算法，其基本出发点是，利用旋 转因子WN k的对称性和周期性，将一个大的DFT分解成一些逐次 变小的DFT来计算。 分解过程遵循两条规则： ①对时间进行偶奇分解； ②对频率进行前后分解。 设N＝2 M ，M为正整数。为了推导方便，取N＝2 3＝8，即离散时间 信号为 按照规则(1)，将序列x(n)分为奇偶两组，一组序号为偶数，另一 组序号为奇数，即 分别表示为：
根据DFT的定义 N x(k)=∑x(n)W=∑x(n)+>(m)W对 偶数n 奇数n N/2-1 N/2-1 ∑x(2W+∑x(2r+1)W (2r+1)k N/2-1 N/2-1 ∑g()W)*+W∑h()(W系) 〃=0 0 因为WM2=W2,所以上式变为 N/2-1 N/2-1 x(k)=∑g()W对n+W∑h()W对a G(k)+WH(),k=0,1,…N-1364) 上式中的G(k)和H(k)都是N2点的DFT
根据DFT的定义 因为 WN 2=WN/2 1，所以上式变为 上式中的G(k)和H(k)都是N/2点的DFT。 (3.64)
按照规则(2),将Xk)分成前后两组,即 X(k)={X(0),X(1),X(2),X(3)|x(4),X(5),X(6),X(7) 由(364)表示的是N2点DFT,前4个k值的DFT可表示为 X(k)=G(k)+WH(k),k=0,1,2,2~1365) 后4个k值的X(k)表示为: N Xk+ >g(r)w? (+2) W ∑h(r)W (艹+2) 2 N/2 N/2 r=0 因为/(+学) N w,Wz=1所以 N/2 N N/2-1 Xk+ ∑g()W2-W∑h()W N =G(k)-WMH(k),k=0,1,2, 3.66
按照规则(2)，将X(k)分成前后两组，即 由(3.64)表示的是N/2点DFT，前4个k值的DFT可表示为 后4个k值的X(k)表示为： 因为 所以 (3.66) (3.65)
按照式(365)和式(366)可画出图3.15所示的信号流程图。 c(0) X(O)=G(0)+WH(0) x(2) N c(1) 点 X(1)=G(1)+WH(1) G(2) DFT X(2)=c(2)+W(2 G(3) x(6) X(3)=C(3)+W(3) H(0) x X(4)=G(0)-WH(0) x(3) H(1) 点 X(5)=G(1)-WH(1) x(5) H(2) FT X(6)=G(2)-WH(2) H(3) oX(7)=G(3)-WAH(3) 图315N点的DFT计算分解成两个N/2点的DFT计算的时间抽选流程图(N=8)
按照式(3.65)和式(3.66)可画出图3．15所示的信号流程图