当前课程知识点:数字信号处理 >  四 利用FFT对离散信号与系统进行快速运算 >  4-4 频域抽取法基2FFT >  4-4 视频

返回《数字信号处理》慕课在线视频课程列表

4-4 视频在线视频

下一节:4-5视频

返回《数字信号处理》慕课在线视频列表

4-4 视频课程教案、知识点、字幕

大家好

这节课我们学习

频域抽取法基2-FFT算法

主要内容包括

频域抽取法基2-FFT定义

原理以及运算流图

我们首先看频域抽取法基2FFT定义

和时域抽取法基2FFT一样

序列的长度也是2的整次幂

把序列的离散傅里叶变换X(k)

按照k的奇偶分解成子序列

就是频域抽取法基2-FFT

也就是DIF-FFT

这种算法也称作Sander-Tukey算法

下面我们来看频域抽取法基2-FFT原理

x(n)的离散傅里叶变换

如公式(1)所示

在频域X(k)按照k的奇偶来分解

那么在时域上

x(n)不能够按n的奇偶来分解了

在时域上是按照n的顺序

分成前后两部分

也就是把x(n)分成前一半子序列

和后一半子序列

例如n等于8的时候

x(0)到x(3)是前一半子序列

x(4)到x(7)是后一半子序列

把前一半子序列和后一半子序列相加

形成一个序列x1(n)

前一半子序列和后一半子序列相减

乘以一个系数

形成一个序列x2(n)

分别对它们进行

N/2点的离散傅里叶变换

得到X1(r)和X2(r)

分别对应

X(k)在偶数点上的值和奇数点上的值

公式(2)和公式(3)也是蝶形运算

输入就是序列的前一半值和后一半值

输出是它们

分别去相加和相减乘以一个系数

我们来看一下

基2DIF-FFT运算流图的画法

还是以N等于8为例

首先把8点的序列分成两个4点的序列

也就是把N点的序列分成

两个N/2点的序列

在时域上x(0)到x(3)是序列的前一半值

x(4)到x(7)是后一半值

利用公式(2)和公式(3)

产生新的子序列x1(n)和x2(n)

然后分别去做N/2点的离散傅里叶变换

就可以得到

频域上X(k)偶数点的值和奇数点的值

那我们来看一下

频域抽取法基2-FFT算法的推导过程

对x(n)进行N点的离散傅里叶变换

我们把x(n)分成前后两个部分

n从0到N/2-1是前半部分

从N/2到N-1是后半部分

对于第二项n不是从0开始的

所以我们要做一个变量代换

令n等于n'+N/2

为了和前面这一项的变量统一

把n'再换成n

那么现在求和的范围

都是从0到N/2减1了

所以把这两项合到一起

对于这个系数

可以把它写成两项相乘的形式

然后把WN的nk次方

提到中括号的外面来

因为WN的N/2次方是等于-1的

所以这一项等于-1的k次方

这样X(k)就可以写成公式(4)这种形式

同学们注意

现在X(k)还没有按照

k的奇偶来进行分解

k的取值还是从0到N-1

下面我们把X(k)按照

k的奇偶来进行分解

当k是偶数的时候

令k等于2r

把k等于2r代到公式(4)中

-1的k次方是等于1的

得到这个公式

然后利用系数的可约性

得到下面这个公式

令中括号里面的这个序列是x1(n)

也就是序列x(n)的

前一半数据加上后一半数据

而这个求和公式

就是x1(n)的N/2点

离散傅里叶变换X1(r)

所以X1(r)是X(k)在偶数点上的值

同理当k是奇数的时候

令k等于2r+1

那么-1的k次方就等于-1

我们也可以得到序列x2(n)

以及x2(n)的离散傅里叶变换X2(r)

也就是x1(n)是序列的前一半数据

和后一半数据相加

序列x2(n)是前一半数据

和后一半数据相减再乘以一个系数

它们分别去做离散傅里叶变换

就可以得到X(k)的偶数点上的值

和奇数点上的值

那么由序列x(n)

构成x1(n)和x2(n)的这个过程

