Part 1 - introduction

What is DFT?

Let's say we have a signal

$$x = (x_0, x_1, x_2, ..., x_{N-1})$$

$x_n \in \mathbb{C}$, that contains $N$ samples.

Joseph Fourier showed that any signal can be represented as a sum of scaled periodic functions. In case of Discrete Fourier Transform it looks like

$$x_n = \sum_{k=0}^{N-1}y_k * csin(k,n)$$

$x_n$ is $n$-th sample of a signal
$y_k \in \mathbb{C}$ is a scaling factor for k-th complex sinusoid
$k,n \in \mathbb{N}$ are parameters for complex sinusoid
$csin(k,n)$ is a complex sinusoid function

So a single sample $x_n$ is represented as a sum of values of complex sinusoids $csin(k,n)$ scaled by their factors $y_k$. How complex sinusoids look like and what parameters $k,n$ mean is explained in the next part.

DFT is a transform that takes a list of samples $x$ and returns a list of scaling factors $y$.

$$DFT(x) = y = (y_0, y_1, y_2, ..., y_{N-1})$$

This version of transform is also called a Forward Discrete Fourier Transform.

Inverse Discrete Fourier Transform (IDFT) does the opposite - takes a list of scaling factors $y$ and returns the original signal $x$

$$IDFT(y) = x = (x_0, x_1, x_2, ..., x_{N-1})$$

Usages of DFT

DFT is used to:

compute spectrum of a signal ie. what frequencies does it contain
explain how and why digital filters work and compute their frequency response
perform fast convolution

DFT just by computing spectrum of a signal is important by itself and considering that it is indispensible for digital filters, it becomes very important tool.

Also DFT is a good introduction to a field of transforms many of which are used to compress or somehow encode audio, images and video (mp3, ogg, jpg, mpeg).

DFT and FFT

Fast Fourier Transform (FFT) is a fast implementation of DFT. They give exactly the same result, just a method of computing the result is different. DFT computed from definition has complexity $O(n^2)$ whereas FFT has complexity $O(n\log n)$. In many cases names FFT and DFT are used interchangeably.

Some programs or libraries deliberately name their functions fft() and ifft() eg. Octave.

next part