As a follow up to a post I made on stackexchange [here][1].  In reference to the CMSIS/DSP Float32 FFT implementation, found [here][2], starting on line ```1162```.  This function implements their complex FFT, and provides an input parameter for en/disabling bit reversal.  It is clear from the source that the bit reversal is applied after the FFT algorithm proper, on line ```1202```.  From this, we know that the same algorithm is used for both forward and inverse transforms.

My question is, why would that be useful as an input parameter?  If the forward transform is applied to a signal without bit reversal, then the inverse transform of that transformed signal without bit reversal would not give you the input signal.

My initial thought was that this would be handy for convolution, because as RBJ and Fat32 pointed out, bit reversal can be avoided when doing convolution if the correct implementation of the forward and inverse transforms are used.  However, after my previous question was answered, I confirmed that this library produces garbage if the forward/inverse transform is applied without bit reversal.  Does anyone have any insight as to why one would bother to offer that as an option?

  [1]: https://dsp.stackexchange.com/questions/72302/ifft...

  [2]: https://github.com/ARM-software/CMSIS_5/blob/devel...

dear dszabo,

when you perform fast convolution by two forward transforms and one inverse transform, you can save the address reversal process in the three transforms by using the rearrangement in frequency form for the forward transform and the rearrangement in time form for the forward transform. Since the two rearrangements, as the final operation at the input to the frequency domain and as the first operation at the output from the frequency domain cancel each other, we can leave them out and perform the spectral product in the non corrected addressing form with out penalty. A simple way to speed up fast convolution

fred h    

Howdy Fred, great to hear from you!  You are indeed correct.  However, with the CMSIS implementation, both the forward and inverse transforms are rearranged on the same (output) side.  The result is that performing a forward followed by an inverse transform would not give you the input, which I verified experimentally.  Maybe it's just an error in their implementation, which would seem pretty glaring to me given that the library has been around quite some time.

Did you do the single sinewave test on the cascade forward and inverse fft?

use a single complex sinewave with one cycle per interval 

exp(j*2*pi*(0:N-1)/N) as the the input. The spectral response should be a single sample at address +1 (starting at index 0) and the output of the cascade inverse transform should be the single complex sinusoid with same  amplitude and same signs (real and imaginary)... This is a great test of the transform pair... you get to see obvious errors as well as scaling errors and arithmetic noise in first fft.

fred  

Can confirm.  I fed in a 32 point single cycle complex sinusoid.  With bit reversal enabled, there's a single peak in frequency bin 1, and the output matches the input.  With bit reversal turned off, the peak is in bin 16 (which is what I would expect because bit reversal), and the output doesn't match the input.  The output of the cascaded transform pair is as follows:

I'd guess this is a complex sinusoid at the Nyquist frequency that is bit reversed based on intuition, but I don't have the patience to check right now.

Edit:  The peak in the non bit-reversed case was actually in bin 8, not 16.  Can't say why that would be, maybe some mixed radix thing...

OOPs, 

is your transform being implemented in fixed point or in floating point? If fixed point the amplitude should be 1/2 the largest allowable amplitude, such as 2^14 for a 16 bit processor. try it again with the larger amplitude. Does the algorithm have a pre-computed trig table? How big is the table? Have you plotted the entries in the table?

fred

I was using single precision floating point, so it's unlikely that the input amplitude was the issue.  The twiddle factors are pre-computed.  In terms of generating the input signal, I'm using arm's CMSIS trig functions, and I'm unsure of their implementation details, but at a glance in the debugger, everything seemed legit.  The twiddle factor LUT for the 32 point transform is 64 entries, containing the 32 real and imaginary point encompassing a full sinusoidal cycle.  I haven't plotted them, but at a glance of the values, they look close enough.  Given that the function works with bit reversal enabled, I'm doubtful that would be an issue.

I did not go through the code and I do not understand it fully.But see whether my suggestion will be useful.

If the FFT or IFFT is decimation in time input must be provided in bit reversal order.Output will be normal order.If the algorithm is decimation in frequency input is in normal order and output will be in bit reversed order.

So if you use decimation infrequency input you may give normal(with out bit reversal) order.But output will be in bit reversed order.If you want to take IFFT you must bit reverse it since IFFT takes input in normal order.Otherwise you will not get original input.

If you want to avoid bit reversal totally give input in normal order to decimation in frequency.To take IFFT use decimation in time which needs input in bit reversed order.

You are correct, there’s a pretty detailed explanation in that stackexchange link as well.  Basically, the CMSIS library uses natural input/reversed output for both forward and inverse transforms, which seems to require bit reversal to do anything useful.  So I’m not sure why they bothered to include it as an option