500万彩票网

【解析新特性】300W单路输出工业电源>>
电子产品世界 » 论坛500万彩票网 » 高校专区 » 坤创E-Geek/天科大新电社 » 500万彩票网【原创】浅谈FFT以及FFT算法的基本实现(上)

共9条 1/1 1 跳转至

【原创】浅谈FFT以及FFT算法的基本实现(上)

高工
2020-05-19 23:26:17    评分

浅谈FFT以及FFT算法的基本实现(上) 

相信网上现在有很多关于FFT的教程,我曾经也参阅了很多网上的教程,感觉都不怎么通俗易懂。在基本上的研究FFT,并且通过编程的形式实现之后。我决定写一篇通俗易懂的关于FFT的讲解。因此我在接下来的叙述中尽量非常通俗细致的讲解。

本人最早知道傅里叶变换的时候是沉迷于音乐的频谱跳动无法自拔,当时就很想做一个音乐频谱显示器。搜阅了很多资料之后,才了解到傅里叶变换,和FFT。当然这都是以前的事情了,最近经过抽空调试,自制了一个FFT的算法,不敢说速度上的优势,但是个人认为是一种通俗易懂的实现方法。经过实际的VC++模拟实验、和STM32跑的也很成功。因此在这里分享给大家。

首先,要会FFT,就必须要对DFT有所了解,因为两者之间本质上是一样的。在此之前,先列出离散傅里叶变换对(DFT):

1589901093782292.png

但是FFT之所以称之为快速傅里叶变换,就利用了以下的几个性质(重中之重!)

1589901122501872.png

  先把这仨公式放到这,接下来会用到。

根据这几个特性,就可以将一个长的DFT运算分解为若干短序列的DFT运算的组合,从而减少运算量。在这里,为了方便理解,我就用了一个按时间抽取的快速傅里叶变换(DIT-FFT)的方法。

首先,将一个序列x(n)一分为二

对于1589901160171637.png设N是2的整次幂 也就是N=2^M

x(n)按照奇偶分组

 1589901251922983.png

 

那么将DFT也分为两组来预算

005.png

这个时候,我们上边提的三个性质中的可约性就起到作用了:

回顾一下:006.png

那么这个式子就可以化为:

006.png

X1(k)X2(k)都是长度为N/2的序列x1(k)x2(k)N/2点的离散傅里叶变换

其中:007.png

至此,一个N点的DFT就被分解为2个N/2的DFT。但是X1(k)X2(k)只有N/2个点,也就是说式(1-1)只是DFT的前半部分。要求DFT的后半部分可以利用其对称性求出后半部分为:

008.png

那么式(1-1)和(1-2)就可以专用一个蝶形信号流图符号来表示。如图:

 

图片1.png

N=8为例,可以用下图表示:

图片2.png

那么通过这样的分解,每一个N/2点DFT只需(N^2)/4次复数相乘计算,明显的节省了运算量。

那么以此类推,继续将已经得出的X1(k)X2(k)按奇偶继续分解,还是上边一样的方法。那么就得出了百度上都可以找到的一大堆的这个图片了。

图片3.png

对于这张图片我想强调的一点就是第二阶蝶形运算的时候,1589944813551698.png之后不应该是image.png吗,为什么是image.png了,这个问题之前困扰了我一段时间,但是不要忘了,前者的image.png的展开是image.png 因为此时N已经按照奇偶分开了,所以是N/2 而image.png也就是image.png是根据image.png的可约性得出的,在这里不能混淆。

对于运算效率就不用多提了,M级的运算总共需要:

1589901918584729.png

    以上就是FFT算法的理论内容了(作者水平有限,如有不对还请大家拍砖,谢谢各位),接下来就是用C语言对这个算法的实现了,关于C语言的实现,咱们下一篇当中再详细阐述~





关键词: FFT代码     500万彩票网 STM32     傅里叶     500万彩票网 快速傅里叶变换    

工程师
2020-05-20 09:25:08    评分
2楼

岩浆的风格


助工
2020-05-21 19:49:16    评分
3楼

期待更新


助工
2020-05-21 19:51:38    评分
4楼

不错的文章


助工
2020-05-21 19:53:48    评分
5楼

学习了


助工
2020-05-21 19:55:21    评分
6楼

学习一下


助工
2020-05-21 19:58:07    评分
7楼

等更新


助工
2020-05-21 20:01:13    评分
8楼

学习一下


工程师
2020-05-21 22:53:31    评分
9楼

讲解的十分专业


共9条 1/1 1 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]
五分时时彩 山东11选5走势 北京赛车pk10玩法 500彩票网 幸运时时彩开奖结果 北京pk10 500彩票网 小米彩票登陆 福建11选5 鼎鑫彩票注册