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

快速傅里叶算法(FFT)快在哪里?

目录

前言

1、DFT算法 

2、FFT算法

2.1 分类

 2.2 以基2 DIT(时间抽取) FFT 算法为例

2.2.1 一次分解 

2.2.2 多次分解

 参考


前言

  对信号分析的过程中,为了能换一个角度观察问题,很多时候需要把时域信号波形变换到频域进行分析,这涉及到对信号求傅里叶变换,在计算机中便于处理的是离散信号,因此需要求信号的离散傅里叶变换,但是离散傅里叶变换(DFT--Discrete Fourier transform)的算法时间复杂度O(n2),为了能提高计算的速度,很多时候我们进行的变换为快速傅里叶变换(FFT--Fast Fourier Transform),其算法时间复杂度O(nlogn),大大提高了计算的速度,那么该快速傅里叶变换算法的快在哪里?中间进行了什么操作,我们下面具体分析。

在之前的一篇文章中我们提到了DFT和FFT的关系

频谱、功率谱、倒频谱_heda3的博客-CSDN博客_倒频谱

1、DFT算法 

DFT的数学计算表达式为:

长度为N的离散时间信号x(n),做N点离散傅里叶变换如下:

  X(k)=\sum_{n=0}^{N-1}x(n)e^{-j\frac{2\pi}{N}kn}=\sum_{n=0}^{N-1}x(n)W_{N}^{kn}

其中k=0,1,2,...N-1

其中W_{N}=e^{-j2\frac{ \pi }{N}}

运算量表述为:

依据上述公式可知,做1点DFT,需要N次复数乘法、N-1次复数加法

做N点DFT,则需要N*N次复数乘法、N*(N-1)次复数加法

当N为256点时,所需运算量65536次复数乘法、65280次复数加法

N=512点时,所需运算量262144次复数乘法、261632次复数加法

N=1024点时,所需运算量1048576次复数乘法、1047552次复数加法

可见当N点从256到1024点变化时,DFT算法的计算量从万级到百万级。

2、FFT算法

2.1 分类

分为按照时间抽取(在时间上将信号长度逐步减少)和按照频率抽取

依据抽取长度分为基2、基4

基2 DIT(时间抽取) FFT  也称为Cooley-Tukey algorithm 库利图基算法

基2 DIF(频率抽取) FFT

基4 FFT

分裂基FFT(包含两种不同基的混合计算)

 2.2 以基2 DIT(时间抽取) FFT 算法为例

基于基2时间抽取将信号划分为两部分分别计算FFT(信号长度N要求为N=2的整数倍):

X(k)=\sum_{n=0}^{N-1}x(n)W_{N}^{kn}=\sum_{n=0}^{N/2-1}x(2n)W_{N}^{k2n}+\sum_{n=0}^{N/2-1}x(2n+1)W_{N}^{k(2n+1)}                          1)

其中k=0,1,2,...N-1

复数运算的特性

W_{N}^{kn}=e^{-j2\frac{ \pi }{N}kn}

对称性: 

 W_{N}^{nk}=W_{N}^{-nk}=W_{N}^{(N-n)k}

周期性:

 W_{N}^{nk}=W_{N}^{(n+N)k}

可约性:

 W_{N}^{nk}=W_{mN}^{mnk} =W_{N/m}^{nk/m}

常见的计算 

W_{N}^{0}=1

W_{N}^{N/2}=-1

W_{N}^{N/4}=-j

2.2.1 一次分解 

依据上述复数运算的特性的可约性,则1)化简为:

X(k)=\sum_{n=0}^{N-1}x(n)W_{N}^{kn}=\sum_{n=0}^{N/2-1}x(2n)W_{N/2}^{kn}+W_{N}^{k}\sum_{n=0}^{N/2-1}x(2n+1)W_{N/2}^{kn}     2)

             X(k)=\sum_{n=0}^{N-1}x(n)W_{N}^{kn}=X_{0}(k)+W_{N}^{k}X_{1}(k)                                                  3)

              其中k=0,1,2,...N-1

利用特性:

W_{N}^{k+N/2}=W_{N}^{N/2}W_{N}^{k}=-W_{N}^{k}

则3)可表述为:

                            X(k)=X_{0}(k)+W_{N}^{k}X_{1}(k)                                                 4)

X(k+N/2)=X_{0}(k)-W_{N}^{k}X_{1}(k)                    

                               其中k=0,1,2,...N/2-1 

