7.2. The Inverse DFT#

Generalizing the strategy used in the previous section’s example, we get the following definition for an inverse Discrete Fourier Transform (IDFT).

Definition 7.1 (The Inverse DFT)

Let \(\blue{x[n]}\) be an arbitrary signal of \(N\) samples, and let \(\darkblue{X[m]}\) be its DFT. The inverse DFT (IDFT) is defined as

(7.1)#\[\blue{x[n]} = \frac{1}{N} \sum_{m=0}^{N-1} \darkblue{X[m]} \cdot \green{e^{+2\pi\cdot\mathrm{j} \cdot \frac{m}{N}\cdot n}}\]

Intuitively, this says that the \(n\)th sample of the signal \(\blue{x[n]}\) can be recovered by averaging the \(n\)th samples of all DFT sinusoids.

Before proving the correctness of this definition, we should highlight the three key ways that it differs from the forward DFT defined by equation (5.12):

  1. There is a global scaling of \(1/N\);

  2. The sign of the complex exponent is flipped: positive for inverse transform, negative for the forward transform;

  3. The summation ranges over \(m\) (frequencies), rather than \(n\) (samples). Note that the number of frequencies (and samples) is still \(N\), so the summation still ranges from \(m=0\) to \(m=N-1\).

The proof of DFT invertibility makes no assumptions about \(\blue{x[n]}\), apart from its duration (\(N\)).

Proof. Plugging in the definition of the DFT \(\darkblue{X[m]}\) (but using sample index \(n'\) to avoid confusion with \(n\)), we get the following:

\[\begin{align*} \frac{1}{N} \sum_{m=0}^{N-1} \darkblue{X[m]} \cdot \green{e^{+2\pi\cdot\mathrm{j} \cdot \frac{m}{N}\cdot n}} &= \frac{1}{N} \sum_{m=0}^{N-1} \left( \sum_{n'=0}^{N-1} \blue{x[n']} \cdot \purple{e^{-2\pi\cdot\mathrm{j}\cdot \frac{m}{N} \cdot n'}} \right) \cdot \green{e^{+2\pi\cdot\mathrm{j} \cdot \frac{m}{N}\cdot n}} & \text{DFT definition for } \darkblue{X[m]}\\ &= \frac{1}{N} \sum_{n'=0}^{N-1} \blue{x[n']} \cdot \sum_{m=0}^{N-1} \purple{e^{-2\pi\cdot\mathrm{j}\cdot \frac{m}{N} \cdot n'}} \cdot \green{e^{+2\pi\cdot\mathrm{j} \cdot \frac{m}{N}\cdot n}} & \text{Rearranging summation}\\ &= \frac{1}{N} \sum_{n'=0}^{N-1} \blue{x[n']} \cdot \sum_{m=0}^{N-1} e^{\purple{-2\pi\cdot\mathrm{j}\cdot \frac{m}{N} \cdot n'}+\green{2\pi\cdot\mathrm{j} \cdot \frac{m}{N}\cdot n}}& e^a\cdot e^b = e^{a + b}\\ &= \frac{1}{N} \sum_{n'=0}^{N-1} \blue{x[n']} \cdot \sum_{m=0}^{N-1} e^{2\pi\cdot\mathrm{j}\cdot \frac{\green{n}-\purple{n'}}{N} \cdot m} \end{align*}\]

Now, there are two cases to consider. If \(\purple{n'} = \green{n}\), then the inner summation simplifies:

\[\begin{align*} \sum_{m=0}^{N-1} e^{2\pi\cdot\mathrm{j}\cdot \frac{\green{n}-\purple{n'}}{N} \cdot m} &= \sum_{m=0}^{N-1} e^{2\pi\cdot\mathrm{j}\cdot \frac{0}{N} \cdot m} = \sum_{m=0}^{N-1} 1 = N & \text{if } n' = n. \end{align*}\]

If \(\purple{n'} \neq \green{n}\), then the inner summation cancels totals to zero. This is because \(\purple{n'}\) and \(\green{n}\) are both integers, and we can use the result of Section 5.7, except now with \(n-n'\) taking the place of the frequency index, and \(m\) taking the place of the sample position:

\[\begin{align*} \sum_{m=0}^{N-1} e^{2\pi\cdot\mathrm{j}\cdot \frac{\green{n}-\purple{n'}}{N} \cdot m} &= 0 & \text{ if } n-n' \neq 0. \end{align*}\]

The entire summation, therefore, has \(N-1\) terms contributing 0 and one term contributing \(\blue{x[n]} \cdot N\). Combining these cases, we can finish the derivation above:

\[\frac{1}{N} \sum_{n'=0}^{N-1} \blue{x[n']} \cdot \sum_{m=0}^{N-1} e^{2\pi\cdot\mathrm{j}\cdot \frac{\green{n}-\purple{n'}}{N} \cdot m} = \frac{1}{N} \cdot \blue{x[n]} \cdot N = \blue{x[n]}.\]

This is exactly what we needed to show: the \(n\)th sample is recovered exactly.

7.2.1. The IDFT in practice#

Like the forward DFT, the inverse DFT (IDFT) is implemented by most signal processing packages.

In Python, we have two ways to invert a DFT, depending on whether we have the full spectrum or only the real part:

# Full spectrum, all N analysis frequencies
X = np.fft.fft(x)

# Full inverse, should produce x_inv == x
x_inv = np.fft.ifft(X)

# Real-part only, 1 + N//2 analysis frequencies
Xr = np.fft.rfft(x)

# Real-part inverse, again produces x_inv == x
x_inv = np.fft.irfft(Xr)

7.2.2. Discussion#

Nowhere in the proof of the inverse DFT did we assume anything about the signal contents \(\blue{x[n]}\): it works for any signal \(\blue{x}\). The entire derivation relies on the definition of the forward transform coefficients \(X[m]\), and a couple of observations about summing complex sinusoids. So what does this actually tell us about the DFT?

The inverse DFT gives us an alternative representation of signals: every signal \(x[n]\) can be uniquely represented as a combination of sinusoids:

  • The summation in the inverse DFT \(\sum_{m=0}^{N-1}\) represents the “combination”;

  • The coefficient \(\darkblue{X[m]}\) encodes the amplitude and phase of the \(m\)th sinusoid;

  • The complex exponential \(\green{e^{2\pi\cdot\mathrm{j} \cdot m \cdot n / N}}\) represents the \(m\)th sinusoid itself.

Up until this point, we’ve occasionally had to assume that such a representation exists. But now we’ve proven that it exists.

Aside from analysis and theoretical properties, the inverse DFT gives us tools to modify signals. Rather than operating on individual samples, we can alter the DFT coefficients to produce desired effects, and then take the inverse DFT to recover the time-domain signal. We’ll have more to say about the frequency domain view of filtering in later chapters, but in the next section, we’ll see how to use this insight for synthesizing signals directly.