python 实现FFT快速傅立叶变换算法

快速傅立叶变换（FFT，Fast Fourier Transform）是一种有效计算离散傅立叶变换（DFT，Discrete Fourier Transform）及其逆变换的算法。DFT和其逆变换在信号处理、图像处理以及许多工程和科学领域中都有广泛的应用。FFT算法通过提高计算效率，将计算复杂度从原始的 (O(N^2)) 降低到 (O(N \log N))。

1. DFT和FFT的基本概念

离散傅立叶变换的定义是：

[ X[k] = \sum_{n=0}^{N-1} x[n] e^{-i \frac{2 \pi}{N} kn} ]

其中，(x[n]) 是输入的离散信号，(X[k]) 是输出的频域信号，(N) 是信号的长度，(k) 是频率索引。

快速傅立叶变换的基本思想是利用信号的周期性和对称性，将大规模的DFT计算分解为多个小规模DFT的计算，从而实现更快的计算。

2. FFT的算法实现

下面是一个基于分治法的FFT算法实现。我们将使用递归的方法来计算FFT。

import numpy as np

def FFT(x):
    N = len(x)
    if N <= 1:
        return x
    even = FFT(x[0::2])  # 取偶数项
    odd = FFT(x[1::2])   # 取奇数项
    T = [np.exp(-2j * np.pi * k / N) * odd[k] for k in range(N // 2)]
    return [even[k] + T[k] for k in range(N // 2)] + \
           [even[k] - T[k] for k in range(N // 2)]

# 测试FFT函数
if __name__ == "__main__":
    # 生成一个测试信号
    fs = 8  # 采样频率
    t = np.arange(0, 1, 1/fs)  # 1秒的时间向量
    freq1 = 2  # 信号1的频率
    freq2 = 3  # 信号2的频率
    x = 0.5 * np.sin(2 * np.pi * freq1 * t) + 0.5 * np.sin(2 * np.pi * freq2 * t)

    # 计算FFT
    X = FFT(x)

    # 输出结果
    freq = np.fft.fftfreq(len(x), d=1/fs)  # 计算频率分量
    print("频率分量:", freq)
    print("FFT结果:", X)

3. 代码解析

1. FFT函数：函数接受一个数组 x，首先判断数组的长度。如果数组长度小于等于1，就直接返回该数组（递归终止条件）。

2. 递归调用：对于数组的偶数项和奇数项分别调用FFT函数，得到 even 和 odd。

3. 合成结果：使用公式计算 (T)（代表乘以根号下的单位复数），并组合得到最终的FFT结果。

4. 测试数据：生成了一个包含两个不同频率正弦波的信号，然后调用FFT函数进行变换，最后打印出频率分量及FFT结果。

4. 总结

快速傅立叶变换为信号处理提供了强大的工具，极大地提高了频域分析的效率。虽然以上的实现是一个简单的递归版本，Python中的NumPy库提供了更加优化的FFT实现。在实际应用中，利用现成的库往往更加高效和方便。了解FFT的基本原理和实现方法，对深入学习信号处理和数字信号分析是非常重要的。