6.3. Conjugate Symmetry#

Theorem 6.2 (DFT conjugate symmetry)

Let \(\blue{x[n]}\) be a real-valued signal with \(N\) samples.

Then the DFT series \(\darkblue{X[0], X[1], \dots, X[N-1]}\) has conjugate symmetry:

\[\darkblue{X[m]} = \overline{\darkblue{X[N-m]}}.\]

In words, this says that the DFT component \(\darkblue{X[m]}\) is the complex conjugate of component \(\darkblue{X[N-m]}\) (and vice versa): their real parts are identical, and their imaginary parts are negatives of each-other.

As it turns out, we’ve seen a version of this already when computing the DFT of sinusoids. A careful look at how we approached the problem will reveal that none of the argument depended on the fact that the input signal \(\blue{x[n]}\) was a sinusoid, only that it was real-valued. Here, we can give a slightly more streamlined proof using the complex exponential.

Proof. We’ll start by observing that for any complex exponential \(e^{\mathrm{j} \cdot \theta}\), the following holds:

\[\overline{e^{\mathrm{j}\theta}} = e^{-\mathrm{j}\theta} \]

This follows immediately from Euler’s formula (4.1)

\[e^{\mathrm{j}\theta} = \red{\cos(\theta)} + \mathrm{j} \cdot \purple{\sin\theta}\]

and the symmetry rules for \(\cos\) and \(\sin\):

\[\begin{align*} \cos(-\theta) &= \cos(\theta)\\ \sin(-\theta) &= -\sin(\theta) \end{align*}\]

so that

\[\begin{align*} e^{-\mathrm{j}\cdot\theta} &= \red{\cos(-\theta)} + \mathrm{j}\cdot\purple{\sin(-\theta)}\\ &= \red{\cos(\theta)} - \mathrm{j}\cdot\purple{\sin(\theta)}\\ &= \overline{e^{\mathrm{j}\cdot\theta}}. \end{align*}\]

Taking \(\theta = 2\pi\cdot\frac{N-m}{N}\cdot n\), we get

\[\begin{align*} \exp\left(\red{-}\mathrm{j}\cdot 2\pi \cdot \frac{\red{N-m}}{N} \cdot n \right) &= \exp\left(\cyan{+}\mathrm{j}\cdot 2\pi \cdot \frac{\cyan{m-N}}{N} \cdot n \right) & \text{cancelling negatives}\\ &= \exp\left(\mathrm{j}\cdot 2\pi \cdot \frac{m}{N} \cdot n \right) & \text{add rotations } 2\pi\cdot n \cdot N / N\\ &= \overline{\exp\left(-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N} \cdot n \right)} & \text{conjugation}. \end{align*}\]

This lets us express \(\darkblue{X[N-m]}\) as follows:

\[\begin{align*} \darkblue{X[N-m]} &= \sum_{n=0}^{N-1} \blue{x[n]} \cdot \exp\left(-\mathrm{j}\cdot 2\pi \cdot \frac{N-m}{N} \cdot n \right) \\ &= \sum_{n=0}^{N-1} \blue{x[n]} \cdot \overline{\exp\left(-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N} \cdot n \right)}\\ &= \overline{\sum_{n=0}^{N-1} \blue{x[n]} \cdot \exp\left(-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N} \cdot n \right)}\\ &= \overline{\darkblue{X[m]}}. \end{align*}\]

Warning

The last step hinges upon the fact that \(\blue{x[n]}\) is real-valued, so \(\blue{x[n]}\cdot\overline{z} = \overline{\blue{x[n]} \cdot z}\) for any complex \(z\). If \(\blue{x[n]}\) was complex-valued, this step would not go through, and we would not have conjugate symmetry.

6.3.1. Which frequencies do we need to compute?#

DFT conjugate symmetry says that there is redundancy in the spectral content of a real-valued signal. But what exactly is the minimal set of frequencies that we must compute to fully represent the signal?

We can think of this by working through each \(m=0, 1, 2, \dots N-1\) and seeing which other components can be inferred once we have \(\darkblue{X[m]}\). We can stop when all \(N\) have been covered.

  • \(\purple{m=0} \Leftrightarrow \purple{N-0= N \equiv 0}\) - The DC component pairs with itself.

  • \(\blue{m=1} \Leftrightarrow \red{N-1}\)

  • \(\blue{m=2} \Leftrightarrow \red{N-2}\)

  • \(\dots\)

How far we can go with this depends on whether \(N\) is even or odd. If \(N\) is even, then

\[\purple{m = \frac{N}{2}} \Leftrightarrow \red{N-\frac{N}{2}} = \purple{\frac{N}{2}}\]

give us the Nyquist frequency, which like the \(\purple{m=0}\) case, pairs with itself. In this case, we’ll have a total of \(M = 1 + N/2\) frequencies: \(m=0\) followed by everything up to and including \(m=N/2\).

If \(N\) is odd, then there is no \(m\) such that \(m=N-m\). The largest \(m\) such that \(m < N/2\) (so \(N-m > N/2\)) is \(m = (N-1) / 2\). This gives us a total of \(M = 1 + (N-1)/2\) frequencies.

These two cases can be combined to give a single formula for \(M\)

\[M = 1 + \left\lfloor \frac{N}{2} \right\rfloor\]

where \(\lfloor\cdot\rfloor\) is the “floor” operation: the largest integer no greater than its input. This expression is implemented in Python as:

M = 1 + N // 2  # Integer division

Fig. 6.6 depicts the conjugate symmetry relationships graphically for both the even- and odd-length cases.

graphical depiction of conjugate symmetry pairing for even and odd lengths

Fig. 6.6 The DFT conjugate symmetry property relates \(\blue{X[m]}\) with \(\red{X[N-m]}\) (arrows). Indices \(\purple{m=0}\) and \(\purple{m=N/2}\) (if \(N\) is even) are only related to themselves. If the signal length is even (top, \(N=8\)), then the first \(M=1 + N/2\) components are sufficient to determine all \(N\) components. If the signal length is odd (bottom, \(N=7\)), then \(M=1 + (N-1)/2\) are sufficient.#

6.3.2. Why does this matter?#

Conjugate symmetry can buy us some efficiency in both the time to compute the DFT, and the space it takes to store the results.

Most Fourier transform implementations provide a specialized function rfft (real-valued input FFT) which can efficiently compute just the non-negative frequency values.

# Compute the full spectrum, all N frequencies
X = np.fft.fft(x)

# Compute just the non-negative spectrum: 1 + N//2 frequencies
X = np.fft.rfft(x)

For small values of \(N\) like the examples we’ve been working with, this is not such a big deal. However, it is not uncommon to have signals of thousands of samples: in this case, reducing the amount of data by 50% can substantially cut down on memory consumption and processing time. This is also beneficial in real-time audio applications, where there can be tight constraints on latency and computing a DFT is often the computational bottleneck.

Additionally, conjugate symmetry teaches us two facts about the DFT:

  1. Because the DC component (\(m=0\)) is its own conjugate, \(\darkblue{X[0]} = \overline{\darkblue{X[0]}}\), we know that it must be real-valued. This shouldn’t be surprising, given that it must also equal the sum of the (real-valued) input samples contained in \(\blue{x[n]}\).

  2. If \(N\) is even, then the Nyquist component \(m=N/2\) is also self-conjugate: \(\darkblue{X[N/2]} = \overline{\darkblue{X[N/2]}}\). It must also be real-valued if \(\blue{x[n]}\) is. This is much less obvious from the DFT definition.