Fast Fourier Transform

[Thomas Klemm]

(12-09-2018 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}^{N-1}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