Prev
Unit 6 · Lesson 6-1
The Discrete-Time Fourier Transform
1h 50m1300 XP
Next

The Discrete-Time Fourier Transform

The spectrum of a sequence, its period of 2π, normalised frequency, FIR frequency responses, moving averages and the DTFT of samples

2020 — the weekend effect
In 2020 millions of people check COVID-19 dashboards every day, and the daily numbers misbehave. Reported cases sag at every weekend and surge after it; in the United States new cases tend to peak on Fridays and deaths on Tuesdays or Wednesdays, and similar weekly cycles appear in many other countries. The virus keeps no calendar — testing sites, laboratories and reporting offices do (Dear Pandemic). The standard advice is a 7-day rolling average, and the weekly wobble vanishes as if it had never been there. It is not luck. A 7-point moving average is a filter, and its frequency response is exactly zero at one cycle per week and at every harmonic of it. This lesson builds the tool that shows why: the Fourier transform of a sequence.
A sequence x[n]x[n] has no time axis in seconds, only an index. Its frequencies are measured in radians per sample, written Ω\Omega: the sequence ejΩne^{j\Omega n} advances its phase by Ω\Omega from one sample to the next. The discrete-time Fourier transform (DTFT) says how much of each Ω\Omega a sequence contains.
X(ejΩ)=∑n=−∞∞x[n] e−jΩn,x[n]=12π∫−ππX(ejΩ) ejΩn dΩX(e^{j\Omega}) = \sum_{n=-\infty}^{\infty} x[n]\,e^{-j\Omega n}, \qquad x[n] = \frac{1}{2\pi}\int_{-\pi}^{\pi} X(e^{j\Omega})\,e^{j\Omega n}\,d\Omega

The DTFT and its inverse. The sum makes a continuous, 2π-periodic function of Ω from a list of numbers; the integral over one period rebuilds the list.

