文档介绍：第四章 FFT
§4-5线性卷积的FFT算法
§4-3 DIF的FFT算法
§4-4 IFFT算法
§4-2按时间抽取(DIT)的FFT算法
§4-1 引言
点击进入
目
§4-1引言
两者的差别仅在指数的符号和因子1/N.
通常x(n)和 都是复数,所以计算一个
X(k)的值需要N次复数乘法运算,和次
,所有的X(k)就要N2次复
数乘法运算,N(N-1)
大时,运算量将是惊人的,如N=1024,则要完
成1048576 次(一百多万次),难以做到实时处理.
一个X(k)的值的工作量,如X(1)
1. 的对称性和周期性
得:
对称性:
周期性:
利用上述特性,可以将有些项合并,并
将DFT分解为短序列,从而降低运算次数,提
,库利(cooley)和图基
(Tukey),仅需
(N/2)log2N =1024=210 时,
需要(1024/2)log2 210 =512*10=5120次。
5120/1048576=% ,速度提高20倍
§4-2 按时间抽取(DIT)的FFT算法 —库利-图基算法
(基2FFT)
(一)N/2点DFT
,设N=2L ,不足时,可补些零。这样有:
n为偶数时:
n为奇数时:
因此,
由于:
所以,上式可表示为:
(n为偶数) (n为奇数)
其中,
:
(1) X (k),X (k)均为N/2点的DFT。
(2) X(k)=X (k)+W X (k)只能确定出
X(k)的k= 个;
即前一半的结果。
1 2
1 2
k
N
同理,
这就是说,X1(k),X2(k)的后一半,分别
等于其前一半的值。
(k)的后一半的确定
由于(周期性),所以: