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.

1
vote
0answers
59 views

Sampling and the Discrete Fourier Transform

Suppose $f:\mathbb{R}\rightarrow\mathbb{C}$. We'd like to take the Fourier Transform of this function, defined as $$F(s) = \int_{-\infty}^\infty f(x)e^{-i \, 2\pi \, s \, x}dx.$$ However, a computer ...
1
vote
0answers
37 views

Why is there periodicity in the output of Richard Voss' fractional Brownian motion?

I am trying to figure out why the output of fractional Brownian motion (fBm) as described by Richard Voss (Random fractal forgeries. In: Fundamental Algorithms for Computer Graphics, R. A. Earnshaw (...
1
vote
0answers
279 views

analyze convolution in spatial domain against multiplication in frequency domain

Lets say I have a image of $NxN$ and a separable filter that I want to apply on it. there are 2 ways to do that: 1. By convolution in spatial domain. 2. By multiplication in frequency domain. I need ...
1
vote
0answers
99 views

Can downsampling create energy at the Nyquist frequency?

I am a bit surprised by the following and would like to share it with you. I expect I am mistaken somewhere and will be happy to be corrected. I have searched StackExchange not only in Mathematics ...
0
votes
0answers
24 views

Linear deconvolution using FFT

I want to deconvolve a filtered signal with a known input to recover the filter used using FFTs. Let $x$ be a vector of length $N$ and $h$ a filter of length $K$ where $N > K$. Let $x \ast h = y$,...
0
votes
0answers
11 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)$ ...
0
votes
0answers
10 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 ...
0
votes
0answers
36 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. ...
0
votes
0answers
9 views

How to convert X,Y Cartesian data to 3D spectrum (frequency, direction, spectral density)?

My question is as follows. I have x,y motion. normally I would ignore directionality and just look at the spectral density of each by performing a FFT on it. For my current problem directionality is ...
0
votes
0answers
17 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
0answers
24 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
0
votes
0answers
20 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
153 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 ...
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
23 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
29 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
13 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
0answers
46 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 ...
0
votes
0answers
18 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
12 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
43 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 ...
0
votes
0answers
24 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
43 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
0answers
12 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
21 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
11 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 ...
0
votes
0answers
54 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
15 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 ...
0
votes
0answers
24 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 ...
0
votes
0answers
24 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
15 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
0answers
59 views

Fourier transform of the ln of a variable

Consider the following Fourier transform: $$\hat{f}(\ln \xi) = \int_{-\infty}^{+\infty} f(x) e^{-2\pi i x \ln{\xi}} \, \, dx $$ Assuming I can calculate $\hat{f}(\ln \xi)$, how can I go from $\hat{f}(\...
0
votes
0answers
50 views

Spectral Derivatives and Wave Numbers

This author is explaining spectral derivatives on a discritized domain with $N$ grid points, using Fast Fourier Transform (fft) and inverse fourier transform (ifft). The distance between grid points ...
0
votes
0answers
91 views

fft of sawtooth signal

I have a very basic question. sorry for such a naive question! I have a sawtooth signal which look like this: this is how I generated this signal : ...
0
votes
0answers
18 views

convolution of nearly periodic data

Suppose I have two vectors $x,y\in\mathbb{C}^n$. I am interested in efficient calculation of the convolution $$z(k) = \sum_{i=0}^{n-1}x(i)y(i+k)$$ for $k=0,...,n-1$. Note that $y$ is taken nearly ...
0
votes
0answers
31 views

Fourier Transform with translation $e^{-4t} µ(t+5)$

note that µ is the Heaviside function. I wonder if the correct transform with translation/shifting would be: $$F(w)= \biggl(\frac{1}{4+iw}\biggl)(e^{5iw})$$
0
votes
0answers
19 views

Where is the inverse fourier in this solution?

I am trying to understand the relationship between the Wiener-Khinchin Theorem and the Autocorrelation Function. I am learning this by myself and just started learning about Fourier Transforms, so I ...
0
votes
0answers
68 views

fit curve with fft and calculate it's derivatives

Here is my issue: I am trying an algorithm using FFT to fit and get a function's approximative in order and calculate its derivative in an easier way (for any data), but I get some discontinuity. At ...
0
votes
0answers
37 views

confused doing FFT

I have data vibration in excel, the first row is time, and the second is vibration. I want to use fft to analyze the vibration. Because, i'm new to dsp, i don't know, what is sampling frecuency, etc. ...
0
votes
0answers
41 views

Fourier transform on formal series

I am searching for a "Fourier transform" $T$ on formal series with coefficients in dyadic numbers, such that: $$T(fg)=T(f)*T(g)$$ Where $*$ is the "coefficient by coefficient " multiplication $(\sum ...
0
votes
0answers
618 views

Compute Transfer Function from FFT of Input and Output

I tried the method described in a previous answer (https://math.stackexchange.com/a/718856/451691) to compute the transfer function of a system I am studying, where: In(t) = a(t); Out(t) = b(t) I ...
0
votes
0answers
51 views

Low Pass Filter using FFT up to the Nth overtone

I'm writing a program in c# that uses Meta.Numerics to calculate the FFT of a signal recorded during one cycle. The overtones are presented as complex numbers. Now I would like to reconstruct the ...
0
votes
0answers
49 views

How can I interpret the discrete impulse response measurement?

Assume that we have our discrete transfer function $G(e^{j\omega_k})$ where, $k = \frac{\pi k}{M} , k = 0, \dots , M$. If we want to find Markov-parameters $g_k$ from the impulse response $$g_k = \...
0
votes
0answers
267 views

How to use FFT algorithm to multiply to positive integers in base 2?

We're given two positive integers of length $n$ in binary representation. Design an algorithm which divides the numbers into ${n \over k}$ blocks of size $k=\lg n$ using FFT algorithm. We ...
0
votes
0answers
25 views

is there special FFT technique for function of angle argument?

I started working with molecular modelling and stuck at the following problem. I need to calculate dihedral interaction energy by hand. The simplest form of the equation is $V = \frac{Va}{2} * \left( ...
0
votes
0answers
66 views

Fast Fourier Transform in C

I have a time domain data of an electric field(windowed) at a point, say $(x,y)$. The time is around 33 picoseconds and sampled at 20,000 points. To convert this data to frequency domain I am using ...
0
votes
0answers
177 views

DFT Shift theorem

I am building a home power meter to use in my house. I sent my board to be manufactured that's why at the moment I am simulating an AC power line and applying an FFT in order to calculate all the ...
0
votes
0answers
225 views

FFT with nonsquare matrix

I want to compute the $K$ sums: $$ f_k = \sum_{j=0}^{N-1} a_j e^{i \frac{2 \pi j k}{K}} $$ for $f_0,f_1,...f_{K-1}$. Now if $K = N$, then this is the usual DFT, but in my application $K \ne N$, as I ...
0
votes
0answers
88 views

The fastest algorithm to calculate the $C^n$

I am looking for the fastest algorithm to calculate the $$C^n$$ where the $C$ is some algebraic constant. For example it can be $$C=\frac{\sqrt3-1}{2}$$ or one of the root of $$x^5+x^2-1=0$$ If $$C=...