一天理解傅里叶变换

原文:http://blogs.zynaptiq.com/bernsee/dft-a-pied/。本文是该网络文章的翻译。如果您对本译文有改进意见或其他想法,欢迎在评论区留言。

 

如果你喜欢数字信号处理,你会觉得这个标题是在吹牛逼。我支持这一点。你当然无法在一天内学习到傅里叶变换的所有性质及其好玩的地方并且最终开始钻研数学,但这篇文章会给你提供一些关于傅里叶变换是如何工作的、它为什么有效、以及为什么我们用一些非常规的手段会使它变得容易理解。最重要的是:你将会学习到傅里叶变换的基础知识,而不需要任何除了加减乘除以外的数学知识!我会用不超过六个章节,用其在音频信号处理中的应用解释傅里叶变换。


第一步:一些简单的前提条件

 

你需要了解以下这些:数字的加减乘除,什么是正弦、余弦,什么是正弦曲线,以及它们长什么样子。显然我不会介绍前两个东西,我会稍微花一点时间介绍最后一个。你可能还记得学校里面学的“三角函数” *,用来计算各种边和角的关系。我们不需要算那些东西,但我们需要知道“正弦”和“余弦”长什么样子。这其实很简单:他们看起来像简单的波浪,有高峰有低谷,并且向左和向右无限延伸。

你可以看到,两种曲线都是周期性的,意思就是在经过一段时间后,他们又看上去跟原来一模一样了。并且,两个波形看起来也很像,但是余弦的波形起始于最高点,但正弦波形起始于0。在实践中,我们怎么区分一个我们观察的波是起始于最高点还是0呢?这是一个好问题:我们并不能区分。并没有一种方法来在实践中区分正弦和余弦波,所以我们统称它们为“正弦曲线”(sinusoid, 希腊语,翻译成英文是“sinus-like”)。正弦曲线一个重要的性质是“频率”(frequency),它告诉我们这个波在一个给定的时间段内可以有多少个波峰和波谷。高频率意味着有很多波峰和波谷,低频率意味着有很少。


 

第二步:理解傅里叶定理(The Fourier Theorem)

 

Jean-Baptiste Joseph Fourier 是那些父母感到又骄傲又羞愧的孩子之一,因为他在14岁的时候会给扔给他们一堆复杂的数学术语。虽然他一生中做了许多重要的工作,但他发现的最重要的东西也许和材料的导热有关。他搞出了一个描述热量如何在特定介质中传播的方程式,并用一个无限多的三角函数的序列解出了这个方程式。基本上,并且这与我们的主题相关的是,傅里叶发现的东西可以总结为:任意的不管多么复杂的信号,都可以表示为一些正弦曲线单独相加的和。

上图中你看到的是我们的原始信号,以及如何用一堆以一种特定关系(“配方”)混合起来的正弦曲线的组合(我们称它们为“部分”)来拟合这个信号。我们会稍后讨论“配方”。你可以看到的是,用到的正弦曲线越多,对原曲线的拟合就越精确。在我们的“现实”世界中,信号是连续的,就是说你可以在非常短的区间内测量它们,精度只取决于你的测量的机器。如果你想完美拟合一个信号,你可能会需要无限多的正弦曲线。幸运的是,我们做数字信号处理的人并不活在这样一个世界中。相反,我们会处理一些“现实世界”中的信号的样本,这些信号是以有限的精度在有规律的区间内测量的。所以我们并不需要无限多的正弦曲线,我们只是需要很多个。我们稍后也会说明“很多是多少”。现在,最重要的是你可以想象得到你的电脑中的每一个信号,在某个特定的配方下,都可以由简单的正弦曲线组成。


第三步:“很多”是多少

 

