FFT（Fast Fourier Transform. ）快速傅里叶变换

算法的输入示时域待处理信号，输出为频域信号

1. 频率轴

输入时域信号，输出频域信号。输出信号的自变量是频率，因变量是幅值。

假设输入时间序列长度为N（即包含N个数据点），两点间隔为Ts,也就是输入信号的采样频率为Fs,则有Ws=2*pi*Fs

频率轴则表示为：Ws*（-N/2:N/2-1）/N  

至于为什么要除以N?

我是从不定原理不（Uncertainty Principle):对于任意一个信号，时间分辨率*频率分辨率>=1/2,当且仅当信号为高斯信号时取等。此原理说明，时域分辨率和频率分辨率是相互制约的。其中一个变大，另一个则变小。

对于傅里叶变换，时域信号具有最好的时间分辨率，频域信号具有最好的频率分辨率。

时域把时间长度为t的信号分为N点，相当于时间缩小了t/Ts=N倍，则频域相当于放大了N倍。所以频率轴是除以N的。

换种理解角度，耐奎斯特采样定律说采样频率fs必须是>=2倍信号频率，信号才能理论上从频域逆变换出完整的时域信号。

2.负频率

负频率究竟有无实际物理意义，这一直是人们讨论的问题。

这个论坛上有个帖子说的蛮好http://www.chinavib.com/forum/thread-51199-1-1.html

3.对于Matlab里的fft

Matlab里有fft快速算法的实现，可惜看不到源代码。

fft()是做DFT

fft(x,N)是做N点FFT，当x的数据长度小于N是，则补零；当x的数据长度大于N，则截断。

蝶形算法 假设前提N是2的幂次，但是Maltab里的fft没有此限制，很想看到Maltab里fft函数的源代码是怎么处理的。。。()

4.放一段Matlab里实现fft的小例子

clear all;
N=2048;
t=linspace(0,20,N);
x=sin(2*pi*4*t);
figure,plot(t(1:50),x(1:50)/10000);
Ts=t(2)-t(1);
Ws=2*pi/Ts;
F=fft(x);
Fc=fftshift(F)*Ts;
W=Ws*(-N/2:(N/2)-1)/N;
figure,plot(W,abs(Fc));