当前课程知识点：数字信号处理 > 第4章 快速傅里叶变换（FFT） > 4.3 按时间抽选的基-2FFT算法的运算量和算法特点 > 4.3 按时间抽选的基-2FFT算法的运算量和算法特点
同学们好
今天我们来讲述
按时间抽选的
基2FFT算法的运算量和算法特点
首先我们看到的这个图
是我们上一节课刚刚讲过的
按时间抽选的基2FFT算法
N等于8点的运算流图
整个流图的计算
我们说实际上都是这一个蝶形计算
我们现在来数一下
我们蝶形的个数
整个
蝶形是分为三列
这个3其实就是
8等于2的3次方
也就是L列
每一列都是有4个蝶形
4其实就是N/2
也就是点数的一半
也就是说
当N等于2的L次方的时候
我们一共会有L级的蝶形
而每一级是有N/2个蝶形
我们前面看过
按时间抽选的基本蝶形图
知道每一个蝶形
一共会有一次复数乘法
和两次复数加法
因此我们
采用按时间抽选的
基2FFT算法
来计算一个N点的序列的
DFT所需要的复数乘法次数
应该为
N/2乘以L
也就是N/2乘以
log2N
而复数加法的次数
应该是N乘以L
也就是N乘以log2N
我们把
直接计算DFT
所需要的运算量
和我们用
按时间抽选的基2FFT算法
所需要的运算量进行一个比较
它们的比值应该是等于N的平方
比上一个N/2log2N
等于2N/log2N
我们用图形来描述比较直观
在这个图形中
横坐标为
N也就是我们的抽样点数
纵坐标为复数乘法的次数
而且后面的数量级是要乘以一个10的3次方
我们看到在图形中的两条线
箭头指向的
其中一条线上面写的是
直接计算DFT时所需要的运算量
而在最下面箭头指了一条线
上面写了
这个是
用FFT算法所需要的计算量
大家比较一下就可以看得出来
点数N越大
采用按时间抽选的FFT算法
它所需要的计算量
优势就表现越为明显
好
在完成了刚才的
按时间抽选的基2FFT算法的运算量计算之后
我们来思考一个问题
采用按时间抽选的基2FFT算法
来计算
N等于16点序列的傅里叶变换
请问需要复数乘法多少次
复数加法多少次
接下来我们来研究
按时间抽选的基2FFT算法它的算法特点
第1个就是原位计算
根据按时间抽选的蝶形运算结构
可以看得出来
每一个碟形结运算完成之后
输出的两个节点值
就放到原输入两个节点的存储器中
这就是我们所说的同址计算
或者叫原位计算
第2个特点是它的倒位序
我们在进行按时间抽选的过程中
分解的思路始终是偶数一组
奇数一组
继续分解
依然是偶数一组 奇数一组
那么经过这样的多次的抽选之后
顺序就被打散了
那么这样的一个顺序
是否有什么规律呢
我们把
自然顺序的值
用二进制来进行描述
以N等于8为例
那么这个数我们就以
三位二进制来描述
分别为000 001 010 011
100 101 110 111
对应的值分别为
从0~7
这是一个自然顺序
接下来我们把这
三位二进制都进行一个倒置
倒置之后的结果为
000 100 010 110 001
101 011和111
再把它转成十进制
就是0 4 2 6
1 5 3 7
这其实就是我们
按时间抽选之后
序列的输入这一列的顺序
它称为倒位序
按时间抽选的
基2FFT算法的第3个特点
是蝶形运算
对于N等于2的L次方点的FFT
输入是一个倒位序
而输出是一个自然顺序
第m级的运算
每个蝶形的两节点之间的距离
为2的m减1次方
而第m级的运算
为Xm(k)
等于Xm-1(k)
加上Xm-1
(K+2)的m-1次方乘以WNr
后半部分
Xm(k+2)的m-1次方
是等于Xm-1(k)
减去Xm-1
(k+2)的m-1次方
乘以WNr
描述出来的蝶形
都是我们的
按时间抽选的蝶形的
基本运算单元的结构
在我们刚刚讲过的
按时间抽选的基本蝶形的
表达式中
其中
旋转因子WNr的确定方法
蝶形运算它的两个节点的第1个节点值
为k
把它表示成L位的二进制数
然后再左移L-m位
把右边空出来的位置给它补零
结果就为
r的二进制数
同学们
今天这节课就上到这儿
谢谢大家
-绪论
-1.1 序列及其运算
-1.2 常用典型序列及序列的周期性
-1.3 线性移不变系统
-1.4 常系数线性差分方程
-1.5 连续时间信号的理想抽样
-1.6 连续时间信号的实际抽样
-第1章作业
-2.1 序列z变换的定义及收敛域
-2.2 四种序列的z变换及收敛域举例
-2.3 留数法及部分分式法求z反变换
-2.4 幂级数展开法求z反变换
-2.5 z变换的线性及移位性质
-2.6 z变换的初值和终值定理
-2.7 z变换的卷积定理
-2.8 序列的傅里叶变换及其性质
-2.9 序列的z变换与连续时间信号的拉普拉斯变换、傅里叶变换的关系
--2.9 序列的z变换与连续时间信号的拉普拉斯变换、傅里叶变换的关系
-2.10 离散线性移不变系统的频域表征
-第2章作业
-3.1 傅里叶变换的四种可能形式
- 3.2 周期序列的傅里叶级数（DFS）的定义
-3.3 周期序列的傅里叶级数（DFS）的性质
-3.4 离散傅里叶变换（DFT）的定义
-3.5 DFT的线性和圆周移位性质
-3.6 DFT的圆周共轭对称性质
-3.7 圆周卷积和与圆周卷积和定理
-3.8 线性卷积与圆周卷积的关系
-3.9 频域抽样理论
-第3章作业
-4.1 直接计算DFT的运算量及减少运算量的途径
- 4.2 按时间抽选的基-2FFT算法的算法原理
-4.3 按时间抽选的基-2FFT算法的运算量和算法特点
-4.4 按频率抽选的基-2FFT算法的算法原理
-4.5 按频率抽选的基-2FFT算法的运算量和算法特点
-第4章作业
-5.1 数字滤波器结构的表示方法
-5.2 IIR滤波器的直接型结构
- 5.3 IIR滤波器的级联型结构
- 5.4 IIR滤波器的并联型结构
-5.5 FIR滤波器的基本结构
- 5.6 FIR滤波器的频率抽样型结构
-5.7 线性相位FIR滤波器的结构
-第5章作业
-6.1 数字滤波器的基本概念
-6.2 数字滤波器的技术指标
-6.3 全通滤波器
- 6.4 最小相位滞后滤波器
-6.5 模拟原型巴特沃思低通滤波器设计
-6.6 模拟原型切贝雪夫低通滤波器设计
-6.7 间接法的IIR数字滤波器设计方案
-6.8 冲激响应不变法
-6.9 双线性变换法
-第6章作业
-7.1 FIR数字滤波器的特点
-7.2 FIR数字滤波器的线性相位条件
- 7.3 线性相位FIR数字滤波器频率响应的特点
-7.4 线性相位FIR数字滤波器幅度函数的特点
-7.5 线性相位FIR数字滤波器的零点位置
-7.6 窗函数设计法的设计思路
-7.7 窗函数设计法的性能分析
-7.8 各种窗函数
-7.9 窗函数法的设计步骤
-第7章作业