我们已经看到了,复杂形状的波形可以用一系列正弦曲线构建出来。我们可能想问:要构建我们电脑上的任意一个信号,需要多少正弦曲线?当然我们可能只需要一个单独的正弦曲线,只要我们知道这个信号是如何构成的。在多数情况下,我们要处理的信号会有一个非常复杂的结构,所以我们并不会提前知道有多少“部分”波在那。在这种情况下,我们要知道如果我们不知道有多少正弦波构成原始信号,那我们需要的上限是多少,这将是非常令人放心的。这仍然并不能让我们知道它到底具体有多少正弦曲线。让我们尝试直观地理解这一点:假设我们对一个信号进行1000次采样,周期最短的那个正弦曲线(也就是频率最大的,波峰和波谷最多的)对每个采样有交替的波峰和波谷。这样的话,频率最大的那个正弦曲线在1000个采样中就有500个波峰和500个波谷,每隔一个采样点就是一个波峰。下图中的黑色的点就代表了我们的采样点,所以频率最高的那个正弦曲线应该长这样:

现在我们来看最低频率的正弦波能有多低。如果我们只有一个采样点,我们如何测量通过这个点的正弦曲线的波峰和波谷个数呢?并不能,因为通过这个点有很多种可能的正弦曲线,同样有很多种可能的频率。

所以一个单独的点并不足以告诉我们关于频率的任何信息。现在如果我们有两个采样点,那么通过这两个点的正弦曲线的频率最低能有多低?在这种情况下,事情会变得简单很多。只会有一个很低频率通过两个点的正弦曲线,长这样:

把左边的两个点想象成两个钉子,然后我们要用一根绳子穿过它们(图中画了3个点,因为正弦波是周期性的,但我们其实只需要左边两个点来分辨它的频率)。我们能看到的最低频率就是像图中的那样,绳子在两个点间上升又下降。如果我们有1000个采样点,这两个“钉子”就是第一个点和最后一个点,也就是编号为1和编号为1000的点。我们从经验中得知,乐器的弦越长频率就越低,所以我们会期望当两个钉子离得更远的时候,频率最低的正弦曲线的频率也会变得更低。如果我们选2000个采样点,那么最低频率的正弦曲线的频率会变得更低,因为我们的两个“钉子”现在是点1和点2000。事实上,最低频率会变为原来的1/2,因为两个“钉子”之间的距离是原来的两倍。因此,如果我们有更多的样本,我们就能分辨出较低频率的正弦波,因为他们的过零点(我们的“钉子”)会移动得更远。这一点对于理解接下来的内容非常重要。

我们也可以看到,在两个“钉子”之后,我们的曲线开始重复一个上升的斜坡(第一个和第三个钉子是相同的)。这说明这相邻两个钉子之间包含着正好一半的正弦波,或者说一个波峰或者一个波谷(译者:这里应该指整个1/2的曲线,而不仅仅是最值点),或者说1/2个周期。

总结一下我们现在学了什么。我们知道了一个采样正弦波的最高频率是每隔一个点为波峰或波谷,最低频率是我们的样本正好是正弦波的半个周期。等一下——这是不是说明,当我们增加采样点的时候,最高频率不会变,但最低频率会降低?完全正确!这样做的结果是,当我们把更长的未知信号放在一块的时候,我们就需要更多的正弦曲线,因为我们采用了较低的频率。(译者:这句话其实没太看懂,原文:“The result of this is that we will need more sine waves when we want to put together longer signals of unknown content, since we start out at a lower frequency.” 如果有更好的翻译建议欢迎留下评论)

非常好。但我们还是不知道最终需要多少正弦曲线。我们已经知道的是一个“部分”可以有的最低和最高频率,这样就可以计算一下有多少种正弦曲线满足这个区间要求。因为我们已经用两个钉子固定了最低频率曲线的两个端点,并且要求所有其他的曲线都要用到这两个钉子(事实上我们为什么要区别对待它们呢?所有的正弦曲线都是平等的!)。想象一下这些正弦曲线是吉他上的两端被固定住的弦,它们只能在两根钉子之间摇摆(除非它们断了),就像我们的正弦曲线。这样就有了一个规律,最低频率的曲线(称其为“部分(1)”)在这两个钉子之间有1/2个周期,部分(2)有1个周期,部分(3)有3/2个,以此类推。

从图形上看起来是这样:

现在,如果我们数一下有多少正弦曲线满足我们的1000个采样点,会发现正好有1000个。事实上,我们会发现我们永远需要采样点个数的正弦曲线。


