信号分析与处理第4版齐冬莲ppts3 3-2 优化版.pptxVIP

离散信号的分析

主讲教师：齐冬莲

目录

快速傅立叶变换（FFT）

1DFT的计算量

2DFT的特点及FFT的思想

3基-2算法的FFT的基本思路

4FFT算法的特点

快速傅立叶变换（FFT）

1、DFT的计算量

•DFT

N1N1

nk1nk

X(k)x(n)wNx(n)NX(k)wN

n0k0

•N点DFT的计算量：

•每计算一个X(k)值需要进行N次复数相乘，N-1次复数相加

•对于N个X(k)点，完成全部DFT运算共需N2次复数相乘和N(N-1)

次复数加法

快速傅立叶变换（FFT）

2、DFT的特点及FFT的思想

2

j

N

wNe

N1N1

1nkmk*1(nm)k1,nmlN

•正交性WN(WN)WN

Nk0Nk00,nmlN

rmNr

•周期性WNWN

N

r2r

•对称性WW0N0mN

NNWN1,WNWN1,WN1

N2NN

rnnrnn2jN2j(mN2)

•可约性WNWN/rWrNWNWNee1,WN1

快速傅立叶变换（FFT）

2、DFT的特点及FFT的思想

•由于DFT计算量与N成几何级数增长，可将长序列分解成多个短序

列信号，然后分别求各个短序列的DFT，最后将它们组合，得到原

序列