Reversing Bit for FFT in Python

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

Hysteric Avocado Sauce

 La cena deve iniziare con un aperitivo degno di nota, di gusto, di carattere… un po’ esotico magari. Questo e’ quello che stavi cercando. La musica consigliata per la preparazione sono i Gotan Project con le loro note calde, un po’ magiche.

Ingredienti:

•  1 avocado
• 1/4 di cipolla
• 1/2 pomodoro
• 1 lime
• tabasco
• olio di oliva
• pepe

Preparazione:quindi si comincia con il pelare l’avocado. Si taglia grosolanamente la polpa in pezzi. La stessa cosa va fatta per il pomodoro privato dei semi e del quartino di cipolla. Mettere il tutto nel bicchire di un mixer e frullare il tutto aggiungendo il succo di un lime e l’olio di oliva. Gradualmente si aggiunge poi il tabasco e si continua a frullare fino a quando la salsa non raggiunge il livello desiderato di piccantezza. Notare che la spicy sensation arriva in ritardo rispetto al gusto dell’avocado e dovrebbe essere solo una “sensation” e non uno shock… Si puo’ regolare la sapidita’ e aggiungere del pepe e/o del coriandolo. L’ideale e’ servire con patatine messicane poco piccanti.