傅里叶变换是一种线性积分变换，用于信号在时域和频域之间的变换。由法国学者约瑟夫·傅里叶系统地提出，所以以其名字来命名以示纪念。本文主要讲解傅里叶变换的公式推导和快速傅里叶变换算法的原理及实现。
笔者并没有在课程中学习过傅里叶变换，最初的基础仅仅是高数中讲到的傅里叶级数。由于项目需要，查阅了大量资料自学了傅里叶变换，学习过程中有一些较难理解的地方，而且感觉其中的一些东西容易忘记，于是决定记录下来，以备后患。
Let’s Go!!!
傅里叶变换的公式推导
三角函数的正交性
傅里叶变换的公式推导需要一些基础性的知识，三角函数的正交性便是其中的关键。
何为三角函数的正交性？
在线性代数中，向量正交指两个向量内积为0。而三角函数的正交指在三角函数系中，任意两个不同的函数乘积在区间的积分为0。当然这个区间是有限制的，区间大小必须是三角函数周期的整数倍。
例如：
- $\int_{-\pi}^{\pi} sin(nx)cos(mx) = 0$
- $\int_{-\pi}^{\pi} sin(nx)sin(mx) = 0, n \ne m$
- $\int_{-\pi}^{\pi} cos(nx)cos(mx) = 0, n \ne m$
上面提到的$m,n$均为整数。
证明
这里需要用到三角函数的积化和差公式：
- $sin(\alpha)cos(\beta) = \frac{1}{2}(sin(\alpha + \beta) + sin(\alpha - \beta))$
- $cos(\alpha)cos(\beta) = \frac{1}{2}(cos(\alpha + \beta) + cos(\alpha - \beta))$
- $sin(\alpha)sin(\beta) = -\frac{1}{2}(cos(\alpha + \beta) - cos(\alpha - \beta))$
当$m \ne n$时:
$$
\begin{align}
&\int_{-\pi}^{\pi} sin(nx)sin(mx)\\\
&= \int_{-\pi}^{\pi} (\frac{1}{2}[cos(nx - mx) - cos(nx + mx)]) \\\
&= \int_{-\pi}^{\pi} \frac{1}{2}cos(n-m)x + \int_{-\pi}^{\pi} \frac{1}{2}cos(m+n)x \\\
&= 0 \\\
\end{align}
$$
而当$m = n$时，不满足正交性。
积分的结果为：
- $\int_{-\pi}^{\pi} sin(nx)sin(nx) = \pi$
- $\int_{-\pi}^{\pi} cos(nx)cos(nx) = \pi$
这个可以用半角公式证明：
$$
\begin{align}
&\int_{-\pi}^{\pi} sin(nx)sin(nx) dx \\\
&= \int_{-\pi}^{\pi} \frac{1 - cos(2nx)}{2} dx\\\
&= \int_{-\pi}^{\pi} \frac{1}{2} + \int_{-\pi}^{\pi} \frac{-cos(2nx)}{2} dx \\\\
&= \pi
\end{align}
$$
傅里叶级数
OK, 到这里我们既可以说一说傅里叶级数了。What is Fourier series？
傅里叶级数可以用来表示任意一个周期函数。
对于一个周期函数 $f(x) = f(x + T),\ T = \frac{2\pi}{\omega}$，
其傅里叶级数为
$$f(x) = \frac{a_0}{2} + \Sigma_{n=1}^{\infty}(a_n cos(n\omega x) + b_n sin(n\omega x))$$
其中
- $a_0 = \frac{2}{T} \int_{0}^{T} f(x) dx$
- $a_n = \frac{2}{T} \int_{0}^{T} f(x) cos(n\omega x) dx$
- $b_n = \frac{2}{T} \int_{0}^{T} f(x) sin(n\omega x) dx$
至于是怎么推导出来的这里就不说明了（其实我也不知道)。不过可以说一下$a_0, a_n, b_n$三个系数是怎么求出来的。
系数的求解
这就用到我们上面提到的三角函数正交性了。
我们选取周期为$[-\pi, \pi]$
$$
\begin{align}
& f(x) = \frac{a_0}{2} + \Sigma_{n=1}^{\infty}(a_n cos(n\omega x) + b_n sin(n\omega x)) \\\
& \int_{-\pi}^{\pi} f(x)dx = \int_{-\pi}^{\pi} \frac{a_0}{2} dx + \int_{-\pi}^{\pi} (\Sigma_{n=1}^{\infty}(a_n cos(n\omega x) + b_n sin(n\omega x))) dx \\\
& \int_{-\pi}^{\pi} f(x)dx = \int_{-\pi}^{\pi} \frac{a_0}{2} dx + \Sigma_{n=1}^{\infty} \int_{-\pi}^{\pi} (a_n cos(n\omega x))dx + \Sigma_{n=1}^{\infty} \int_{-\pi}^{\pi} (b_n sin(n\omega x)) dx \\\
& \int_{-\pi}^{\pi} f(x)dx = a_0 \cdot \pi + 0 + 0
\end{align}
$$
所以，$a_0 = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) dx$
$a_n$的证明稍微麻烦一点,需要一个小小的技巧。
$$
\begin{align}
& f(x) = \frac{a_0}{2} + \Sigma_{n=1}^{\infty}(a_n cos(n\omega x) + b_n sin(n\omega x)) \\\
& f(x)cos(m\omega x) = \frac{a_0}{2}cos(m\omega x) + \Sigma_{n=1}^{\infty}(a_n cos(n\omega x) + b_n sin(n\omega x))cos(m\omega x) \\\
& \int_{-\pi}^{\pi} f(x)cos(m\omega x)dx = \int_{-\pi}^{\pi} \frac{a_0}{2} cos(m\omega x)dx \\\
& + \int_{-\pi}^{\pi} (\Sigma_{n=1}^{\infty}(a_n cos(n\omega x)cos(m\omega x) + b_n sin(n\omega x))) cos(m\omega x)dx \\\
\end{align}
$$
机智如你，一定想到了为什么要多乘一个$cos(m\omega x)$。对，这样就可以让$a_0, b_n$消失，只剩下我们需要的$a_n$。
我们继续
$$
\begin{align}
& \int_{-\pi}^{\pi} f(x)cos(m\omega x)dx = 0 + \Sigma_{n=1}^{\infty} \int_{-\pi}^{\pi} (a_n cos(n\omega x) cos(m\omega x))dx + 0\\\
& \int_{-\pi}^{\pi} f(x)cos(m\omega x)dx = \Sigma_{n=1}^{\infty} \int_{-\pi}^{\pi} (a_n cos(n\omega x) cos(m\omega x))dx\\\
\end{align}
$$
其实这里的系数$a_n$也只有一个能保留下来，那就是当$m = n$时。
$$
\begin{align}
& \int_{-\pi}^{\pi} f(x)cos(m\omega x)dx = \Sigma_{n=1}^{\infty} \int_{-\pi}^{\pi} (a_n cos(n\omega x) cos(m\omega x))dx\\\
& \int_{-\pi}^{\pi} f(x)cos(n\omega x)dx = a_n \int_{-\pi}^{\pi} (cos(n\omega x) cos(n\omega x))dx\\\
& \int_{-\pi}^{\pi} f(x)cos(n\omega x)dx = a_n \pi\\\
\end{align}
$$
可以解得：$a_n = \frac{1}{\pi} \int_{0}^{T} f(x) cos(n\omega x) dx$。$b_n$的求解这里就不进行赘述了，与$a_n$同理。
将$a_0, a_n, b_n$推广到任意周期，即可得到上面的结果：
- $a_0 = \frac{2}{T} \int_{0}^{T} f(x) dx$
- $a_n = \frac{2}{T} \int_{0}^{T} f(x) cos(n\omega x) dx$
- $b_n = \frac{2}{T} \int_{0}^{T} f(x) sin(n\omega x) dx$
傅里叶级数的意义
$$f(x) = \frac{a_0}{2} + \Sigma_{n=1}^{\infty}(a_n cos(n\omega x) + b_n sin(n\omega x))$$
从这个公式中我们可以看到，一个周期函数可以由一个常函数和无穷多个正弦函数和余弦函数叠加而成。
其中$n\omega$表示这些正弦函数和余弦函数的角频率是周期函数角频率的整数倍。
欧拉公式
傅里叶变换只能表示周期性函数，但是现实世界中周期性函数很少。那么问题来了，能不能表示非周期函数。答案是可以的，其实非周期性的函数就是一个周期无穷大的函数。
开始之前，仍然需要一个预备知识——欧拉公式(Euler formula)。让我们见识一下这个号称数学界最美的公式。
初见惊为天人，其形也，翩若惊鸿，婉若游龙。荣曜秋菊，华茂春松。
$$e^{i\theta} = cos\theta + isin\theta$$
再见则细思恐极。
当$\theta = \pi$时，$e^{i\pi} + 1 = 0$，这便是欧拉恒等式。
是不是感觉数学中最基本的符号和数字都被包含在这个等式中，一切浑然天成！
其实吧，我们只想要从中得到下面的两个公式：
- $cos\theta = \frac{1}{2}(e^{i\theta} + e^{-i\theta})$
- $sin\theta = -\frac{1}{2}i(e^{i\theta} - e^{-i\theta})$
傅里叶级数的复指数形式
将$cos\theta,sin\theta$替换之后，我们便得到了傅里叶级数的复指数形式：
$$
\begin{align}
& f(x) = \frac{a_0}{2} + \Sigma_{n=1}^{\infty}(a_n
cos(n\omega x) + b_n sin(n\omega x)) \\\
&= \frac{a_0}{2} + \Sigma_{n=1}^{\infty}(a_n \frac{1}{2}(e^{in\omega x} + e^{-in\omega x}) - b_n \frac{1}{2}i(e^{in\omega x} - e^{-in\omega x})) \\\
&= \frac{a_0}{2} + \Sigma_{n=1}^{\infty}a_n \frac{1}{2}(e^{in\omega x} + e^{-in\omega x}) - \Sigma_{n=1}^{\infty}b_n \frac{1}{2}i(e^{in\omega x} - e^{-in\omega x})) \\\
&= \frac{a_0}{2} + \Sigma_{n=1}^{\infty} \frac{1}{2}(a_n - b_n i)e^{in\omega x} + \Sigma_{n=1}^{\infty} \frac{1}{2}(a_n + b_n i)e^{-in\omega x} \\\
& = \Sigma_{0}^{0} \frac{a_0}{2} e^{i0\omega x} + \Sigma_{n=1}^{\infty} \frac{1}{2}(a_n - b_n i)e^{in\omega x} + \Sigma_{n=- \infty}^{-1} \frac{1}{2}(a_{-n} + b_{-n} i)e^{in\omega x} \\\
&= \Sigma_{n=-\infty}^{\infty} C_n e^{in\omega x}
\end{align}
$$
其中
$$
C_n =\left \{
\begin{align}
& \frac{a_0}{2}, n = 0\\\
& \frac{1}{2}(a_n - b_n i), n > 0\\\
& \frac{1}{2}(a_{-n} + b_{-n} i), n<0\\\
\end{align}
\right.
$$
接下来我们求$C_n$.
我们已知
$$
\left\{
\begin{align}
& a_0 = \frac{2}{T} \int_{0}^{T} f(x) dx\\\
& a_n = \frac{2}{T} \int_{0}^{T} f(x) cos(n\omega x) dx\\\
& b_n = \frac{2}{T} \int_{0}^{T} f(x) sin(n\omega x) dx\\\
\end{align}
\right.
$$
当$n = 0$时
$$
\begin{align}
& C_0 = \frac{a_0}{2} = \frac{1}{T} \int_{0}^{T} f(x) dx\\\
\end{align}
$$当$n > 0$时
$$
\begin{align}
C_n &= \frac{1}{2}(a_n - b_n i)\\\
& = \frac{1}{2} \frac{2}{T} \int_{0}^{T} f(x) cos(n\omega x)dx - \frac{1}{2}i\frac{2}{T} \int_{0}^{T} f(x) sin(n\omega x) dx\\\
& = \frac{1}{T} \int_{0}^{T} f(x) cos(n\omega x) - i \cdot sin(n\omega x) dx\\\
& = \frac{1}{T} \int_{0}^{T} f(x) e^{-in\omega x} dx\\\
\end{align}
$$当$n < 0$时
$$
\begin{align}
C_n &= \frac{1}{2}(a_{-n} + b_{-n} i)\\\
& = \frac{1}{2} \frac{2}{T} \int_{0}^{T} f(x) cos(-n\omega x)dx + \frac{1}{2}i\frac{2}{T} \int_{0}^{T} f(x) sin(-n\omega x) dx\\\
& = \frac{1}{T} \int_{0}^{T} f(x) cos(-n\omega x) + i \cdot sin(-n\omega x) dx\\\
& = \frac{1}{T} \int_{0}^{T} f(x) e^{-in\omega x} dx\\\
\end{align}
$$
咦！$n>0$和$n<0$时，$C_n$居然是一样的，如果$n=0$时也一样那就Prefect了！
下面是见证奇迹的时刻！
$$
\begin{align}
C_0 &= \frac{1}{T} \int_{0}^{T} f(x) dx\\\
& = \frac{1}{T} \int_{0}^{T} f(x) e^{-i0\omega x} dx\\\
\end{align}
$$
$C_n$的形式居然统一了，$C_n = \frac{1}{T} \int_{0}^{T} f(x) e^{-in\omega x} dx$。
到此，转换到复指数形式之后，傅里叶级数就看起来简单多了。 $$ f(x)= \Sigma_{n=-\infty}^{\infty} \frac{1}{T} \int_{0}^{T} f(x) e^{-in\omega x} dx \ e^{in\omega x} $$
连续傅里叶变换
对于非周期函数（可视为周期为无穷的函数）$f(x) = f(x + T), T \to \infty$
在周期函数中，$\omega = \frac{2\pi}{T}$ 表示角频率。$n\omega$表示正弦函数和余弦函数的角频率是该周期函数角频率的整数倍。
但是当$T \to \infty$时， $\omega \to 0$。$n\omega$表示的含义则是$n\omega$变成了一个连续的量（之前是离散的）。
也就是说非周期函数仍然可以由一个常函数和无穷多个正弦函数和余弦函数叠加而成。但是这些正弦函数和余弦函数的角频率变得特别密集，充斥在整个实数轴上。
为了表示方便，我们用$\omega$代替$n\omega$。则$T$可以表示为$\frac{\Delta \omega}{2\pi}$
于是，傅里叶变换的公式就诞生了。真是千呼万唤始出来呀！
$$\begin{align}
f(x)
&= \Sigma_{n=-\infty}^{\infty} \frac{\Delta \omega}{2\pi} \int_{-\infty}^{\infty} f(x) e^{-i\omega x} dx \ e^{i\omega x}\\\
&= \int_{-\infty}^{\infty} \frac{1}{2\pi} \int_{-\infty}^{\infty} f(x) e^{-i\omega x} dx \ e^{i\omega x} d\omega\\\
&= \frac{1}{2\pi} \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} f(x) e^{-i\omega x} dx \ e^{i\omega x} d\omega\\\
\end{align}
$$
令$F(\omega) = \int_{-\infty}^{\infty} f(x) e^{-i\omega x} dx$，该式即为傅里叶变换。
则$f(x) = \frac{1}{2\pi} \int_{-\infty}^{\infty} F(\omega) \ e^{i\omega x} d\omega$，称为傅里叶变换的逆变换 。
傅里叶变换公式的含义
一个时域内的函数$f(x)$经过傅里叶变换之后，得到了一个频域内的函数$F(\omega)$。给定一个$\omega$，就可以得到一个$F(\omega)$，$F(\omega)$表示函数$f(x)$在对应频率的振幅。由于$\omega \in (-\infty, \infty)$，所以可以得到无穷多个$F(\omega)$。
傅里叶变换的逆变换公式的含义
对得到的无穷多个$F(\omega)$积分由重新得到了原函数$f(x)$。说明了$f(x)$可以由这无穷多个函数叠加而成。这与之前的傅里叶级数表示的意义是相同的。
离散傅里叶变换（DFT）
由于傅里叶变换经常用于信号的处理，将一个信号拆分成多个正弦信号的叠加。但是由于信号需要使用计算机处理，计算机只能处理离散的数据，所以需要将傅里叶变换离散化。
傅里叶变换中$\omega$是一个连续的量，而实际的信号处理中 $\omega$的值是根据输入信号的采集频率确定的。
令T表示采样周期，N表示采样次数。对于一个输入为N个点的离散序列$x[n], 0 \le n \lt N$
其离散傅里叶变换为：
$$\bar {x}[k] = \Sigma_{n=0}^{N-1} (x[n] \cdot e^{-i\frac{2 \pi n}{N} k})
$$
逆变换为：
$$x[n] = \frac{1}{N} \Sigma_{k=0}^{N-1} \bar {x}[k] \cdot e^{i\frac{2\pi k}{N} n}
$$
其中$\frac{2\pi n}{N}$为角频率
具体证明比较复杂，此处不进行叙述。
快速傅里叶变换原理
快速傅里叶变换算法实现
递归
迭代
Ending
