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