The Discrete Fourier Transform: Structure for even- vs. odd-length transforms

Background
DFT structure: Even-length N
DFT structure: Odd-length N
Coding examples

1 Background

Introduction

The DFT defined earlier is valid for integer valued $N$ . This allows $N$ to be either even or odd. For a real valued discrete time signal, $x[n]$ , this gives rise to subtle differences in the structure of its DFT, $X[k]$ , depending on whether $N$ is even or odd.

As a side point, it’s worth noting that in many real world applications, the DFT is evaluated using the FFT algorithm, which originally required signals where the number of samples was a power of 2, i.e., even $N$ . However, there are now a host of more modern implementations of the DFT, where this requirement is relaxed.

In any case, and whichever algorithm is used to compute the DFT, it is useful to understand how the structure of the resulting spectrum, $X[k]$ , depends on the choice of $N$ . This page summarises some useful things to remember, particularly when doing frequency domain signal processing that will be returned to the time domain via the inverse DFT.

DFT structure for real valued discrete time signals

Consider a real valued discrete time signal $x[n]$ . The DFT of this signal can be calculated via

(1) $\begin{align*} X[k] = \sum_{n=0}^{N-1} x[n] e^{-2\pi i k n/N}, \hspace{0.5cm} k = 0, 1, 2, ... , N-1 \end{align*}$

for sample time index $n$ , frequency bin index $k$ , and number of time samples included in the transformation $N$ (which is also equal to the number of frequency bins).

For a real signal $x[n]$ the spectrum, $X[k]$ , is conjugate symmetric about the Nyquist limit. The Nyquist limit is usually defined, in terms of $k = 1, 2, 3, ... N-1$ , as corresponding to $\frac{N}{2}$ .

The conjugate symmetry property means that the `upper half’ of the spectrum, i.e., from $\frac{N}{2} + 1$ up to $N-1$ (for even-length $N$ ), can be perfectly derived from the `lower half’. In other words, the `upper half’ is redudent information. In practical frequency domain analysis and processing it often makes sense to discard it and work with a single-sided spectrum representation.

The structure of $X[k]$ will be slightly different, depending on whether $N$ is even or odd. This page provides a brief graphical summary of these structural distinctions.

2 DFT structure: Even-length N

For real discrete time signals of length $N$ (even-length), the DFT structure contains $\frac{N}{2} + 1$ unique spectral amplitudes. By `unique’ we mean that we can use these amplitudes to form a single-sided spectrum representation where we discard the `upper half’ of the spectrum. As long as this single-sided spectral representation includes all of these unique entries, we can fully recover the whole spectrum (i.e., obtain the double-sided DFT), and/or perform a valid inverse DFT to obtain a discrete time signal representation.

Even-length DFT transforms are used more often than odd-length transforms, due to use of FFT algorithms where signal blocks of length $2^N$ enable the greatest computational efficiency..

The DFT structure of an even-length $N$ transform is illustrated in Figure 1.

**Figure 2:** The structure of the DFT, $X[k]$ , when $N$ is **even**. Note that $*$ indicates taking the complex conjugate.

3 DFT structure: Odd-length N

For real discrete time signals of length $N$ (odd-length), the DFT structure contains $\frac{N+1}{2}$ unique spectral amplitudes.

The DFT structure of an odd-length $N$ transform is illustrated in Figure 2.

**Figure 2:** The structure of the DFT, $X[k]$ , when $N$ is **odd**. Note that $*$ indicates taking the complex conjugate.

4 Coding examples