数字信号处理 第2版 课件 苏令华 3.5 时间抽取基2-FFT

——时间抽取基2-FFT快速傅里叶变换(FFT)应用领域：通信、导航、雷达、声纳、测控等离散傅里叶变换(DFT)DiscreteFourierTransform

信号的频谱分析案例分析时域波形图频域频谱图ADC采样频率数据帧长DSP运算能力直接计算DFT运算量16KHz2048点（128ms）传感器ADC数字信号处理器决策层256万次/帧直升机声音识别装置声信号复乘次数复加次数计算一个X(k)

计算N点X(k)DFT的运算量（N>>1）0641282565121024642561285121024N（取样点数）复乘运算次数×103DFT运算量N=64，N2=4096；N=2048，N2=4194304；DFT的运算量传感器ADC数字信号处理器决策层直升机声音识别装置声信号ADC采样频率数据帧长DSP运算能力直接计算DFT运算量16KHz2048点（128ms）256万次/帧400万次/帧实时性差！JamesWilliamCooleyJohnWilderTukey1965年，FFT(FastFourierTransform)诞生减少运算量的基本途径1将长序列（大点数N）的DFT分解为若干短序列（小点数N）的DFT2利用的周期性和对称性，用短序列的DFT组合出长序列的DFT

实序列

一个N点DFT2点DFTN/4点DFTN/2点DFTN/2点DFTN/4点DFTN/4点DFTN/4点DFT2点DFT2点DFT2点DFT分解算法思想DecimationinTime-基2-FFT2点DFTN/4点DFTN/2点DFTN/2点DFTN/4点DFTN/4点DFTN/4点DFT2点DFT2点DFT2点DFT组合一个N点DFT分解算法思想DecimationinTime-基2-FFT

设序列的长度满足，离散傅里叶变换为：

将点长序列按照时间序号n

的奇偶顺序进行抽取，分解成两个点的子序列，记为和。一个N点DFT分解成两个N/2点DFT012345670123456701234567一个N点DFT分解成两个N/2点DFT0123456701234567024601234567一个N点DFT分解成两个N/2点DFT01234567012345670123一个N点DFT分解成两个N/2点DFT01234567一个N点DFT分解成两个N/2点DFT012345670135701230123快速傅里叶变换n为偶数：n为奇数：一个N点DFT分解成两个N/2点DFT一个N点DFT分解成两个N/2点DFT3.5快速傅里叶变换3.5快速傅里叶变换一个N点DFT分解成两个N/2点DFT0123456712300123DFTDFTDFT一个N点DFT分解成两个N/2点DFT0123456712300123DFTDFTDFTN/2点DFTN/2点DFTN=8=23N/2点DFTN/2点DFT复乘次数复加次数第一次分解运算量分析N/2点DFTN/2点DFTN/4点DFTN/4点DFT8点序列第二次分解流图N/2点DFTN/4点DFTN/4点DFTN/4点DFTN/4点DFT8点序列第二次分解流图N/2点DFT分解成两个N/4点DFT一个N点DFT2点DFTN/4点DFTN/2点DFTN/2点DFTN/4点DFTN/4点DFTN/4点DFT2点DFT2点DFT2点DFTN/2点DFTN/2点DFTN/4点DFTN/4点DFT3.5快速傅里叶变换8点长序列第二次分解流图N/2点DFTN/4点DFTN/4点DFTN/4点DFTN/4点DFT3.5快速傅里叶变换8点长序列第二次分解流图X3(0)X3(1)x(0)x(4)2点DFTDIT基2-FFT算法原理2点序列DFT2点DFT2点DFT2点DFT2点DFT8点序列第三次分解流图372.41126441943042048204.8512010485761024113.8230426214451236.64481638412821.41924096645.412648运算量减少比例FFT运算量DFT运算量序列长度运算量分析0641282565121024642561285121024N（取样点数）复乘运算次数×103DFT运算量FFT运算量运算量分析传感器ADC数字信号处理器决策层直升机声音识别装置声信号数据帧长DSP运算能力直接计算DFT运算量FFT运算量2048点（128ms）400万次/帧1万次/帧256万次/帧[fn,pn]=uigetfile('*.wav','Pickawavefile');[y,fs]=wavread([pnfn]);sound(y(3*(1e+5):5*(1e+5),:),fs)W=zeros(N,N);echooffforn=0:N-1fork=0:N-1W(n+1,k+1)=exp(-j*n*k*2*pi/N);endendechoonx=y((4*(1e+5)+1):(4*(1e+5)+N),1);ticX1=x'*W;tocticX2=fft(x,N);toctocElapsedtimeis

0.295376

seconds.pauseticX2=fft(x,N);tocElapsedtimeis0.001574seconds.figuresubplot(211)plot(abs(X1(1:N)));subplot(212)plot(abs(X2(1:N)));echooff02004006008001000120002040600200400600800100012000204060DFT计算的频谱FFT计算的频谱运算特点DIT-基2-FFT算法流图（8点）存储位置A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)运算特点DIT-基2-FFT算法流图（8点）存储位置A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)运算特点DIT-基2-FFT算法流图（8点）存储位置A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)运算特点DIT-基2-FFT算法流图（8点）存储位置A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)运算特点DIT-基2-FFT算法流图（8点）000100010110001101011