快速傅氏变换（Fast Fourier Transform，FFT）算法基本原理详细解析

FFT

基本原理

FFT算法

Cooley-Tukey 步骤概述：

1、分解：将原始序列分成偶数部分和奇数部分。原始DFT问题就被分解成两个长度为N/2的子问题，分别对应偶数索引和奇数索引的元素。

2、递归：递归地对这两个子序列应用FFT算法。这一步骤将继续进行，直到序列长度减小到足够简单（例如长度为1），可以直接计算其DFT。

3、组合：使用蝶形运算（一个简单的数学运算，用于结合两个小DFTs的结果来形成一个大DFT的结果）将所有小DFTs的结果合并起来，得到最终的DFT结果。

蝶形运算

组合的具体实例

最终结果

优化

Cooley-Tukey 变体形式

1. 时域抽选法（DIT）

2. 频域抽选法（DIF）

应用

应用中的关键问题

1. 补零（Zero Padding）

2. 频谱泄露（Spectral Leakage）

3. 栅栏效应（Fence Effect）

4. 加窗（Windowing）

5. 细化（Interpolation）

6. 频谱混叠（Spectral Aliasing）

其他相关的概念

频率分辨率

频率步长

提高准确性的策略

采样时间的选择

加窗技术的应用

其他需要考虑的问题

1、频率值的准确性与频率分辨率的关系

2、信号非周期截断对频谱图的影响（频谱泄露）

3、信号的周期延拓对频谱的影响

4、信号补零对频谱的影响

5、FFT点数不等于信号数据点数对FFT结果的影响

总结

FFT

快速傅里叶变换（FFT）是一种用于计算离散傅里叶变换（DFT）及其逆变换的高效算法。DFT是一种数学技术，用于将一个函数或信号分解成不同频率的成分。FFT广泛应用于信号处理、图像处理、通信系统等领域，因为它能够快速而有效地计算DFT，大大提高了处理速度。

基本原理

DFT将时域信号转换为频域信号。对于长度为 N 的复数序列 x[n]，其DFT定义为：

FFT算法

最著名的FFT算法是由库尔兹（Cooley）和图基（Tukey）在1965年提出的，通常称为Cooley-Tukey算法。该算法基于“分治”策略，将一个大问题分解为若干个小问题解决。

Cooley-Tukey基于分治策略，将一个DFT分解成许多较小的DFTs，以减少总的计算量。算法通常应用于N是2的幂次方的情况，但也可以通过修改用于其他大小。

Cooley-Tukey 步骤概述：

假设我们有一个长度为8的序列 x[0],x[1],...,x[7]。使用Cooley-Tukey算法的8点FFT详细步骤如下：

1、分解：将原始序列分成偶数部分和奇数部分。原始DFT问题就被分解成两个长度为N/2的子问题，分别对应偶数索引和奇数索引的元素。

首先，按照Cooley-Tukey算法，我们将序列分成偶数索引的部分和奇数索引的部分：

2、递归：递归地对这两个子序列应用FFT算法。这一步骤将继续进行，直到序列长度减小到足够简单（例如长度为1），可以直接计算其DFT。

接下来，我们对这两个长度为4的子序列（偶数索引序列和奇数索引序列）递归地应用FFT。每个子序列再次被分解为更小的子序列：

这一步骤会递归进行，直到子序列的长度为1，此时的FFT可以直接计算，因为长度为1的序列的FFT就是其自身。

3、组合：使用蝶形运算（一个简单的数学运算，用于结合两个小DFTs的结果来形成一个大DFT的结果）将所有小DFTs的结果合并起来，得到最终的DFT结果。

每当完成一个子序列的FFT计算后，我们使用蝶形运算将结果组合起来。对于长度为4的FFT，我们将两个长度为2的FFT结果结合起来；然后，对于长度为8的FFT，我们将两个长度为4的FFT结果结合起来。

假设递归计算后，我们得到了以下两组结果：

蝶形运算

对于序列中的每个元素 k （其中 k=0,1,...,3），进行蝶形运算：

组合的具体实例

以 k=0 为例，我们可以计算：

通过类似的方法，可以计算出 X[1], X[2], X[3], X[5], X[6], X[7]。

最终结果

通过以上的蝶形运算，我们将得到原始序列的FFT结果 X[1],...,X[7]。这个结果是经过组合偶数部分和奇数部分的FFT结果，以及应用旋转因子后得到的。

优化

位逆序排列：在FFT的执行过程中，输入信号通常需要重新排列。这是因为Cooley-Tukey算法在递归地执行过程中，会以一种特定的顺序处理数据。数据的重新排列通常是通过位逆序来完成的。
蝶形运算：蝶形运算是FFT算法中的核心，用于在每一级递归中有效地组合结果。每个蝶形操作涉及两个输入点，通过特定的加法和乘法操作，产生两个输出点。

Cooley-Tukey 变体形式