第四步:关于配方

 

前面的章节中我们看到了任意一个计算机上的信号都可以用一堆正弦曲线构建出来,并且了解了要完美构建出任意曲线,我们需要的曲线的最高频率和最低频率,也知道了采样点的个数对于决定最低频率的“部分”是非常重要的。还没有讨论的是,如何将正弦波混合在一起以产生一个特定的结果。要用正弦曲线模拟出任意给定信号,我们需要测量一个信号的另外一个方面。事实上,频率并不是我们唯一需要知道的东西,我们也需要知道每个正弦曲线的振幅。换句话说,对于每个正弦波,我们需要多少,来构建我们的信号。振幅是一个正弦曲线波峰的高度,也就是波峰到零轴的距离。振幅越大,我们听到的声音就会越响。所以,如果你的信号中有很多贝斯,你会毫无疑问地会期待在一堆正弦曲线中低频比高频占更大的比重。一般来说,在低音比较重地声音里,低频的正弦曲线会比高频的振幅要大。在我们的分析中,我们会需要去决定每个“部分”正弦曲线的振幅来完成我们的“配方”。


第五步:关于苹果和橘子(译者:我不知道这是啥意思。。有知道的请评论给我)

 

如果你还跟得上的话,我们已经几乎完成了傅里叶变换的旅程。我们已经学习了我们需要多少正弦曲线,这个数字取决于我们的采样个数,有一个频率上限和一个频率下限,并且我们需要决定每个“部分”波的振幅来完成我们的配方。但是,我们还并不清楚如何从采样中得出正确的配方。直观地说,我们可以通过比较一个给定频率的正弦曲线和我们测量到的采样数据,看看它们有多“相等”,来决定其振幅。如果它们完全相等,我们就知道了这个正弦曲线现在一定存在并且有相等的振幅;如果它们一点也不匹配,我们就会认为这个频率的曲线不会出现。但是我们如何比较一个正弦曲线和一个采样信号呢?幸运的是,做数字信号处理的人已经解决了这个问题。事实上,这跟数的加减乘除一样简单——我们用一个已知频率的“参考”正弦曲线,单位振幅(就是振幅为1的意思,就跟我们用计算器或者计算机的sin()函数得到的东西一样)乘以我们的采样数据,然后把得到的乘积加在一起,我们就得到了我们现在关注的这个频率的正弦曲线的振幅。

下面是一小段C语言代码实现:

这段代码把存在inputData[0...transformLength-1]的采样点转换成一个包含“部分”正弦曲线的振幅数据的数组transformData[0...transformLength-1]。通常我们会命名我们的参考正弦曲线的频率步数为bin(译者:我们现在考虑的频率是bin * sampleRate / transformLength),这就意味着它们可以被想象成是一个个容器,里面放的是每个“部分”正弦曲线的振幅。假设我们我们完全不知道我们的信号长什么样,离散正弦变换(Discrete Sine Transform, DST)是一个非常通用的手段,否则我们就能用一些更高效的方法来决定这些频率。(比如,如果我们知道我们的信号是由一个单一的正弦曲线构成的,我们就能直接查看它的振幅而不需要再在一堆正弦波上做计算。可以在一种基于傅里叶定理的“Goertzel”算法的文献中找到做这种计算的高效的方法)。

给那些坚持要一些解释的人:直观上地解释我们为什么和一个已知频率的正弦曲线相乘。想象一下,这跟物理上给定频率的“共振”有点像。sin(arg)函数实际上是一个被我们的输入波形激发的谐振器。如果输入的波形包含我们当前关注的频率的部分,那么输出就是我们参照的正弦曲线的共振的振幅。由于我们的参照正弦曲线是单位振幅的,那么实际上输出就是哪个部分的真实振幅。由于谐振器仅仅是一个简单的滤波器,这种变换可以(不可否认的是,仅仅在比较宽松的条件下)被视为是一堆非常窄的带通滤波器,中心位于我们正在测量的这个频率上。这帮助我们解释了为什么傅里叶变换提供了一种高效的过滤信号的手段。

