从傅里叶变换到快速算法

在数字信号处理、音频分析、图像压缩乃至现代通信等众多领域，傅里叶变换都是一个核心的数学工具。它能将信号从时间或空间域转换到频率域，让我们得以观察信号中蕴含的各种频率成分。

然而，传统的离散傅里叶变换计算量巨大。对于包含N个数据点的序列，其计算复杂度与N的平方成正比。当数据量庞大时，这种计算负担变得难以承受，严重限制了其实用性。

正是在这种背景下，快速傅里叶变换应运而生。它并非一种新的数学变换，而是离散傅里叶变换的一种高效计算算法。该算法能将计算复杂度从N的平方降低到N乘以N的对数，实现了计算效率的飞跃。

算法核心：分而治之的思想

快速傅里叶变换之所以“快速”，其精髓在于巧妙地运用了“分而治之”的策略。

该算法发现，一个长度为N的序列的离散傅里叶变换，可以通过将其分解为两个长度为N/2的子序列的离散傅里叶变换来组合得到。这个过程可以递归进行，不断将大问题分解为更小的子问题，直到分解到最基础的、长度为2或1的序列，其傅里叶变换可以直接计算。

这种分解之所以可行，依赖于离散傅里叶变换公式中旋转因子的周期性和对称性。通过将序列按奇偶索引分开处理，大量冗余的计算被消除，相同的中间结果得以重复利用，从而大幅减少了所需的复数乘法和加法次数。

两种经典实现：时间抽取与频率抽取

在具体的实现路径上，快速傅里叶变换主要有两种经典形式：

• 按时间抽取算法：在时间域（即原始序列的顺序）上将序列进行奇偶分解。它首先将输入序列按照索引的奇偶性重新排列，然后逐级进行蝶形运算，最终得到频率域的输出。
• 按频率抽取算法：直接在频率域对输出序列进行奇偶分解。

虽然两者的分解顺序和信号流图方向不同，但它们在数学上是完全等价的，计算复杂度也相同。理解这两种结构有助于从不同角度把握算法的内在逻辑。

目前，大多数通用计算库中实现的都是基于时间抽取的算法。

蝶形运算：算法中的基本单元

无论采用哪种分解方式，快速傅里叶变换的每一级计算都由最基本的“蝶形运算”构成。

蝶形运算是一个简单的计算单元，通常涉及两个复数数据点和一对旋转因子。其操作可以形象地理解为：两个输入点，经过与旋转因子相乘和相加/相减后，得到两个新的输出点。

整个快速傅里叶变换的网络就是由这些蝶形运算单元层层连接而成。通过分析蝶形运算的流程，可以直观地看到数据是如何被混合、计算并最终转化为频域表示的。

理解单个蝶形运算，是理解整个算法数据流的关键。

应用与实践入门要点

对于初学者而言，无需立即深究其严密的数学推导，可以从几个实践角度建立认知：

• 明确输入输出：输入是一个复数序列（实数序列可视为虚部为零的复数），输出是同样长度的复数序列，代表了信号在各频率分量上的幅度和相位。
• 了解“基数”概念：最常见的基-2算法要求数据点长度N是2的整数次幂。若非如此，通常需要通过补零来满足条件。
• 善用成熟工具：在现代编程中，我们极少需要从头实现快速傅里叶变换，而是直接使用成熟的科学计算库。

但这并不妨碍理解其原理。知道算法在做什么，能帮助我们正确解释运算结果，例如：

• 理解频谱图中频率轴的范围、幅度和相位的含义。
• 认识频谱泄露、栅栏效应等现象。

从而更有效地利用这一强大工具。

《夸克》非常好用的免费AI浏览器

下载APP查看