致EE120。

傅里叶级数和傅里叶变换是工程学领域里的一个重要工具。其思想也非常深刻：从频率的角度分析问题；把复杂函数分解成具有不同频率的分量；将函数在时域和频域之间进行转换。

傅里叶级数

连续时间傅里叶级数

傅里叶级数的核心思想是：**任何周期函数都可以展开为三角级数。**假设有一函数\(x(t)\)，其最小正周期是\(T\)，则它一定可以展开成\[x(t) = \sum_k A_k{\rm e}^{jk\omega_0t}, \tag{$*$}\]

其中，\(\omega_0={2\pi\over T}\)称为基频，\(A_k\)称为傅里叶系数。根据复指数函数的周期性，可以知道上式右边的周期是\(T\)。为方便计算，使用复指数而不是余弦或正弦函数。复指数函数与三角函数的关系由欧拉公式给出：\[{\rm e}^{j\theta} = \cos\theta + j\sin\theta.\]

一个简单的例子是取\(x(t)=\cos{\omega_0t}\)，由欧拉公式立即得到 \[\cos{\omega_0t}={1\over2}{\rm e}^{-j\omega_0t} + {1\over2}{\rm e}^{j\omega_0t}.\] 在这个展开中，\(A_k = \cases{{1\over 2} & if $k = \pm 1$, \cr 0 & else.}\)由此也可见，引入负的频率分量是有必要的。

为了工程应用的方便，用\(t\)表示自变量，其通常意义为连续的时间，并且其取值是整个实数集。而\(x\)和\(y\)通常是关于\(t\)的函数，常称为信号。

既然认定可以做\((*)\)那样的展开，那么就要问：如何确定式中的系数\(A_k\)？有人想出了一种做法：计算 \[\eqalign{ \int_T x(t){\rm e}^{-jk\omega_0t} ;{\rm d}t &= \int_T \sum_\kappa A_\kappa{\rm e}^{j(\kappa-k)\omega_0t} ;{\rm d}t \cr &= \sum_\kappa A_\kappa\int_T {\rm e}^{j(\kappa-k)\omega_0t} ;{\rm d}t \cr &= TA_k }\] 积分号的下标\(T\)表示积分在任意一个长度为\(T\)的区间内进行。最后一个等号成立源于复指数函数在一个周期上的积分\[\int_T {\rm e}^{j(\kappa-k)\omega_0t} ;{\rm d}t = \cases{T & if $\kappa = k$, \cr 0 & else.}\] 因此 \[A_k={1\over T}\int_T x(t){\rm e}^{-jk\omega_0t} ;{\rm d}t.\] 上式称为分析方程(Analysis Equation)，而与之相对的\((*)\)式则称为综合方程(Synthesis Equation)。

离散时间傅里叶级数

有时候将时间视为离散的可以带来方便。数字设备如计算机通常只能处理离散时间的信号。通常用\(n\)表示离散时间，其取值范围是整数集。用\(x[n]\)这样的记号来表示一个离散时间信号。

设有一离散时间信号\(x[n]\)，其最小正周期为\(N\)，那么沿用刚才的思想，它应当可以展开成\[x[n] = \sum_{k\in S_N} A_k {\rm e}^{jk\omega_0n}.\]

其中，\(S_N\)是任意一个包含\(N\)个连续整数的集合，常取\(S_N=\{0,1,\dots,N-1\}\)。和连续时间的情况不同，这里\(k\)的取值是有限多个，主要是因为复指数函数的周期性。

上式为综合方程。使用类似的技巧（这次是求和而不是积分），可以得到傅里叶系数： \[\eqalign{ \sum_{k\in S_N} x[n] {\rm e}^{-jk\omega_0n} &= \sum_{k\in S_N}\sum_{\kappa\in S_N} A_\kappa {\rm e}^{j(\kappa-k)\omega_0n} \cr &= \sum_{\kappa\in S_N}A_\kappa \sum_{k\in S_N} {\rm e}^{j(\kappa-k)\omega_0n} \cr &= NA_k }\] 同样，求和符号里只有一项不为零，因此最后一个等号成立。因此得到分析方程 \[A_k = {1\over N} \sum_{k \in S_N} x[n] {\rm e}^{-jk\omega_0 n}.\]

