1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ does the same happen on the forward FFT as well, or only on the inverse FFT? $\endgroup$ – Fat32 Oct 17 '17 at 9:20
  • $\begingroup$ Hi Fat32, yes, the same happens. $\endgroup$ – Fabien Dupont Oct 17 '17 at 10:18
  • $\begingroup$ you need to take a close look at the documentation of both FFT and iFFT function calls. they could both be the same algorithm. and it might have the bit reversing built in. look for terms like "Decimation-in-Time" and "Decimation-in-Frequency". $\endgroup$ – robert bristow-johnson Oct 17 '17 at 10:57
  • $\begingroup$ Hi Robert and all, Thank you for your answers. I have direct access to the code (but am not allowed to share it for confidientiality issues). We have investigated a bit further and found the probable root cause. I will post an ansser to my own question to share the findings with the community. In short : it was indeed a misunderstanding of the basics on my side. $\endgroup$ – Fabien Dupont Oct 17 '17 at 11:26
  • $\begingroup$ Fabien, now you have written your own answer and indeed I made a test with my own FFT code, so it made clear and I remembered that changing the place of bit-reveresal stage has an effect on the result. So we can say that the re-ordering algorithm depends on the place where it would take place. Which is also evindent from the butterfly nets you have provided. $\endgroup$ – Fat32 Oct 17 '17 at 12:50
1
$\begingroup$

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 :

bit reversed input

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

natural order input

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=&arnumber=6323745)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.