I always found this Fast Fourier Transform (FFT) business a little foggy. Now what happened is that on my new Leopard distribution after the installation of Matplotlib I found that I had the fft function but not the ifft function… So in the end I took the legendary Numerical Recipes book and I started to convert the C++ version in python. Well, let me say that it wasn’t that trivial since the C++ version was based on vectors with intercalated real and imaginary parts which were messing up the understanding of the indexes in some of the for loops… In the end I managed. Here is the code for the function needed: you need a function to rearrange the input vector reversing position according their number in binary format (i.e. 0101 goes into 1010 and 0001 into 1000 etc.)… here is the code:
""" This function serves as a base for the calculation of FFT. It simply swaps vector elements just according to their position expressed in binary digits. For example using a vector of lenght 16 (4 bits), the vector element 4 = 0100 transforms into 0010 = 2 and 10 = 1010 goes into 0101 = 5 and so on... """ def bitReverse(x): xn = 1.0*x N = int(len(xn)) if N%2 != 0: raise ValueError, 'N is not power of 2' j = 0 for i in range(0,N): if j>i: shelf = xn[j] xn[j] = xn[i] xn[i] = shelf m = N/2 while (m >= 2 and j > m-1): j = j-m m = m >> 1 j += m return xn
