当前课程知识点:数字信号处理 > 四 利用FFT对离散信号与系统进行快速运算 > 4-3 时域抽取法基2FFT > 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 视频
-第二模块测试题
--第二模块测试题-作业
-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应用
--反馈实例
--吉布斯效应