为了完整性:当然,上面说的那些过程都是可逆的,我们的信号可以(在数值精度的限制下)用”部分“正弦曲线简单相加完美重构出来。这作为一个练习留给读者。用余弦曲线作为基本的函数也可以做同样的过程——我们只需要把sin(arg)项改为cos(arg)来得到离散余弦变换(Discrete Cosine Transform, DCT)的直接实现。

我们已经在本文的第一段讨论过,在实际应用中我们无法分辨一个”类正弦“曲线到底是正弦还是余弦。相反,我们总是测量正弦形曲线,所以到底是正弦还是余弦在实践中并没有太大用处(译者:本文中出现的“正弦曲线”,有的是指相位任意的正弦曲线,有的特指相位为0的,这是我的错误,后续会更正),除了一些特殊情况(如图像压缩,每个图像可能用余弦或者正弦作为基函数建模特征,比如用余弦作为基函数可以很好地表示出大面积相同的颜色)。正弦曲线比正弦和余弦函数要更通用一些,因为他可以在其周期的任意时刻开始,而(真正的)正弦曲线总是从0开始,余弦曲线总是从1开始。如果以(真正的)正弦曲线作为参照,余弦曲线会比它晚开始1/4个周期。通常我们会用三角学里常用的单位——度数或者弧度表示这个偏移量。一整个周期是360°(读作:度),或者2\pi弧度(读作”二派“。\pi是一个希腊字符,数值为3.14159265358979323846...。其在三角学中有重要作用)。所以余弦曲线就有90°或者说\pi/2的偏移量。这个偏移量叫做一个正弦曲线的相位,所以余弦曲线相对于正弦就有90°或者说\pi/2的相位偏移。

所以相位这个东西有啥用?因为我们并不能总限制我们的信号让它起始于0相位或者90°相位(因为我们是在观察信号,信号可能本身并不受我们控制),确定其频率,幅度和相位以便在任意适合唯一地描述它是非常有意义的。如果只用正弦和余弦,我们就限制在了0相位或者90度相位,这样任何一个有任意相位的正弦曲线都会导致其相邻频率出现虚假的峰值(因为它们试图“帮助”我们的分析,从而强行将这个曲线用0相位和90°相位的曲线拟合出来)。这有点像把一个圆石头填满一个方的洞里——你会需要更小的圆石头取填满剩下的空隙,然后需要更更小的石头取填满还空着的地方,以此循环。所以我们需要的是一种通用的能适用于构造任意相位的正弦曲线的变换。


第六步:离散傅里叶变换

 

从正弦变换到傅里叶变换很简单,只是让它变得更“通用”。在正弦变换中我们一直用正弦曲线,而在傅里叶变换中正弦和余弦都会用到。也就是说,对于我们关注的任意频率,我们会用测量过的信号和频率相同的正弦、余弦均进行“比较”(或“共振”)。如果它长得更像正弦波,那么正弦波部分的振幅就会更大一些;如果它长得更像一个余弦波,那么余弦波部分的振幅就会更大一些。如果它长得像相反的正弦波,意思是,它从0开始但是紧接着下降到-1而不是上升到1,那么正弦部分会有一个绝对值比较大的负的振幅。可以证明的是,用正负号(+,-)和正弦余弦的相位可以表示任意给定频率的正弦形曲线*。

我们现在还是不知道傅里叶变换的好处都有啥。虽然我已经说过,用正弦和余弦变换实现的傅里叶变换的好处就是我们可以表示任意相位的正弦曲线,但是现在还没见过什么正弦曲线,只有正弦函数和余弦函数。这就需要一个附加的步骤:

在DFT的输出基础上运行了Listing 1.3中的代码后,我们就得到了一个输入信号用一些正弦曲线的和的表示。第k个正弦曲线用frequency[k], magnitude[k]和phase[k]表示。单位是Hz(赫兹,周期/秒), dB(Decibel)和°(度)。注意做过如上述代码的处理,即把那些正弦、余弦转换成一个单独的正弦曲线后,我们把箱子(bin)里面放的“振幅”命名为“大小”(magnitude),因为它现在永远是一个正值。我们可以说,振幅为-1.0对应着大小为1.0相位为+或-180°。在文献中,在我们做傅里叶变换时,magnitude[]数组被称为被测量信号的“幅度谱”(Magnitude Spectrum),phase[]数组被称为被测量信号的“相位谱”(Phase Spectrum)。

