EEPW论坛

浅谈FFT以及FFT算法的基本实现（上） 

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

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

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

但是FFT之所以称之为快速傅里叶变换，就利用了以下的几个性质（重中之重！）

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

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

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

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

将x(n)按照奇偶分组

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

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

回顾一下：

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

则X₁(k)和X₂(k)都是长度为N/2的序列x₁(k)和x₂(k)的N/2点的离散傅里叶变换

其中：

至此，一个N点的DFT就被分解为2个N/2的DFT。但是X₁(k)和X₂(k)只有N/2个点，也就是说式（1-1）只是DFT的前半部分。要求DFT的后半部分可以利用其对称性求出后半部分为：

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

以N=8为例，可以用下图表示：

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

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

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

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

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