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.

161 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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
47 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
19 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
33 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
52 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
9 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
16 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
71 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
17 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
1answer
116 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
1answer
42 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 ...
0
votes
0answers
62 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
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
79 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
39 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
1answer
73 views

Example of 1-D Poisson Equation in physics field, engineering field, or others in daily life

In 2D Poisson Equation I have example in electrostatics, $${\Delta ^2}\phi = - \frac{{{\rho _{el}}}}{\varepsilon }.$$ And I need an example of 1D Poisson Equation in daily life. In Engineering field,...
0
votes
0answers
48 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
739 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
54 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
360 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
1answer
121 views

Complexity of Cooley Tukey FFT

http://www.jstor.org/stable/2003354?seq=5#page_scan_tab_contents In the original algorithm of Cooley Tukey it says that in page 298 (11) and (12) the total number of operations is T(r) = rNlogN/...
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
79 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
1answer
169 views

Fast fourier transform

In fast fourier transform, what are the square and the square root of $\omega_{128}$, the primitive 128th root of 1? Is it possible for you to help me on this one?
0
votes
1answer
83 views

Fourier Transform Scaling the magnitude

I have a set of signals $S_1,\dots,S_N$, for which I am numerically computing the Fourier transforms $F_1,\dots,F_N$. Where $S_i$'s and $F_i$'s are C++ vectors (my computations are in C++). My ...
0
votes
0answers
198 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
288 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
2answers
137 views

Understanding FFT through Matlab.

Suppose, I have the following matrix which represents a grayscale image in the spatial domain, ...
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=...
0
votes
0answers
70 views

Discorrespondence between Continous Fourier Transform and Discrete Fourier Transform

My goal is to use a deconvolution method to extract a desired signal (delta peak) out of a convoluted measured function. My problem at first concerns the discrete Fourier Transform (DFT) or FFT ...
0
votes
0answers
590 views

Using FFT to efficiently multiply multiple polynomials modulo N

I have a set of polynomials $P_k$ defined as: $$ P_k = \sum_{n = 0}^{n = N} p_{kn} x^n $$ $N$ is large ($2^{16}$) I would like to perform multiplication on the polynomials: $$ Q = \prod_{k=0}^{k=K}...
0
votes
1answer
284 views

What is the correct order of DFT values when executing the DIT FFT algorithm?

I was checking the correctness through SageMath (and later through Wolfram Alpha and Mathematica) of some simple whiteboard computations that I've done manually (namely, I have tried to compute the ...
0
votes
1answer
32 views

Artificially improving the spectral power of a low frequency signal

First of all, I have to state upfront that I am not sure if this question is valid. Essentially, my question pertains to the frequency of a time series with measurement data. I obtained the ...
0
votes
0answers
93 views

How to express mathematically the frequency image?

I have the following frequency square image N x N How to express this frequency image in mathematical formulation? Thanks
0
votes
0answers
519 views

Plotting Fourier transform of integral function on Matlab

I want to plot the Fourier transform of $$f(t)=\int_{0}^{t}\exp\left(-\frac{1}{1-s^{2}}\right)\,ds,\qquad\text{if }|s|<1,\text{ otherwise }0$$ ...
0
votes
0answers
50 views

Use of FFT with a different definition of multiplication operator

FFT enables us to perform multiplication of polynomials in O(nlogn), where "multiplication" is the standard multiplication over the complex numbers. Is there a general procedure to extend this use of ...
0
votes
0answers
59 views

What does the imaginary part of a set of polar coordinates represent before and after funning an FFT?

My colleague and I are trying to learn stuff that is way above our pay grade. We are curious about the nature of the FFT. We realize that we will most likely not understand the inner workings of the ...
0
votes
0answers
338 views

How to Prove the Fourier Transform of Vertical Line Mathematically?

I've tried to do Fourier transform in Matlab of vertical line. Basically, I make matrix A having size 100x100 and give the value 1s in certain number of coloumn vector, whereas the others is 0s. Here ...
0
votes
0answers
234 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
605 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
496 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
192 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
482 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 ...