Cooley-Tukey算法主要有两种变体：时域抽选法（decimation in time, DIT）和频域抽选法（decimation in frequency, DIF）。尽管这两种变体在处理方式上有所不同，它们都遵循了分而治之的原则，通过递归地分解和组合操作以达到降低计算量的目的（两种方法的核心思想都是将DFT分解为较小的DFTs，然后递归地计算这些DFTs）。

1. 时域抽选法（DIT）

DIT FFT算法首先将序列分成偶数索引的部分和奇数索引的部分，然后分别对这两部分计算DFT，最后将结果组合起来得到完整的DFT结果。这种分解过程递归进行，直到分解的序列长度为1（一种自顶向下的方法。它首先处理整个序列，然后逐步分解为更小的部分进行处理）。具体步骤如下：

分解：将原始序列分为两部分，一部分包含偶数索引处的元素，另一部分包含奇数索引处的元素。这一步将问题规模缩小一半。
递归：对每个子序列递归地应用相同的分解过程，直到序列长度缩减到1或达到可以直接计算的简单情况。
蝶形运算：在每一级的递归中，使用蝶形运算合并计算结果，最终得到完整的DFT结果。

DIT方法的优点是逻辑清晰，易于理解和实现。它从整个序列出发，逐步深入到序列的细节。

2. 频域抽选法（DIF）

与DIT类似，DIF FFT算法也是通过递归分解的方式工作，但它是从频域的角度出发，先计算较小长度的DFT，然后合并它们以得到更长长度的DFT结果（一种自底向上的方法。与DIT相反，DIF从序列的单个元素开始，逐步将它们组合成更大的部分）。具体步骤如下：

蝶形运算：首先对序列中的每一对元素（通常是相邻元素）进行蝶形运算，这一步骤不需要元素的重排序。
合并：将步骤1中的结果组合起来，形成更大的子序列，并对这些子序列应用蝶形运算。
重复：重复步骤2，直到所有的元素都被合并为一个完整的序列，此时完成了DFT的计算。

DIF方法的特点是从细节出发，逐渐构建出整体的结果，这种方式在实际实现中可能更适合某些并行处理架构。

应用

FFT的应用非常广泛，几乎涉及到所有需要信号处理的领域，例如：

数字信号处理（DSP）：在语音处理、图像处理等领域，FFT是实现快速卷积、滤波等操作的关键技术。
通信系统：FFT用于调制解调技术中，特别是在正交频分复用（OFDM）等现代无线通信技术中扮演着核心角色。
声学：FFT用于分析不同频率的声音成分，用于声音识别、降噪等应用。
谱分析：在物理、化学等科学研究中，FFT用于分析物质的光谱特性。

应用中的关键问题

在使用快速傅里叶变换（FFT）过程中，常会遇到以下几个关键的概念和技术，它们对于理解和应用FFT至关重要。下面详细介绍这些概念：

1. 补零（Zero Padding）

补零是在信号的末尾添加零的过程，目的是增加FFT的点数，从而提高频率分辨率。通过补零，可以使FFT的输出包含更多的频率点，使得频谱更加细腻。需要注意的是，补零并不改变信号的频谱内容，只是在频谱上进行了“插值”，使其看起来更平滑（换言之，补零不能增加信号的频谱信息或改善原始信号的频率分辨率，补零实质上是在频谱中进行了插值，使得频谱看起来更平滑）。

2. 频谱泄露（Spectral Leakage）

频谱泄露是指在进行FFT时，由于信号的长度通常不是无限的，且不一定正好是周期的整数倍，导致原本应集中在某个频率的能量分散到其他频率上。这会造成频谱的模糊，使得无法准确地区分接近的频率成分。频谱泄露是离散傅里叶变换的固有属性，无法完全避免。

3. 栅栏效应（Fence Effect）

栅栏效应，也称为拾取效应，是由于FFT固定频率分辨率的特性造成的。当信号中的频率成分不正好落在FFT频率网格的点上时，会出现能量被相邻的频率点“拾取”的现象，导致频谱的不精确表示。这种效应在频谱分析中尤为显著。

4. 加窗（Windowing）

为了减少频谱泄露的影响，通常在进行FFT之前会对信号加窗。加窗是指将信号与一个窗函数进行逐点乘法操作，目的是减少信号两端的不连续性。窗函数在信号中间值较大，两端逐渐衰减到零，从而减少了非周期信号带来的边缘效应。常用的窗函数包括汉宁窗、汉明窗和布莱克曼窗等（加窗的根本目的是为了在进行FFT时，通过模拟信号的周期性延拓，使得信号的开始和结束部分平滑过渡，相互衔接。这样做可以显著减少信号在首尾部分的突变，从而有效减少频谱泄露的现象。）。

5. 细化（Interpolation）

细化是指通过数学处理提高频谱的频率分辨率的技术，不同于补零，细化尝试通过算法来估计信号中的频率成分，从而获得更精确的频率信息。细化通常在信号处理后进行，作为一种后处理步骤。

