傅里叶变换交互式指南

傅里叶变换(Fourier Transform)是有史以来最深刻的见解之一。不幸的是，其含义隐藏在密集的方程中：

$\displaystyle{X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i 2 \pi k n / N}}$

$\displaystyle{x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k \cdot e^{i 2 \pi k n / N}}$

哎呀。与其跳进符号里，不如让我们亲身体验关键思想。这里有一个通俗的比喻：

傅里叶变换(Fourier Transform)是做什么的？ 给定一杯冰沙，它找到配方。
如何？ 将冰沙通过过滤器提取每种成分。
为什么？ 配方比冰沙本身更容易分析、比较和修改。
我们如何找回冰沙？ 混合配料。

以下是上述内容的“数学英语”版本：

傅里叶变换获取一个基于时间的模式，测量每个可能的周期，并返回整体的"周期配方"（每个找到的周期的振幅、偏移和旋转速度）。

要开始看方程了吗？不！让我们动手实践，体验通过实时模拟，看看任何模式如何由周期构建而成。

如果一切顺利，我们将有一个顿悟时刻，直观地理解为什么傅里叶变换是可能的。详细的数学分析留到后续文章。

这不是对方程的强行灌输，而是我希望经历的一次轻松漫步。出发！

从冰沙到配方

数学变换是一种视角的改变。我们根据计数对象，改变数量的概念，从“单个项目”（沙地上的线条，计数系统）到“10的组”（十进制）。计分？用计数法。乘法？请用十进制。

傅里叶变换将我们的视角从消费者转变为生产者，将 我有什么？ 转化为 它是如何制作的？

换句话说：给定一杯冰沙，让我们找到配方。

为什么？嗯，配方是饮料的绝佳描述。你不会分享逐滴的分析，而会说“我喝了一杯橙子/香蕉冰沙”。配方比物体本身更容易分类、比较和修改。

那么……给定一杯冰沙，我们如何找到配方？

嗯，想象你有一些过滤器：

通过"香蕉"过滤器倒入。提取出1盎司香蕉。
通过"橙子"过滤器倒入。2盎司橙子。
通过"牛奶"过滤器倒入。3盎司牛奶。
通过"水"过滤器倒入。3盎司水。

我们可以通过过滤每种成分来反向工程配方。关键点在于：

过滤器必须独立。香蕉过滤器需要捕捉香蕉，而不是其他东西。添加更多橙子绝不应影响香蕉读数。
过滤器必须完整。如果我们漏掉一个过滤器（“还有芒果！”），就得不到真正的配方。我们的过滤器集合必须捕捉所有可能的成分。
成分必须可组合。冰沙可以毫无问题地分离和重新组合（饼干？不太行。谁要碎屑？）。成分以任何顺序分离和组合后，必须得到相同的结果。

将世界视为周期

傅里叶变换(Fourier Transform)采用了一个特定的视角： 如果任何信号都可以被过滤成一组圆形路径呢？

哇。这个概念令人震撼，可怜的约瑟夫·傅里叶最初的想法曾被拒绝。(真的吗，Joe，即使是楼梯图案也可以由圆圈构成？)

尽管数十年的争论在数学界，我们期望学生毫无困难地内化这个概念。呃。让我们来梳理一下直觉。

傅里叶变换找到信号的配方，就像我们的奶昔制作过程：

从基于时间的信号开始
应用过滤器测量每个可能的"圆形成分"
收集完整配方，列出每种"圆形成分"的量

停步。大多数教程在这里会兴奋地抛出工程应用。别害怕；把这些例子看作是“哇，我们终于看到了以前令人困惑的想法背后的源代码（DNA）”。