傅里叶变换

连续时间傅里叶变换

傅里叶变换将周期函数展开成了三角级数。那么自然会想，如何处理非周期的函数。非周期的函数，可以视作周期是无穷大的函数。即研究傅里叶级数在\(T\to\infty\)的表现。可想而知，当周期趋于无穷时，基频将趋于0，无限细分的求和式将会转化为积分的形式。具体而言， \[\eqalign{ x(t) &= \sum_k A_k {\rm e}^{jk\omega_0t} \cr &= \sum_k {1\over T}\left[\int_{-T/2}^{T/2} x(t) {\rm e}^{-jk\omega_0t} ;{\rm d}t\right] {\rm e}^{jk\omega_0t} \cr &= {1\over 2\pi}\sum_k \left[\int_{-\pi/\omega_0}^{\pi/\omega_0} x(t) {\rm e}^{-jk\omega_0t} ;{\rm d}t\right] {\rm e}^{jk\omega_0t} \omega_0\cr }\]

如果\(T\to\infty\)，即\(\omega_0\to 0^+\)，则 \[x(t) = {1\over 2\pi}\int_{-\infty}^\infty \left[\int_{-\infty}^\infty x(t) {\rm e}^{-j\omega t} ;{\rm d}t\right] {\rm e}^{j\omega t};{\rm d}\omega.\]

定义\(x(t)\)的傅里叶变换为 \[X(j\omega) = {\cal F}\{x(t)\} = \int_{-\infty}^\infty x(t) {\rm e}^{-j\omega t} ;{\rm d}t.\] 则 \[x(t) = {\cal F}^{-1}\{X(j\omega)\} = {1\over 2\pi}\int_{-\infty}^\infty X(j\omega) {\rm e}^{j\omega t} ;{\rm d}\omega.\]

上面两式分别称为分析方程和综合方程。\(X(j\omega)\)是\(\omega\)的函数，括号里写\(j\omega\)是为了将它和拉普拉斯变换联系起来。

由综合方程可见，非周期函数可以表示成复指数函数带权的积分，不同频率的权重则由分析方程所确定的傅里叶变换\(X(j\omega)\)决定。

综合方程也定义了傅里叶逆变换。

Dirichlet条件和Dirac函数

傅里叶曾经相信，任何函数的傅里叶级数都是存在的。因为相信这个断言，才能给出\((*)\)式，并用它导出傅里叶系数的分析方程。然而，数学总是包含各种各样的反例，\(x(t)\)的傅里叶级数若要存在，仍须满足一定的条件。这些条件由Dirichlet给出：

1. 有界；
2. 在任意有限区间内只有有限个间断点，间断点左右的极限不可以是无穷；
3. 在任意有限区间内只有有限个极值点。
4. 在一个周期内绝对可积: \(\int_T |x(t)| ;{\rm d}t < \infty\)。

对于非周期的函数，第4条可以理解为“在\((-\infty, \infty)\)上绝对可积”，而满足Dirichlet条件则表明该函数存在傅里叶变换。

尽管如此，有的时候为了工程应用的方便，在严格意义上的傅里叶变换不存在的时候，使用含有Dirac函数的表达式来表示傅里叶变换，以使其满足综合方程。

Dirac函数\(\delta(t)\)大致可以定义为阶跃函数\(u(t)=\cases{0 & if $t < 0$ \cr {1\over2} & if $t = 0$ \cr 1 & if $t > 0$}\)的导数。因此在\(t\neq0\)时处处为0，而在\(t=0\)的时刻为\(\infty\)。因此，它常常用于描述一个时间无限短但作用量有限的冲击，例如质点的密度函数。它的重要性质如下 \[\int_{-\infty}^{\infty} x(t)\delta(t) ;{\rm d}t = x(0)\] 对于任意函数\(x\)总成立。

