Hello all,

I'm going through The Scientist and Engineer's Guide to Digital Signal Processing. I'm currently on Chapter 12 - Fast Fourier Transform.
I understand the example of Interlaced Decomposition and I understand the the Bit Reversal Sorting (BRS) works, but specifically for the example shown. In Figure 12-2, the samples of a 16 point array are the integers from 0-15. The sample values describe both the location in the array and the sample value itself.
So, with these sample values in the example, it makes sense that you can use Bit Reversal Sorting to perform the decomposition efficiently.
What I'm having difficulty wrapping my head around is why, as the book says, "The FFT time domain decomposition is usually carried out by a bit reversal sorting algorithm." In real-world application, the sample values won't be increasing as integers from 0 to whatever. If you fill in the example array with arbitrary integers (using the appropriate bit-depth), bit reversal sorting will no longer work. What am I missing here?
I've written an algorithm to perform the interlace decomposition with an array holding any values, which is much more complicated than the sorting shown in Figure 12-3. To summarize my question, how can the method used in Table 12-3 be used in the real world when the numbers likely won't be so neat?

Peter

Hi,

I think that for BRS what you reverse is the memory addresses not the content of the sample values, that's why some implementations FFT requires the memory allocation to meet certain alignment requirements, to take advantage of this trick.

I appreciate the clarification. That makes sense.

I wrote an algorithm that will work for any signal with a length of 2^N (where N is some positive integer). It seems the bit reversal only works for the Time->Frequency direction, so I guess the hard part is done. Now I'm trying to understand how the frequency spectra is rearranged with the Butterfly method.

I'm not familiar with that particular book, but I'll second that the bit reversal is done on the sample addresses, not their values.   There are alternate algorithms to do the bit reversal either first or last, but it is always the sample address that gets reversed, not the value.

What language are your using to write your algorithm?

I'm writing in Javascript. I know it's probably not the best language for DSP, but I've gotten comfortable with using it as a canvas for many things. I'm not real-time processing at the moment. I'm learning how to perform the FFT from start to finish with a single signal array. I have a graphical interface that displays the signals and spectra. I'll be moving to C++ for real-time audio processing after I get beyond the basics.

I would like to create a nice DSP library for audio for Javascript at some point. I don't really like the ones I've found so far but I'm sure there is something out there that is very powerful and easy to use.
I've used Howler for some success.