Introduction to "FFT"

               首先，我构思了一会儿，希望通过比较好的方式，阐述FFT. 开源，分享.

... ...

回答，什么FFT？

           FFT，Fast Fourier Transform. 它是一种快速的DFT(Discret Fourier Transform)，由于人们在利用DFT的时候，算法速度很慢，计算时间长,（长的你根本受不了，等的天都黑了~它还没计算出结果），于是牛人就想办法在算法上改进传统的DFT. 改进的结果就是FFT。它不是一种新的变换，而是对DFT的改进，而由于快速的特性，得到广泛的应用~

DFT：

对于复数序列，离散傅里叶变换公式为：

实现DFT也是要花点时间的

我之前做DFT的笔记在这里，要搞懂FFT，必须先明白DFT

http://blog.csdn.net/cinmyheart/article/details/21050119

Get start with "FFT" （基于时间抽选的基-2 FFT 算法）

算法原理：

按照输入的信号顺序的奇偶数来把原来一个部分的DFT分成两个部分的DFT

最后原来的DFT[x(n)] 被恒等的化做两个部分相加.

注意事项:

一.       W2N = exp(-2*pi*j*2/N) == exp(-2*pi*j/(N/2));这是极其重要的恒等变形！累加的范围从原来的0~N-1, 降低到了0~N/2 -1 !!!

二.  exp(-2*pi*j* (r*k)/(N/2)) == exp(-2*pi*j *( r*(k+N/2)) / (N/2) ) 这里利用了 exp(-2*pi*j * X)的周期性

利用这个周期性，可以推理得到，

这是很重要的性质，利用这种周期性，我知道前面一般，就可以算出后面的一半数据了，因为相同的！

X1(N/2 + k) = X1(k)

三.

k  = 0,1,2,3 ... (N/2 -1）

 利用 

W_(N/2 + k)_N == exp(-2*pi*j*(N/2 + k)/N ) 

== W_(N/2)_N* W_(k)_N == exp(-2*pi*j*(N/2 )/N ) * exp(-2*pi*j*(k)/N )

== - W_(k)_N == - exp(-2*pi*j *(k/N))

于是！W_(N/2 + k)_N == -W_(k)_N

上面等式的左边+N/2 得到的是后半部分的X1(k) [注意k的取值范围已经不是0 ~N-1咯]

最后我们完成了一件很漂亮的事情，简直“算命先生”哈哈利用“一半的数据，我们可以获得全部的数据”

为什么这么说呢？

看这个图

X1 和X2是输入数据

X(k)是输出，

X(k)         ==前半部分 = X1(k) + W_k_N * X2(k);

X(k+N/2) ==后半部分 = X1(k) -  W_k_N * X2(k);

k是0~N/2,此时我们利用N/2的输入数据，能够得到N的输出数据.

正是基于以上的几点原因，才会有速度的提升！！！

想法虽好，怎么实现呢？

Butter fly 

看这里，

X(k)         ==前半部分 = X1(k) + W_k_N * X2(k);

X(k+N/2) ==后半部分 = X1(k) -  W_k_N * X2(k);

有没有很像一只蝴蝶~

这里是基于N/2 点的DFT，于是只有一次奇偶重排序,

前面四个点是奇数顺序点，后面四个是偶数顺序点（注意计数从0开始，而不是1,所以0是奇数顺序点）

上图得到的其实是4对 蝶形，: )

这里N == 8,可以在N/2 中有4个点，还可以进行奇偶重排序，直到只有两个点，不需要再进行奇偶重排序

程序实现的注意事项

1. 奇偶重排序——实现方式 Bits reversal,在之后的link中会以C语言代码demo的方式给出

2.  在第一层，W_0_N 第二层 W_0_N,W_2_N, 第三层W_0_N W_1_N W_2_N W_3_N

这个W_r_N的系数r和层数的关系，用C 语言的形式表述为

  tmp = k << (bits - m);
   然后取低的m个有效位，即可以得到r      
  r =  tmp & ((1<<m) - 1);    

3. It‘s time to implement yourown FFT !

http://blog.csdn.net/cinmyheart/article/details/39042623

Introduction to "FFT"