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

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

4-3视频在线视频

下一节:4-4 视频

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

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

大家好

这节课我们学习时域抽取法基2FFT算法

主要内容包括

时域抽取法基2FFT定义

原理以及运算流图

我们首先看一下时域抽取法基2FFT定义

假设序列长度是N等于2的M次方

基数是2 所以叫基2

M是正整数

把序列x(n)按照n的奇偶分解成子序列

就称为时域抽取法基2FFT

也就是DIT-FFT

也叫做库利图基算法

如果N不等于2的M次方

可以进行补0

使序列达到这个长度

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

序列x(n)的离散傅里叶变换是X(k)

k从0到大N-1 如公式(1)所示

把序列x(n)按照n的奇偶分成两组

形成两个子序列

n是偶数的时候 设n等于2r

n是奇数的时候 设n等于2r+1

其中r等于0到N/2-1

这样形成了两个子序列x1(r)和x2(r)

分别对这两个子序列进行

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

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

我们来分析一下

X(k)和X1(k) X2(k)的关系

因为我们要按照n的奇偶对x(n)进行分解

所以离散傅里叶变换的公式

就分解成两部分

一部分n是偶数

另外一部分n是奇数

n是偶数 令n等于2r

n是奇数 令n等于2r+1

对于这个系数

它可以写成两项的乘积

一项是WN的k次方

一项是WN的2rk次方

由系数的可约性

我们可以得到这个公式

前面这一项

是x1(r)的N/2点离散傅里叶变换X1(k)

后面这一项是WN的k次方乘以

x2(r)的N/2点离散傅里叶变换X2(k)

k是从0到N/2-1

这样我们就得到了x(k)的前一半值

也就是k等于0到N/2-1的时候对应的值

那么后一半的数据呢

k+N/2对应的就是N/2到N-1这一部分

那么也就能得到X(k)的后一半的值了

所以我们把k加N/2带到公式(2)里面来

得到公式(3)

在公式(3)中

这个系数在上一讲中

我们已经推导出来了

它是等于负的WN的k次方

那么X1(k+N/2)等于什么呢

把k+N/2代入到

X1(r)的N/2点离散傅里叶变换式当中

这一部分分成两部分的乘积

那么乘积的后一项

它是等于1的

把化简的结果再代回到公式里面来

我们就可以看到

正好是x1(r)的离散傅里叶变换

同理

我们可以得到X2(k+N/2)等于X2(k)

把这几个值代入到公式(3)中

就可以得到X(k)的后一半的数据值

是由公式(4)所描述的

所以如果求出来了

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

X1(k)和X2(k)

那么就可以由公式(2)和公式(4)

求出X(k)的前半部分和它的后半部分

同理可以把N/2点的离散傅里叶变换

继续分解

分解成N/4点的离散傅里叶变换

依此类推

直到两点的离散傅里叶变换

那么公式(2)和公式(4)所描述的关系

可以用蝶形运算来表示

这个是蝶形运算符号

左边是输入

C表示支路系数

右边是输出

向上的支路是相加

也就是A+CB

向下的支路是相减

也就是A-CB

那么这两个公式

我们用蝶形运算符号来表示的话

就是输入是X1(k)和X2(k)

支路系数是WN的k次方

输出就是

X(k)的前一半数据和后一半数据

下面我们以N等于8为例

对完整的过程进行一下介绍

首先把8点的序列分解成两个N/2点的序列

也就是n等于偶数的时候

形成的序列是x1(r)

n等于奇数的时候

形成一个子序列是x2(r)

在频域上X(k)的值是

由公式(2)和公式(4)所求出来的

也就是说

它要分成前一半的数据和后一半的数据

这样的话

X(0)到X(3)是由公式(2)给出的

X(4)到X(7)是由公式(4)给出来的

我们把它画成运算流图的形式

x(n)先分成两个子序列

x1(r)和x2(r)

它们分别去进行4点的离散傅里叶变换

得到X1(k)和X2(k)

