Questions tagged [fft]

The fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse.

Filter by
Sorted by
Tagged with
117 votes
4 answers
53k views

Why is it a bad idea to filter by zeroing out FFT bins?

It's very easy to filter a signal by performing an FFT on it, zeroing out some of the bins, and then performing an IFFT. For instance: ...
endolith's user avatar
  • 15.8k
101 votes
6 answers
209k views

Why should I zero-pad a signal before taking the discrete Fourier transform?

In an answer to a previous question, it was stated that one should zero-pad the input signals (add zeros to the end so that at least half of the wave is "blank") What's the reason for this?...
Jonas's user avatar
  • 3,071
69 votes
8 answers
129k views

How do I implement cross-correlation to prove two audio files are similar?

I have to do cross correlation of two audio file to prove they are similar. I have taken the FFT of the two audio files and have their power spectrum values in separate arrays. How should I proceed ...
user avatar
50 votes
3 answers
101k views

Why is the FFT "mirrored"?

If you do an FFT plot of a simple signal, like: t = 0:0.01:1 ; N = max(size(t)); x = 1 + sin( 2*pi*t ) ; y = abs( fft( x ) ) ; stem( N*t, y ) 1Hz sinusoid + DC ...
bobobobo's user avatar
  • 945
36 votes
9 answers
14k views

Is there an algorithm for finding a frequency without DFT or FFT?

