Fourier Series, Fourier Transform, DFT, FFT

后文会用到复数，这里回顾一下关于复数的基本知识。

复数 \(C\) 的定义如下： \[C = R + jI\] 其中， \(R\) 和 \(I\) 是实数， \(R\) 表示复数的实部， \(I\) 表示复数的虚部。 \(j\) 是虚数单位，即 \(j= \sqrt{-1}\) （注：数字上常用 \(i\) 表示虚数单位，这里用 \(j\) 是按照电工学中通常的习惯）。

一个复数 \(C\) 的共轭(Complex conjugate)表示为 \(C^{*}\) ，其定义为：\[C^{*} = R - jI\] 复数从几何的角度可以被看成是平面（称为复平面）上的一个点，其横坐标是实轴（ \(R\) 的值），其纵坐标是虚轴（ \(I\) 的值）。也就是说，复数 \(R + jI\) 是复平面直角坐标系统中的点 \((R,I)\) 。

有时，在极坐标下表示复数很有用： \[C = |C| (\cos \theta + j \sin \theta)\] 其中， \(|C|=\sqrt{R^2 + I^2}\) 是复平面的原点到点 \((R,I)\) 的向量的长度， \(\theta\) 是该向量与实轴的夹角。

利用欧拉公式(Euler’s formula)： \[e^{j\theta} = \cos \theta + j \sin \theta\] 极坐标下复数又可以表示（称为指数形式的表示）为： \[C = |C| e^{j \theta}\]

例如，复数 \(1 + j2\) 的极坐标表示是 \(\sqrt{5} e^{j \theta}\) ，其中 \(\theta=64.4^{\circ}\) 。

前面的公式还可以用于复函数。例如，变量 \(u\) 的复函数 \(F(u)\) 可表示为 \(F(u) = R(u) + jI(u)\) ，其中 \(R(u)\) 和 \(I(u)\) 分别是实分量函数和虚分量函数。复共轭函数是 \(F^{*}(u) = R(u) - jI(u)\) 。

法国数字家傅里叶发现， 具有周期 \(T\) 的连续变量 \(t\) 的周期函数 \(f(t)\) 可以被描述为乘以适当系数的正弦和余弦和。 这个和就是傅里叶级数，它具有如下形式：

\begin{align*} f(t) &= a_0 + a_1 \cos(\frac{2 \pi}{T} t) + b_1 \sin(\frac{2 \pi}{T} t) + a_2 \cos(2 \frac{2 \pi}{T} t) + b_2 \sin(2 \frac{2 \pi}{T} t) + \cdots + a_n \cos(n \frac{2 \pi}{T} t) + b_n \sin(n \frac{2 \pi}{T} t) \\ &= a_0 + \sum_{n=1}^{\infty} \left[a_n \cos(n \frac{2 \pi}{T} t) + b_n \sin (n \frac{2 \pi}{T} t) \right] , \qquad (n = 1,2,\cdots) \tag{傅里叶级数的三角形式} \\ \end{align*}

其中，各个系数可按以下各式计算。
直流分量：
\[a_0 = \frac{1}{T} \int_{t_0}^{t_0 + T}f(t) \, \mathrm{d}t\]
余弦分量的幅度：
\[a_n = \frac{2}{T} \int_{t_0}^{t_0 + T}f(t) \cos(n \frac{2 \pi}{T} t) \, \mathrm{d}t , \qquad (n = 1,2,\cdots)\]
正弦分量的幅度：
\[b_n = \frac{2}{T} \int_{t_0}^{t_0 + T}f(t) \sin(n \frac{2 \pi}{T} t) \, \mathrm{d}t , \qquad (n = 1,2,\cdots)\]
为方便起见，通常积分区间 \(t_0 \sim t_0 + T\) 取为 \(0 \sim T\) 或者 \(-\frac{T}{2} \sim \frac{T}{2}\) 。

说明：并非任意周期信号都能进行傅里叶级数展开，需要满足一定的条件才能进行傅里叶级数展开。不过，在实践中，这些条件一般都会满足，这点不介绍这些条件。

如果将前面介绍的傅里叶级数中“同频率项合并”，傅里叶级数还可以写为另一种形式：

\begin{equation} f(t) = c_0 + \sum_{n=1}^{\infty} c_n \cos(n \frac{2 \pi}{T} t + \varphi_n) \tag{傅里叶级数的另一种常见三角形式} \end{equation}

