Researched
Fast Fourier Transform
Cooley and Tukey's algorithm (1965) computes Fourier transforms thousands of times faster and makes digital signal processing practical.
Open in the interactive tree →It cuts the work from N squared to about N log N operations (Gauss had found a version around 1805). The FFT sits inside Wi-Fi and mobile radio, audio and image compression, MRI and radar.
Prerequisites
Unlocks
- CT and MRI scanning1971MRI images are reconstructed from Fourier-transformed signals
- Mobile Networks (1G to 4G)19834G and later mobile standards use OFDM, implemented with the FFT
- Wi-Fi (IEEE 802.11)1997Wi-Fi's OFDM modulation is computed with fast Fourier transforms