Signals and Systems

5.1 Discrete-Time Fourier Transform (DTFT)

Imron Rosyadi

Discrete-Time Fourier Transform (DTFT)

Representation of Aperiodic Signals in Discrete Time

Welcome to this lecture on the Discrete-Time Fourier Transform, or DTFT. Today, we’ll explore how to represent aperiodic discrete-time signals in the frequency domain, building on concepts from continuous-time Fourier analysis and discrete-time Fourier series. This is a fundamental concept in digital signal processing, crucial for understanding and designing various ECE systems.

Why DTFT? Connecting Time and Frequency

• Signals & Systems: Understanding how signals behave in both time and frequency domains is critical.
• Aperiodic Signals: Unlike periodic signals, aperiodic signals don’t repeat. How do we analyze their frequency content?
• Analogy to Continuous Time: Recall the Continuous-Time Fourier Transform (CTFT) for aperiodic continuous-time signals. We’ll follow a similar path for discrete-time signals.
• From DTFS to DTFT: The DTFT can be derived from the Discrete-Time Fourier Series (DTFS) by extending the period to infinity.

The Fourier Transform is a cornerstone of signals and systems. For periodic signals, we have Fourier Series. But what about signals that don’t repeat, known as aperiodic signals? For continuous-time signals, we used the CTFT. Today, we develop the equivalent for discrete-time signals: the DTFT. The core idea is similar: we’ll start with a periodic signal and let its period approach infinity, much like how the CTFT was derived from the CTFS.

Developing the DTFT: From Periodic to Aperiodic

To understand the DTFT, we start with a finite-duration aperiodic sequence \(x[n]\).

1. Finite-Duration Aperiodic Signal \(x[n]\)

• \(x[n]=0\) outside a range \(-N_1 \leq n \leq N_2\).
• This is the signal we want to analyze.

Figure 5.1(a): Finite-duration signal $x[n]

2. Construct a Periodic Signal \(\tilde{x}[n]\)

• Create \(\tilde{x}[n]\) such that \(x[n]\) is one period of \(\tilde{x}[n]\).
• As period \(N \rightarrow \infty\), \(\tilde{x}[n]\) becomes identical to \(x[n]\) over an increasingly large interval.

Figure 5.1(b): Periodic signal \(\tilde{x}[n]\)

Let’s consider a general discrete-time sequence \(x[n]\) that only has non-zero values over a finite duration, say from \(-N_1\) to \(N_2\). This is our aperiodic signal. To apply Fourier series concepts, we construct a new periodic signal, \(\tilde{x}[n]\), where \(x[n]\) forms exactly one period. Imagine taking \(x[n]\) and repeating it every \(N\) samples. As we make this period \(N\) larger and larger, \(\tilde{x}[n]\) will look more and more like \(x[n]\) within any finite window.

The Discrete-Time Fourier Series (DTFS)

The periodic signal \(\tilde{x}[n]\) can be represented by its Discrete-Time Fourier Series (DTFS):

\[ \tilde{x}[n]=\sum_{k=\langle N\rangle} a_{k} e^{j k(2 \pi / N) n} \quad \text{(Eq. 5.1)} \]

where the Fourier series coefficients \(a_k\) are given by:

\[ a_{k}=\frac{1}{N} \sum_{n=\langle N\rangle} \tilde{x}[n] e^{-j k(2 \pi / N) n} \quad \text{(Eq. 5.2)} \]

• The summation \(\sum_{k=\langle N\rangle}\) or \(\sum_{n=\langle N\rangle}\) denotes a sum over any \(N\) consecutive values of \(k\) or \(n\), respectively.
• \(\omega_0 = 2\pi/N\) is the fundamental frequency.

For this periodic signal \(\tilde{x}[n]\), we can use the DTFS. Equation 5.1 shows that \(\tilde{x}[n]\) is a sum of complex exponentials, each with a frequency that is a multiple of the fundamental frequency \(\omega_0 = 2\pi/N\). The coefficients \(a_k\) tell us the amplitude and phase of each of these exponential components, and they are calculated using Equation 5.2.

