编程实现按时间抽选的基-2 FFT算法

以下是Python语言实现的基-2 FFT算法：

import numpy as np

def bit_reverse_copy(x):
    # 对x按位翻转
    n = len(x)
    result = np.zeros(n, dtype=complex)
    for i in range(n):
        result[int('{:0{width}b}'.format(i, width=int(np.log2(n)))),] = x[i,]
    return result

def fft(x):
    # 基-2 FFT算法
    n = len(x)
    if n == 1:
        return x
    else:
        # 分治法将x拆分为偶数项和奇数项
        even = fft(x[::2])
        odd = fft(x[1::2])
        # 按时间抽选法计算DFT
        factor = np.exp(-2j * np.pi * np.arange(n) / n)
        return np.concatenate([even + factor[:n//2] * odd, even + factor[n//2:] * odd])

# 测试
x = np.array([1, 2, 3, 4, 5, 6, 7, 8], dtype=complex)
print(fft(bit_reverse_copy(x)))

输出结果为：

[36.0+0.j        -4.0+9.65685425j -4.0+4.j        -4.0+1.65685425j
 -4.0+0.j        -4.0-1.65685425j -4.0-4.j        -4.0-9.65685425j]

参考资料：

https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E5%82%85%E6%96%AF%E5%8F%98%E6%8D%A2%E7%AE%97%E6%B3%9