或者写为：
\[f(t) = d_0 + \sum_{n=1}^{\infty} d_n \sin(n \frac{2 \pi}{T} t + \theta_n)\]
各个系数为（ \(a_0, a_n, b_n, n = 1,2,\cdots\) 的计算公式前面已经介绍过）：
\[\begin{aligned} & c_0 = d_0 = a_0 \\ & c_n = d_n = \sqrt{a_n^2 + b_n^2} , \qquad (n = 1,2,\cdots) \\ & \tan \varphi_n = - \frac{b_n}{a_n} \\ & \tan \theta_n = \frac{a_n}{b_n} \\ \end{aligned}\]

通常把频率为 \(1/T\) （此时角频率为 \(\frac{2 \pi}{T}\) ， \(n=1\) ）的分量称为“基波”，把频率为 \(2/T\) （角频率为 \(\frac{4 \pi}{T}\) ）、 \(3/T\) （角频率为 \(\frac{6 \pi}{T}\) ）等的分量称为“二次谐波”，“三次谐波”等。

显然，各分量幅度（ \(c_n\) 或 \(d_n\) ）及相位（ \(\varphi_n\) 或 \(\theta_n\) ）确定下来后，周期函数的傅里叶级数展开就确定了。

我们把幅度 \(c_n\) 和角频率 \(\frac{2 \pi n}{T}\) 之间的关系图称为幅度频谱（简称幅度谱），把相位 \(\varphi_n\) 和角频率 \(\frac{2 \pi n}{T}\) 之间的关系图称为相位频谱（简称相位谱）。

不过，很多时候，相位谱不是很重要，常常直接忽略它。

设周期函数 \(f(t)\) 的周期为 \(T\) ，记其角频率 \(\omega_1 = 2 \pi / T\) ，下面将从傅里叶级数的基本定义推导出傅里叶级数的指数形式。
由欧拉公式可知 \(\cos(n \omega_1 t) = \frac{1}{2} (e^{j n \omega_1 t} + e^{- j n \omega_1 t}), \, \sin(n \omega_1 t) = \frac{1}{2j} (e^{j n \omega_1 t} - e^{- j n \omega_1 t})\) ，把这两个式子代入到前面介绍的傅里叶级数基本定义中，有：
\[\begin{aligned} f(t) &= a_0 + \sum_{n=1}^{\infty} \left[a_n \cos(n \omega_1 t) + b_n \sin (n \omega_1 t) \right] \\ &= a_0 + \sum_{n=1}^{\infty} \left( a_n \frac{e^{j n \omega_1 t} + e^{- j n \omega_1 t}}{2} + b_n \frac{e^{j n \omega_1 t} - e^{- j n \omega_1 t}}{2j} \right) \\ &= a_0 + \sum_{n=1}^{\infty} \left( \frac{1}{2} (a_n - j b_n) e^{j n \omega_1 t} + \frac{1}{2} (a_n + j b_n) e^{- j n \omega_1 t} \right) \\ \end{aligned}\]

令 \(F(n \omega_1) = \frac{1}{2} (a_n - j b_n)\) ，由于 \(a_n\) 是 \(n\) 的偶函数， \(b_n\) 是 \(n\) 的奇函数，可知 \(F(- n \omega_1) = \frac{1}{2} (a_n + j b_n)\) ，从而上式可接着变形为：
\[f(t) = a_0 + \sum_{n=1}^{\infty} \left( F(n \omega_1) e^{j n \omega_1 t} + F (- n \omega_1) e^{- j n \omega_1 t} \right)\]
令 \(F(0) = a_0\) ，考虑到： \(\sum_{n=1}^{\infty} F (- n \omega_1) e^{- j n \omega_1 t} = \sum_{n=-1}^{-\infty} F (n \omega_1) e^{j n \omega_1 t}\) ，从而上式可接着变形为：
\[f(t) = \sum_{n=- \infty}^{\infty}F(n \omega_1) e^{j \omega_1 t}\]
一般我们把 \(F(n \omega_1)\) 简写为 \(F_n\) ，上式即为 周期函数 \(f(t)\) （设周期为 \(T\) ）的傅里叶级数的指数形式 ：

\begin{equation} f(t) = \sum_{n=- \infty}^{\infty}F_n e^{j \omega_1 t} \tag{傅里叶级数的指数形式} \end{equation}

