Fourier Series, Fourier Transform

# Discrete Fourier Transform (DFT)

The discrete Fourier transform converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency.

The derivation from how you get to the DFT comes from Fourier Series.

We get that

$f_{n}=β_{k=0}F_{k}e_{i(N2Οnkβ)}=β_{k=0}F_{k}W_{nk}$

- Discrete data $f_{n}$ is expressed as a sum of coefficients $F_{k}$
- $W_{nk}$ is a Root of Unity where $W=e_{N2Οiβ}$

To find $F_{k}$, weβll need another useful property of our Nth roots of unity: $W_{jk}W_{βjl}=β_{j=0}W_{j(kβl)}=NΞ΄_{k,l}$

- where $Ξ΄_{k,l}$ is the Kronecker Delta

We can now convert any data set into its Fourier coefficients, and back!

**Inverse DFT:**
$f_{n}=β_{k=0}F_{k}W_{nk}$

**DFT:**
$F_{k}=N1ββ_{n=0}f_{n}W_{βnk}$

The discrete Fourier transform is invertible.

### Splitting DFT into 2 to get to the FFT

The usual DFT of the sequence $f_{n}$ is

$F_{k}=N1ββ_{n=0}f_{n}W_{βnk}$

- where $W$ is a complex exponential, see Root of Unity

We can express $f_{n}$ with DFTs of two new arrays of half the length $g_{n}=21β(f_{n}+f_{n+2Nβ})$ $h_{n}=21β(f_{n}βf_{n+2Nβ})W_{βn}$ where $nβ[0,2Nββ1]$

Then, $F_{even}=G=DFT(g)$ and $F_{odd}=H=DFT(h)$

This is how we can use the FFT.

Lack of standardization

### Properties

As consequences of the properties of $N$th roots of unityβ¦

- The sequence ${F_{k}}$ is
*doubly infinite*and*periodic*. i.e., If we allow $k<0$ or $k>Nβ1$, the $F_{k}$ coefficients repeat. *Conjugate symmetry*: If data $f_{n}$ is real, $F_{k}=F_{Nβk}β$

Hence the $β£F_{k}β£$ are symmetric about $k=2Nβ$