Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

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
4
votes
2answers
225 views

Creating an array whose DFT is all whole numbers

I'm working on a simple FFT implementation and currently running some unit tests. Long floating point numbers in C and assembly become very hard to keep track of, and this whole thing is error prone. ...
4
votes
2answers
4k views

Removing drift from integration of accelerometer data

I am trying to get a positional data from the accelerometer data using the following steps: Re-zero the accelerometer value Removing mean from accelerometer value First integration of accelerometer ...
4
votes
1answer
4k views

Non Uniform FFT / DFT with FFTW?

Can FFTW perform the FFT on data which is not uniform in time? I can't seem to find a straight-forward answer to this question anywhere online.
4
votes
2answers
10k views

PSD estimate using FFT - scaling and units

I know that similar questions have already been asked – I have read the answers, yet I am still not sure if I understand the topic properly at some points. I want to use FFT to calculate PSD ...
4
votes
1answer
564 views

Mapping the value of a sample in a 2-D DFT to cycles/pixel

If I have an image and its 2-D DFT of that image, what is the mapping between the value of the DFT at (u,v), and the frequency in the spatial domain in the x and y components, in cycles/pixel? I want ...
4
votes
1answer
462 views

What is a Phase Delay filter?

I'm looking at a job spec, detailed below. I'm perplexed as to what is being asked for. Could someone offer a basic understanding of this material? I can imagine a solution may involve performing ...
4
votes
1answer
634 views

High Level Process, Calculating Cepstrum When You Only Have Spectrum

I am not a DSP expert, so I would like someone to check my thought process: I have a text file representing the spectrum (calculated by some FFT hardware), and I'd like to calculate a cepstrum. I'm ...
4
votes
1answer
4k views

Best way to resample a signal (image)?

I have an original image $\ I(x_i,y_j)$ where $\ x_i = i*\Delta x, 0<= i < n_i $ and $\ y_j = j*\Delta y, 0<= j < n_j$ I am trying to implement a function that resamples the image ...
4
votes
2answers
1k views

FFT, How to decide if there is a signal among noise?

I have sets of data of different deep sky objects. My job is to check for any periodicity. I use IDL to run an FFT and wavelet methods to check for a signal. To test my code I ran the IDL built in ...
4
votes
1answer
214 views

Is there a “first” Fourier transform?

Every time I've read "first Fourier transform", I've assumed it to be a misspelling of the fast Fourier transform. Recently though, I saw the term in both the title and keywords of an article from a ...
4
votes
1answer
241 views

Zero padding effect on a FFT of gaussian noise

I have a gaussian noise $\nu(t)$ with variance $\sigma^2$. After a FFT I get $X(\omega)$. If now I do the IFFT on the $X(\omega)$ can I say that the result is still a gaussian noise of variance $\...
4
votes
2answers
825 views

Efficient computation of dot product of convolutions

I have two FIR filters $f_{1},f_{2}$ and two short time-slices of signals $s_{1},s_{2}$. I need to compute: $$\left<s_{1}*f_{1},\ s_{2}*f_{2}\right>$$ Which I compute using six FFTs: each $s_{i}...
4
votes
1answer
1k views

Is it possible to do single vehicle tracking using Fourier transform?

I am working on a project in image processing which is based on importance of phase only reconstruction of a signal obtained using Fourier transform.For more information about phase only ...
4
votes
2answers
3k views

OFDM transmitter bandwidth

Theory Suppose an OFDM transmitter with four subcarriers is implemented using the structure shown below. If the serial data input rate is 40 bps, each parallel stream will run at 10 bps. ...
4
votes
2answers
1k views

How to Apply Window Functions in Frequency Domain?

I am trying to apply a window function to smooth my signal and finally obtain the peaks of the signal. Yet, for spectral leakage I apply window function in time domain. After taking the Fourier ...
4
votes
1answer
3k views

Effect of sampling interval length and Gaussian noise on the frequency-spectrum

Suppose you have a signal $s(t)$, corrupted by Gaussian noise of $\eta(t)$ with zero mean and standard deviation $\sigma$. So that the measured signal is $f(t)=s(t)+\eta(t)$. I now want to calculate ...
4
votes
2answers
366 views

Is $O (N \log N)$ FFT speed the fastest we can ever attain?

