实序列的FFT代码实现

以下是实序列FFT的代码实现，假设输入的实序列长度为 $N$：

import math

def fft_real(x):
    N = len(x)
    # 补成长度为2N的复序列
    x_complex = [0] * (2*N)
    for i in range(N):
        x_complex[i] = x[i]
    # 对补成的复序列进行FFT变换
    fft_complex(x_complex)
    # 根据FFT的对称性质，进行特殊处理
    X = [0] * N
    X[0] = x_complex[0].real
    X[N//2] = x_complex[N].imag
    for k in range(1, N//2):
        re = (x_complex[k] + x_complex[2*N-k].conjugate()).real
        im = (x_complex[k] - x_complex[2*N-k].conjugate()).imag
        X[k] = re
        X[N-k] = im
    return X

def fft_complex(x):
    N = len(x)
    if N == 1:
        return
    # 分别对奇偶数位进行FFT变换
    even = [x[i] for i in range(0, N, 2)]
    odd = [x[i] for i in range(1, N, 2)]
    fft_complex(even)
    fft_complex(odd)
    # 合并结果
    for k in range(N//2):
        t = math.e ** (-2j * math.pi * k / N) * odd[k]
        x[k] = even[k] + t
        x[k+N//2] = even[k] - t

其中，`fft_complex` 函数实现的是标准的复序列FFT变换，`fft_real` 函数则根据实序列FFT的算法步骤，对补成的复序列进行特殊处理，并返回实序列的FFT变换结果。