I was looking in the Android app store for a guitar tuner. I found a tuner app that claimed it was faster than other apps. It claimed it could find the frequency without using the DFT (I wish I still ...
Slamice's user avatar
  • 463
34 votes
3 answers
46k views

Picking the correct filter for accelerometer data

I am fairly new to DSP, and have done some research on possible filters for smoothing accelerometer data in python. An example of the type of data Ill be experiencing can be seen in the following ...
Michael M's user avatar
  • 443
31 votes
5 answers
10k views

Is there a technical term for this simple method of smoothing out a signal?

Firstly, I am new to DSP and have no real education in it, but I am developing an audio visualization program and I am representing an FFT array as vertical bars as in a typical frequency spectrum ...
Michael Bromley's user avatar
29 votes
4 answers
6k views

Which time-frequency coefficients does the Wavelet transform compute?

The Fast Fourier Transform takes $\mathcal O(N \log N)$ operations, while the Fast Wavelet Transform takes $\mathcal O(N)$. But what, specifically, does the FWT compute? Although they are often ...
endolith's user avatar
  • 15.8k
28 votes
2 answers
20k views

Overlap-Add versus Overlap-Save

What differences or other criteria can be used to help decide between using overlap-add and overlap-save for filtering? Both overlap-add and overlap-save are described as algorithms for doing FFT ...
hotpaw2's user avatar
  • 35.3k
27 votes
1 answer
33k views

What is the difference between PSD and squared magnitude of frequency spectrum?

The power spectrum of a signal can be calculated by taking the magnitude squared of its Fourier transform. Being an audio person, the signal of interest for me would be a time series. How does this ...
learnvst's user avatar
  • 1,513
26 votes
6 answers
100k views

What is a frequency bin?

I'm doing a research on the FFT method, and a term that always comes up is "frequency bin". From what I understand, this has something to do with the band created around the frequency of a given ...
JonTrav1's user avatar
  • 261
26 votes
4 answers
63k views

What effect does a delay in the time domain have in the frequency domain?

If I have a signal that is time limited, say a sinusoid that only lasts for $T$ seconds, and I take the FFT of that signal, I see the frequency response. In the example this would be a spike at the ...
gallamine's user avatar
  • 693
26 votes
3 answers
48k views

Intuitive explanation of cross-correlation in frequency domain

According to the cross-correlation theorem : the cross-correlation between two signals is equal to the product of fourier transform of one signal multiplied by complex conjugate of fourier transform ...
silver surfer's user avatar
25 votes
3 answers
13k views

Tips for improving pitch detection

I'm working on a simple web app that allows the user to tune his/her guitar. I'm a real beginner in signal processing, so please don't judge me too harshly if my question is inappropriate. So, I ...
Rad'Val's user avatar
  • 463
25 votes
1 answer
64k views

low pass filter and FFT for beginners with Python

I am new to signal processing and especially to FFT, hence I am not sure if I am doing the correct thing here and I am a bit confused with the result. I have a discrete real function (measurement ...
Till B's user avatar
  • 353
23 votes
6 answers
17k views

What are the problems with designing an FIR filter using FFT?

I'm trying to get an understanding of the relationship between an FIR filter designed from "first principles" using a filter kernel with convolution, and a filter designed in one of two ways using FFT ...
bryhoyt's user avatar
  • 1,423
22 votes
5 answers
28k views

Fast Cosine Transform via FFT

I want to implement the Fast Cosine Transform. I read on wikipedia, that there is a fast version of the DCT which is similarly computed to the FFT. I tried to read the cited Makhoul* paper, for the ...
Framester's user avatar
  • 321
22 votes
2 answers
78k views

Power spectral density vs. FFT bin magnitude

What's the difference between these? Both are measurements of some form of signal power, but surely there's some difference between the power they are measuring?
mavavilj's user avatar
  • 1,414
22 votes
4 answers
7k views

How to distinguish voice from snoring?

Background: I'm working on an iPhone application (alluded to in several other posts) that "listens to" snoring/breathing while one is asleep and determines if there are signs of sleep apnea (as a pre-...
Daniel R Hicks's user avatar
22 votes
2 answers
27k views

Improving spectrogram resolution in Python?

I'm using the specgram() function in matplotlib to generate spectrograms of speech wave files in Python, but the output is ...
Alek Storm's user avatar
21 votes
4 answers
51k views

Discrete Fourier Transform: What is the DC Term really?

I am currently toying around with the Discrete Fourier Transform (DFT) in Matlab to extract features from images. I like to fully understand the concepts that I use. I have read several explanations, ...
Domi's user avatar
  • 323
21 votes
2 answers
8k views

Does using the Goertzel algorithm actually give better frequency resolution?

I am reading this article, and I am getting a little confused by the author's liberal use of 'frequency resolution' regarding the Goertzel Algorithm. Basic question: Does using the Goertzel algorithm ...
Spacey's user avatar
  • 9,817
20 votes
9 answers
7k views

Is there an algorithm to compute the phase for a single frequecy?

If you have a function $f(t)=A \cdot \sin(\omega t+\phi)$, and reference sin wave $\sin(\omega x)$ what would be a fast algorithm to compute $\phi$? I was looking at Goertzel algorithm, but it doesn'...
SamFisher83's user avatar
20 votes
3 answers
10k views

Why are magnitudes normalised during synthesis (IDFT), not analysis (DFT)?

In most examples and FFT code that I've seen, the output (frequency magnitudes) of the forward DFT operation is scaled by N -- i.e. instead of giving you the magnitude of each frequency bin, it gives ...
bryhoyt's user avatar
  • 1,423
20 votes
3 answers
7k views

FFT with asymmetric windowing?

Common non-rectangular window functions all seem to be symmetric. Is there ever a case when one would want to use a non-symmetric window function before an FFT? (Say if the data on one side of the ...
hotpaw2's user avatar
  • 35.3k
20 votes
4 answers
12k views

How do you calculate spectral flatness from an FFT?

Ok, the spectral flatness (also called Wiener entropy) is defined as the ratio of the geometric mean of a spectrum to its arithmetic mean. Wikipedia and other references say the power spectrum. Isn'...
endolith's user avatar
  • 15.8k
19 votes
2 answers
18k views

Why do we say that "zero-padding doesn't really increase frequency resolution"

Here is a sinusoid of frequency f = 236.4 Hz (it is 10 milliseconds long; it has N=441 points at sampling rate ...
Basj's user avatar
  • 1,277
19 votes
2 answers
24k views

Why does spectral leakage arise in an FFT?

I've tried googling and wikipedia-ing it, but I haven't gotten any answers beyond 'it's because the frequency of the input signal is sitting between two bins'. I understand that this is the reason, ...
Kitchi's user avatar
  • 721
18 votes
7 answers
7k views

What are some of the differences between DFT and FFT that make FFT so fast?

I'm trying to understand FFTs, here's what I have so far: In order to find the magnitude of frequencies in a waveform, one must probe for them by multiplying the wave by the frequency they are ...
Seph Reed's user avatar
  • 305
18 votes
3 answers
19k views

When to use the DTFT vs the DFT (and their inverses) in analysis?

In many of my readings, whenever some author speaks about working in the frequency (transform) domain (of a digital signal), they often times take the DFT, or the DTFT, (and of course their ...
TheGrapeBeyond's user avatar
18 votes
1 answer
28k views

What is the phase and magnitude response of white noise?

I would like to create white noise in the frequency domain, and then transform it to the time domain using python. To understand the problem, I simply generated white noise in the time domain, and ...
Uffe's user avatar
  • 355
17 votes
6 answers
13k views

Is there any practical application for performing a double Fourier transform? ...or an inverse Fourier transform on a time-domain input?

In mathematics you can take the double derivative, or double integral of a function. There are many cases where performing a double derivative models a practical real-world situation, like finding the ...
tjwrona's user avatar
  • 325
17 votes
5 answers
14k views

FFT of sine wave not coming as expected i.e single point

The cyan plot is a spectrum of 50 Hz, and the magenta one is a 50.1 Hz sine wave (having amplitude 0.7). Both are sampled at 1024 samples/s. I performed a 1024 point FFT to get this spectrum. Why is ...
gpuguy's user avatar
  • 1,370
17 votes
2 answers
2k views

Why real part of FFT converts image into rotation + original?

I have read this image: taken its FFT (2D) and then Inverse FFT to get exactly the image back. Code is provided for reference: ...
Failed Scientist's user avatar
17 votes
2 answers
2k views

DFT with geometrically-spaced bins?

The traditional Discrete Fourier Transform (DFT) and its cousin, the FFT, produce bins that are spaced equally. In other words, you get something like the first 10 hertz in the first bin, 10.1 through ...
Brannon's user avatar
  • 295
16 votes
9 answers
27k views

Why do we use window in time domain rather than do FFT modify the spectrum and than inverse FFT

I thought that DSP would be done by using FFT of portions of a signal, modify the samples that result from FFT (since they represent the spectrum of our signal + noise) and remove any unwanted signals ...
quantum231's user avatar
16 votes
4 answers
27k views

Extracting frequencies from FFT

I performed 512 point FFT on a signal. I got another set of 512 Numbers. I understand that those numbers represent amplitude of the various sine and cosine waves having different frequencies. If my ...
gpuguy's user avatar
  • 1,370
16 votes
3 answers
5k views

Fast Fourier transform- non-integer number of cycles in the FFT aperture

There are a few excellent discussion threads and answers on this site (eletronics.se) on the theory of Fourier transforms. I tried implementing the same in a simulation tool (MS Excel :)). I have a ...
Vaibhav Garg's user avatar
16 votes
2 answers
34k views

Image Reconstruction:Phase vs. Magnitude

Figure 1.(c) shows the Test image reconstructed from MAGNITUDE spectrum only. We can say that the intensity values of LOW frequency pixels are comparatively more than HIGH frequency pixels. Figure 1.(...
sagar's user avatar
  • 549
16 votes
1 answer
5k views

Find similar Music using FFT Spectrums

I have been experimenting some weeks to find a way to match/find similar Songs in a Library containing different Genres of Music. My first try was to Detect Features like Tempo or how much Bass there ...
gfg's user avatar
  • 161
16 votes
2 answers
12k views

What data should I use to test an FFT implementation, and what accuracy should I expect?

I'm involved with an effort to implement an FFT algorithm, and am curious what the recommended advice is for the input test data to use -- and why! -- and what accuracy to expect. On test inputs, I'...
Brooks Moses's user avatar
15 votes
4 answers
6k views

Lower frequencies stronger in FFT?

I'm calculating FFT from microphone input. I notice that lower frequencies always seems to have more power (higher dB) than higher frequencies. I cut the data into frames of 24576 bytes (4096*6). ...
Tedd Hansen's user avatar
15 votes
4 answers
17k views

Most efficient way to extract frequency components of audio signal with near-human accuracy in real time

I'm trying to work out how (if possible) to extract the frequency components of an arbitrary audio sample (typically music) in an FFT-like manner, but in my research on the FFT algorithm, I'm learning ...
bryhoyt's user avatar
  • 1,423
15 votes
1 answer
29k views

What are the units of my data after an FFT?

Magnetometer measures the derivative of the magnetic field, or dB/dt, with an output in microvolts (mV). The Sampling rate is 128 Hz, so if we collect data for 2 minutes, $2 \times 60 \times 128=...
MikiBelavista's user avatar
15 votes
2 answers
15k views

Is it customary to correct for the gain of a window?

Consider how the Hanning window is defined: 0.5 - 0.5 * cos(n*2*Pi/(N-1)) By this definition, it has a gain of 0.5, which is simply the average value of the ...
user5108_Dan's user avatar
15 votes
3 answers
714 views

How to efficiently calculate only the low coefficients of a zero-padded FFT

I've got an algorithm that zero pads a sequence to 4N, does an FFT, and only uses the lowest frequency N points out of the generated 4N. This seems like a lot of wasted work, any ideas how this can ...
Mark Borgerding's user avatar
14 votes
5 answers
35k views

Fastest implementation of fft in C++?

I have a MATLAB program that uses fft and ifft a lot. Now I want to translate it to C++ for production. I used OpenCV but I ...
Saeid's user avatar
  • 255
14 votes
7 answers
3k views

Why does a longer observation time improve DFT resolution, but repeating a signal does not?

As was proven here: https://math.stackexchange.com/questions/228614/why-doesnt-repeating-a-signal-give-rise-to-a-finer-resolution-of-dft-fft repeating a certain sequence does not improve DFT frequency ...
Ariane's user avatar
  • 141
14 votes
4 answers
7k views

Intuition for sidelobes in FFT

I was wondering if there's a intuitive way to understand why sidelobes appear when performing an FFT on a signal of fixed length?
CatsLoveJazz's user avatar
14 votes
7 answers
12k views

The difference between DFT and DFS

In the literature, I've found that DFS and DFT are one and the same. If they are one and the same why to use two different names for them? If there is really a difference what is it and what is the ...
phanitej's user avatar
  • 450

1
2 3 4 5
64