开发者

Cooley Tukey twiddle factor in a simple python script

I'm reading how the cooley tukey method works, but I have a few problems with the following python script:

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

What does the twiddles = [math.e**(inv*2j*math.pi*k/N) for k in xrange(M)]+[N] line does? Seems like an array but why the +[N]?

And why accessing the twiddles[-1] value then?

I can't figure this out


Trying to explain code when the level of expertise of the person asking the question is unknown is difficult. That said here it goes:

  1. python has a concatenation operator for sequences nl. + so the twiddles = line creates a sequence of some sort and appends the number N to it.
  2. twiddles[-1] accesses the last element in the sequence here the number N as the comments suggest.
  3. the twiddles sequence expression uses complex numbers to generate a sequence consisting of the N points on the unit circle by dividing it in N equal slices.


The code you asked about is doing the following:

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


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

The code appears to add the 'N' to the end of the twiddles array just for convenience, so that it can be used later, and so that it can easily be passed to the function as part of the twiddles argument instead of passing it as a separate variable.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