然后经过一级蝶形

就可以得到X(k)的前一部分值

和X(k)的后一部分值

比如说X(0)

它是等于X1(0)加上X2(0)乘以W8的0次方

这个蝶形的另外一个输出是X(4)

它等于X1(0)减去X2(0)乘以W8的0次方

所以它们两个是一个蝶型的输出

其它的点也是一样的

然后再把N/2点的子序列

按照r的奇偶来分解成N/4点的子序列

也就是把x1(r)和x2(r)

按照r的奇偶来进行分解

这样形成了4个N/4点的子系列

x3(l)到x6(l)

l是等于0到N/4-1

我们以8点的序列为例

来再看一下这个过程

第一次分解是把n为偶数的点

作为一个序列x1(r)

把n为奇数的点

作为另外一个序列x2(r)

第二次分解是把x1(r)

r的偶数点形成一个序列

奇数点形成一个序列

同样x2也是这样

这样就形成了4个两点的序列

分别对应着x3(l)到x6(l)

对x3(l)和x4(l)进行两点的离散傅里叶变换

得到X3(k)和X4(k)

再经过一级蝶形就得到了X1(k)

同理也可以得到X2(k)

那么两点的离散傅里叶变换

也是一级蝶形

x3(l)的两点离散傅里叶变换是X3(k)

把这个求和号展开

就可以得到蝶形运算的这种形式

左边的这个图

就是两点的蝶形运算流图

下面我们把刚才的过程总结一下

首先把x(n)按照n的奇偶分成两个子序列

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

得到的结果进行一级蝶形运算

得到输出

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

继续分解

分解成N/4点的离散傅里叶变换

由于x1(r)和x2(r)

又分别按照r的奇偶进行了抽取

所以N/4点的离散傅里叶变换

它的输入顺序就变成了

x(0) x(4) x(2) x(6)

然后分别去进行N/4点离散傅里叶变换

如果它还是2的整次幂

可以继续进行分解

因为这里N等于8

所以这个N/4点离散傅里叶变换

就是两点的了

那么两点的离散傅里叶变换

也是一级蝶形

这样得到了完整的

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

其中W8的0次方

W8的1次方

这些叫做旋转因子

因为8是2的3次方

所以它一共是分解成了三级

这个就是时域抽取法基2-FFT原理

和它的运算流图

下面我们来举一个例子

利用时域抽取法基2-FFT求X(k)

在实际当中

输入它是按照自然顺序排列的

也就是x(0) x(1) x(2) x(3)

但是FFT它的输入不是自然顺序

是因为n按照奇偶不断的进行了抽取

得到这样一个顺序

这个顺序叫做倒序

所以我们要把这个自然顺序变成倒序

才能够进行FFT的运算

因此我们进行一个变址运算

变成倒序

这个输入经过一级蝶形运算

我们看它得到什么值

这一点的值应该是

x(0)加上x(2)乘以W4的0次方

所以它等于4

蝶形运算向上是相加 向下是相减

所以这一点的值是-2

同理我们可以得到

下面这两个点的值是6和-2

然后这些值再进行第二级蝶形运算

就可以得到X(k)的值

X(0)是等于10

X(2)等于-2

X(1)是等于-2+2j

X(3)是等于-2-2j

那么由这个结果我们也可以验证

在DFT模块中学习的性质

如果输入是实序列

那么它的离散傅里叶变换

应该是共轭对称的

X(1)和X(3)这两个值是共轭的

另外对于没有对称点的这两个点

一个是k等于0

一个是k等于N/2

k等于0的时候

它应该是序列的所有值之和

对于k等于N/2这一点

因为在这里面N是等于4

所以N/2是等于2

所以X(2)这一点

它的值应该是序列的值

加一项 减一项 加一项 减一项

所以它等于-2

和我们进行离散傅里叶变换的结果

是一样的

这些就是时域抽取法基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-3视频笔记与讨论

也许你还感兴趣的课程:

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