Connecting DTFS Coefficients to the Aperiodic Signal

Since \(\tilde{x}[n] = x[n]\) over one period (which includes \(-N_1 \leq n \leq N_2\)), we can replace \(\tilde{x}[n]\) with \(x[n]\) in the summation for \(a_k\):

\[ a_{k}=\frac{1}{N} \sum_{n=-N_{1}}^{N_{2}} x[n] e^{-j k(2 \pi / N) n}=\frac{1}{N} \sum_{n=-\infty}^{+\infty} x[n] e^{-j k(2 \pi / N) n} \quad \text{(Eq. 5.3)} \]

We define a new function, the Discrete-Time Fourier Transform (DTFT) of \(x[n]\):

\[ X\left(e^{j \omega}\right)=\sum_{n=-\infty}^{+\infty} x[n] e^{-j \omega n} \quad \text{(Eq. 5.4)} \]

Now, we can see that the Fourier coefficients \(a_k\) are simply samples of \(X(e^{j\omega})\):

\[ a_{k}=\frac{1}{N} X\left(e^{j k \omega_{0}}\right) \quad \text{(Eq. 5.5)} \]

Because \(x[n]\) is zero outside its finite duration, we can extend the summation limits for \(a_k\) to infinity and replace \(\tilde{x}[n]\) with \(x[n]\). This leads us to define the DTFT, \(X(e^{j\omega})\), which is essentially an infinite sum of \(x[n]\) weighted by complex exponentials. Crucially, we find that the DTFS coefficients \(a_k\) are proportional to samples of this DTFT function \(X(e^{j\omega})\) at specific frequencies \(k\omega_0\). \(X(e^{j\omega})\) acts as an “envelope” for the Fourier series coefficients.

From Summation to Integration: The DTFT Pair

Substitute \(a_k\) back into the DTFS synthesis equation for \(\tilde{x}[n]\):

\[ \tilde{x}[n]=\sum_{k=\langle N\rangle} \frac{1}{N} X\left(e^{j k \omega_{0}}\right) e^{j k \omega_{0} n} \quad \text{(Eq. 5.6)} \]

Since \(1/N = \omega_0 / 2\pi\):

\[ \tilde{x}[n]=\frac{1}{2 \pi} \sum_{k=\langle N\rangle} X\left(e^{j k \omega_{0}}\right) e^{j k \omega_{0} n} \omega_{0} \quad \text{(Eq. 5.7)} \]

As \(N \rightarrow \infty\):

• \(\omega_0 = 2\pi/N \rightarrow 0\) (samples become infinitely close).
• The summation becomes an integral.
• \(\tilde{x}[n] \rightarrow x[n]\).

Figure 5.2: Graphical interpretation of Eq. 5.7, showing the Riemann sum.

Now, we take this expression for \(\tilde{x}[n]\) and rewrite it slightly by substituting \(1/N\) with \(\omega_0 / 2\pi\). This form is very important because it looks like a Riemann sum. As we let the period \(N\) approach infinity, the fundamental frequency \(\omega_0\) approaches zero. This means the frequency samples \(k\omega_0\) become infinitesimally close, and the summation transforms into an integral. At the same time, \(\tilde{x}[n]\) becomes identical to our original aperiodic signal \(x[n]\). This is the crucial step that bridges the Fourier series to the Fourier transform.

The Discrete-Time Fourier Transform (DTFT) Pair

The result of this limiting process gives us the DTFT pair:

Analysis Equation (Forward DTFT):

(From time domain \(x[n]\) to frequency domain \(X(e^{j\omega})\))

\[ X\left(e^{j \omega}\right) =\sum_{n=-\infty}^{+\infty} x[n] e^{-j \omega n} \quad \text{(Eq. 5.9)} \]

• \(X(e^{j\omega})\) is the spectrum of \(x[n]\).
• It shows how \(x[n]\) is composed of complex exponentials at different frequencies.

