0
1个
2 N
0 N
、W ,
1 N 3 、W N2、W N,
N 1 2 N
2个 4个
第三列 4种类型运算 系数 WN、W ……
0
0 1 2 第M列 N/2种类型运算 系数 WN、W N、W N .......W
, 共N/2 个
4.2.3按时间抽取的FFT算法的特点
(6) 存储单元
原位运算共需:N个单元存放 x(n)以及N/2 个单元存放 (k=0,1,……,N/2 –1)
第4章 快速傅里叶变换(FFT) 要点:有限长序列可以通过离散傅里 叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大, 很难实时地处理问 题, 因此引出了快速傅里叶变换(FFT) . FFT 并 不 是 一 种 新 的 变 换 形 式 , 它 只 是 DFT的一种快速算法.并且根据对序列分 解与选取方法的不同而产生了FFT 的多 种算法. FFT在离散傅里叶反变换、线性 卷积和线性相关等方面也有重要应用.
4.2按时间抽取的快速傅里叶变换算法
2 ( X (k ) DET [ x(n)] x(n)WNnk x1 (2r )WN rk x2 (2r 1)WN2 r 1) k n 0 r 0 r 0
N 1 2 r 0 N 1 2 r 0
N 1
N 1 2
N 1 2
N 1
0 n N 1
(n=0,1,...,N-1) .
4.1快速傅里叶变换
二者计算量相同, 因此以DFT为例, 则 完成整个DFT运算共需 N * N 次复数乘 法以及N * ( N - 1 ) 次复数加法. 即 4 * N * N 次实数乘法及2 N * ( 2 N - 1 ) 次实数 加法. 当 N=1024 时 , 直 接 DFT 算 法 需 复 乘 1,048, 576次, 所以要进行数字的实时处 理, 就必须设法减少其运算量.