Discrete Time Fourier Transform (DTFT) Discrete-Time Fourier Transform (DTFT)
What is the Discrete-Time Fourier Transform?
The DFS represents a periodic discrete-time signal in terms of frequency components. But how can we represent an aperiodic discrete-time signal in the frequency domain? This leads us to the Discrete-Time Fourier Transform (DTFT).
From DFS to DTFT
In the DFS, the signal repeats every $N$ samples, so the frequency $\omega$ cannot take arbitrary values. Only complex exponentials that also repeat every $N$ samples can be used, and their frequencies lie on a grid with spacing $\Delta\omega = 2\pi/N$.
An aperiodic signal has no period, so its frequencies are not limited to such a grid. To see how this discrete grid turns into a continuous range of frequencies, consider a finite-duration aperiodic signal $x[n]$. We cannot apply the DFS to $x[n]$ directly, because it has no period. So we make it periodic by repeating it every $N$ samples. This is called a periodic extension:
\[x[n] \quad\xrightarrow{\text{Periodic extension}}\quad \tilde{x}_N[n]\]As $N$ increases, the copies of $x[n]$ move farther apart. As $N\to\infty$, they move infinitely far apart, and only $x[n]$ itself is left. In this sense, an aperiodic signal can be viewed as a periodic signal with an infinite period.
At the same time, in the frequency domain, the spacing $\Delta\omega = 2\pi/N$ goes to $0$. The harmonic frequencies $\omega_k = 2\pi k/N$ get closer and closer together, and in the limit they fill the whole frequency range. So instead of the discrete index $k$, we use the continuous variable $\omega$.
Likewise, the DFS coefficients $\tilde{X}[k]$, which exist only at the harmonic frequencies, become a function $X(e^{j\omega})$ defined at every frequency. This function is the DTFT of $x[n]$.
As $N$ grows, the copies of $x[n]$ move apart and the DFS coefficients $\tilde{X}[k]$ get closer together. As $N\to\infty$, they become the continuous function $X(e^{j\omega})$.
The periodic extension was only a step along the way. After the limit, $N$ no longer appears in $X(e^{j\omega})$, so the DTFT can be applied directly to an aperiodic signal $x[n]$, without repeating it first.
DTFT Representation
The DTFT provides a pair of equations that convert between the time-domain representation $x[n]$ and the frequency-domain representation $X(e^{j\omega})$.
\[x[n] \quad\longleftrightarrow\quad X(e^{j\omega})\]The argument is written $e^{j\omega}$ rather than $\omega$ because $X$ depends on $\omega$ only through $e^{j\omega}$.
Synthesis Equation: Frequency → Time
Suppose we know the frequency-domain representation $X(e^{j\omega})$. We can construct the original signal $x[n]$ by combining the complex exponentials of all frequencies with appropriate weights. This is described by the DTFT synthesis equation:
\[x[n] = \frac{1}{2\pi} \int_{-\pi}^{\pi} X(e^{j\omega}) e^{j\omega n} d\omega \tag{1}\]where $X(e^{j\omega})$, the DTFT of $x[n]$, is also called its spectrum. The integrand repeats every $2\pi$ in $\omega$, so the integral can be taken over any interval of length $2\pi$.
Unlike in the DFS, the frequency $\omega$ is continuous, so the sum over harmonics becomes an integral over frequency. As a result, $X(e^{j\omega})$ is not a weight of a single frequency, as $\tilde{X}[k]$ was. Instead, a narrow band of width $d\omega$ around $\omega$ gets the weight $(1/2\pi)\,X(e^{j\omega})\,d\omega$. So $X(e^{j\omega})$ describes how the signal is distributed over a continuous range of frequencies, like a density.
Analysis Equation: Time → Frequency
Conversely, suppose we know the original signal $x[n]$ and want to find how much of each frequency $\omega$ it contains. The DTFT analysis equation gives this:
\[X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n} \tag{2}\]As in the DFS, this sum is the inner product of $x[n]$ with the complex exponential $e^{j\omega n}$, but now it runs over all $n$.
Unlike in the DFS, the sum has infinitely many terms, so it does not always converge. If $x[n]$ is absolutely summable, its DTFT exists:
\[\sum_{n=-\infty}^{\infty} \lvert x[n]\rvert < \infty\]This condition is enough, but it is not required. Signal that never decay, such as a constant or a sinusoid, do not satisfy this condition, so their DTFT does not exist as an ordinary function.
Winding a Signal Around the Origin
The analysis equation $\small(2)$ has a simple picture. Each term $x[n]e^{-j\omega n}$ is an arrow on the complex plane. Its length is $x[n]$, and its direction is $-\omega n$. (If $x[n]$ is negative, the arrow points the opposite way.) Each time $n$ increases by one, the arrow turns by $\omega$ clockwise. So the analysis equation winds the signal around the origin, turning by $\omega$ per sample, and adds up all the arrows.
Here, $\omega$ is not the frequency of the signal. It is a frequency we choose to test. The signal stays the same, and we try every $\omega$ one by one.
Suppose $x[n]$ oscillates at the frequency $\omega_0$.
- If $\omega \neq \omega_0$, the longest arrows point in a different direction each time. The arrows point in all directions and cancel out, so the sum stays small.
- If $\omega = \omega_0$, the arrow makes one full turn for every cycle of the signal, so the longest arrows always point the same way. They pile up on one side, and the sum becomes large.
This is the same cancellation we saw for the orthogonality of the harmonics in the DFS.
The arrow is as long as the signal is high, and turns by $\omega$ per sample. When $\omega$ matches the frequency of the signal, the points it leaves gather on one side.
In the example above, the red arrow means center of mass of the points, which is their average position:
\[\frac{1}{m} \sum_{n=0}^{m-1} x[n] e^{-j\omega n}\]where $m$ is the number of points drawn so far.
The DTFT uses the sum itself, not the average. The sum is just $m$ times the center of mass, so the two point in the same direction and grow together. So the magnitude of $X(e^{j\omega})$ shows how much of the frequency $\omega$ the signal contains, and its angle shows the phase of that component.
DFS vs. DTFT
The DTFT extends the DFS from periodic signals to aperiodic ones. As in the DFS, $x[n]$ and $X(e^{j\omega})$ are two representations of the same signal, but the two domains no longer look alike. In the DFS, both $\tilde{x}[n]$ and $\tilde{X}[k]$ were discrete and periodic. In the DTFT, $x[n]$ is discrete and aperiodic, while $X(e^{j\omega})$ is continuous and periodic.
| DFS | DTFT | |
|---|---|---|
| Time-domain | Periodic $\tilde{x}[n]$ | Aperiodic $x[n]$ |
| Frequency-domain (Spectrum) | $\tilde{X}[k]$ | $X(e^{j\omega})$ |
| Frequencies used | $N$ harmonics $\omega_k=2\pi k/N$ | Every $\omega$ in an interval of length $2\pi$ |
| Synthesis | Sum over $N$ harmonics | Integral over $2\pi$ |
| Analysis | Sum over one period ($N$ samples) | Sum over all $n$ |
Understanding $X(e^{j\omega})$
Periodicity in Frequency
$X(e^{j\omega})$ is always $2\pi$-periodic in $\omega$.
\[X(e^{j(\omega+2\pi)}) = X(e^{j\omega})\]The reason is the same as in the DFS: $n$ is an integer. Since $e^{-j(\omega+2\pi)n}=e^{-j\omega n}$ for every integer $n$, the $\omega$ and $\omega+2\pi$ correspond to the same complex exponential. The spectrum must therefore take the same value at both.
Why is $X(e^{j\omega})$ $2\pi$-periodic?
Starting from the analysis equation,
\[X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n}\]replace $\omega$ with $\omega+2\pi$:
\[X(e^{j(\omega+2\pi)}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j(\omega+2\pi) n}\]Since
\[e^{-j(\omega+2\pi) n} = e^{-j\omega n}\]we obtain
\[X(e^{j(\omega+2\pi)}) = X(e^{j\omega})\]Therefore, only one period of $X(e^{j\omega})$ is needed to completely represent the signal, and it is usually taken to be $-\pi\leq\omega<\pi$.
Recall from the post on complex exponentials that the frequencies near $\omega=0$ and $\omega=\pm2\pi$ are low, and that the highest frequency is $\omega=\pm\pi$.
Magnitude and Phase
Like $\tilde{X}[k]$, $X(e^{j\omega})$ is complex-valued, so it can be written in polar form:
\[X(e^{j\omega}) = \lvert X(e^{j\omega}) \rvert \, e^{j\angle X(e^{j\omega})}\]The magnitude $\lvert X(e^{j\omega}) \rvert$ determines how strongly the frequency $\omega$ is present in the signal, and the phase $\angle X(e^{j\omega})$ determines how far that component is shifted. Unlike in the DFS, both are now functions of a continuous variable, so the magnitude spectrum and the phase spectrum are curves rather than sets of points.
For example, a signal that varies slowly has a magnitude spectrum concentrated near $\omega=0$, while a signal that changes sign at every sample has one concentrated near $\omega=\pi$.
As in the DFS, the magnitude spectrum of a real signal is even and its phase spectrum is odd:
\[\lvert X(e^{-j\omega}) \rvert = \lvert X(e^{j\omega}) \rvert \,,\qquad \angle X(e^{-j\omega}) = -\angle X(e^{j\omega})\]Why is the magnitude even and the phase odd?
Take the complex conjugate of the analysis equation. Since $x[n]$ is real, only the exponential changes:
\[X^*(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{j\omega n} = X(e^{-j\omega})\]A complex number and its conjugate have the same magnitude and opposite phases.
[Example] Spectrum of a decaying exponential
Consider a decaying exponential $x[n]=a^n u[n]$ with $\lvert a\rvert<1$:
\[X(e^{j\omega}) = \frac{1}{1-ae^{-j\omega}} \,,\qquad \lvert X(e^{j\omega})\rvert = \frac{1}{\sqrt{1+a^2-2a\cos\omega}}\]If $0<a<1$, the signal decays smoothly, and the magnitude is largest at $\omega=0$. If $-1<a<0$, the signal changes sign at every sample, and the magnitude is largest at $\omega=\pi$. Notice also that the magnitude depends on $\omega$ only through $\cos\omega$, so it is even.
Move $a$ from positive to negative. The peak of the magnitude moves from $\omega=0$ to $\omega=\pm\pi$, while the magnitude stays even and the phase stays odd.
DTFT Properties
The DTFT has the same properties as the DFS. The proofs are also the same, with the sum over one period replaced by a sum over all $n$, so we only state the results and point out what changes.
Linearity
The DTFT of a sum is the sum of the DTFTs:
\[ax_1[n] + bx_2[n] \quad\longleftrightarrow\quad aX_1(e^{j\omega}) + bX_2(e^{j\omega})\]Time Shift
Shifting a signal in time changes only the phase of its spectrum:
\[x[n-n_0] \quad\longleftrightarrow\quad e^{-j\omega n_0} X(e^{j\omega})\]As in the DFS, the magnitude spectrum does not change. The phase changes by $-\omega n_0$, which is a straight line in $\omega$ with slope $-n_0$.
Move the pulse by $n_0$ samples. The magnitude does not change; only the slope of the phase does.
Why does a time shift change only the phase?
Apply the analysis equation to the shifted signal and let $m=n-n_0$:
\[\sum_{n=-\infty}^{\infty} x[n-n_0] e^{-j\omega n} = \sum_{m=-\infty}^{\infty} x[m] e^{-j\omega (m+n_0)} = e^{-j\omega n_0} X(e^{j\omega})\]Frequency Shift
Multiplying a signal by a complex exponential shifts its spectrum:
\[e^{j\omega_0 n} x[n] \quad\longleftrightarrow\quad X(e^{j(\omega-\omega_0)})\]Unlike in the DFS, the frequency is continuous, so the spectrum can be shifted by any amount $\omega_0$, not only by a whole number of harmonics.
Convolution
The convolution of two signals is defined as
\[x[n] * h[n] = \sum_{m=-\infty}^{\infty} x[m] \, h[n-m]\]Unlike in the DFS, the sum runs over all $m$, because the signals are no longer periodic. To tell it apart from periodic convolution, it is also called linear convolution.
Convolution in time becomes multiplication in frequency:
\[x[n] * h[n] \quad\longleftrightarrow\quad X(e^{j\omega}) \, H(e^{j\omega})\]Convolution mixes many samples together, but in the frequency domain each frequency is simply multiplied by a number. This is the main reason why the frequency domain is useful.
Why does convolution become multiplication?
Apply the analysis equation to the convolution and change the order of the two sums:
\[\begin{aligned} \sum_{n=-\infty}^{\infty} \left( \sum_{m=-\infty}^{\infty} x[m] \, h[n-m] \right) e^{-j\omega n} &= \sum_{m=-\infty}^{\infty} x[m] \left( \sum_{n=-\infty}^{\infty} h[n-m] e^{-j\omega n} \right) \end{aligned}\]By the time shift property, the sum in parentheses is $e^{-j\omega m}H(e^{j\omega})$. Therefore, the right side is
\[H(e^{j\omega}) \sum_{m=-\infty}^{\infty} x[m] e^{-j\omega m} = X(e^{j\omega}) \, H(e^{j\omega})\]Parseval’s Relation
The energy of a signal can be computed in either domain:
\[\sum_{n=-\infty}^{\infty} \lvert x[n]\rvert^2 = \frac{1}{2\pi} \int_{-\pi}^{\pi} \lvert X(e^{j\omega})\rvert^2 d\omega\]Unlike in the DFS, the right side is an integral. Thus, $\lvert X(e^{j\omega})\rvert^2$ describes how the energy is distributed over frequency, not the energy of a single frequency.
Summary
| Property | Time domain | Frequency domain |
|---|---|---|
| Linearity | $ax_1[n]+bx_2[n]$ | $aX_1(e^{j\omega})+bX_2(e^{j\omega})$ |
| Time Shift | $x[n-n_0]$ | $e^{-j\omega n_0}X(e^{j\omega})$ |
| Frequency Shift | $e^{j\omega_0 n}x[n]$ | $X(e^{j(\omega-\omega_0)})$ |
| Linear Convolution | $x[n]*h[n]$ | $X(e^{j\omega})\,H(e^{j\omega})$ |
| Parseval’s Relation | $\sum_{n=-\infty}^{\infty}\lvert x[n]\rvert^2$ | $\frac{1}{2\pi}\int_{-\pi}^{\pi}\lvert X(e^{j\omega})\rvert^2\,d\omega$ |