# Conjugate Symmetry

## Contents

# 6.3. Conjugate Symmetry#

(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**:

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:

This follows immediately from Euler’s formula (4.1)

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

so that

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

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

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

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\)

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.

## 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:

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]}\).

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.