# 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. ...
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 ...
44 views

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

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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
### phase of Fourier transform when arrives at $\pi$
I'm trying to calculate Phase of "rect" which is like below \begin{equation} f(x)=\begin{cases} 1, & \text{if $256<x<768$}.\\ 0, & \text{otherwise}. \end{cases} \...