举例而言，把\(X(j\omega) = 2\pi\delta(\omega-\omega_0)\)代入傅里叶变换的综合方程，可以得到 \[x(t) = {1\over2\pi}\int_{-\infty}^{\infty} 2\pi\delta(\omega-\omega_0) {\rm e}^{j\omega t};{\rm d}\omega = {\rm e}^{j\omega_0 t}\]

由此可以得到\[{\cal F}\{{\rm e}^{j\omega_0 t}\} = 2\pi\delta(\omega-\omega_0).\] 由欧拉公式，得\[{\cal F}\{\cos \omega_0 t\} = \pi\left[\delta(\omega-\omega_0) + \delta(\omega+\omega_0)\right].\] 取\(\omega_0 = 0\)，得\[{\cal F}\{1\} = 2\pi\delta(\omega).\] 以上便导出了一些不满足Dirichlet条件(不是绝对可积的)的函数所对应的傅里叶变换。

查表法

导数是通过极限定义的，但是，对每个函数都套用极限定义是非常麻烦的，因此我们总结导数的运算法则，并归纳一些基本函数的导数，在这样的基础上来计算更加复杂的函数的导数。

类似地，尽管一个函数的傅里叶变换总是可以由上节所述的分析方程求出，对不同的函数都计算一遍反常积分也是非常费事的。因此，更常用的办法是查阅事先计算出来的傅里叶变换表，并运用相关性质来得到所需要的傅里叶变换。

傅里叶变换表以及相关性质可以在各类数学工具书中找到。

离散时间傅里叶变换

对于离散时间的信号，也可以仿照连续时间傅里叶变换的定义 \[{\cal F}\{x(t)\} = \int_{-\infty}^\infty x(t) {\rm e}^{-j\omega t} ;{\rm d}t\] 把时间换成离散的，积分号换成求和符号，定义离散时间傅里叶变换： \[X({\rm e}^{j\omega}) = {\cal F}\{x[n]\} = \sum_n x[n] {\rm e}^{-j\omega n}\] 上式称为分析方程。离散信号经傅里叶变换后得到的\(X({\rm e}^{j\omega})\)是关于\(\omega\)的函数。在括号里写\({\rm e}^{j\omega}\)的原因，一方面是为了和连续时间傅里叶变换在记号上加以区分，一方面暗示离散时间傅里叶变换是以\(2\pi\)为周期的函数，另一方面它还便于把离散时间傅里叶变换和z变换相联系。

我们可以直接写出综合方程并验证其正确性： \[\eqalign{ x[n] &= {1\over 2\pi}\int_{2\pi} X({\rm e}^{j\omega}) {\rm e}^{j\omega n} ;{\rm d}\omega \cr &= {1\over 2\pi}\int_{2\pi} \left[\sum_m x[m] {\rm e}^{-j\omega m}\right] {\rm e}^{j\omega n} ;{\rm d}\omega \cr &= {1\over 2\pi}\sum_m x[m] \int_{2\pi} {\rm e}^{j\omega (n-m)} ;{\rm d}\omega \cr }\] 式中的定积分仅在\(m=n\)时不为零，所以可以验证以上等式成立。

离散时间信号往往要比连续时间信号容易处理（例如，无需考虑间断点），判定傅里叶变换是否存在的Dirichlet条件的前3条均不适用，而只需最后一条，将绝对可积改成“绝对可求和”：\[\sum_n |x[n]| < \infty. \]

离散时间里也不会遇到Dirac函数这样具有古怪性质的函数。Dirac函数在离散时间中的版本是单位冲击函数 \[\delta[n] = \cases{1 & if $n = 0,$ \cr 0 & else.}\] 是一个具有良好定义的普通函数。

离散傅里叶变换和快速傅里叶变换

