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.

167 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
0answers
236 views

Optimization for getting amplitude of FFT results for real signals

I need to compute amplitude of FFT result for real signals, which means that I don't need the precise result of FFT or phase information of the result. So I think I don't need to implement the ...
0
votes
0answers
619 views

Why, traditionally, does FFT use complex numbers as a wrapper for magnitude and phase?

I've read questions like this one, this one, and this one which ask why we use complex numbers instead of real numbers, and that's one half of the question, but the other half, which I've never seen ...
0
votes
1answer
508 views

NTT for fast multiplication of polynomials over a finite field, and the connection to polynomial evaluation

Trying to code NTT and INTT in order to have faster polynomial multiplication. That has been extremely mind boggling for me. The polynomials are over a finite field $GF(q)$. I've already coded some ...
0
votes
0answers
76 views

Analysis of a linear increase in standard divination. What might cause a linear increase in floating point error?

Background: We are doing mathematical transformations on large matrices of inline fraunhofer holography data (the nature of this isn't really important, but if you are curious, essentially it is a ...
0
votes
0answers
194 views

Chossing a prime for fft of size $2^n$

I have a $p$ degree polynomial where $p$ is prime, I want to find the value of this polynomial at all points from $1$ to $p-1$,to make the fft on this polynomial easier I padded it with zeroes up to ...
0
votes
0answers
130 views

FFT butterfly diagram

I got confused in the FFT butterfly diagram. Can someone please help me understand it? If I have the vector $x = (-3, -2, -1, 0, 1, 2, 3, 4)$, and I want to apply FFT to it using the Butterfly ...
0
votes
2answers
489 views

Fourier series Coefficients and wolframalpha

1) Please can my answers be checked, including my final Fourier series. 2) Is it possible to use Wolframalpha to check my answers? If so, how will I go about doing this? Deduce the Fourier series ...
0
votes
0answers
232 views

How to evaluate an integral using FFT when the integrand is sensitive to discretization points?

I am looking to find the following function using a FFT method: \begin{equation} g(x)=\frac{1}{2\pi} \int_{-m\pi}^{m\pi} \psi(u) \mathrm{e}^{iux}du \end{equation} I start by discretizing $ x \in [...
0
votes
0answers
48 views

How to calculate the integral of a fourier trasfom

I have to calculate this integral : $\int_{-\infty}^{+\infty} \hat G(\omega)e^{i\frac{\pi}{2}\omega}d\omega$ ($\hat G(\omega)$ is the Fourier trasform) with: $G:x\in \Bbb{R}\to \begin{cases} g(x), ...
0
votes
0answers
55 views

Is my formula for DFT correct?

I'm doing "Digital Image" online course. I tried to solve the following question $x(n_1,n_2)$ is defined as $x(n_1,n_2)=(−1)^{(n_1+n_2)}$ when $0≤n_1$, $n_2≤2$ and zero elsewhere. Denote by $X(k_1,k_2)...
0
votes
0answers
113 views

Doesn't the recursive Fast Fourier Transform violate f(-x) =/= f(x) for odd functions?

When you recursively split into $Y_{even}$ and $Y_{odd}$, from the second recursion onwards don't these sets have their even-ness and odd-ness violated? I.e., assume you are running the FFT algorithm ...
0
votes
0answers
800 views

Fast fourier transform in sliding window of a signal

I would like to detect the change of the frequency content through a real signal using sliding window as shown in following figure. Fixed size sliding window on a signal However, applying fourier ...
0
votes
0answers
179 views

Does the ring in this Fast Fourier Transform image of a hexagonally close packed structure have significance?

I have a picture of a hexagonally close-packed lattice and I took the FFT of the image using ImageJ. Below are the results. I expected the FFT to also be a lattice with reciprocal lattice spacing, I ...
0
votes
0answers
518 views

Why FFT algorithm (Cooley-Tukey) takes O(nlogn)?

I was wondering how this algorithm can be formally interpreted with an upper bound n*log(n). There's some formal proof for this? I would appreciate if somebody can help me. Thank you.
0
votes
0answers
28 views

Can any integral of this form be written as a sum of convolutions?

Does the second equality always hold? $$ I(x) \equiv \int dy F(y,x-y) = \sum_{i=1}^{N}\int dy f_i(y)g_i(x-y) $$ Motivation: The first integral is not obviously a convolution that I could calculate ...
0
votes
0answers
396 views

Worked out FFT example per Hand

Can anyone please show me the worked out example of FFT. Suppose for the signal x = (1/2, 1/4, 0, 1/4 , 1/2, 1/4, 0, 1/4). What I think I know: First I need to do the bit reversing, I get x = (1/...
-1
votes
1answer
86 views

Is $fft^{-1}(fft(x)\times fft(y))$ integer?

I have some troubles with the following question: Let ($x_0, x_1, ..., x_{N-1}$) and ($y_0, y_1, ..., y_{N-1}$) be two sequences of integers from the set {$0,1,...,9$}. Let ($p_0, p_1, ..., p_{N-1}$) ...