5
$\begingroup$

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:

  1. What happens if no bit reversal is performed?
  2. If the natural order is important, does it matter if the bit reversal is performed at the beginning or the end?
  3. 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.

Improve this question
$\endgroup$
1
  • $\begingroup$ FWIW, this whole thing was spurred looking at the CMSIS DSP library function for FFTs. They provide an input parameter for en/disabling bit reversal. After a quick test, I've pretty much decided that disabling bit reversal is pointless in that particular implementation. $\endgroup$
    – Dan Szabo
    Commented Dec 30, 2020 at 16:07

2 Answers 2

Reset to default
6
$\begingroup$

If you're using the FFT and iFFT to perform fast convolution, yes, you can do it in-place and you can do without bit-reversing in the sample processing, but you will have to bit-reverse the transfer function $H[k]$. You would use the DIF for the forward FFT and the DIT for the inverse FFT.

O&S have the clearest treatment, in my opinion. I am robbing some drawings from O&S.

Note this DIF accepts the data input as normal order in and returns bit-reversed data in the output. Note that the butterfly has the twiddle factor multiplied in the output of the butterfly.

DIF

Here is the DIT. Note that it accepts the data input in bit-reversed order and returns normal order data in the output. Also note that the butterfly exactly undoes the DIF butterfly. It multiplies first at the input to the butterfly.

DIT butterfly DIT

Now if you use the DIT as the iFFT, then you need to make sure you scale the input by $\frac1N$ (that can be done with the transfer function multiplication) and conjugate the twiddle factors $W_N^r$. The multiplication in the frequency domain (between the FFT DIF and the iFFT DIT) must be done with the transfer function $H[k]$ pre-bitreversed.

In the 1980s, I wrote a very simple DIF FFT and DIT iFFT in C code. Do you want it? I might be able to find it. Lemme know.

Actually, I posted the C code here before.

Improve this answer
$\endgroup$
17
  • 1
    $\begingroup$ I forgot the fact that, both DIF and DIT butterfly signal flow graph structures can be adopted to work with normal input vs normal output without index reversal required, but then they lose in-place computation property and require multiple buffers to hold temporary stage calculations... $\endgroup$
    – Fat32
    Commented Dec 30, 2020 at 0:32
  • 1
    $\begingroup$ right. but if you do the DIF in and DIT out thing that i spelled out, you can do it in-place and avoid bit reversing in the sample processing code. you do have to bit-reverse the transfer function, $H[k]$ in advance. $\endgroup$
    – robert bristow-johnson
    Commented Dec 30, 2020 at 0:36
  • 1
    $\begingroup$ Yes, I see that, the comment was about my answer actually :-). And btw, if you use DIF for forward and DIT for inverse FFT, (as I've suggested below) then you won't have to reverse $H[k]$, and then you can fully avoid bit-reversal. $\endgroup$
    – Fat32
    Commented Dec 30, 2020 at 0:43
  • 1
    $\begingroup$ But, right now I'm running the code in matlab? I use DIF-forward-FFT for $x[n]$ and $h[n]$ into $H[k]$ and $X[k]$ (in output reversed untouched form), then multiply them $Y[k]=X[k]H[k]$, then use a DIT-inverse-FFT (without input re-ordering) to get $y[n]$. And it works ok? (as expected in my view)? $\endgroup$
    – Fat32
    Commented Dec 30, 2020 at 0:54
  • 1
    $\begingroup$ ok exactly, the way it's. I'm multiplying bit-reversed $X[k]$ with bit-reversed $H[k]$, they are both bit-reversed; because I use DIF (without output normal order correction) to produce them. So their multiplication $Y[k] = X[k]H[k]$ is also bit reversed, and then I use DIT for IFFT without input reversal, because its input $Y[k]$ is already in reordered form. And all this is in-place computation. (I use one buffer for $H[k]$ and one buffer for $X[k]$, then output $Y[k]$ uses either of the existing buffers.) $\endgroup$
    – Fat32
    Commented Dec 30, 2020 at 1:30
3
$\begingroup$

Yes the basic DIT and DIF FFT butterfly structures (with in-place computation, and buffered input, as shown on RBJ's answer) require an index reversal (via bit reversing for radix-2) at the input for DIT, and at the output for DIF respectively, so that normal order input vs normal order output is maintained.

  1. If bit-reversal is skipped, DIT output will be in error, whereas DIF computation will be correct but the output will be placed at wrong locations.

  2. Yes it matters, as the first line stated, DIT and DIF require bit-reversal at different stages.

  3. Yes they are mathematically equivalent: in the sense that they provide the exact same outputs with infinite precision arithmetic, and they require the same number of complex MACs. However, some (very) slight performance differences can be observed due to different indexing and twiddle manipulations.

To avoid index reordering during an FFT based convolution, you can use forward DIF FFTs, and inverse DIT FFT. This way, your normal inputs are processed into reversed outputs with DIF butterflies, and their multiplication is inverted with DIT without an index reversal, as the output of DIF is already index reversed if not corrected.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ @robertbristow-johnson let $x[n] = [1,2]$ and $h[n] = [1,-3]$, lets use 4-point DFT for simplicity. Then normal-order DFTs are: $X[k] = [3, 1-2i, -1, 1+2i]$ and $H[k] = [-2, 1+3i, 4, 1-3i]$. Now, the DIF final stage produces naturally bit-reversed outputs as: $X_r[k] = [3, -1, 1-2i, 1+2i]$ and $H_r[k] = [-2, 4, 1+3i, 1-3i]$... Now, this $H_r[k]$ is naturally in bit reveresed form. I do not specifically reverse it. It naturally comes reversed by the untouched DIF butterfly final stage output. I don't reverse by myself. That's what I mean. And this saves you from 3 explicit reversals. $\endgroup$
    – Fat32
    Commented Dec 30, 2020 at 14:10
  • $\begingroup$ thanks so much for your answer. To clarify on '1', with the DIT output being in error. Would that give the DFT of the bit-reversed input, which would not simply have the same coefficients in a different order? $\endgroup$
    – Dan Szabo
    Commented Dec 30, 2020 at 14:26
  • 1
    $\begingroup$ @DanSzabo No, if you omit the input reversal in DIT algorithm, then the output samples will be in magnitude error, not just scrambled. I've never used DIT for such purpose. May be (I can't say so) at the inverse DFT stage you can correct the magnitude errors (in addition to position index errors) but that would require extra work, comapred to DIF-DIT combination. $\endgroup$
    – Fat32
    Commented Dec 30, 2020 at 14:45
  • 2
    $\begingroup$ Thank you again for all the info, it was very helpful! $\endgroup$
    – Dan Szabo
    Commented Dec 30, 2020 at 15:44
  • 2
    $\begingroup$ you're right, @Fat32. if $H[k]$ is derived from $h[n]$, which presumably was in normal order, then using the DIF FFT alg, the $H[k]$ comes out in bit-reversed order. and for fast convolution, i think that you have to derive the $H[k]$ from $h[n]$ in order to insure the length of $h[n]$ so that the overlap-add or overlap-save is done correctly. $\endgroup$
    – robert bristow-johnson
    Commented Dec 30, 2020 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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