1.3 Discrete-time Fourier transform

Definition of DTFT

The Discrete-time Fourier Transform (DTFT) analyzes discrete-time signals in the frequency domain. It takes a sequence of samples and reveals what frequencies are present, how strong they are, and how they relate to each other. This makes it foundational for filter design, spectral analysis, and understanding how digital systems respond to different inputs.

Discrete-time signals

Discrete-time signals are sequences of values defined at integer time indices, written as $x[n]$ where $n$ is an integer. They can come from sampling a continuous-time signal at regular intervals, or they can be generated directly in a digital system (think audio samples, digital communication symbols, or sensor readings).

The key distinction from continuous-time signals: you only have values at specific instants, not a smooth curve. This discrete nature is what makes the DTFT the right transform for the job, rather than the continuous-time Fourier transform.

Fourier transform formula

The DTFT of a discrete-time signal $x[n]$ is defined as:

$X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n}$

Breaking this apart:

• $X(e^{j\omega})$ is the resulting frequency-domain representation, a function of the continuous frequency variable $\omega$.
• Each sample $x[n]$ gets multiplied by the complex exponential $e^{-j\omega n}$, which acts as the basis function for frequency $\omega$.
• The sum runs over all integer time indices from $-\infty$ to $\infty$.
• The normalized frequency $\omega$ ranges from $-\pi$ to $\pi$ (in radians per sample).

Notice the notation $X(e^{j\omega})$ rather than just $X(\omega)$. This convention emphasizes that the DTFT is the z-transform evaluated on the unit circle ($z = e^{j\omega}$).

Frequency domain representation

The DTFT maps $x[n]$ from the time domain to a continuous function of frequency. Even though the input is discrete, the output $X(e^{j\omega})$ is continuous and $2\pi$-periodic in $\omega$.

This frequency-domain view lets you:

• Identify which frequencies are present in a signal and their relative strengths
• Determine bandwidth and spectral shape
• Design frequency-selective filters by specifying desired behavior in the $\omega$ domain
• Analyze how LTI systems modify different frequency components

Properties of DTFT

The DTFT has a set of properties that make frequency-domain analysis practical. Rather than computing the full summation every time, you can often use these properties to derive transforms of modified signals from known ones.

Linearity

The DTFT obeys superposition. For signals $x[n]$ and $y[n]$ with DTFTs $X(e^{j\omega})$ and $Y(e^{j\omega})$:

$a \cdot x[n] + b \cdot y[n] \leftrightarrow a \cdot X(e^{j\omega}) + b \cdot Y(e^{j\omega})$

This means you can decompose a complex signal into simpler parts, transform each one separately, and combine the results.

Time shifting

Delaying a signal by $k$ samples introduces a linear phase shift in the frequency domain:

$x[n-k] \leftrightarrow e^{-j\omega k} X(e^{j\omega})$

The magnitude spectrum $|X(e^{j\omega})|$ stays the same. Only the phase changes, by $-\omega k$. This is why a pure delay doesn't alter what frequencies are present; it just shifts their phases.

Frequency shifting

Multiplying by a complex exponential in time shifts the spectrum:

$x[n] e^{j\omega_0 n} \leftrightarrow X(e^{j(\omega-\omega_0)})$

This is the modulation property. It translates the entire spectrum by $\omega_0$, which is the basis for frequency-domain modulation and demodulation techniques.

Time reversal

Reversing the time axis reflects the spectrum:

$x[-n] \leftrightarrow X(e^{-j\omega})$

For real-valued signals where $X(e^{-j\omega}) = X^*(e^{j\omega})$, time reversal conjugates the spectrum.

Conjugation

Taking the complex conjugate of a signal in time produces:

$x^*[n] \leftrightarrow X^*(e^{-j\omega})$

This combines conjugation with frequency reversal. For real signals ($x[n] = x^*[n]$), this property gives you the conjugate symmetry relation $X(e^{j\omega}) = X^*(e^{-j\omega})$, which means the magnitude spectrum is even and the phase spectrum is odd.

Convolution vs multiplication

Convolution in time becomes multiplication in frequency:

$x[n] * h[n] \leftrightarrow X(e^{j\omega}) H(e^{j\omega})$

This is arguably the most practically important DTFT property. For an LTI system with impulse response $h[n]$, the output spectrum is simply the input spectrum times the frequency response $H(e^{j\omega})$. It turns a computationally expensive convolution sum into a pointwise product.

The dual also holds: multiplication in time corresponds to periodic convolution in frequency (scaled by $\frac{1}{2\pi}$).

Parseval's relation

Parseval's relation connects energy in both domains:

$\sum_{n=-\infty}^{\infty} |x[n]|^2 = \frac{1}{2\pi} \int_{-\pi}^{\pi} |X(e^{j\omega})|^2 d\omega$

The total energy computed from the time-domain samples equals the total energy computed from the power spectral density $|X(e^{j\omega})|^2$. This is useful for verifying calculations and for analyzing how energy distributes across frequency.

