From Time Domain to Frequency Domain | DSP-101

Every Signal is a Sum of Sinusoids

Why do engineers care so much about the frequency domain? The answer lies in a remarkable mathematical fact: any signal can be expressed as a weighted sum of sinusoids. This is the essence of Fourier analysis, and it transforms signal processing from a problem of tracking waveforms over time into a problem of managing amplitudes and phases across frequencies. For a discrete-time signal, the natural tool for this transformation is the Discrete-Time Fourier Transform (DTFT).

Thinking in frequencies pays dividends throughout DSP. Filters are most naturally designed by specifying which frequencies to pass and which to reject. Noise that concentrates in a particular frequency band is easy to suppress once it is visible as a spectral peak. Speech, music, and RF signals each have characteristic frequency-domain signatures that reveal structure invisible in the time domain. The frequency domain is not just convenient — it is often the most natural home for the problems we want to solve.

The Discrete-Time Fourier Transform

The DTFT maps a discrete-time sequence x[n] to a continuous function of frequency X(e^jω). Unlike the Z-transform, which uses a general complex variable z, the DTFT evaluates the Z-transform on the unit circle z = e^jω. The result is a complex-valued function of the normalized angular frequency ω (radians per sample), which is periodic with period 2π.

DTFT Definition

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

The DTFT sums the sequence x[n] weighted by complex exponentials e^{−jωn}. The result X(e^{jω}) is a continuous, periodic function of ω with period 2π. Convergence requires the sequence to be absolutely summable.

The inverse DTFT recovers x[n] by integrating X(e^jω) over one period:

Inverse DTFT

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

Integrating X(e^{jω}) e^{jωn} over [−π, π] and dividing by 2π recovers the original sequence x[n] exactly. This confirms the DTFT is a complete, invertible representation.

Normalized Frequency

In discrete time, frequency ω is measured in radians per sample, ranging from −π to π. To convert to physical frequency in Hz, multiply by f_s/(2π). The Nyquist frequency f_s/2 corresponds to ω = π.

ω = 2π f / f_s — so ω = π corresponds to f = f_s/2 (Nyquist)

Key DTFT Properties

The DTFT inherits a rich set of properties from the Fourier transform family. These properties are not merely mathematical curiosities — they are practical tools that let you reason about how operations on a signal (shifting, scaling, filtering) manifest in the frequency domain without re-doing the integral each time.

Linearity

Superposition

DTFT{ax[n] + by[n]} = aX(e^jω) + bY(e^jω). Decompose complex signals into simpler components, transform each, and add results.

Time Shift

Phase Shift

DTFT{x[n − n₀]} = e^−jωn₀ X(e^jω). Delaying a signal by n₀ samples multiplies its spectrum by a linear phase factor — magnitude is unchanged.

Convolution

Multiplication

DTFT{x[n] ∗ h[n]} = X(e^jω) H(e^jω). Convolution in time equals pointwise multiplication in frequency — the foundation of linear filtering.

Symmetry

Real Signals

For real x[n], |X(e^jω)| is even and ∠X(e^jω) is odd. This conjugate symmetry means the full spectrum is determined by its values on [0, π].

The convolution–multiplication duality is arguably the most important property. It means that filtering — which is convolution in the time domain — becomes pointwise multiplication in the frequency domain. To design a low-pass filter, you simply specify H(e^jω) = 1 for |ω| < ω_c and H(e^jω) = 0 otherwise, then find the corresponding h[n] via the inverse DTFT.

Common DTFT Pairs

A handful of DTFT pairs appear over and over in DSP. Memorizing these — or being able to derive them quickly — saves significant computation.

Unit Impulse

\delta[n] \xrightarrow{\text{DTFT}} 1 \quad (\text{flat spectrum for all }\omega)

The unit impulse δ[n] has a flat (white) spectrum — equal energy at all frequencies. This is why it is the ultimate test signal for LTI systems.

Causal Exponential

a^n u[n] \xrightarrow{\text{DTFT}} \frac{1}{1 - a\,e^{-j\omega}}, \quad |a| < 1

