第四章快速傅里叶变换 §4-1引言 频域分析:一种有效的工具 DFT: x(n)<>X(k) 0<n<N 0<k<N-1 X(k=X(e 2丌 k X((eo)= ftir (nT) 可题 Yx(n),0≤n≤N-1有效的→快速的→实时处理 Cooley-Tukey, 1965 FFT 丑X(k)0≤k≤N-1
第四章 快速傅里叶变换 §4-1 引言 频域分析：一种有效的工具 DFT: x(n) X (k) 0 n N −1 0 k N −1 k N j X k X e 2 ( ) ( ) = = X (e ) X (e ) FT[x (nT)] a j a j = △ 问题： x(n), 0 n N −1 X(k) 0 k N −1 有效的→ 快速的→实时处理 FFT Cooley −Tukey,1965
第四章快速傅里叶变换 §4-2直接计算DFT的起源和改善DF运算效率的途径 一、直接计算DFT的问题 X(k)=∑x(n)0≤k≤N-1 x(n)=1∑X(k)W0≤n≤N-1 设N=10248092 *: N =10 65.5×10 +:N(N-1) 106 65.5×106
一、直接计算DFT的问题 ( ) ( ) 0 1 1 0 = − − = X k x n W k N N n kn N ( ) 0 1 1 ( ) 1 0 = − − − X k W n N N x n N kn N 第四章 快速傅里叶变换 §4-2 直接计算DFT的起源和改善DFT运算效率的途径 2 ：N +：N(N −1) 6 6 =10 65.510 6 6 =10 65.510 设 N =1024 8092
第四章快速傅里叶变换 §4-2直接计算DFT的起源和改善DF运算效率的途径 二、改善DFT运算效率的基本途径 1利用W的特性 ①WN”=W=W(共轭)对称性 W=W=Wmk周期性
二、改善DFT运算效率的基本途径 ① WN k(N−n ) =WN −kn = (WN kn ) （共轭）对称性 1.利用WN kn的特性 ② WN kn =WN k(n+N) =WN n(k+N) 周期性 第四章 快速傅里叶变换 §4-2 直接计算DFT的起源和改善DFT运算效率的途径
第四章快速傅里叶变换 §4-2直接计算DFT的起源和改善DF运算效率的途径 2.长序列分解 Decimation-in-Time (IT) Decimation-in-Frequency 4 N N 4 N NN N N2(N w- 4= 8 N 4 4 N N N
2．长序列分解 N 2 N 4 N 2 N 4 N 4 N 4 N Decimation-in-Time (DIT) Decimation-in-Frequency (DIF) 第四章 快速傅里叶变换 §4-2 直接计算DFT的起源和改善DFT运算效率的途径 2 2 2 2 2 2 2 N N N N = + → 2 2 N v N 2 2 2 3 2 N = → 8 8 8 2 2 N N 2 2 2 N 4 4 4 2 2 N N = →
第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法) 、算法原理 Vx(n),0≤n≤N-1,N=2(若N≠2",可通过补零达到) FFT→基-2FFT/即N为2的整数幂的FFT 由FF7的定义: M1)=∑xm如k=01.…,N-1(4-4) 2x1(m) DFT N-x(n) DFT ?N-x(n) DFT
一、算法原理 x(n), 0 n N −1, 2 (若 2 ，可通过补零达到) N = N - 2 / 2 FFT FFT → 基 FFT 即N为 的整数幂的 01 1 (4 - 4) : 1 0 − = = = − N n kn N X(k) x(n)W k , , ,N FFT 由 的定义 DFT N x n − ( ) x n DFT N ( ) 2 − 1 x n DFT N ( ) 2 − 2 ? 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法) 令x(m)=x(2r) =01W N x 2(n)=x(2r+ 0., 代入(44)式 X(k)=∑x(2+∑x2r+1)W ∑x)W+vA∑x(nW式中 N x1()=DFT[x1(m)0≤k≤ X(K)+WNX,(k) 2 N 0≤k≤N-1(4-7) X2(k)=DFT[x2(m)0≤k≤ 2
代入(4-4)式 − = − = = + + 1 2 0 1 2 0 2 ( ) (2 ) (2 1) N r N r N r k X k x r WN x r W = = = + 2 0 2 0 2 2 2 1 ( ) ( ) N r N r r k N k N r k x r WN W x n W 1 2 ( ) (2 ) 01 1 = = − N 令 x n x r r , ,..., △ 1 (4 -5) 2 ( ) (2 1) 01 2 = + = − N x n x r r , ,..., △ 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) ( ) ( ) 1 2 X k W X k k = + N 0 k N -1 (4 - 7) 1 2 ( ) [ ( )],0 1 2 ( ) [ ( )],0 2 2 1 1 = − = − N X k DFT x n k N X k DFT x n k 式中：
第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法 可见 DET N-DFT ?N-DFT DET 由(47)式 x1(k) X(k),0≤k≤ N 0<k<一-1 问题:≤k≤N-时,Y(k)=? 2
可见： N −DFT DFT N − 2 DFT N − 2 N −DFT ? 由(4-7)式 1 2 0 − N k ( ) 1 X k X (k), ( ) 2 X k 1 2 0 − N k 问题： −1时， ( ) =？ 2 k N X k N 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法)
第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法 rk 利用W的周期性,W 2 2 N r(+k) X(+)=∑x(r)WN 三∑x(朋 k,0≤k≤N-1 (4-10) 同理有, x:k+)=X().0≤k≤-1(41 可见X1(k)和X2(k的后半部分完全重复了各自的前半部分 代入(4-7)式,有:
rk WN 2 利用 的周期性， ) 2 ( 2 2 k N r N rk WN W + = − = + + = 1 2 0 ) 2 ( 2 1 1 ) ( ) 2 ( N r k N r WN x r N X k − = = 1 2 0 2 1 ( ) N r rk WN x r 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) [ ( ) ( ) ] 可见X1 k 和X2 k 的后半部分完全重复了各自的前半部分 代入(4-7)式，有: 1 2 = 1 ( ) , 0 − N X k k (4-10) 同理有， 1 2 ) ( ), 0 2 ( 2 + = 2 − N X k k N X k (4-11)
第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法 - Tukey X(,+k)=X(k)+x2(k) N W32=e=-10≤k≤--1 2 X(k) -,(k) 0sk≤-1 归纳起来有 X(k)=X1(k)+WX2(k)k=02 (4-13) X(N+6)=X()+x:()k=012-1(4-14) 可见, DET w-DET N-DFT DFT
) ( ) ( ) 2 ( 2 ) 2 1 k X k W X k N X k N N + + = + 1 2 1 0 2 = = − − N W e k j N N 归纳起来有 1 (4 -14) 2 ) ( ) ( ) 0,1,..., 2 ( 1 (4 -13) 2 ( ) ( ) ( ) 0,1,..., 1 2 1 2 + = + = − = + = − N k X k W X k k N X N X k X k W X k k k N k N 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) 1 2 = 1 ( ) − 2 ( ) 0 − N X k W X k k k N 可见， N −DFT DFT N − 2 DFT N − 2 N −DFT
第四章快速傅里叶变换 §4-3按时间抽取(DT的FFT算法( Cooley- Tukey算法) 上述运算可用下列蝶形信号流图表示 x1(k) X(k)=X1()+WX2(k) x1(k) X(+k)=X(k)-Wx() ±运算符 图4-1蝶形运算流图符号
上述运算可用下列蝶形信号流图表示: 第四章 快速傅里叶变换 §4-3 按时间抽取(DIT)的FFT算法(Cooley-Tukey算法) ( ) 1 X k ( ) 1 X k ( ) ( ) ( ) 1 2 X k X k W X k k = + N ) ( ) ( ) 2 ( 1 2 k X k W X k N X k + = − N k WN + − 运算符 图 4-1 蝶形运算流图符号