Questions tagged [fft]

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

1,963 questions
Filter by
Sorted by
Tagged with
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, ...
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'...
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....
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1answer
6k views

1answer
10k views

...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...