DSP第四章快速傅里叶变换1.ppt

文档介绍：第四章学习目标
理解按时间抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点
理解按频率抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点
理解IFFT算法
了解混合基、分裂基和基-4FFT算法
了解CZT算法
理解线性卷积的FFT算法及分段卷积方法
本章作业练习
P200:
1
2
3
7
9
13
第四章快速傅里叶变换
FFT: Fast Fourier Transform
1965年,Cooley, Tukey
《机器计算傅里叶级数的一种算法》
一、直接计算DFT的问题及改进途径
运算量
复数乘法
复数加法
一个X(k)
N
N – 1
N个X(k)
(N点DFT)
N 2
N (N – 1)
实数乘法
实数加法
一次复乘
4
2
一次复加
2
一个X (k)
4N
2N+2 (N – 1)=2 (2N – 1)
N个X (k)
(N点DFT)
4N 2
2N (2N – 1)
FFT算法分类:
时间抽选法
DIT: Decimation-In-Time
频率抽选法
DIF: Decimation-In-Frequency