Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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