bit reverse

Hi,

I generated the tables.  Basically I fed the fft a input vector which results in an output vector that just counts up from 1-4k  (or 8k in your case).  To figure out what input vector to use,  do an inverse fft on a vector that counts up 1-8k in matlab or with CMSIS.  Then, with bit reverse disabled, feed this input vector to CMSIS forward fft.  Now the output is all jumbled and you need to figure out what swaps to do.  I wrote a short script to swap pairs of indexes in the output until the output was the 1-4k counting vector and recorded the swaps.

The last relevant part, in order to fully optimize arm_bitreversal, I downshifted the bit reversal table so that I would not have to do it on the fly.

There was a thread on here somewhere, where some people translated arm_bitreversal_32 from assembly into C.  I can't seem to find it anymore though.

I recently translated the 16 bit function, but haven't had time to test my results.  Maybe it will help though:

/*

* @brief  In-place bit reversal function.

* @param[in, out] *pSrc        points to the in-place buffer of unknown 32-bit data type.

* @param[in]      bitRevLen    bit reversal table length

* @param[in]      *pBitRevTab  points to bit reversal table.

* @return none.

*/

static void arm_bitreversal_16(uint16_t * pSrc, uint16_t bitRevLen, const uint16_t * pBitRevTable)

{

   uint32_t v0, v1, i;

   uint32_t *p0, *p1;

   for (i = (bitRevLen + 1) >> 1; i > 0; i--) {

      p0 = (uint32_t*)((uint8_t*)pSrc + (pBitRevTable[0] >> 1));

      p1 = (uint32_t*)((uint8_t*)pSrc + (pBitRevTable[1] >> 1));

      v0 = *p0;

      v1 = *p1;

      *p0 = v1;

      *p1 = v0;

      pBitRevTable += 4;

   }

}

If I find my old script to print out the swaps necessary, I'll post it here.

Cheers,

Dan

edited the code to fix a flaw

Hi,

I generated the tables.  Basically I fed the fft a input vector which results in an output vector that just counts up from 1-4k  (or 8k in your case).  To figure out what input vector to use,  do an inverse fft on a vector that counts up 1-8k in matlab or with CMSIS.  Then, with bit reverse disabled, feed this input vector to CMSIS forward fft.  Now the output is all jumbled and you need to figure out what swaps to do.  I wrote a short script to swap pairs of indexes in the output until the output was the 1-4k counting vector and recorded the swaps.

The last relevant part, in order to fully optimize arm_bitreversal, I downshifted the bit reversal table so that I would not have to do it on the fly.

There was a thread on here somewhere, where some people translated arm_bitreversal_32 from assembly into C.  I can't seem to find it anymore though.

I recently translated the 16 bit function, but haven't had time to test my results.  Maybe it will help though:

/*

* @brief  In-place bit reversal function.

* @param[in, out] *pSrc        points to the in-place buffer of unknown 32-bit data type.

* @param[in]      bitRevLen    bit reversal table length

* @param[in]      *pBitRevTab  points to bit reversal table.

* @return none.

*/

static void arm_bitreversal_16(uint16_t * pSrc, uint16_t bitRevLen, const uint16_t * pBitRevTable)

{

   uint32_t v0, v1, i;

   uint32_t *p0, *p1;

   for (i = (bitRevLen + 1) >> 1; i > 0; i--) {

      p0 = (uint32_t*)((uint8_t*)pSrc + (pBitRevTable[0] >> 1));

      p1 = (uint32_t*)((uint8_t*)pSrc + (pBitRevTable[1] >> 1));

      v0 = *p0;

      v1 = *p1;

      *p0 = v1;

      *p1 = v0;

      pBitRevTable += 4;

   }

}

If I find my old script to print out the swaps necessary, I'll post it here.

Cheers,

Dan

edited the code to fix a flaw

Hi Daniel,

There was a thread on here somewhere, where some people translated arm_bitreversal_32 from assembly into C.  I can't seem to find it anymore though.

Are you referring to this Convert arm_bitreversal2.S file to c code?

Regards,

Goodwin

yup that's it.  Good thing too, cause I now see a flaw in the code I posted here.  I forgot about the data being a complex pair.  In the assembly I got around this by loading the pair all at once as a 32 bit number (even though its actually 2 16 bit numbers).  But in my posted C code, I'm only loading 16 bits.  So here is a modified version that loads the 32 bits rather than 16.

/*

* @brief  In-place bit reversal function.

* @param[in, out] *pSrc        points to the in-place buffer of unknown 32-bit data type.

* @param[in]      bitRevLen    bit reversal table length

* @param[in]      *pBitRevTab  points to bit reversal table.

* @return none.

*/

static void arm_bitreversal_16(uint16_t * pSrc, uint16_t bitRevLen, const uint16_t * pBitRevTable)

{

  uint32_t v0, v1, i;

  uint32_t *p0, *p1;

  for (i = (bitRevLen + 1) >> 1; i > 0; i--) {

      p0 = (uint32_t*)((uint8_t*)pSrc + (pBitRevTable[0] >> 1));

      p1 = (uint32_t*)((uint8_t*)pSrc + (pBitRevTable[1] >> 1));

      v0 = *p0;

      v1 = *p1;

      *p0 = v1;

      *p1 = v0;

      pBitRevTable += 4;

  }

}