Back to Home Page

//
// Bitrev - A function to generate a bit-reversed number sequence
// Author: Bob Day (bobday.nh@verizon.net)
//
// Assembly language version, September, 1973
// This version (1.0), November, 2002
//
// Copyright (C) November, 2002 by Bob Day.  All Rights reserved.
//
// This program may be used and distributed, with 
// acknowledgment to the author, under the terms
// of the GNU General Public License.
//
//
// This routine generates a sequence of bit-reversed
// numbers.  If you start "Num" at zero, it
// will generate bit-reversed 1, bit_reversed 2, 
// bit reversed 3, etc., which is what you need for
// rearranging an FFT.  This particular example generates
// bit reversed numbers in a 16 bit width.  For different
// widths, start the "bitTbl" table at the appropriate
// place.  Note that half the time the statement in the
// "while" loop is not executed at all; 1/4 the time it
// is executed once; 1/8 the time it is executed twice, 
// etc., so this routine is quite efficient.  Having
// the small table saves a machine instruction or so
// in the loop.
//
// Essentially, the Bitrev function simulates an odometer
// whose lowest order digit position is on the left,
// rather than on the right.
//

//
// Function Declarations
//
void Bitrev(unsigned short* pNum);


int main()
{
long            idx;
unsigned short  num;

num = 0;
for (idx = 0; idx < 65535; ++idx)
  {
  Bitrev (&num);
  }

return 0;
}


void Bitrev(unsigned short* pNum)
{
static unsigned short bitTbl[] = {0x8000, 0x4000, 0x2000, 0x1000, 0x800, 0x400,
                                  0x200, 0x100, 0x80, 0x40, 0x20, 0x10, 0x8, 0x4,
                                  0x2, 0x1, 0};
register unsigned short* pBitTbl;


pBitTbl = bitTbl;

while (*pNum & *pBitTbl)
  {
  *pNum ^= *pBitTbl++;
  }

*pNum |= *pBitTbl;
return;
}

Back to Home Page