CISC 457, Lecture 16 - 1D Discrete Fourier Transform

We now consider discrete functions, as opposed to the continuous functions of the previous lectures. Discrete functions are defined at discrete positions:

$f(x)$ is defined on integer values of $x$ between $0$ and $N-1$ .

Discrete Fourier Transform (DFT)

The DFT is the discrete analogue of the continuous FT, with a sum replacing the integral:

$\displaystyle F(u) = \sum_{x=0}^{N-1} f(x) \; e^{-\large i {2 \pi x \over N} u}$

The ${2 \pi x \over N}$ term varies in $[0,2 \pi)$ as $x$ varies in $[0,N)$ .

When $u=1$ , the sinusoid corresponding to $e^{\large i {2 \pi x \over N} u}$ has a single cycle in $[0,N)$ . When $u=2$ , the sinusoid has two cycles in $[0,N)$ .

So $u$ corresponds to the wavenumber in the continuous FT. That is, $u$ is the number of cycles in the range $[0,N)$ .

Inverse DFT

The inverse DFT is also analagous to its continuous counterpart:

$\displaystyle f(x) = {1 \over N} \sum_{u=0}^{N-1} F(u) \; e^{\large i {2 \pi u \over N} x}$

Discrete Functions

Discrete Fourier Transform (DFT)

Inverse DFT