Where do I get bit reverse table?

I don't know where to get the actual table required but I can explain how to generate one and what it is for regarding FFT algorithms.

To do a bit reverse table is just a nested for loop like this

// using TABLE_RADIX forces table size to be a power of 2
int brev[ 1 << TABLE_RADIX ];

for( int i = 0; i < ( 1 << TABLE_RADIX ); i++ ) // for all indexes
{
  brev[i] = 0;
  for( int j = 0; j < TABLE_RADIX; j++ ) // only count bits here
  {
    brev[i] <<= 1;
    brev[i] |= ( i >> j ) & 1;
  }
}

The purpose of having this table is due to a quirk of the FFT algorithm.  As it turns out, the indexing done in the FFT algorithm (and the IFFT too) relates the input index to the output index in a manner where reversing the bits of the input index creates the appropriate index for the output.  As you can see the inner for loop would have to be run for every input to output index operation of the FFT algorithm so by creating a table up front, the FFT algorithm can be run multiple times and only needs to be calculated once.  Further, if this table is calculated at compile time, then there is no dynamic initialization necessary at all. Now, it is simply a look up into the table using the input index to generate the output index.  Some DSP's have a special addressing mode that does this automatically eliminating the need for the table all together.

Jim Noxon

Hi Noxon, thank you for your code. I have tried your code to generate the brev, but seems the code got some error. I just like to confirm with you if the logic '( 1 << TABLE_RADIX )' in line number 4 is correct. It is because the result will become zero after shifting and causing the outer loop to loop for once only. By the way, as from the dsplib documentation, the brev is describe as 'Pointer to bit reverse table containing 64 entries', so what's the 64 entries means, does it means TABLE_RADIX = 64 ? Thank you

Yes, the line of code is correct.  The 64 entries refers to a table of only 64 numbers.  Thus TABLE_RADIX should be 6 since 2^6=64.  This way, you will not shift the 1 bit all the way off the left side and the outer loop will operate as expected.

Then when it asks you to provide a pointer, merely pass it brev as this will be converted to a pointer to the beginning of the table automatically.

Jim Noxon