傅里叶变换简介

本文链接：个人站 | 简书 | CSDN
版权声明：除特别声明外，本博客文章均采用 BY-NC-SA 许可协议。转载请注明出处。

1. 傅里叶级数 Fourier Series (FS)

傅里叶级数得名于法国数学家约瑟夫·傅里叶，他提出任何函数都可以展开为三角级数。

考虑一个在区间 $[t_0, t_0+T]$ 上可积的函数 $f(t)$ ，其傅里叶级数为
$f(t) = \dfrac{a_0}2 + \sum\limits_{n=1}^\infty\left(a_n\cos\dfrac{2\pi n}Tt + b_n\sin\dfrac{2\pi n}Tt\right) \tag{1}$
其中
$a_n = \dfrac2T\int_{t_0}^{t_0+T}f(t)\cos\dfrac{2\pi n}Tt\mathrm{d}t, n=0, 1, 2, \cdots \tag{2}$
$b_n = \dfrac2T\int_{t_0}^{t_0+T}f(t)\sin\dfrac{2\pi n}Tt\mathrm{d}t, n=1, 2, \cdots \tag{3}$
由欧拉公式 $\mathrm{e}^{i\theta} = \cos\theta+i\sin\theta$ 得
$\begin{align} \cos\theta &= \dfrac12\left(\mathrm{e}^{i\theta}+\mathrm{e}^{-i\theta}\right)\\ \sin\theta &= -\dfrac i2\left(\mathrm{e}^{i\theta}-\mathrm{e}^{-i\theta}\right) \end{align} \tag{4}$
代入（1）可得
$f(t) = \dfrac{a_0}2 + \sum\limits_{n=1}^\infty\left(\dfrac{a_n-ib_n}2\mathrm{e}^{i\frac{2\pi n}Tt} + \dfrac{a_n+ib_n}2\mathrm{e}^{-i\frac{2\pi n}Tt}\right) \tag{5}$
令
$\begin{equation} c_n = \begin{cases} \dfrac{a_n - ib_n}2 &\text{n>0}\\ \dfrac{a_0}2 &\text{n=0}\\ \dfrac{a_{|n|} + ib_{|n|}}2 &\text{n<0} \end{cases} \end{equation}\tag{6}$
则可以得到傅里叶级数的复数形式
$f(t) = \sum\limits_{n=-\infty}^{+\infty}c_n\mathrm{e}^{i\frac{2\pi n}Tt}\tag{7}$
其中
$c_n = \dfrac1T\int_{t_0}^{t_0+T}f(t)\mathrm{e}^{-i\frac{2\pi n}Tt}\mathrm{d}t, \qquad n=0, \pm1 \pm2,\cdots\tag{8}$

2. 傅里叶变换 Fourier Transform (FT)

傅里叶变换可以看作傅里叶级数的连续形式。

