# Questions tagged [fast-fourier-transform]

Use this tag for questions related to the fast Fourier transform, an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components.

253 questions
Filter by
Sorted by
Tagged with
13 views

### Is possible to use negative exponents in FFT Algorithm?

I want to apply the FFT to discover all possible sum in two vector. Let's say it's a = [-1,2,3] and b = [4,5]. I wanted to use FFT to find all possible sums, putting the numbers of the vector as ...
39 views

24 views

### The time complexity of integer multiplication by FFT without any sophistication.

David Harvey and Joris van der Hoeven proved at this year that the product of two integers whose bit length is $O(n)$ can be computed in $O(n\log n)$. I've heard that the optimal complexity of ...
20 views

### scaling magnitude of the dft

I have seen a lot of question like this, but still I have doubts about the answer. When using the fft in matlab the solution need to be divided by the length of the signal (N). I have seen many ...
23 views

### Convert overlap save method to multi-bank filter

I want to understand what does mean by mixing bin in this article "Turning Overlap-Save into a Multiband Mixing, Downsampling Filter Bank" and why should the filter length be multiple of decimation ...
22 views

### Deconvolution of probability density functions

I am trying to implement a code that yields the probability density function $p(f)$, given knowledge of two other PDFs, $p(\omega)$ and $p(\theta)$. The whole procedure is based on the paper ...
12 views

286 views

### Question about roots of unity in the Fast Fourier Transform

I am learning about the Fast Fourier Transform, which converts a polynomial from its coefficient representation into its point-wise form using divide-and-conquer. The Fast Fourier Transform evaluates ...
43 views

### FFT-Filter frequency cutoff and negative frequencies

When using a standard implementation for the FFT, for example the numpy implementation, the Fourier transformed output is in so called "standard" order. To quote the numpy implemenetation If $A$ = ...
90 views

### Determine the shift in tonal center of a piece of music.

Starting with a sampled audio signal of acapella vocals, I am interested in determining the shift in the tonal center of the music through the performance. As a choir progresses through a ...
13 views

### Siegman Discrete Fourier Transform notation misunderstanding

I was reading A.E. Siegman's Fiber Fourier Optics paper and came across the following equation which was described as the DFT:enter image description here and I don't understand why it's that equation ...
46 views

### FFT in Python without numpy yields other result than with numpy

I tried to find an implementation of the FFT algorithm in Python without the use of the numpy library. I found one and it seemed to work, but when I tested it on a more realistic sample it failed and ...
32 views

34 views

### Why must the length of a sequence under the discrete Fourier transform be equal to the input sequence length?

Let's consider a continuous signal, $f(t)$, which has been sampled $N$ times, with spacing $T$ between samples. We denote the $N$ samples $f, f, ..., f[N-1]$. The Fourier transform of the ...
88 views

### Discrete Fourier transform of $(1,1,1,1)$

I am asked to determine the Fourier transform of $(1,1,1,1)$. In the solution I found this: I don't get how is he transitioning from the $\omega$'s to $-i, i, -1, 1$ etc... How to break it down, so ...
133 views

### Bandlimited reconstruction of sampled periodic functions.

This has to do with the Nyquist-Shannon sampling and reconstruction theorem and the so-called Whittaker–Shannon interpolation formula. I had previously asked an ancillary question about this here but ...
29 views

### Problem in Wiener-Khinchin of a discrete signal using matlab

I am trying to calculate the PSD from the autocorrelation using the Wiener Khinchin theorem. In particular I am trying to do this starting from the matlab formula xcorr, which produces an array of ...
45 views

### Quantify measure of oscillations in periodic time series data

I have a periodic time series data that are constantly sent to server from machines. It has uneven sampling rate. I want to quantify measure of oscillations by combining information about frequency +...
30 views

### Shifting phase in Fourier frequency domain

Suppose I have 2 identical Gaussian pulses, but separated by some phase offset. If I take the Fourier transform of it to move from time domain to frequency domain, how can I manipulate the phase terms ...
23 views

### psd of a signal using the welch procedure

I have seen that it is possible to calculate the PSD of a signal u , doing this procedure U=fft(u) psd=U*conj(U) Is this the Welch method? can you someone recommend me a book or a paper that ...
56 views

### dimension after fast fourier transform

I am doing a frequency analysis. Reading some literature I have seen that when you perform an fft on a time history of a variable, the dimension of this variable remains the same also after the ...
75 views

### Imaginary Numbers and DFT

I'm not a math guy per se, but i am trying to understand the DFT. I get to the point where imaginary numbers are used with Euler's formula. What I don't understand is why we need an imaginary plane ...
23 views

### How to interpolate under specific conditions using FFT?

I am solving a very specific problem where I need to apply FFT to interpolate. I am given two sets of distinct points $A = (a_{1}, a_{2}, ... , a_{n})$ and $B = (b_{1}, b_{2}, ..., b_{n})$. Using $B$, ...
51 views

### Linear deconvolution using FFT

I want to deconvolve a filtered signal with a known input to recover the filter used using FFTs. Let $x$ be a vector of length $N$ and $h$ a filter of length $K$ where $N > K$. Let $x \ast h = y$,...
I have a covariance matrix $Q$ and need to find $Q^{-1}$. Here, $Q$ is a Toeplitz matrix. I want to calculate the inverse of the matrix with FFT-based methods rather than the conventional ones like ...