0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

一文快速教会你傅立叶算法

硬件攻城狮 来源:嵌入式客栈 2023-02-08 10:01 次阅读

[导读]今天来聊聊如何实现快速傅立叶变换FFT及其应用,希望大家喜欢。直接谈FFT,可能没这方面基础的同学,不太能明白,先看看它的相近较容易理解的几个概念吧。

啥是傅立叶级数?

在数学中,傅里叶级数(Fourier series)是把类似波的函数表示成简单正弦波的方式。更正式地说法是,它能将任何周期性函数或周期信号分解成一个(可能由无穷个元素组成的)简单振荡函数的集合,即正弦函数和余弦函数(或者,等价地使用复指数),从数学的定义来看,是这样地:

设x(t)是一周期信号,其周期为T。若x(t)在一个周期的能量是有限的,有即

则,可以将x(t)展开为傅立叶级数。怎么展开呢?计算如下:

公式中的k表示第k次谐波,这是个什么概念呢?不容易理解,看下对于一个方波的前4次谐波合成动图就比较好理解了。这里的合成的概念是时域上的叠加的概念,图片来源wikipedia

c64c59a0-a6f8-11ed-bfe3-dac502259ad0.gif

c67a06ca-a6f8-11ed-bfe3-dac502259ad0.png

啥是傅里叶变换?

在数学中,傅里叶变换(Fourier transform FT)是一种数学变换,它将一个函数(通常是一个时间的函数,或一个信号)分解成它的组成频率,例如用组成音符的音量和频率表示一个音乐和弦。傅里叶变换指的是频域表示和将频域表示与时间函数相关联的数学运算。其本质是一种线性积分变换,用于信号在时域(或空域)和频域之间的变换,在物理学和工程学中有许多应用。因其基本思想首先由法国学者约瑟夫·傅里叶系统地提出,所以以其名字来命名以示纪念。实际上傅里叶变换就像化学分析,确定物质的基本成分;信号来自自然界,也可对其进行分析,确定其基本频率成分。其数学定义为:

对于连续时间信号x(t),若x(t)在时间维度上可积分,(实际上并不一定是时间t维度,这里可以是任意维度,只需在对应维度空间可积分即可),即:

那么,x(t)的傅立叶变换存在,且其计算式为:

c68d0f72-a6f8-11ed-bfe3-dac502259ad0.png

其反变换为:

c6a32ffa-a6f8-11ed-bfe3-dac502259ad0.png

上面这两个公式是啥意思呢?在度量空间可积可以理解成其在度量空间能量有限,也即对其自变量积分(相当于求面积)是一个确定值,那么这样的函数或者信号就可以进行傅立叶变换展开,展开得到的就变成是频域的函数了,如果对频率将函数值绘制出曲线就是我们所说的频谱图,而其反变换就比较好理解了,如果我们知道一个信号或者函数谱密度函数,就可以对应还原出其时域的函数,也能绘制出时域的波形图。

c6b0d6f0-a6f8-11ed-bfe3-dac502259ad0.gif

当然,本文限定讨论时域信号是因为我们电子系统中的应用最为普遍的就是一个时域信号,当然推而广之,其他的多维度信号也能利用上面定义进行推广,同样在多维空间信号也非常有应用价值,比如2维图像处理等等。

上面两个概念是一个东东么?

傅立叶级数对应的是周期信号,而傅立叶变换则对应的是一个时间连续可积信号(不一定是周期信号)

傅立叶级数要求信号在一个周期内能量有限,而后者则要求在整个区间能量有限

傅立叶级数的对应是离散的,而傅立叶变换则对应是连续的。

故而,两者的物理含义不同,且其量纲也是不同的,代表周期信号的第k次谐波幅度的大小,而则是频谱密度的概念。所以答案是这两者从本质上不是一个概念,傅立叶级数是周期信号的另一种时域的表达方式,也就是正交级数,它是不同的频率的波形的时域叠加。而傅立叶变换则是完全的频域分析,傅里叶级数适用于对周期性现象做数学上的分析,傅里叶变换可以看作傅里叶级数的极限形式,也可以看作是对周期现象进行数学上的分析,同时也适用于非周期性现象的分析。傅里叶级数适用于对周期性现象做数学上的分析,傅里叶变换可以看作傅里叶级数的极限形式,也可以看作是对周期现象进行数学上的分析,同时也适用于非周期性现象的分析。

啥是离散傅立叶变换?

离散傅里叶变换(Discrete Fourier Transform,缩写为DFT),是傅里叶变换在时域和频域上都呈离散的形式,将信号的时域采样变换为其DTFT的频域采样。

在形式上,变换两端(时域和频域上)的序列是有限长的,而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT,也应当将其看作其周期延拓的变换。在实际应用中通常采用快速傅里叶变换计算DFT。

对于N点序列

