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.
0
votes
0answers
8 views
Multiplying Many-Variable Polynomials Using Fast Fourier Transforms
I'm having some trouble figuring out how to use Fast Fourier Transforms to multiply multivariate polynomials. I'm writing a program that intended to expand a large polynomial made of lots of small ...
0
votes
1answer
27 views
Comparability of Analytic Signal with (Discrete) Fourier Analysis
I am working with a finite signal response from an experiment. Basically, I feed in a uniform amplitude sine wave which ramps from 20Hz to 20kHz over the course of 50 seconds, and I read the output, ...
0
votes
1answer
20 views
Confused With using Fast Fourier Transformation for solving equations
As far as I know, the 3 steps of FFT while solving $F_nc = y$ :
Split c into c', c'' such that c' contains elements with even indexes from c and c'' contains the odd ones.
Now we have $F_mc' = y'$ ...
1
vote
1answer
188 views
FFT: Multiplying multiple poynomials in O(KSlogS) time
I have a problem where I have to use the Fast Fourier Transform (FFT) algorithm $K$ polynomials $P_1,...,P_K$ where $\mbox{deg}(P_1) + · · · + \mbox{deg}(P_K) = S$.
I have to show that I can find the ...
0
votes
2answers
32 views
Fast Fourier Transform with Negative Integer Exponent
Given $f(x)=ax+b+\frac{c}{x}$ and $N$, I'd like to ask how to calculate $\sum_{i=1}^{N}f(x)^i$ efficiently using fast Fourier transform?
0
votes
0answers
23 views
Convert Real and Imaginary part from FFT to bands
how can I convert real and imaginary part from FFT to octave bands? I know how to do it for Absolute value, but dont know for Re, Im parts.
Thanks
1
vote
0answers
20 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 ...
1
vote
0answers
55 views
How to implement boundary value in Python using spectral methods
I want to solve the heat equation $$u_t=au_{xx},\quad 0\leq t, \ 0\leq x\leq\pi$$ in Python using spectral methods. I set $u(0,x)=\sin(x)$ as initial value for the time and choose $a=2$. My Code:
<...
0
votes
0answers
18 views
How does scaling in frequency domain affect real space?
I have a 3 dimensional array of real data corresponding to measurements in physical 3D space, and its corresponding data in spectral space.
I want to scale certain specific frequencies in the ...
0
votes
0answers
57 views
Fast Fourier transform of the Gaussian function
As I know, the Fourier transform of the Gaussian function is also Gaussian.
The simple verification for that is shown below.
http://mathworld.wolfram.com/FourierTransformGaussian.html
But fast ...
1
vote
1answer
17 views
Can FFT be used to cluster sound waves based on their similarity?
I am new to this so apologies if the question appears trivial.
Say we have n sound files and we want to cluster them to identify which ones are more similar. I ...
1
vote
0answers
35 views
circulant matrix inversion using fast fourier transform
I am Huda. May I know, if I have a circulant matrix, can I calculate its inversion using fast fourier transform? If yes, I really need an explanation.
Thank you.
1
vote
0answers
6 views
2D FFT with unit stride data access?
I am trying to design a large 1D FFT by splitting N into two smaller FFTs of sizes N1 and N2. This is common approach stemming from the Cooley Tukey Algorithm. My FFT is taking time sampled data in ...
0
votes
0answers
14 views
How to re-scale and do correctly the discrete Fourier transform.
I'm stuck with the re-scaling and the proper choice of parameters in doing the discrete Fourier transform. I explain: Suppose you want to calculate the Fourier transform
$$
F(p) = \frac{1}{2\pi}\int ...
0
votes
0answers
19 views
Average of product of Fourier transform of two signals
I have two signals which depend on x and z, $a(x,z)$ and $b(x,z)$. Their Fourier transform along both directions is denoted as $A(k_x,k_z)$ and $B(k_x,k_z)$, respectively. I would like to compute the ...
0
votes
0answers
27 views
Matrix factorisation of the Fourier matrix
I am currently reading a paper Low Communication FMM-Accelerated FFT on GPUs
In that I am not able to understand the definition of the twiddle factor matrix $T_{P, M}$.
The Fourier matrix $F_N$ is ...
0
votes
0answers
12 views
DFT of a series of RC exponentials
Context: I'm trying use matlab to apply a single-pole filter to a time-domain ramp waveform that is generated by a sequence of time-shifted "RC steps" that are added together.
The time domain voltage ...
0
votes
1answer
22 views
Calculate $Av^{\rightarrow}$ using FFT
Given a vector $v^{\rightarrow} = (v_0,v_1, ... v_{n-1})$
And given the matrix A =
$(a_0, a_1 ... a_{n-1})$
$(a_{n-1}, a_0,...., a_{n-2})$
$(a_{n-2}, a_{n-1}, a_0,...., a_{n-3})$
.....
$(a_1, ......
0
votes
0answers
45 views
Fourier tranform of the derivative
I have been recently studing Fourier transform and there is a proposition that says: If $\lim \limits_{x \to\infty}xf(x)=\lim\limits_{{x}\to -\infty}xf(x)=0$ then $$\hat{f'}(z)=-iz\hat{f}(z)$$
and ...
2
votes
1answer
25 views
Could families of “Airys” and “Bairys” of integer “frequencies” be useful?
A very famous family of functions are the complex exponentials and in the case of real valued functions, the sin and cos functions. They are related by the famous Euler formulas:
$$\exp(i\phi) = \cos(...
0
votes
3answers
37 views
Fast Fourier Transform algoritm - simple explanation(step by step)
I can't find step by step explanation of the FFT algorithm. Why it is faster than common DFT?
As I understand, we calculate DFT for $X$, and for $Y$, then merge them and got the final DFT.
2
votes
0answers
41 views
Any Efficient Multiplication with a Primitive Root over Prime Field?
Description: to multiply the "complex unit" $w^{N/4}$ over a prime field, i.e., $w^N \equiv 1 \bmod (\,p)$ (suppose $p, N$ do provide such primitive root).
I am implementing the radix-4 Number ...
0
votes
0answers
17 views
Fourier odd and even extension of descending steps function
Can anybody help me find even and odd extension of the descending steps function if $f(x)$ be:
\begin{cases}
f(x)= 1 & x\in[0,1]\\
f(x)= (0.5) & x\in[1,2]
\end{cases}
0
votes
0answers
11 views
Should DFT of cosine function be infinite at its frequency?
The Fourier transform of the cosine function is an infinite spike (Dirac delta function) at the frequency of the cosine wave. But it seems most DFT programs give a finite spike corresponding to the ...
0
votes
0answers
42 views
Discrete Fourier transform of sampled sin function nothing like continuous?
So I'm a little confused about what is going on with the discrete Fourier transform.
I tested out discrete Fourier transform with a little python script on a sin function
...
1
vote
1answer
39 views
Coordinates of a vector FFT
I was reading a paper about DFT, at the end he got the relations $Y=\frac{1}{\sqrt N}W_n \cdot y$ and $y=\frac{1}{\sqrt N}W_n \cdot Y$, where $y$ is a vector and $Y$ is the coordinates of that vector ...
1
vote
1answer
14 views
Why is the dot product of two columns $j$ and $k$ in FFT equal to $1+w^{j-k} + \dots + w^{(n-1)(j-k)}$?
The matrix is of the following form:
$\begin{pmatrix}
1 & 1 & \cdots & 1 & 1 \\
1 & w & \cdots & w ^{n-2} & w^{n-1} \\
\vdots & \vdots & \ddots & \vdots &...
2
votes
1answer
65 views
How to minimize sum of matrix-convolutions?
Given $A$, what should be B so that
$\lVert I \circledast A - I \circledast B \rVert _2$
is minimal for any $I$?
$I \in \mathbb{R}^{20x20}, A \in \mathbb{R}^{5x5}, B \in \mathbb{R}^{3x3}. $ Note ...
0
votes
0answers
20 views
Fourier transform of delta(dirac) function-multiplication with exp function
I am trying to find an integral of multiplication exponential function with a delta function.
I know a property of delta function that if I would like to take the integral of the multiplication delta ...
0
votes
0answers
37 views
Informations about Fourier Transform for a Python project (sound manipulation)
I have a project in Python with a friend where we want to manipulate music sound, and we'll need Fourier Transforms, so I made research online and wanted to know if I understand correctly the concepts....
0
votes
0answers
8 views
Most efficient method to find peak frequency of an FFT
I'm using a real to complex fft to get the peak frequency of a signal. What I want to know is the most efficient way to find the index of that peak. I currently use im^2 + re^2 and compare to the ...
0
votes
1answer
42 views
Efficient way to do a Fourrier Transform like operation
Suppose we have two functions $f,g:[0,\infty) \rightarrow [0,\infty)$. Then one can use Fast Fourrier Transforms to quickly compute $\int_0^t f(t-s) g(s) \, ds$ for $t$ in some range of values $[0,T]$ ...
0
votes
2answers
117 views
How to calculate 8-point FFT of data by hand
Given the following data:
Two period sine; samples = [0, 1, 0, -1, 0, 1, 0, -1];
I am asked to calculate the FFT of the sampled data to find the complex coefficients.
I don't necessarily want the ...
0
votes
0answers
11 views
fft algorithm - twidle multiplication
im trying to understand how fft(fast fourier transform) algorithm work and after watching several videos i couldn't understand why there is multiplication with Wn in this specific places and why the ...
0
votes
0answers
19 views
Not getting expected results with FFT
So I made this virtual car that moves at a velocity that is the sum of three different sine waves (whose individual frequencies I know). I constructed this velocity time graph
Then I perform a FFT on ...
0
votes
0answers
10 views
Discrete Hartley Transform when N=8
Hi I am currently studying FHT Algorithm but have a hard time to grasp it.
I want to calculate FHT when N=8.
http://mathworld.wolfram.com/HartleyTransform.html
thanks to (19) of the upper link, the ...
1
vote
1answer
14 views
Discrete Hartley Transform Diagram
Hi I am looking for DHT diagram(or pseudo code) for N=8
but cannot gain any result.
since I am not major in math, cannot grasp whole article.
So is there anyone who can draw DHT diagram in N=8 for ...
0
votes
0answers
42 views
Using fft() in Matlab
I have a function defined like:
$$x(t)=2e^{-\frac{r}{2}t}\sin\left(\frac{1}{2}\sqrt{16\pi^2-r^2}\cdot t\right)\left(\frac{\Theta(t)}{\sqrt{16\pi^2-r^2}}\right)
$$ Where $\Theta(t)$ is the Heaviside ...
0
votes
0answers
11 views
How to assess the convergence of a time series towards a periodic signal and assess the sufficiency of the sample size?
I have a sampled temporal signal, result of a transient fluid simulation. At the beginning the flow is being established, so the first few seconds of signal should be ignored (question : is there a ...
2
votes
0answers
29 views
Increasing frequency resolution of FFT on a windowed sample of a signal
Okay, this gets a bit technical, let me explain the background. In doing loudspeaker measurements for its direct sound in normal rooms that have reflections, what we do is measure the whole impulse ...
1
vote
0answers
60 views
Filter a signal using FFT
I need to filter a signal without it losing its properties so that later that signal is inserted into an artificial neural network. I'm using the R and the signal library, I thought about using a low-...
1
vote
0answers
26 views
Difference between NFFTs, NUFFTs, USFFTs (for CT purposes)
I am trying to understand for what cases and in what way NUFFTs would be useful for CT reconstruction. Therefore, I am trying to create an overview for myself that starts with the "easy" problems ...
1
vote
0answers
33 views
What is the Discrete Fourier Transform of a periodic sequence?
Shor's algorithm utilises the properties of quantum computers to find $r$ in,
$$
a^r = 1 \mod n
$$
wherein $r$ is even and $a^{r/2} + 1\neq 0$. However I haven't been able to find any resources in how ...
0
votes
1answer
32 views
How to deduce formulae of signal waves? [closed]
For a highschool assessment I am conducting a research on vowel inventories of numerous Turkish speakers. My question is in two parts: Firstly I would like to ask if it is possible (if yes, how so?) ...
0
votes
0answers
20 views
Two dimentional discrete Fourier Transform, dimentions when performing convolution
I have trouble wrapping my head around the way 2d convoluion with fft is performed. I understand how 2d convolution works when performed clasically (technically I'm interested in cross-correlation as ...
1
vote
0answers
35 views
Finding working modulus for FFT over finite fields
I would like to implement multiplication of polynomials using NTT. I followed Number-theoretic transform (integer DFT) and it seems to work.
Now I would like to implement multiplication of ...
0
votes
1answer
88 views
Fourier coefficients computed by MATLAB fft function don't match exact ones
I am trying to find out the Fourier coefficients of function $\cos\left(\frac{\pi x}{7}\right)$ on the interval of $[0\,,\,7]$ by using MATLAB built-in function fft in order to verify my own DFT and ...
0
votes
0answers
21 views
Polar representation of a function in Fourier transform
I need to perform a Fourier transform of the function which has the following form
$$\hat{f}(\omega)=\mathcal{F}(\mathbb{e}^{i S(x)}R(x)),$$
where both $R(x)$ and $S(x)$ are real. I am wondering if ...
0
votes
0answers
14 views
DFT on a Vector $p(x) = x^n$
Let $m \in \Bbb N$, $n \in \Bbb N$, such that $m$ divides $n$.
What is the output of a $DFT_m$ of order $m$ when the input is the coefficient vector of the polynomial $p(x) = x^n$?
Well this ...
0
votes
1answer
37 views
Simple DFT Coefficients => Amplitude/Frequencies
Im trying on DFT and FFT in Python with numpy and pyplot.
My Sample Vector is
x = np.array([1,2,4,3]
The DFT coefficients for that vector are
...