也是一个蝶形运算

例如x1(0)它是x(0)加上x(4)

x2(0)是这个蝶形的另外一个输出

就是x(0)减x(4)乘以W8的0次方

有了x1(n)和x2(n)

分别去做4点的离散傅里叶变换

就可以得到X1(k)和X2(k)

也就是X(k)的偶数点上的值

和奇数点上的值

然后再将N/2点的序列

分解成N/4点的序列

也就是把4点的序列分成2点的序列

对x1(n)和x2(n)分别分成

前半部分序列和后半部分序列

然后相加或者是相减

再乘系数

形成4个新的子序列x3(l)到x6(l)

在这里l是0和1

例如x1(n)分成

前一半子序列和后一半子序列

经过一级蝶形可以得到x3(l)和x4(l)

分别对它们进行

两点的离散傅里叶变换

就可以得到X3(k)和X4(k)

而X3(k)是X1(k)的偶数点上的值

X4(k)是X1(k)的奇数点上的值

同理由x2(n)也可以得到X2(k)

前一半的值和后一半的值

两点的离散傅里叶变换

也是可以用一个蝶形来表示的

这样就可以得到

频域抽取法基2-FFT完整的运算流图

在这个运算流图中

输入是自然顺序

输出是倒序

也就是按照频域变量的奇偶

不断的进行分解得到的

因为8是2的3次方

所以它也是有三级蝶形运算

W8的0次方到W8的3次方

和DIT-FFT一样

也是旋转因子

那么在时域抽取法当中

输入是倒序

输出是自然顺序

先是小的蝶形

然后是大的蝶形

在频域抽取法当中

正好是反过来的

那么时域抽取法运算流图

和频域抽取法运算流图

它们是互为转置的关系

如果把这个流图的所有支路方向都反向

并且把输入输出进行交换

也就是这边如果是输入

这边是输出的话

就可以得到

时域抽取法基2-FFT运算流图

所以这两种流图是互为转置的

最后我们再举一个例子

利用频率抽取法基2-FFT

求x(n)的离散傅里叶变换X(k)

对于频域抽取法

它的输入是自然顺序

所以不用再进行变址运算了

首先把输入经过第一级蝶形运算

我们看第一级蝶形的输出

对于这个黑色的蝶形

这一点的输出应该是x(0)加上x(2)

下面这一点的输出

应该是x(0)减x(2)乘以W4^0

另外一个蝶形的输出

也是按照相同的方式得出

然后第一级蝶形的输出

作为第二级蝶形的输入

再进行计算

就可以得到X(k)的偶数点上的值

和奇数点上的值

而这个4呢 是x(0)加x(2)

6是x(1)加x(3)

所以X(k)在k等于0这一点的值

是序列的所有值之和

k等于2的时候这个值

就是4减6乘以1

所以它等于-2

由下面这个蝶形

可以求出k等于1和k等于3的时候这个值

它们两个是共轭的

但是这个值不能直接输出

因为它是倒序

所以还要进行一个变址运算

把它变成自然顺序输出

这些就是

频域抽取法基2-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 视频

-第二模块测试题

--第二模块测试题-作业

三 时域离散信号与系统DFT分析

-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 视频

-第三模块测试题

--第三模块测试-作业

四 利用FFT对离散信号与系统进行快速运算

-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 视频

-第四模块测试题

--第四模块测试-作业

五 IIR数字滤波器设计及实现结构

-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视频

-第五模块测试题

--第五模块测试-作业

六 FIR数字滤波器设计及实现结构

-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

--巴特沃斯滤波器设计

--窗函数设计法设计FIR滤波器及仿真分析

--梳状滤波器

-课后拓展内容

--离散时间LTI系统响应求解

--采样与混叠实例

--离散时间调制

--离散傅里叶变换应用MATLAB

--FFT应用

--模拟到数字滤波器映射

--反馈实例

--FIR滤波器设计思想及方法

--吉布斯效应

--用线性代数计算数字滤波器系统函数

--数字滤波器指标及设计方法FDA

--其他种类的特殊滤波器及应用

4-4 视频笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。