Lesson 20

Discrete Fourier Transform (DFT)

Usually, we do not have an infinite amount of data which is required by the DTFT. Instead, we have 1 image, a segment of speech, etc. Also, most real- world data are not of the convenient form .

Finally, on a computer, we can not calculate an uncountably infinite (continuum) of frequencies as required by the DTFT.

ACTUAL DATA ANALYSIS on a computer- Use a DFT to look at a finite segment of data.

In our development in the previous section of periodic with the part of the signal that was repeated, we could have assumed that our finite segment of data came from windowing" an infinite length sequence

where is a rectangular window:

is just the samples of between and is 0 everywhere else. Therefore, it is defined , and we can take its DTFT:

So,

as we saw before.

Let's say now that we want to sample (which is continuous and periodic with period ) so we store it on a computer.

Sample :

Assume we want 8 points in frequency - then sample at 8 uniformly spaced points on the unit circle:

Values of frequency are

If we let , what happens? If , we get repetition of the points we sampled so only samples are unique.

Define Discrete Fourier Transform (DFT) as

for , i.e. only look at the distinct sampled frequencies of .

Note: The resolution of the samples of the frequency spectrum is since we sample the spectrum at points that are spaced apart in frequency, that is, .

Note: If we looked at the samples of for all to for frequencies , we would get the closely related Discrete Fourier Series (DFS) which is of course periodic with period since is periodic.

The DFT is just one period of the DFS.

DFT is more useful because who wants to store all the samples of a periodic signal?!! The DFT is just one period of the DFS.

Now

Shorthand Notation for the DFT:

Let root of unity since . You may also write simply as .

Then

is the DFT of your windowed sequence

Ex.

Ex.

Find .

Given and , find .

,

is an integer with and (as usual), find its DFT.

Synthesis: INVERSE DFT

How can we recover from ?

Synthesis formula is

Prove this gives back :

ORTHOGONALITY OF EXPONENTIALS AGAIN!

So,

and

Ex. Find the IDFT of .

Given and , find .

Given and , find .

Selected DFT Properties

1. Linearity.

2. Time shift.

3. Frequency shift.

4. Multiplication.

5. Circular convolution.

6. Real/Even.

If is real, then

If is even, then is real. (For a finite length function to be even, )