Geek asks and answers

Cooley Tukey twiddle factor in simple python script

I read 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 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 twiddles = [math.e ** (inv * 2j * math.pi * k / N) for k in xrange (M)] + [N] line do? It seems to be an array, but why + [N]?

And why access to the value of twiddleles [-1] then?

I can't figure it out

+3
source share
2 answers

Trying to explain the code when the level of knowledge of the person asking the question is unknown is difficult. It says here:

  • python has a concatenation operator for nl sequences. +, so the line twiddles =creates some sequence and adds the number N.
  • twiddles[-1] N, .
  • twiddles , N , N .
+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 .

+2

More articles:


All Articles