其中，
\[\begin{aligned} \omega_1 & = \frac{2 \pi}{T} \\ F_n & = \frac{1}{T} \int_{t_0}^{t_0 + T}f(t) e^{-j n \omega_1 t} \, \mathrm{d}t, \qquad (n = 0, \pm 1, \pm 2, \cdots) \\ \end{aligned}\]
通常积分区间 \(t_0 \sim t_0 + T\) 取为 \(0 \sim T\) 或者 \(-\frac{T}{2} \sim \frac{T}{2}\) 。

显然，如果给出 \(F_n\) ，则 \(f(t)\) 唯一确定。在傅里叶级数的指数形式中傅里叶系数 \(F_n\) 不再是实数，而是复数，有模有辐角。

注： \(F_n\) 的推导过程如下： \(F_n = \frac{1}{2} (a_n - j b_n) = \frac{1}{T} \int_{t_0}^{t_0 + T} f(t) \cos (n \omega_1 t) \, \mathrm{d}t -j \frac{1}{T} \int_{t_0}^{t_0 + T} f(t) \sin (n \omega_1 t) \, \mathrm{d}t = \frac{1}{T} \int_{t_0}^{t_0 + T}f(t) e^{-j n \omega_1 t} \, \mathrm{d}t, \quad (n = 0, \pm 1, \pm 2, \cdots)\)

傅里叶级数的指数形式中系数 \(F_n\) 和傅里叶级数的三角形式中的幅度 \(c_n\) 和相位 \(\varphi_n\) 的关系如下：
\[\begin{aligned} & F_0 = c_0 \\ & F_n = |F_n| e^{j \varphi_n} , \quad (n = 1, 2, \cdots) \\ & F_{-n} = |F_{-n}| e^{-j \varphi_n} , \quad (n = 1, 2, \cdots) \\ & |F_n| = |F_{-n}| = \frac{1}{2} c_n , \quad (n = 1, 2, \cdots) \\ \end{aligned}\]

设周期矩形脉冲信号（又称为方波信号） \(f(t)\) 的脉冲宽度为 \(\tau\) ，脉冲幅度为 \(E\) ，重复周期为 \(T\) （显然角频率 \(\omega_1 = 2 \pi/T\) ），如图 5 所示。求其傅里叶频谱。

直流分量 \(a_0\) ，余弦分量的幅度 \(a_n\) ，正弦分量的幅度 \(b_n\) 分别计算如下。
\[\begin{aligned} a_0 &= \frac{1}{T} \int_{-T/2}^{T/2} f(t) \, \mathrm{d}t = \frac{1}{T} \int_{-T/2}^{T/2} E \, \mathrm{d}t = \frac{E \tau}{T} \\ a_n &= \frac{2}{T} \int_{-T/2}^{T/2} f(t) \cos(n \omega_1 x) \, \mathrm{d}t = \frac{2E}{n \pi} \sin \left( \frac{n \pi \tau}{T} \right) , \qquad (n = 1,2,\cdots) \\ b_n &= \frac{2}{T} \int_{-T/2}^{T/2} f(t) \sin(n \omega_1 x) \, \mathrm{d}t = 0, \qquad (n = 1,2,\cdots) \\ \end{aligned}\]
从而可求得 \(c_0, c_n, \varphi_n \, (n=1,2,\cdots)\) 以及 \(F_n , \, (n = 0, \pm 1, \pm 2, \cdots)\) 。

其指数形式傅里叶级数幅度和相位如图 6 所示。

由于， \(F_n\) 在这个例子中恰为实数（一般情况 \(F_n\) 为复数），此时相位不是 0 就是 \(\pi\) ，可以用 \(F_n\) 的正负分别表示相位 \(\varphi_n\) 为 0 和 \(\pi\) ，这时我们可以把幅度谱和相位谱画在同一张图上，如图 7 所示。

由前面的分析知，通过极限的方法，我们可以从周期信号的傅里叶级数导出非周期信号频谱的表示式，这称为傅里叶变换(Fourier transform)。在这里，不严格推导，直接给出非周期信号傅里叶变换的公式。

非周期信号 \(f(t)\) 的傅里叶变换为：

\begin{equation} F(\omega) = \mathscr{F}[f(t)] = \int_{- \infty}^{\infty} f(t) e^{-j \omega t} \, \mathrm{d}t \tag{傅里叶变换} \end{equation}

对应的傅里叶逆变换为：