Synthesis Equation (Inverse DTFT):

(From frequency domain \(X(e^{j\omega})\) to time domain \(x[n]\))

\[ x[n] =\frac{1}{2 \pi} \int_{2 \pi} X\left(e^{j \omega}\right) e^{j \omega n} d \omega \quad \text{(Eq. 5.8)} \]

• Integrates over any interval of length \(2\pi\).
• Reconstructs \(x[n]\) as a linear combination of complex exponentials.

Important

Key Differences from CTFT:

1. Periodicity: \(X(e^{j\omega})\) is always periodic in \(\omega\) with period \(2\pi\).
2. Integration Interval: The integral in the synthesis equation is over a finite interval of length \(2\pi\).

These stem from the periodicity of discrete-time complex exponentials \(e^{j\omega n}\) in \(\omega\).

These two equations, 5.9 and 5.8, form the Discrete-Time Fourier Transform pair. Equation 5.9, the analysis equation, takes a discrete-time signal \(x[n]\) and transforms it into its frequency domain representation, \(X(e^{j\omega})\). This function, often called the spectrum, tells us the frequency content of \(x[n]\). Equation 5.8, the synthesis equation, allows us to reconstruct the original time-domain signal \(x[n]\) from its spectrum.

It’s crucial to note the main differences from the continuous-time Fourier transform. Firstly, \(X(e^{j\omega})\) is always periodic with a period of \(2\pi\). This is a direct consequence of discrete-time complex exponentials repeating every \(2\pi\) radians. Secondly, the inverse transform only requires integration over a finite \(2\pi\) interval, unlike the infinite integral in the CTFT. These properties are fundamental to understanding discrete-time signal processing.

Frequency Interpretation in Discrete Time

The periodicity of \(X(e^{j\omega})\) with period \(2\pi\) has important implications for interpreting frequencies:

Low Frequencies:

• Values of \(\omega\) near \(0, \pm 2\pi, \pm 4\pi, \ldots\)
• Correspond to slowly varying signals.
• Example: \(x_1[n]\) in Figure 5.3(a) with its spectrum \(X_1(e^{j\omega})\) in Figure 5.3(b).

Figure 5.3(a): Slowly varying signal \(x_1[n]\)

Figure 5.3(b): Spectrum \(X_1(e^{j\omega})\) concentrated near \(0, \pm 2\pi, \dots\)

High Frequencies:

• Values of \(\omega\) near \(\pm \pi, \pm 3\pi, \ldots\)
• Correspond to rapidly varying, alternating signals.
• Example: \(x_2[n]\) in Figure 5.3(c) with its spectrum \(X_2(e^{j\omega})\) in Figure 5.3(d).

Figure 5.3(c): Rapidly varying signal \(x_2[n]\)

Figure 5.3(d): Spectrum \(X_2(e^{j\omega})\) concentrated near \(\pm \pi, \dots\)

Because discrete-time complex exponentials \(e^{j\omega n}\) are periodic in \(\omega\) with period \(2\pi\), frequencies like \(\omega=0\), \(\omega=2\pi\), \(\omega=4\pi\) all represent the same “DC” or slowly varying component. Similarly, frequencies like \(\omega=\pi\), \(\omega=3\pi\), \(\omega=5\pi\) represent the fastest possible oscillation in a discrete-time signal, where successive samples alternate in sign. These are considered the “high frequencies” in discrete-time. The figures illustrate this: a signal with energy concentrated near \(0\) and \(2\pi\) is smooth, while a signal with energy near \(\pi\) is rapidly oscillating.

Example 5.1: Real Exponential Sequence

Consider the causal real exponential sequence:

\[ x[n]=a^{n} u[n], \quad|a|<1 \]

Using the DTFT analysis equation (Eq. 5.9):

\[ \begin{aligned} X\left(e^{j \omega}\right) & =\sum_{n=-\infty}^{+\infty} a^{n} u[n] e^{-j \omega n} \\ & =\sum_{n=0}^{\infty}\left(a e^{-j \omega}\right)^{n} \end{aligned} \]

