基2蝶形fft算法代码

基2蝶形FFT（Fast Fourier Transform）算法是一种高效的离散傅里叶变换算法，它的核心思想是利用递归分解和分治策略，将大数组的DFT分解成一系列小数组的DFT和一些简单的计算步骤。在Python中，可以使用numpy库中的`fft`函数来实现蝶形FFT，以下是基本的代码示例：

import numpy as np

def fft(x):
    N = len(x)
    if N == 1:
        return x
    else:
        X_even = fft(x[0::2])  # 对偶数索引的部分做FFT
        X_odd = fft(x[1::2])   # 非对偶数索引的部分做FFT
        factor = np.exp(-2j * np.pi * np.arange(N) / N)  # 蝶形因子
        result = np.concatenate((X_even + factor[:N//2] * X_odd,  # 结合奇数索引的结果
                                X_even + factor[N//2:] * X_odd))  # 结合偶数索引的结果
    return result

# 使用示例
x = np.array([1, 2, 3, 4])
y = fft(x)

在这个代码中，`fft()`函数首先检查输入向量的长度是否为1，如果是，则直接返回该向量，因为它已经是频域表示了。然后，通过递归地对数组的两半应用FFT，并利用特定的蝶形因子计算合并结果，实现了基2的FFT。