第4章 离散傅里叶变换(2)

第五节 快速傅里叶变换

N 4 W矩阵为： W 0 0 W W 0 0 W W 0 W 0 W 0 W 0 0 1 2 3 W W W W 0 2 4 6 W W W W 0 W3 W6 W9 W W0 W1

W0 W W0 W 00

W 0 W 1

1 W W 0 W1 W0

矩阵由原来的16个元素变为了2个独立元素。

《测试信号分析与处理》课程 ,第4章 离散傅里叶变换;第一节 序列的傅里叶变换 —非周期序列频谱 第二节 离散傅里叶级数(DFS) —周期序列频谱 第三节 离散傅里叶变换(DFT) —有限长序列离散频谱 第四节 离散傅里叶变换的性质

第五节 快速傅里叶变换二、基2时析型FFT算法(时间抽取法)

1.算法原理 对长度为 N 2 L (L为正整数，若原序列的长 度不满足此条件，则可用零补足)的序列x(n),按 序列各项序号的奇偶将序列分成两个子序列(大点 数化为小点数),有 偶序号序列 y(r ) x(2r ) 奇序号序列 z(r ) x(2r 1) X(n)的DFT最后结果 蝶形图 X (k ) Y (k ) W Z (k ) N k X ( k ) Y ( k )

W N Z (k ) 2 k N

Y(k)

X(k)

WN k

Z(k)

-1

X(k+N//2)

《测试信号分析与处理》课程 ,第4章 离散傅里叶变换;第一节 序列的傅里叶变换 —非周期序列频谱 第二节 离散傅里叶级数(DFS) —周期序列频谱 第三节 离散傅里叶变换(DFT) —有限长序列离散频谱 第四节 离散傅里叶变换的性质

第五节 快速傅里叶变换2.算法的具体实现

《测试信号分析与处理》课程 ,第4章 离散傅里叶变换;第一节 序列的傅里叶变换 —非周期序列频谱 第二节 离散傅里叶级数(DFS) —周期序列频谱 第三节 离散傅里叶变换(DFT) —有限长序列离散频谱 第四节 离散傅里叶变换的性质

第五节 快速傅里叶变换 3.流程图规律 1)蝶群序号

蝶距(序号 差)

蝶群宽(点 数)

蝶群数

第一级(2 点DFT)

20 2i 1

2 2i

1

N 21

第i级( 2i 点DFT)

N 2i

2)L级蝶形运算，每一级都是“同址运算”

《测试信号分析与处理》课程 ,第4章 离散傅里叶变换;第一节 序列的傅里叶变换 —非周期序列频谱 第二节 离散傅里叶级数(DFS) —周期序列频谱 第三节 离散傅里叶变换(DFT) —有限长序列离散频谱 第四节 离散傅里叶变换的性质

第五节 快速傅里叶变换 3)每个蝶形单元的运算，都包括乘 与相应的DFT结果加减各一次k W 4)同一级中， N 的分布规律相同k WN

,并

第i级( 2 点DFT): W

i

0 2i

; W

1 2i

;...; W

2 i 1 1 2i