Skip to content

Chapter 14

The fast Fourier transform

Four 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 14.1
0 of 4 read2 on the essential pathabout 76 minutes

Lessons in this chapter

Samples x[n] = 1, 2, 0, −1, 0, 1, 2, 1 for n = 0 to 7 as stems; even samples marked with dots, odd samples with squares. Complex plane, k = 3: arrow X_ev[3] = 1−2j, then the product W₈ to the 3 times X_od[3] = −2.12+0.71j nose to tail, ending at X[3] = −1.12−1.29j (ring); flipped, it ends at X[7] = 3.12−2.71j (square). Finished outputs: X[0] = 6, X[4] = 0, X[1] = 3.12+2.71j, X[5] = −1.12+1.29j, X[2] = −1−3j, X[6] = −1+3j. Multiplies so far: 36.Samples x[n] = 1, 2, 0, −1, 0, 1, 2, 1 for n = 0 to 7 as stems; even samples marked with dots, odd samples with squares. Complex plane, k = 3: arrow X_ev[3] = 1−2j, then the product W₈ to the 3 times X_od[3] = −2.12+0.71j nose to tail, ending at X[3] = −1.12−1.29j (ring); flipped, it ends at X[7] = 3.12−2.71j (square). Finished outputs: X[0] = 6, X[4] = 0, X[1] = 3.12+2.71j, X[5] = −1.12+1.29j, X[2] = −1−3j, X[6] = −1+3j. Multiplies so far: 36.

Lesson 1 Essential18 minYou are hereRead

The FFT

Split the samples into even and odd, reuse each product twice, and repeat. Watch an 8-point DFT shrink from 64 multiplies to 12.

Schematic of an FFT of length N = 31, prime: 31 sample rows. One stage column: radix 31, one box of 31 rows. Work 961 (direct 961).Schematic of an FFT of length N = 31, prime: 31 sample rows. One stage column: radix 31, one box of 31 rows. Work 961 (direct 961).

Lesson 222 minYou are hereRead

More FFT algorithms

Split a DFT by any factor of N, rescue prime lengths with Bluestein's chirp, pack two real signals into one FFT, and compare what libraries choose.

Real multiplies against the length of each signal N, both axes logarithmic, N from 4 to 4096. A dashed line for direct, N squared, and a solid staircase for the FFT route, drawn up to the current N. N = 4096: direct 16.8 million, FFT route 671 744 with an FFT of 8192. Cheaper: FFT route.Real multiplies against the length of each signal N, both axes logarithmic, N from 4 to 4096. A dashed line for direct, N squared, and a solid staircase for the FFT route, drawn up to the current N. N = 4096: direct 16.8 million, FFT route 671 744 with an FFT of 8192. Cheaper: FFT route.

Lesson 3 Essential16 minYou are hereRead

Fast convolution

Convolve by multiplying FFTs, find the lengths where that is cheaper than flip and slide, and cut a long signal into blocks.

Plot of the size of the running total against sample n, 0 to 204, for a 770 Hz input. Up to sample n = 204: loop k = 20 (780.5 Hz), a solid line ending in a ring, is at 91.18; loop k = 18 (702.4 Hz), a dashed line ending in a square, is at 13.65.Plot of the size of the running total against sample n, 0 to 204, for a 770 Hz input. Up to sample n = 204: loop k = 20 (780.5 Hz), a solid line ending in a ring, is at 91.18; loop k = 18 (702.4 Hz), a dashed line ending in a square, is at 13.65.

Lesson 420 minYou are hereRead

Goertzel and the chirp z-transform

Compute one DFT bin with a loop that rotates and adds, decode phone keys with eight such loops, then zoom into a narrow band of the spectrum.

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