💡A period of 2π, and normalised frequency
Because nn is an integer, e−j(Ω+2π)n=e−jΩne^{-j(\Omega + 2\pi)n} = e^{-j\Omega n}: the DTFT repeats every 2π2\pi. Only −π<Ω≤π-\pi < \Omega \le \pi carries information, and for a real sequence only 0≤Ω≤π0 \le \Omega \le \pi. The fastest oscillation a sequence can show is (−1)n=ejπn(-1)^n = e^{j\pi n}, at Ω=π\Omega = \pi. For samples taken at rate fsf_s, Ω=2πf/fs=ωT\Omega = 2\pi f/f_s = \omega T — normalised frequency. Ω=π\Omega = \pi is the Nyquist frequency, and the 2π2\pi-periodicity is aliasing (Lesson 5-2) seen from the sequence's side. Indeed, if x[n]=xc(nT)x[n] = x_c(nT), X(ejΩ)=1T∑k=−∞∞Xc ⁣(j Ω−2πkT),X(e^{j\Omega}) = \frac1T\sum_{k=-\infty}^{\infty} X_c\!\left(j\,\frac{\Omega - 2\pi k}{T}\right), the periodic spectrum of Lesson 5-1 with its frequency axis divided by fsf_s.
💡The frequency response of an FIR filter
A filter that forms each output from the current and past inputs, y[n]=∑k=0M−1bk x[n−k]y[n] = \sum_{k=0}^{M-1} b_k\,x[n-k], has the impulse response h[k]=bkh[k] = b_k and the frequency response H(ejΩ)=∑k=0M−1bk e−jΩk.H(e^{j\Omega}) = \sum_{k=0}^{M-1} b_k\,e^{-j\Omega k}. Feed it ejΩne^{j\Omega n} and out comes H(ejΩ) ejΩnH(e^{j\Omega})\,e^{j\Omega n}: the same sequence, scaled and shifted in phase — the eigenfunction property of Lesson 3-1, for sequences. scipy.signal.freqz evaluates HH on any grid of frequencies.
Derivation
The moving average
An MM-point moving average has bk=1/Mb_k = 1/M. Summing the geometric series,
H(ejΩ)=1M∑k=0M−1e−jΩk=1M 1−e−jΩM1−e−jΩ.H(e^{j\Omega}) = \frac1M\sum_{k=0}^{M-1} e^{-j\Omega k} = \frac1M\,\frac{1 - e^{-j\Omega M}}{1 - e^{-j\Omega}} .
Take e−jΩM/2e^{-j\Omega M/2} out of the numerator and e−jΩ/2e^{-j\Omega/2} out of the denominator:
H(ejΩ)=e−jΩ(M−1)/2 sin⁡(MΩ/2)Msin⁡(Ω/2).H(e^{j\Omega}) = e^{-j\Omega(M-1)/2}\,\frac{\sin(M\Omega/2)}{M\sin(\Omega/2)} .
The magnitude is zero wherever MΩ/2M\Omega/2 is a multiple of π\pi but Ω/2\Omega/2 is not: at Ω=2πk/M\Omega = 2\pi k/M for k=1,…,M−1k = 1, \dots, M - 1. The phase, −Ω(M−1)/2-\Omega(M - 1)/2, is linear: every frequency is delayed by the same (M−1)/2(M - 1)/2 samples (Lesson 4-2).
📐Seven days
For daily data and M=7M = 7, the zeros fall at Ω=2π/7\Omega = 2\pi/7, 4π/74\pi/7 and 6π/76\pi/7 radians per day: periods of 7, 3.5 and 2.33 days. A weekly reporting pattern, whatever its shape, is a sum of exactly these frequencies, so the average removes it completely. Slow changes pass almost untouched: a 30-day wave keeps 91 % of its amplitude, a yearly one 99.9 %. The price is time. A trailing average — each day with the six before it — lags the trend by (7−1)/2=3(7 - 1)/2 = 3 days. A centred average has no lag, but it needs three days of the future, so the last three days of any centred curve are always missing or provisional.
You see, but you do not observe.
– Sherlock Holmes in Arthur Conan Doyle, "A Scandal in Bohemia" (1891), quoted on Wikiquote
🕰A meteorologist's smoothing
The Hann window of Lesson 6-3 is named after the Austrian meteorologist Julius von Hann, who smoothed weather records with a three-term weighted average (Hann function). The weights 14,12,14\tfrac14, \tfrac12, \tfrac14 give H(ejΩ)=e−jΩcos⁡2(Ω/2)H(e^{j\Omega}) = e^{-j\Omega}\cos^2(\Omega/2): unit gain for slow changes, and a zero at Ω=π\Omega = \pi that wipes out day-to-day alternation.
⚠Every causal smoother lags
A filter that uses only the past cannot respond to a change before it happens. The 7-day trailing average delays everything by three days; heavier smoothing delays more. When a smoothed curve turns, the real turn happened earlier — a fact worth remembering whenever a dashboard, a stock chart or a flight instrument shows filtered data.
💡Where you will use this
Sampling the DTFT at NN frequencies is the DFT of Lesson 6-2. FIR filter design (Lesson 9-1) is the art of shaping H(ejΩ)H(e^{j\Omega}), and the z-transform (Unit 8) generalises the DTFT as the Laplace transform generalises Fourier's. Moving averages are everywhere: sensor smoothing, economic indicators, and the decimation filters of Lesson 5-3.
📚Further reading
  • Oppenheim and Willsky, Signals and Systems, sections 5.1–5.4 — the discrete-time Fourier transform and its properties.
  • Alan V. Oppenheim and Ronald W. Schafer, Discrete-Time Signal Processing (3rd ed., Pearson, 2010), chapter 2.
  • Why are COVID-19 numbers lower on the weekends? — the weekly reporting cycle, explained.
↓But there is a problem
The DTFT is a continuous function of frequency, but a computer can evaluate only a finite list of frequencies — and done the obvious way, NN frequencies of an NN-sample record cost N2N^2 multiplications. For a million samples, that is a trillion. In 1963, at a meeting of President Kennedy's science advisers about detecting Soviet nuclear tests, a statistician started sketching a way around it.