  # Introduction to DSP - frequency: Fourier transforms

 Jean Baptiste Fourier showed that any signal or waveform could be made up just by adding together a series of pure tones (sine waves) with appropriate amplitude and phase. This is a rather startling theory, if you think about it. It means, for instance, that by simply turning on a number of sine wave generators we could sit back and enjoy a Beethoven symphony. Of course we would have to use a very large number of sine wave generators, and we would have to turn them on at the time of the Big Bang and leave them on until the heat death of the universe. Fourier's theorem assumes we add sine waves of infinite duration. The diagram shows how a square wave can be made up by adding together pure sine waves at the harmonics of the fundamental frequency. Any signal can be made up by adding together the correct sine waves with appropriate amplitude and phase. The Fourier transform is an equation to calculate the frequency, amplitude and phase of each sine wave needed to make up any given signal. The Fourier Transform (FT) is a mathematical formula using integrals The Discrete Fourier Transform (DFT) is a discrete numerical equivalent using sums instead of integrals The Fast Fourier Transform (FFT) is just a computationally fast way to calculate the DFT The Discrete Fourier Transform involves a summation: Where j is the square root of minus one (defined as a number whose sole property is that its square is minus one). Note that the DFT and the FFT involve a lot of multiplying and then accumulating the result - this is typical of DSP operations and is called a 'multiply/accumulate' operation. It is the reason that DSP processors can do multiplications and additions in parallel. 