当前课程知识点:数字信号处理 > 四 利用FFT对离散信号与系统进行快速运算 > 4-2 减少DFT运算量的途径 > 4-2 视频
大家好
这节课我们学习
减少离散傅里叶变换运算量的途径
主要内容包括
减少运算量的两种途径
一个是利用
离散傅里叶变换运算系数的固有特性
另外一个是将长序列
分解为短序列的离散傅里叶变换
我们首先来看
离散傅里叶变换运算系数的固有特性
x(n)的离散傅里叶变换是X(k)
由公式(1)表示
系数WN的nk次方具有下面的特性
首先是系数的对称性
如公式(2)所示
其中WN等于e^(-j2π/N)
第二个是系数的周期性
由于WN的N次方是等于1的
所以把指数部分乘以一个k
或者乘以一个n结果还是等于1
把它们分别和系数WN的nk次方去相乘
就可以得到公式(3)和公式(4)
这两个公式说明
系数WN的nk次方是具有周期性的
并且周期是N
同理我们还可以得到公式(5)
第三个特性是系数的可约性
如公式(6)所示
我们以这个公式为例进行一下推导
把WrN等于e^(-j2π/rN)带到等号的左边来
然后进行化简
就可以得到WN的m次方
同样后面的两个公式
也可以用这种方法进行推导
这个系数还有一些特殊的值
WN的0次方等于1
WN的N/4次方等于-j
WN的N/2次方等于-1
比如说一个数和WN的0次方去相乘
是不需要复数乘法的
这样可以减少运算量
由WN的N/2次方等于-1
我们可以推导出公式(7)
WN的k+N/2次方
等于负的WN的k次方
利用这些性质
我们可以减少运算量
另一方面
由于离散傅里叶变换的运算量
是和序列长度N有关的
比如进行N点的离散傅里叶变换
需要的复数乘法次数是N的平方次
所以如果把长序列分解成短序列
就能够减少运算量
x(n)进行N点的离散傅里叶变换
它所需要的复数乘法运算量
是N的平方次
把N点的序列分成两个N/2点序列
x1(r)和x2(r) 它们分别去做
N/2点的离散傅里叶变换
所需要的复数乘法运算量
是N/4的平方加上N/4的平方
然后再把N/2点的序列
分成N/4点的序列
所需要的复数乘法运算量
是这几个值相加
继续分解 直到两点
我们从这个图里面可以看出
随着序列的不断分解
运算量是不断的下降
所以FFT算法就是不断的把长序列的
离散傅里叶变换
分解成短序列的离散傅里叶变换
并且利用系数的周期性
对称性 特殊值
来减少离散傅里叶变换的运算次数
对于N点的基2FFFT
它需要的复数乘法运算次数
是N/2乘以以2为底的N的对数
这个表里面列出了不同N值的离散傅里叶变换
和基2FFT所需要的复数乘法次数
从所列出的结果可以看出
FFT所需要的复数乘法次数
远远小于DFT所需要的复数乘法次数
这些就是减少运算量的途径
这节课的内容我们就学习到这里
再见
-课程简介
-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应用
--反馈实例
--吉布斯效应