bit reverse

Hi dangould and welcome to the Community!

I have moved your question to Software Development Tools where I think someone should be able to help.

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

Hi dangould,

First, please clarify that you just want to extend the CMSIS-DSP FFT function to handle 8192 sample length,  you are not writing your own FFT function which will be able to handle this longer number of samples.

Doing the bit reversal for the new length is not very hard. The difficulty that you have to resolve in extending an existing FFT function for handling longer data is in the twiddle factors. Problems that may arise include:

• Obstacle in expanding the twiddle factors. You will need twice the memory (compared to the longest, 4096-point, FFT function in CMSIS-DSP library), it should be a contiguous block. If something occupies the memory after the last data in the previous shorter twiddle factor table you have to find a way to "push it aside" to accommodate the twofold increase in twiddle factors. Alternatively, you can get the needed memory somewhere else and modify the pointer that the existing FFT function uses for the twiddle factors.

• If you will be able to solve or circumvent the first obstacle, the next problem is making the existing FFT function get the correct twiddle factors corresponding to data samples. Perhaps, you have to organize the twiddle factors in unusual arrangement or you can modify the step size through the twiddle factor table. As of this time I don't have a clear idea about the details of implementation of FFT functions in CMSIS-DSP, if you have a comprehensive documentation, better yet, the source code, they are of great help.

I believe that's the problem that you should plan to solve first. After you have crafted your solution you have to weigh the advantages and disadvantages compared to writing a new function. A factor to consider is if your application will only handle the longer number of samples or will still support the shorter FFT lengths.

If you have a bright idea, however, please share it with us. Even if you think your idea is not rigid, fellow members may be able to help polish it.

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;

  }

}

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

By the way, depending on your application, your input to the FFT might be real data. If that is the case you can represent your data in Q15 or Q31 format. The Q15 and Q31 versions of Real FFT functions in CMSIS-DSP support a length of 8192.

Thanks for the input all. Time line is short, so I adjusted my path and have decomposed the FFT into smaller FFTs to generate the needed 8k FFT. Likely not the most optimal solution, but meets the requirements.

For those interested in the algorithm...

UltraLong FFT - Dillon Engineering