快速傅立叶变换 FFT.ppt

第四章快速傅里叶变换(FFT)
主要内容
DIT-FFT算法
DIF-FFT算法
IDFT高效算法及实序列的FFT算法
线性调频z变换
§ 引言
FFT: Fast Fourier Transform
1965年,Cooley-Turky 发表文章《机器计算傅里叶级数的一种算法》,提出FFT算法,解决DFT运算量太大,在实际使用中受限制的问题。
FFT的应用。频谱分析、滤波器实现、实时信号处理等。
DSP芯片实现。TI公司的TMS 320c30,10MHz时钟,基2-FFT1024点FFT时间15ms。
典型应用:信号频谱计算、系统分析等
系统分析
频谱分析与功率谱计算
§ 直接计算DFT的问题及改进途径
1、 DFT与IDFT
2、DFT与IDFT运算特点
复数乘法
复数加法
一个X(k)
N
N – 1
N个X(k)
(N点DFT)
N 2
N (N – 1)
同理:IDFT运算量与DFT相同。
实数乘法
实数加法
一次复乘
4
2
一次复加
2
一个X (k)
4N
2N+2 (N – 1)=2 (2N – 1)
N个X (k)
(N点DFT)
4N 2
2N (2N – 1)
例用FFT算法处理一幅N×N点的二维图像,如用每秒可做10万次复数乘法的计算机,当N=1024时,问需要多少时间(不考虑加法运算时间)?
解当N=1024点时,FFT算法处理一幅二维图像所需复数乘法约为次,仅为直接计算DFT所需时间的10万分之一。即原需要3000小时,现在只需要2 分钟。
3、降低DFT运算量的考虑
FFT算法分类:
时间抽选法
DIT: Decimation-In-Time
频率抽选法
DIF: Decimation-In-Frequency
§ 按时间抽取(DIT)的FFT算法
(Decimation In Time)
1、算法原理
设序列点数 N = 2M,M 为整数。
若不满足,则补零
将序列x(n)按n的奇偶分成两组:
N为2的整数幂的FFT算法称基-2FFT算法。