It's been a long time since I scratch built an FFT algorithm, and I feel like I should already know this, but I just can't recall and figured I might get a quick answer on here that may be useful to others. FWIW, I did see one question that was already answered that was very related, but I am hoping for clarification.
Looking at Decimation in Time algorithms, bit reversal is typically shown applied to the input. For Decimation in Frequency, it is typically shown applied to the output. My questions are:
- What happens if no bit reversal is performed?
- If the natural order is important, does it matter if the bit reversal is performed at the beginning or the end?
- Are the DIT and DIF algorithms mathematically equivalent?
I am implementing a FFT based convolution. It would seem that the bit reversal is not needed and I was hoping to figure out why. I found the figures/analysis here helpful for reference.