JoshJers' Ramblings

Infrequently-updated blog about software development, game development, and music

FFTs Part 4: The Inverse FFT

This is part 4 of a series of posts about FFTs and the specific algorithms that FFT-20XX uses.

  1. The Discrete Fourier Transform
  2. The Basics of the FFT
  3. Some Optimizations to the FFT
  4. The Inverse FFT (← you are here)
  5. The FFT-20XX Complex-Input Algorithm
  6. The FFT-20XX Real-Input Algorithm(s)

In the last post we looked at ways to make the core FFT algorithm more efficient. Before we (finally!) get to the actual FFT-20XX algorithm, it’s worth going over how the inverse FFT works. But to do that, we need to first take a detour into the decimation-in-frequency (DIF) FFT.

I hope you’re ready for some more diagrams because we’re about to dive in.

Note

In this post we’ll be focusing on radix-2 because it’s the simplest form to reason about, but all of this applies to other radixes as well.

Flipping Our Focus

Last time we started graphing the data flow of the FFT algorithm (using semi-standard butterfly diagrams). The radix-2 decimation-in-time algorithm ultimately ends up looking like this:

The diagram of a radix-2 FFT from the previous part, showing the four stages of the algorithm and how they interleave, with the input indices in bit-reversed order and the output indices in sorted order. " 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 0 0 0 0 0 0 0 4 0 4 0 4 0 4 0 2 4 6 0 2 4 6 0 1 2 3 4 5 6 7

If you remember back in part 2, we visualized the rotations for a length-8 FFT, and split things into even/odd inputs and first/last halves of the output.

We can, instead, visualize the same rotations, but switch to looking at even/odd outputs and first/last havles of the inputs (effectively transposing the breakdown we did before):

Note

I’m going to go through this faster than I did the first time, in the hopes that having already done a similar set of steps once, it’s clearer what’s going on this time.

Similar to part 2, we’ll group the evens and odds (this time, outputs instead of inputs), and make the rotations in the second half of the odd outputs be a negation of the first half’s rotations:

Now, we can note that for a given output, the first and last half inputs have the same rotations (i.e. inputs 0 and 4 have matching rotations, 1 and 5, etc), with the evens being summed and the odds being subtracted. We can pre-add (for the evens) and pre-subtract (for the odds) these to get two 4x4 blocks, first the evens, which is just a standard 4-element FFT:

Then the odds which, like in part 2, are a little bit different:

In this case, before doing the sub-FFT, we can rotate the inputs to the sub-FFT to get it in standard N2\frac{N}{2}-length FFT form:

This effectively puts the add/sub step first at each “level”, then the rotation afterwards (to feed into the next sub-FFT).

Because of the way that the divisions into sub-FFTs happen based on outputs rather than inputs, this results in a graph that looks like the DIT diagram, but flipped horizontally:

A diagram of a 16-element decimation-in-frequency FFT, showing the four "stages" of processing and how they interleave. The flow of the diagram and the angles are the same as the decimation-in-time version, but in reverse. 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 0 0 0 0 0 0 0 4 0 4 0 4 0 4 0 2 4 6 0 2 4 6 0 1 2 3 4 5 6 7

Where decimation-in-time started with smaller sub-FFTs and then built up to the full one, each step of decimation-in-frequency instead does a computation pass on its inputs and then splits them up into sub-FFTs after, such that the last step of the radix-2 DIF is just a set of standard length-2 FFTs.

The computation pass is also different: rather than rotate the odd input before the addition and subtraction, DIF instead does the add/sub first then rotates odd output. This is why the rotation (twiddle) factors in the above diagram are on the right-hand side of the butterflies instead of the left.

Despite looking almost like its reversal, this actually computes the exact same outputs as the DIT FFT given the same inputs (ignoring floating-point error, for the pendantic. Yeah, I see you).

Note that, as formulated here, the diagram starts with the inputs in-order and ends with the outputs bit-reversed; this is a consequence of the alternate way we broke down the algorithm. It’s still possible to do the bit-reverse on the inputs so the outputs come out in-order, however. If we rearrange the inputs and outputs in the diagram accordingly, we get the folowing:

Diagram of a radix-2 decimation-in-frequency FFT, with the inputs in bit-reversed order and the outputs in natural (sorted) order, just like the original decimation-in-time diagrams. The angle indices in each stage are in bit-reversed order as a consequence of this reordering. 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 4 2 6 1 5 3 7 0 0 4 4 2 2 6 6 0 0 0 0 4 4 4 4 0 0 0 0 0 0 0 0

Just to reiterate: the above two diagrams are functionally identical, it is simply a matter of visualizing them with different input/output orderings.

We now have enough information to turn this into a routine that — like the DIT version — does the bit reversal on the inputs before computing the result in-place. Here is some pseudocode:

