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

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

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

对于：

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

将x(n)按照奇偶分组：

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

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

回顾一下：

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

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

其中：

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

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

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

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

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

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

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

FFT

C语言实现

对于FFT算法C语言的实现，网上的方法层出不穷，介于本人比较懒（懒得看别人的程序），再加上自给自足丰衣足食的原则，我自己也写了一个个人认为比较通俗易懂的程序。并且为了帮助读者理解，我特意尽量减少了库函数的使用，一些基本的函数都是自己写的（难免有很多BUG），但是作为FFT算法已经够用了，目前这个程序只能处理2^N的数据，理论上来讲如果不够2^N的话可以在后面数列补0这种操作，当然为了简约文中也就没有实现，但是主要的功能还是具备的，下面将代码开源如下：

←左右滑动，查看代码→

/*

功能：将input里的数据进行快速傅里叶变换 并且输出

*/

#include

#include

#define FFT_LENGTH 8

double input[FFT_LENGTH]={1,1,1,1,1,1,1,1};

struct complex1{ //定义一个复数结构体

double real; //实部

double image; //虚部

};

//将input的实数结果存放为复数

struct complex1 result_dat[8];

/*

虚数的乘法

*/

struct complex1 con_complex(struct complex1 a,struct complex1 b){

struct complex1 temp;

temp.real=(a.real*b.real)-(a.image*b.image);

temp.image=(a.image*b.real)+(a.real*b.image);

return temp;

}

/*

简单的a的b次方

*/

int mypow(int a,int b){

int i,sum=a;

if(b==0)return 1;

for(i=1;i=n)break;

}

return i;

}

/*

简单的交换数据的函数

*/

void swap(struct complex1 *a,struct complex1 *b){

struct complex1 temp;

temp=*a;

*a=*b;

*b=temp;

}

/*

dat为输入数据的数组

N为抽样次数 也代表周期 必须是2^N次方

*/

void fft(struct complex1 dat[],unsigned char N){

/*最终 dat_buf计算出 当前蝶形运算奇数项与W 乘积

dat_org存放上一个偶数项的值

*/

struct complex1 dat_buf,dat_org;

/* L为几级蝶形运算 也代表了2进制的位数

n为当前级蝶形的需要次数 n最初为N/2 每级蝶形运算后都要/2

i j为倒位时要用到的自增符号 同时 i也用到了L碟级数 j是计算当前碟级的计算次数

re_i i_copy均是倒位时用到的变量

k为当前碟级 cos(2*pi/N*k)的 k 也是e^(-j2*pi/N)*k 的 k

*/

unsigned char L,i,j,re_i=0,i_copy=0,k=0,fft_flag=1;

//经过观察，发现每级蝶形运算需要N/2次运算，共运算N/2*log2N 次

unsigned char fft_counter=0;

//在此要进行补2 N必须是2^n 在此略

//蝶形级数 (L级)

L=log2(N);

//计算每级蝶形计算的次数(这里只是一个初始值) 之后每次要/2

//n=N/2;

//对dat的顺序进行倒位

for(i=1;i0;j--){

//判断i的副本最低位的数字 并且移动到最高位 次高位 ..

//re_i为交换的数 每次它的数字是不能移动的 并且循环之后要清0

re_i|=((i_copy&0x01)=1;

}

swap(&dat[i],&dat[re_i]);

}

//进行fft计算

for(i=0;i