快速傅里叶变换（FFT）基本原理

快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的加速算法，而DFT则是将连续的傅里叶变换离散化（在时域和频域离散），连续傅里叶变换可由傅里叶展开式推导得出。

正向逻辑为： 傅里叶展开式 \(\rightarrow\) 推导得到 \(\rightarrow\) 连续傅里叶变换对 \(\rightarrow\) 离散后得到 \(\rightarrow\) 离散傅里叶变换 \(\rightarrow\) 开发加速算法 \(\rightarrow\) 快速傅里叶变换 ## 傅里叶变换 ### 三角函数形式 对于一个周期为 \(T\) 的信号 \(x(t)\)，其基频为 \(f_1=1/T\)。对 \(x(t)\) 进行傅里叶展开：

\[ x(t) = \frac{a_0}{2} +\sum^{\infty}_ {n=1} \left[ a_n \cos\left(2\pi n f_1 t \right) + b_n \sin\left(2\pi n f_1 t \right) \right] \]

上式中的 \(a_n\) 和 \(b_n\) 是傅里叶系数：

\[ a_n = \frac{2}{T} \int^T_ 0 x(t) \cos \left( 2\pi n f_1 t \right) dt \]

\[ b_n = \frac{2}{T} \int^T_ 0 x(t) \sin \left( 2\pi n f_1 t \right) dt \]

根据欧拉公式，可以将傅里叶变换式写为指数形式，指数形式看起来更为简洁，利于推导。 根据欧拉公式，有以下变换：

\[ \cos \left( 2\pi n f_1 t \right) = \frac{1}{2} \left[ e^{j2\pi n f_1 t} + e^{-j2\pi n f_1 t} \right] \]

\[ \sin \left( 2\pi n f_1 t \right) = \frac{1}{2j} \left[ e^{j2\pi n f_1 t} - e^{-j2\pi n f_1 t} \right] \]

欧拉公式：\(e^{ix} = \cos x + i \sin x\)

带入傅里叶展开式，可得：

\[ x(t) = \frac{a_0}{2} +\sum^{\infty}_ {n=1} \left[ \frac{a_n}{2} \left[ e^{ j 2\pi n f_1 t } + e^{ -j 2\pi n f_1 t } \right] + \frac{b_n}{2j} \left[ e^{ j 2\pi n f_1 t } - e^{ -j 2\pi n f_1 t } \right] \right] \]

合并同类项可得：

\[ x(t) = \frac{a_0}{2} +\sum^{\infty}_ {n=1} \left[ \frac{a_n - j b_n}{2} e^{ j 2\pi n f_1 t } + \frac{a_n + b_n}{2} e^{ -j 2\pi n f_1 t } \right] \]

观察指数项前的系数，令

\[ X(2\pi n f_1) = \frac{a_n - j b_n}{2} \]

则有：

\[ X(-2\pi n f_1) = \frac{a_n + j b_n}{2} \]

发现指数项前的系数具有奇偶性，利用奇偶性并改变求和符号的下限，将展开式改写为：

\[ x(t) = \sum^{\infty}_ {n=-\infty} X(2\pi n f_1) e^{ j 2\pi n f_1 t } \]

注意，此时求和符号的下限由一变为负无穷，\(1 \rightarrow -\infty\)。式中的 $X(2n f_1) $ 展开后为：

\[ \begin{gathered} X(2\pi n f_1) =\frac{1}{2} \left[ \frac{2}{T} \int^T_ 0 x(t) \cos \left( 2\pi n f_1 t \right) dt - \frac{2j}{T} \int^T_ 0 x(t) \sin \left( 2\pi n f_1 t \right) dt \right] \\\\ = \frac{1}{T} \int^T_ 0 x(t) \left[ \cos \left( 2\pi n f_1 t \right) - j \sin \left( 2\pi n f_1 t \right) \right] dt \end{gathered} \]

再利用欧拉公式，可得：

\[ X(2\pi n f_1) = \frac{1}{T} \int^T_ 0 x(t) e^{ -j 2\pi n f_1 t} dt \]

总结上述推导过程，得到指数形式的傅里叶变换对：

