当前课程知识点:数字信号处理 > 四 利用FFT对离散信号与系统进行快速运算 > 4-6 进一步减少运算量的措施 > 4-6 视频
大家好
这节课我们学习
进一步减少运算量的措施
主要内容包括
多类蝶形单元运算
旋转因子的生成
以及实序列的FFT算法
我们首先看一下
基2DIT-FFT算法运算流图
在FFT运算中
每个蝶形都有一个旋转因子
有一些旋转因子的值比较特殊
不需要进行乘法运算
例如W8的0次方等于1
也就是WN的0次方等于1
任何数和1相乘都等于它本身
所以不需要乘法
再有W8的2次方等于-j
也就是WN的N/4次方等于-j
一个复数a+jb和-j相乘等于b-aj
所以也不需要乘法运算
这样的旋转因子叫做
无关紧要的旋转因子
那么去除无关紧要的旋转因子
就可以减少运算量
在DIT-FFT当中
第一级和第二级当中的
所有的旋转因子
都是无关紧要的旋转因子
不需要乘法运算
在第三级以后
也包含了这两个旋转因子
在第一 二级中
每级都有N/2个蝶形
所以原来是需要N/2次复数乘法
基2FFT
它所需要的复数乘法次数是MN/2
那么从这里面去除掉
第一 二级的复数乘法次数
剩下的复数乘法次数就由公式(1)所描述
对于DIF-FFT
它和DIT-FFT是相反的
所以最后两级中的旋转因子
都是无关紧要的旋转因子
在DIT-FFT中
当L大于等于3的时候
也就是第三级以后
每级都有两个无关紧要的旋转因子
而每级当中每一个旋转因子都对应着
N除以2的L次方个蝶形运算
那么第L级它减少的复数乘法次数
就是2N除以2的L次方
这样从第三级到第M级
减少的复数乘法次数
就是2N除以2的L次方求和
利用等比级数求和
我们可以算出
从第三级到第M级
减少的复数乘法次数是N/2-2
把刚才(1)式中的
复数乘法次数 再减去
从第三级到第M级的复数乘法次数
就是去除了无关紧要的旋转因子
以后所剩的这个乘法次数
另外
还可以利用特殊的复数运算
来减少运算量
实现一次复数乘法
需要四次实数乘法和两次实数加法
但是有些特殊的复数
和其它复数相乘的时候
所需要的实数运算会少一些
比如WN的N/8次方
这个数和其它的复数相乘
只需要两次实数乘法和两次实数加法
在进行程序实现的时候
如果包含了所有的旋转因子
就叫做一类蝶形单元运算
去除掉等于正负1的旋转因子
就是二类蝶形单元运算
去除掉等于正负j的旋转因子
就是三类蝶形单元运算
再处理特殊的这个旋转因子
那么就是四类蝶形单元运算
很明显
蝶形单元类型越多
所需要的运算量就会越少
但是编程肯定是越来越复杂了
第二个就是旋转因子的生成
一种方法是在进行每级的运算的时候
直接产生旋转因子
所以计算速度慢
另外一种方法就是预先计算出旋转因子
形成旋转因子表
在进行FFT的时候进行查表
这种方法计算速度快
但是因为要事先形成一个旋转因子表
所以占用内存多
在实际当中
一般都是实序列
如果直接对它进行FFT
可以把实序列看成是
虚部为零的复序列
但是这样的话就会浪费运算量
浪费计算时间
那么有两种情况
一种情况就是有两个实序列
需要进行离散傅里叶变换
我们只想用一次N点的FFT来完成
这种情况我们在第三个模块里面
已经学习过了解决办法了
因为这两个序列都是实序列
所以可以把它们两个合成一个复序列
其中一个实序列作为实部
另外一个实序列作为虚部
形成一个新的序列
也是N点的序列x(n)
对x(n)进行N点的离散傅里叶变换
得到X(k)
那么X(k)
可以分解成有限长共轭对称分量
和有限长共轭反对称分量
根据离散傅里叶变换的共轭对称性
序列x1(n)
它的离散傅里叶变换
应该是
序列离散傅里叶变换的
有限长共轭对称部分Xep(k)
序列的虚部乘以j
也就是jx2(n)
它的离散傅里叶变换是jX2(k)
应该是X(k)的有限长共轭反对称部分
也就是Xop(k)
等式两边同时除以j
就可以得到X2(k)
等于1/j乘以Xop(k)
这样我们就用一次N点的FFT
计算了两个N点实序列的
离散傅里叶变换X1(k)和X2(k)
由X(k)计算X1(k)和X2(k)的公式
如公式(3)和公式(4)所示
另外一种情况是只有一个实序列
假设这个实序列是2N点
现在我们需要用一次N点的FFT
来进行计算它的离散傅里叶变换
如果计算N点的FFT
那么序列的长度应该是N
而现在的序列是2N点
所以我们可以借鉴DIT-FFT算法
将一个2N点的实序列
分解成两个N点的实序列
也就是y(n)的偶数点组成一个序列
y(n)的奇数点组成一个序列
x1(r)和x2(r)都是N点的序列
对它们进行离散傅里叶变换
可以得到X1(k)和X2(k)
然后再经过一级蝶形运算
就可以得到Y(k)的前一半的值
和后一半值
现在是有两个N点的实序列
我们需要用一次N点FFT来进行计算
就是前面的第一种情况
用一次N点FFT
来计算两个N点的实序列的
离散傅里叶变换
下面我们来看一下具体的步骤
首先对y(n)进行分解
形成两个实序列
然后把这两个实序列
组合成一个复序列
再进行N点的离散傅里叶变换
得到X(k)
根据前面一种情况
我们已经推导出来的结果
就是x1(r)的离散傅里叶变换
X1(k)是Xep(k)
x2(r)的离散傅里叶变换X2(k)
是等于(1/j)Xop(k)
就是公式(3)和公式(4)
有了X1(k)和X2(k)
再用蝶形运算公式就可以求出
Y(k)的前一半值和后一半值
也就是公式(5)
这样我们就得到了一个
2N点的离散傅里叶变换Y(k)
那么Y(k)的后一半数据
还有一种方法可以进行计算
就是先利用蝶形运算求出Y(k)的
前一半数据
因为2N点的序列y(n)是实序列
所以它的离散傅里叶变换
应该是共轭对称的
所以可以利用这个性质
求出Y(k)的后一半的数据
这些就是减少运算量的措施
第四模块的内容到这节课我们就完成了
下面我们来总结一下
在这个模块中
首先分析了
采用快速傅里叶变换的原因
是因为
离散傅里叶变换的运算量太大了
不利于信号与系统的实时处理
因此需要减少运算量
那么减少运算量的途径
是利用系数的固有特性
以及将长序列分解成短序列来进行计算
然后我们学习了时域抽取法
和频域抽取法
基2FFT算法原理以及运算流图
在DIT-FFT中
是按照时域变量的奇偶
不断的对时域序列进行分解
直至两点
形成蝶形运算
在DIF-FFT中
是按照频域变量的奇偶进行分解
也是形成了蝶形运算
在此基础上
我们分析了基2FFT算法的运算量
以及运算规律
对两种算法进行了比较
学习了IDFT的高效算法
以及进一步减小运算量的措施
FFT是DFT的快速算法
在实际应用当中
当需要用到DFT的时候
例如对信号的谱分析
计算LTI系统的输出
进行FIR滤波器的设计
都可以采用FFT来进行实现
这节课的内容我们就学习到这里
再见
-课程简介
-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应用
--反馈实例
--吉布斯效应