如果地震振动可以被分解为“成分”（不同速度和振幅的振动），那么建筑物可以被设计成避免与最强的振动相互作用。
如果声波可以被分解为成分（低音和高音频段），我们可以增强我们关心的部分，隐藏我们不关心的部分。随机的噼啪噪声可以被去除。也许类似的“声音配方”可以进行比较（音乐识别服务比较的是配方，而不是原始音频片段）。
如果计算机数据可以用振荡模式表示，也许最不重要的部分可以被忽略。这种“有损压缩”可以大幅减小文件大小（这就是为什么JPEG和MP3文件比原始.bmp或.wav文件小得多）。
如果无线电波是我们的信号，我们可以使用滤波器来收听特定频道。在奶昔世界里，想象每个人关注不同的成分：亚当找苹果，鲍勃找香蕉，查理找花椰菜（抱歉伙计）。

傅里叶变换在工程中很有用，当然，但它是一个关于找到观察到的效果背后根本原因的隐喻。

用圆来思考，而不仅仅是正弦波

我最大的困惑之一是区分“正弦波”和“圆”的定义。

一个"正弦波"是一种特定的来回模式（一个正弦(sine) 或余弦波），99%的情况下它指的是一维运动。
一个"圆"是你可能知道的圆形二维图案。如果你喜欢用十美元的词汇描述十美分的想法，你可能会把圆形路径称为"复正弦波"。

将圆形路径标记为“复正弦波”就像把一个单词描述为“多个字母”。你放大了错误的细节层次。单词是关于概念的，而不是它们可以被拆分成字母！

