快速傅里叶变换的python

实现：

import numpy as np

def fft(x):
    """快速傅里叶变换"""
    x = np.asarray(x, dtype=float)
    N = x.shape[0]
    if N % 2 > 0:
        raise ValueError("必须是2的幂次方.")
    elif N <= 32:  
        return dft(x)
    else:
        X_even = fft(x[::2])
        X_odd = fft(x[1::2])
        factor = np.exp(-2j * np.pi * np.arange(N) / N)
        return np.concatenate([X_even + factor[:int(N / 2)] * X_odd,
                               X_even + factor[int(N / 2):] * X_odd])

def dft(x):
    """离散傅里叶变换"""
    x = np.asarray(x, dtype=float)
    N = x.shape[0]
    n = np.arange(N)
    k = n.reshape((N, 1))
    M = np.exp(-2j * np.pi * k * n / N)
    return np.dot(M, x)

if __name__ == "__main__":
    x = np.random.random(1024)
    print(np.allclose(np.fft.fft(x), fft(x)))  # 验证结果是否正确

说明：

该代码实现了一个快速傅里叶变换的函数`fft(x)`，使用递归的方式进行计算，如果输入序列长度小于等于32，则使用离散傅里叶变换`dft(x)`计算，否则将输入序列分成偶数项和奇数项，分别进行递归计算，并使用旋转因子将结果合并。在主程序中，随机生成一个长度为1024的序列，并与numpy库中的fft函数进行比较，验证结果是否正确。