首先考虑定义在 $[-\frac T2, \frac T2]$ 上的函数的傅里叶级数展开：
$f(t) = \sum\limits_{n=-\infty}^{+\infty}c_n\mathrm{e}^{i\frac{2\pi n}Tt}\tag{9}$
其中
$c_n = \dfrac1T\int_{-T/2}^{T/2}f(t)\mathrm{e}^{-i\frac{2\pi n}Tt}\mathrm{d}t, \qquad n=0, \pm1 \pm2,\cdots\tag{10}$
令
$\Delta\omega=\dfrac{2\pi}T\tag{11}$
记
$\hat{f}(n\Delta\omega)=Tc_n=\int_{-T/2}^{T/2}f(t)\mathrm{e}^{-in\Delta\omega t}\mathrm{d}t, \qquad n=0, \pm1, \pm2, \cdots\tag{12}$
则
$c_n=\dfrac{\hat{f}(n\Delta\omega)}T=\dfrac{\Delta\omega}{2\pi}\hat{f}(n\Delta\omega)\tag{13}$
$\begin{equation} \begin{split} f(t) &= \sum\limits_{n=-\infty}^{+\infty}c_n\mathrm{e}^{i\frac{2\pi n}Tt} \\ &= \dfrac1{2\pi} \sum\limits_{n=-\infty}^{+\infty}\hat{f}(n\Delta\omega)\mathrm{e}^{in\Delta\omega t}\Delta\omega \end{split} \end{equation} \tag{14}$
当 $T\to\infty$ 时， $n\Delta\omega\to\omega$ ， $\Delta\omega\to\mathrm{d}\omega$ ， (14) 中的求和变为积分
$f(t) = \dfrac1{2\pi}\int_{-\infty}^{+\infty}\hat{f}(\omega)\mathrm{e}^{i\omega t}\mathrm{d}\omega\tag{15}$
相应地，(12) 变为
$\hat{f}(\omega)=\int_{-\infty}^{+\infty}f(t)\mathrm{e}^{-i\omega t}\mathrm{d}t\tag{16}$
(16) 称为傅里叶变换，记作 $\hat{f}(\omega) = \mathcal F[f](t)$ ；(15) 称为傅里叶变换的逆变换，记作 $f(t) = \mathcal F^{-1}[\hat{f}](\omega)$ 。在信号分析中， $f(t)$ 称为信号的时域表示， $\hat{f}(\omega)$ 称为信号的频域表示。

需要明确的是，不管是用时域还是用频域来表示一个信号，它们代表的都是同一个信号。可以从线性空间的角度理解这一点。同一个信号在不同的表象（或者说基向量）下具有不同的坐标。同一个向量在不同表象下的坐标可以通过一个线性变换联系起来。如果是有限维的空间，这个线性变换可以表示为一个矩阵。而傅里叶变换则是无限维空间不同表象之间的一种变换。举例来说，在量子力学中，一个波函数的坐标表象到动量表象间的变换就是一个傅里叶变换。

也可以将角频率 $\omega$ 替换为自然频率 $\nu$ ，有 $\omega = 2\pi\nu$ ，则
$\hat{f}(\nu) =\mathcal Ff(t)= \int_{-\infty}^{+\infty}f(t)\mathrm{e}^{-i2\pi\nu t}\mathrm{d}t\tag{17}$
$f(t) =\mathcal F^{-1}\hat{f}(\nu) = \int_{-\infty}^{+\infty}\hat{f}(\xi)\mathrm{e}^{i2\pi\nu t}\mathrm{d}\nu\tag{18}$

3. 离散时间傅里叶变换 Discrete-time Fourier Transform (DTFT)

一般情况下，我们处理的信号都是离散的。取 $f(t)$ 在时间上的离散采样
$f_n = f(n\tau), \qquad n=0, \pm1, \pm2, \cdots\tag{19}$
$\tau$ 是采样的时间间隔。傅里叶变换只能作用在连续函数上，为此我们引入
$\begin{split} f_s(t) &= f(t)\sum\limits_{n=-\infty}^{+\infty}\delta(t-n\tau)\\ &=\sum\limits_{n=-\infty}^{+\infty}f(t)\delta(t-n\tau)\\ &=\sum\limits_{n=-\infty}^{+\infty}f_n\delta(t-n\tau) \end{split} \tag{20}$
其中
$\begin{equation} \delta(x) = \begin{cases} +\infty, &x=0\\ 0, &x\neq0 \end{cases} \end{equation} \tag{21}$
为 Dirac 函数。 $\sum\limits_{n=-\infty}^{+\infty}\delta(t-n\tau)$ 称为 Dirac 梳子，亦称 Shah 分布，是一个采样函数，常用在数字信号处理和离散时间信号分析中。