傅里叶变换是关于圆形路径（不是一维正弦波）并且欧拉公式(Euler's formula) 是一种生成圆形路径的巧妙方法：

我们必须使用虚指数来在圆形中移动吗？不。但它方便且紧凑。当然，我们可以将路径描述为二维（实部和虚部）的协调运动，但不要忘记大局：我们只是在绕圈。

沿着圆形路径运动

假设我们在电话聊天，像往常一样，我希望我们同时画出同一个圆。(你保证过的！) 我应该说什么？

圆有多大？（振幅，即半径的大小）
我们画圆有多快？（频率。1圈/秒是1赫兹(Hz)或2*pi弧度/秒）
我们从哪里开始？（相位角，0度对应x轴）

我可以说“2英寸半径，从45度开始，每秒一圈，开始！”。半秒后，我们每个人都应该指向：起点 + 经过的角度 = 45 + 180 = 225度（在一个2英寸的圆上）。

每个圆形路径都需要大小、速度和起始角度（幅度/频率/相位）。我们甚至可以组合路径：想象微型电动车，以不同的速度绕圈行驶。

组合位置 所有周期 是我们的信号，就像混合口味 所有成分 是我们的奶昔。

这是一个基本圆形路径的模拟：

(基于这个动画，这里是源代码。需要现代浏览器。点击图形暂停/恢复。）

每个周期的大小按顺序列出，从0Hz开始。周期 [0 1] 表示

0Hz周期的振幅为0（0Hz = 恒定周期，固定在x轴的0度处）
1Hz周期的振幅为1（每个时间间隔完成1个周期）

现在棘手部分：

蓝色图形测量的是实部周期的. 另一个可爱的数学困惑：圆的实轴通常水平，但其大小显示在垂直轴上。如果你愿意，可以在脑海中将圆旋转90度。
时间点以最快频率间隔. 1Hz信号需要2个时间点作为起点和终点（单个数据点没有频率）。时间值 [1 -1] 显示这些等间隔点上的振幅。

跟上我了吗？ [0 1] 是一个纯1Hz周期。

现在让我们加入一个2Hz周期。 [0 1 1] 表示"Nothing at 0Hz, 1Hz of amplitude 1, 2Hz of amplitude 1"：

哇。小马达变得疯狂：绿线是1Hz和2Hz周期，蓝线是组合结果。尝试切换绿色复选框以清晰查看最终结果。组合的“口味”是一种从最大值开始摆动，然后在区间其余部分降至低点的摆动。

黄色点是我们实际测量信号的位置。定义了3个周期（0Hz、1Hz、2Hz），每个点位于信号的三分之一处。在这种情况下，周期 [0 1 1] 生成时间值 [2 -1 -1]，从最大值（2）开始，降至低点（-1）。

哦！我们不能忘记相位，即起始角度！使用 magnitude:angle 设置相位。所以 [0 1:45] 是一个从45度开始的1Hz周期：

这是经过移位的版本 [0 1]。在时间域我们得到 [.7 -.7] 而不是 [1 -1]，因为我们的周期并未完全对齐测量间隔（测量间隔仍在中点），这可能是我们期望的！

傅里叶变换找到一组周期速度、振幅和相位，以匹配任何时间信号。

我们的信号成为一个抽象概念，我们可以将其视为“时间域中的观测”或“频率域中的成分”。

话不多说：试试看！在模拟器中，输入任何你想看到的时间模式或周期模式。如果是时间点，你会得到一组周期（组合成一个“波”），它们与你期望的点匹配。

但是……组合波在黄色时间间隔之间难道不会有奇怪的值吗？当然。但谁知道信号在我们不测量时是直线传播、曲线传播，还是突然进入其他维度？它在我们需要等间隔时刻正好表现出我们所需的行为。

在时间上制造一个尖峰

我们能否在时间域中制造一个尖峰，比如 (4 0 0 0)，用周期来实现？我将使用圆括号 () 表示一系列时间点，方括号 [] 表示一系列周期。

尽管尖峰对我们这些时间居民来说似乎很无聊（一个数据点，就这些？），想想周期世界中的复杂性。我们的周期成分必须从对齐开始（处于最大值4），然后“向外爆炸”，每个周期都有伙伴在未来抵消它。所有剩余点为零，这是多个周期同时运作时的一个棘手平衡（我们不能简单地“关掉它们”）。

让我们逐一分析每个时间点：

在时间0（最初一刻），每个周期成分都处于最大值。忽略其他时间点， (4 ? ? ?) 可以由4个周期组成（0Hz、1Hz、2Hz、3Hz），每个幅度为1、相位为0（即1+1+1+1=4）。
在未来的每个时刻（t=1,2,3），所有周期的和必须抵消。

诀窍在于：当两个周期位于圆的对侧（北与南、东与西等）时，它们组合的位置为零（3个周期如果均匀分布在0°、120°和240°也会抵消）。

想象一群点围绕圆运动。以下是每个周期在每个时刻的位置：

Time 0 1 2 3 
------------
0Hz: 0 0 0 0 
1Hz: 0 1 2 3
2Hz: 0 2 0 2
3Hz: 0 3 2 1

注意3Hz周期如何从0开始，到达位置3，然后位置“6”（由于只有4个位置，6 模运算(modulo) 4 = 2），然后位置“9”（9模4得1）。

当我们的周期长度为4个单位时，相距半个周期（2个单位）的周期速度要么对齐（差值为0、4、8…），要么在相反侧（差值为2、6、10…）。

好的。我们来深入每个时间点：

时间0：所有周期处于最大值（总共4）
时间1：1Hz和3Hz相消（位置1和3相反），0Hz和2Hz也相消。净值为0。
时间2：0Hz和2Hz在位置0对齐，而1Hz和3Hz在位置2（对侧）对齐。总和仍为0。
时间3：0Hz和2Hz相消。1Hz和3Hz相消。
时间4（重复t=0）：所有周期对齐。

诀窍是让各个速度抵消（0Hz对2Hz，1Hz对3Hz），或者让对齐的对子抵消（0Hz+2Hz对1Hz+3Hz）。

当每个周期具有相同功率和0相位时，我们开始时对齐，随后抵消。（我还没有一个漂亮的证明——有人愿意试试吗？——但你可以自己看看。尝试 [1 1], [1 1 1], [1 1 1 1] 并注意我们生成的信号： (2 0), (3 0 0), (4 0 0 0)).

在我的脑海中，我将这些信号标记为“时间尖峰”：它们在一个瞬间有值，其他时间为零（专业名称是德尔塔函数(delta function).)

