傅里叶级数与FFT

背景

学习下傅里叶级数与FFT的内容，记录以下方面：

1. 周期函数的傅里叶级数展开
2. 有限区间上函数的傅里叶级数展开
3. FFT

前要知识

函数的内积：

如果我有两个函数$f(x),g(x)$，$x{\in}(a,b)$，定义：$(f(x),g(x))=\int_{a}^{b}f^*(x)g(x)dx$ 为f(x),g(x)在区间(a,b)上的内积

若$(f(x),g(x))=\int_{a}^{b}f^*(x)g(x)dx=0$ ，则说明f(x),g(x)在区间(a,b)上正交。

狄利克雷条件（Dirichlet conditions）

对于一个函数f(x)，所谓满足狄利克雷条件就是要满足两个要求：

1. 在一个周期上只有有限个第一类间断点
   • 是什么：第一类间断点指的是左右极限都存在的间断点（比如可去间断点或跳跃间断点）。
   • 简单来说，函数不能有“无限震荡”或者“趋于无穷大”的断点（比如 1/x 在x=0 处是第二类间断点，不行）。
2. 在一个周期上只有有限个单调区间
   • 是什么：也就是说函数在任意一个周期内，波峰和波谷的数量必须是有限的，不能来回无规则地无限上下震荡（比如魏尔斯特拉斯函数）。
3. 在现实世界和工程应用中，我们遇到的信号（比如方波、锯齿波、三角波）几乎都天然满足这些条件。

---

周期函数的傅里叶级数展开

三角函数展开

首先，对于这样一组三角函数族：

{1 ,$cos(k{\pi}x/l)$, $sin(k{\pi}x/l)$; k=1,2,……}

不难证明：

$$\begin{aligned} \frac{1}{l} \int_{-l}^{l} \cos \frac{k\pi x}{l} \cos \frac{n\pi x}{l} dx &= \delta_{kn}, & \quad \frac{1}{l} \int_{-l}^{l} \sin \frac{k\pi x}{l} \sin \frac{n\pi x}{l} dx &= \delta_{kn} \\ \frac{1}{l} \int_{-l}^{l} \cos \frac{k\pi x}{l} \sin \frac{n\pi x}{l} dx &= 0, & \quad \frac{1}{2l} \int_{-l}^{l} \cos \frac{k\pi x}{l} \cdot 1 dx &= \delta_{k0} \end{aligned}$$

因此，这样一个函数族，他是”周期为2l的函数构成的函数空间“中的一组正交完备基。

也就是说，对于任意一个函数f(x)满足：

1. f(x)=f(x+2l)
2. f(x)满足狄利克雷条件

我们就可以将f(x)展开为：

$$f(x) = a_0 + \sum_{k=1}^{\infty} \left[ a_k \cos \frac{k\pi x}{l} + b_k \sin \frac{k\pi x}{l} \right]$$

对于其中的系数，我们可以利用三角函数的正交性表达出来：

$$\begin{aligned} a_0 &= \frac{1}{2l} \int_{-l}^{l} f(x) dx, \\ a_k &= \frac{1}{l} \int_{-l}^{l} f(x) \cos \frac{k\pi x}{l} dx, \qquad b_k = \frac{1}{l} \int_{-l}^{l} f(x) \sin \frac{k\pi x}{l} dx \end{aligned}$$

指数函数展开

由欧拉公式可知：

$$e^{ik\pi x/l} = \cos \frac{k\pi x}{l} + i \sin \frac{k\pi x}{l}$$

因此指数函数也存在正交性关系，也可以作为一组正交完备基：

$$正交性关系：\frac{1}{2l} \int_{-l}^{l} e^{-ik\pi x/l} e^{in\pi x/l} dx = \delta_{kn}$$

其正交完备基为：$\left\{ e^{ik\pi x/l} ; \; k = 0, \pm 1, \pm 2, \cdots \right\}$

因此，满足条件的f(x)也可以展开为：

$$f(x) = \sum_{k=-\infty}^{\infty} c_k e^{ik\pi x/l}$$

其中：$c_k = \frac{1}{2l} \int_{-l}^{l} f(x) e^{-ik\pi x/l} dx$