void CalculateDFT(
  complex[] inputs,
  complex[] outputs,
  int len)
{
  if (len == 1)
  {
    outputs[0] = inputs[0]
    return
  }

  BitReverseCopy(inputs, outputs, len)

  for (int span = 2; span <= len; span *= 2)
  {
    for (int groupI = 0; groupI < len / span; groupI++)
    {
      var *data = &outputs[groupI * span]

      // We can pull the twiddle lookup/calculation
      // out of the innermost loop. Note the bit
      // reversal in the index lookup.
      var twiddle = Twiddle(BitRev(groupI, len), len)

      for (int k = 0; k < span / 2; k++)
      {
        int kOdd = k + span / 2

        complex even = data[k]
        complex odd  = data[kOdd]

        // Note the post-rotation here vs. the pre-
        // rotation that DIT does.
        data[k]    = even + odd
        data[kOdd] = (even - odd) * twiddle;
      }
    }
  }
}

This code is very similar to the DIT version; the main differences are the bit-reversed angle lookup and the rotation of the output of the computation pass instead of rotating the inputs (again, a consequence of doing the even/odd split on the outputs instead of the inputs).

Note

On systems without a fast fused multiply-add (FMA) instruction, this DIF formulation ends up being a really nice choice! However, there’s a trick using FMA mentioned in a note in part 3 (which is broken down nicely on The ryg blog) which, sadly, does not work with the DIF’s post-rotation.

A nice thing about the DIF formulated this way (with the bit reverse first) is that it lets the angle lookup move outside of the innermost loop (as you can see above). This is especially nice for radix-4 implementations where the table doesn’t store the 3k3k angles and they’re built via a multiplication, as the multiplication itself can move out of the inner loop.

The other interesting thing is that, with the angle lookups in bit-reversed order, you can store your table of rotations in bit-reversed order as well and, when stored this way, you automatically get nice cache-coherence for the smaller FFT types. If you look at the above butterfly diagram, the first angle is always 0, the second is always a quarter turn (it’s 416\frac{4}{16} in the above diagram, and for a length-8 FFT it would be 28\frac{2}{8}, which is equivalent), and so on. So with an arbitrarily-large FFT table, any given (power-of-2) sized FFT of length NN would just use the first N2\frac{N}{2} elements of the table.

Note

These properties are also true for DIT implementations where the bit reverse is done at the end instead of on the input.

That’s decimation-in-frequency! It ends up being a near-reversal of the way that decimation-in-time works, yet still computes the same result. Now that we’re through that, we can finally get to:

The Inverse FFT

Breaking a (time domain) signal down into its frequency components is pretty handy (you can use it to write cool visualizers, for instance!), but it’s even more useful if you can go from frequencies back into time-domain samples, letting you convert your audio into frequencies, manipulate them in some way (like an EQ) and then turn it back into samples that can be played back or encoded as normal.

The FFT (and the DFT in general) is really a linear system, which means it can be inverted, so we can make a transform that takes the output of an FFT and gives us the original inputs. This is the inverse FFT (IFFT).

To figure out how to do this, let’s start with the simplest useful case: a single DIT radix-2 pass (with an arbitrary angle kk):

Diagram of a 2-length FFT, showing the two inputs going into a single processing node, then back out to the two outputs. The second input node has a "k" representing the fact that it is rotated by an unspecified angle. 0 1 0 1 k

There are effectively two steps here:

  1. Rotate input 1 by kk.
  2. Add/subtract input 0 with the rotated input 1 to get the two outputs.

To invert this, we need to undo these two steps (in the opposite order as we did them).

Undoing the addition/subtraction is first, and this one is easiest to do algebraically. If we have these two equations:
 y0=x0+x1y_0 = x_0 + x_1
 y1=x0−x1y_1 = x_0 - x_1

We can solve them for x0x_0 and x1x_1 to get:
 x0=(y0+y1)/2x_0=(y_0 + y_1)/2
 x1=(y0−y1)/2x_1=(y_0 - y_1)/2

After that, we need to undo our initial step 1, which is the rotation by kk. Undoing a rotation is just rotating the same amount the other way, so that becomes a rotation by −k{-}k.

Note

Because a complex rotation value for a given angle looks like cos⁡ θ+i sin⁡ θ\cos\,\theta + i\,\sin\,\theta, the opposite rotation would be:
 cos⁡(−θ)+i sin⁡(−θ)\cos({-}\theta) + i\,\sin({-}\theta)

By the negative angle trig identites, this becomes:
 cos⁡ θ−i sin⁡ θ\cos\,\theta - i\,\sin\,\theta

So reversing the angle just means negating the imaginary component of the twiddle factor.

For a moment, we’re actually going to ignore that 12\frac{1}{2} scale on our result (just for now — we’ll get back to it), which ends up making the resulting 2-element inverse FFT steps look like:

  1. Add/subtract inputs 0 and 1 (the outputs from our forward FFT) to get two output values.
  2. Rotate the second output of the first step by −k{-}k.

