Skip to content

Chapter 13

The discrete Fourier transform

Six lessons in Part V, Discrete-time Fourier analysis. Read them in order, or start anywhere: a prerequisite is a link, never a gate.

Start with 13.1
0 of 6 read4 on the essential pathabout 117 minutes

Lessons in this chapter

Spectrum strip: the size curve |X| of x = 4, 3, 2, 1, from 10 at 0 down to 2 at π and back; N = 3 filled dots on it, spaced 2π/3 = 0.67π rad/sample, with heights 10, 2.65 and 2.65. Time panel: copies of x as open circles every 3 samples, and their sum x̃ as filled squares. The copies overlap: samples where two or more copies add are hatched, for example n = 0, 3 and 6. One period, n = 0 to 2, reads 5, 3 and 2.Spectrum strip: the size curve |X| of x = 4, 3, 2, 1, from 10 at 0 down to 2 at π and back; N = 3 filled dots on it, spaced 2π/3 = 0.67π rad/sample, with heights 10, 2.65 and 2.65. Time panel: copies of x as open circles every 3 samples, and their sum x̃ as filled squares. The copies overlap: samples where two or more copies add are hatched, for example n = 0, 3 and 6. One period, n = 0 to 2, reads 5, 3 and 2.

Lesson 1 Essential20 minYou are hereRead

Sampling the spectrum

Keep N equally spaced values of a spectrum and see that they describe the signal repeated every N samples. Find the shortest N that loses nothing.

Samples x[n] = 1.5, 0.35, 0, −0.35, −1.5, −0.35, 0, 0.35 for n = 0 to 7. Chain for bin 4: 8 of 8 arrows added nose to tail, sum so far 0.00. Bars: bin 0 0.00, bin 1 4.00, bin 2 0.00, bin 3 2.00, bin 4 0.00, bin 5 2.00 (mirror of 3), bin 6 0.00 (mirror of 2), bin 7 4.00 (mirror of 1).Samples x[n] = 1.5, 0.35, 0, −0.35, −1.5, −0.35, 0, 0.35 for n = 0 to 7. Chain for bin 4: 8 of 8 arrows added nose to tail, sum so far 0.00. Bars: bin 0 0.00, bin 1 4.00, bin 2 0.00, bin 3 2.00, bin 4 0.00, bin 5 2.00 (mirror of 3), bin 6 0.00 (mirror of 2), bin 7 4.00 (mirror of 1).

Lesson 2 Essential25 minYou are hereRead

The DFT

Turn N samples into N bins, each one the signal multiplied by a turning probe and added up, then read bins as hertz, mirrors and resolution.

Shift n₀ = 4: inside the box, n = 0 to 7, the samples read 1, 0, 0, 0, 5, 4, 3, 2, with faint copies outside it. Eight dials, k = 0 to 7, turned by 0°, −180°, −360°, −540°, −720°, −900°, −1080°, −1260°. Sizes under the dials: 15.00, 9.04, 3.61, 2.87, 3.00, 2.87, 3.61, 9.04.Shift n₀ = 4: inside the box, n = 0 to 7, the samples read 1, 0, 0, 0, 5, 4, 3, 2, with faint copies outside it. Eight dials, k = 0 to 7, turned by 0°, −180°, −360°, −540°, −720°, −900°, −1080°, −1260°. Sizes under the dials: 15.00, 9.04, 3.61, 2.87, 3.00, 2.87, 3.61, 9.04.

Lesson 3 Essential22 minYou are hereRead

Properties of the DFT

Shift a sequence round a ring and watch each DFT bin turn without changing size; mirror it to conjugate the DFT; meet circular convolution.

Two stem plots against sample n, 0 to 9. Linear output y = x * h: 1, 3, 6, 9, 7, 4. From the DFT product, N = 4 points: 8, 7, 6, 9, total 30. The last 2 samples wrap back by 4 and add on, at n = 0 and n = 1 (hatched).Two stem plots against sample n, 0 to 9. Linear output y = x * h: 1, 3, 6, 9, 7, 4. From the DFT product, N = 4 points: 8, 7, 6, 9, total 30. The last 2 samples wrap back by 4 and add on, at n = 0 and n = 1 (hatched).

Lesson 4 Essential16 minYou are hereRead

Circular vs linear convolution

See why multiplying DFTs gives a convolution whose tail wraps onto its start, and how zero-padding stops it.

An 8 by 8 grid of unit arrows: the entry in row k, column n points at angle minus 2π k n / 8. Row 0 points right everywhere; row 4 alternates right and left. The column x = 1, 2, 3, 4, 3, 2, 1, 0. Results so far: X[0] = 16.00, X[1] = −4.83 − 4.83j, X[2] = 0.00, X[3] = 0.83 − 0.83j, X[4] = 0.00, X[5] = 0.83 + 0.83j, X[6] = 0.00, X[7] = −4.83 + 4.83j.An 8 by 8 grid of unit arrows: the entry in row k, column n points at angle minus 2π k n / 8. Row 0 points right everywhere; row 4 alternates right and left. The column x = 1, 2, 3, 4, 3, 2, 1, 0. Results so far: X[0] = 16.00, X[1] = −4.83 − 4.83j, X[2] = 0.00, X[3] = 0.83 − 0.83j, X[4] = 0.00, X[5] = 0.83 + 0.83j, X[6] = 0.00, X[7] = −4.83 + 4.83j.

Lesson 520 minYou are hereRead

The DFT as a matrix

Write the DFT as one matrix times one column, see why its rows cancel, and see why a circular convolution becomes a bin-by-bin product.

Stem plot of value against sample n, −8 to 23: x as dots at n = 0 to 7 and 16 to 23, its mirror image as squares at n = −8 to −1 and 8 to 15. Dotted seams at n = 0, 8 and 16; at each one the values meet, 0.90 with 0.90 and 0.20 with 0.20: no jump.Stem plot of value against sample n, −8 to 23: x as dots at n = 0 to 7 and 16 to 23, its mirror image as squares at n = −8 to −1 and 8 to 15. Dotted seams at n = 0, 8 and 16; at each one the values meet, 0.90 with 0.90 and 0.20 with 0.20: no jump.

Lesson 614 minYou are hereRead

The discrete cosine transform

See why the DFT's repetition makes a jump at every seam, how mirroring the signal removes it, and why that lets a few cosines rebuild a smooth signal.

After this chapter

Where to go next.

The chapters either side, and the rest of Part V in the library.

Phasorium
LibraryEvery lesson, in order

Parts

About Phasorium
Look