以下是我如何想象初始对齐，然后是净抵消：

移动时间尖峰

并非所有事情都发生在t=0。我们能否将尖峰改为 (0 4 0 0)?

似乎周期成分应该类似于 (4 0 0 0)，但周期必须在t=1（未来1秒）处对齐。这就是相位发挥作用的地方。

想象一场有4名选手的比赛。正常比赛是所有人都在起跑线后排成一排，即 (4 0 0 0) 时间模式。无聊。

如果我们希望所有人同时完成到达终点？简单。只需让每个人向前或向后移动适当的距离。也许老奶奶可以从终点线前2英尺处起跑，尤塞恩·博尔特从100米后退处起跑，然后他们手牵手冲过终点线。

相移，即起始角度，是周期宇宙中的延迟。以下是我们如何调整起始位置，使每个周期延迟1秒：

0Hz周期不动，因此它已经对齐。
1Hz周期在整个4秒内完成1转，因此1秒延迟相当于四分之一圈。将其相位向后移动90度（-90），它在t=1时达到相位=0，即最大值。
2Hz周期快两倍，因此给它两倍的角度覆盖（-180或180相位偏移——它穿过圆，无论哪种方式）。
3Hz周期快三倍，因此给它三倍的距离移动（-270或+90相位偏移）

如果时间点 (4 0 0 0) 由周期构成 [1 1 1 1]，那么时间点 (0 4 0 0) 是由 [1 1:-90 1:180 1:90]构成的。（注意：我使用“1Hz”表示“在整个时间段内一个周期”）。

哇——我们在脑中计算这些周期！

干涉可视化类似，只是对齐发生在t=1处。

测试你的直觉：你能做出 (0 0 4 0)，即2秒的延迟吗？0Hz没有相位。1Hz有180度，2Hz有360度（即0度），3Hz有540度（即180度），所以它是 [1 1:180 1 1:180].

发现完整的变换

重大洞察：我们的信号只是一堆时间脉冲！如果我们合并每个时间脉冲的配方，我们应该能得到完整信号的配方。

傅里叶变换按频率逐个构建配方：

将完整信号(a b c d)分解为“时间尖峰”：(a 0 0 0) (0 b 0 0) (0 0 c 0) (0 0 0 d)
对于任何频率（如2Hz）， 暂定的 配方是“a/4 + b/4 + c/4 + d/4”（每个尖峰的振幅在所有频率之间分配）
等等！我们需要为每个尖峰添加相位偏移（“1秒延迟”的角度取决于频率）。
实际频率配方 = a/4（无偏移）+ b/4（1秒偏移）+ c/4（2秒偏移）+ d/4（3秒偏移）。

然后我们可以遍历每个频率以得到完整的变换。

下面是从“数学英语”到完整数学的转换：

几点说明：

N = 我们拥有的时间样本数
n = 当前考虑的样本（0 到 N-1）
x_n = 时间 n 处的信号值
k = 当前考虑的频率（0 赫兹到 N-1 赫兹）
X_k = 信号中频率 k 的含量（幅度和相位，一个复数）
1/N 因子通常被移到 逆变换 （从频率回到时间）。这被允许，尽管我更喜欢在正向变换中使用 1/N，因为它给出了 实际的 时间尖峰的大小。你甚至可以疯狂地在两个变换上都使用 $1/\sqrt{N}$（正向和反向结合会产生 1/N 因子）。
n/N 是我们经过的时间百分比。2 * pi * k 是我们的速度（弧度/秒）。e^-ix 是我们逆向移动的圆形路径。组合起来就是我们在这个速度和时间内移动的距离。
傅里叶变换的原始方程只是说“将复数相加”。许多编程语言不能直接处理复数，所以你需要将所有内容转换为直角坐标再相加。