数字信号处理_4 FFT概述.pptVIP免费

1第5章快速傅里叶变换25.1概述10()[()]()NnkNnXkDFTxnxnW101()[()]()NnkNkxnIDFTXkXkWN2/cos2/sin2/jNNWeNjNN点有限长序列x(n)DFT:IDFT:其中0,1,1kN0,1,1nN3DirectcomputationcostofDFTExample:x(n)={2，3，3，2}，computeitsDFT.1,1,0,10NkWnxkXknNNn000044440233210XWWWW01234444123321XWWWWj02464444223320XWWWW03694444323321XWWWWjHowmanycomplexadditions？N=4，Howmanycomplexmultiplications？4直接计算DFT的计算量10:()(),01NknNnDFTXkxnWkN222011222112221(1)(1)(1)(1)1111()(0)1()(1)()()1()1jjnjNNNNjkjknjkNNNNkNjNjNnjNNNNNXxeeeXxXxkeeeXeee(1)xNN×1N×NN×15运算量复数乘法复数加法一个X(k)N个X(k)(N点DFT)实数乘法实数加法一次复乘42一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)(N点DFT)4N22N(2N–1)10()NnkNnxnWajbcjdacbdjadcbNN–1N2N(N–1)6数据长度复乘复加NN2N(N-1)1625624032102499264409640321281638416256102410485761047552..................7nkNW()()nkNnknNkNNNWWWnkmnkNmNWW//nknkmNNmWW2jnknkNNWe（1）对称性（2）周期性（3）可约性的特性())nNKNnKnKNNNWWW（-()221;NNKKNNNWWW可得*KNnKnKnNNNWWW01;NW8FFTDFTDFTDFTDFT算法的基本思想：利用系数的特性，合并运算中的某些项，把长序列短序列，从而减少其运算量。N/2DFTN/2DFTNDFT一级分裂N/2次复数乘法N/2DFTN/2DFTNDFT重新组合2222NN复数乘法：22222NNN组合的计算量:N/29两级分裂22442NNN次复数乘法NN42N/2DFTNDFTN/4DFTN/4DFTN/4DFTN/4DFTN/2DFT两级分裂第一级第二级101点DFT：)()()0(00nxWnxX分裂到1-DFT1111111122224481-DFT2-DFT4-DFT8-DFT2logLN级Totalcost:2log2NNFFT:次复数乘法202LNL每级有N/2次由于组合造成的附加计算量2LN假设序列长度为：二分，共11算法计算复杂度复乘次数NN2NN2log2(DirectDFT)(FFT)12•时间抽选法DIT:Decimation-In-Time•频率抽选法DIF:Decimation-In-FrequencyFFT算法分类13•课堂练习–5.2•作业–5.1(a)1.048576秒(b)5.120毫秒(c)16.777216秒，24.576毫秒解：