What is the Fast Fourier Transform? [closed]_问答_开发者

Closed. This question needs to be more focused. It is not currently accepting answers.

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 4 years ago.

Improve this question

I was asked an interview question where I needed to use it but I have no idea what it is.

So in plain english what is the Fast Fourier Transform and h开发者_开发技巧ow can I use it to find the derivative of a function given its (x, y) values as input?

How would you implement it?

EDIT:

I am asking this because given a sequence of (x, y) values I needed to calculate how the function looks like, derive it and find the number of times it is constantly changing (that is, (0, 1), (1, 2) is counted as one) or does not change at all (0, 5), (1, 5) is also counted as one change).

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

Also, Mastering The Fourier Transform in One Day is worth reading as well.

In English (?)

Say you have a sound coming from the speaker.

You then set up, let's get a nice round number here, 1024 harmonic oscillators that resonate to specific frequency ranges.

Play the sound for, say, a second.

Oscillators begin to resonate to the sound coming from the speaker. After the said second you read how much every oscillator is resonating. As a result you get a discrete fourier transform, meaning you get a chart of how much each of the frequency ranges contributed to the sound coming from the speaker.

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

Of course in explaining the DFT, the speakers part is not really appropriate since you have to work on sampled input. So in this case the 1024 digital "oscillators" should actually be measured after 1/44th of a second, given the audio is sampled at the rate of 44kHz.

Fast Fourier Transform is an algorithm to perform a Discrete Fourier Transform that's pretty easy for computers to run on an incoming signal. It imposes some constraints you have to work with in your implementation (e.g. the number of samples has to be a power of 2), because it uses some clever tricks to drastically reduce the amount of calculation performed on the sample buffer.

There is really no need to go deeper, since the two links I gave provide a pretty clear explanation. And note that it's impossible to go from theory to implementation without knowing the math behind it.

I hope this introduction makes some sense!

Fourier analysis is a family of mathematical techniques, all based on decomposing signals into sinusoids. The discrete Fourier transform (DFT) is the family member used with digitized signals.

From Wolfram,

The fast Fourier transform (FFT) is a discrete Fourier transform algorithm which reduces the number of computations needed for N points from 2N^2 to 2NlgN, where lg is the base-2 logarithm. If the function to be transformed is not harmonically related to the sampling frequency, the response of an FFT looks like a sinc function (although the integrated power is still correct). Aliasing (also known as leakage) can be reduced by apodization using an apodization function. However, aliasing reduction is at the expense of broadening the spectral response.

It's usually taught as a part of Signal Processing courses. So, you must have been needing to work on some image/sound processing. :)

See these lectures from Stanford Engineering: here

Basically, DFT is

What is the Fast Fourier Transform? [closed]

And Cooley-Tukey FFT algorithm's pseudo code 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)

Also, you may wanted to look into

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

The fast Fourier transform (FFT) is an algorithm for calculating the discrete Fourier transform (DFT). You could think of the DFT as a way of representing a sampled signal as a sum of sinusoids. Since the derivative of a sine is simple, you can estimate the derivative of a signal sample by finding the derivative of its DFT.

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

Update: In plainer English, it's a way of looking at a sequence of numbers as a sum of waves.

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

this might solve your problem: Fast Fourier transform on wikipedia

They even have links to implemented algorithms.

Basically it's a way to do a Fourier Tranform numerically, which allows a computer to do it.