当前课程知识点:数字信号处理 > 四 利用FFT对离散信号与系统进行快速运算 > 4-5 基2FFT算法运算量及运算规律 > 4-5视频
大家好
这节课我们分析
基2-FFT算法运算量以及运算规律
主要内容包括
基2FFT算法运算量
基2FFT算法运算规律
DIT-FFT算法与DIF-FFT算法比较
以及IDFT的高效算法
在分析基2FFT算法运算量之前
我们先来回顾一下
基2DIT-FFT算法运算流图
当N等于8的时候
基2FFT需要三级蝶形运算
每级需要四个碟形
也就是N/2个碟形
所以当N等于2的M次方的时候
一共有M级蝶形
M等于以2为底N的对数
每级有N/2个蝶形运算
下面我们来看
基2FFT算法的运算量
也就是它所需要的复数乘法次数
和复数加法次数
对于一个蝶形来讲
它需要一次复数乘法
和两次复数加法
那么每级有N/2个蝶形运算
所以一级蝶形需要
N/2次复数乘法和N次复数加法
而M级蝶形需要
M乘以N/2次复数乘法
和MN次复数加法
这就是基2FFT所需要的运算量
如果直接计算离散傅里叶变换
需要的复数乘法次数是N的平方次
需要的复数加法次数是N乘以N-1次
所以直接计算离散傅里叶变换
所需要的复数乘法和基2-FFT
所需要的复数乘法运算的比值
是2N除以以2为底的N的对数
例如N等于1024
这二者之比就是204.8
也就是说 直接计算的运算量
比基2FFT的运算量要大很多
下面我们来看
基2FFT算法的运算规律
第一个是原位运算
当数据输入到存储器以后
每个蝶形运算的结果
仍然存放在这一组存储器里面
这就叫做原位运算
也就是说 蝶形运算的输出
还放到原来存放蝶形运算
输入的存储器中
所以原位运算的结构
可以节省存储单元
降低设备成本
我们来举例说明一下
对于这个蝶形运算
x(0) x(4)是输入
把它们分别存放在
A(0)和A(1)存储器里面
系数存放在暂存器中
经过蝶形运算得到输出X3(0)和X3(1)
还存放到A(0)和A(1)中
这个就是原位运算
由于每个蝶形
它的输入只对该蝶形起作用
比如说x(0)和x(4)
它就只对这个蝶形起作用
和别的蝶形没有关系
并且每个蝶形的输入和输出节点位置
是在同一个水平线上
不会影响到其它的蝶形
所以在这个蝶形计算之后
输入就没有用了
因此这一级蝶形运算的输出
还是放在A(0)到A(7)这些存储器里面
覆盖了原来的输入
这样是没有问题的
同样第二级的输出
还是存到A(0)到A(7)这些存储器里面
直到最终的输出
这个就是原位运算
那么对于N点的FFT
它只需要N个存储单元就可以了
对于DIT-FFT
A(0)到A(7)顺序存放了
X(0)到X(7)可以直接输出
第二个是旋转因子的变化规律
在每级蝶形里面都需要乘以系数
这个系数叫做旋转因子
当N等于2的M次方的时候
第L级的旋转因子如公式(1)所示
其中J是从0到2的L-1次方减1
p等于J乘以2的M-L次方
例如N等于8
M等于3 就是有三级蝶形
L等于2 就是第二级
那么第二级需要有两个旋转因子
J等于0的时候
p是等于0的
旋转因子是W8的0次方
等于W4的0次方
J等于1的时候
p等于2
旋转因子是W8的2次方
还等于W4的1次方
那么从这个运算流图里面我们看
最后一级是4个大碟形
需要4个旋转因子
在第二级这两个碟形
需要两个旋转因子
上下两部分是一样的
那我们看后一级中
指数是偶数的旋转因子
就是前一级的旋转因子
W8的0次方等于W4的0次方
W8的2次方等于W4的1次方
所以前一级的旋转因子
是后一级旋转因子中
指数是偶数的那些旋转因子
这是旋转因子的规律
第三个就是倒序
就是码位倒读规则
在DIT-FFT中
输入是按照倒序来进行排列的
输出是按照自然顺序排列的
在DIF-FFT中输入是自然顺序
输出是倒序
那么自然顺序和倒序
它的关系是什么呢
我们从这个表中来看一下
n是自然顺序 从0到7
把它用二进制数来进行表示
就是000 001 一直到111
然后进行码位倒读
就是二进制数从后往前读
所以码位倒读
就是000 100 010 110
再写出它相对应的十进制数
就是它的倒序0 4 2 6 1 5 3 7
如果N等于16
那么自然顺序就是0到15
然后用四位二进制数来表示
再进行码位倒读
就可以得到它的倒序
把输入数据从自然顺序变成倒序
就需要进行数据的交换
输入x(n)存放到存储器A(0)到A(7)中
要把它变成倒序
A(1)和A(4)要进行数据交换
A(3)和A(6)要进行数据交换
那么其它几个存储器
不需要进行数据交换
这个过程就是变址的过程
当n等于倒序的时候
数据不需要交换
当n小于倒序的时候
1小于4
这时候要进行数据的交换
当n大于倒序的时候
表示已经调换过了
所以对于DIT-FFT来讲
在输入的时候要有这个变址运算
而对于DIF-FFT
在输出的时候要进行变址运算
下面我们对DIT-FFT算法
和DIF-FFT算法进行比较
首先看相同之处
两种算法的运算量相同
也就是说
它所需要的复数乘法和复数加法
次数是相同的
第二个相同之处就是
基本的DIT-FFT与DIF-FFT两种算法
都是原位运算
有一些变体运算就不是原位运算了
我们再来看不同之处
一个就是基本的
DIT-FFT与DIF-FFT两种算法结构不同
DIT-FFT输入是倒序
输出是自然顺序
DIF-FFT输入是自然顺序
输出是倒序
同样这个基本的
DIT-FFT和DIF-FFT就是我们
前面介绍的这两种算法
那么在变体结构当中
比如说DIT-FFT它也可以是
输入是自然顺序
输出是倒序的
所以我们在这里说的是
基本的这个算法结构是不一样的
那么DIT和DIF根本的区别就在于
它的蝶形结不一样
蝶形运算不一样
DIT-FFT它是先乘后加减
而DIF-FFT它是先加减后乘
这个就是相同和不同之处
最后我们再来看一下IDFT的高效算法
第一种方法
我们对离散傅里叶变换的
正反变换式进行比较
可以看出
在正变换式中是WN的nk次方
在反变换中是WN的-nk次方
并且最后再乘以一个1/N
所以在原来的FFT算法当中
可以把旋转因子从
WN的p次方变成WN的-p次方
最后输出结果
再乘以1/N就可以得到IFFT
这是第一种方法
在这种方法里面
需要对FFT的程序进行修改
如果我们不想修改FFT算法
而想直接用它的话
可以用下面的这种方法
对IDFT的公式
两边同时取共轭
然后再取一次共轭
这样等式左边还是x(n)
等式右边 我们看中括号里面
它实际上就是X(k)的共轭的
离散傅里叶变换式
所以这个式子又可以写成
X(k)的共轭 进行FFT
再取共轭 乘以1/N
就可以得到X(k)的反变换x(n)了
在这种方法里面
可以直接用FFT的程序
这节课我们学习了
基2FFT算法的运算量
对DIT-FFT和DIF-FFT进行了比较
并且介绍了IDFT的高效算法
这节课的内容我们就学习到这里
再见
-课程简介
-1-0 内容简介
--1-0 视频
-1-1 时域离散信号的表示与运算
--1-1 视频
-1-2 LTI时域离散系统
--1-2 视频
-1-3 系统初始状态对输出的影响
--1-3视频
-1-4 模拟信号数字处理方法
--1-4 视频
-第一模块测试题
--第一模块测试-作业
-2-0 内容简介
--2-0 视频
-2-1 序列的傅里叶变换
--2-1视频
-2-2 序列傅里叶变换的性质
--2-2 视频-1
--2-2 视频-2
-2-3 周期序列离散傅里叶级数与傅里叶变换的表示
--2-3 视频
-2-4 时域离散信号FT与模拟信号FT之间的关系
--2-4视频
-2-5 序列的Z变换及其逆变换
--2-5视频
-2-6 序列Z变换的性质
--2-6 视频
-2-7 利用Z变换求解差分方程
--2-7 视频
-2-8 利用系统函数的极点分布分析系统的因果性和稳定性
--2-8 视频
-2-9 利用Z变换定性分析系统特性
--2-9 视频
-第二模块测试题
--第二模块测试题-作业
-3-0 内容简介
--3-0 视频
-3-1 序列的离散傅里叶变换
--3-1 视频
-3-2 DFT与Z变换、傅里叶变换的关系
--3-2视频
-3-3 离散傅里叶变换的隐含周期性
--3-3 视频
-3-4 离散傅里叶变换的性质
--3-4 视频
-3-5 循环卷积计算
--3-5 视频
-3-6 频率域采样
--3-6 视频
-3-7 利用DFT计算线性卷积
--3-7 视频
-3-8 利用DFT对信号进行谱分析
--3-8 视频
-第三模块测试题
--第三模块测试-作业
-4-0 内容简介
--4-0 视频
-4-1 采用快速傅里叶变换的原因
--4-1 视频
-4-2 减少DFT运算量的途径
--4-2 视频
-4-3 时域抽取法基2FFT
--4-3视频
-4-4 频域抽取法基2FFT
--4-4 视频
-4-5 基2FFT算法运算量及运算规律
--4-5视频
-4-6 进一步减少运算量的措施
--4-6 视频
-第四模块测试题
--第四模块测试-作业
-5-0 内容简介
--5.0视频
-5-1 数字滤波器介绍
--5.1视频
-5-2 滤波器技术指标
--5.2视频
-5-3 巴特沃斯模拟低通滤波器
--5.3视频
-5-4 切比雪夫模拟低通滤波器
--5.4视频
-5-5 脉冲响应不变法设计IIR数字低通滤波器
--5.5视频
-5-6 双线性变换法设计IIR数字低通滤波器
--5.6视频
-5-7 数字各型滤波器的设计
--5.7视频
-5-8 由信号流图求网络系统函数
--5.8视频
-5-9 IIR系统基本网络结构
--5.9视频
-5-10 IIR数字滤波器的工程应用
--5.10视频
-5-11 IIR数字滤波器的量化误差
--5.11视频
-第五模块测试题
--第五模块测试-作业
-6-0 引言
--6-0 视频
-6-1 线性相位FIR滤波器的条件与特点
--6-1 视频
-6-2 线性相位FIR滤波器的零点分布
--6-2 视频
-6-3 FIR数字滤波器的基本实现结构
--6-3 视频
-6-4 FIR数字滤波器的频率采样结构
--6-4 视频
-6-5 格型网络结构
--6-5视频
-6-6 窗函数法设计线性相位FIR滤波器的原理
--6-6 视频
-6-7 典型窗函数及其特性
--6-7 视频
-6-8 窗函数法设计线性相位FIR数字滤波器步骤
--6-8 视频
-6-9 频率采样法设计线性相位FIR滤波器
--6-9 视频
-6-10 频率采样法的逼近误差及其改进措施
--6-10 视频
-6-11 等波纹最佳逼近法设计FIR数字滤波器
--6-11 视频
-6-12 FIR数字滤波器的工程应用
--6-12 视频
-6-13 FIR滤波器和IIR滤波器比较
--6-13 视频
-第六模块测试题
--第六模块测试-作业
-实验一
--实验一 视频
--实验一指导书
-实验二
--实验二 视频
--实验二指导书
-实验三
--实验三指导书
--实验三视频
-实验四
--实验四指导
-模拟信号数字处理 学案
-DFT应用 学案
--DFT应用 学案
-课程拓展讨论
--模块一 讨论1
--模块一 讨论2
--模块二讨论1
--模块二讨论2
--模块三讨论1
--模块三讨论2
--模块四讨论1
--模块四讨论2
--模块五讨论1
--模块五讨论2
--模块五讨论3
--模块五讨论4
--模块六讨论1
--模块六讨论2
--模块六讨论3
--模块六讨论4
--模块六讨论5
-微课
--DFT
--梳状滤波器
-课后拓展内容
--采样与混叠实例
--离散时间调制
--FFT应用
--反馈实例
--吉布斯效应