c7181d88-a6f8-11ed-bfe3-dac502259ad0.png

它的离散傅立叶变换为(DFT)为:

c72f8522-a6f8-11ed-bfe3-dac502259ad0.png

其中k=0,1,....,N-1,上面的式子展开一下:

c7403016-a6f8-11ed-bfe3-dac502259ad0.png

c752d4fa-a6f8-11ed-bfe3-dac502259ad0.jpg

啥是快速傅立叶变换?

快速傅立叶变换(Fast Fourier Transform:FFT)是一种计算数字信号序列的离散傅立叶变换(Discrete Fourier Transform:DFT)或其逆变换(IDFT)的算法。傅里叶分析将信号从其原始域(通常是时间或空间)转换为频域的表示,反之亦然。DFT是通过将一系列值分解成不同频率的分量来获得的。这个操作在很多领域中都很有用,但是直接从定义中计算它通常太慢而不实际。FFT通过将DFT矩阵分解成稀疏(大部分为零)因子的乘积来快速计算这种转换。所以其本质是实现离散傅立叶变换的一种优化算法,将时间复杂度从降低为,其中N为待计算序列的长度。当N非常大时,这种优化在时间维度上提升是非常显著的。尤其在嵌入式应用领域,由于受限于采用的芯片算力往往不强,所以FFT算法较之于DFT的效果是非常有应用价值的。

1994年,Gilbert Strang将FFT描述为“我们一生中最重要的数值算法”,并被IEEE杂志《计算科学与工程》列入20世纪十大算法之一,它深远的影响了我们世界与日常生活。说这个算法改变了世界也不为过。在我们日常生活中很多设备里面都有它的影子,比如手机、比如photoshop,比如数字音响等等。

快速傅立叶算法的最核心思想就是计算机科学里面常见的分治思想,即把一个复杂的问题,分解为一个小的类似问题进行求解。

FFT基本上可分为两类,时间抽取法和频率抽取法,而一般的时间抽取法和频率抽取法只能处理长度N=2M的情况,另外还有组合数基四FFT来处理一般长度的FFT。所谓抽取,就是把长序列分为短序列的过程,可在时域也可在频域进行。最常用的时域抽选方法是按奇偶将长序列不断地变为短序列,结果使输入序列为倒序,输出序列为顺序排列,这就是Coolly—Tukey算法。

假定待变换离散时间序列信号长度为,将x(n)按照奇偶分组:

c77d1792-a6f8-11ed-bfe3-dac502259ad0.png

上式可变换为:

c7993df0-a6f8-11ed-bfe3-dac502259ad0.png

c7aafe14-a6f8-11ed-bfe3-dac502259ad0.png

c7bc1ea6-a6f8-11ed-bfe3-dac502259ad0.png

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

从而,

由于A(k),B(k)都是点的DFT,X(k)为N点的DFT。那么这一分治思想还可以进一步做下去,这里就不赘述了。

下图就是一个时间抽取的基2FFT算法的示意图:

c7cbe638-a6f8-11ed-bfe3-dac502259ad0.png

对于频率抽取基2的示意图其原理类似,这里放个图:

c7e4cdc4-a6f8-11ed-bfe3-dac502259ad0.png

不同点:

DIT2 FFT是在时域先进行奇欧倒序,频域输出为正序

DIF2 FFT其输入序列在时域是正序,而频域输出为奇偶分开的倒序。

代码实践

好了,前面码了这么多字,还是不够直观,为了更好说明前面的分治思想,这里放了个递归实现代码测一下看看疗效:

#include
#include
#include
#include

