当前课程知识点:数字信号处理 > 四 利用FFT对离散信号与系统进行快速运算 > 4-1 采用快速傅里叶变换的原因 > 4-1 视频
大家好
这节课我们分析
为什么要采用快速傅里叶变换
主要内容包括
直接计算DFT的运算量
DFT和FFT运算时间比较
离散傅里叶变换由于计算量很大
不适于实时应用
那么它的运算量到底有多大呢
下面我们来分析一下
直接计算DFT的运算量
假设有限长序列x(n)
非零值长度为N
利用这个公式计算其N点离散傅里叶变换
k从0到N-1
也就是需要计算X(k)的N个值
我们以计算的复数运算量为例
先来看计算X(k)的一个值的时候
所需要的运算量
例如当k=1时
把k=1代到离散傅里叶变换式中
得到X(1)等于∑(x(n)乘以WN^n)
把求和号展开
可以看出每一项需要一次复数乘法
这样就需要N次复数乘法
然后再相加 需要N-1次复数加法
其它点的计算也是一样的
而X(k)有N个值
所以计算所有值
就需要N的平方次复数乘法
和N乘以N-1次复数加法
当N的值比较大的时候
复数加法也近似N的平方次
例如N等于512
它的平方是26万多
N等于1024
那么它的平方是100多万次
所以可以看出运算量确实很大
下面我们比较一下DFT和FFT的运算时间
设序列xn等于n+1乘以1个N点的矩形序列
所以序列的长度是N
对它进行N点的离散傅里叶变换
和快速傅里叶变换
当然也可以采用其它的序列
我们通过MATLAB程序的结果来进行比较
在程序中用这几条语句来定义x(n)
更改这个N值
就可以得到其它点数的计算时间
比如把256改成512 1024等等
tic toc 是计时函数
它可以计算在这两条语句之间的
这个程序执行的时间
因为序列长度和计算点数相等
所以FFT函数中的N也可以省略
在DFT函数中
是按照矩阵相乘的方法来进行实现的
也就是先形成这个系数矩阵
然后用x(n)和系数矩阵相乘得到X(k)
这个表格列出了不同点数的运算时间结果
从这些结果可以看出
DFT所需要的时间
远远大于FFT所需要的时间
并且计算点数越多
相差的时间就越大
在前面的程序中
要计算不同点数的运算时间
需要更改N的值
如果我们希望在一个程序中
能够计算出这个表中所有点数的运算时间
可以采用for循环
每次循环生成一个N值
然后进行计算
比如在这个表中
点数是从256到4096
在这个循环中i等于1的时候
对应着N是等于256
i等于5的时候
对应的N是4096
运行这个程序就可以得到不同点数的
DFT和FFT的运算时间
这节课我们分析了为什么要采用
快速傅里叶变换
以及DFT和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应用
--反馈实例
--吉布斯效应