---

注意：

• 二者变化的傅里叶系数有以下关系：

1. $c_0=a_0$
2. $c_k = \frac{1}{2}(a_k - i b_k)$

• 由于三角函数：$cos(k{\pi}x/l)$与$cos(-k{\pi}x/l)$是线性相关的；$sin(k{\pi}x/l)$与$sin(-k{\pi}x/l)$是线性相关的，因此三角函数做傅里叶展开时K=0,1,2…。但是对于指数函数$e^{ik\pi x/l}$与$e^{-ik\pi x/l}$线性无关，因此$k = 0, \pm 1, \pm 2, \cdots$

---

有限区间的函数傅里叶级数展开

对于有限区间的函数f(x)，在满足一定条件，与相应边界条件的情况下，可以对函数进行延拓成周期函数，再做傅里叶级数展开

奇延拓

若函数$f(x),x\in(0,l)$满足：

1. f(0)=f(l)=0
2. 狄利克雷条件

则可进行奇延拓，方法是把定义在(0,l)上的图像先关于原点对称翻转到(-l,0)，形成一个关于原点对称的奇函数，再将其以2l为周期无限延拓，则有：

$$F(x) = \begin{cases} f(x), & 0 < x \le l \\ 0, & x = 0 \\ -f(-x), & -l \le x < 0 \end{cases}$$

此时由于F(x)是一个奇函数，他的傅里叶级数展开项应该不含偶函数，因此，F(x)的傅里叶级数展开为：

$$F(x) = \sum_{k=1}^{\infty} b_k \sin \frac{k\pi x}{l}$$

其中：$b_k = \frac{1}{l} \int_{-l}^{l} F(x) \sin \frac{k\pi x}{l} dx$

限定在$x\in(0,l)$上有：

$$\begin{aligned} f(x) &= \sum_{k=1}^{\infty} b_k \sin \frac{k\pi x}{l}, \quad 0 < x < l \\ b_k &= \frac{2}{l} \int_{0}^{l} f(x) \sin \frac{k\pi x}{l} dx \end{aligned}$$

偶延拓

若函数$f(x),x\in(0,l)$满足：

1. f’(0)=f‘(l)=0
2. 狄利克雷条件

则可进行偶延拓，方法是把定义在(0,l)上的图像先沿着y轴（x=0）翻转，形成一个关于y轴对称的偶函数，再将其以2l为周期无限延拓，则有：

$$F(x) = \begin{cases} f(x), & 0 < x \le l \\ f(-x), & -l \le x < 0 \end{cases}$$

此时由于F(x)是一个偶函数，他的傅里叶级数展开项应该不含奇函数，因此，F(x)的傅里叶级数展开为：

$$F(x) = a_0 + \sum_{k=1}^{\infty} a_k \cos \frac{k\pi x}{l}$$

其中：$a_0 = \frac{1}{2l} \int_{-l}^{l} F(x) dx$，$a_k = \frac{1}{l} \int_{-l}^{l} F(x)\cos\frac{k\pi x}{l} dx$

限定在$x\in(0,l)$上有：

$$\begin{aligned} f(x) &= a_0 + \sum_{k=1}^{\infty} a_k \cos \frac{k\pi x}{l}, \quad 0 < x < l \\ a_0 &= \frac{1}{l} \int_{0}^{l} f(x) dx \\ a_k &= \frac{2}{l} \int_{0}^{l} f(x) \cos \frac{k\pi x}{l} dx \end{aligned}$$

一般延拓

若函数$f(x),x\in(0,l)$满足：

1. 狄利克雷条件

则可进行一般延拓，方法是把定义在(0,l)上的图像直接作为第一个周期，然后不断复制粘贴到整个实数轴上无限延拓（即满足 (F(x)=F(x+l))。为了与前述奇、偶延拓的傅里叶级数基底（周期为2l）在区间上保持统一，我们将其在[-l, l]上的表达式定义为：

$$F(x) = \begin{cases} f(x), & 0 < x \le l \\ f(x+l), & -l \le x < 0 \end{cases}$$

