《数字信号处理》课程教学资源（PPT课件讲稿）第四章 快速傅里叶变换

第四章快速傅里叶变换 §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.510 6 6 =10 65.510 设 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算法)