radix-2 fft 代码实现

下面是一个使用Python实现的基于Cooley-Tukey算法的Radix-2快速傅里叶变换（FFT）的示例代码：

import numpy as np

def fft_radix2(x):
    N = len(x)
    if N <= 1:
        return x
    even = fft_radix2(x[0::2])
    odd = fft_radix2(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]
X = fft_radix2(x)
print(X)

这段代码实现了一个基于Cooley-Tukey算法的递归式Radix-2 FFT。它接受一个长度为2的幂次方的输入序列x，并返回其傅里叶变换结果X。在示例中，输入序列x为[0, 1, 2, 3]，通过调用`fft_radix2(x)`计算其FFT并打印结果。

Radix-2 FFT是一种将傅里叶变换分解为多个较小规模的子问题来加速计算的方法。它使用了递归的思想，将输入序列分为偶数索引和奇数索引的两个子序列，并利用旋转因子将它们重新组合起来。这个过程递归地进行，直到最终得到FFT的结果。

请注意，这只是一个简单的示例代码，用于说明Radix-2 FFT的基本实现方式。在实际应用中，可能需要考虑性能优化、处理边界条件等其他因素。