The DFT

Whereas the CTFT takes a continuous signal and outputs a continuous frequency spectrum and the DTFT takes a discrete signal and outputs a continuous, periodic frequecy spectrum, the Discrete Fourier Transform takes a discrete finite signal and outputs a discrete frequency spectrum. This is useful for signal processing because we cannot store infinite signals in a computer’s memory.

Definition 1

Definition 2

Convolution and the DFT

Circular Convolution

When the DFT coefficients of two signals are multiplied, the resulting coefficients describe a circular convolution of the original two signals.

Definition 3

A circular convolution between two finite sequences is given by

The mechanics of the circular convolution are the same as that of the regular convolution, except the signal is circularly shifted as shown in Figure 1.

A circular convolution is equivalent to a periodic convolution over a single period.

Linear Convolution with the DFT

  1. Take the Inverse DFT

If we compute the DTFT of each periodic extension, then

and the IDTFT of this will be

Block Convolutions

The first method of block convolution is the overlap-add method.

  1. Since convolution is linear,

  2. Compute the DFTs, multiply them, and take the inverse DFT.

The other method of block convolution is the overlap-save method.

  1. Compute the DFTs, multiply the coefficients, and compute the inverse DFT.

FFT

Definition 4

It works by exploiting properties of the Nth roots of unity.

Definition 5

The roots of unity have the following properties.

Theorem 1

The Nth roots of unity are conjugate symmetric.

Theorem 2

The Nth roots of unity are periodic in N.

Theorem 3

Decimation in Time

These are just the DFTs of the even and odd elements of the signal!

Decimation in Frequency

The decimation in frequency approach is very similar to the decimation in time approach except instead we split the frequency components

Last updated