Discrete-time Fourier transform

Why it matters

Once a sensor signal has been sampled, every filter, spectrum estimate and frequency measurement in software works on sequences. The discrete-time Fourier transform (DTFT) is the exact spectrum of a sequence and the frequency response of a digital filter. The DFT/FFT that you actually compute is a sampled version of it, so understanding the DTFT is what lets you interpret an FFT plot correctly.

Key ideas

Definition. The DTFT X(e^(jω)) of a sequence x[n] is a continuous function of the digital frequency ω (rad/sample), even though x[n] is defined only at integers. Many books write it as X(ω) or X(Ω).

Periodicity. e^(−jωn) repeats when ω increases by 2π (n is an integer), so X(e^(jω)) is always periodic with period 2π. Only one interval, −π ≤ ω ≤ π (or 0 … 2π), carries information.

• ω = 0 is DC; ω = π is the highest frequency a sequence can have (it alternates +, −, +, −).
• For a sequence obtained by sampling at fs, ω = 2πf/fs, so ω = π corresponds to fs/2.

Existence. The DTFT converges if x[n] is absolutely summable (Σ|x[n]| < ∞); square-summable sequences converge in the mean-square sense. Sequences like 1, cos ω0n or u[n] need impulses in frequency.

Relation to the z-transform. X(e^(jω)) = X(z) evaluated on the unit circle z = e^(jω), provided the ROC includes the unit circle. That is why a stable LTI system always has a frequency response.

Symmetry for real sequences. X(e^(−jω)) = X*(e^(jω)): magnitude even, phase odd. Real and even x[n] ⇒ real and even X.

Properties

• Linearity; time shift x[n − n0] ↔ e^(−jωn0) X(e^(jω)); frequency shift e^(jω0n) x[n] ↔ X(e^(j(ω − ω0))).
• Convolution x * h ↔ X·H — so an LTI system's output spectrum is Y = H·X, with H(e^(jω)) the frequency response.
• Multiplication x[n]·w[n] ↔ (1/2π) periodic convolution of the spectra — the origin of windowing and leakage.
• Differentiation in frequency: n·x[n] ↔ j dX/dω.
• Value shortcuts: X(e^(j0)) = Σ x[n], X(e^(jπ)) = Σ (−1)ⁿ x[n], x[0] = (1/2π) ∫ over 2π of X dω.

Truncation and leakage. Observing only N samples multiplies the signal by a window. A pure tone's spectral line becomes a sin(Nω/2)/sin(ω/2) shape with main-lobe width 4π/N and sidelobes. Longer records give narrower main lobes (better resolution); tapered windows trade a wider main lobe for lower sidelobes.

Formulas

• X(e^(jω)) = Σ x[n] e^(−jωn) (n from −∞ to ∞) — analysis equation.
• x[n] = (1/2π) ∫ over any 2π interval of X(e^(jω)) e^(jωn) dω — synthesis equation.
• Σ |x[n]|² = (1/2π) ∫ over 2π of |X(e^(jω))|² dω — Parseval.
• aⁿ u[n] ↔ 1/(1 − a e^(−jω)), |a| < 1.
• δ[n − n0] ↔ e^(−jωn0).
• rectangular pulse, 1 for 0 ≤ n ≤ N − 1 ↔ e^(−jω(N−1)/2) · sin(Nω/2)/sin(ω/2).
• h[n] = sin(ωc n)/(πn) (with h[0] = ωc/π) — ideal low-pass filter of cut-off ωc.
• ω = 2πf/fs = ΩTs — link between digital and analogue frequency.

Symbols: ω digital frequency (rad/sample); f analogue frequency (Hz); fs sampling rate (Hz); Ω analogue angular frequency (rad/s); Ts = 1/fs (s); a real or complex constant with |a| < 1; N length in samples; ωc cut-off (rad/sample).

Worked examples

Example 1 (standard). For x[n] = (0.5)ⁿ u[n], find |X| at ω = 0 and ω = π, and say what kind of spectrum this is.

1. X(e^(jω)) = 1/(1 − 0.5 e^(−jω)).
2. At ω = 0: e^(−j0) = 1, X = 1/(1 − 0.5) = 2.
3. At ω = π: e^(−jπ) = −1, X = 1/(1 + 0.5) = 0.667.
4. Check with the shortcuts: Σ x[n] = 1/(1 − 0.5) = 2 ✓; Σ (−1)ⁿ (0.5)ⁿ = 1/(1 + 0.5) = 0.667 ✓.
5. |X| = 2 at DC and 0.667 at ω = π — a low-pass spectrum (a negative a would give a high-pass one).

Example 2 (GATE level). x[n] = {1, 2, 1} for n = 0, 1, 2. Find X(e^(jω)), its value at ω = 0, π/2, π, and verify Parseval.

1. X = 1 + 2e^(−jω) + e^(−j2ω) = e^(−jω)(e^(jω) + 2 + e^(−jω)) = e^(−jω)(2 + 2cos ω).
2. |X| = 2 + 2cos ω (never negative), phase −ω — linear phase, because x is symmetric about n = 1.
3. |X(e^(j0))| = 4, |X(e^(jπ/2))| = 2, |X(e^(jπ))| = 0 (low-pass, with a null at the highest frequency).
4. Parseval: Σ x² = 1 + 4 + 1 = 6; (1/2π) ∫ (2 + 2cos ω)² dω = (1/2π) ∫ (4 + 8cos ω + 4cos² ω) dω = (1/2π)(8π + 0 + 4π) = 6 ✓.
5. X(e^(jω)) = e^(−jω)(2 + 2cos ω): magnitudes 4, 2 and 0 at ω = 0, π/2, π; energy 6.

Common mistakes

• Treating the DTFT as discrete — it is continuous in ω; the DFT is the discrete one.
• Forgetting the 2π periodicity, for example looking for a feature at ω = 1.5π instead of −0.5π.
• Mixing ω (rad/sample) with Ω (rad/s). Convert with ω = ΩTs.
• Sign errors in e^(−jωn): e^(−jπ) = −1, e^(−j3π/2) = +j.
• Claiming that zero-padding improves resolution. It only samples the same DTFT more finely; resolution needs a longer record.
• Using the DTFT of aⁿ u[n] for |a| ≥ 1 — it does not converge.

For GATE IN

Expect: evaluating the DTFT of a short sequence at ω = 0, π/2 or π; Parseval or x[0] = (1/2π)∫X dω used to evaluate an integral; identifying low-pass/high-pass behaviour or linear phase from a short impulse response; ideal-filter impulse responses; and conversion between analogue and digital frequency. Practise the e^(−jω) factoring trick for symmetric sequences.

Quick check

1. What is the DTFT of δ[n − 2]?
2. x[n] = {1, −1} (n = 0, 1). Is it low-pass or high-pass?
3. A 1 kHz tone sampled at 8 kHz — digital frequency?
4. (1/2π) ∫ X(e^(jω)) dω over one period equals what?
5. Period of every DTFT? Answers: 1. e^(−j2ω). 2. High-pass: X(0) = 0, |X(π)| = 2. 3. ω = 2π × 1/8 = π/4 rad/sample. 4. x[0]. 5. 2π.