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
10
votes
3answers
24k 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, ...
10
votes
6answers
5k 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'...
10
votes
3answers
2k views

MATLAB: $\tt fft$ and $\tt ifft$ scaling

In MATLAB, the outputs of the fft and/or ifft functions often require additional processing before being considered for analysis....
10
votes
3answers
8k views

Can edge detection be done in the frequency domain?

Can we take advantage of the fact that high frequency components in the FFT of an image generally correspond to edges, to implement an edge detection algorithm in the fourier domain? I did try ...
10
votes
3answers
3k views

How to create a distortion compensation filter

I am creating a channelizer that consists of a complex mixer, CIC decimator, and a FIR compensation/decimation filter. The final FIR filter may, if it matters, be implemented as more than one filter. ...
10
votes
2answers
3k views

What statistic is used to determine presence of a signal in noise?

This is a detector problem I believe: I am being stumped by what appears to be a simple problem. Basically, I have a band of interest. If signal energies exist within this band of interest, then I ...
10
votes
3answers
9k views

FFT for a specific frequency range.

I would like to convert a signal to frequency domain. The desired frequency range is 0.1 Hz to 1 Hz and the frequency resolution ...
10
votes
2answers
747 views

Is it valid to increase amplitude (and presumably FFT quality) by simply scaling the data?

I'm using a version of "KISS FFT" by Mark Borgerding. It accepts an array of 16-bit fixed-point input values and produces a 32-bit float result array. I've discovered that if the input amplitudes ...
10
votes
1answer
5k views

Creating a spectrogram

I've been trying to work out the logic for this task, and plan to use the KissFFT source package to perform the fast fourier transform. Please let me know if this looks about right: Allocate an FFT ...
10
votes
2answers
5k views

How do you handle negative frequencies in the power spectrum of a complex signal?

When we apply the DFT operation on a real signal $x[n]$ to get $X[k]$, then take the square magnitude of the $X[k]$, $\lvert X[k]\rvert^2$, the power spectrum is symmetrical. You can take the ...
10
votes
4answers
8k views

Radix-4 FFT versus Radix-2

Is a radix-4 implementation faster than a equivalently well coded radix-2 FFT? And if so, why would it be faster?
9
votes
2answers
2k views

Artifacts in FFT

I recently realized that FFT's aren't perfect. Meaning if I take a signal and then take it's FFT, and then do an inverse FFT, the resulting output isn't exactly the same as the input. Here's an image ...
9
votes
3answers
4k views

What is a good FFT window function to reject DC?

I'm using an FFT to analyze what is essentially the power envelope of a signal (see here for info on the containing project), and, since power numbers are always positive, to eliminate the DC ...
9
votes
1answer
3k views

How can I detect potholes using an accelerometer mounted in a vehicle?

I am currently studying DSP and FFT, I am very new to this and have been doing electronics for a long time with Arduino and hobby projects. Recently, I am doing a project with the goal to map potholes ...
9
votes
1answer
2k views

How to estimate the signal-to-noise ratio of a waveform?

I have a signal: $f_i(t_i=i\Delta t)$, where $i = 0\ldots n-1$. The signal seems to vary quickly around a slower varying "trend". I am assuming that the quickly varying part is noise and the slowly ...
9
votes
1answer
1k views

Discrete Fourier transform - finding the fundamental quickly?

First, I appologize because I'm a software developper and it's been a very long time I didn't dive into pure mathematics, so my question might seem dumb. I hope not. The context is pitch recognition ...
9
votes
2answers
4k views

How to do prediction using frequency domain data?

Both linear regression and Kalman filtering can be used to estimate and then predict from a time domain sequence of data (given some assumptions about the model behind the data). What methods, if ...
9
votes
3answers
1k views

DFT - Removing window effect in spectral domain with convolution

I was thinking about the DFT windowing subject and a thought came to my mind. A DFT will yield the spectrum of a signal convoluted with spectrum of the window used, therefore having a main lobes and ...
9
votes
2answers
642 views

What is obtained from the cross correlation plot?

Let’s assume that we have two audio signals, x(t) and y(t) affected by the noise as shown below. And we would like to cross-correlate these two signals and the cross-correlation plot is shown as ...
9
votes
1answer
786 views

Removing noise from F2F signal

(This question relates to Extracting Binary Magnetic-Strip Card Data from raw WAV) I am extracting the binary sequence from the magnetic strip on a credit card. As you can see, the signal is ...
8
votes
3answers
8k views

baffled by fft phase spectrum!

A very simple MATLAB experiment: f = 200; fs = 1000; t = 0: 1/fs : 1; x = cos(2*pi*f*t); plot(angle(fftshift(fft(x)))); And here's the output: Now, made ...
8
votes
4answers
1k views

DFT-like transform using triangle waves instead of sin waves

We know that DFT (discrete Fourier transform) breaks down a signal into multiple frequencies of sine waves. Does there exist a transform that does the same thing, but for triangle waves? For my ...
8
votes
3answers
3k views

How to check the FFT results of a sine wave?

I have been given an audio file (sine wave) 1000Hz as an input to my FFT algorithm. I have got 8192 power spectrum samples in a array. What is the best and easiest way to check whether my output is ...
8
votes
2answers
44k views

How to analyze audio input/spectrum correctly

I am quite new to Java and Signal Processing, but I was assigned a project dealing in audio processing. My topic given to me is a game that has a component of analyzing a song (any given song) and ...
8
votes
5answers
3k views