用如下的蝶形方式表述为3式和4式:

 两次复数运算:

 一次复数运算:

也即是N点DFT包含:2个 N/2点DFT和N/2个蝶形运算,一个蝶形运算包含一次复数乘法和两次复数加法

上述:做N点DFT,则需要N*N次复数乘法、N*(N-1)次复数加法

则2个N/2点DFT,则需要2*(N/2*N/2)=N^{^{2}}/2次复数乘法,2*(N/2)*(N/2-1)=N(N/2-1)次复数加法运算;蝶形运算次数:N/2次复数乘法,N次复数加法。

因此总的复数乘法计算:N(N+1)/2    总的复数加法次数:N^{^{2}}/2

通过上述的一次分解前后的运算量分析,可见经过一次分解后(信号按照奇偶数将N点DFT划分为N/2点DFT,并将两个N/2点DFT组合的方式),其运算量降低了一半,计算效率得到了提升。

2.2.2 多次分解

当N一直分解下去直到DFT的点数为2时,最小的计算单元为一个基本的蝶形运算,因此由于信号长度最初定义为N=2的整数倍,也即是N=2^{^{M}},因此N点DFT运算可以分解为M级蝶形运算,每一级为N/2个蝶形运算。

通过上述的FFT计算方法,则N点FFT运算需要M*N/2个蝶形运算,复数乘法次数:

N/2*M=N/2*log_{2}^{N}

复数加法次数:

   N/2*2*M=N*log_{2}^{N}

 

当N点从256到1024点变化时,FFT算法的计算量从千级到万级。可见FFT运算速度较DFT得到较大的提升。

    现在我们可以明显知道FFT到底快在哪里,因为经过对信号的逐级分解,将大点DFT划分为小点DFT计算,也即是N点FFT若基于基2抽取方法,则需要log_{2}^{N}级分解,N点DFT最终划分为2点DFT计算,并结合指数运算的特性,减少冗余计算,使得运算量大为减小。

 参考

【1】《数字信号处理》

【2】如何利用FFT(基2时间以及基2频率)信号流图求序列的DFT

 

相关文章:

快速傅里叶算法(FFT)快在哪里?

目录 前言 1、DFT算法 2、FFT算法 2.1 分类 2.2 以基2 DIT(时间抽取) FFT 算法为例 2.2.1 一次分解 2.2.2 多次分解 参考 前言 对信号分析的过程中,为了能换一个角度观察问题,很多时候需要把时域信号波形变换到频域进行分…...

利用Markdown写学术论文资料汇总贴

1是最详细的,重点看! Markdown 写作,Pandoc 转换:我的纯文本学术写作流程 2补充一些细节,也可以看看。 用Markdown写作学术论文 3写得和上面差不多,如果上面两篇有什么问题还没解决,可以看看…...

MySQL 高级查询

目录1.左关联2.右关联3.子查询4.联合查询5.分组查询1.左关联 MySQL中的左关联(Left Join)是一种基于共同列的连接操作, 它将左侧表中的所有行与右侧表中匹配的行结合在一起, 如果右侧表中没有匹配的行,则结果集中右侧…...

JavaSE学习day4_01 循环for,while,do...while

1. 循环高级 1.1 无限循环 for、while、do...while都有无限循环的写法。 最为常用的是while格式的。 因为无限循环是不知道循环次数的,所以用while格式的 代码示例: while(true){} 1.2 跳转控制语句(掌握) 跳转控制语句&…...

C/C++中的static关键字

概述在C/C中都有static关键字的使用,可以分别修饰变量和函数,分为静态变量【静态成员】、静态成员函数。2. static用法概况静态变量的作用范围在一个文件内,程序开始时分配空间,结束时释放空间,默认初始化为0&#xff…...

67 自注意力【动手学深度学习v2】

67 自注意力【动手学深度学习v2】 深度学习学习笔记 学习视频:https://www.bilibili.com/video/BV19o4y1m7mo/?spm_id_fromautoNext&vd_source75dce036dc8244310435eaf03de4e330 给定长为n 的序列,每个xi为长为d的向量,自注意力将xi 既当…...

电子学会2022年12月青少年软件编程(图形化)等级考试试卷(二级)答案解析

青少年软件编程(图形化)等级考试试卷(二级) 一、单选题(共25题,共50分) 1. 一个骰子,从3个不同角度看过去的点数如图所示,请问5的对面是什么点数?( ) …...

关于链表中插入结点的操作……

