python实现FFT

FFT（快速傅里叶变换）是一种高效的算法，用于计算离散傅里叶变换（DFT）。在Python中，可以使用NumPy库中的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)]

x = [0, 1, 2, 3, 4, 5, 6, 7]
result = fft(x)
print(result)

这个实现使用了递归，分别对一个序列的偶数和奇数部分进行FFT计算，然后合并结果。在合并结果时，需要乘上旋转因子，即np.exp(-2j * np.pi * k / n)。

使用上述代码，可以对一个长度为2的n次幂的序列进行FFT计算。对于其他长度的序列，可以使用填充（padding）或截断（truncation）的方法来将序列长度调整为2的n次幂。