What is Fft: Definition and 178 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. A

    Number of Multiplications in the FFT Algorithm

    Hello everyone, maybe some of you know the formula for the number of multiplications in the FFT algorithm. This is again given as ##N/2 \cdot log(N)##. Why is that so? Can you really "prove" this? I can only deduce this from what I know, because we have ##log(N)## levels and ##N/2##...
  2. raminee

    A Editing in Freq domain and applying inverse FFT

    Hello All, I am somewhat familiar with FFT and iFFT and its uses. However I have an issue when I edit in Freq domain and try to get back to time domain . I have an audio signal in time domain that I transform to frequency domain using an FFT routine in block sizes of N points. (in my case 256...
  3. F

    Using PASCO's FFT Ap for Investigation 16D

    I was trying to incorporate this lab into the course, but when I try using a tuning fork on the FFT/Spectrum Analyzer app I can't get a well defined frequency reading. I tried doing the same thing on an opensource FFT app and had the same issue. I am thinking most laptop microphones these days...
  4. A

    MATLAB Boundary conditions in the resolution of a PDE with the FFT method

    How to impose boundary conditions when solving a PDE with fft? For example here: If I copy this code I get periodic boundary conditions. Thank you
  5. B

    Understanding the Basics of FFT for Image Processing

    if you watch this Video : The Julia Programming Language at time marker 28:00, You will see that Grant takes an FFT of an Image. In order to do a FFT, you need to know the sampling rate, but what is the sampling rate of one image? And what if your image is not size 2^N ? Does the program just...
  6. M

    MATLAB FFT interpretation of time vector (simple)

    I have video data that shows an object moving up and down. I'd like to extract the frequency the object moves. Following the given example here (scroll down to "Examples"), am I correct in assuming Fs would be camera frame rate and L would be the total number of frames? Thanks so much!
  7. Lecture 1 - Data Driven Methods in Dynamical Systems

    Lecture 1 - Data Driven Methods in Dynamical Systems

    This is an introductory video for my class on data driven methods in dynamical systems theory. We will cover topics including SVDs, FFTs, DMD, PCA, and many other acronyms.
  8. tworitdash

    MATLAB Creating and recovering a frequency shift in time domain in MATLAB

    I am trying to simulate and process the Doppler signals. My main problem is a little more complex so I am only posting a simple version of it. Task1: I have a time-domain signal with the velocity of the target as mu. I need to change the velocity to mu cos(theta) where theta is a vector from 0...
  9. tworitdash

    MATLAB FFT of conjugate doesn't coincide exactly at the negative frequency

    I am trying to understand why the conjugate of a signal in the time domain doesn't produce an exact flip of the frequency domain spectrum. There is always a one-pixel shift in the result. The MATLAB code is shown below. I use a flip for the conjugate spectrum to show that it doesn't match the...
  10. tworitdash

    MATLAB How to change the frequency values inside a time domain signal phase

    The problem I am having is simple. I have a Gaussian spectrum initially. Like this, Process 1: S = m0/sqrt(2*pi*sigma^2) * exp(-(vel_axis - mu).^2/(2*sigma^2)); Here, mu is the mean velocity (frequency) and sigma is the standard deviation. vel_axis is the axis on which I am calculating this...
  11. Schwann

    I Linearity of power spectral density calculations

    I have a question related to linearity of power spectral density calculation. Suppose I have a time series, divided into some epochs. If I compute PSD by Welch's method with a time window equal to the length of an epoch and without any overlap, I obtain this result: If I calculate the...
  12. DrClaude

    FFT scaling vs analytical FT

    When considering the forward FFT of a mathematical function sampled at times ##t = 0, \Delta, \ldots, (N-1) \Delta##, following the usual convention, we have something like $$ H(f) = \int_{-\infty}^{+\infty} h(t) e^{-2 \pi i f t} dt \quad \Rightarrow \quad H_k = \sum_{n=0}^{N-1} h_n e^{-2 \pi i...
  13. SchroedingersLion

    Solving Integrals with FFT: Help Needed!

    Hi guys, for a project I had to get involved with discrete Fourier transforms to solve PDEs. However, the code that I implemented according to a pseudo-code from a paper did not work - it seems like I calculated integrals incorrectly. To search the error, I tried to integrate the sin(x)...
  14. M

    Confused by envelope detection and windowing+overlapping

    Summary: Should both envelope detection and windowing+overlapping be used before FFT? Summary: Should both envelope detection and windowing+overlapping be used before FFT? Hi everyone! I'm somewhat a newbie to signal analysis, but I've also noticed that there seem to be many different...
  15. D

    How to use the window functions on a signal in MATLAB?

    Homework Statement I am suppose to write a program that compares the FFT (Fast Fourier Transform Diagrams) of a sampled signal without the use of a window function and with it. The window function should be as long as the signal and the signal should have N points, N chosen as to not cause...
  16. F

    I Solving PDE's with chebychev FFT

    I have seen one lecturer solve a PDE with just using Fast Fourier Transform (##FFT##) of a function ##v## on a chebychev grid. ##v_t=\mu v_x## This lecturer uses ##FFT## on ##V##, then solves the ODE using an ODE solver in Matlab, then inverse ##FFT## to get the real solution ...
  17. C

    MATLAB FFT problem for Fresnel simulation

    Hi all, I'm trying to simulate the Fresnel diffraction by using this expersion : $$ A(x')=\frac{1}{j\lambda z}e^{jk(z+\frac{x'^2}{2z})}F(A^{trans}(x)e^{jk\frac{x^2}{2z}})_{u=\frac{x'}{\lambda z}} $$ So when I use this formula my problem is that I don't know how to take the good frequency, here...
  18. K

    Unbiased estimate of a parameter in the Rice distribution

    I am trying to estimate the amplitude of a real signal with a particular frequency and unknown phase. The signal is sampled at a frequency much higher than the Nyquist frequency for the signal. For simplicity, I take an FFT period which is a multiple of the signal period (which conveniently is a...
  19. D

    Meaning of the FFT of a Poynting Vector integral, reflection coefficient

    Hello, For calculating the mean power at a specific cross section of a waveguide, one can calculate the mean value of the temporal function of Poynting Vector, P(t), where P(t) is the ExHy-EyHx. Note that I am not talking about phasors or a sinusoidal state. If I integrate over the waveguide...
  20. J

    How can I integrate sinusoids in python code using FFT?

    Hello, Thank you for taking time to read my post. I have a discrete set of data points that represent an acceleration signal. I want to take the integral of this set of points twice so as to get a function which represents the position over time. To accomplish this, I have taken the FFT of the...
  21. J

    I Can an FFT be used to extract individual sinusoids from a set of data points?

    Hello, Thank you for taking time to read my post. Background: I have a accelerometer project that I am playing with that gives me the acceleration of the object. I can plot this data and it looks very nice. I want to integrate this to get the velocity and then integrate it again to get the...
  22. N

    Multiplying Big Numbers Using FFT

    Multiplying big numbers is a very common application of the FFT, and as such, there are many papers on the subject available online. However, these papers all use sophisticated algorithms where a simple one seems to work. My question is, what's wrong with the simple algorithm: Multiplication...
  23. I

    How to center the bandwidth for carrier frequency?

    I have a baseband signal in IQ form. I have a method to calculate the carrier offset and estimate the carrier bin. I want to center the carrier to the middle of the bandwidth. How do I do so? Do I simply multiply the IQ data by the exponential with the carrier offset, but doesn't that shift the...
  24. N

    Image FFT and Lens MTF: Evaluating Final Image Quality

    Hi, I am trying to determine the final image on a detector having a 600x600 mm viewed object and the known MTF of a lens. So when I FFT the object, thus creating frequencies -128/600 : 128/600 for a 256x256 image, how does the multiplication of the transformed object and the MTF "keep track" of...
  25. M

    Calculating Magnetic Field Strength from FFT

    Hello All, Briefly on the exposition; I'm an undergraduate assistant to a professor. We contribute to the Muon g-2 experiment in Fermilab, designing and optimizing the magnetic-measurement equipment. As you might imagine I utilize the Fourier Transform often to analyze data. The data I'm...
  26. M

    Calculating Magnetic Field from FFT Amplitude

    So a little bit of background: I work in an undergraduate lab at UMass Amherst and am currently building/optimizing a faraday magnetometer for use in the Muon g-2 experiment at Fermilab. The magnetometer works as follows. A laser is shone through a crystal with a particular Verdet Constant at...
  27. GhostLoveScore

    I Why are the bins N/2 - N not a mirror image of bins 0 - N/2 in FFT analysis?

    I am trying to do Fast Fourier Transform on some data recorded from RTL SDR. I managed to write a program that does that, but the problem is this. This is final result as it should look And this is my result It may be hard to understand this, I'll try to explain. My graph is done using 5000...
  28. B

    Pressure sensor- Digital_Filter

    I have input data from a pressure sensor:https://physicsforums-bernhardtmediall.netdna-ssl.com/data/attachments/93/93464-7e84f120a9323e7d16b7dfa59c069739.jpg [Broken] We run this into an FFT and found that the max point is at 3.3378Hz. So we did a Digital band pass Filter for 3.3Hz - 3.6Hz...
  29. R

    Simple 8-bit FFT Processor for 512pt Array at 20MHz

    Hello. I'm looking for a "simple" FFT processor able to process an 8 bits input in an array of at least 512 pts with a speed of at least 20 MHz. I've precised "simple" instead of certain TI DSP with up to 196 pins ! I only need FFT nothing else. Does it exist ? Thanks by advance for replies.
  30. T

    Algorithm for dB vs time graph for one frequency from FFT?

    I'm doing a physics experiment for school, for which I am measuring the reverb time for specific frequencies in a room. What I did was record a 1000 Hz sound, and some time after it, and looked at its FFT on Audacity to see the intensity of just 1000 Hz at a given time. Manually, I can do this...
  31. GhostLoveScore

    Calculating power spectral density from FFT

    EDIT: Sorry. It's FFT - Fast Fourier Transform, not FTT. I am interested in doing some amateur radio astronomy. Mainly at 1420MHz, hydrogen line. I have a RTL SDR stick. For those who don't know what that is, it's USB DVB-T receiver that can receive anything between 24 – 1766 MHz. Now, there...
  32. B

    Cool sound generator project

    So I have working code of a : FFT Digital low pass and high pass filter and sound generator What cool projects can I make which these ?
  33. B

    I Units of Amplitude & Frequency in Coding (n=0 to 52920)

    for (int n = 0; n < 52920; n++){ F = Amplitude * sin(2 *pi*n* Frequency/44100) ; } what are the units of Amplitude ? I know Frequency is in Hz also what are the unit of F?
  34. B

    Understanding N-Stages of FFT & DFT Formula for Frequency Domain

    1) How many stages are in N numbers for a FFT? I know N=8 has 3 stages and N=4 has 2 stages ? 2) The DFT formula converts a signal from the time domain into the frequency domain. Is this done by comparing x[n] against signals known as sinusoidal basis functions? are e-j2 pi kn/N sinusoidal...
  35. CassiopeiaA

    A Take FFT to find time period for eclipsing binaries

    I am trying to use Kepler Data for Eclipsing Binaries to estimate time period, and then other parameters such as mass, eccentricity, semi-major axis, distance, etc. of the binary systems. I want to write code in MATLAB which will use FFT to find the time period. The available data has the...
  36. M

    I Understanding Fourier Transforms

    Hello all, First time poster here so please excuse any mistakes as I'm unfamiliar with the conventions of this forum. Also before I get started I'd like to say I wasn't sure exactly where a question like this would go; I debated in the Math Programs and Latex section but figured general physics...
  37. John_Blacktower

    A Pseudospectral method using FFT to solve diff equation

    Hello everyone, I'm trying to solve by FFT a convection diffusion eqaution on a 3 D box with an slit condition on z-axix and periodic conditions on x and y axis. ∂C/∂t=D∇[2]C-v⋅∇C (1) v=vx + vy + vz i have solved the velocity of fluid, i mean a really know what is the velocity of flow field...
  38. V

    I Poisson Equation Neumann boundaries singularity

    I am trying to solve the poisson equation with neumann BC's in a 2D cartesian geometry as part of a Navier-Stokes solver routine and was hoping for some help. I am using a fast Fourier transform in the x direction and a finite difference scheme in the y. This means the poisson equation becomes...
  39. V

    I Solving u_x=(sin(x))*(u) in Fourier space

    Does anyone know if it is possible to solve an equation of the type u_x=(sin(x))*(u) on a periodic domain using the fft. I have tried methods using convolutions but have had no success thanks in advance
  40. M

    Efficient 2D FFT in C for Large Arrays: Where to Find the Code?

    I am looking for a 2D fft that takes in a 2D array of heights and does a fft in c on the array. I would like if the code was capable of working with big arrays, such as 8192 x 8192 I have tried the paulbourke and sanfoundry websites. The first was not giving me the output that is expected and...
  41. G

    A FFT phase result interpretation?

    I have a complex signal eg: cos(wt + phase1) + i*cos(wt + phase2) the frequency of both the waves is same. When i have a look at the phase spectrum of the above signal, i am not able to interpret the phase values. They are making no sense. I tried to determine phase shift for real signals and...
  42. T

    A Regarding the Continous Wavelet Transform 'a' parameter

    Hi there, I've recently been doing some studying into time-frequency analysis. I've covered some of the basic materials regarding the Short-Time Fourier Transform (STFT) along with the concepts of temporal and frequency resolution (along with the uncertainty principle of course). I've now...
  43. B

    Non-uniformly sampled transfer function data

    I have non-uniformly sampled transfer function data (magnitude only) in the range of 100kHz and 200MHz. Using this transfer function, I would like to calculate output from specific input. Question : To obtain phase of the transfer function from the magnitude data, I am trying to use Hilbert...
  44. J

    MATLAB 3D Diffusion Equation in MATLAB

    Hi guys, I have functioning MATLAB code for my solution of the 3D Diffusion equation (using a 3D Fourier transform and Crank-Nicolsen) that runs just from the command window and automatically plots the results. However, it seems like my solution just decays to zero regardless of what initial...
  45. K

    Automotive Why is an FFT done after a noise signal is captured?

    Presently there is a gear whine noise issue in a vehicle transmission. Our NVH team captured the noise signal using a microphone and then did an FFT of the signal and gave us a frequency plot. What exactly can I take out of it? Can I assume every harmonic belongs to a noise generated by a gear...
  46. E

    Reverse FFT of a ratio of two FFTs

    Dear all, I don't know if this is the correct place for this question, but I did a little search on the forum and I saw that most FFT related questions have been posted here. My question is this: I need to deconvolve two real signals (in my case they are two probability density functions), so I...
  47. A

    Help designing a music visualizer for a 12x12 LED screen

    I am working in a group for designing a LED interactive Screen. My part of the project is the design of the music visualization system. I am new in this area, but I know I need to use some op-amps to filter the input signal from the mp3 player. Could anyone give me any suggestions on how to...
  48. davidbenari

    Analyzing RC response with convolution theorem and fft.

    Some textbooks like (Numerical recipes the art of scientific computing) derive the DFT as a Riemann sum of the CTFT. With this in mind it would be natural then to approximate the identity ##y(t)=x*h=\mathcal{F}^{-1}\big\{XH\big\}## with the mathlab code y=ifft(fft(x).*fft(h)) which roughly...
  49. J

    I On liquid oscillation excitation

    (I'm new to the Forum, so if I violate the rules unknowingly, please do let me know) So, during a recent research, I analyzed the frequency spectrum of our hand's oscillation while walking. As it turns out, it contains distinct harmonic frequencies (around 1.8*n Hz), and the second among them...
  50. Y

    Frequency spectrum in Doppler effect

    Homework Statement I have been investigating the Doppler effect in a circular motion with a stationary source and moving observer (however the main aim is to determine the speed of sound in the end). Using Vernier software - Logger Pro - I have obtained two graphs of the sound pressure against...
Back
Top