当前课程知识点：数字信号处理 > 第4章 快速傅里叶变换（FFT） > 4.5 按频率抽选的基-2FFT算法的运算量和算法特点 > 4.5 按频率抽选的基-2FFT算法的运算量和算法特点
同学们好
今天我们要给大家讲述的是
按频率抽选的基2FFT算法的
运算量和算法特点
在讨论这种算法的运算量的时候
我们把上一次
推出来的按频率抽选的
基2FFT的流图拿出来看一看
在这个图形中
我们计算
N等于8点的序列 x(n) 的DFT
实际上最终
也都是来计算蝶形
我们来数一下蝶形的个数
当N等于8的时候
蝶形一共有三列
也就是8等于2的三次方
也就是L列
再来看每一列蝶形的个数
均为4个
也就是N/2
所以整个
计算过程中
蝶形的数量是
N/2乘以L
而每一个碟形
都需要计算一次复数乘法
和两次复数加法
因此总的复数乘法的次数就为
N/2L
也就是N/2log2N
而复数加法的次数为
NL也就是Nlog2N
同样的我们可以来比较一下
直接计算DFT时候的运算量
和按频率抽选的
基2FFT算法的运算量
它们的比值为
N的平方
/N/2log2N
又等于2N/log2N
接下来我们来看
按频率抽选的基2FFT算法的算法特点
它第1个算法特点
是原位计算
这一点和前面所讲过的
按时间抽选的基2FFT算法是一样的
也就是我们所说过的同值计算
它的第2个运算特点
就是蝶形运算
按频率抽选的蝶形运算
和按时间抽选的蝶形运算
是不一样的
按频率抽选的蝶形运算
对一个N=2的L次方点的FFT
它的输入是一个自然顺序
输出是一个倒位序
关于倒位序我们在前面讲
按时间抽选的基2FFT算法已经介绍过
而两个节点之间的距离
2的L-m方
就等于
N/2的m次方
其中
第m级的运算
Xm(k)
是等于
Xm-1(k)
加上
Xm-1
(k+N/2的M次方)
Xm（k+N/2的m次方）
是等于Xm-1(k)
减去Xm-1
(k+N/2的m次方
再乘一个WNr
在蝶形运算过程中
旋转因子
它的确定方法是这样的
蝶形运算
两个节点的第1个节点为k值
表示成L位的二进制数
左移m-1位
把右边空出来的位置补零
结果就为r的二进制数
最后我们来讨论一下
按时间抽选
和按频率抽选的基2FFT算法它们的异同点
首先
按时间抽选和按频率抽选
它们的基本蝶形是不同的
按时间抽选的基2FFT算法
是先进行复数乘法
再进行复数加法
而按频率抽选这个算法
是先进行复数加法
再进行复数乘法
第2个是关于运算量
按时间抽选和按频率抽选的基2FFT算法
它们的运算量是相同的
它们所需要的计算的蝶形的个数也是相同的
而每一个基本蝶形所需要的运算量
都是一次复数乘法和两次复数加法
所以这两种方法的运算量是完全相同的
第3个就是
按时间抽选和按频率抽选
这两种算法都是一个原位运算
最后按时间抽选和按频率抽选的基本蝶型
互为转制结构
同学们
今天这节课我们就上到这儿
谢谢大家
-绪论
-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章作业
