Clarity on Bit Reversal Sorting

Started by pbowers 1 year ago5 replieslatest reply 1 year ago178 views

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?


[ - ]
Reply by jmjaureguigJune 9, 2022


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.

[ - ]
Reply by pbowersJune 9, 2022

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.

[ - ]
Reply by SlartibartfastJune 9, 2022

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.

[ - ]
Reply by TreefarmerJune 9, 2022

What language are your using to write your algorithm?

[ - ]
Reply by pbowersJune 9, 2022

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.