\[ x(t) = \sum^{\infty}_ {n=-\infty} X(2\pi n f_1) e^{ j 2\pi n f_1 t } \]

\[ X(2\pi n f_1) = \frac{1}{T} \int^T_ 0 x(t) e^{ -j 2\pi n f_1 t} dt \]

以上两个公式中，第二式才是傅里叶变换，第一式是傅里叶变换反演公式。

当信号没有周期，即周期无穷大时 \(T\rightarrow \infty\)，有\(f_1\rightarrow 0\)，此时第一式的求和符号可以改写为积分号，\(f_1\) 可以被当作是一个连续变化的量，傅里叶变换对就被改写为了连续形式。

傅里叶变换对第一式：表示被采集信号 \(x(t)\) 可以由具有不同频率（\(2\pi n f_1\)）和幅值（\(X(2\pi n f_1)\)）的周期信号叠加得到。

傅里叶变换对第二式：为傅里叶变换，表示不同频率分量前的系数，可以理解为，该频率分量在被采集信号中的占比。

傅里叶变换的目的：得到被采集信号包含的频率成分和每个频率成分在原信号中的占比，用图形表示则为频谱图。

离散傅里叶变换对应的是在时域、频域都有限长，且都是离散的一类变换。

现有一个时域模拟信号 \(x(t)\)，对其进行采样，采样长度为 \(T\), 采样点有 \(N\) 个，采样时间间隔为 \(\Delta t\)。

则采样长度与采样点的关系为：

\[ T=N\Delta t \]

采样频率为：

\[ f_s = \frac{1}{\Delta t} \]

频谱的基频是\(f_1\)，即：

\[ f_1=\frac{1}{T} \]

根据傅里叶变换公式，由傅里叶变换求得的频谱谱线都是基频的整数倍，即频谱谱线的间隔：

\[ \Delta f=f_1=\frac{1}{T} = \frac{1}{N\Delta t} \]

记采样得到的离散的时域数字信号为\(x(k\Delta t)\)，把傅里叶变换式中的连续变量替换为离散变量

\[ t=k\Delta t,\quad 2\pi nf_1=2\pi n \Delta f \]

再将\(T=N\Delta t\)带入傅里叶变换对，对时间积分变为有限时间段内求和，即，\(\int \rightarrow \sum\)，\(dt\rightarrow\Delta t\)，得到：

\[ x(k\Delta t) = x(k)= \sum^{N-1}_ {n=0} X(2\pi n \Delta f) e^{ j 2\pi n k / N } \]

\[ X(2\pi n \Delta f) =X(n)= \frac{1}{N} \sum^{N-1}_ {k=0} x(k\Delta t) e^{ -j 2\pi n k /N} \]

习惯上将标定因子 \(N\) 移至反变换式中去，并且用 \(n\) 表示第 \(n\) 个采样点，用 \(k\) 表示第 \(k\) 条谱线（频率分量），即将上式中 \(n\) 和 \(k\) 的位置互换。总结上述结论有：

\[ x(n) = \frac{1}{N} \sum^{N-1}_ {n=0} X(k) e^{ j 2\pi n k / N } \]

\[ X(k) = \sum^{N-1}_ {k=0} x(n) e^{ -j 2\pi n k /N} \]

上式就是离散傅里叶变换式。式中：

\[ k= 0,1,2\dots,N-1; \quad n= 0,1,2\dots,N-1 \]

根据离散傅里叶变换式可以求出第 \(n\) 条谱线对应的傅里叶系数的值，即该频率分量在整个信号中的占比。

我们注意到离散傅里叶变换式中求和符号的上下限改变了，不再是正负无穷。再改为正负无穷可以吗？改了之后两个公式含义还一样吗？答案是一样的，要用采样定理回答该问题。虽然标注是无穷，但是采样频率一定要大于2倍的被采样信号最高频率：

\[ f_s=\frac{1}{\Delta t}>2f_m \]

当采样频率已经确定为 \(1/ \Delta t\) 时，满足采样定理的 \(x(t)\) 的最高频率分量是：

\[ f_m