# Performed the Danielson-Lanczos shuffling for FFT, but I don't know what to do next

I'm writing an audio analysis program and need to do some FFT to frames of the data. I've got some code (rather verbose so I'll leave out the details) that successfully performs the shuffling of the data according to the Danielson-Lanczos Lemma through bit reversal of indices. For example the sequence of data 0,1,2,3,4,5,6,7 becomes 0,2,4,6,1,3,5,7 (though I'm working with a larger window than 8 samples!)

The problem is that I'm a little confused on what to do with the resultant vector. I'm just completely lost. I've read something about doing the transform on pairs of data points and then combining them. So would I apply the DFT to 0 and 2, then add the resulting vector with that of the DFT of 4 and 6 (using the above example data points) and add that to (DFT(1,3) + DFT(5,7))?

If it matters, I'm dealing with just the right channel of a wav file, so the signal has no imaginary part.

(I'm developing in Unity with C# and the only libraries j could find are .Net 4.0, and Unity only supports 3.5 right now. Plus I think it's interesting, if not confusing!)

• Welcome to DSP.SE! I'm wondering why you're rolling your own FFT? There are several libraries available that do it all for you. I'm not saying you shouldn't! Just that your aim doesn't seem to be to learn the FFT, but to apply it to solve a problem. – Peter K. Dec 8 '15 at 19:07
• The signal may not have an imaginary part, the the intermediate values and the result very often will. The next step is repeating a DFT butterfly. Writing ones own FFT and understanding how it works, before blindly using a canned FFT library (there are many), is a great learning exercise. – hotpaw2 Dec 8 '15 at 19:29
• Aside from the learning experience, I'm writing in C# and using the code in Unity, which only supports .net 3.5 as far as I'm aware. All the libraries I've found use .net 4.0 – Liz Dec 8 '15 at 20:14
• This project appears to be open source C# that seems to predate 3.5. – Peter K. Dec 8 '15 at 20:17

The problem is that I'm a little confused on what to do with the resultant vector.

You have not a resultant vector, you have two vectors [0,2,4,6], [1,3,5,7] and by the D-L lemma you can compute the DFT of the original vector as a linear combination of the DFTs of these two vectors.

Taking into account that the two shorter DFTs are periodic and that the combination coefficients for the second half are the negative of the coefficients used for the first half, we are lead either to a very simple recursive implementation of the FFT algorithm or to more complicated implementations that don't use recursion. Let's stay simple...

In a pythonesque pseudocode, the recursive implementation can be written as simply as

def fft(x,n,e):
if n==1:
X = x # the DFT of a scalar is the scalar itself
return X
else:
X0, X1 = fft(x[0::2],n/2,e[0::2]), fft(x[1::2],n/2,e[0::2])
X0, X1 = X0 + e*X1, X0-e*X1
X = concatenate(X0,X1)
return X


where

• x is the vector of which we want to compute the DFT
• n is its length
• e is a vector with the so called _twiddle_factors_, that is one half of the n-th roots of unity (from the lower part of the unit circle for forward DFT, from the upper otherwise)

and the [start:stop:step] notation stands for a selection of the elements of a vector, with a missing stop meaning to the end.

To call fft you have to provide the initial vector of twiddle factors

X = fft( x,  n, exp(-2*pi*1j*(0..n/2-1)/n)) # forward
x = fft(X/n, n, exp(+2*pi*1j*(0..n/2-1)/n)) # inverse


where 1j id the imaginary unit and (0..n/2-1) indicates an aritmetic progression from 0 to n/2-1, extremes included.

• sorry, by a single vector I meant the modulus of each portion of data (being comprised as the square root of the sum of the real and imaginary parts each squared). By combining the two, I obtain one, and I've sorted out what to do with the bin indexes now to relate them to frequency, but I'm not clear on what the modulus of the frequency spectrum means. It is the power of each sinusoidal of corresponding frequency during that particular frame, is it not? How does one go about converting that to decibels? Decibel conversion requires a reference value. What would that be in this case? – Liz Dec 10 '15 at 20:41