\begin{equation} f(t) = \mathscr{F}^{-1}[F(\omega)] = \frac{1}{2 \pi} \int_{- \infty}^{\infty} F(\omega) e^{-j \omega t} \, \mathrm{d}t \tag{傅里叶逆变换} \end{equation}

式中， \(F(\omega)\) 是 \(f(t)\) 的频谱函数，它一般是复函数，可以写作：
\[F(\omega) = |F(\omega)| e^{j \varphi(\omega)}\]
其中 \(|F(\omega)|\) 是 \(F(\omega)\) 的模，它代表信号中各频率分量的相对大小， \(\varphi(\omega)\) 是 \(F(\omega)\) 的相位函数，它表示信号中各频率分量之间的相位关系。类似地， \(|F(\omega)| \sim \omega\) 与 \(\varphi(\omega) \sim \omega\) 曲线分别称为非周期信号的幅度频谱与相位频谱。

已知，单边指数信号的表示式为：
\[f(t) = \begin{cases} e^{-at} & (t \ge 0) \\ 0 & (t<0) \end{cases}\]
其中 \(a\) 为正实数。

单边指数信号的傅里叶变换推导如下：
\[\begin{aligned} F(\omega) &= \int_{- \infty}^{\infty} f(t) e^{-j \omega t} \, \mathrm{d}t \\ &= \int_{0}^{\infty} e^{-at} e^{-j \omega t} \, \mathrm{d}t \\ &= \int_{0}^{\infty} e^{(a + j \omega) t} \, \mathrm{d}t \\ &= \frac{1}{a + j \omega} \\ \end{aligned}\]
从而：
\[\begin{aligned} & |F(\omega)| = \frac{1}{\sqrt{a^2 + \omega^2}} \\ & \varphi(\omega) = - \arctan \left(\frac{\omega}{a} \right) \\ \end{aligned}\]
单边指数信号的波形及频谱如图 9 所示。

对于任意两个信号 \(f_1(t)\) 和 \(f_2(t)\) ，两者做卷积运算定义为：
\[f_1(t) \ast f_2(t) = \int_{- \infty}^{\infty} f_1(\tau) f_2(t - \tau)\, \mathrm{d} \tau\]

时域卷积定理：
设函数 \(f_1(t)\) 和 \(f_2(t)\) 的傅里叶变换为 \(F_1(\omega)\) 和 \(F_2(\omega)\) ，则：

\begin{equation} \mathscr{F}[f_1(t) \ast f_2(t)] = F_1(\omega) \cdot F_2(\omega) \tag{时域卷积定理} \end{equation}

证明如下：
\[\begin{aligned} \mathscr{F}[f_1(t) \ast f_2(t)] & = \int_{- \infty}^{\infty} \left[ \int_{- \infty}^{\infty} f_1(\tau) f_2(t - \tau)\, \mathrm{d} \tau \right] e^{-j \omega t} \, \mathrm{d}t \\ &= \int_{- \infty}^{\infty} f_1(\tau) \left[ \int_{- \infty}^{\infty} f_2(t - \tau) e^{-j \omega t} \, \mathrm{d} t \right] \, \mathrm{d} \tau \\ &= \int_{- \infty}^{\infty} f_1(\tau) F_2(\omega) e^{-j \omega t} \, \mathrm{d} \tau \\ &= F_2(\omega) \int_{- \infty}^{\infty} f_1(\tau) e^{-j \omega t} \, \mathrm{d} \tau \\ &= F_2(\omega) \cdot F_1(\omega) \\ \end{aligned}\]
它说明： 时域中两信号的卷积等效于在频域中频谱相乘。

频域卷积定理：

\begin{equation} \mathscr{F}[f_1(t) \cdot f_2(t)] = \frac{1}{2 \pi} F_1(\omega) \ast F_2(\omega) \tag{频域卷积定理} \end{equation}

频域卷积定理的证明过程和时域卷积定理的证明过程类似，这里不再重复。

前面介绍的离散傅里叶变换及逆变换的公式可以写为矩阵形式。
离散傅里叶变换的矩阵形式：
\[\begin{bmatrix} X(0) \\ X(1) \\ \vdots \\ X(N-1) \end{bmatrix} = \begin{bmatrix} W^0 & W^0 & W^0 & \cdots & W^0 \\ W^0 & W^{1 \times 1} & W^{2 \times 1} & \cdots & W^{(N-1) \times 1} \\ \vdots & \vdots & \vdots & & \vdots \\ W^0 & W^{1 \times (N-1)} & W^{2 \times (N-1)} & \cdots & W^{(N-1) \times (N-1)} \end{bmatrix} \begin{bmatrix} x(0) \\ x(1) \\ \vdots \\ x(N-1) \\ \end{bmatrix}\]