服了,好久没敲链表了,这都忘了 newnode->next cur->next; cur->next newnode; newnode->next cur->next; cur->next newnode; newnode->next cur->next; cur->next newnode; newnode->next cur->next; cur-…...

【项目精选】百货中心供应链管理系统

点击下载源码 近年来,随着计算机技术的发展,以及信息化时代下企业对效率的需求,计算机技术与通信技术已经被越来越多地应用到各行各业中去。百货中心作为物流产业链中重要的一环,为了应对新兴消费方式的冲击,从供货到销…...

Qt优秀开源项目之十六:SQLite数据库管理系统—SQLiteStudio

首先,感谢CSDN官方认可 SQLiteStudio是一款开源、跨平台(Windows、Linux和MacOS)的SQLite数据库管理系统。 github地址:https://github.com/pawelsalawa/sqlitestudio 官网:https://sqlitestudio.pl/ 特性很多&#xf…...

Python __doc__属性:查看文档

在使用 dir() 函数和 __all__ 变量的基础上,虽然我们能知晓指定模块(或包)中所有可用的成员(变量、函数和类),比如:import string print(string.__all__)程序执行结果为:[ascii_lett…...

电子科技大学操作系统期末复习笔记(一):操作系统概述

目录 前言 操作系统概述 操作系统的目标与功能 操作系统的定义 目标 功能 操作系统的历史 单用户系统 简单批处理系统 多道批处理系统 分时系统 个人电脑 → 分布式系统 → 互联网时代 → 移动计算时代 → ...... 实时系统 操作系统的基本特征 并发 共享 虚拟…...

[实践篇]13.20 Qnx进程管理slm学习笔记(三)

【QNX Hypervisor 2.2用户手册】目录(完结) 4.2 模块 我们可以将组件组合成一个模块。模块中的进程可以组成一个子系统,也可以用于建立一组系统状态,例如基本操作和各种更高级别操作。注意,必须命名模块,以便可以在内部引用它们。而且每个模块必须描述成一个元素,形势如…...

冰冰学习笔记:多线程

欢迎各位大佬光临本文章!!! 还请各位大佬提出宝贵的意见,如发现文章错误请联系冰冰,冰冰一定会虚心接受,及时改正。 本系列文章为冰冰学习编程的学习笔记,如果对您也有帮助,还请各位…...

补充一些前端面试题

javascript有哪些库指路>js中的库uniapp和vue有什么区别什么是uniappuni-app(uni,读you ni,是统一的意思)是一个使用Vue.js开发所有前端应用的框架,开发者编写一套代码,可发布到iOS、Android、Web&#…...

七大设计原则之单一职责原则应用

目录1 单一职责原则介绍2 单一职责原则应用1 单一职责原则介绍 单一职责(Simple Responsibility Pinciple,SRP)是指不要存在多于一个导致类变更的原因。假设我们有一个 Class 负责两个职责,一旦发生需求变更,修改其中…...

[USACO23JAN] Leaders B

题面翻译 题面描述 FJ 有 NNN 头奶牛,每一头奶牛的品种是根西岛 G 或荷斯坦 H 中的一种。 每一头奶牛都有一个名单,第 iii 头奶牛的名单上记录了从第 iii 头奶牛到第 EiE_iEi​ 头奶牛的所有奶牛。 每一种奶牛都有且仅有一位“领导者”,对…...

C++模板初阶

C模板初阶泛型编程函数模板概念函数模板格式函数模板原理函数模板的实例化模板参数的匹配原则类模板类模板的定义格式类模板的实例化泛型编程 我们前面学习了C的函数重载功能,那么我们如何实现一个通用的交换函数呢,比如:我传入int就是交换int&#xff…...

文献阅读:Scaling Instruction-Finetuned Language Models

文献阅读:Scaling Instruction-Finetuned Language Models 1. 文章简介2. 实验 1. 数据集 & 模型 1. 数据集考察2. 使用模型 2. scale up对模型效果的影响3. CoT对模型效果的影响4. 不同模型下Flan的影响5. 开放接口人工标注指标 3. 结论 文献链接:…...

gpt草稿

ChatgptWhatChatGPT(全名:Chat Generative Pre-trained Transformer [2])是由OpenAI开发的一个人工智能聊天机器人程序,于2022年11月推出。该程序使用基于GPT-3.5架构的大型语言模型并通过强化学习进行训练。ChatGPT里面有两个词&…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...