快速傅里叶变换(FFT).pptxVIP

01引言03进一步减少运算量的措施02基2FFT算法04其它快速算法简介第4章快速傅里叶变换(FFT)

DFT是信号分析与处理中的一种重要变换。直接计算DFT的计算量N2无法直接用DFT算法进行谱分析和信号的实时处理直到——1965年：DFT的一种快速算法出现……FFT更快、更灵活的好算法4.1引言

4.2.1直接计算DFT的特点及减少运算量的基本途径长度为N的有限长序列x(n)的DFT为：若x(n)为复数序列，则123654(4.2.1)对N个k值，共需要：N2次复数乘法和N(N-1)次复数加法对一个k值，直接按上式计算X(k)值需要：N次复数乘法、(N-1)次复数加法4.2基2FFT算法

把N点DFT分解为几个较短的DFTN点DFT的复乘次数、复加次数都N2。1利用旋转因子WmN的周期性和对称性。周期性：2(4.2.2)3对称性：4或者5减少运算量的途径：6

4.2.2时域抽取法基2FFT基本原理FFT算法基本上分为两大类：时域抽取法FFT（DIT-FFT：DecimationInTimeFFT）频域抽取法FFT（DIF-FFT：DecimationInFrequencyFFT）DIT―FFT算法：设序列x(n)的长度为N，且满足为自然数按n的奇偶把x(n)分解为两个N/2点的子序列：

P1由于P2所以则x(n)的DFT为：

由于X1(k)和X2(k)均以N/2为周期，且，所以X(k)又可表示为其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即

图4.2.1蝶形运算符号

图4.2.28点DFT的一次时域抽取分解运算流图

运算量分析：完成一个蝶形运算需要：一次复数乘法运算、两次复数加法运算。经过一次分解后，计算1个N点DFT共需要：计算两个N/2点DFT、N/2个蝶形运算，即总共需要的复数乘法次数为：复数加法次数为：

由于N=2M,N/2仍然是偶数，故可以对N/2点DFT再作进一步分解。与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即那么，X1(k)又可表示为

01式中02同理，由X3(k)和X4(k)的周期性和WmN/2的对称性Wk+N/4N/2=-WkN/2最后得到：

其中经过第二次分解，又将N/2点DFT分解为2个N/4点DFT和N/4个蝶形运算。壹贰用同样的方法可计算出：

图4.2.38点DFT第二次时域抽取分解运算流图依次类推，经过M次分解，最后将N点DFT分解成N个1点DFT和M级蝶形运算，而1点DFT就是时域序列本身。0102

图4.2.48点DIT―FFT运算流图

N=201x[k]={x[0],x[1]}02基2时间抽取FFT算法流图

4点基2时间抽取FFT算法流图x[0]x[2]x[1]x[3]X1[0]X1[1]X2[0]X2[1]2点DFT2点DFT-1-1-1-1X[0]X[1]X[2]X[3]

4点基2时间抽取FFT算法流图

8点基2时间抽取FFT算法流图4点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]-1-1-1-1

8点基2时间抽取FFT算法流图4点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]-1-1-1-1

第一级第二级第三级基2时间抽取FFT算法

4.2.3DIT―FFT算法与直接计算DFT运算量的比较N=2M运算流图有M级蝶形，每一级都有N/2个蝶形运算，每一级运算都需要N/2次复数乘和N次复数加。所以，M级运算总共需要的复数乘次数为：复数加次数为：例如，N=210=1024时123

图4.2.5FFT算法与直接计算DFT所需乘法次数的比较曲线

4.2.4DIT―FFT的运算规律及编程思想原位计算1N=2M点FFT共进行M级运算，每级有N/2个蝶形运算。同一级中，每个蝶形的两个输入数据只对计算本蝶形有用，而且每个蝶形的输入输出数据结点又同在一条水平线上。这意味着计算完一个蝶形后，所得输出数据可立即存入原输入数据所占用的存储单元。旋转因子的变化规律2N点DIT―FFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因