This ends up looking like:

Diagram of a 2-length inverse FFT, showing the two inputs going into a single processing node, then back out to the two outputs. The second output node has a "-k" representing the fact that it is rotated by the opposite of the angle from the forward FFT. 0 1 0 1 -k

Which looks just like the DIF from earlier, except with the angle negated!

This continues to work as we scale the FFT up to larger sizes. Here it is as a 16-element inverse FFT:

A diagram of a 16-element inverted decimation-in-time FFT, which looks exactly like the earlier decimation-in-frequency diagram (with bit-reversed outputs), except all of the rotations are negated. 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 -0 -0 -0 -0 -0 -0 -0 -0 -0 -4 -0 -4 -0 -4 -0 -4 -0 -2 -4 -6 -0 -2 -4 -6 -0 -1 -2 -3 -4 -5 -6 -7

That’s right, by inverting the decimation in time FFT we end up with what looks like a decimation in frequency FFT with negated angles!

A Grumpy Aside

Honestly, I don’t actually like the “decimation-in-time/frequency” terminology, specifically because when using the same code for the inverse, it ends up being wrong: the DIT algorithm is decimating the inputs which are in time domain for a forward FFT, but they’re actually in frequency domain for an inverse FFT (since we’re going from frequency space back to time).

I would have preferred “decimation-in-input” and “decimation-in-output” but I don’t think I’m going to win a fight that I’m 60 years late to.

This relationship plays out the other way, as well: inverting the DIF gets a DIT-like FFT with negated angles:

A diagram of a 16-element inverted decimation-in-frequency FFT, which looks exactly like the earlier decimation-in-time diagram (with bit-reversed inputs), except all of the rotations are negated. 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 -0 -0 -0 -0 -0 -0 -0 -0 -0 -4 -0 -4 -0 -4 -0 -4 -0 -2 -4 -6 -0 -2 -4 -6 -0 -1 -2 -3 -4 -5 -6 -7

This is great, because it means the same routine (whether DIT or DIF) can be used for forward and inverse complex FFTs!

But, what about that 12\frac{1}{2} scale that we ignored earlier? Every (radix-2) step in the IFFT has that 12\frac{1}{2} scale on all of its outputs, so we can factor them all out of the inner steps and combine them into a single 1N\frac{1}{N} scale per output for the whole process!

Tiny Math!

The scale becomes 1N\frac{1}{N} because there are log⁡ N\log\,N passes, each with a 12\frac{1}{2} scale, and (12)log⁡ N=1N(\frac{1}{2})^{\log\,N} = \frac{1}{N}.

Thus, to use our (forward) FFT routine as an inverse FFT, there only need to be two changes:

  1. The twiddles need to have their sin⁡\sin components negated (to rotate by the opposite angle).
  2. Scale each resulting value by 1N\frac{1}{N} (where N is the FFT length).
    • This scale can be applied at the start or at the end, it doesn’t matter; it’s a constant scale to the whole result. You could even do it in the middle somewhere if you’re an absolute monster.

Here’s some pseudocode for this, which uses the same overall algorithm to compute either the forward or inverse FFT:

void CalculateFFT(
  complex[] inputs,
  complex[] outputs,
  int len,
  bool inverse)
{
  if (len == 1)
  {
    outputs[0] = inputs[0]
    return
  }

  BitReverseCopy(inputs, outputs, len)

  for (int subLen = 2; subLen <= len; subLen *= 2)
  {
    for (int subStart = 0; subStart < len; subStart += subLen)
    {
      var *data = &outputs[subStart]

      for (int k = 0; k < subLen / 2; k++)
      {
        int kOdd = k + subLen / 2
        complex evenSum = data[k]
        complex oddSum  = data[kOdd]

        // Get the twiddle factor and invert the imaginary
        // component for an inverse FFT to negate the rotation.
        var tw = Twiddle(k, subLen);
        if (inverse)
          tw.imag = -tw.imag

        oddSum *= tw
        data[k]    = evenSum + oddSum
        data[kOdd] = evenSum - oddSum
      }
    }
  }

  if (inverse)
  {
    // The inverse FFT needs to scale everything down
    // by the FFT length.
    float scale = 1 / len;
    for (int i = 0; i < len; i++)
    {
      outputs[i] *= scale;
    }
  }
}

We Made It!

This brings us (finally!) to the end of the “standard” breakdown of various FFT techniques. In this post, we looked at:

  • The decimation-in-frequency FFT, which is effectively a reversal of the flow of a decimation-in-time FFT.
  • The inverse FFT, which can be calculated the same as a forward FFT with the angles negated and with a constant scale.

In the next two posts, I’m going to go way off into the weeds and discuss the algorithmic variants that I used in FFT-20XX, starting with the algorithm for complex inputs.