This is a geometric series. For convergence, we require \(|a e^{-j\omega}| < 1\), which simplifies to \(|a|<1\).

\[ X\left(e^{j \omega}\right) = \frac{1}{1-a e^{-j \omega}} \]

Let’s look at our first example: a causal real exponential. This signal starts at \(n=0\) and decays exponentially. The condition \(|a|<1\) is essential for the infinite sum to converge. We plug \(x[n]\) into the DTFT formula. The unit step \(u[n]\) changes the lower limit of the sum to \(n=0\). We recognize this as a standard geometric series, which has a known closed-form solution. The result is \(1 / (1 - a e^{-j\omega})\).

Interactive Plot: Example 5.1 Spectrum

Explore the magnitude and phase spectrum of \(x[n] = a^n u[n]\) for different values of \(a\).

viewof a_val = Inputs.range([-0.9, 0.9], {value: 0.5, step: 0.05, label: "Coefficient 'a' (|a|<1)"});

Here’s an interactive plot where you can observe how the magnitude and phase of the DTFT change for different values of ‘a’. Notice the periodicity of both magnitude and phase with period \(2\pi\). When ‘a’ is positive, the spectrum is concentrated at low frequencies (\(\omega=0, \pm 2\pi\)). When ‘a’ is negative, the signal alternates more rapidly, and its spectrum shifts towards high frequencies (\(\omega=\pm \pi\)). This visual helps reinforce the concept of low and high frequencies in discrete time.

Example 5.2: Two-Sided Exponential Sequence

Consider the two-sided exponential sequence:

\[ x[n]=a^{|n|}, \quad|a|<1 \]

This signal is symmetric around \(n=0\).

Using the DTFT analysis equation (Eq. 5.9):

\[ \begin{aligned} X\left(e^{j \omega}\right) & =\sum_{n=-\infty}^{+\infty} a^{|n|} e^{-j \omega n} \\ & =\sum_{n=0}^{\infty} a^{n} e^{-j \omega n}+\sum_{n=-\infty}^{-1} a^{-n} e^{-j \omega n} \end{aligned} \]

By substituting \(m=-n\) in the second sum, and evaluating both geometric series:

\[ X\left(e^{j \omega}\right) = \frac{1}{1-a e^{-j \omega}}+\frac{a e^{j \omega}}{1-a e^{j \omega}} = \frac{1-a^{2}}{1-2 a \cos \omega+a^{2}} \]

In this case, \(X(e^{j\omega})\) is purely real.

Figure 5.5(a): Signal \(x[n]=a^{|n|}\) for \(0<a<1\).

Next, we examine a two-sided exponential, which means it extends to both positive and negative infinity. The absolute value in the exponent makes it symmetric. We split the summation into two parts: one for \(n \ge 0\) and one for \(n < 0\). By a change of variable in the second sum, both become standard geometric series. After some algebraic manipulation, we arrive at the closed-form expression. Note that since \(x[n]\) is a real and even signal, its Fourier transform \(X(e^{j\omega})\) is purely real and even.

Interactive Plot: Example 5.2 Spectrum

Observe the real-valued spectrum of \(x[n] = a^{|n|}\) for \(0 < a < 1\).

viewof a_abs_val = Inputs.range([0.05, 0.95], {value: 0.7, step: 0.05, label: "Coefficient 'a' (0 < a < 1)"});

This interactive plot shows the real-valued spectrum of the two-sided exponential. Since \(x[n]\) is real and even, its DTFT is also real and even, meaning the phase is either \(0\) or \(\pi\). As ‘a’ approaches 1, the signal decays slower, becoming broader in time, and its spectrum becomes sharper and more concentrated around DC (\(\omega=0\)). This illustrates the inverse relationship between signal duration in time and bandwidth in frequency.

Example 5.3: Rectangular Pulse

Consider the rectangular pulse sequence:

\[ x[n]= \begin{cases}1, & |n| \leq N_{1} \\ 0, & |n|>N_{1}\end{cases} \]

