自己用matlab实现fft.m函数

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

x ( t ) = ∑ k = ? ∞ ∞ X ( k Ω 0 ) e j k Ω 0 t x(t)=\sum_{k=-\infty}^{\infty}X(k\Omega_{0})e^{jk\Omega_{0}t} x(t)=k=?∞∑∞X(kΩ0)ejkΩ0t 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 其中。 Ω 0 = 2 π T \Omega_{0}=\frac{2\pi}{T} Ω0​=T2π​，T为周期。

X ( j Ω ) = ∫ − ∞ ∞ x ( t ) e − j Ω t d t X(j\Omega)=\int_{-\infty}^{\infty}x(t)e^{-j\Omega t}dt X(jΩ)=∫−∞∞​x(t)e−jΩtdt x ( t ) = 1 2 π ∫ − ∞ ∞ X ( j Ω ) e j Ω t d Ω x(t)=\frac{1}{2\pi}\int_{-\infty}^{\infty}X(j\Omega)e^{j\Omega t}d\Omega x(t)=2π1​∫−∞∞​X(jΩ)ejΩtdΩ

X ( k ) = ∑ n = 0 N − 1 x ( n ) e − j 2 π N n k X(k)=\sum_{n=0}^{N-1}x(n)e^{-j\frac{2\pi}{N}nk} X(k)=n=0∑N−1​x(n)e−jN2π​nk x ( n ) = 1 N ∑ k = 0 N − 1 X ( k ) e j 2 π N n k x(n)=\frac{1}{N}\sum_{k=0}^{N-1}X(k)e^{j\frac{2\pi}{N}nk} x(n)=N1​k=0∑N−1​X(k)ejN2π​nk 其中，N为离散信号的周期

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

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

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