灵魂级别详解基

     小小的研究快速傅里叶的原因是老师讲完了快速傅里叶，还在云里雾里时，老师让人用C语言写出来，觉得难得好笑，然后就点名到我了。

  公式推导：从傅里叶到推导到快速傅里叶，这样的公式推导书上，网上太多了，我就不在这里详细推导了。会列出及重要的结果：帮助我使用快速傅里叶。

这个图只有一维， 也是蝶形算法最基本最简单的一个，最好理解。看第二个框图，前端输入是x（），右边是X（），也就是傅里叶变换的结果，1框图是详细计算步骤，就这两步，特别简单，本身傅里叶特别复杂，计算量特别大，这个我们介绍的算法相比之下，计算量大大减小，减少多少看书就知道了。

上图最基本的单位大概理解了，下面是基本的公式估计也就理解了：

不理解的话，小小的解释下，左边是傅里叶结果，右边的输入x1(k),x2(k),Wnk,,估计就Wnk不理解，另两个就是从前端的输入来的，Wnk，我就动手解释下怎么算的：

上图把Wnk转化为复数，这样那个Wnk才能真正的用于实践，看了这个东西，估计也不会算，反正我只看了我也不会，先不管那个N，k，先看看八位蝶形算法：

原理最关键的就是这个，左端输入，通过很多小的蝶形运算基本单位，就可以得到左端的结果。正常的人都可以发现出来的顺序好像出问题了，规律直接告诉：

就是把所属的序号转化为二进制，进行log2N次圆周移位。这是我总结的，比书上的简单，输入自然序出来倒序，输入倒序出来自然序。

讲到这里，应该是懂了怎么算，但是为啥要这么算，得看书去，公式推导，我自己推估计也不行，但是知道怎么回事就行。

开始讲程序了，程序里的注释应该很简单明了，根据上面的理解估计应该没问题，加上我的文字解释真的太简单了。

这两个头文件，估计都知道，能运行C语言的环境基本上都有，这个没问题。

定义两个参数：N，就是输入多少个点，也就是数据，必须满足2的多少次方，8,16,64,128，等等；那个log2N，就是2的多少次方的那个多少，比如说，64，就是2的6次方。

先定义一个结构体，就是复数的实部real，虚部img，很多头文件complex都有相关的定义，但是那个头文件麻烦，兼容性不好，所以这里主动自己定义了。

x[N]这个结构体数组就是输入的数组，虚部都是0，因为采样回来的没有虚部，顺便说明下，下面的运算基本上都是复数的方式进行的。

这里定义了一个数组，按照道理来说，应该程序自己算啊，其实是这样的，在实际的工程应用当中，这样的运算是认为有点浪费资源的，而且应用当中输入的点数也就是数据。都是固定的，所以直接计算好了定义成数组，方便高效。

这样的数据哪里来的呢，方法有很多比如EXCEL，或者matlab，或者其他的，我推荐使用matlab，写一个小程序就行了：如图所示

多少位的改上面的参数就行了，顺便说一下，这是我第一次使用matlab做那么一点有用的事。

这里定义几个子函数，懂复数的人基本上都知道，如果忘了也没关系，反正懂了这个久了不用也会忘记，会调用就行。

前面将原理的时候说了，输入自然序出来倒序，输入倒序，出来自然序，所以必须将倒倒序转化为自然序，因为我们想要的肯定是输入自然序，输出自然序。

其实得到自然序，主要的就是这个位运算，要是熟悉代码的人，一看就明白，不熟悉的自己下来仔细推导一下。

最后那个if可能很多人就不明白了，很简单，比如八位的输入01234567输出04261537，这里发现，需要交换数据的1和4,3和6，只需要交换一次就可以。

最关键的就是这个算法了，就是所谓的蝶形运算，给了图我觉得真的不容易懂，我反正看图叫我写出来也不可能，因为我根本不清楚，到底是怎样得到输出的。

下面说说我的理解，这段文字配合上面的蝶形运算的图哈，其实就是算每一个节点，每一个节点都是利用，里面的每一个参数我都讲了，我们计算的时候，如果想知道某一个输出的结果，那个必须知道前一级对应的节点，然后前一级对应的节点又必须知道更前一级的某些节点，有些人可能还是不清楚怎样才知道自己需要前一级的那些节点呢，有这样疑问的同志估计还是不明白那个蝶形图到底怎么回事，那个图就是告诉咩一个数据对应的关系，前者箭头指向后者就是后者需要前者，这很明了了。

这里说说算法的基本思想流程，先算第一级蝶形运算，，每一个第一级都要算完，然后再算，每一级每一个数据都要算完，这样才能算下一级，以此类推，算出最终结果。

算法里有三重运算，每一个变量也就是ijk，这三个循环变量的封顶的那个数据，其实很容易理解，先假设输入八位数据，然后把相应的封顶数据算出来，再弄个16个数据的，规律自己就出来了，自己动手算一下，就明白了。

需要的函数都讲完了，理解与否看造化。下面是主函数和输出的结果。

 

 

这里的数据结果和matlab完全符合，matlab那个数据我没有截图，但是是完全正确的。