What is fast Fourier transform?

Question

I was asked a question about where I needed to use it, but I have no idea what it is. So, in plain English, Fast Fourier Transform, and how can I use it to search for a derivative of a function, given its (x, y) value as an input?

How would you implement it?

EDIT:
I ask about this because, given the sequence of values ​​(x, y), I needed to calculate what the function looks like, get it and find the number of times it constantly changes (i.e. (0, 1), (1, 2 ) is considered one) or does not change at all (0, 5), (1, 5) is also taken into account as one change).

Answer 1

As for the first part of the question, the former physics professor Bartosz Milewski has a very nice explanation of what FFT is and how it works.

In addition, it is worth mastering the Fourier transform in one day .

In English (?)

Say you have sound from the speaker.

Then you tune, let's get a round number here, 1024 harmonic oscillators that resonate in specific frequency ranges.

Play a sound, say, a second.

Oscillators begin to resonate with the sound coming from the speaker. After that second, you read how each oscillator resonates. As a result, you get a discrete Fourier transform, that is, you get a diagram of how each of the frequency ranges contributed to the sound coming from the speaker.

Instead of visualizing sound as the amount of air pressure caused by the waveform, changing the time intervals, you visualized it as a series of intensities of frequency ranges.

Of course, explaining DFT, some speakers are not very suitable, since you have to work with sampled input. Thus, in this case, 1024 digital “generators” should actually be measured after 1/44 of a second, given that sound is sampled at a speed of 44 kHz.

Fast Fourier Transform is an algorithm for performing a discrete Fourier transform, which is pretty easy for computers to run on an incoming signal. It imposes some restrictions that you have to work with in your implementation (for example, the number of samples must be 2), because it uses some smart tricks to drastically reduce the number of calculations performed in the sample buffer.

In fact, there is no need to go deeper, because the two links I gave give a fairly clear explanation. And note that it is impossible to move from theory to implementation without knowing the mathematics behind it.

I hope this introduction makes sense!

Answer 2

Fourier analysis is a family of mathematical methods based on the decomposition of signals into sinusoids. Discrete Fourier Transform (DFT) is a member of the family used with digitized signals.

From tungsten

Fast Fourier Transform (FFT) is a discrete Fourier transform algorithm that reduces the number of calculations needed for N points from 2N ^ 2 to 2NlgN, where lg is the logarithm of base-2. If the transformed function is not harmoniously related to the sampling rate, the FFT response looks like a sinc function (although the built-in power is still correct). Smoothing (also known as leakage) can be reduced by apodization using the apodization function. However, a decrease in smoothing occurs due to the expansion of the spectral response.

He usually studies in signal processing courses. So you probably needed to work on image / sound processing. :)

Watch these lectures from Stanford Engineering: here

In principle, DFT

And the pseudo-code of the Cooley-Tukey FFT algorithm is as follows:

Y0,...,N−1 ← ditfft2(X, N, s): DFT of (X0, Xs, X2s, ..., X(N-1)s): if N = 1 then Y0 ← X0 trivial size-1 DFT base case else Y0,...,N/2−1 ← ditfft2(X, N/2, 2s) DFT of (X0, X2s, X4s, ...) YN/2,...,N−1 ← ditfft2(X+s, N/2, 2s) DFT of (Xs, Xs+2s, Xs+4s, ...) for k = 0 to N/2−1 combine DFTs of two halves into full DFT: t ← Yk Yk ← t + exp(−2πi k/N) Yk+N/2 Yk+N/2 ← t − exp(−2πi k/N) Yk+N/2 endfor endif 

(Shamelessly copied from http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm )

In addition, you can watch

• http://www.fftw.org/download.html
• http://www.developer.com/java/other/article.php/3457251
• http://www.dspguide.com/pdfbook.htm

Answer 3

Fast Fourier Transform (FFT) is an algorithm for computing the Discrete Fourier Transform (DFT). You can think of DFT as a way of representing a sampling signal as a sum of sinusoids. Since the sine derivative is simple, you can evaluate the derivative of the signal sample by finding the derivative of your DFT.

This is a big topic in signal processing , and I recommend buying an introductory book or taking a course to learn more.

Refresh . In more understandable English, this is a way to look at a sequence of numbers as the sum of the waves.

Answer 4

The simplest explanation I can think of: Given a WAV file containing a tone, the FFT can tell you about the frequency of that tone. But it can also be used for more interesting things.

Answer 5

this can solve your problem: Fast Fourier transform on Wikipedia

They even have links to implemented algorithms.

Basically, this is a way to make a digital Fourier diagram numerically, which allows the computer to do this.