6. 频谱混叠（Spectral Aliasing）

频谱混叠发生在采样频率低于信号中最高频率成分的两倍时（违反了奈奎斯特采样定理）。在FFT分析中，如果原始信号没有经过适当的抗混叠滤波，那么高于采样频率一半的频率成分会被错误地映射（混叠）到较低的频率上，导致频谱分析结果不准确（此处大家可以搜索压缩感知相关内容，当信号可以被稀疏表示时，是可以在不满足奈奎斯特采样定理的前提下实现信号的采样，并且不产生频谱混叠）。

其他相关的概念

频率分辨率

频率分辨率是测量系统能够区分两个相邻频率成分的最小频率差异。在FFT中，频率分辨率是由总的采样时间决定的。具体来说，频率分辨率可以通过公式 Δf=1/T 来计算，其中 Δf 是频率分辨率，T 是采样时间的总长度。这意味着，通过增加采样时间（即分析的时间窗口），我们可以提高频率分辨率，使得更接近的频率成分能够被区分开。

频率步长

频率步长是离散频谱中相邻频点之间的间距。在进行FFT时，由于信号被离散化处理，整个频谱也是离散的，每个频点代表一个特定的频率。频率步长由采样率和FFT点数共同决定，具体可以通过 fs/N 计算得到，其中 fs 是采样率，N 是FFT的点数。这意味着，虽然通过增加采样时间可以提高频率分辨率，但频率步长是由采样率和FFT点数确定的，与采样时间无关。

提高准确性的策略

采样时间的选择

虽然增加采样时间可以提高频率分辨率，但对于提高频率幅值的准确度，需要考虑的是待测频率与频率步长的关系。当待测频率正好是频率步长的整数倍时，可以获得较高的频率和幅值准确度。因此，在实际应用中选择采样时间时，应考虑使采样时间与待测信号的周期成整数关系，以确保待测频率符合频率步长的整数倍。

加窗技术的应用

加窗技术可以减少频谱泄露，从而提高频率成分的幅值准确度。通过适当选择窗函数，可以在减少泄露的同时，尽可能保持频率成分的幅值不变形。

综上所述，FFT分析中频率的准确性和幅值的正确度不仅取决于采样时间的长度，还需要考虑采样策略（如采样时间与信号周期的关系、采样率与FFT点数的选择）和信号处理技术（如加窗）的综合应用。这些因素共同作用，以期达到对信号频谱的准确分析。

其他需要考虑的问题

1、频率值的准确性与频率分辨率的关系

频率分辨率决定了FFT能够区分两个相近频率的能力，而频率值的准确性指的是能否准确测量这些频率的实际值及其对应的幅值。虽然提高频率分辨率（通过增加采样时间）有助于更好地区分接近的频率，但这并不直接影响频率及其幅值的准确测量。频率值的准确性更多地受到信号截断方式和是否进行信号处理（如窗函数处理）的影响。

2、信号非周期截断对频谱图的影响（频谱泄露）

当信号在进行FFT之前被非周期性截断时，即信号的采样长度不是信号周期的整数倍，会导致频谱泄露。这意味着信号的能量会错误地分布到本应集中的频率以外的频率上，导致频谱图中频率及其幅值的不准确。

3、信号的周期延拓对频谱的影响

对信号进行周期延拓，尤其是非整周期的截断信号，虽然可以通过增加采样时间提高频率分辨率，但它会在相邻两段信号之间产生间断点，导致信号连接的不连续。这种操作虽然提高了频率分辨率，但对于提高频率值及其幅值的准确性帮助不大。

综合整周期截断和非整周期截断后的延拓次数对频谱的影响情况来看，对信号进行延拓相当于增加了采样时间，能够提高频率分辨率，但是不会改善频谱中频率及其幅值的准确性。

4、信号补零对频谱的影响

补零是在信号末尾添加零值的过程，这个操作不会改变原始频谱的基本特性，即频率值及其幅值基本保持不变。补零主要影响的是频谱的显示方式，使得频谱看起来更光滑。但是，补零并不改善频率及其幅值的准确性，且大量补零可能会引入结构变化，导致频率出现微小偏差。

补零对于原始频谱图几乎没有影响，其各频率值及其幅值在补零数量较少时没有变化，当补零数量较多时会发生微小的变化，频谱图逐渐变得更加光滑连续，但对频率及其幅值的影响很小。随着补零次数的增多，信号的结构会发生变化，频率也会有一定的偏差。

5、FFT点数不等于信号数据点数对FFT结果的影响

当FFT点数与信号数据点数不匹配时，FFT算法会对信号进行补零或截断，以匹配所需的FFT点数。如果FFT点数大于信号数据点数，系统会自动补零；如果FFT点数小于信号数据点数，则会截断信号。这种不匹配可能会影响频谱分析的结果，包括频率分辨率和频谱泄露等方面，因此选择合适的FFT点数对于获得准确的频谱分析结果至关重要。