Fast Fourier Transform

12092018, 02:54 AM
Post: #1




Fast Fourier Transform
I hope you can help me. I am trying to understand how the fast Fourier transform is calculated (FFT).
Sample problem: n_0 = 0.54 n_1 = 0.66 n_2 = 0.52 where N = 3 The formula to the FFT (I think) is: X_k = Σ( x_n * e^(i * 2 * π * k * n / N) ) for n = 0 to N1 Using the formula above I get: X_0 = 1.62 X_1 = 0 X_2 = 0 But the fft function on the HP Prime returns: 1.72 0.05  0.12124355653i 0.05 + 0.12124355653i However Wolfram Alpha returns: 0.993042 0.0288675 + 0.07i 0.0288675  0.07i I am confused. Are there different fast Fourier transforms or am I missing something obvious? I want to understand the basic calculation before I attempt to understand the Tukey and Cooley algorithm. Any help and insight is appreciated. Thanks! 

12092018, 07:59 AM
(This post was last modified: 12092018 08:52 AM by toshk.)
Post: #2




RE: Fast Fourier Transform
since we don't time interval you are sampling i am assuming 1sec;
hence the frequency is 1; N=3; n=0..N3; w*n=2*pi*f*i*n e^(2*π*i*n/N) your summing formula edited (Σ( x_n * e^(i * 2 * π * k * n / N) ) for n = 0 to N1) in matrix form on Prime X_K=vandermonde([1,e^(2*π*i/3),e^(4*π*i/3)])*[[0.54],[0.66],[0.52]]; and the inverse is true for X_n=inv(vandermonde([1,e^(2*π*i/3),e^(4*π*i/3)]))*[[1.72],[−0.050.12124355653*i],[−0.05+0.12124355653*i]] or simply fft([0.54,0.66,0.52]) Yes there are formulae for fft all depending how samples data are handle;(math, physics, statistics, signals...etc ) However Wolfram Alpha returns: normalize of Prime ans; fft([0.54,0.66,0.52])/1.7211976093 

12092018, 11:14 AM
Post: #3




RE: Fast Fourier Transform
(12092018 02:54 AM)Eddie W. Shore Wrote: Any help and insight is appreciated. Using your sample problem where N = 3: \(x_0 = 0.54\) \(x_1 = 0.66\) \(x_2 = 0.52\) This formula is the definition given for the discrete Fourier transform: \(X_{k}=\sum _{n=0}^{N1}x_{n}\cdot e^{{\frac {2\pi i}{N}}kn}\) We can use the following abbreviations for the 3rd roots of 1: \(\Phi = e^{{\frac {2\pi i}{3}}} = 1 ∠120°\) \(\Psi = \Phi^2 = \Phi^{1} = 1 ∠120°\) \(X_{0}=0.54 \cdot e^{{\frac {2\pi i}{3}} 0\cdot 0}+0.66 \cdot e^{{\frac {2\pi i}{3}} 0\cdot 1}+ 0.52 \cdot e^{{\frac {2\pi i}{3}} 0\cdot 2} = 0.54 + 0.66 + 0.52 = 1.72\) \(X_{1}=0.54 \cdot e^{{\frac {2\pi i}{3}} 1\cdot 0}+0.66 \cdot e^{{\frac {2\pi i}{3}} 1\cdot 1}+ 0.52 \cdot e^{{\frac {2\pi i}{3}} 1\cdot 2} = 0.54 + (0.66 + 0.52\cdot\Phi)\cdot\Phi = 0.05000 i0.12124\) \(X_{2}=0.54 \cdot e^{{\frac {2\pi i}{3}} 2\cdot 0}+0.66 \cdot e^{{\frac {2\pi i}{3}} 2\cdot 1}+ 0.52 \cdot e^{{\frac {2\pi i}{3}} 2\cdot 2} = 0.54 + (0.66 + 0.52\cdot\Psi)\cdot\Psi = 0.05000 +i0.12124\) This is in accordance with the result that the HP Prime returns. HTH Thomas 

12092018, 05:24 PM
Post: #4




RE: Fast Fourier Transform
Thank you so much! You are amazing!
Eddie 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)