首先请忘掉你在高赞看到的多项式系数表示法点值表示法，FFT是搞傅里叶变换的！首先得把傅里叶变换搞清楚了！连傅里叶变换的意义都没搞清楚就上FFT，是不可能完全理解的！高赞里的系数表示法点值表示法只是一个FFT的应用！高赞答主可能是直接把别人的应用照搬过来了，其实对于理解FFT 没有帮助，只会让人云里雾里。

我们需要明白：FFT算法实质上就是DFT算法的改良版，而DFT算法则是傅里叶变换的离散版。按傅里叶变换→DFT→FFT的思路推导，即可理解FFT。

为使文章简明，此处略过傅里叶变换的详细数学推导，仅说明物理意义。

如果你知道它的物理意义，可以跳过本节，直接从2. DFT开始即可。不知道傅里叶变换是啥的，请移步其他单纯介绍傅里叶变换的文章，或者翻高数教材。

我们知道，周期函数的傅里叶级数实质上是将函数 f(t) 分解为无数个不同频率、不同幅值的正、余弦信号，而这些信号的频率都是基频 \omega_0 的整数倍（即 n\omega_0 ）。换言之，我们是在用无数个这样不同频率，不同幅值的正、余弦信号来逼近周期函数 f(t) 。分解的过程中，对于每一个 n\omega_0 ，我们都得到了对应的幅值，这是不是就组成了一个函数关系（自变量为 n\omega_0 ，因变量为幅值，即相应频率信号的强度）？我们称之为频谱函数。

而对于非周期函数，傅里叶变换则是求频谱密度函数，该函数的自变量是 \omega ，因变量是信号幅值在频域中的分布密度，即单位频率信号的强度。（如果你学过概率论，可以将频谱函数和频谱密度函数类比为离散概率分布和概率密度函数）

如果上面的物理意义你没有看明白，可以接着往下看。如果明白了，可以跳转至2. DFT。

为什么这么说呢？我们将周期函数的傅里叶级数转化为指数形式，即

c_{n}=\frac{1}{T}\int_{-\frac{T}{2}}^{\frac{T}{2}} f(t)e^{-jn\omega_0t}dt

f(t)=\sum_{n=-\infty}^{n=+\infty}c_ne^{jn\omega_0t}

然而傅里叶级数显然是以 T 为周期，对于更为常见的非周期函数，傅里叶级数无法对其进行逼近操作。

那么对于非周期函数，我们把它的周期看作无穷大。基频 \omega_0=\frac{2\pi}{T} 则趋近于无穷小，又因为基频相当于周期函数的傅里叶级数中两个相邻频率的差值 (n+1)\omega_0-n\omega_0 ，我们可以把它记作 \Delta\omega 或者微分 d\omega 。 n\omega_0 则相当于连续变量 \omega 。这样就得到了针对非周期函数的频谱函数如下

c_{n}=\frac{\Delta\omega}{2\pi}\int_{-\infty}^{+\infty} f(t)e^{-jwt}dt

我们会发现这里的 c_n 是趋于0的。

将它代入f(t)=\sum_{n=-\infty}^{n=+\infty}c_ne^{jn\omega_0t}

得到

f(t)=\sum_{-\infty}^{+\infty}(\frac{\Delta\omega}{2\pi}\int_{-\infty}^{+\infty} f(t)e^{-jwt}dt)e^{j\omega t}=\int_{-\infty}^{+\infty}\frac{1}{2\pi}(\int_{-\infty}^{+\infty}f(t)e^{-j\omega t}dt)e^{j\omega t}d\omega

则非周期函数的傅里叶变换定义为

F(\omega)=\int_{-\infty}^{+\infty}f(t)e^{-j\omega t}dt

我们可以发现 c_n=\frac{d\omega}{2\pi}F(\omega) ，即我们选取了信号幅值在频域中的分布密度 F(\omega) 来表示傅里叶变换，而不是相应频率的信号幅值大小 c_n 。因为如果选择后者，那傅里叶变换的函数值就都是无穷小了，这显然对我们没有任何帮助。

我们一般也用频率 f 来进行傅里叶变换

F(f)=\int_{-\infty}^{+\infty}f(t)e^{-j2\pi f t}dt

所以我们可以说，傅里叶变换的目的就是将信号转化为无数个不同频率的正弦信号的叠加，然后揭示这些正弦信号的强度和频率的关系。

懂DFT的朋友们可以跳过本节，直接进入3.FFT。

我们说过，傅里叶变换的目的就是得到信号的频谱密度函数（自变量是 \omega ，因变量是信号幅值在频域中的分布密度，即单位频率信号的强度），它实际上揭示了信号的强度和频率的关系。

对于傅里叶变换

F(f)=\int_{-\infty}^{+\infty}f(t)e^{-j2\pi f t}dt

我们做数学题时碰到的 f(t) 大多数是在 t 上连续的，但由于计算机采集的信号在时域中是离散的，故实际应用中的 f(t) 都是其经采样处理后得到的 f_s(t) 。

同时，计算机也只可能计算出有限个频率上对应的幅值密度，即 f 也是离散的。

DFT就是 t 和 f 都为离散版的傅里叶变换。

懂采样的朋友们可以跳过本节，直接进入2.2节。

采样的具体操作是什么？我们首先引入冲激函数（也叫Dirac函数）的概念。

当 t\neq0 时 \delta(t)=0 ； \int_{-\infty}^{+\infty}\delta(t)dt=1 。

根据它的定义，我们可知 \int_{-\infty}^{+\infty}\delta(t-t_0)f(t)dt=f(t_0) 。这是Dirac函数的重要性质，容易看出，它可以筛选出 f(t) 在 t_0 处的函数值，即起到采样的作用。

但是Dirac函数一次只能选取一个函数值，所以我们将很多个采样点不同的Dirac函数叠加起来，就可以实现时域上的采样了。这样叠加的函数被称为梳状函数，表达式为 \delta_s(t)=\sum_{n=-\infty}^{\infty}\delta(t-nT_s)

其中 T_s 为采样周期。

将时域上的连续信号与它相乘，即可得到 f_s=\sum_{n=-\infty}^{\infty}f(t)\delta(t-nT_s) 。

对于采样得到的 x_s(t)=\sum_{n=-\infty}^{\infty}x(t)\delta(t-nT_s) 进行傅里叶变换。

根据傅里叶变换的定义

X(\omega)=\int_{-\infty}^{+\infty}x(t)e^{-j\omega t}dt

则 X_s(\omega)=\int_{-\infty}^{\infty}(\sum_{n=-\infty}^{\infty}x(t)\delta(t-nT_s))e^{-j\omega t}dt

交换积分与求和顺序，得到 X_s(\omega)=\sum_{n=-\infty}^{\infty}\int_{-\infty}^{\infty}x(t)\delta(t-nT_s)e^{-jwt}dt

根据Dirac函数的筛选特性， X_s(\omega)=\sum_{n=-\infty}^{\infty}x(nT_s)e^{-jwnT_s}

这样就完成了我们的时域离散化计算。

时域离散化得到的结果 X_s(\omega) 在频域上仍是连续的，而计算机只能求取有限个 \omega 对应的频谱密度。此外， X_s(\omega)中的时域采样次