离散傅里叶逆变换的矩阵形式：
\[\begin{bmatrix} x(0) \\ x(1) \\ \vdots \\ x(n-1) \end{bmatrix} = \frac{1}{N} \begin{bmatrix} W^0 & W^0 & W^0 & \cdots & W^0 \\ W^0 & W^{-1 \times 1} & W^{-1 \times 2} & \cdots & W^{-1 \times (N-1)} \\ \vdots & \vdots & \vdots & & \vdots \\ W^0 & W^{-(N-1) \times 1} & W^{- (N-1) \times 2} & \cdots & W^{-(N-1) \times -(N-1)} \end{bmatrix} \begin{bmatrix} X(0) \\ X(1) \\ \vdots \\ X(N-1) \\ \end{bmatrix}\]

上面两个公式简写为：

\begin{equation} \boldsymbol{X}(k) = \boldsymbol{W}^{nk} \boldsymbol{x}(n) \tag{离散傅里叶变换的矩阵形式} \end{equation}

和

\begin{equation} \boldsymbol{x}(n) = \frac{1}{N} \boldsymbol{W}^{-nk} \boldsymbol{X}(k) \tag{离散傅里叶逆变换的矩阵形式} \end{equation}

此处， \(\boldsymbol{X}(k)\) 与 \(\boldsymbol{x}(n)\) 分别为 \(N\) 列的列矩阵，而 \(\boldsymbol{W}^{nk}\) 与 \(\boldsymbol{W}^{-nk}\) 分别为 \(N \times N\) 方阵（这两个方阵都是对称矩阵）。

例：求 \(x(n) = \{1,1,1,1 \}\) （如图 10 (a)所示）的离散傅里叶变换，再由离散傅里叶逆变换求得 \(x(n)\) ，验证结果的正确性。
由 \(N=4\) 得到 \(W^1 = e^{-j (2 \pi/4)} = -j\) ，直接应用离散傅里叶变换公式，有：
\[\begin{aligned} \begin{bmatrix} X(0) \\ X(1) \\ X(2)\\ X(3) \end{bmatrix} &= \begin{bmatrix} W^0 & W^0 & W^0 & W^0 \\ W^0 & W^1 & W^2 & W^3 \\ W^0 & W^2 & W^4 & W^6 \\ W^0 & W^3 & W^6 & W^9 \end{bmatrix} \begin{bmatrix} x(0) \\ x(1) \\ x(2) \\ x(3) \end{bmatrix} \\ &= \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 4 \\ 0 \\ 0 \\ 0 \end{bmatrix} \\ \end{aligned}\]

离散傅里叶逆变换为：
\[\begin{bmatrix} x(0) \\ x(1) \\ x(2)\\ x(3) \end{bmatrix} = \frac{1}{4} \begin{bmatrix} W^0 & W^0 & W^0 & W^0 \\ W^0 & W^{-1} & W^{-2} & W^{-3} \\ W^0 & W^{-2} & W^{-4} & W^{-6} \\ W^0 & W^{-3} & W^{-6} & W^{-9} \end{bmatrix} \begin{bmatrix} 4 \\ 0 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}\]
显然，通过离散傅里叶逆变换可求得原始信号。

说明：在这个例子中，离散傅里叶变换得到的序列恰好都为实数。不过，离散傅里叶变换得到的序列一般为复数，比如 \(x(n) = \{1,2,3,4 \}\) 的离散傅里叶变换是一个复数序列，计算如下：
\[\begin{aligned} \begin{bmatrix} X(0) \\ X(1) \\ X(2)\\ X(3) \end{bmatrix} &= \begin{bmatrix} W^0 & W^0 & W^0 & W^0 \\ W^0 & W^1 & W^2 & W^3 \\ W^0 & W^2 & W^4 & W^6 \\ W^0 & W^3 & W^6 & W^9 \end{bmatrix} \begin{bmatrix} x(0) \\ x(1) \\ x(2) \\ x(3) \end{bmatrix} \\ &= \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 10 \\ -2+j2 \\ -2 \\ -2-j2 \end{bmatrix} \\ \end{aligned}\]

快速傅里叶变换(Fast Fourier transform, FFT)是一种计算离散傅里叶变换的快速算法。