用Python写一个FFT+CZT算法程序

下面是一个使用Python实现FFT+CZT算法的程序：

import numpy as np

def czt(x, w):
    """
    CZT算法实现函数
    :param x: 输入序列
    :param w: 旋转因子
    :return: CZT变换结果
    """
    n = len(x)
    y = np.zeros(n, dtype=np.complex128)
    m = len(w)
    a = np.zeros((m, n), dtype=np.complex128)
    b = np.zeros((m, n), dtype=np.complex128)

    for i in range(m):
        for j in range(n):
            a[i][j] = w[i] ** j

    for i in range(m):
        b[i] = np.fft.fft(x * a[i])

    for j in range(n):
        for i in range(m):
            y[j] += w[i] ** (-j) * b[i][j]

    return y

def fft_czt(x):
    """
    FFT+CZT算法实现函数
    :param x: 输入序列
    :return: FFT+CZT变换结果
    """
    n = len(x)
    w = np.exp(-2j * np.pi / n)
    y = np.zeros(n, dtype=np.complex128)

    if n == 1:
        y[0] = x[0]
    else:
        xe = x[0::2]
        xo = x[1::2]
        ye = fft_czt(xe)
        yo = fft_czt(xo)
        for k in range(n):
            y[k] = ye[k % (n // 2)] + w ** k * yo[k % (n // 2)]

    return czt(y, w)

# 示例代码
x = np.array([1, 2, 3, 4, 5, 6, 7, 8])
y = fft_czt(x)
print(y)

上面的程序定义了 `czt` 和 `fft_czt` 两个函数，其中 `czt` 函数实现了CZT算法，`fft_czt` 函数则是在FFT算法基础上使用CZT算法实现的FFT+CZT算法。程序使用了Numpy库中的数组和计算函数，可以快速地进行向量化计算。在示例代码中，我们使用输入序列 `[1, 2, 3, 4, 5, 6, 7, 8]` 进行变换，并输出结果。