Comments

You must log in or register to comment.

SuperBelgian t1_iye4ji3 wrote

The Fast Fourier Transform is an algoritm to do a Fourier Transform.

A Fourier Transform transforms data between de time and frequency domain, which gives anoter perspective on the data.

Imagine a simple trafic light:

In the time domain, the traffic light is first Green, then Orange, then Red in a repeating cycle.

At any given moment in time, you only see a single color, so looking in the time domain doesn't tell you anything about which and how many colors exist in the sequence.

By transforming this sequence into a frequency domain (the frequency/wavelength of the light), you will see 3 distinct peaks corresponding to Green, Orange, and Red.
In the frequency domain, you can imediately tell which collors exists, but you don't have any information about the sequence in time for these colors.

FFT is used for about everything:
In sound it detects individual notes in chords.
In images, it is used to detect all colors and intensities.
In data, it is used to detect patterns.
Etc...

5

capilot t1_iye18b2 wrote

The Fourier transform is a way to analyze a waveform and determine the correct combination of pure sine waves and cosine waves that can be combined to re-create the original wave. Knowing the composition of an arbitrary wave in this way can enable all sorts of analysis and processing, including advanced signal processing.

The problem is that it's highly compute intensive, involving a sequence of integrals and so forth. In most cases, there are other analytic methods that are more practical than Fourier transform because of the work required.

In 1964, the Fast Fourier Transform was invented. It's basically a computational "trick" that replaces all those integrals with simple shifts and adds and subtracts. All of a sudden it became practical to use Fourier transforms in all sorts of ways that weren't practical before.

That video linked by /u/croninsiglos looks really good, off to watch it now.

4