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.

396 questions
Filter by
Sorted by
Tagged with
12 views

Intuition for performing a Fourier Transform on a multidimensional Array

I am currently working on a Software that simulates the behaviour of metals on a microscopic scale for a given set of time intervals in consideration of different stresses and external circumstances. ...
• 101
25 views

Fourier Transform With Weighted Kernel

I am working on a spectral problem and trying to perform a numerical calculation involving an integral of this form $$\int_{\mathbb{R}}dx f(x,k)e^{-ixk}$$ I am sort of interpreting this as a Fourier ...
• 403
44 views

• 615
77 views

How to compute the Fourier transform of a zero-centered Gaussian pulse over a specified range, say $[0,1]$?

Given an even Gaussian kernel $f : \Bbb R \to \Bbb R^+$ $$f(x) = \exp \left(- \frac{1}{2\sigma^2} x^2 \right)$$ and a probability density function (or, if you discretize $[0,1]$, then a probability ...
• 703
20 views

60 views

FFT stride pattern formula

Edit I have found a solution and I posted it below. Thanks to everyone who tried to help! Question I have implemented the radix-2 DIT FFT algorithm but I could not find a formula to determine the ...
• 141
20 views

How can the Cooley-Tukey algorithm for multiplying polynomials be implemented without approximations?

I view the main idea behind the Cooley-Tukey algorithm as follows. Suppose we have two $n$-degree polynomials (with coefficients in $\mathbb{Z}$). We will Evaluate the polynomials on the $2n + 1$ ...
44 views

FFT ELI5 - I mostly get it, but not quite - is my understanding of frames/windows off?

tl/dr: I've got two audio recordings of the same song without timestamps, and I'd like to align them. I believe FFT is the way to go, but while I've got a long way, it feels like I'm right on the ...
• 137
23 views

Finding the second derivative using DFT

Suppose you have an even real-valued function f(x), which is periodic with T=2L. Introducing a grid $$x[n]=-L+ndx,\quad f(x[n])\equiv f_n,$$ $$dx=\frac{2L}{N},\quad n=0,\ldots N-1,$$ its DFT is ...
• 33
33 views

Fourier transform of $f(x)=\frac{1}{1+|x|^n}$ and $f(t)=\frac{1}{\left(1+|x|\right)^n}$ where $n>0$

I was looking for the FT of the symmetric functions: $f(x)=\frac{1}{1+|x|^n}$ and/or $f(x)=\frac{1}{\left(1+|x|\right)^n}$ where $n>0$. Here $-\infty \leq x \leq \infty$. I expect the FT to be ...
25 views

• 848
1 vote
20 views

What is the relation between the input and output coordinates of a Discrete Fourier Transform?

So take a 2D DFT for example: $$F(k,l)=\frac{1}{MN}\sum_{m=0}^{M-1}\sum_{n=0}^{N-1}{f(m,n)e^{-2\pi{i}(\frac{k}{M}m+\frac{l}{N}n)}}$$ Practically, this just means that we take a pre-set matrix of ...
10 views

FFT result relationship when padding with different amount of zeros?

Suppose I have a list a=[1,2,3,4] and have already calculated its DFT: fft(a)=[10.+0.j, -2.+2.j, -2.+0.j, -2.-2.j]. Now I'd like ...
• 101
1 vote
101 views

Why does splitting a polynomial into even and odd degree terms results in polynomials taking as input $x^2$?

The question came up under comments to this YT presentation on FFT as a point taken as self evident, and Math SE seems like a natural place to answer it. The idea is to evaluate a polynomial of degree ...
• 7,835
30 views

How to inverse magnitude and phase Fourier signal

Assume that my measurement equipment returns magnitude and phase of some signal in frequency domain. How to inverse this frequency, magnitude and phase described signal to time domain signal (e.g. in ...
• 23
65 views

Factorization in Fast Fourier Transform

I am trying to understand the FFT using matrix factorization, and there is just one step that I am unclear about. I took a look at this quesetion (Fast Fourier Transform as Matrix Factorization) but ...
• 1,402
93 views

Binary polynomial evaluation

Let $p(x) = a_0 + a_1x + a_2x^2 + \dots + a_{n-1}x^{n-1}$ be a polynomial in $\mathbb{Z}_p[x]$ with binary coefficients, i.e., such that $a_i \in \{0,1\}$ for all $i = 0,1,\dots,n-1$. I like to refer ...
• 259
1 vote
13 views

Extreme sensitivity to the input scale of a Continuous Fourier Transform approximation from Discrete Fourier Transform

Is there a way to 'bypass' the condition $\Delta k=\frac{1}{x_{max}-x_{min}}$, which requires the range of $x$ to be very large when approximating the CFT as a DFT? To contextualise my question: ...
• 897
52 views

2D Fourier transform of periodic structure showing frequencies lower than fundamental frequencies

Is there a possibility that there appears a maxima in the fourier space (in the absolute value of the transform) of a purely periodic structure. I was of the impression that purely periodic structures ...
• 525
phase of Fourier transform when arrives at $\pi$
I'm trying to calculate Phase of "rect" which is like below f(x)=\begin{cases} 1, & \text{if $256<x<768$}.\\ 0, & \text{otherwise}. \end{cases} \...