此时由于$F(x)$既不是奇函数也不是偶函数，它的傅里叶级数展开中既包含正弦项，也包含余弦项。因此，$F(x)$的傅里叶级数展开为：

$$F(x) = a_0 + \sum_{k=1}^{\infty} \left( a_k \cos \frac{k\pi x}{l} + b_k \sin \frac{k\pi x}{l} \right)$$

其中：

$$\begin{aligned} a_0 &= \frac{1}{2l} \int_{-l}^{l} F(x) dx \\ a_k &= \frac{1}{l} \int_{-l}^{l} F(x)\cos\frac{k\pi x}{l} dx \\ b_k &= \frac{1}{l} \int_{-l}^{l} F(x)\sin\frac{k\pi x}{l} dx \end{aligned}$$

限定在$x\in(0,l)$上有：

$$\begin{aligned} f(x) &= a_0 + \sum_{k=1}^{\infty} \left( a_k \cos \frac{k\pi x}{l} + b_k \sin \frac{k\pi x}{l} \right), \quad 0 < x < l \\ a_0 &= \frac{1}{l} \int_{0}^{l} f(x) dx \\ a_k &= \frac{1}{l} \int_{0}^{l} f(x) \left[ 1 + (-1)^k \right] \cos \frac{k\pi x}{l} dx \\ b_k &= \frac{1}{l} \int_{0}^{l} f(x) \left[ 1 + (-1)^k \right] \sin \frac{k\pi x}{l} dx \end{aligned}$$

(注：由于一般延拓没有对称性来抵消系数，积分无法像前面那样直接化简为2倍。上述化简公式利用了平移变换，引入了奇偶项的交替特性。你会发现当 k为奇数时，$a_k=0$,且 $b_k=0$。这是因为周期为l的信号在周期为 2l的基底中，只有偶次谐波分量。)

一般延拓的复指数傅里叶级数

由前文可推导，其复指数傅里叶级数展开为：

$$F(x) = \sum_{k=-\infty}^{\infty} c_k e^{ik\pi x/l}$$

其中系数 $c_k$ 为：

$$c_k = \frac{1}{2l} \int_{-l}^{l} F(x) e^{-ik\pi x/l} dx$$

限定在 $x\in(0,l)$上有：

$$f(x) = \sum_{k=-\infty}^{\infty} c_k e^{ik\pi x/l}, \quad 0 < x < l$$

系数公式变为：

$$c_k = \frac{1}{2l} \int_{0}^{l} f(x) [1 + (-1)^k] e^{-ik\pi x/l} dx$$

更常用的版本

​ 正常使用一般延拓时傅里叶级数的基底周期应该是l而不是2l，此时有：

$$f(x) = \sum_{k=-\infty}^{\infty} c_k e^{i\frac{2k\pi x}{l}}$$

其中系数 $c_k$为：

$$c_k = \frac{1}{l} \int_{0}^{l} f(x) e^{-i\frac{2k\pi x}{l}} dx$$

---

FFT

FFT(Fast Fourier Transform)，也称快速傅里叶变换，他是一种快速计算DFT的算法，我们关注其数学上的实现DFT(Discrete Fourier Transform)，也称离散傅里叶变换

DFT

DFT可以把有限长离散序列变到离散频域，其可以看作是把有限长序列做一般周期延拓后再取离散傅里叶级数一个主周期。

用人话讲：DFT做的事可以理解为用 N个不同频率的复指数信号去“探测”原序列 x[N]，看每个频率成分占多大比例。

假定，给定一个有限长的序列：$x_{[1]},x_{[2]},….x_{[N]}$ ，

其 DFT 定义为

$$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j 2\pi k n / N}, \qquad k = 0,1,\dots,N-1$$

其中：

1. $x[n]$为时域离散信号，共n个点

2. 每个 $X[k]$ 是一个复数，包含：

   • 幅值：$|X[k]|$—其中包含了频率$f_{(k)}$分量的强度信息

   • 相位：$\angle X[k]$—其中包含了频率$f_{(k)}$分量的相位信息

3. k为频率索引

4. N为点数

其逆变换IDFT为：

$$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j2\pi kn/N}, \quad n=0,1,\dots,N-1$$