当前位置: 首页 > news >正文

matlab求kcf算法响应图_1周学FFT——第5天 时间抽选奇偶分解基-2 FFT算法

4b1e4a22eb46b7182926f8003c004cc0.png

时间抽选奇偶分解基-2 FFT算法名字很长,其内容包括三部分内容

  1. 时间抽选(Decimation-in-time,DIT)是指在时域内将序列
    进行分解;
  2. 奇偶分解是指按照n的取值将
    分为奇偶两组,目的是将计算1个N点的DFT转化为计算2个
    点的DFT;
  3. 基-2(radix-2)是指
    ,M为自然数,比如
    就是符合基-2条件的。目的是可以一直进行奇偶分解直到将N点DFT分解为一堆2点DFT。

在不致混淆的时候,时间抽选奇偶分解基-2 FFT算法可简称为基-2 FFT算法。由于基-2可以最大限度的减少乘法运算次数,所以实际当中如果点数不满足基-2条件,可以人为在

中填补零点凑
基-2

以下为算法的推导过程: 序列

的DFT序列为:

,则n取偶数时可写作
,n取奇数时可写作
,按照奇偶将上式分为两组:

根据周期性2

,所以式(1)又可以写作:

则根据定义,

都是
点DFT。于是,将式(3)、(4)带入式(2)可得:

式(5)表示

可分解为两个折半点数的DFT
的和。由于
,因此上式只能表示
点的
。对于
的另一半,可以利用DFT隐含的周期性得到。因为
是周期为
的周期序列,所以:

所以将

代入式(5)得:

将式(5)、(6)合并可得

的完整表达式:

式(3)、(4)、(7)就是基-2FFT算法的核心

例子:

利用基-2 FFT算法求序列x(n)的N=4的DFT。

知乎对多行公式的支持简直一言难尽,没办法只能在其他地方再贴一遍:

1周学FFT——第5天 时间抽选奇偶分解基-2 FFT算法​www.jianshu.com
dff28ba418b631bbae31507d44f08d99.png

另外,通过观察可以发现,计算

各点、
各点和
各点的结构是完全一致的,这种结构被称为
蝶形运算(butterfly operation)

比如计算

的算式可以绘制为如下所示的蝶形运算:

8d3b86ba37d3a4c3ceb6fb10e7d9e8b1.png
计算$X_1(0)$和$X_1(1)$的蝶形运算示意图

再如计算

的算式可以绘制为如下所示的蝶形运算:

4b89c8dcf30e6be3a08cad6defff4966.png
计算$X(0)$和$X(2)$的蝶形运算示意图

将N=4的基-2FFT算法全部的蝶形运算画在一起如下图所示:

63e91fa638081a1c25686fddc22b103c.png
N=4时蝶形运算全貌

一次标准的蝶形运算包含1次复数乘法和2次复数加法(或1次复数乘加和1次复数加法)。如上图所示,N=4的DFT需要4次蝶形运算,共计4次复数乘法,远少于传统DFT的16次复数乘法。更进一步,经过更一般的推导可知,基-2 FFT算法的时间复杂度为

,当N=1024时,基-2 FFT算法比传统算法快64倍。

习题

  1. 根据基-2 FFT算法求序列x(n)的8点DFT,并画出蝶形流程图;
  2. 设计matlab程序,实现基-2 FFT算法。

相关文章:

  • xlwt追加写入_python3中关于excel追加写入格式被覆盖问题(实例代码)
  • 地图上的标签为图片_三种方式制作数据地图
  • arcengine 将一个shp的数据读取到另一个shp_从零开始,构建电子地图网站:0_3_数据处理python(1)...
  • python极简主义_极简主义的践行者:一行python有哪些玩法?
  • idea中maven找不到本地仓库jar包_Mac Intellij Maven使用本地仓库的jar包
  • mysql默认安装目录 linux_关于Linux安装mysql默认配置文件位置详解
  • jquery mysql实现加入购物车_jquery-实现加入购物车效果
  • mysql 查询最近7天 时间戳数据_mysql查询今天、昨天、7天、近30天、本月数据
  • 景安mysql主机_景安国内虚拟主机空间如何创建数据库
  • mysql新手问题大全_初学者必读:MySQL数据库常见问题汇总
  • qopenglwidget 拖动窗口时图形消失_CAD画图时鼠标原来是这么用的!
  • mysql root 赋权_mysql 里对root及普通用户赋权及更改密码的一些命令
  • freebsd linux mysql_怎样在linux或unix服务器上安装、使用MySQL
  • mysql eav_检索MySQL EAV结果作为关系表的最佳性能是什么
  • mysql与后台乱码问题_MySQL+PHP[utf-8]乱码原因与解决方法
  • 《微软的软件测试之道》成书始末、出版宣告、补充致谢名单及相关信息
  • 【MySQL经典案例分析】 Waiting for table metadata lock
  • 【RocksDB】TransactionDB源码分析
  • angular2开源库收集
  • ES学习笔记(10)--ES6中的函数和数组补漏
  • input实现文字超出省略号功能
  • iOS 系统授权开发
  • Java Agent 学习笔记
  • Java反射-动态类加载和重新加载
  • Just for fun——迅速写完快速排序
  • MYSQL 的 IF 函数
  • orm2 中文文档 3.1 模型属性
  • Redis字符串类型内部编码剖析
  • Spark in action on Kubernetes - Playground搭建与架构浅析
  • Spring Cloud(3) - 服务治理: Spring Cloud Eureka
  • Work@Alibaba 阿里巴巴的企业应用构建之路
  • 服务器从安装到部署全过程(二)
  • 使用Tinker来调试Laravel应用程序的数据以及使用Tinker一些总结
  • [地铁译]使用SSD缓存应用数据——Moneta项目: 低成本优化的下一代EVCache ...
  • ​​快速排序(四)——挖坑法,前后指针法与非递归
  • ​configparser --- 配置文件解析器​
  • # 手柄编程_北通阿修罗3动手评:一款兼具功能、操控性的电竞手柄
  • $HTTP_POST_VARS['']和$_POST['']的区别
  • (3)STL算法之搜索
  • (floyd+补集) poj 3275
  • (Git) gitignore基础使用
  • (ResultSet.TYPE_SCROLL_INSENSITIVE,ResultSet.CONCUR_READ_ONLY)讲解
  • (附源码)springboot宠物医疗服务网站 毕业设计688413
  • (附源码)计算机毕业设计ssm高校《大学语文》课程作业在线管理系统
  • (详细版)Vary: Scaling up the Vision Vocabulary for Large Vision-Language Models
  • (转)memcache、redis缓存
  • ****Linux下Mysql的安装和配置
  • ./include/caffe/util/cudnn.hpp: In function ‘const char* cudnnGetErrorString(cudnnStatus_t)’: ./incl
  • .CSS-hover 的解释
  • .java 指数平滑_转载:二次指数平滑法求预测值的Java代码
  • .Net Core webapi RestFul 统一接口数据返回格式
  • .net core 微服务_.NET Core 3.0中用 Code-First 方式创建 gRPC 服务与客户端
  • .net 中viewstate的原理和使用
  • .net和jar包windows服务部署
  • .NET设计模式(2):单件模式(Singleton Pattern)