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

Question

我正在阅读cooley tukey 方法是如何工作的，但我对以下的 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

你问的代码在做以下事情：

+[N] # appends N to the end of the array


twiddles[-1] # is the last element of the array ( the N in this case ).

这段代码似乎是为了方便，把'N'加到twiddles数组的末尾。这样做的目的是为了后面使用时更方便，并且可以把它作为twiddles参数的一部分传给函数，而不需要单独传一个变量。

Answer 2

当我们不知道提问者的技术水平时，解释代码会比较困难。不过，我试着来讲解一下：

1. 在Python中，有一个可以把多个序列连接在一起的操作符叫做+。所以，twiddles = 这一行代码是创建了一个序列，并把数字N加到这个序列里。
2. twiddles[-1] 是用来获取序列中的最后一个元素，这里就是数字N，正如注释所说的那样。
3. twiddles 这个序列是用复数来生成的，它会把单位圆分成N等份，从而得到N个点。