Convergence of DTFT

Not every discrete-time signal has a well-defined DTFT. The infinite summation in the definition must converge, and the type of convergence depends on the signal's properties.

Absolutely summable sequences

A signal $x[n]$ is absolutely summable if:

$\sum_{n=-\infty}^{\infty} |x[n]| < \infty$

When this condition holds, the DTFT converges uniformly to a continuous function of $\omega$. Finite-length sequences and exponentially decaying sequences (like $a^n u[n]$ with $|a| < 1$) satisfy this condition.

Convergence conditions

There are two main sufficient conditions for DTFT convergence:

1. Absolutely summable ($\ell_1$): The DTFT converges pointwise and uniformly to a continuous function $X(e^{j\omega})$.
2. Square summable ($\ell_2$, finite energy): The DTFT converges in the mean-square sense. The energy of the difference between the partial sum and the true DTFT approaches zero as more terms are included, but the DTFT may have discontinuities.

Signals that are neither absolutely summable nor square summable (like the unit step $u[n]$) require generalized functions (impulses in the frequency domain) to represent their DTFT.

Region of convergence

For the DTFT specifically, the "region of convergence" is the set of frequencies $\omega$ where the sum converges. For absolutely summable signals, this is the entire range $[-\pi, \pi]$.

More broadly, convergence ties into the z-transform framework. The DTFT exists when the unit circle $|z| = 1$ lies within the ROC of the z-transform. If the z-transform has poles on or near the unit circle, convergence becomes problematic, and the ROC tells you about the signal's stability and causality properties.

Calculation of DTFT

Direct evaluation

The most straightforward approach: plug the signal into the definition and evaluate.

$X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n}$

Steps for a finite-length signal $x[n]$ nonzero only for $n = n_1$ to $n = n_2$:

1. Write out the sum with the actual nonzero limits: $X(e^{j\omega}) = \sum_{n=n_1}^{n_2} x[n] e^{-j\omega n}$
2. Substitute each sample value and expand.
3. Simplify using Euler's formula or geometric series identities where possible.
4. Express the result in terms of $\omega$.

For infinite-length signals like $a^n u[n]$ with $|a| < 1$, the sum becomes a geometric series that has a closed-form solution.

Properties-based approach

When direct evaluation is cumbersome, use known transform pairs and DTFT properties to build up the answer.

For example, if you know the DTFT of $a^n u[n]$ and your signal is $n \cdot a^n u[n]$, you can use the differentiation-in-frequency property rather than evaluating the sum from scratch. Similarly, if a signal is a shifted or scaled version of a known sequence, apply time-shifting and linearity.

This approach rewards familiarity with the standard transform pairs and a habit of looking for structural patterns in the signal before computing.

Examples of common sequences

These transform pairs come up repeatedly and are worth memorizing:

• Unit impulse: $\delta[n] \leftrightarrow 1$
• Causal exponential: $a^n u[n] \leftrightarrow \frac{1}{1 - a e^{-j\omega}}, \quad |a| < 1$
• Unit step: $u[n] \leftrightarrow \frac{1}{1 - e^{-j\omega}} + \pi \sum_{k=-\infty}^{\infty} \delta(\omega - 2\pi k)$
• Cosine: $\cos(\omega_0 n) \leftrightarrow \pi[\delta(\omega - \omega_0) + \delta(\omega + \omega_0)]$ (within $[-\pi, \pi]$)

The unit step is notable because it's not absolutely summable, so its DTFT requires an impulse term. The exponential $a^n u[n]$ is one of the most useful building blocks since many causal system impulse responses take this form.

Inverse DTFT

The inverse DTFT recovers the time-domain sequence $x[n]$ from its frequency-domain representation $X(e^{j\omega})$.

Definition of IDTFT

$x[n] = \frac{1}{2\pi} \int_{-\pi}^{\pi} X(e^{j\omega}) e^{j\omega n} d\omega$

This integrates the product of $X(e^{j\omega})$ and $e^{j\omega n}$ over one period of the frequency variable. The $\frac{1}{2\pi}$ normalization factor ensures the forward and inverse transforms are consistent.

Compare with the forward DTFT: the forward transform sums over time with $e^{-j\omega n}$, while the inverse integrates over frequency with $e^{+j\omega n}$.

Existence of IDTFT

For the IDTFT to recover $x[n]$ exactly, $X(e^{j\omega})$ must be:

1. Periodic with period $2\pi$
2. Absolutely integrable over one period: $\int_{-\pi}^{\pi} |X(e^{j\omega})| d\omega < \infty$

In practice, if the original signal $x[n]$ is absolutely summable or has finite energy, these conditions are typically satisfied. When $X(e^{j\omega})$ contains impulse functions (as with the unit step or sinusoids), the integration is handled in the distributional sense.

Calculation of IDTFT

Three common approaches:

1. Direct evaluation: Substitute $X(e^{j\omega})$ into the integral and evaluate analytically. This works well when $X(e^{j\omega})$ has a simple closed form.
2. Partial fractions: If $X(e^{j\omega})$ is a rational function of $e^{j\omega}$, decompose it into partial fractions that match known transform pairs.
3. Transform pair tables: Recognize $X(e^{j\omega})$ (or parts of it) as the DTFT of a known sequence and read off the answer.

For numerical work, the IDTFT is often approximated by sampling $X(e^{j\omega})$ at $N$ equally spaced frequencies and applying the inverse DFT (IDFT), which can be computed efficiently via the FFT.

Applications of DTFT

Frequency response of LTI systems

The frequency response of an LTI system is the DTFT of its impulse response:

$H(e^{j\omega}) = \sum_{n=-\infty}^{\infty} h[n] e^{-j\omega n}$

$H(e^{j\omega})$ is a complex-valued function. Its magnitude $|H(e^{j\omega})|$ tells you the gain at each frequency, and its phase $\angle H(e^{j\omega})$ tells you the phase shift. Together, they completely characterize how the system modifies any input signal's spectrum.

For a causal system described by a difference equation, you can also obtain $H(e^{j\omega})$ by substituting $z = e^{j\omega}$ into the transfer function $H(z)$.

Filtering in frequency domain

The convolution property makes frequency-domain filtering straightforward: multiply the signal's DTFT by the desired filter's frequency response.

• Ideal filters specify a rectangular passband (e.g., $|H(e^{j\omega})| = 1$ for $|\omega| < \omega_c$ and 0 otherwise). These are useful conceptually but have infinite-length, non-causal impulse responses.
• FIR filters approximate the desired frequency response with a finite-length impulse response. Design methods include windowing and frequency sampling.
• IIR filters use feedback (poles) to achieve sharper frequency selectivity with fewer coefficients, at the cost of potential stability concerns.

Frequency-domain filtering also enables efficient computation: transform both signal and filter to the frequency domain, multiply, and inverse-transform. For long signals, overlap-add or overlap-save methods make this practical.

Spectral analysis of signals

Examining $|X(e^{j\omega})|^2$ (the power spectrum) reveals how energy distributes across frequency. Key things you can extract:

• Dominant frequencies: Peaks in the magnitude spectrum indicate the strongest frequency components.
• Bandwidth: The range of frequencies containing most of the signal's energy.
• Spectral shape: Whether energy is concentrated (narrowband) or spread out (wideband).
• Spectral leakage: When analyzing finite-length segments of a signal, truncation causes energy to spread into adjacent frequencies. Windowing techniques (Hamming, Hanning, Blackman) reduce this leakage at the cost of frequency resolution.

These techniques underpin applications in audio processing, speech recognition, radar, communications, and vibration analysis.

Relationship with other transforms

The DTFT sits within a family of Fourier-related transforms. Each handles a different combination of discrete/continuous and periodic/aperiodic signals.

DTFT vs DFT

The DFT is what you actually compute in practice. It samples the DTFT at $N$ equally spaced frequencies:

$X[k] = X(e^{j\omega})\big|_{\omega = 2\pi k/N} = \sum_{n=0}^{N-1} x[n] e^{-j2\pi kn/N}$

Key differences:

• The DTFT is continuous in frequency; the DFT is discrete ($N$ frequency points).
• The DFT implicitly assumes the input sequence is periodic with period $N$. If the signal isn't actually periodic, this causes spectral leakage.
• The DFT can be computed efficiently using the FFT algorithm ($O(N \log N)$ vs. $O(N^2)$).
• You can think of the DFT as a sampled version of the DTFT, and the DTFT as the continuous interpolation of the DFT.

DTFT vs Fourier series

The Fourier series decomposes a periodic continuous-time signal into discrete frequency coefficients. The DTFT does the opposite pairing: it takes a discrete-time (aperiodic) signal and produces a continuous frequency representation.

These two transforms are duals in the sense that discreteness in one domain corresponds to periodicity in the other. If you sample a periodic continuous-time signal, the Fourier series coefficients are related to the DFT of the resulting discrete sequence.

DTFT vs z-transform

The z-transform generalizes the DTFT to the complex plane:

$X(z) = \sum_{n=-\infty}^{\infty} x[n] z^{-n}$

The DTFT is the z-transform evaluated on the unit circle, $z = e^{j\omega}$. The z-transform exists over a region of the complex plane (the ROC), and the DTFT exists only when the unit circle falls within that ROC.

The z-transform is more general because it can handle signals whose DTFT doesn't converge (e.g., growing exponentials). It also provides a natural framework for analyzing system stability (poles inside the unit circle) and causality (ROC extends outward from the outermost pole).

Note: The original guide mentioned the Laplace transform here. The Laplace transform is the continuous-time analog of the z-transform, not a direct comparison with the DTFT. The mapping is $z = e^{sT}$ where $T$ is the sampling period, connecting the s-plane to the z-plane.