Bit-reversal equivalence on IFFT (radix-2 Cooley-Tukey) From everything that I read on the internet, I understood that when performing FFT or IFFT, one should perform bit-reversal to obtain a result in natural order (Assuming input is also in natural order). I also understood that this bit-reversal can be performed before or after the FFT or IFFT processing.

However, when interverting the order of operations, from :

bit_reversal();
IFFT();


to :

IFFT();
bit_reversal();


I don't get the same results. I would expect some difference due to rounding (I am working in fixed-precision here). But I get really completely different results.

Unfortunately, I am not allowed to share the code here, so my question is not about the implementation of the bit-reversal or IFFT, but more about fundamentals that I may have missed : can we operate bit-reversal equivalently before or after the radix-2 IFFT, without changing the radix-2 algorithm ?

Thanks in advance.
To answer my own question : no you can't use the exact same algorithm. 

In the case here of a decimation-in-time, radix-2 Cooley Tuckey, in-place FFT/IFFT algorithm, we have the choice between two implementations which are exactly equivalent :



The above uses bit-reversed inputs and produce natural order results.



The above uses natural order input and produces bit-reversed outputs.

You can see that the operations are the same : for each butterfly operators, same input data, same twiddle factors. It's just the address of that data (here, the number of lines from the top) that changes.

The same applies for IFFT. When applying the bit-reversal after the IFFT, I would have needed to change the IFFT algo so that it changes the addressing scheme to match the second algo.

To go a bit further on the topic : "ALGEBRAIC FORMULATION OF THE
FAST FOURIER TRANSFORM" from Tran-Thong. (http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&amp;arnumber=6323745)