×
# Discrete Fourier Transform

### Drawing T-Rex with epicycles

### Aproximating T-Rex with parametric equations

The Discrete Fourier Transform is defined as \begin{aligned} X_{k}&=\dfrac{1}{n}\sum _{n=0}^{N-1}x_{n}\cdot e^{-{\frac {i\,2\pi }{N}}\,kn}\\ &=\sum _{n=0}^{N-1}x_{n}\cdot \left[\cos \left({\frac {2\pi }{N}}kn\right)-i\cdot \sin \left({\frac {2\pi }{N}}kn\right)\right], \end{aligned} where the last expression follows from the first one by Euler's formula. Essentially, it transforms a sequence of $N$ complex numbers $$\displaystyle \mathbf {x} :=x_{0},x_{1},\ldots ,x_{N-1}$$ into another sequence of complex numbers, $$\displaystyle \mathbf {X} :=X_{0},X_{1},\ldots ,X_{N-1}.$$

A few important notes:

- $N =$ number of time samples we have
- $n =$ current sample we're considering $(0 \ldots N-1)$
- $x_n =$ value of the signal at time $n$
- $k =$ current frequency we're considering (0 Hertz up to $N-1$ Hertz)
- $X_k =$ amount of frequency $k$ in the signal (amplitude and phase, a complex number)

Originally the T-Rex curve (signal) is defined with 203 points. After calculating the Fourier coefficient $X_k$, we can easily determine its phase and amplitude for every value of $k$.

The animation with epicycles demonstrates how a simple sum of complex numbers in terms of phases/amplitudes can be nicely visualized as a set of concatenated circles in the complex plane. Each circle represents a Fourier coefficient $X_k$ sorted by amplitude.

It is possible to approximate the T-Rex curve. In this case we can use the Fourier coefficients $X_k$ to define the parametric equations: \begin{eqnarray*} x & = \sum_{k=0}^{N-1} \big( a_k \, \cos\left( k \,t \right) - b_k \, \sin\left( k \,t \right) \big), \\ y & = \sum_{k=0}^{N-1} \big( b_k \, \cos\left( k \,t \right) + a_k \, \sin\left( k \,t \right) \big) \end{eqnarray*} with $t\in[0, 2\pi)$. The coefficients $a_k$ and $b_k$ are the real and imaginary parts of $X_k$.

That's it! If you liked this applet, please let me know: j.ponce@uq.edu.au