What is Fast fourier transform: Definition and 34 Discussions

A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. The DFT is obtained by decomposing a sequence of values into components of different frequencies. This operation is useful in many fields, but computing it directly from the definition is often too slow to be practical. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors. As a result, it manages to reduce the complexity of computing the DFT from



O

(

N

2


)



{\displaystyle O\left(N^{2}\right)}
, which arises if one simply applies the definition of DFT, to



O
(
N
log

N
)


{\displaystyle O(N\log N)}
, where



N


{\displaystyle N}
is the data size. The difference in speed can be enormous, especially for long data sets where N may be in the thousands or millions. In the presence of round-off error, many FFT algorithms are much more accurate than evaluating the DFT definition directly or indirectly. There are many different FFT algorithms based on a wide range of published theories, from simple complex-number arithmetic to group theory and number theory.
Fast Fourier transforms are widely used for applications in engineering, music, science, and mathematics. The basic ideas were popularized in 1965, but some algorithms had been derived as early as 1805. In 1994, Gilbert Strang described the FFT as "the most important numerical algorithm of our lifetime", and it was included in Top 10 Algorithms of 20th Century by the IEEE magazine Computing in Science & Engineering.The best-known FFT algorithms depend upon the factorization of N, but there are FFTs with O(N log N) complexity for all N, even for prime N. Many FFT algorithms depend only on the fact that




e


2
π
i

/

N




{\displaystyle e^{-2\pi i/N}}
is an N-th primitive root of unity, and thus can be applied to analogous transforms over any finite field, such as number-theoretic transforms. Since the inverse DFT is the same as the DFT, but with the opposite sign in the exponent and a 1/N factor, any FFT algorithm can easily be adapted for it.