对 $f_s(t)$ 作傅里叶变换
$\begin{split} \hat{f}_s(\omega)&=\int_{-\infty}^{+\infty}f_s(t)\mathrm{e}^{-i\omega t}\mathrm{d}t\\ &=\int_{-\infty}^{+\infty}\sum\limits_{n=-\infty}^{+\infty}f(t)\delta(t-n\tau)\mathrm{e}^{-i\omega t}\mathrm{d}t\\ &=\sum\limits_{n=-\infty}^{+\infty}\int_{-\infty}^{+\infty}\delta(t-n\tau)f(t)\mathrm{e}^{-i\omega t}\mathrm{d}t\\ &=\sum\limits_{n=-\infty}^{+\infty}f_n\mathrm{e}^{-i\omega n\tau} \end{split} \tag{22}$
这里利用了 Dirac 函数的性质 $\int_{-\infty}^{+\infty}\delta(x)g(x)\mathrm dx=g(0)$ 。(22) 即为离散时间傅里叶变换。

下面简单介绍一下采样定理。若原信号 $f(t)$ 不包含高于 $\Omega_m$ 的频率，即 $\hat{f}(\omega) = 0,\forall |\omega| > \Omega_m$ ，则只要采样频率 $\omega_s\geq2\Omega_m$ ，时域采样就能完全重建原信号。

将 $\hat{f}(\omega)$ 在 $[-\frac{\omega_s}2, \frac{\omega_s}2]$ 上展开为傅里叶级数
$\hat{f}(\omega) = \sum\limits_{m=-\infty}^{+\infty}c_m\mathrm e^{i\frac{2\pi m}{\omega_s}\omega}\tag{23}$
其中
$c_m = \frac 1{\omega_s}\int_{-\omega_s/2}^{\omega_s/2}\hat{f}(\omega)\mathrm e^{-i\frac{2\pi m}{\omega_s}\omega}\mathrm d\omega\tag{24}$
注意到 $|\omega|>\Omega_m$ 时 $\hat{f}(\omega) = 0$ ，而 $\omega_s\geq2\Omega_m$ ，故 $|\omega|>\omega_s/2$ 时 $\hat{f}(\omega) = 0$ ，因此 (24) 可改写为
$\begin{split} c_m &= \frac 1{\omega_s}\int_{-\infty}^{+\infty}\hat{f}(\omega)\mathrm e^{-i\frac{2\pi m}{\omega_s}\omega}\mathrm d\omega\\ &=\frac{2\pi}{\omega_s}f(-\frac{2\pi}{\omega_s}m)\\ &=\tau f(-m\tau)\\ &=\tau f_{-m} \end{split} \tag{25}$
代入 (23)，得
$\begin{split} \hat{f}(\omega) &= \sum\limits_{m=-\infty}^{+\infty}\tau f_{-m}\mathrm e^{i\frac{2\pi m}{\omega_s} \omega}\\ &= \sum\limits_{n=-\infty}^{+\infty}\tau f_{n}\mathrm e^{-i\frac{2\pi n}{\omega_s}\omega}\\ &= \tau\sum\limits_{n=-\infty}^{+\infty}f_n\mathrm{e}^{-i\omega n\tau }\\ &= \tau\hat{f}_s(\omega) \end{split} \tag{26}$
这里 $n=-m$ 。(26) 说明原信号的傅里叶变换可以由采样信号确定，进而可以利用傅里叶逆变换重建原信号。

此外，不难发现
$\begin{split} \hat{f}_s(\omega) &= \sum\limits_{n=-\infty}^{+\infty}f_n \mathrm{e}^{-i\omega n\tau } \\ &= \sum\limits_{n=-\infty}^{+\infty}f_n\mathrm{e}^{-i2\pi n\frac \omega{\omega_s}} \end{split} \tag{27}$
是一个周期为 $\omega_s$ 的周期函数。离散傅里叶变换 $\hat{f}_s(\omega)$ 可以看作原信号连续傅里叶变换 $\hat{f}(\omega)$ 的周期延拓，时域的离散化造成了频域的周期化。

4. 离散傅里叶变换 Discrete Fourier Transform (DFT)

