Discrete Fourier Transform (DFT)

DFT transforms the time domain signal samples to the

frequency domain components.
Amplitude

Amplitude
Signal
DFT Spectrum

Time Frequency

DFT is often used to do frequency analysis of a time domain signal.

Four Types of Fourier Transform

2
 DFT: Graphical Example

1000 Hz sinusoid with

32 samples at 8000 Hz
sampling rate.

DFT
Sampling rate
8000 samples = 1 second
32 samples = 32/8000 sec
= 4 millisecond

Frequency
1 second = 1000 cycles
32/8000 sec =
(1000*32/8000=) 4 cycles
3
 DFT Coefficients of Periodic Signals

Periodic
Digital
Signal

Equation of DFT coefficients:

4
 DFT Coefficients of Periodic Signals

Fourier series coefficient ck is periodic of N

Copy

Amplitude
spectrum of the
periodic digital
signal

5
 Example 1
The periodic signal: is sampled at

Solution: Fundamental frequency

a. We match x(t )  sin(2t ) with x(t )  sin(2ft ) and get f = 1 Hz.

Therefore the signal has 1 cycle or 1 period in 1 second.

Sampling rate fs = 4 Hz 1 second has 4 samples.

Hence, there are 4 samples in 1 period for this particular signal.

Sampled signal

6
 Example 1 – contd. (1)

b.

7
Example 1 – contd. (2)

8
On the Way to DFT Formulas

Imagine periodicity of
N samples.

Take first N samples

(index 0 to N -1) as
the input to DFT.

9
 DFT Formulas

Where,

Inverse DFT:

10
 MATLAB Functions

FFT: Fast Fourier Transform

11
 Example 2

Solution:

12
 Example 2 – contd.

Using MATLAB,

13
 Example 3
Inverse DFT of the previous example.

14
 Example 3 – contd.

Using MATLAB,

15
 Relationship Between Frequency Bin k
and Its Associated Frequency in Hz

Frequency step or frequency resolution:

Example 4
In the previous example, if the sampling rate is 10 Hz,

16
 Example 4 – contd.
a.
Sampling period:

For x(3), time index is n = 3, and sampling time instant is

f

b.
Frequency resolution:        
k

Frequency bin number for X(1) is k = 1,

and its corresponding frequency is

Similarly, for X(3) is k = 3, and its

corresponding frequency is

17
 Amplitude and Power Spectrum

Since each calculated DFT coefficient is a complex number, it is not convenient

to plot it versus its frequency index

Amplitude Spectrum:

To find one-sided amplitude spectrum, we double the amplitude.

18
Amplitude and Power Spectrum –contd.

Power Spectrum:

For, one-sided power spectrum:

Phase Spectrum:

19
 Example 5

Solution:

See Example 2.

20
Example 5 – contd. (1)

21
 Example 5 – contd. (2)

Amplitude Spectrum Phase Spectrum

One sided Amplitude Spectrum

Power Spectrum
22
 Example 6

Solution:

23
 Zero Padding for FFT
FFT: Fast Fourier Transform.
A fast version of DFT; It requires signal length to be power of 2.

Therefore, we
need to pad zero
at the end of the
signal.

However, it does
not add any new
information.

24
 Example 7
Consider a digital signal has sampling rate = 10 kHz. For amplitude spectrum we
need frequency resolution of less than 0.5 Hz. For FFT how many data points are
needed?

Solution:

For FFT, we need N to be power of 2.

214 = 16384 < 20000 And 215 = 32768 > 20000

Recalculated frequency resolution,

25
 MATLAB Example - 1

fs

xf = abs(fft(x))/N; %Compute the amplitude spectrum

26
MATLAB Example – contd. (1)

27
MATLAB Example – contd. (2)

28
MATLAB Example – contd. (3)

………..
29
 Effect of Window Size

When applying DFT, we assume the following:

1. Sampled data are periodic to themselves (repeat).

2. Sampled data are continuous to themselves and band limited to

the folding frequency.

1 Hz sinusoid,
with 32
samples

30
 Effect of Window Size –contd. (1)

If the window size is not multiple of waveform cycles:

Discontinuous

31
Effect of Window Size –contd. (2)
2- cycles Mirror Image

Produces
single
frequency

Produces many
harmonics as well.

Spectral
Leakage

The bigger the

discontinuity, the more
32
the leakage
 Reducing Leakage Using Window

To reduce the effect of spectral leakage, a window function can be used

whose amplitude tapers smoothly and gradually toward zero at both ends.

Window function, w(n)

Data sequence, x(n)
Obtained windowed sequence, xw(n)

33
 Example 8
Given,

Calculate,

34
 Different Types of Windows

Rectangular Window (no window):

Triangular Window:

Hamming Window:

Hanning Window:

35
Different Types of Windows –contd.
Window size of 20 samples

36
 Example 9
Problem:

Solution:
Since N = 4, Hamming window function can be found as:

37
 Example 9 – contd. (1)
Windowed sequence:

DFT Sequence:

38
Example 9 – contd. (2)

39
MATLAB Example - 2

40
MATLAB Example – 2 contd.

41
 DFT Matrix

Frequency Spectrum Multiplication Matrix Time-Domain samples

42
 DFT Matrix
Let,

Then

DFT equation:

DFT requires N2 complex multiplications.

43
 FFT
FFT: Fast Fourier Transform

A very efficient algorithm to compute DFT; it requires less multiplication.

The length of input signal, x(n) must be 2m samples, where m is an integer.

Samples N = 2, 4, 8, 16 or so.

If the input length is not 2m, append (pad) zeros to make it 2m.

4 5 1 7 1 4 5 1 7 1 0 0 0
N=5 N = 8, power of 2

44
 DFT to FFT: Decimation in Frequency
DFT:

45
DFT to FFT: Decimation in Frequency
Now decompose into even (k = 2m) and odd (k = 2m+1) sequences.

46
DFT to FFT: Decimation in Frequency

47
DFT to FFT: Decimation in Frequency

12 complex
multiplication

48
DFT to FFT: Decimation in Frequency

For 1024 samples data sequence,

DFT requires 1024×1024 =
1048576 complex multiplications.
FFT requires (1024/2)log(1024) =
5120 complex multiplications.

49
IFFT: Inverse FFT

50
 FFT and IFFT Examples

FFT

Number of complex multiplication =

IFFT

51
 DFT to FFT: Decimation in Time
Split the input sequence x(n) into the even indexed x(2m) and x(2m + 1),
each with N/2 data points.

Using

52
DFT to FFT: Decimation in Time

As,

53
 DFT to FFT: Decimation in Time

First iteration:

Second iteration:

54
 DFT to FFT: Decimation in Time

Third iteration:

2
  2   2  
2 2


WN  e N
 cos   j sin  W e
2 8
e 2
 cos( / 2)  j sin( / 2)   j
 N   N  8

IFFT

55
 FFT and IFFT Examples

FFT

IFFT

56
Fourier Transform Properties (1)
FT is linear:
• Homogeneity
• Additivity

Homogeneity:
DFT
x[] X[]
DFT
kx[] kX[]

Frequency is not
changed.

57
Fourier Transform Properties (2)

Additivity

If : x1[n]  x2 [n]  x3 [n]

Then : Re X 1[ f ]  Re X 2 [ f ]  Re X 3 [ f ]
and Im X 1[ f ]  Im X 2 [ f ]  Im X 3 [ f ]

58
 Fourier Transform Pairs
Delta Function Pairs
in Polar Form

Delta Function

Shifted Delta Function

Same Magnitude,
Different Phase

Shifted Delta Function

59