## Clarity on Bit Reversal Sorting

Started by 2 years ago5 replieslatest reply 2 years ago208 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?

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.

[ - ]