离散时间傅里叶变换在频域上仍然是连续的。如果把频域也离散化，就得到了离散傅里叶变换。
$\hat{f}_k = \sum\limits_{n=0}^{N-1}f_n\mathrm{e}^{-i\frac{2\pi}Nnk}, \qquad k=0, 1, \cdots, N-1\tag{28}$
也可以写成矩阵形式
$\begin{equation} \left[ \begin{matrix} \hat{f}_0\\ \hat{f}_1\\ \hat{f}_2\\ \vdots\\ \hat{f}_{N-1} \end{matrix} \right] =\left[ \begin{matrix} 1 & 1 & 1 & \cdots & 1\\ 1 & \varphi & \varphi^2 & \cdots & \varphi^{ N-1}\\ 1 & \varphi^2 &\varphi^4 & \cdots & \varphi^{2(N-1)}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & \varphi^{N-1} & \varphi^{2(N-1)} & \cdots & \varphi^{(N-1)^2} \end{matrix} \right] \left[ \begin{matrix} f_0\\ f_1\\ f_2\\ \vdots\\ f_{N-1} \end{matrix} \right] \end{equation} \tag{29}$
其中 $\varphi=\mathrm e^{-i2\pi/N}$ 。

离散傅里叶变换的逆变换为
$f_n = \frac{1}{N}\sum\limits_{k=0}^{N-1}\hat{f}_k\mathrm e^{i\frac{2\pi}{N}nk}, \qquad n=0, 1, \cdots, N-1 \tag{30}$

5. 快速傅里叶变换 Fast Fourier Transform (FFT)

直接根据定义计算离散傅里叶变换的复杂度是 $O(N^2)$ 。快速傅里叶变换是快速计算离散傅里叶变换及其逆变换的一类数值算法。FFT 通过把 DFT 矩阵分解为稀疏矩阵之积，能够将复杂度降低到 $O(N\log N)$ 。

在 Python 中可以利用 scipy.fftpack 进行快速傅里叶变换。

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

from scipy.fftpack import fft, ifft

x = np.linspace(0, 2*np.pi, 200) # 采样频率为 200Hz
y = np.cos(5*x) + 0.5*np.sin(25*x) + 0.3*np.cos(75*x) # 根据采样定理，信号中不能包含超过 100Hz 的频率成分
plt.figure(figsize=(10,12))
ax1 = plt.subplot(311)
ax1.plot(x, y, 'r')
ax1.set_title('original signal in time domain')

Y = fft(y) # 快速傅里叶变换，得到频域
ax2 = plt.subplot(323)
ax2.plot(range(200), abs(Y))
ax2.set_title('original signal in frequency domain')

Y[10:-9] = 0 # 滤波
ax3 = plt.subplot(324)
ax3.plot(range(200), abs(Y))
ax3.set_title('filtered signal in frequency domain')

filtered = ifft(Y).real # 逆变换，得到滤波后的时域信号
ax4 = plt.subplot(313)
ax4.plot(x, filtered, 'g')
ax4.set_title('filtered signal in time domain')

参考文献

小波与傅里叶分析基础（第二版），电子工业出版社，2017.6
Fourier transform - Wikipeida https://en.wikipedia.org/wiki/Fourier_transform
Discrete-time Fourier transform - Wikipedia https://en.wikipedia.org/wiki/Discrete-time_Fourier_transform
Discrete Fourier transform - Wikipedia https://en.wikipedia.org/wiki/Discrete_Fourier_transform
Discrete Fourier transforms (scipy.fftpack) https://docs.scipy.org/doc/scipy/reference/fftpack.html

最后编辑于：2020.04.06 17:27:49

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,029评论 6赞 492
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,395评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,570评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,535评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,650评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,850评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,006评论 3赞 408
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,747评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,207评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,536评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,683评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,342评论 4赞 330
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,964评论 3赞 315
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,772评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,004评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,401评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,566评论 2赞 349