Discrete Fourier Transform (DFT) Discrete Fourier Transform (DFT)
What is the Discrete Fourier Transform?
The DTFT represents an aperiodic discrete-time signal in the frequency domain. However, its spectrum $X(e^{j\omega})$ is a function of continuous variable $\omega$, so a computer can neither store it nor evaluate it at every frequency. To work with a spectrum numerically, we need a representation that consists of finitely many values.
The Discrete Fourier Transform (DFT) provides exactly this. It represents a finite-length signal of length $N$ by $N$ frequency-domain values $X[k]$. These values are obtained by sampling the DTFT at $N$ equally spaced frequencies.
From DTFT to DFT
Consider a finite-length signal $x[n]$ that is zero outside $0\leq n \leq N-1$. Its DTFT is given by the DTFT analysis equation. Since $x[n]$ is zero outside this range, only $N$ terms of the sum remain:
\[X(e^{j\omega}) = \sum_{n=-\infty}^\infty x[n] e^{-j\omega n} = \sum_{n=0}^{N-1} x[n] e^{-j\omega n}\]So far nothing is new: both the signal and the equation are those of the DTFT.
The problem is that $\omega$ is still continuous. The DFT therefore evaluates $X(e^{j\omega})$ only at the frequency $\omega_k=2\pi k/N$, rather than at every $\omega$. Since $X(e^{j\omega})$ is $2\pi$-periodic, the $N$ values $k=0,1,\dots,N-1$ cover one full period.
\[X[k] = X(e^{j\omega}) \Big|_{\omega=\frac{2\pi k}{N}} = \sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi k}{N}n}\]In other words, the DFT and the DTFT represent the same signal; the DFT simply keeps only $N$ frequencies.
However, sampling in frequency makes the signal periodic in time. If we return to the time domain using only $N$ values $X[k]$, we obtain $x[n]$ repeated every $N$ samples:
\[\tilde{x}[n] = \sum_{r=-\infty}^\infty x[n-rN]\]The period $N$, which vanished in the limit $N\to\infty$ when we derive the DTFT, reappears once the frequency is sampled.
Sampling the DTFT at $N$ frequencies gives the DFT. Going back from those $N$ samples gives $x[n]$ repeated every $N$ samples.
Nevertheless, no information is lost. Since $x[n]$ has length $N$, the copies do not overlap, so one period of $\tilde{x}[n]$ is exactly $x[n]$. A signal of length $N$ is completely determined by $N$ samples of its DTFT.
Outside $0\le n\le N-1$, however, the two transforms see different signals. In the DTFT the signal is zero there, whereas in the DFT it implicitly repeats. This difference becomes visible later, when we shift or convolve signals.
DFT Representation
The DTFT provides a pair of equations that convert between the time-domain representation $x[n]$ and the frequency-domain representation $X[k]$.
\[x[n] \quad\longleftrightarrow\quad X[k]\]Both sides consist of exactly $N$ values: $x[n]$ for $0\le n\le N-1$ and $X[k]$ for $0\le k\le N-1$.
Synthesis Equation: Frequency → Time
Suppose we know frequency-domain representation $X[k]$. We can construct the original signal $x[n]$ by combining $N$ complex exponentials with appropriate weight. This is described by the DFT synthesis equation:
\[x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2\pi k}{N}n} \tag{1}\]where $X[k]$ is the DFT coefficient associated with the frequency $\omega_k=2\pi k/N$.
Unlike in the DTFT, the frequencies are discrete, so the integral over frequency becomes a finite sum again. As a result, $X[k]$ is once more the weight of a single frequency, as $\tilde{X}[k]$ was in the DFS.
The equation has the same form as the DFS synthesis equation. What differs is not the equation but how it is used: the DFS applies it to every $n$ and obtains a periodic signal, whereas the DFT applies it only to $0\le n\le N-1$ and keeps a finite-length signal.
Analysis Equation: Time → Frequency
Conversely, suppose we know the original periodic signal $x[n]$. Now we want to determine the contribution of the frequency $\omega_k$ to the signal. This is described by the DFT analysis equation:
\[X[k] = \sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi k}{N}n}\]This is the equation we obtained above by sampling the DTFT at $\omega_k=2\pi k/N$.
Unlike in the DTFT, the sum has only $N$ terms, so it always converges. No condition on $x[n]$ is needed.
Both equations are finite sums over finitely many values, so a computer can evaluate them exactly. This is what makes the DFT, among the three transforms, the one used in practice.
DFS vs. DTFT vs. DFT
The DFT is not an independent third transform. It shares its equations with the DFS and its values with the DTFT, as the table below shows.
| DFS | DTFT | DFT | |
|---|---|---|---|
| Time-domain | $\tilde{x}[n]$: discrete, periodic | $x[n]$: discrete, aperiodic | $x[n]$: discrete, $N$ samples |
| Frequency-domain (Spectrum) | $\tilde{X}[k]$: discrete, periodic | $X(e^{j\omega})$: continuous, periodic | $X[k]$: discrete, $N$ values |
| Frequencies used | $N$ harmonics $\omega_k=2\pi k/N$ | Every $\omega$ in an interval of length $2\pi$ | $N$ harmonics $\omega_k=2\pi k/N$ |
| Synthesis | Sum over $N$ harmonics | Integral over $2\pi$ | Sum over $N$ harmonics |
| Analysis | Sum over one period ($N$ samples) | Sum over all $n$ | Sum over $N$ samples |
For a finite-length signal $x[n]$ with periodic extension $\tilde{x}[n]$, the three spectra agree at the harmonic frequencies:
\[X[k] = \tilde{X}[k] = X(e^{j\omega})\Big|_{\omega=\frac{2\pi k}{N}}, \qquad 0\le k\le N-1\]Understanding $X[k]$
Periodicity in Time
For an $N$-point DFT, the synthesis equation reconstructs the $N$ samples $x[0],\dots,x[N-1]$. If we extend the same equation to any integer $n$, it generates an $N$-periodic sequence. For example, at $n=N$ every exponential becomes $e^{j2\pi k}=1$, so the equation gives $x[0]$ again:
\[x[N] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j2\pi k} = \frac{1}{N} \sum_{k=0}^{N-1} X[k] = x[0]\]In general, the resulting sequence $\tilde{x}[n]$ repeats every $N$ samples:
\[\tilde{x}[n+N] = \tilde{x}[n]\]The reason is similar to why the DTFT is periodic in frequency. In the DTFT, $X(e^{j\omega})$ is $2\pi$-periodic because $n$ is an integer. Here, each complex exponential in the synthesis equation is $N$-periodic because $k$ is an integer:
\[e^{j\frac{2\pi k}{N}(n+N)} = e^{j\frac{2\pi k}{N}n} \cdot e^{j2\pi k} = e^{j\frac{2\pi k}{N}n}\]In short, sampling in one domain makes the signal periodic in the other. The DFT uses only $N$ values in each domain, but its equations repeat every $N$ in both.
Why do the samples give $x[n]$ repeated every $N$ samples?
Start from the samples of the DTFT:
\(X[k] = \sum_{m=-\infty}^{\infty} x[m] e^{-j\frac{2\pi k}{N}m}\) Substitute the samples $X[k]=\sum_{m} x[m]e^{-j(2\pi k/N)m}$ into the synthesis equation:
\[\begin{aligned} \frac{1}{N}\sum_{k=0}^{N-1} X[k] e^{j\frac{2\pi k}{N}n} &= \sum_{m=-\infty}^{\infty} x[m] \left( \frac{1}{N}\sum_{k=0}^{N-1} e^{j\frac{2\pi k}{N}(n-m)} \right) \end{aligned}\]By the orthogonality of the complex exponentials, the sum in parentheses is $1$ when $n-m$ is a multiple of $N$ and $0$ otherwise. Only the terms with $m=n-rN$ remain:
\[\frac{1}{N}\sum_{k=0}^{N-1} X[k] e^{j\frac{2\pi k}{N}n} = \sum_{r=-\infty}^{\infty} x[n-rN]\]Because of this periodicity, a sample shifted past one end of $0\le n\le N-1$ comes back in at the other end. This is why shifts and convolutions in the DFT are circular, as we will see in the post on circular convolution.
Effect of the DFT Length $N$
Let $L$ be the length of the signal and $N$ the DFT length. There are three cases:
- $N<L\,$: the copies of $x[n]$ overlap, causing time-domain aliasing.
- $N=L\,$: the copies neither overlap nor leave a gap, so one period is exactly the original signal $x[n]$.
- $N\ge L\,$: $N-L$ zeros appear between the copies.
When $N\ge L$, these zeros are the same as zeros added to the end of $x[n]$ before taking the DFT. This is called zero-padding.
Move $N$ to change the $N$-point DFT of a signal of length $L=8$. The sum of the copies, $\tilde{x}[n]$, is what the synthesis equation gives back. When $N<L$, the copies overlap. When $N>L$, zeros appear between them.
Magnitude and Phase
Like $\tilde{X}[k]$ and $X(e^{j\omega})$, $X[k]$ is complex-valued, so it can be written in polar form:
\[X[k] = \lvert X[k] \rvert \, e^{j\angle X[k]}\]The magnitude $\lvert X[k] \rvert$ determines how strongly the frequency $\omega_k$ is present in the signal, and the phase $\angle X[k]$ determines how far that component is shifted.
Since $X[k]$ is a sample of $X(e^{j\omega})$, its magnitude and phase are samples too. The magnitude spectrum and the phase spectrum of the DFT are $N$ points on the curves of the DTFT.
To read these points, we need to know which frequency each index $k$ stands for. The index $k$ corresponds to $\omega_k=2\pi k/N$, so $k$ runs from $\omega=0$ to just below $\omega=2\pi$. Recall from the post on complex exponentials that the frequencies near $0$ and $2\pi$ are low, and that the highest frequency is $\pi$. Therefore:
- $k=0$ is the lowest frequency, $\omega=0$.
- $k=N/2$ is the highest frequency, $\omega=\pi$.
- $k>N/2$ are the negative frequencies, because $\omega_k$ and $\omega_k-2\pi$ are the same frequency.
The highest frequency is in the middle of the DFT, not at the end.
As in the DFS, the magnitude spectrum of a real signal is even and its phase spectrum is odd:
\[\lvert X[N-k] \rvert = \lvert X[k] \rvert \,,\qquad \angle X[N-k] = -\angle X[k]\]The second half of the DFT mirrors the first half. For a real signal, the values for $0\le k\le N/2$ are enough to know all of $X[k]$.
[Example] DFT of a cosine
Consider $x[n]=\cos\big((2\pi\cdot 2/8)\,n\big)$ with $N=8$. From the example in the DFS post with $A=1$, $\phi=0$ and $k_0=2$,
\[X[2] = 4 \,,\qquad X[6] = 4\]and all other values are zero.
The cosine has only one frequency, but two values of the DFT are nonzero. $X[2]$ is the positive frequency $\omega=\pi/2$, and $X[6]$ is the negative frequency $\omega=3\pi/2-2\pi=-\pi/2$. The two have the same magnitude, as the symmetry requires.
DFT Properties
The DFT uses the same equations as the DFS, so it has the same properties. The only thing that changes is how a shift is described, because the signal now has only $N$ samples.
Linearity
The DFT of a sum is the sum of the DFTs:
\[ax_1[n] + bx_2[n] \quad\longleftrightarrow\quad aX_1[k] + bX_2[k]\]Both signals must have the same length $N$. If one is shorter, we add zeros to its end first.
Time Shift
In the DFS, shifting a periodic signal brings samples in from the next period. In the DFT, the signal has only the $N$ samples $x[0],\dots,x[N-1]$, so a sample that is shifted out at one end comes back at the other end. This is called a circular shift, and it is written with the index taken modulo $N$:
\[x[(n-m) \bmod N]\]For example, a circular shift of ${1,2,3,4}$ by one sample gives ${4,1,2,3}$.
An ordinary shift moves the whole signal to the right. In a circular shift with $N=3$, the sample that leaves at the right end comes back in at the left end.
A circular shift changes only the phase of the DFT:
\[x[(n-m) \bmod N] \quad\longleftrightarrow\quad e^{-j\frac{2\pi k}{N}m} X[k]\]This is the time shift property of the DFS, seen within one period.
Frequency Shift
Multiplying a signal by a complex exponential shifts its DFT circularly:
\[e^{j\frac{2\pi k_0}{N}n} x[n] \quad\longleftrightarrow\quad X[(k-k_0) \bmod N]\]Convolution
Multiplying two DFTs gives the circular convolution of the two signals, not their linear convolution. In circular convolution, the shift is circular:
\[\sum_{m=0}^{N-1} x_1[m] \, x_2[(n-m) \bmod N] \quad\longleftrightarrow\quad X_1[k] \, X_2[k]\]This is the periodic convolution of the DFS, seen within one period. We look at it in detail in the post on circular convolution.
Parseval’s Relation
The energy of a signal can be computed in either domain:
\[\sum_{n=0}^{N-1} \lvert x[n]\rvert^2 = \frac{1}{N} \sum_{k=0}^{N-1} \lvert X[k]\rvert^2\]Both sides are finite sums, so the energy can be computed exactly from the $N$ values of the DFT.
Summary
| Property | Time domain | Frequency domain |
|---|---|---|
| Linearity | $ax_1[n]+bx_2[n]$ | $aX_1[k]+bX_2[k]$ |
| Time Shift | $x[(n-m)\bmod N]$ | $e^{-j(2\pi k/N)m}X[k]$ |
| Frequency Shift | $e^{j(2\pi k_0/N)n}x[n]$ | $X[(k-k_0)\bmod N]$ |
| Circular Convolution | $\sum_{m=0}^{N-1}x_1[m]\,x_2[(n-m)\bmod N]$ | $X_1[k]\,X_2[k]$ |
| Parseval’s Relation | $\sum_{n=0}^{N-1}\lvert x[n]\rvert^2$ | $\frac{1}{N}\sum_{k=0}^{N-1}\lvert X[k]\rvert^2$ |