第四章 快速付里叶变换(FFT) Fast Fourier Transforming
41引言 ●快速付里叶变换FFT ◆有限长序列通过离散傅里叶变换(DFT)将其频域离散化成有限 长序列。但其计算量太大(与N的平方成正比),很难实时地 处理问题,因此引出了快速傅里叶变换(FFT)。 ◆FFT并不是一种新的变换形式,它只是D「T的一种快速算法, 并且根据对序列分解与选取方法的不同而产生了FT的多种算 法 ◆FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重 要应用
4.1引言 ●产生故事 1965(COy].M)和图基( N Turkey)在 《 Mathematic of Computation》杂志上发表了著名的“机器 计算付里级数的一种算法”文章,提出一种快速计算DFT的 方法和计算机程序-揭开了FFT发展史上的第一页
41引 ●本章主要内容 ◆直接计算DFT算法存在的问题及改进途径。 ◆多种DFT算法(吋间抽取算法DIT算法,频率抽取算法DIF算 法,线性调频Z变换即CzT法) ◆FT的应用
42基2F算法 ●DFT计算存在的问题及改进途径 ◆问题提出:设有限长序列X(n),非零值长度为N计算 对x(n)进行一次DFT运算,共需多大的运算工作量?
42基2FF算法 有限长序列x(n)的N点DFT为 X(k)=∑x(m)Wk=0,1,…,N-1 可得,计算X(k的所有N个值,共需NN次复数乘法和 NN-1)次复数加法运算。 结论:大的运算量将导致实时信号处理发生困难
42基2FF算法 ◆减少运算量的途径 口把N点DFT分解为几个较短的DFT,可使乘法次数大大减少 口充分利用旋转因子的周期性和对称性,即 W 周期性:N=N(m-)-2mm 2丌 对称性:W=WAm,[WN]=W,W+2=-W
42基2FF算法 ●时域抽取法基2FFT基本原理 基于2FFT算法分为 ◆时域抽取法FT( Decimation-In- Time fft, DIT-FFT) ◆频域抽取法FFT( Decimation-In- Frequency FFT,DIT- FD
42基2FF算法 ◆DIT-FFT算法 设序列X(n)的长度为N,且满足 N=2M,M为自然数 按n的奇偶把x(n)分解为两个N2点的子序列 N X, (r)=r(2i =0,1, N x2(r)=x(2r+1),r=0,1,…-1
42基2FF算法 Ⅹ(n)的DFT为 X(k)=∑x(n)W+∑x(n)W nEcr+ N/2-1 x(2)W x(2r+1)W(2+ ∑x(rW r,(r)w kr 由于 W2kr se'N e 2-wkr N/2 所以 X(k)=∑x(W2+W∑x2(T)W2=X()+WX2(k)