This means \(x[n]=1\) for \(n = -N_1, \ldots, 0, \ldots, N_1\).

The DTFT is:

\[ X\left(e^{j \omega}\right)=\sum_{n=-N_{1}}^{N_{1}} e^{-j \omega n} \quad \text{(Eq. 5.11)} \]

This is a finite geometric series.

Using the formula for a finite geometric series, we get:

\[ X\left(e^{j \omega}\right)=\frac{\sin \omega\left(N_{1}+\frac{1}{2}\right)}{\sin (\omega / 2)} \quad \text{(Eq. 5.12)} \]

This function is the discrete-time counterpart of the continuous-time sinc function.

Figure 5.6(a): Rectangular pulse for \(N_1=2\).

Our third example is the discrete-time rectangular pulse. This signal has a constant value of 1 for a finite number of samples centered around zero, and is zero elsewhere. The DTFT involves a finite sum of complex exponentials. This sum can be evaluated using the formula for a finite geometric series. The resulting expression is often called the Dirichlet kernel, and it’s the discrete-time equivalent of the continuous-time sinc function. A key difference, however, is that this discrete-time version is periodic, unlike the aperiodic sinc function.

Interactive Plot: Example 5.3 Spectrum

Visualize the spectrum of a rectangular pulse \(x[n]\) for different pulse widths \(N_1\).

viewof N1_val = Inputs.range([1, 10], {value: 3, step: 1, label: "Pulse half-width N1"});

In this interactive plot, you can change the half-width \(N_1\) of the rectangular pulse. Observe how increasing \(N_1\) makes the pulse wider in the time domain, and consequently, its spectrum becomes narrower in the frequency domain, with more distinct sidelobes. This again demonstrates the inverse relationship between signal duration and spectral bandwidth. Notice the main lobe centered at \(\omega=0\) and how its width changes. Also, observe the periodicity of the spectrum.

Convergence Issues

For the DTFT analysis equation (Eq. 5.9) to converge, \(x[n]\) must satisfy certain conditions:

1. Absolute Summability:

\[ \sum_{n=-\infty}^{+\infty}|x[n]|<\infty \quad \text{(Eq. 5.13)} \]

• This is the strongest condition and guarantees uniform convergence of \(X(e^{j\omega})\).

2. Finite Energy:

\[ \sum_{n=-\infty}^{+\infty}|x[n]|^{2}<\infty \quad \text{(Eq. 5.14)} \]

• If \(x[n]\) has finite energy, the DTFT converges in a mean-square sense (Plancherel’s theorem).

Note

Synthesis Equation Convergence:

The synthesis equation (Eq. 5.8) generally has no convergence issues because the integral is over a finite interval of length \(2\pi\).

This is a key difference from the CTFT, where reconstruction can exhibit Gibbs phenomenon.

Just like with continuous-time Fourier transforms, the infinite sum in the DTFT analysis equation doesn’t always converge. We have two main conditions. The most stringent is absolute summability, which guarantees that the DTFT exists and is a continuous function of frequency. A weaker but still very important condition is finite energy. If a signal has finite energy, its DTFT converges in a mean-square sense, which is sufficient for many practical applications.

Interestingly, the synthesis equation, which reconstructs the time-domain signal, typically doesn’t have convergence issues. This is because it involves an integral over a finite interval (\(2\pi\)), unlike the infinite integral in the CTFT synthesis. This means we don’t usually see the Gibbs phenomenon in DTFT reconstruction when integrating over the full \(2\pi\) range.

Example 5.4: Unit Impulse Signal

Consider the unit impulse:

\[ x[n]=\delta[n] \]

Using the DTFT analysis equation:

\[ X\left(e^{j \omega}\right)=\sum_{n=-\infty}^{+\infty} \delta[n] e^{-j \omega n} = e^{-j \omega (0)} = 1 \]

The DTFT of a unit impulse is \(1\), meaning it contains equal contributions at all frequencies.