作为测量以分贝为单位的箱量值(bin magnitude)的参考,我们的输入波应该有位于[-1.0, 1.0)的采样值,对应着0分贝和数字满量程(Digital Full Scale, DFS)。有一个DFT的有趣的应用,Listing 1.3可以用来写一个基于DFT的频谱分析图。


总结

 

我们已经看到了傅里叶变换和它的“亲属”,离散正弦余弦变换提供了一种非常方便的用来分解一个信号得到一堆“部分”波的工具。这些“部分”波是正弦或者余弦波,或者说是正弦曲线(用正弦和余弦波的组合来描述的)。傅里叶变换同时用正弦和余弦的好处是我们可以引入相位的概念,这会让傅里叶变换变得更通用,因为我们可以用其来清晰地分析一些既不是纯正弦也不是纯余弦的正弦曲线,当然也包括其他信号。

傅里叶变换跟要做的信号其实在某种程度上是无关的,不管信号有多么复杂,或者仅仅是一个简单的正弦曲线,要做的操作数量其实是一样的。这就是离散傅里叶变换被称为非参数的转换,意思就是其有一个“智能”的对信号的分析并没有什么帮助(当我们知道我们要分析的信号是一个正弦曲线时,我们更会愿意去只得到它的相位、频率和振幅,而不是用一堆预先定义了频率的正弦余弦波)。

我们也知道了我们会用一堆固定频率的跟输入没有关系的栅格(我们的bin)来测量信号。由于我们(几乎是)根据频率选择的参考正弦和余弦波,所以我们用来分析的栅格是认为的。讲完这个后,有一个很明显的问题摆在我们面前:可能会出现被测量的频率在我们测量的两个频率中间。结果是,一个频率刚好位于我们的两个频率“箱”(bin)之间的正弦曲线在变换中并不会被很好地表示出来。离输入波频率最接近的频段的两个相邻的频率箱将会尝试”纠正“频率的偏差,因此输入波的能量将会被分散在几个邻近的箱子中。这也是为什么傅里叶变换不能毫无困难地分析一个声音来返回其根音和和声(这也是为什么我们称正弦和余弦波为 部分,而不是和声或者泛音)。

简单地说,没有更深一步的后续处理,DFT就是一堆窄的、有一点点重叠的带通滤波器(”频道“),并对每个频道带有附加的相位信息。这对分析信号、过滤和一些其他的灵活的技巧(改变一个信号的音高而不改变其速度是其中一个,在作者的另一篇文章中有阐述),都很有用,但这需要一些针对性较强的后续处理。这也可以被看作是一系列变换(使用其他基函数而不仅仅是正余弦)中的一个特例。展开讲这个概念超出了本文的范围。

最后,需要被提及的是有一个更高效的DFT的实现,即”快速傅里叶变换“(Fast Fourier Transform, FFT),其首先由Cooley和Tukey在1969年(但其根源要追溯到高斯和其他人的工作中)提出。FFT是一个高效在更短时间内计算DFT的算法,其得到的结果是一样的。但是,由于Cooley/Tukey对于FFT的实现要求其变换长度(Transform Length)是2的次幂。实际大多数情况下,这是一个可以接受的限制。有很多很多关于不同的FFT的实现方法的文献,所以可以说有很多种不同的FFT的实现,其中有些并没有传统FFT的2的次幂的约束。下面Listing 1.4的smbFft()函数给出了一种实现。

*)注意在文献中,由于对傅里叶变换进行的泛化可以工作在另一种称为”复信号“的输入信号上(”复“在这个情景中的意思是一种数,而不是说输入信号的和声结构很复杂),你会看到正弦和余弦部分有着”实部“(余弦)和”虚部“(正弦)的名字。

1 条思考于 “一天理解傅里叶变换

发表评论

电子邮件地址不会被公开。

*