I am wondering about whether or not there is a theoretical limit as to the speed at which we can compute a DFT. We all know that the FFT executes in $O (N \log N)$ time. However, is this a lower bound ...
4
votes
3answers
6k views

How to Remove the Periodic Oscillations from a Signal

The task that I have is to remove the annual and semiannual oscillation from a set of temperature measurements, taken over several years, by means of least squares method. I found the method ...
4
votes
1answer
57 views

Transform Length and event duration

Does the length of a Fourier Transform affect the ability to discern a small event in the data? This is a tricky question to ask, let me clarify. I don't care about when the event happened and I don'...
4
votes
1answer
420 views

2D Convolution in MATLAB Causes Artifacts (Boundary Issues)

I`m trying to do a 2D fast convolution in Matlab of large matrices. If I use FFT version based on convolution theorem ( https://en.wikipedia.org/wiki/Convolution_theorem ), there are some artefacts in ...
4
votes
1answer
277 views

Why isn't the Hartley Transform more widely used?

I was doing a bit of research on FFT and I came across this paper. According to it, computing the Fourier Transform using FHT is significantly faster than other methods, even for complex data. Yet, ...
4
votes
1answer
4k views

The necessity of null subcarrier in OFDM?

In looking to LTE specifications, with the subcarrier spacing $\Delta f = 15 \textrm{kHz}$, for bandwidth $10 \textrm{MHz}$, fft size $N_{fft} = 1024$ that needs a sampling rate $F_s \geq 1024 \times ...
4
votes
1answer
777 views

Calculating Beam pattern, Directivity of microphone array

As answered in Relationship of Fourier Transform and Spatial Directivity Pattern the relation between directivity pattern and weights is given. But I am bit confused, I have Beamformer weights (...
4
votes
1answer
2k views

What does the word 'bin' mean in the context of FFT's?

Everywhere I read about the FFT, I read about frequency bins. I can't find anything about what is precisely meant with 'bin'. What I wonder about is if this is actually meant to imply that the FFT ...
4
votes
2answers
1k views

Thoretically, what makes multi-pitch detection so difficult?

For multi-pitch detection, I mean for example pressing several piano keys at the same time. For signal pitch detection (pressing one key at a time), after FFT, mostly the frequency with the largest ...
4
votes
1answer
477 views

Is it possible to decompose an image into basis images using MATLAB?

I have read that: Using Fourier decomposition any arbitrary image can be represented as summation of orthogonal basis images. I want to see the basis images for any image say Lena or Cameraman, ...
4
votes
1answer
2k views

Audio Steganography using Phase Encoding Technique

I referred the below papers to understand the working of Phase Encoding,but the explanation is not proper.Just a few steps have been given in brief. ijcsi.org www.ijarcce.com Can someone please ...
4
votes
2answers
683 views

how were DTMF frequencies determined exactly and how can I extend them?

I've been playing with DTMF frequencies and the Goertzel algorithm, and would like to know exactly HOW the DTMF frequencies were determined. I understand that they were chosen such that none of the ...
4
votes
1answer
2k views

Matching masked images

Let's say I have two images that are parts of the same bigger image, cut using two masks (for simplicity, let's assume that the masks are just rectangles of the same size). The images are presumed to ...
4
votes
1answer
1k views

Convolving With half-Hanning

The goal is to get a 200ms decaying delay of an audio signal while preserving the sharpness of attacks to mimick human perception of sound. The paper I'm following convolves a 200ms half-Hanning ...
4
votes
1answer
5k views

How to get coefficients for sine/cosine function from complex FFT?

I'm working on a control system that measures the movement of a vibrating robot arm. Because there is some deadtime, I need to look into the future of the somewhat noisy signal. My idea was to use the ...
4
votes
1answer
65 views

Multidimensional FFT with mixed directions

Let's say I have three-dimensional complex array $X[m,n,p]$, $m \in \{0, 1, \ldots, M-1\}$, $n \in \{0, 1, \ldots, N-1\}$, $p \in \{0, 1, \ldots, P-1\}$; i.e. $X \in \mathbb C^{M \times N \times P}$. ...
4
votes
2answers
2k views

How to determine SNR from FFT of measured data?

I am doing impedance measurements, where I do a frequency sweep of a test current, and I measure the resulting voltage. Offline, I compute the FFTs of the voltage and current, and I want to make sure ...
4
votes
6answers
1k views

Find Short Clip of Audio Within Longer Clip Of Audio

I need help figuring out a way to automatically synchronize two audio files that are both different recordings of the same source. More info below. This example is from a concert, where there is only ...
4
votes
2answers
4k views

Effect of Hanning Window on phase of FFT

I'm calculating the beat of song through the frequency domain. I have 60 seconds of audio sampled at 48000Hz, multiplied by a Hanning window in the time domain. This gives me a resolution in the ...
4
votes
3answers
3k views

FFT the whole input vs FFT segment

suppose I have a 4 seconds signal captured at $f_s$ = 1024Hz, which gives 4,096 data array. What is the different between these 2 FFT methods (MATLAB code) [1] FFT the entire input with 4096-points ...
4
votes
1answer
171 views

1-D Fourier Transform Of A 2-D Image But At An Arbitrary Orientation

If one has a 2-D array and would like to take the 1-D Fourier transform along a direction $\theta$ degrees off the horizontal, is there a better/faster way to do this rather than rotating the image by ...
4
votes
2answers
356 views

Matching LPC frequency response to raw sample data frequency response

Background: The intention is feature/formant extraction from speech input. I have used an FFT on raw samples in the past and have done simple peak picking from a weighted average of frequencies over ...
4
votes
2answers
2k views

What is the right way to extract particular frequency phase information from FFT?

Signals acquisition: Two proximity sensors are positioned Orthogonal to each other. These would be measuring the vibrations of a rotating shaft. Problem: Each of these 2 signals has two dominant ...
4
votes
1answer
643 views

$1/n$ octave complex smoothing

An excellent answer to this post explains how to do $1/n$ octave energy smoothing and mentions complex smoothing can be done as well, but it's tricky business because of phase wrapping. How is phase ...
4
votes
1answer
1k views

STFT overlap add method - What am i doing wrong?

i am trying to implement a short time fourier transform of an audio signal to do some filtering (subtract another stft signal using spectral subtraction). I am using a hamming window function with 50% ...
4
votes
0answers
357 views

Extra 'fingers' found in graph after applying FFT in MATLAB

I am currently working on the FFT function in MATLAB. In this function, i require a 1024 number of data Time Domain plot and produce a 400 number of data Frequency domain plot. After applying the FFT ...
3
votes
3answers
8k views

Window function and length of signal

I'm new to FFT and DSP and I want to ask you some questions about calculating FFT in Matlab. The following code is from Matlab help, I just removed the noise. What happens if I choose the length of ...
3
votes
3answers
586 views

strange phenomenon in spectrogram of Windowed Fourier Transform [edited] [closed]

I am trying to understand how the Windowed Fourier transform works, so I used Matlab to create an artificial signal, and plotted the Windowed Fourier transform using a gaussian window. $x(t) = \left\...
3
votes
3answers
5k views

Speech Recognition - Project Idea

Wondering if someone could offer me any advice or help. Sorry if this question is too broad or anything. I'm wanting to complete an algorithm in basic Speech analysis. The algorithm will detect ...
3
votes
3answers
3k views

How to build a program that gives you on the fly the chords of the song while listening to it?

I am trying to think how can I program a SW that can recognize Chords on the fly. since I know nothing about music, Can I assume that the chords are orthogonal and unique? I guess I can since it is ...
3
votes
6answers
740 views

Clarification on defining FFT bin sizes

When reconstructing the frequency domain for an FFT, what is the most self-consistent way to do this -- i.e. how is it best to define the bin width, $\Delta f$? For example, previously I thought it a ...
3
votes
3answers
5k views

Zero-pad before or after windowing for FFT

What's the correct way. Should I zero-pad a signal before or after applying a windowing function?
3
votes
2answers
9k views

FFT for a single frequency

I was looking for a more efficient way of finding the magnitude and phase of a signal at a certain frequency without performing an FFT because it produces more information than I need and I came ...
3
votes
2answers
205 views

Auto-correlation function, an inverse problem

$x[n]$ is a complex function $n=0,1,2,\cdots,L-1 $ we assume $x[n]$ is periodic in its index: $x[n+L]=x[n]$ Its auto-correlation function $C[n]$ is uniquely defined as: $$ C[n]=\sum_{i=0}^{L-1} x[i+...