第4章 快速傅立叶变换 问题的提出 解决问题的思路与方法 基2时间抽取FFT算法 基2时间抽取FFT算法的计算复杂度

Presentation on theme: "第4章 快速傅立叶变换 问题的提出 解决问题的思路与方法 基2时间抽取FFT算法 基2时间抽取FFT算法的计算复杂度"— Presentation transcript:

1 第4章 快速傅立叶变换 问题的提出 解决问题的思路与方法 基2时间抽取FFT算法 基2时间抽取FFT算法的计算复杂度
第4章 快速傅立叶变换 问题的提出 解决问题的思路与方法 基2时间抽取FFT算法 基2时间抽取FFT算法的计算复杂度 基2时间抽取FFT算法流图规律 基2频率抽取FFT算法 FFT算法的实际应用

2 问题的提出 4点序列{2，3，3，2} DFT的计算复杂度 如何提高DFT的运算效率? 复数乘法 N 2 复数加法 N(N-1)

3 解决问题的思路 1. 将长序列DFT分解为短序列的DFT 2. 利用旋转因子 的周期性、对称性、可约性。

4 旋转因子 的性质 1)周期性 2) 对称性 3)可约性

5 解决问题的方法 将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。
基2时间抽取(Decimation in time)FFT算法 基2频率抽取(Decimation in frequency)FFT算法

6 基2时间抽取FFT算法流图 N=2 x[k]={x[0], x[1]}

7 4点基2时间抽取FFT算法流图 X1[0] x[0] X [0] 2点DFT X1[1] x[2] X [1] -1 X2[0] x[1]

8 4点基2时间抽取FFT算法流图

9 8点基2时间抽取FFT算法流图 x[0] X [0] x[2] X [1] 4点DFT x[4] X [2] X [3] x[6] x[1]
-1 X2[1] X [5] -1 X2[2] X [6] -1 X2[3] X [7] -1

10 8点基2时间抽取FFT算法流图 x[0] X [0] x[2] X [1] 4点DFT x[4] X [2] X [3] x[6] x[1]
-1 X2[1] X [5] -1 X2[2] X [6] -1 X2[3] X [7] -1

11 基2时间抽取FFT算法 第三级 第一级 第二级

12 算法的计算复杂度 复乘次数 复乘次数 N N 2

13 基2时间抽取FFT算法流图 第三级 第一级 第二级

14 FFT算法流图旋转因子 规律 第一级的蝶形系数均为 ，蝶形节点的距离为1。 第二级的蝶形系数为 ，蝶形节点的距离为2。
第一级的蝶形系数均为 ，蝶形节点的距离为1。 第二级的蝶形系数为 ，蝶形节点的距离为2。 第三级的蝶形系数为 ，蝶形节点的距离为4。 第M级 的蝶形系数为 ，蝶形节点的距离为N /2。

15 倒序 k k k 1 x [00 0] 1 1] x [ k 0] x [10 0] 1 x [01 0] x [11 0] x [ k ]
1 2 1 x [00 0] 1 1] 1 2 x [ k 0] x [10 0] 倒序 1 x [01 0] x [11 0] x [ k 2 1 ] 1 x [001 ] 1 x [101 ] 1 x [01 1] x [111 ]

16 基2频率抽取FFT算法

17 4点 DFT W W 4点 W DFT W x[0] X[0] x[1] X[2] x[2] X[4] x[3] X[6] x[4]
N W -1 x[1] x[5] 1 N W -1 x[2] x[6] 2 N W -1 x[3] x[7] 3 N W -1 4点 DFT X[1] X[3] X[5] X[7]

18 W x[0] 2点 x[1] x[2] x[3] x[4] x[5] x[6] W x[7] W W DFT 2点 DFT 2点 DFT
N W 1 2 3 -1 x[0] x[3] x[1] x[2] x[4] x[5] x[6] x[7] 2点 DFT X[0] -1 X[4] -1 N W 2点 DFT X[2] 2 N W X[6] 2点 DFT X[1] 2 N W -1 X[5] 2点 DFT X[3] X[7]

19 W W W W W W W W W W W W x[0] X[0] x[1] X[4] x[2] X[2] x[3] X[6] x[4]
x[1] N X[4] -1 W x[2] N X[2] -1 W 2 W x[3] N N X[6] -1 -1 W x[4] N X[1] -1 W 1 W x[5] N N X[5] -1 -1 W 2 W x[6] N N X[3] -1 -1 W 3 W 2 W x[7] N N N X[7] -1 -1 -1

20 FFT算法应用 利用N点复序列的FFT计算两个N点实序列FFT 利用N点复序列的FFT，计算2N点序列的FFT 利用FFT计算IFFT

21 利用N点复序列的FFT算法计算 两个N点实序列FFT x1[k], x2[k]是实序列， 将其构成复序列y[k]=x1[k]+j x2[k] DFT{x1[k]+j x2[k]}=YR [m]+jYI [m]

22 利用N点复序列的FFT，计算2N点序列的FFT
y[k]是一个长度为2N的序列 问题：如何利用N点FFT，计算4N点序列的FFT？

23 利用FFT实现IFFT 步骤：A) 将X [m]取共轭 C) 对B)中结果取共轭并除以N