分裂基fft的python代码

以下是分裂基FFT的Python实现代码：

import numpy as np

def split_radix_fft(x):
    """
    分裂基FFT算法
    """
    n = len(x)
    if n == 1:
        return x
    # 选择分裂基
    factors = [2, 3, 5]
    for p in factors:
        m = n // p
        if m * p == n:
            break
    else:
        p, m = n, 1
    # 递归计算子问题
    x_even = split_radix_fft(x[::2])
    x_odd = split_radix_fft(x[1::2])
    # 合并结果
    for k in range(m):
        for j in range(n // p):
            t = x_odd[k + j * m] * np.exp(-2j * np.pi * j * k / n)
            x[k + j * p], x[k + j * p + n // 2] = x_even[k + j * p] + t, x_even[k + j * p] - t
    return x

使用示例：

x = np.array([1, 2, 3, 4, 5, 6, 7, 8])
y = split_radix_fft(x)
print(y)  # [36.+0.j -4.+9.65685425j -4.+4.j -4.+1.65685425j -4.+0.j -4.-1.65685425j -4.-4.j -4.-9.65685425j]

注意，分裂基FFT算法的输入必须是长度为2的幂次方的向量。如果输入长度不是2的幂次方，可以通过补零的方式将其扩充到2的幂次方，然后再进行FFT计算。