Main Archive Specials Wiki | FAQ Links Submit Forum


Bit-Reversed Counting

References : Posted by mailbjl[AT]yahoo[DOT]com

Notes :
Bit-reversed ordering comes up frequently in FFT implementations. Here is a non-branching algorithm (given in C) that increments the variable "s" bit-reversedly from 0 to N-1, where N is a power of 2.

Code :
int r = 0; // counter
int s = 0; // bit-reversal of r/2
int N = 256; // N can be any power of 2
int N2 = N << 1; // N<<1 == N*2

do {
printf("%u ", s);
r += 2;
s ^= N - (N / (r&-r));
}
while (r < N2);



Comments


Added on : 10/08/05 by wahida_r[ AT ]yahoo[ DOT ]com
Comment :
   This will give the bit reversal of N number of elements(where N is a power of 2). If we want reversal of a particular number out of N,is there any optimised way other than doing bit wise operations          



Added on : 30/03/06 by mailbjl[ AT ]yahoo[ DOT ]com
Comment :
There's a better way that doesn't require counting, branching, or division.  It's probably the fastest way of doing bit reversal without a special instruction.  I got this from Jörg's FXT book:

unsigned r; // value to be bit-reversed

// Assume r is 32 bits
r = ((r & 0x55555555) << 1) | ((r & 0xaaaaaaaa) >> 1);
r = ((r & 0x33333333) << 2) | ((r & 0xcccccccc) >> 2);
r = ((r & 0x0f0f0f0f) << 4) | ((r & 0xf0f0f0f0) >> 4);
r = ((r & 0x00ff00ff) << 8) | ((r & 0xff00ff00) >> 8);
r = ((r & 0x0000ffff) << 16) | ((r & 0xffff0000) >> 16);




Added on : 20/09/10 by frankyfm[ AT ]web[ DOT ]de
Comment :
The way mentioned in the comment might be faster but is fixed to 32 bits. If you do a FFT with 1024 points you need 10 bits bit-reversal. Thus the originally mentioned algorithm is more flexible because it works for any bit width. If you use it for FFT (that's actually the only case you normally use bit-reversal) you either need to calculate the bit-reversal for each array index, so counting upwards in bit-reversal order is not such a bad way. I'm not sure whether the second algorithm is really faster than the counter if you consider the whole array. (There are 5 instructions per line making 25 instructions in sum for each calculated index with the second algorithm compared to 7 instructions in the counting algorithm)    



Add your own comment
Comments are displayed in fixed width, no HTML code allowed!
Email:

Comment:

Are you human?



Site created and maintained by Bram
Graphic design by line.out | Server sponsered by fxpansion