The causal exponential a^n u[n] (with |a| < 1 for convergence) transforms to a rational frequency response. The magnitude peaks near ω = 0 for positive real a and near ω = π for negative a.

Rectangular Window (Ideal LP Filter)

H(e^{j\omega}) = \begin{cases} 1 & |\omega| \leq \omega_c \\ 0 & \omega_c < |\omega| \leq \pi \end{cases} \xrightarrow{\text{IDTFT}} h[n] = \frac{\omega_c}{\pi}\operatorname{sinc}\!\left(\frac{\omega_c n}{\pi}\right)

The ideal low-pass filter has a rectangular spectrum (1 for |ω| ≤ ωc, 0 otherwise). Its inverse DTFT is the sinc sequence h[n] = ωc/π · sinc(ωc n/π) — infinite in duration, which is why practical filters must truncate and window it.

The Limitation: Continuous Frequency

The DTFT is mathematically elegant but computationally inconvenient. Its output X(e^jω) is a continuous function of ω — it takes on infinitely many values. A digital computer can only store and manipulate a finite set of numbers. We cannot represent or compute the full DTFT on a machine without some approximation or sampling strategy.

A second issue is efficiency. Even evaluating X(e^jω) at a single frequency ω₀ requires summing over all N samples of x[n], which is O(N) per frequency point. Evaluating at K frequency points costs O(NK) — potentially enormous for long signals.

Why the DTFT Isn't Enough

The DTFT maps a finite (or infinite) discrete-time sequence to a continuous frequency function. Digital systems need a discrete frequency representation — a finite set of numbers — to be computable. The solution is to sample the DTFT at N equally spaced frequencies.

Sampling the DTFT: The DFT

If we evaluate the DTFT at N equally spaced frequencies ω_k = 2πk/N for k = 0, 1, …, N−1, we obtain the Discrete Fourier Transform (DFT):

DFT Definition

X[k] = \sum_{n=0}^{N-1} x[n]\,e^{-j2\pi kn/N}, \quad k = 0, 1, \ldots, N-1

X[k] is the DFT of the N-point sequence x[n]. Each bin k corresponds to frequency ωk = 2πk/N radians/sample, or fk = k·fs/N Hz. The DFT is both discrete in time and discrete in frequency — fully computable.

The DFT is the DTFT sampled at N equally spaced points around the unit circle. Crucially, it is a finite, invertible transform: N complex numbers go in, N complex numbers come out, and the original sequence is exactly recoverable via the inverse DFT. This makes it the workhorse of computational spectral analysis.

However, sampling the DTFT in frequency is not free. Just as sampling in time creates periodicity in frequency (aliasing), sampling in frequency creates periodicity in time — the DFT implicitly treats x[n] as one period of a periodic signal. This circular (periodic) nature of the DFT has important consequences for windowing, zero-padding, and circular convolution, all of which are explored in the next lessons.

The next lesson dives into the DFT formula, the meaning of each frequency bin, frequency resolution, and the DFT as a matrix operation — building the computational toolkit for spectrum analysis.

Key Takeaways

Every signal is a weighted sum of sinusoids; the frequency domain reveals this decomposition, making filter design and noise analysis natural and intuitive.
The DTFT maps a discrete-time sequence x[n] to a continuous, 2π-periodic function X(e^jω) of normalized angular frequency ω (radians/sample).
Normalized frequency ω = π corresponds to the Nyquist frequency f_s/2; the relationship is ω = 2πf/f_s.
Convolution in time equals multiplication in frequency — the foundation of LTI filtering in the frequency domain.
The DTFT is continuous in frequency and therefore not directly computable; a digital machine requires a finite, discrete frequency representation.
Sampling the DTFT at N equally spaced frequencies yields the DFT: X[k] = Σ x[n] e^−j2πkn/N, which is fully computable and invertible.
The DFT implicitly treats x[n] as periodic with period N — a key property that drives windowing and zero-padding considerations.