傅里叶里傅
01 Aug 2019前言
本来只打算简单介绍下傅里叶变换的, 但是一开始写文章, 就发现自己很多点都没有搞清楚. 陆陆续续花了两周多的时间才感觉自己是真的明白了. 果然以教为学是最好的学习方法.
这篇文章没有非常严谨的推导证明, 只是用我觉得 intuitive 的理解来介绍相关知识. 因为傅里叶分析主要用于信号处理, 所以在网上查找资料时, 涉及到很多信号处理的相关知识, 什么采样定理, 梳状函数等等, 我会尽量不去涉及这些相关知识 (因为我也不懂啊).
看这篇文章前最好对傅里叶变换有个大概的了解, 推荐看这篇文章: 傅里叶分析之掐死教程
概述
前言中推荐的那篇文章对于傅里叶分析的介绍已经很好了, 文章中涉及到了几个概念, 1) 傅里叶级数 (FS) 2) 傅里叶变换 (FT) 3) 离散傅里叶变换 (DFT), 如果查找相关资料你还会看到 4) 离散时间傅里叶变换 (DTFT), 5) 离散傅里叶级数 (DFS) 6) 快速傅里叶变换 (FFT), 7) 连续时间傅里叶变换 (CTFT) 等等, 我当时的疑惑点就是这些概念彼此之间究竟是什么关系? 离散的是什么? 连续的是什么? 离散时间又是什么意思?
上面提到的几个概念中有些其实描述的是同一个东西, 只是名字不一样. 一般说 傅里叶变换 就是指 连续时间傅里叶变换, 通常也认为 离散傅里叶级数 和 离散傅里叶变换 是同一个概念, 最后, 快速傅里叶变换 只是 离散傅里叶变换 的一种快速算法实现. 最终上面的概念就剩下四个 1) 傅里叶级数 2) 傅里叶变换 3) 离散傅里叶变换 4) 离散时间傅里叶变换. 傅里叶分析的核心思想就是对一个函数进行分析, 对于一个函数我们可以从多个维度去描述它, 傅里叶分析关心的是函数它连续还是离散? 周期还是非周期? 两两组合就分别对应我们那四个概念.
| 连续 | 离散 | |
|---|---|---|
| 周期 | 傅里叶级数 | 离散傅里叶变换 |
| 非周期 | 傅里叶变换 | 离散时间傅里叶变换 |
离散时间的意思是指信号在时域上离散, 换句话说就是待分析的函数是离散的. 离散傅里叶变换 没有 时间 这个限定词, 就意味着它既在时间上离散, 还在其它地方离散, 和时间对应的就是频率. 后面我们会看到, 在频域上离散就表示待分析的函数是周期的.
傅里叶级数 (Fourier Series)
先给出定义: f(x) 是周期为 T 的函数
这个公式的含义就是, 任何周期函数可以转换成一系列的正余弦函数的累加. 对于这个公式, MIT 6.024 线性代数公开课里给出的解释我觉得是最漂亮的. 任何一个 n 维的空间中, 一定可以找到一组正交基, 空间中所有向量都可以由这组正交基进行线性运算来得到. 所谓正交基, 就是一组两两正交的基向量. 在二维和三维空间中, 两向量点乘为 0 就说明这两个向量垂直. 将这一性质拓展到 n 维空间就是, 两个向量的点乘为 0 则两向量正交.
现在我们把函数当成一个无限维空间 (希尔伯特空间) 中的向量, 类比有限维空间中点乘的公式, 定义希尔伯特空间的点乘的公式为:
\[f(x) \cdot g(x) = \int_{\infty} f(x)g(x) dx\]我们可以发现傅里叶级数中的各项, 两两之间点乘的结果为 0, 所以傅里叶级数就是希尔伯特空间中的一组正交基.
利用傅里叶级数正交这一性质, 求各项的系数就非常简单了, 公式两边各乘上要求系数的项,
然后积分就好了 (因为等式两边均为周期为 T 的函数, 所以只需要在周期 T 内积分就可以了):
p.s. \(a_0\) 项除以 2 的原因是, 如果不除以 2, 其它各项乘以自身之后积分的结果都是 \(\frac{T}{2}\), 而 1 在周期内的积分是 T, 这里为了统一, 所以 \(a_0\) 需要除以 2.
傅里叶级数还有另外一个形式. 根据欧拉公式, 我们有 \(e^{xi} = cosx + i sinx\), 所以:
\[cosx = \frac{e^{xi} + e^{-xi}}{2} \\ sinx = \frac{e^{xi} - e^{-xi}}{2i}\]将上式代入原本的傅里叶级数, 我们有:
\[\begin{align*} f(x) &= \sum_{n=0}^{+\infty} \left(c_n e^{\frac{2\pi n}{T}xi} + c_{-n} e^{\frac{-2\pi n}{T}xi} \right) \\ &= \sum_{n=-\infty}^{+\infty} \left(c_n e^{\frac{2\pi n}{T}xi} \right) \\ c_n &= \frac{a_n - ib_n}{2} \end{align*}\]求 \(c_n\) 我们可以把之前求的 \(a_n\) 和 \(b_n\) 带入, 也可以利用正交性质来求解.
需要注意的是, 涉及到复数时, 向量点乘的定义为 \(a \cdot b = a^H \cdot b\),
其中的 \(a^H\) 表示共轭转置 (Hermitian), 其实就是把向量中的 i 变成 -i.
最终得到:
\[\begin{align*} f(x) &= \sum_{n=-\infty}^{+\infty} \left(c_n e^{\frac{2\pi n}{T}xi} \right) \\ c_n &= \frac{1}{T}\int_{T} f(x) e^{\frac{-2\pi n}{T}xi} dx \end{align*}\]傅里叶变换 (Fourier Transform)
傅里叶级数要求 f(x) 是周期函数, 那如果不是周期函数是不是就没法处理了呢?
换个角度看, 非周期函数其实就是周期 T 无穷大的的周期函数.
所以对于傅里叶变化, 我们只需要把 \(T \to \infty\) 带入到上面的傅里叶级数中就可以了.
为了方便, 我们定义 \(\Delta \delta = \frac{1}{T}\), 其中 \(\delta\) 表示频率.
当 \(T \to \infty\) 时:
\[\Delta \delta = d\delta \\ n d\delta = \delta\]将上面这些带入之前的傅里叶级数有:
\[\begin{align*} f(x) &= \int_{\infty} c_{\delta} e^{2\pi\delta xi} d\delta \\ c_{\delta} &= \int_{\infty} f(x) e^{-2\pi\delta xi} dx \end{align*}\]因为 \(T \to \infty\), 原先 \(c_n\)
中的系数 \(\frac{1}{T}\) 变成 \(d\delta\) “挪” 到了 f(x) 中, 同时将 f(x) 中的求和符号换成了积分符号.
离散时间傅里叶变换 (Discrete-Time Fourier Transform)
之前我们看的都是连续的函数, 但是现实中我们获取到的都是离散的数值, 或者说是数字化了的信号.
离散时间傅里叶变换就是离散化的傅里叶变换,
f(x) 变成了一组离散的数 f[k] 其中 k 为采样点序号.
怎么处理呢? 想像一下, 所谓的连续函数不过就是采样间隔无穷小的函数, 令每秒采样数为 N:
因为 f[k] 是离散的, 所以把 \(c_{\delta}\) 中的积分符号换成求和符号, 注意, dx 不能去掉, 为什么?
因为 dx 就是个常量, 一个无穷小的常量, 和积分是没有关系的.
分析下 \(c_{\delta}\) 你会发现它是一个周期函数, 也就是说 \(c_{\delta + \Delta} = c_{\delta}\).
为什么? 首先 \(e^{xi}\) 是个周期为 \(2\pi\) 的函数, 要让 \(c_{\delta + \Delta} = c_{\delta}\) 成立,
就需要对于每个 k, 我们有 \(e^{\frac{-2\pi k}{N}\Delta i} = 1\), 显然只要 \(\Delta \frac{k}{N}\) 为非零整数即可.
我一开始这里没有明白, 就很疑惑, 为什么同一个函数, 离散的在频域是周期的而连续的在频域不是周期的,
现在看来就很简单了, 因为 f(x) 中的 x 是实数, 你没办法找到一个数与任意实数相乘都为非零整数,
而对于离散的函数, 你只要 \(\frac{\Delta}{N}\) 是非零整数即可, 因为 k 本身就是整数.
将 dx “挪” 到 f[k] 中, 上面式子就变成:
现在还有个问题, 前面分析过了, \(c_{\delta}\) 是周期函数, 所以显然 \(c_{\delta} e^{\frac{2\pi k}{N}\delta i}\)
也是个周期函数, 对一个周期函数, 在 \(\infty\) 上积分, 显然值只可能是: 无穷大, 无穷小或者零. 这种情况下,
再乘以一个无穷小的 dx, 最终的值究竟是什么呢? 我们来看下这个 dx 究竟是什么.
我们反过来看, \(c_{\delta}\) 是个连续周期函数, 那么我们是不是也可以对它进行傅里叶级数分解呢? 所以:
可以看到 \(dx = \frac{1}{\int_{\infty} d\delta}\), 最后我们利用 \(c_{\delta} e^{\frac{2\pi k}{N}\delta i}\)
和 dx 的周期为 \(N\) 这一性质, 可以将在 \(\infty\) 的积分变成:
所以离散时间傅里叶变换的最终结果就是:
\[\begin{align*} f[k] &= \frac{1}{N}\int_{N} c_{\delta} e^{\frac{2\pi k}{N}\delta i} d\delta \\ c_{\delta} &= \sum_{k=-\infty}^{+\infty} \left(f[k] e^{\frac{-2\pi k}{N}\delta i} \right) \end{align*}\]离散傅里叶变换 (Discrete Fourier Transform)
有了离散时间傅里叶变换的基础, 离散傅里叶变换就很简单了, 只需要将 \(\delta\) 转换回 \(\frac{n}{T}\) 即可:
\[\begin{align*} f[k] &= \frac{1}{N}\sum_{n \in TN} \left(c_n e^{\frac{2 \pi kn}{NT} i}\right) d\delta \\ c_n &= \sum_{k=-\infty}^{+\infty} \left(f[k] e^{\frac{-2 \pi kn}{NT} i} \right) \end{align*}\]同样的道理, 利用 f[k] 周期为 NT 的性质, 同时将 \(d\delta\) “挪” 到 \(c_n\) 中:
最终离散傅里叶变换的结果为:
\[\begin{align*} f[k] &= \frac{1}{N} \sum_{n \in NT} \left(c_n e^{\frac{2 \pi kn}{NT} i} \right) \\ c_n &= \frac{1}{T} \sum_{k \in NT} \left(f[k] e^{\frac{-2 \pi kn}{NT} i} \right) \end{align*}\]我们可以看到, 离散傅里叶变换的形式才是傅里叶分析的一般形式, 要连续傅里叶变换就让 \(N \to \infty\), 要非周期就让 \(T \to \infty\).
所谓连续不过就是采样间隔无穷小的离散.
快速傅里叶变换 (Fast Fourier Transform)
快速傅里叶变换就不多说了, 就是基于离散傅里叶变换的线性代数形式的一些特征, 将计算复杂度由 \(n^2\) 降为 \(nlog(n)\) 的一种算法.
其他
可以发现时域的函数和频域的函数在傅里叶分析中是非常对称的, 比如时域连续, 在频域就是非周期, 在时域非周期, 在频域就是连续. 写这篇文章的时候, 时域和频域的表达形式, 我也刻意用了相对称的表述方式.
最后, 我们可以将最开始的表格扩充下:
| 时域 | 连续 | 离散 | |
|---|---|---|---|
| 周期 | 傅里叶级数 | 离散傅里叶变换 | 离散 |
| 非周期 | 傅里叶变换 | 离散时间傅里叶变换 | 连续 |
| 非周期 | 周期 | 频域 |
p.s. 对于带复数的函数求导, 只需要将 i 当成一个常数即可