Now, let’s approximate \(\delta[n]\) using the inverse DTFT over a limited frequency range \([-W, W]\):

\[ \hat{x}[n]=\frac{1}{2 \pi} \int_{-W}^{W} e^{j \omega n} d \omega = \frac{\sin W n}{\pi n} \quad \text{(Eq. 5.16)} \]

• As \(W \rightarrow \pi\), \(\hat{x}[n]\) approaches \(\delta[n]\).
• Unlike CTFT, no Gibbs phenomenon for \(W=\pi\).

Our final example is the unit impulse, \(\delta[n]\). This is the simplest discrete-time signal, non-zero only at \(n=0\). When we apply the DTFT analysis equation, the sum collapses to just one term, \(e^{-j\omega \cdot 0}\), which is 1. This means the unit impulse has a flat spectrum, containing all frequencies equally.

Now, if we try to reconstruct this impulse using the inverse DTFT but integrate only over a finite band of frequencies, say from \(-W\) to \(W\), we get the function \(\sin(Wn) / (\pi n)\). This function is similar to the sinc function. What’s important here is that as \(W\) approaches \(\pi\), this function perfectly converges to \(\delta[n]\) without the overshoot and undershoot characteristic of the Gibbs phenomenon seen in continuous-time for rectangular pulses. This is due to the finite integration interval of the DTFT synthesis equation.

Interactive Plot: Example 5.4 Impulse Reconstruction

Observe how the approximation \(\hat{x}[n]\) approaches \(\delta[n]\) as the integration bandwidth \(W\) increases.

viewof W_val = Inputs.range([0.1, 3.14], {value: 3.14/2, step: 0.1, label: "Bandwidth W (0 to π)"});

This interactive plot allows you to vary the bandwidth \(W\) used for reconstructing the unit impulse. As you increase \(W\) towards \(\pi\), you’ll see \(\hat{x}[n]\) becoming sharper and more concentrated at \(n=0\), while values for \(n \ne 0\) diminish. Crucially, when \(W\) reaches \(\pi\), \(\hat{x}[n]\) becomes exactly \(\delta[n]\) (1 at \(n=0\) and 0 elsewhere), demonstrating the perfect reconstruction without Gibbs phenomenon, which is a unique and important aspect of the DTFT synthesis.

Summary & ECE Applications

Key Takeaways:

• The DTFT extends Fourier analysis to aperiodic discrete-time signals.
• DTFT Pair:
  • Analysis: \(X\left(e^{j \omega}\right) =\sum_{n=-\infty}^{+\infty} x[n] e^{-j \omega n}\)
  • Synthesis: \(x[n] =\frac{1}{2 \pi} \int_{2 \pi} X\left(e^{j \omega}\right) e^{j \omega n} d \omega\)
• Periodicity: \(X(e^{j\omega})\) is always periodic with period \(2\pi\).
• Frequency Interpretation: Low frequencies near \(0, \pm 2\pi, \ldots\); High frequencies near \(\pm \pi, \pm 3\pi, \ldots\).
• Convergence conditions for analysis (absolute summability/finite energy) differ from synthesis (always converges).

Tip

Applications in ECE:

• Digital Filter Design: DTFT is essential for understanding and designing digital filters (e.g., FIR, IIR) by analyzing their frequency response.
• Spectral Analysis: Analyzing the frequency content of discrete-time signals (e.g., speech, audio, biomedical signals).
• System Analysis: Characterizing the input-output behavior of discrete-time LTI systems using frequency response.
• Communication Systems: Modulation, demodulation, and channel equalization in digital communication.

To summarize, the DTFT provides a powerful framework for analyzing aperiodic discrete-time signals in the frequency domain. Remember the two key equations and the crucial property of periodicity in the frequency domain. The DTFT is not just a theoretical tool; it’s fundamental to many practical ECE applications, from designing the digital filters in your phone or audio system, to analyzing brain signals in medical devices, and understanding how data is transmitted in communication systems. Mastering the DTFT is a critical step in your journey as an ECE student.