傅里叶变换实现代码python

以下是Python实现的傅里叶变换代码：

import numpy as np

def DFT(x):
    """
    Discrete Fourier Transform (DFT)
    """
    N = len(x)
    X = np.zeros(N, dtype=np.complex)
    for k in range(N):
        for n in range(N):
            X[k] += x[n] * np.exp(-2j * np.pi * k * n / N)
    return X

def FFT(x):
    """
    Fast Fourier Transform (FFT)
    """
    N = len(x)
    if N == 1:
        return x
    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[:N//2] * X_odd,
                           X_even + factor[N//2:] * X_odd])

其中，DFT函数是使用暴力方法实现的离散傅里叶变换，FFT函数是使用快速傅里叶变换算法实现的傅里叶变换。

使用方法：

x = np.array([1, 2, 3, 4])
X = DFT(x)
print(X)
X = FFT(x)
print(X)

输出：

[10.+0.j -2.+2.j -2.+0.j -2.-2.j]
[10.+0.j -2.+2.j -2.+0.j -2.-2.j]