#defineq8/*2^q点,256*/
#defineN(1<1){/*N如小于1,直接返回*/
intk,m;complexz,w,*vo,*ve;
ve=tmp;vo=tmp+n/2;
for(k=0;k1){
intk,m;complexz,w,*vo,*ve;
ve=tmp;vo=tmp+n/2;
for(k=0;k

代码来源:https://www.math.wustl.edu/~victor/mfmm/fourier/fft.c

为华盛顿大学的教学代码,上面代码仅测试了正变换,对于逆变换有兴趣的可以试试。

c7f95cb2-a6f8-11ed-bfe3-dac502259ad0.png

总结一下

本文目的为了方便理解快速傅立叶的算法思想,如果需要将算法实际应用到单片机或者DSP中,还需要做进一步的优化,实际使用时,一般会将蝶形算子做成一个表,另外也会做定点优化。对于ARM芯片而言,其CMSIS库有现成的实现例子可以直接使用,对于TI系列DSP而言,也内置了FFT代码库,可直接使用。

审核编辑:汤梓红

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 算法
    +关注

    关注

    23

    文章

    4608

    浏览量

    92844
  • FFT
    FFT
    +关注

    关注

    15

    文章

    434

    浏览量

    59368
  • 函数
    +关注

    关注

    3

    文章

    4329

    浏览量

    62575
  • 傅立叶
    +关注

    关注

    0

    文章

    36

    浏览量

    12527
  • 傅立叶变换
    +关注

    关注

    3

    文章

    105

    浏览量

    32381

原文标题:快速教会你傅立叶算法

文章出处:【微信号:mcu168,微信公众号:硬件攻城狮】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    快速傅立叶变换(FFT)算法实验

    本帖最后由 mr.pengyongche 于 2013-4-30 02:23 编辑 快速傅立叶变换(FFT)算法实验、摘
    发表于 12-21 10:54

    如何实现傅立叶变换算法

    计算量太大,直接用DFT算法进行谱分析和信号的实时处理是不切实际的。快速傅立叶变换(Fast FourierTransformation,简称FFT)使DFT运算效率提高1~2个数量级。其原因是当N较大时,对DFT进行了基4和基
    发表于 10-08 09:48

    浅懂示波器FFT快速傅立叶变换功能及运用

    氏变换,是离散傅氏变换的快速算法,它是根据离散傅氏变换的奇、偶、虚、实等特性,对离散傅立叶变换的算法进行改进获得的。这看,头都大了。今天我们就带大家简单的了解下什么是傅里叶变换以及它
    发表于 01-14 17:00

    教你招如何去实现傅立叶变换算法

    教你招如何去实现傅立叶变换算法
    发表于 04-30 06:05

    示波器FFT快速傅立叶变换不会用?看完这篇帖子,我彻底悟了

    的直流成分,直流信号的频率是0Hz。我们将通道的耦合方式改成交流,滤除直流信号,就会发现第条的直线消失了。FFT快速傅立叶变换的作用:FFT就是分析信号的频谱,在物理学、电子类学科
    发表于 09-22 13:42

    基于FPGA的快速傅立叶变换

    摘要:在对FFT(快速傅立叶变换)算法进行研究的基础上,描述了用FPGA实现FFT的方法,并对其中的整体结构、蝶形单元及性能等进行了分析。
    发表于 06-20 14:13 1103次阅读

    1024点FFT快速傅立叶变换

    Xilinx FPGA工程例子源码:1024点FFT快速傅立叶变换
    发表于 06-07 14:13 33次下载

    26步教会入门freemaster (1)

    Freemaster 是freescale 个很不错的工具,本文章主要是为了让大家快速掌握Freemaster 的用法,使我们监控变量,调试程序更方便!以下26 步教会使用free
    发表于 06-21 17:56 163次下载

    教会解决日常使用中电子地磅的小故障

    教会解决日常使用中电子地磅的小故障
    发表于 02-14 16:46 17次下载

    DSP进行浮点快速傅立叶变换剖析

    前言本文目的是演示如何使用STM32F30x 内部的DSP 进行浮点快速傅立叶变换(FFT),为联系实际应用
    的头像 发表于 09-18 06:44 9504次阅读

    快速傅立叶变换的基本概念及加窗函数的介绍

    4.2 快速傅立叶变换及加窗函数
    的头像 发表于 05-07 06:09 6501次阅读
    <b class='flag-5'>快速</b><b class='flag-5'>傅立叶</b>变换的基本概念及加窗函数的介绍

    简述FPGA的快速傅立叶变换

    摘要:在对FFT(快速傅立叶变换)算法进行研究的基础上,描述了用FPGA实现FFT的方法,并对其中的整体结构、蝶形单元及性能等进行了分析。 傅立叶变换是数字信号处理中的基本操作,广泛应
    的头像 发表于 05-27 11:21 2236次阅读
    简述FPGA的<b class='flag-5'>快速</b><b class='flag-5'>傅立叶</b>变换

    基于FPGA的快速傅立叶变换算法研究

    傅立叶变换是数字信号处理中的基本操作,广泛应用于表述及分析离散时域信号领域。但由于其运算量与变换点数N的平方成正比关系,因此,在N较大时,直接应用DFT算法进行谱变换是不切合实际的。
    发表于 02-22 09:38 279次阅读

    读懂FFT

    快速傅立叶变换(FFT)是离散傅立叶(DFT)的快速算法,它是根据离散傅立叶变换的奇、偶、虚、实等特性,对离散
    的头像 发表于 05-05 09:51 1.3w次阅读
    <b class='flag-5'>一</b><b class='flag-5'>文</b>读懂FFT

    浅懂示波器FFT快速傅立叶变换功能及运用

    氏变换,是离散傅氏变换的快速算法,它是根据离散傅氏变换的奇、偶、虚、实等特性,对离散傅立叶变换的算法进行改进获得的。这看,头都大了。今天我们就带大家简单的了解下什么是傅里叶变换以及它
    的头像 发表于 11-08 15:01 6846次阅读
    浅懂示波器FFT<b class='flag-5'>快速</b><b class='flag-5'>傅立叶</b>变换功能及运用