Chapitre 3

For high-dimensional signals, this complexity implies that the Discrete Fourier Transform (DFT) is quite slow, which is why the Fourier transform found limited application primarily in a theoretical context until the 1960s. Fortunately, in 1965, Cooley and Tukey leveraged hidden symmetries in the DFT to devise a rapid computation algorithm for the DFT, known as the Fast Fourier Transform algorithm (FFT).

In particular, FFT is very effective when the size of the signals is a power of 2. This explains why the typical format of digital images is 512 or 1024, as these sizes allow for efficient manipulation using FFT."

The development of FFT is considered one of the greatest scientific advances of the 20th century, as it enabled the practical application of the Fourier transform in an enormous number of fields [8].