文档介绍：Chap4快速傅立叶变换(FFT)
本章主要内容
按时间抽取(DIT)的FFT算法
按频率抽取(DIF)的FFT算法
线性调频z变换
实序列FFT算法
FFT应用
§ 引言
一、DFT的计算工作量
两者的差别仅在指数的符号和因子1/N
§ 引言(续)
分析计算一个X(k)的值的工作量:如X(1)
考虑一般情况: 都是复数
一个X(k):N次复数乘法,(N-1)次复数加法
所有X(k):N2次复数乘法,N(N-1)次复数加法
运算量与N2(序列长度)成正比!
当N很大时,如N=1024,则要完成1048576次
(一百多万次)运算,这样,难以做到实时处理。
§ 引言(续)
二、算法改进
1. 的对称性和周期性
对称性:
周期性:
得到:
§ 引言(续)
利用上述特性,可以将有些项合并,并将DFT分解为短序列,从而降低运算次数,提高运算速度。1965年,库利(cooley)和图基(Tukey)首先提出FFT算法,对于N点DFT,仅需次复数乘法运算。例如:
§ 引言(续)
例如:
将第n项和第N-n项合并,其中实部部分得:
乘法次数减少一半!其它项同样。
§ ——库利-图基算法
一、算法原理(基-2FFT)
(n)按n的奇偶分为两组做DFT,设
不足时可在序列末尾补零,这样有:
n为偶数时:
n为奇数时:
因此:
§(续)
其中:
§(续)
均为N/2点DFT
只能确定出的前N/2,即:
的后N/2点的确定
§(续)
的后一半也完全由的前一半所确定。
结论:
一个N点序列的DFT可由两个N/2点的DFT来确定。