离散傅里叶变换基于上节所述的离散时间傅里叶变换。如上节所述，离散时间信号的傅里叶变换是一个以\(2\pi\)为周期的连续函数。虽然信号是离散时间的，但是其傅里叶变换仍然是连续的，这样也不便于利用计算机进行处理。

离散傅里叶变换接受长度为\(N\)的离散时间信号\(\{x[n]\}_{n=0}^{N-1}\)，并计算信号\[\tilde x[n] = \cases{x[n] & if $0 \leq n < N$, \cr 0 & else}\]的离散时间傅里叶变换\(\tilde X({\rm e}^{j\omega})\)在\([0, 2\pi)\)内的\(N\)个等间距采样，即 \[X[k] = \left.\tilde X({\rm e}^{j\omega})\right|_{\omega = {2k\pi\over N}}\qquad k=0,1,\dots,N-1. \]

根据离散时间傅里叶变换的定义，可以得到离散傅里叶变换的计算公式 \[X[k] = \sum_{n=0}^{N-1} x[n]{\rm e}^{-j{2k\pi\over N}n}. \]

另一方面，如果对\(x[n]\)做周期延拓，并和傅里叶级数的分析方程相对比，不难发现\[X[k] = NA_k.\]

所以可以用离散时间傅里叶级数的综合方程来导出离散傅里叶逆变换的计算公式 \[x[n] = {1\over N}\sum_{k=0}^{N-1} X[k]{\rm e}^{j{2k\pi\over N}n}.\]

快速傅里叶变换(FFT)算法是利用分治思想来快速计算离散傅里叶变换的一种算法。它可以在\(O(N\log N)\)的时间内计算出\(X[0], X[1], \dots, X[N-1]\)的值。在工程实践中所做的大部分傅里叶变换都是快速傅里叶变换。

应用举例：多项式乘法

傅里叶变换有一个重要性质是卷积定理。以离散情况为例，函数\(x\)和\(y\)的卷积定义为 \[(x*y)[n] = \sum_k x[k]y[n-k].\] 卷积定理指出，时域内的卷积经过傅里叶变换，转化为频域内的数量乘法，即 \[{\cal F}\{(x*y)[n]\} = X({\rm e}^{j\omega})Y({\rm e}^{j\omega}).\]

不难验证卷积和多项式的乘法是等同的： \[\eqalign{ (1+x)(1+2x+x^2) &= 1+3x+3x^2+x^3, \cr \{1, 1\} * \{1, 2, 1\} &= \{1, 3, 3, 1\}. \cr }\]

下面我们利用卷积定理来计算这两个多项式的乘积。由于我们事先知道了结果的长度为\(N=4\)，为了避免混叠(aliasing)现象的产生，离散傅里叶变换至少需要4个采样值。因此先将输入数据的长度扩展为4： \[\eqalign{ x &= \{1, 1, 0, 0\}, \cr y &= \{1, 2, 1, 0\}. \cr }\]

运用快速傅里叶算法，得到频域数值 \[\eqalign{ X &= \{2, 1-j, 0, 1+j\}, \cr Y &= \{4, -2j, 0, 2j\}. \cr }\]

在频域内做数量乘法： \[ XY = \{8, -2-2j, 0, -2+2j\}. \]

运用快速傅里叶逆变换，得到 \[ x * y = \{1, 3, 3, 1\}. \]

当两个多项式的次数都很高时，尽管多了时域和频域之间的两次转换，总的计算时间仍然远远小于朴素的（使用卷积在时域中的定义）算法。自然数也可以看做一个多项式，只不过其变量固定地取进位制中约定的数值，例如\(x=10\)（十进制）或\(x=2\)（二进制）。因此，这里所给出的多项式乘法算法还可以用于大整数的乘法计算中。在很多现有的大整数运算库（例如GNU MP）中，当两个数特别巨大时，它们的乘法就是利用快速傅里叶变换来计算的。