3

我正在阅读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] 值呢？

我想不通

4

2 回答 2

2

当提出问题的人的专业水平未知时，试图解释代码是很困难的。这就是说：

  1. python 有一个用于序列 nl 的连接运算符。+因此该twiddles =行创建了某种序列并将数字 N 附加到它上面。
  2. twiddles[-1]访问序列中的最后一个元素，这里N是注释建议的数字。
  3. twiddles序列表达式使用复数生成由N单位圆上的点组成的序列，方法是将其分成相等的切片N。
于 2011-05-15T20:01:15.620 回答
2

您询问的代码正在执行以下操作：

+[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 参数的一部分传递给函数，而不是将其传递为一个单独的变量。

于 2011-05-15T19:53:50.167 回答