自己用matlab实现fft.m函数

首先，我们需要系统回忆一下4种形式的Fourier变换

$$x(t)=\sum _{k=?\infty }^{\infty }X(k{\Omega }_0)e^{jk{\Omega }_{0}t}$$
X ( k Ω 0 ) = 1 T ∫ T x ( t ) e ? j k Ω 0 t d t X(k\Omega_{0})=\frac{1}{T}\int_{T}x(t)e^{-jk\Omega_{0}t}dt X(k/span>Ω0​)=T1​∫T​x(t)e−jkΩ0​tdt
其中。${\Omega }_0=\frac{2\pi }{T}$，T为周期。

$$X(j\Omega )={\int }_{-\infty }^{\infty }x(t)e^{-j\Omega t}dt$$
$$x(t)=\frac{1}{2\pi }{\int }_{-\infty }^{\infty }X(j\Omega )e^{j\Omega t}d\Omega$$

$$X(k)=\sum _{n=0}^{N-1}x(n)e^{-j\frac{2\pi }{N}nk}$$
$$x(n)=\frac{1}{N}\sum _{k=0}^{N-1}X(k)e^{j\frac{2\pi }{N}nk}$$
其中，N为离散信号的周期

$$X(e^{jw})=\sum _{n=-\infty }^{\infty }x(n)e^{-jwn}$$
$$x(n)=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }X(e^{jw})e^{jwn}dw$$
以上4种情况的傅里叶变换，最为常用的是第3种和4种，也称之为离散傅里叶级数DFS,离散时间傅里叶变换DTFT。第1种情况和第2种情况分别被成为傅里叶级数FS和傅里叶变换FT。我们今天的思路也是由DFS介绍到DFT再最后介绍FFT。

由上述4种情况可以总结出的是，如果信号在时域是周期的，那么在频域则必定是离散的。如果在时域是非周期的，那么在频域必定是连续的。

我们知道，在计算机种要实现信号的频谱分析及其他方面的处理工作时，对信号的要求应该由2点，一是时域和频域都应该是离散的，二是应该有限长。在上述4种情况中，只有DFS在时域和频域都是离散的。但是，两者却都是无限长的。我们仔细观察这个变换对
$$X(k)=\sum _{n=0}^{N-1}x(n)e^{-j\frac{2\pi }{N}nk}$$
$$x(n)=\frac{1}{N}\sum _{k=0}^{N-1}X(k)e^{j\frac{2\pi }{N}nk}$$
其中，N为离散信号的周期。
仔细观察我们可以知道，$e^{j\frac{2\pi }{N}nk}$和$e^{-j\frac{2\pi }{N}nk}$相对n和k都是以N为周期的（因为$e^{jw}$是以$2\pi$为周期的）。利用这个性质，我们将DFS重写，得到离散傅里叶变换DFT。
$$X(k)=\sum _{n=0}^{N-1}x(n)e^{-j\frac{2\pi }{N}nk}=\sum _{n=0}^{N-1}x(n)W_N^{nk}$$
其中，$k=0,1,...N-1$
$$x(n)=\frac{1}{N}\sum _{k=0}^{N-1}X(k)e^{j\frac{2\pi }{N}nk}=\frac{1}{N}\sum _{n=0}^{N-1}$$