Page plan · 15 pages

Written for: Engineering and computer science students

1. 1

   Cooley and Tukey, 1965: the fast Fourier transform

   • This deck reads the 1965 Cooley-Tukey paper on computing Fourier transforms by machine.
   • The paper introduced the algorithm now known as the fast Fourier transform (FFT).
   • We read it as engineers: what was the cost, what was the idea, and why did it spread?
2. 2

   Reading path: cost, idea, method, results

   • First, the cost problem: why the direct discrete Fourier transform is expensive.
   • Second, the core idea: split one long transform into shorter ones.
   • Third, the method: halving repeatedly and the butterfly operation.
   • Last, results, trade-offs and the applications that followed.
3. 3

   Why the direct DFT costs N² operations

   • The DFT turns N input samples into N output frequency values.
   • Each output is a sum over all N inputs, weighted by complex exponentials.
   • N outputs times N terms each gives on the order of N² complex multiply-adds.
   • Doubling the signal length therefore roughly quadruples the work.
4. 4

   Limits of earlier shortcuts

   • Earlier shortcuts exploited symmetries in the data or special sample layouts.
   • Such tricks helped for particular cases but did not change the growth rate for general N.
   • Hand and early machine computation stayed limited to short records.
   • A general method with much lower growth was still missing.
5. 5

   The key insight: split one long transform into short ones

   • Key insight: a transform of length N can be built from smaller transforms.
   • Split the samples into two groups, such as even-indexed and odd-indexed ones.
   • Each half needs a DFT of length N/2, which costs far less than one of length N.
   • The two partial results are then combined with a small number of extra operations.
6. 6

   The method: repeated halving when N is a power of two

   • When N is a power of two, the split can be applied again and again.
   • Each halving cuts the problem size until only length-2 transforms remain.
   • This gives log₂ N stages of work.
   • Each stage costs on the order of N operations, so the total is about N log₂ N.
7. 7

   Implementing the butterfly operation

   • The butterfly takes two values and produces two new values.
   • One input is multiplied by a complex twiddle factor, a root of unity.
   • The sum and the difference of the two terms form the outputs.
   • The same small operation is repeated throughout, which makes it easy to code.
8. 8

   Inside one stage: N/2 butterflies

   • Each stage applies N/2 butterflies, one per pair of values.
   • Pairs within a stage are independent of each other.
   • Running log₂ N stages of N/2 butterflies gives the overall operation count.
   • Each butterfly uses one complex multiplication and two additions.
9. 9

   Advantages: fewer operations and in-place computation

   • The main advantage is far fewer operations than the direct N² approach.
   • The butterfly outputs can overwrite its inputs, so computation can run in place.
   • In-place work needs little extra storage beyond the data array.
   • Both gains mattered on the small-memory machines of the 1960s.
10. 10

    Memory and speed trade-offs

    • In-place computation saves memory but leaves outputs in scrambled, bit-reversed order.
    • Reordering is needed to read results in natural frequency order.
    • Twiddle factors can be computed once and stored, or recomputed, trading memory for speed.
    • The simplest form assumes N is a power of two, which limits flexibility.
11. 11

    How the paper set up its tests

    • The paper tested the algorithm by running it on sample signals.
    • Results were checked against the direct DFT definition for correctness.
    • Run time was the quantity of interest, compared with the direct computation.
    • Test lengths were chosen to suit the power-of-two structure.
12. 12

    What the tests on sample signals showed

    • The tests confirmed that the fast method reproduces the direct DFT results.
    • They showed the saving in computation growing as the signal length grew.
    • This supported the claim that the method is practical, not only elegant.
13. 13

    Applications that followed: spectra, filtering, imaging

    • Spectral analysis became practical for much longer records.
    • Filtering could be done in the frequency domain at low cost.
    • Imaging and other multidimensional data could use fast transforms along each axis.
    • Cheaper transforms made frequency-domain methods a routine engineering tool.
14. 14

    N² against N log₂ N: the speed-up in numbers

    • At N = 64, the direct DFT needs 4,096 operations against 384 for the FFT.
    • At N = 1024, the counts are 1,048,576 against 10,240.
    • At N = 16384, they are 268,435,456 against 229,376.
    • The gap widens as N grows, because N² outgrows N log₂ N.

    Table: Operation counts for the direct DFT and the FFT. Source: Computing the DFT, CSE 616 lecture notes (slide 'Significance') · checked 2026-10-10

15. 15

    Why one 1965 paper changed signal processing

    • It cut the cost of a core operation from N² to N log₂ N.
    • The idea was general, simple to program and memory-friendly.
    • Lower cost opened new uses of frequency analysis across engineering.
    • For students, it shows how restructuring an algorithm can beat faster hardware.