数字信号处理PPT课件

.,1,第四章快速傅里叶变换4-1引言,频域分析：一种有效的工具,DFT:,问题：,.,2,一、直接计算DFT的问题,第四章快速傅里叶变换4-2直接计算DFT的起源和改善DFT运算效率的途径,设,.,3,二、改善DFT运算效率的基本途径,第四章快速傅里叶变换4-2直接计算DFT的起源和改善DFT运算效率的途径,.,4,2长序列分解,第四章快速傅里叶变换4-2直接计算DFT的起源和改善DFT运算效率的途径,.,5,一、算法原理,第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),.,6,代入(4-4)式,第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),.,7,可见：,第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),.,8,利用的周期性，,第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),代入(4-7)式，有:,(4-10),.,9,归纳起来有,第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),.,10,上述运算可用下列蝶形信号流图表示:,第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),.,11,例：N=8,第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),.,12,计算量分析：,第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),.,13,2-DFT：,可见仅需计算“+/-”运算。,第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),.,14,例：N=8(P129),第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),图4-5N=8时的按频率抽取FFT运算流图,.,15,例：N=2v_(P130),第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),图4-5N点基-2FFT的级迭代过程,.,16,二、运算量比较,1.DIT-FFT：N=2,第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),由图4-6可见，,2.DFT,.,17,3.DIT-FFT的运算效率,三、DIT-FFT算法的特点,1.原位运算(In-place),第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),.,18,3.输入序列的序号及整序规律,第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),.,19,(1)乱序的原因,例：N=8,第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),.,20,(2)整序的规律,四、DIT-FFT算法的若干变体详见P.134-135:图4-11图4-14,第四章快速傅里叶变换4-3按时间抽取(DIT)的FFT算法(Cooley-Tukey算法),.,21,一、算法原理,将X(n)，0nN-1按顺序分为前后两半,注意：两个和式并不是N/2-DFT,第四章快速傅里叶变换4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法),.,22,所以，式(4-23)可改写为,(4-24),可按k的奇偶取值将X(k)分为两部分：,第四章快速傅里叶变换4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法),.,23,(4-25),(4-26),第四章快速傅里叶变换4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法),.,24,显然，若令,则有（式(4-25)(4-26)分别变为）,第四章快速傅里叶变换4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法),.,25,可见，,第四章快速傅里叶变换4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法),.,26,例：N=8，DIF的分解过程（见图4-16）P.137,第四章快速傅里叶变换4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法),（显然与DIT-FFT算法的分解类似）,.,27,例：N=8，DIF-FFT算法流图图4-18，P.138,注意:,第四章快速傅里叶变换4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法),.,28,二、DIF-FFT与DIT-FFT的比较,图4-18N=8,DIF-FFT算法流图,第四章快速傅里叶变换4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法),.,29,图4-5N=8,DIT-FFT算法流图,第四章快速傅里叶变换4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法),.,30,1.二者的区别,(1)输入与输出DIF：顺序反序DIT：反序顺序,(2)蝶形运算,第四章快速傅里叶变换4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法),DIT：先相乘，后加减,DIF：先加减，后相乘,.,31,2.二者的相似之处,(1)分解过程DIF：列每列N/2个蝶形运算DIT：列同上同上,(2)原位运算（所有运算均由蝶形运算构成）,3.二者关系,第四章快速傅里叶变换4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法),.,32,三、逆DFT的快速算法(IFFT),1.算法一：,比较IDFT与DFT，可见,第四章快速傅里叶变换4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法),.,33,例：N=8，DIT-IFFT算法流图图4-19，P.138,第四章快速傅里叶变换4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法),.,34,2.算法二,优点：,第四章快速傅里叶变换4-4按频率抽取(DIF)的FFT算法(Sande-Tukey算法),四、DIF-FFT算法的若干变体,.,35,(1)通过补零，使序列长度=2基-2FFT,一、算法原理,(2)N=ML（复合数）统一的FFT算法,(3)NML（素数）Chirp-Z变换(CZT),处理方法：,N-DFTN,第四章快速傅里叶变换4-5N为复合数的FFT算法统一的FFT算法,.,36,为此，令,n=Mn1+n0,n0=0,1,M-1列号n1=0,1,L-1行号,第四章快速傅里叶变换4-5N为复合数的FFT算法统一的FFT算法,.,37,同理，对DFT的输出X(k)做类似的处理：,令k=Lk1+k0k0=0,1,L-1n1k1=0,1,M-1n0,第四章快速傅里叶变换4-5N为复合数的FFT算法统一的FFT算法,.,38,=1,第四章快速傅里叶变换4-5N为复合数的FFT算法统一的FFT算法,.,39,第四章快速傅里叶变换4-5N为复合数的FFT算法统一的FFT算法,式中,.,40,二、运算步骤,第四章快速傅里叶变换4-5N为复合数的FFT算法统一的FFT算法,.,41,例：N=12=43,M=4,L=3算法流图：图4-20,P.144,详见(4-38)P.142,第四章快速傅里叶变换4-5N为复合数的FFT算法统一的FFT算法,.,42,三、基数（指特定的分解）,1.N=2基2FFT算法,2.N2,N=r1,r2,rMM级r1,r2,rM点DFT混合基算法,r1=r2=rMN=rMM级r-DFT基-rFFT算法,比如：a)N=2M基-2FFTb)N=4M基-4FFT,第四章快速傅里叶变换4-5N为复合数的FFT算法统一的FFT算法,.,43,四、运算量估算,(1)M个L-DFT：ML2=NLML(L-1)=N(L-1),(2)乘N个因子：N,(3)L个M-DFT：LM2=NMLM(M-1)=N(M-1),总运算量：NL+N+NM=N(L+M+1)N2N(L-1)+N(M-1)=N(L+M-2)50CZT优于直接计算),.,67,第四章快速傅里叶变换4-8线性调频Z变换(Chirp-ZTransform),五、CZT算法的特点,2)N,M均可为质数任意情况,3)取样起始点z0任选：,4)可任意取值,的角间隔（频率）任意,频率分辨率可变,进行窄带学分辨分析,.,68,第四章快速傅里叶变换4-8线性调频Z变换(Chirp-ZTransform),DFT的推广,.,69,第四章快速傅里叶变换4-9细化FFT算法(ZoomFFTorZFFT),一、问题提出,1)FFT/DFT：分辨率fN=fs/N，(0fs),.,70,第四章快速傅里叶变换4-9细化FFT算法(ZoomFFTorZFFT),二、算法原理(详见图4-30/P157),.,71,第四章快速傅里叶变换4-10FFT的应用,一、利用FFT求卷积快速卷积,.,72,第四章快速傅里叶变换4-10FFT的应用,二、利用FFT求相关快速相关,.,73,第四章快速傅里叶变换4-11FFT的其它形式,WinogradFourier