前言
终于下定决心要啃掉这块骨头。大四选修数字图像处理的时候,第一次接触傅里叶变换,然后实现了时间度复杂度为
拉格朗日等数学家发现某些周期函数可以由三角函数的和表示,而傅里叶则猜测任意周期函数都可以写成三角函数的和,也就是高等数学中的傅里叶级数。大家当然都不相信啦,但又不能给出有力的论据。直到 20 年后(1829 年)狄利克雷才给出了让人满意的答案:只有满足一定条件时,周期函数才能展开成傅里叶级数。这个条件被称为狄利克雷条件。傅里叶级数用吴文俊先生的话说就是:
把质的困难转化成量的复杂
而最早具有这种想法的人是泰勒,他在 1715 年研究出泰勒公式。泰勒级数把函数表达式转化为多项式函数来近似,是求导函数组成的特征函数和,反应变化剧烈程度。傅里叶级数是频谱叠加的三角函数和,反应变化频率本质属性。
实函数的傅立叶级数和泰勒级数不过是观察复幂级数的两种不同方式
傅里叶级数
傅里叶级数具体构造过程可以参考马同学高等数学的文章。假设nint()
为向下取整函数,在 Python 中相当于 round()
函数。由于
根据这个向量就能得到函数的幅值频谱图,其中纵坐标为幅值,也就是上面的向量。横坐标为角频率(角速度的标量),也就是对应的基中的
非奇非偶函数既有正弦分量也有余弦分量,所以就需要有两个频域图。当
复数形式
傅里叶级数具有两个频域图,而另一种角度,即复数形式的傅里叶级数就可以结合正弦和余弦分量,详情可见马同学高等数学。复数形式的傅里叶级数如下所示:
傅里叶变换
傅里叶级数只能用于周期函数,后来的数学家将其扩展到非周期函数上,其思想就是让周期
离散时间傅里叶变换
上面提及的傅里叶变换
时域和频域具有以下关系:
时域 | 频域 |
---|---|
周期 | 离散 |
非周期 | 连续 |
连续 | 非周期 |
离散 | 周期 |
即大部分的信号为:连续时间周期信号、连续时间非周期信号、离散时间非周期信号和离散时间周期信号。而计算机存储的信号为时域上采样得到的信号,因此在计算机中我们用不到连续时域信号,以下内容均默认为时域离散,即频域是周期的。
离散傅里叶变换
由于计算机只能处理有限长的信号,对于时域周期的信号,则可以对其一个周期内的信号进行傅里叶变换,然后扩展到整个时域上。对于无限长非周期信号就需要对信号进行截断,然后再当成是周期信号的一个周期来处理
例如在
总结
综上所述,计算机对现实中的信号的时域采样(离散化)得到了离散时间傅里叶变换(DTFT),这个过程中频域会被周期化;然后对信号进行截断,即只收集一段时间的信号;继而对频域进行采样(离散化)得到离散周期傅里叶级数(DFS),这个过程中时域会被周期化。最后只取一个周期进行分析,即只取一个周期内的
快速傅里叶变换
1965 年,Cooley 和 Tukey 提出了计算离散傅里叶变换(DFT)的快速算法,将 DFT 的运算量减少了几个数量级。快速傅里叶变换(FFT)中的” 快速” 等价于快速排序中的 “快速”。也就是说,我们需要在计算机上实现排序,有各种各样的排序算法,快速排序这个算法比较好用。快速傅里叶变换也一样,利用了分治策略,减小了算法的时间复杂度。对于
大部分快速傅里叶变换是基于 2 的,即信号的长度为 2 的整数幂(不足则补 0)。快速傅里叶算法每次将长度为
所以
蝶形图
以
测试
1 | import numpy as np |
对于一个长度为 1024 的序列,手动实现的离散傅里叶变换算法需要的时间为 0.2748403549194336 秒,而 numpy
的快速傅里叶变换算法只需要 0.0009996891021728516 秒,最终计算结果一致。
总结
花了整整一周的时间终于总结完了快速傅里叶变换相关的内容,虽然复数部分不是很深入,但是目前至少能比较熟练得使用这个 20 世纪最伟大的算法了。以上内容之所以花了这么多时间,还是因为概念不清晰,了解傅里叶变换、离散时间傅里叶变换、离散傅里叶变换和快速傅里叶变换就花了不少时间,如果这次没有记录下来,我相信下次看到还是不会!
参考文献
- 马同学高等数学。如何理解傅立叶级数公式?. https://www.matongxue.com/madocs/619.html.
- 马同学高等数学。从傅立叶级数到傅立叶变换. https://www.matongxue.com/madocs/712.html.