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

220 questions
7 views

### Number of Computation(Additions and Multiplications) in Prime Factor FFT [on hold]

How to calculate the number of additions and multiplications in Prime-factor FFT. like for 1008-point FFT or 432-point FFT.
10 views

### Analytical expression for PSD

Is it possible to obtain an analytical expression for the PSD? The PSD is defined as follows, $S(\omega) = lim_{T \rightarrow \infty} \frac{1}{T} |Y(\omega)|^2$ Assuming there is $Y(\omega)$ ...
9 views

### Unexpected results for Fourier synthesis using IFFT in 2D

I am trying to recover a 2D function using inverse DFT, to my understanding the IDFT outputs the coefficients of the fourier series of the original function up to the Nyquist frequency. So for ...
41 views

### DFT is not a sampling of FT?

From wikipedia: The discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time ...
28 views

### even/odd signals and their FFT

I want to use the following property of the Fourier transform: Even functions have even transforms; odd functions have odd transforms. in mathematical terms: if $f(t)$ is a function that has an ...
63 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 ...
25 views

### How does matrix vector multiplication scale a norm of vector?

Given a square Vandermonde matrix $\mathbf{V} =$\begin{pmatrix} 1 & x_0 & x_0^2 & \ldots x_0^{n-1}\\ 1 & x_1 & x_1^2 & \ldots x_1^{n-1}\\ \vdots\\ 1 & x_{n-1} & x_{n-1}...
33 views

### Circulant matrix-vector product procedure

A circulant matrix $C$ can be represented as $$C = F^{-1} \mbox{diag}(Fc) \, F$$ When $C$ is multiplied by vector $b$ $$C b = F^{-1} \mbox{diag}(Fc) \, (F b)$$ My question only about procedure. ...
33 views

### Applying Fourier transform to represent equation with integral as a sum of variables

According to a paper the equation with integral $\int_{-\infty}^{\infty}dx \rho_0(\lambda)e^{-b\lambda}=1/N$ (#1) where $\rho_0(\lambda)$ is a distribution function, $N$ is a natural number, can be ...
17 views

### Is it possible to use FFT to derive a Fourier series fitting to data?

I want to do something like what is done in this question about fitting , ie find a Fourier series that approximates a continuous but complicated function. However I want to know whether it is ...
28 views

20 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 ...
28 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 ...
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 ...
23 views

22 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 ...
39 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....
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]$ ...
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 ...
150 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 ...