复习：傅里叶级数和傅里叶变换

Wed Dec 9, 2015

致EE120。

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

傅里叶级数

连续时间傅里叶级数

傅里叶级数的核心思想是：**任何周期函数都可以展开为三角级数。**假设有一函数x(t)，其最小正周期是T，则它一定可以展开成(∗)x(t)=∑kAkejkω0t,

其中，ω0=2πT称为基频，Ak称为傅里叶系数。根据复指数函数的周期性，可以知道上式右边的周期是T。为方便计算，使用复指数而不是余弦或正弦函数。复指数函数与三角函数的关系由欧拉公式给出：ejθ=cos⁡θ+jsin⁡θ.

一个简单的例子是取x(t)=cos⁡ω0t，由欧拉公式立即得到 cos⁡ω0t=12e−jω0t+12ejω0t. 在这个展开中，Ak={12if k=±1,0else.由此也可见，引入负的频率分量是有必要的。

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

既然认定可以做(∗)那样的展开，那么就要问：如何确定式中的系数Ak？有人想出了一种做法：计算 ∫Tx(t)e−jkω0t;dt=∫T∑κAκej(κ−k)ω0t;dt=∑κAκ∫Tej(κ−k)ω0t;dt=TAk 积分号的下标T表示积分在任意一个长度为T的区间内进行。最后一个等号成立源于复指数函数在一个周期上的积分∫Tej(κ−k)ω0t;dt={Tif κ=k,0else. 因此 Ak=1T∫Tx(t)e−jkω0t;dt. 上式称为分析方程(Analysis Equation)，而与之相对的(∗)式则称为综合方程(Synthesis Equation)。

离散时间傅里叶级数

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

设有一离散时间信号x[n]，其最小正周期为N，那么沿用刚才的思想，它应当可以展开成x[n]=∑k∈SNAkejkω0n.

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

上式为综合方程。使用类似的技巧（这次是求和而不是积分），可以得到傅里叶系数： ∑k∈SNx[n]e−jkω0n=∑k∈SN∑κ∈SNAκej(κ−k)ω0n=∑κ∈SNAκ∑k∈SNej(κ−k)ω0n=NAk 同样，求和符号里只有一项不为零，因此最后一个等号成立。因此得到分析方程 Ak=1N∑k∈SNx[n]e−jkω0n.

傅里叶变换

连续时间傅里叶变换

傅里叶变换将周期函数展开成了三角级数。那么自然会想，如何处理非周期的函数。非周期的函数，可以视作周期是无穷大的函数。即研究傅里叶级数在T→∞的表现。可想而知，当周期趋于无穷时，基频将趋于0，无限细分的求和式将会转化为积分的形式。具体而言， x(t)=∑kAkejkω0t=∑k1T[∫−T/2T/2x(t)e−jkω0t;dt]ejkω0t=12π∑k[∫−π/ω0π/ω0x(t)e−jkω0t;dt]ejkω0tω0

如果T→∞，即ω0→0+，则 x(t)=12π∫−∞∞[∫−∞∞x(t)e−jωt;dt]ejωt;dω.

定义x(t)的傅里叶变换为 X(jω)=F{x(t)}=∫−∞∞x(t)e−jωt;dt. 则 x(t)=F−1{X(jω)}=12π∫−∞∞X(jω)ejωt;dω.

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

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

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

Dirichlet条件和Dirac函数

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

1. 在任意有限区间内只有有限个间断点，间断点左右的极限不可以是无穷；
2. 在任意有限区间内只有有限个极值点。
3. 在一个周期内绝对可积: ∫T|x(t)|;dt<∞。

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

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

Dirac函数δ(t)大致可以定义为阶跃函数u(t)={0if t<012if t=01if t>0的导数。因此在t≠0时处处为0，而在t=0的时刻为∞。因此，它常常用于描述一个时间无限短但作用量有限的冲击，例如质点的密度函数。它的重要性质如下 ∫−∞∞x(t)δ(t);dt=x(0) 对于任意函数x总成立。

举例而言，把X(jω)=2πδ(ω−ω0)代入傅里叶变换的综合方程，可以得到 x(t)=12π∫−∞∞2πδ(ω−ω0)ejωt;dω=ejω0t

由此可以得到F{ejω0t}=2πδ(ω−ω0). 由欧拉公式，得F{cos⁡ω0t}=π[δ(ω−ω0)+δ(ω+ω0)]. 取ω0=0，得F{1}=2πδ(ω). 以上便导出了一些不满足Dirichlet条件(不是绝对可积的)的函数所对应的傅里叶变换。

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

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

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

离散时间傅里叶变换

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

我们可以直接写出综合方程并验证其正确性： x[n]=12π∫2πX(ejω)ejωn;dω=12π∫2π[∑mx[m]e−jωm]ejωn;dω=12π∑mx[m]∫2πejω(n−m);dω 式中的定积分仅在m=n时不为零，所以可以验证以上等式成立。

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

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

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

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

离散傅里叶变换接受长度为N的离散时间信号{x[n]}n=0N−1，并计算信号x~[n]={x[n]if 0≤n<N,0else的离散时间傅里叶变换X~(ejω)在[0,2π)内的N个等间距采样，即 X[k]=X~(ejω)|ω=2kπNk=0,1,…,N−1.

根据离散时间傅里叶变换的定义，可以得到离散傅里叶变换的计算公式 X[k]=∑n=0N−1x[n]e−j2kπNn.

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

所以可以用离散时间傅里叶级数的综合方程来导出离散傅里叶逆变换的计算公式 x[n]=1N∑k=0N−1X[k]ej2kπNn.

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

应用举例：多项式乘法

傅里叶变换有一个重要性质是卷积定理。以离散情况为例，函数x和y的卷积定义为 (x∗y)[n]=∑kx[k]y[n−k]. 卷积定理指出，时域内的卷积经过傅里叶变换，转化为频域内的数量乘法，即 F{(x∗y)[n]}=X(ejω)Y(ejω).

不难验证卷积和多项式的乘法是等同的： (1+x)(1+2x+x2)=1+3x+3x2+x3,{1,1}∗{1,2,1}={1,3,3,1}.

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

运用快速傅里叶算法，得到频域数值 X={2,1−j,0,1+j},Y={4,−2j,0,2j}.

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

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

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