Piano pitch detection

I'm working on a piano tuning program and part of it requires real-time pitch detection. Here is the scheme I have so far which works to some degree but could probably use some refinement. I'm ...
8
votes
1answer
8k views

FFT of image data: “mirroring” to avoid boundary effects

I load and display an image of some rice in Matlab: g = imread('rice.png'); imshow(g); I take the FFT of this image and shift it: ...
8
votes
3answers
6k views

How do window size, sample rate influence FFT pitch estimation?

I am trying to create a pitch-detection program which extracts the frequencies of peaks in a power spectrum obtained from an FFT (fftpack). I am extracting the peak ...
8
votes
3answers
2k views

FFT for line detection

I am trying use the FFT in a different way then most people ask about. I want to be able to take a picture of a graph with regular repeating vertical lines, and to process the image to determine how ...
8
votes
2answers
1k views

Time resolution of the Short Time Fourier Transform (STFT)

I'm struggling to figure out how the time points of an STFT are calculated, and I can't find a definitive answer. Let's say I have a 4Hz stationary signal and I'm going to use a 64 second window with ...
8
votes
2answers
2k views

Phase shift and phase spectrum terms in multidimensional signal

I know about phase of a 1D signal. But when I go into higher dimensions like 2D,3D etc, it becomes headache to grasp the concept. What are the terms phase shift and phase spectrum mean in case of ...
8
votes
2answers
3k views

Gesture recognition with Hidden Markov Models

I am currently working on a gesture recognition system (for an Android Application). I think that I have completed the Image processing stage, where I am able to extract the contour of the hand (I am ...
8
votes
2answers
1k views

Standard deviation of spectral flatness — so what am I measuring, conceptually?

In my never-ending quest to identify snores, I've found that "spectral flatness" seems to be a fair measure of signal "quality". I'm computing spectral flatness as the geometric mean of the FFT ...
8
votes
1answer
6k 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=...
8
votes
3answers
9k 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 ...
8
votes
3answers
7k views

How do I go about detecting whistles, pops and other sounds in live audio input?

I've read many questions on SO, and frankly, each one of them is not describing any particular way to go about it. Some say "do FFT" and some say "zero crossing" etc. But I've only gone as far as ...
8
votes
1answer
2k views

Can I use FFT to interpret accelerometer gestures?

I have the need to detect two different gestures that occur when looking at accelerometer data. Here's a run down (as brief as I can make it): Lets say an iPhone is being oscillated back and forth ...
7
votes
4answers
3k 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?
7
votes
3answers
21k views

How to make a signal conjugate symmetric?

Take the simple frequency-domain band-pass filtering operation below . . . ...
7
votes
5answers
536 views

Fast & accurate convolution algorithm (like FFT) for high dynamic range?

It seems that FFT-based convolution suffers from limited floating-point resolution due to evaluating everything around the roots of unity, as you can see in the $10^{14}$-factor error in this Python ...
7
votes
1answer
10k views

Symmetry of real and imaginary parts in FFT [duplicate]

...
7
votes
3answers
7k views

How important is it to use power of 2 when using FFT?

Here is the problem. I have a 2D array of data, first column represents the time data and the second column represents the sinusoidal response data, based on the time data. I apply fft and I get my ...
7
votes
1answer
2k views

Do FFT-based filtering methods add intrinsic latency to a real time algorithm?

In a current audio processing application, I am working entirely in the time domain using IIR filters. This is so I can use an audio buffer of just 3 or 4 samples and can guarantee that there will be ...
7
votes
3answers
10k views

What are high frequencies and low frequencies in a signal?

I'm new to signal processing. I'm plotting a signal in the time-domain in matlab. I don't understand which parts of the signal are high frequencies and low frequencies, can someone explain what a high ...
7
votes
1answer
894 views

Good Heuristic Point Where Sending FFT to GPU is Computationally Worth It?

This is a rather simple question, but I haven't found much posted within the last 5 years or so regarding a good rule of thumb for computing an FFT on the GPU vs the CPU. I know that most of the ...
7
votes
2answers
3k views

Filtering - multiplication in frequency domain

I am trying to create a simple low pass filter, but I have got what I consider a surprising result when looking at the frequency response of a simple Butterworth filter. I have copied much of the ...
7
votes
1answer
5k views

1/n octave smoothing

Given a frequency response obtained with FFT, I would like to apply a 1/n octave smoothing. What filter should I be using and how? Maybe someone could point to a good reference (a paper or book on the ...
7
votes
1answer
3k views

What transform can I use to “zoom” in a specific portion of a signal's spectrum?

If I recall correctly, there is a variation of the DFT that can be used to analyze a specific band of the spectrum of a signal. How is it called?
7
votes
2answers
6k views

Logarithmic fourier transform(LFT) on audio signal

I am trying to analyze the musics as possible as precisely. Of course I tried FFT, but got some problems. I found low frequencies have very low resolution than human's hearing. I tried very long time ...
7
votes
1answer
2k views

Failed to implement Goertzel algorithm in Python

After some questioning on stackoverflow, I tried to implement a Goertzel algorithm in Python. But it doesn't work : https://gist.github.com/4128537 ...
7
votes
2answers
8k views

radix-4 FFT implementation

I implemented a 4-point radix-4 FFT and found that I need to do some manipulation of the output terms to get it to match a dft. My code is a pretty direct implementation of the matrix-formulation so ...