View More On Wikipedia.org
  1. C

    A Memory issues in numerical integration of oscillatory function

    Hello! I need to numerically integrate a frequently oscillating, decaying complex function over the interval from 0 to infinity, which is continuous. For brevity, I provide the general integral view $$\int_{0}^{\infty} A(t)e^{e^{iw't}}dt$$. I'm using Python libraries for this task...
  2. A

    I Fourier Transformation on a Ring

    Hello, I have a question about the FFT and would like to share my thoughts with you. The background is a problem 30.2-6 from the legendary algorithms book by Cormen. It says that instead of doing an n element FFT over the field of complex numbers, we can use ##\mathbb{Z}_m##, where ##m = 2^{t...
  3. N

    I Get the time axis right in an inverse Fast Fourier Transform

    Hi I would like to transform the S-parameter responce, collected from a Vector Network Analyzer (VNA), in time domain by using the Inverse Fast Fourier Transform (IFFT) . I use MATLAB IFFT function to do this and the response looks correct, the problem is that I do not manage to the time scaling...
  4. .Scott

    The Fast Fourier Transform is described in the Quantum Domain

    In August, "Quantum Information Processing" published an article describing a full FFT in the quantum domain - a so-called QFFT, not to be confused with the simpler QFT. According to the publication:
  5. M

    MATLAB Fast Fourier Transform in MATLAB

    Hi PF! I'm following a tutorial in MATLAB, shown here t = 0:.001:.25; x = sin(2*pi*50*t) + sin(2*pi*120*t); y = x + 2*randn(size(t)); Y = fft(y,251); Pyy = Y.*conj(Y)/251; f = 1000/251*(0:127); plot(f,Pyy(1:128)) title('Power spectral density') xlabel('Frequency (Hz)') I read the...
  6. M

    I The fast Fourier transform and droplet frequencies

    Hi PF! Suppose we take a drop of fluid and let it sit on a substrate, and then vibrate the substrate. Doing this excites different modes. If someone where to analyze the vibrations, would they take an FFT of the interface, basically reconstructing it from basis functions (harmonics), where the...
  7. K

    Perform an image deconvolution using FFTs and Python

    Homework Statement [/B] This problem is from Mark Newman's Computational Physics, problem 7.9, found at http://www-personal.umich.edu/~mejn/cp/exercises.html. The problem gives us a blurry convolved image, according to a Gaussian point spread function and our objective is to deconvolve it to...
  8. Telemachus

    Fortran Discrete Fast Fourier transform with FFTW in FORTRAN77

    Hi, this thread is an extension of this one: https://www.physicsforums.com/posts/5829265/ As I've realized that the problem is that I don't know how to properly use FFTW, from http://www.fftw.org. I am trying to calculate a derivative using FFTW. I have ##u(x)=e^{\sin(x)}##, so...
  9. W

    MHB I am trying to figure out the right fast fourier transform size.

    I am using a Tascam recorder to record an environmental nuisance noise that is occurring in my home. I then use Virtins Multi Instrument Software, which includes an oscilloscope, band pass filter, and a spectrum analyser. Noise source is probably machinery at a legal marijuana grow op. That...
  10. E

    Using the Fourier Transform on Partitioned Images

    If I cut my image into several portions and use the Fast Fourier Transform on each portioned image, will I achieve the same result as if I used Fast Fourier Transform on the whole image? I have this concern because I need to process a large image using the Fast Fourier Transform, the problem is...
  11. Z

    MATLAB Is FFT the Proper Method for Transforming Green Function in MATLAB?

    Hi everybody. I have a (1×N) Green function in MATLAB. I want to use the FFt function for Green function to transform the time domain. Does the FFT command work correctly for Green function using: A=fft(Green function, nfft). Here nfft is the number of transformed points. Is it necessary that...
  12. Z

    MATLAB FFT for one 1*N Green function in MATLAB

    I have a 1×N Green function in energy domain. I want to use the FFT (fast Fourier transform) for this Green function in MATLAB. But this function is non-periodic. Could you help me about this? How can I change the energy interval to convert Green function as a periodic function?
  13. R

    Some questions about Fourier transformation

    Hi, I'm writting a program in the computer and I've to perform a fast Fourier transform to get the frequency domain information. I've read different website, I've watched some videos, etc and I don't fully understand the whole theory about FFT. I've to say that I don't have a solid mathematics...
  14. E

    MATLAB Implementation of Fresnel Diffraction in MatLab

    I'm trying to simulate the Fresnel Diffraction in MatLab using the Fast Fourier Transform syntax. But I'm not getting really good diffraction patterns. Here is the code: %% Fourier Transform for G(p, q) g = layer.*exp(((1i*pi)/(lambda*z))*(r_obj)); G = fftshift(fft2(g)); %% Fourier Transform...
  15. B

    MHB Calculating Harmonics from FFT of sin(x) Function

    Hi Folks, The Fourier Cosine Transform of cos(x) for 0<x<a and 0 everywhere else is given as F(\omega)=\displaystyle\frac{1}{\sqrt{2 \pi}}[\frac{\sin a (1-\omega)}{1-\omega}+\frac{\sin a (1+\omega)}{1+\omega}] I can plot this and we get a continuous amlitude spectrum of F(\omega) against...
  16. G

    Losing energy during Fast Fourier Transform

    Alright guys. First off, this is my first post (happy to be here!) and I'm hoping this is the correct section of the forum. I'm an engineering student, currently working towards finishing my master's thesis. Short introduction. I am trying to simulate an ocean wave environment, as a...
  17. P

    Fast Fourier Transform (FFT) power spectrum angle

    Dear Physics Buddies, How are well all, okay I hope. I was wondering if I might browse all your infinite intellects and ask you a very simple question. I am working with some medical images in MATLAB and my collaborators would like to know the orientation of the fibres that it contains...
  18. D

    MHB Fast Fourier Transform and its inverse

    Does every FFT have \(i\) in it? Given \(u_t = -(u_{xxx} + 6uu_x)\). \(f'''(x) = \mathcal{F}^{-1}\left[(ik)^3\mathcal{F}(f(x))\right]\) \(f'(x) = \mathcal{F}^{-1}\left[(ik)\mathcal{F}(f(x))\right]\) The only equation I have used the pseudo-spectral method on was the NLS which is \(u_t =...
  19. L

    Fast Fourier Transform in excel

    I really need your help - i can't work out how to do a FFT in excel. The main problem is I don't have a constant sampling rate - I recorded the time and then the corresponding magnitude of the wave. I have followed everything oneline but I can't seem to get anything to work as I can't fill the...
  20. C

    Using a Fast Fourier Transform

    Hi I'm working on a project which takes up ECG signals and tries to evaluate the condition of the patient. For one particular disease (ventricular tachycardia) the ECG looks close to a sine wave. Hence, I find the predominant frequency in the signal. I shift the original signal now by half...
  21. O

    Fast Fourier Transform in Real Time

    I guess this is programming and physics all combined into one but hopefully I can get some help anyway. I am doing some signal analysis of real-time streaming sensor data. I would like to do a DFFT on the data in real time as it streams in. So far pretty easy, however, there are a number of...
  22. E

    Extracting periodicity with Fast Fourier Transform

    Hello all, I want to extract the period out of a complex discrete signal. Currently I have the Matlabscript of the attachement. However, the values I get out of this script are not correct. There is some kind of systematic bias in it. I think it has something to do with index *...
  23. X

    Fast fourier transform on exponential decay function

    Hi all: I have one confused question. one continuous exponential decay function f=exp(-lamda*t) start from t=0 to infinity. I sample 1024 data points from the decay function. time variable (t) ranges from 0 to 1 second. the tail data of this exponential function is zero. I apply discret FFT on...
  24. B

    MATLAB Fast Fourier transform - MATLAB

    I have raw data in following format Time <-> Ch1 <-> Ch2 <-> Ch3 0.01 <-> 1.6 <-> 1.62 <-> 1.92 0.03 <-> 1.63 <-> 1.62 <-> 1.96 0.05 <-> 1.63 <-> 1.63 <-> 2.04 ...so...
  25. A

    Fast Fourier Transform

    First of all I apologies if I am in the wrong part of the forum for this question but here it is: How do I go about finding the Fast Fourier Transform (FFT) for a given data set? Homework Equations Ive tried using FFT Magnitude = FFT (Real numbers)^2 + FFT (imaginary numbers)^2...
  26. S

    Finding an average of a signal using Fast Fourier Transform?

    Hi all, I have discrete data of a signal but I do not know the periods of the signal. The signal is like a "beat" I guess, but not really sure. I plan to use fft in MATLAB to get it's frequency spectrum and get the 0Hz value as the average of the signal. Is this a bad idea? Any other ways...
  27. M

    MATLAB MATLAB: Fast Fourier Transform

    I have run the following command: c = wavread('sample.wav'); amplitude = log (abs(fft(c))); and obtained the following plot: http://img179.imageshack.us/img179/8733/withoutplusone.jpg [Broken] however, i was told to use this instead: amplitude = log (1+abs(fft(c))); and obtained...
  28. T

    Solving the wave equation numerically using the Fast Fourier Transform

    Homework Statement According to the website, the statement is as follows: Write a program which will calculate the evolution of the Wave Equation, in the case of a bound string. Test this program on the base eigenfunctions, i.e. the sinusoids, and on more interesting combinations. You...
  29. T

    Fast Fourier Transform Amplitude Units

    Hi there, So I have a multi year time series of of heights in meters that I am working on. If I compute the FFT on the data and then calculate the amplitude as: abs(FFT)/N where N is the number of samples what units do I end up with for the amplitude? Is it still in meters? Cheers
  30. P

    FFT (Fast Fourier Transform) - a method for phase continuation

    Hello everyone, Finding a good query to find an answer in www search engines isn't as easy as I thought. The subject is very narrow and sophisticated. When one performs a FFT, he/she/IT ;) gets the amplitude and phase spectra. The phase spectrum ranges from -PI to PI. Then, there are of course...
  31. K

    Fast Fourier Transform graph

    Homework Statement Which of the following things are true given the sound data that is represented in the two graphs above? Select ALL that are true. (One graph of Sound Pressure v Time with what looks like a repeating pattern & one graph of Amplitude v Frequency with 2 large spikes at 512Hz...
  32. H

    Fast Fourier Transform (FFT) Input Question

    Hi, I have a question about the FFT. I'm starting to learn the concepts behind it, but I'm struggling at this one particular thing... Ok, let's say you have this diagram. http://www.ece.uvic.ca/499/2004a/group05/image/radix2.jpg Can someone explain to me exactly what "N-point" means? Also...
  33. W

    Evaluate a function via fast fourier transform using Matlab

    Hi all, I'm new to Matlab, and I'm trying to evaluate a function via fast Fourier transform using Matlab, then compare the values at each gridpoint with the exact value. The function is y1 = cos(x)-20*sin(5*x)+6*sin(12*x) on the interval [-pi, pi], using n = 9 gridpoints. I first tried...
  34. W

    Fast Fourier Transform

    Hi all , This FFT program may help some of you in your Engineering studies , it was a lot of fun to write and use .. I wrote it in pascal . All the instructions are included at the beginning.. I think my approach to reordering the twiddle factors is innovative as it is written in assembly...
Back
Top