第4意快速傅里叶夜换(H 第4章快速傅里叶变换(FT) 41引言 4.2基2FFT算法 43进一步减少运算量的措施 44分裂基FFT算法 45离散哈特莱变换OHT Back
第4章 快速傅里叶变换(FFT) 第4章 快速傅里叶变换(FFT) 4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施 4.4 分裂基FFT算法 4.5 离散哈特莱变换(DHT)
第4意快速傅里叶夜换(H 41引言 DFT是信号分析与处理中的一种重要变换。因直 接计算DFT的计算量与变换区间长度N的平方成正比, 当N较大时,计算量太大,所以在快速傅里叶变换(简 称FFT)出现以前,直接用DFT算法进行谱分析和信号 的实时处理是不切实际的。直到1965年发现了DFT的 种快速算法以后,情况才发生了根本的变化
第4章 快速傅里叶变换(FFT) 4.1 引言 DFT是信号分析与处理中的一种重要变换。因直 接计算DFT的计算量与变换区间长度N的平方成正比， 当N较大时，计算量太大，所以在快速傅里叶变换(简 称FFT)出现以前，直接用DFT算法进行谱分析和信号 的实时处理是不切实际的。直到1965年发现了DFT的 一种快速算法以后，情况才发生了根本的变化
第4意快速傅里叶夜换(H 42基2FFT算法 42.1直接计算DFT的特点及减少运算量的基本途径 长度为N的有限长序列x(n)的DFT为 X(k)=∑x(m)WM,k=0,1…,N (4.2.1) 考虑x(n)为复数序列的一般情况,对某一个k值, 直接按(4,2.1)式计算X(k)值需要N次复数乘法、(N-1)次 复数加法
第4章 快速傅里叶变换(FFT) 4.2 基2FFT算法 4.2.1 直接计算DFT的特点及减少运算量的基本途径 长度为N的有限长序列x(n)的DFT为 考虑x(n)为复数序列的一般情况，对某一个k值， 直接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次 复数加法。 1 0 ( ) ( ) , 0,1, , 1 N kn N n X k x n W k N − = = = − (4.2.1)
第4章快速傅里叶夜换(FEE) 如前所述,N点DFT的复乘次数等于N2。显然, 把N点DFT分解为几个较短的DFT,可使乘法次数大大 减少。另外,旋转因子W具有明显的周期性和对称 性。其周期性表现为 2丌 m+IN -j-、,(m+N) e W (4.2.2) N 其对称性表现为 WNn=WNm或者[WN=m]=W n+一
第4章 快速傅里叶变换(FFT) 如前所述，N点DFT的复乘次数等于N2 。显然， 把N点DFT分解为几个较短的DFT，可使乘法次数大大 减少。另外，旋转因子Wm N具有明显的周期性和对称 性。其周期性表现为 2 2 j m lN j m ( ) m lN m N N W e e W N N − + − + = = = (4.2.2) 其对称性表现为 2 [ ] m N m N m m N N N N N m m N N W W W W W W − − − + = = = − 或者
第4意快速傅里叶夜换(H 422时域抽取法基2FFT基本原理 算法基本上分为两大类:时域抽取法 FFr( Decimation in time fft简称 DIT-FFT)和频域抽取 法 FT(Decimation In Frequency FFT简称DF-FT)。 下面先介绍DF一FT算法。 设序列x(n)的长度为N,且满足 N=2,M为自然数 按血的奇偶把x(n)分解为两个N2点的子序列 ,( 2 0 N (r)=x(2r+1)
第4章 快速傅里叶变换(FFT) 4.2.2 时域抽取法基2FFT基本原理 FFT 算法基本上分为两大类：时域抽取法 FFT(Decimation In Time FFT,简称DIT-FFT)和频域抽取 法FFT(Decimation In Frequency FFT,简称DIF―FFT)。 下面先介绍DIF―FFT算法。 设序列x(n)的长度为N，且满足 2 , M N M = 为自然数 按n的奇偶把x(n)分解为两个N/2点的子序列 1 2 ( ) (2 ), 0,1, 1 2 ( ) (2 1), 0,1, 1 2 N x r x r r N x r x r r = = − = + = −
第4意快速傅里叶夜换(H 则x(m)的DFT为 X()=∑x(m)W+∑x(n)W如 N/2-1 ∑x(2)W+∑x(2r+1 k(2r+1) ∑x(m)+W 2kr 由于 r=0 r=0 2kr r kr- N/2 所以 N/2-1 X(k)=∑x()W2+W∑x2()2=X1(k)+WK2(k) r=0
第4章 快速傅里叶变换(FFT) 则x(n)的DFT为 / 2 1 / 2 1 2 (2 1) 0 0 / 2 1 / 2 1 2 1 2 0 0 ( ) ( ) ( ) (2 ) (2 1) ( ) ( ) kn kn N N n n N N kr k r N N r r N N k kr N N r r X k x n W x n W x r W x r W x r W x r W = = − − + = = − − = = = + = + + = + 由于 2 2 2 2 2 2 / 2 j kr N j kr kr kr N W e e W N N − − = = = 所以 / 2 1 / 2 1 1 / 2 2 / 2 1 2 0 0 ( ) ( ) ( ) ( ) ( ) N N kr k kr k N N N N r r X k x r W W x r W X k W X k − − = = = + = +
第4章快速傅里叶夜换(FEE) 其中X(k)和X2(k)分别为x1(r)和x2r)的N2点DFT, N/2-1 X,(k)=>,(r)W/2=DFT[,(r) (4.2.5) X2(k)=2 x2(r)WT2=DFT[x2(r) (4.2.6) 由于X1(k)和X2(k)均以N2为周期,且 WN2=-W,所以X(k)又可表示为 X(k)=X1(k)+WX2(k)k0,N-1 (4.2.7) X(k、N、x)所X2(k)k=02… (4.2.8)
第4章 快速傅里叶变换(FFT) 其中X1 (k)和X2 (k)分别为x1 (r)和x2 (r)的N/2点DFT， 即 / 2 1 1 1 / 2 1 0 / 2 1 2 2 / 2 2 0 ( ) ( ) [ ( )] ( ) ( ) [ ( )] N kr N r N kr N r X k x r W DFT x r X k x r W DFT x r − = − = = = = = (4.2.5) (4.2.6) 由于X1 (k)和X2 (k)均以N/2为周期，且 2 ，所以X(k)又可表示为 N k k W W N N + = − 1 2 1 2 ( ) ( ) ( ) 0,1, 1 2 ( ) ( ) ( ) 0,1, 1 2 2 k N k N N X k X k W X k k N N X k X k W X k k = + = − + = − = − (4.2.7) (4.2.8)
第4意快速傅里叶夜换(H a+BC B A- BC 图42.1蝶形运算符号
第4章 快速傅里叶变换(FFT) 图4.2.1 蝶形运算符号 C A B A＋ BC A－ BC
第4意快速傅里叶夜换(H X1(0) X(0) N2点X1(1) X(1) x1(2) X(2) DET x1(3) X(3) X(4) N2点X2(1) X(5) x2(2) x(5 X(6) DET x2(3) X(7) 图422N点DFT的一次时域抽取分解图(N=8)
第4章 快速傅里叶变换(FFT) 图4.2.2 N点DFT的一次时域抽取分解图(N=8) N/ 2点 DFT W N 0 N/ 2点 DFT W N 1 W N 2 W N 3 x(0) X1 (0) x(2) x(4) x(6) x(1) x(3) x(5) x(7) 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)
第4意快速傅里叶夜换(H 与第一次分解相同,将xl(r)按奇偶分解成两个N/4 长的子序列x3()和x4(l),即 x1(D)=x(21+、l=01.M x()=x2(2) 4 那么,X1(k)又可表示为 N/4-1 X(k)=∑x(2)W32+∑x1(21+1)2 N/4-1 N/4-1 ∑x(1)WM4+W2∑x1()WM i=0 x3(k)+WMa2X4(k),k=0,1,…N/2 (4.2.9)
第4章 快速傅里叶变换(FFT) 与第一次分解相同，将x1(r)按奇偶分解成两个N/4 长的子序列x3 (l)和x4 (l)，即 3 2 4 1 ( ) (2 ) , 0,1, , 1 ( ) (2 1) 4 x l x l N l x l x l = = − = + 那么，X1 (k)又可表示为 / 4 1 / 4 1 2 (2 1) 1 1 / 2 1 / 2 0 0 / 4 1 / 4 1 3 / 4 / 2 4 / 4 0 0 3 / 2 4 ( ) (2 ) (2 1) ( ) ( ) ( ) ( ), 0,1, / 2 1 N N kl k l N N i i N N kl k kl N N N i i k N X k x l W x l W x l W W x l W x k W X k k N − − + = = − − = = = + + = + = + = − (4.2.9)