python - 简单 python 脚本中的 Cooley Tukey 旋转因子

Question

我正在阅读 cooley tukey method works ，但我在使用以下 python 脚本时遇到了一些问题:

def fft_CT_twiddles(x, inverse = False, verbose = False, twiddles = None) :
    """
    Computes the DFT of x using Cooley-Tukey's FFT algorithm. Twiddle factors
    are precalculated in the first function call, then passed down recursively.
    """
    t = time.clock()
    N = len(x)
    inv = -1 if not inverse else 1
    if N % 2 :
        return dft(x, inverse, False)
    M = N // 2
    if not twiddles :
        twiddles = [math.e**(inv*2j*math.pi*k/N) for k in xrange(M)]+[N]
    x_e = x[::2]
    x_o  = x[1::2]
    X_e = fft_CT_twiddles(x_e, inverse, False, twiddles)
    X_o  = fft_CT_twiddles(x_o, inverse, False, twiddles)
    X = []
    for k in range(M) :
        X += [X_e[k] + X_o[k] * twiddles[k * twiddles[-1] // N]]
    for k in range(M,N) :
        X += [X_e[k-M] - X_o[k-M] * twiddles[(k - M) * twiddles[-1] // N]]
    if inverse :
        X = [j/2 for j in X]
    t = time.clock() - t
    if verbose :
        print "Computed","an inverse" if inverse else "a","CT FFT of size",N,
        print "in",t,"sec."
    return X

什么是 twiddles = [math.e**(inv*2j*math.pi*k/N) for k in xrange(M)]+[N]线呢？看起来像一个数组，但为什么是 +[N]？

然后为什么要访问 twiddles[-1] 值？

我想不通

Answer 1

在不知道提问者的专业水平的情况下尝试解释代码是很困难的。话虽如此:

1. python 有一个用于序列 nl 的串联运算符。 + 因此 twiddles = 行创建了某种序列并在其后附加了数字 N。
2. twiddles[-1] 访问序列中的最后一个元素，如注释所示，此处为编号 N。
3. twiddles 序列表达式使用复数生成由单位圆上的N 个点组成的序列，将其分成N 等于切片。