FFT (Fast Fourier Transform, 快速傅里叶变换) 是离散傅里叶变换的快速算法，也是数字信号处理技术中经常会提到的一个概念。用快速傅里叶变换能将时域的数字信号转换为频域信号，转换为频域信号后我们可以很方便地分析出信号的频率成分。

单频信号FFT

# single frequency signal
sampling_rate = 2**14
fft_size = 2**12
t = np.arange(0, 1, 1.0/sampling_rate)
x = np.array(map(lambda x : x*1e3, t))
y = np.sqrt(2)*np.sin(2*np.pi*1000*t)
y = y + 0.005*np.random.normal(0.0,1.0,len(y))
# fft
ys = y[:fft_size]
yf = np.fft.rfft(ys)/fft_size
freq = np.linspace(0,sampling_rate/2, fft_size/2+1)
freqs = np.array(map(lambda x : x/1e3, freq))
yfp = 20*np.log10(np.clip(np.abs(yf),1e-20,1e100))
fft_size = 2**14
t = np.arange(0, 1, 1.0/sampling_rate)
x = np.array(map(lambda x : x*1000, t))
y = np.sqrt(2)*np.sin(2*np.pi*1000*t) + np.sqrt(2)*np.sqrt(2)*np.sin(2*np.pi*4000*t)
y = y + 0.005*np.random.normal(0.0,1.0,len(y))
# fft
ys = y[:fft_size]
yf = np.fft.rfft(ys)/fft_size
freq = np.linspace(0,sampling_rate/2, fft_size/2+1)
freqs = np.array(map(lambda x : x/1e3, freq))
yfp = 20*np.log10(np.clip(np.abs(yf),1e-20,1e100))
相比于单频数字信号的快速傅里叶变换而言，多频数字信号的快速傅里叶变换有着更加苛刻的条件。除此之外，很多时候，我们并不知道被采样数字信号的所有频率成分，亦或我们只能在有限的时间段中对信号进行测量，无法知道在测量范围之外的信号是怎样的，因此只能对测量范围之外的信号进行假设。而快速傅里叶的假设很简单：测量范围之外的信号是所测量信号的重复。这就会引起在 fft_size 个点的采样范围内无法放下整数个所有被采样频率的波形而造成频谱泄漏。

<2>频谱泄漏
当我们把双频信号FFT示例中的 fft_size 的值改为 2**12 时，这时，基频为 16Hz，不能被 1kHz整除，所以 1kHz 处发生了频谱泄露，而它能被 4kHz 整除，所以 4kHz 可以很好地被采样。
<2.1>频谱泄漏的原因
# 50Hz正弦波512点FFT采样
t = np.arange(0, 1.0, 1.0/8000)
x = np.sin(2*np.pi*50*t)[:512]
pl.plot(np.hstack([x,x,x]),linewidth=2)
pl.xlabel('Sampling point')
pl.ylabel('Amplitude[a.u.]')
pl.ylim(-1.5,1.5)
pl.show()