PPT6 DFT FFT - Lecture notes 6 PDF

Preview

Summary

Course Instructor: Abul Kalam Azad...

Description

Fourier Analysis  What is Fourier series? Fourier first showed that any periodic waveform can be synthesized by a sum of sinusoids that are harmonically related. Any continuous-time periodic waveform can be represented by the Fourier series as follows:

Since

Thus

Where

{Xo, X1, X2, …, X} are the Fourier series coefficients . Each coefficient controls the amplitude of the corresponding harmonic required to construct a signal. 

How to calculate the Fourier series coefficients of a periodic signal?

The Fourier series representation of signal can be represented as

Xk of the above equation can be found by

where T0 =1/f0 = Fundamental period.



Example: Determine the Fourier series coefficients of the following square wave whose fundamental frequency is 25 Hz.

Page 1 of 22

Solution:

Since, e-j2k = 1 and, e-jk = 1 if k is even and e-jk = -1 if k is odd thus

Using the following equation we can find the value of X0 when k = 0.

K = 0 in the above equation gives X0 = 0. Thus

So the signal can be represented by Fourier series as

since 1/j = e-j/2 hence

If we are only interested in the magnitude of each coefficient, we have

Page 2 of 22



How to calculate the Fourier transform of a non-periodic D-T signal?

Fourier series help us to find the spectrum of periodic signals only. As most of the signals are not periodic, another tool is needed to find the spectrum of non-periodic (aperiodic) signals. This is called the Fourier Transform. Let x(t) be a non-periodic continuous-time signal, x[n] is the samples of x(t) such that x[n] = x(nTs). The spectrum of x[n] is given by the Fourier transform as follows:

where ω = ωTs rad and ω = 2πf0 rad/s. 

Prove that the Fourier spectrum of a non-periodic signal is periodic.

It is interesting to note that non-periodic signals have periodic spectrum that repeats every 2π.

Note that e-j2nk = 1. Page 3 of 22



Effect of sampling rate:

Fig: The continuous-time signal can exactly be reconstructed from the D-T signal

Fig: Lower sampling rate gives rise to aliasing effect 

Shannon sampling theorem and aliasing effect

If the signal has frequency components beyond | |, after sampling, these frequency components will affect the other replicas in the spectrum. Even with an ideal low pass filter, the original signal cannot be reconstructed. This is the so-called aliasing effect. Shannon Sampling Theorem for general non-periodic signals

A continuous-time non-periodic signal x(t) with frequencies no higher than fmax can be reconstructed exactly from its samples x[n] = x(nTs) if the samples are taken at a rate of fs = 1/Ts that is greater than 2fmax (Nyquist rate).

Page 4 of 22





Solution of aliasing problem 

Increase the sampling rate such that fs  2fmax



Use anti-aliasing filter first: Pre-filter the input signal such that it will never has frequency components beyond ||.

What is the Shannon Sampling theorem? Given that the maximum frequency of a piece of music is 100 kHz. The music is sampled at 44.1 kHz. Do you think there is aliasing problem? If the sampling frequency cannot be changed but it is known that human ear cannot hear signal of frequency higher than 20 kHz, how would you modify the system to solve the aliasing problem? Explain your answer clearly.

Answer: Shannon Sampling Theorem: A bandlimited continuous-time signal, with highest frequency fmax Hz, can be uniquely recovered from its samples provided that the sampling rate FS ≥ 2 fmax samples/second. Explanation of Shannon Sampling Theorem: Suppose we have a continuous-time signal x(t) which has frequencies no higher than fmax. If this signal is sampled at a rate of FS = 1/TS, where FS ≥ 2 fmax, then the signal x(t) can be reconstructed uniquely from its samples x[n] = x(nTS). Aliasing problem: The maximum frequency of the piece of music is 100 kHz. If the music is sampled at 44.1 kHz, there is aliasing problem because sampling rate FS (= 44.1 kHz) < 2 fmax (=2×100 kHz). Solution to Aliasing problem: There are two ways to solve the aliasing problem: (1) To increase the sampling rate such that FS ≥ 2 fmax and (2) To pre-filter the signal using an anti-aliasing filter before sampling it. Page 5 of 22

System Modification: In this case, as the sampling rate cannot be changed and human ear cannot hear signal of frequency higher than 20 kHz, we can use an anti-aliasing filter to remove all frequency components above 20 KHz before sampling it. Explanation of the modified system: By using the anti-aliasing pre-filter, we have now an audio signal with maximum frequency of 20 kHz. If it is now sampled at an rate of 44.1 kHz, the criteria of Shannon sampling theorem is satisfied because FS (= 44.1 kHz) > 2 fmax (=2×20 kHz) Thus, there is no aliasing problem now and the original audio signal (up to 20 kHz in this case) can be exactly reconstructed from the samples.  What is the discrete Fourier transform Spectrum of non-periodic discrete-time signals is periodic and continuous and, thus difficult to be handled by computer. Moreover, since the spectrum is periodic, there is no point to keep all periods and one period is enough. As the computer cannot handle continuous data, we can only keep some samples of the spectrum to represent the spectrum. This approach is called Discrete Fourier Transform (DFT). The Fourier transform of a non-periodic discrete sequence is given by

Assume x[n] is a non-periodic sequence with N samples, i.e. {x[n] : n = 0,1, ..., N-1}

If we are now interested only in N equally spaced frequencies of 1 period of the Fourier spectrum, i.e.,

for k = 0, 1, 2, ............................ N-1 Here

Discrete Fourier Transform (DFT) is exactly the output of the Fourier Transform of a non-periodic sequence at some particular frequencies.

Page 6 of 22



Prove that discrete Fourier transform is periodic

Here, e-j2n =1 

What is Inverse discrete Fourier transform?

If we know X[k], we can reconstruct back the signal x[n] via the inverse discrete Fourier transform defined as



How can we get back to the signal using Inverse discrete Fourier transform?

It can be proved as follows:

Because the value of the terms in the square bracket is

Page 7 of 22

 Properties of DFT 1. Linear property: If X1[k] is the DFT of x1[n] and X 2[k] is the DFT of x2[n], then 2.

periodicity: If X[k] is the DFT of x[n] with N samples,

3.

Shift property: If X[k] is the DFT of x[n], the DFT of y[n] = x[n-m] is

Mathematical Problem: on DFT (a) Find the DFT of the sequence x(n) = [1, 0, 0, 1]. (b) Draw time vs x(n) if x(n) is obtained by sampling a continuous-time signal with a sampling rate of 8 kHz. Also represent the DFT by the plots of (c) magnitude versus angular frequency and (d) phase versus angular frequency. Solution: DFT of x(n) is given by N 1

X (k )   x (n)e  j 2kn /N n 0 3

X (0)   x (n )e j 2 0 n /4  x (0)  x (1)  x (2)  x (3)  1  0  0  1  2 n 0

 X (0)  2 and X (0)  0 3

X (1)   x(n)e j2  1 n/4  x (0)e j2 1* 0/4  x (1)e j2 1*1/4  x (2)e  j2 1* 2/4  x (3)e j2 1* 3/4 n 0

 1  0  0  1e j 3 /2  1  j  X (1)  2 and X (1)  tan 1 (1)  450 3

X (2)   x(n)e  j 2 2 n /4  x(0)e  j 2 2*0 /4  x (1)e  j 2 2*1 /4  x (2)e  j 2 2*2 /4  x (3)e  j 2  2*3 /4 n 0

 1  0  0  1e j 3  1  1  0  X (2)  and X (2) is indeterminate 3

X (3)   x (n )e j 2  3n/4  x (0)e j 2 3* 0/4  x (1)e j 2 3*1/4  x (2)e j 2 3* 2/ 4  x (3)e j 2  3*3/4 n 0

 1  0  0  1e j 9 /2  1  j  X (3)  2 and X (3)  tan 1 ( 1)   450

Page 8 of 22

(b) Plot of x(n)

Sampling rate, Fs  8kHz  S ampling interval, T  1 Fs  125  s .

(c) Plot of magnitude versus angular frequency (magnitude spectrum)

Angular frequency = k, where,   2 NT  2 (4 125 10 6) 12.57 10 3 rad s -1

(d) Plot of phase versus angular frequency (Phase spectrum)

Page 9 of 22

Mathematical Problem: on IDFT Find the IDFT, x(n) from the DFT components, X(k) = [2, 1+j, 0, 1-j]. Solution: IDFT of X(k) is given by

1 N 1 x( n)   X (k ) e j 2 kn/ N N k 0 x(0) 

1 3 1 1 X ( k )e j 2 k 0/4   X (0)  X (1)  X (2)  X (3)   2  1 j  0  1  j   1  N k 0 4 4

1 3 1 X ( k ) ej 2 k 1/4   X (0) ej 2 01/4  X (1)ej 2 11/4  X (2)ej 2  21/4  X (3)ej 2  31/ 4   4 k 0 4 1 1   2  (1  j) e j / 2  0  (1  j) e j 3 /2   2  (1  j ) j  (1  j)(  j)   0 4 4

x(1) 

1 3 1 X ( k )e j 2 k 2 /4   X (0)e j 2 0 2/ 4  X (1)e j 2 1 2/ 4  X (2)e j 2 22/ 4  X (3)e j 2 32/ 4   4 k 0 4 1 1   2  (1  j) e j  0  (1  j) e j 3   2  (1  j)  (1  j)   0 4 4

x(2) 

1 3 1 x(3)   X ( k ) e j 2 k 3/4   X (0)e j 2 03/ 4  X (1)ej 2  13/4  X (2)ej 2  23/ 4  X (3)e j 2  33/ 4  4 k 0 2 1 1   2  (1  j) e j 3 /2  0  (1  j) e j 9 / 2    2  (1  j)(  j)  (1  j ) j  1 4 4

 x( n)  [1, 0, 0, 1]

Mathematical Problem:

Page 10 of 22

Problem:

Page 11 of 22

 Problem: (i) Determine spectrum of the signal x1[n] = {1 2 2 0 0} using DFT with N = 5. (ii) Given x2[n] = {1 2 5 6 6}. Based on the DFT of x1[n], determine DFT of x2[n] with N = 5. (Hint: x2[n] = x1[n] + 3x1[n-2]). (i) X1[k] = [5 -3.0777i 0.7265i - 0.7265i 3.0777i] 2k 2k -j2π*2k/5 X2[k] = X1[k] + 3 W5 X1[k] = X1[k] (1+3W5 ) = X1[k] (1+3e ) Comments: 1. If x[n] is real then X[k] have symmetric real part and anti-symmetric imaginary part. Example: a (dc) b+cj d+ej f+gj .... .... f-gj d-ej b-cj 2. 3.

If x[n] is real and even symmetric then X[k] are all real and real parts are symmetric Example: a (dc) b d f .... .... f d b If x[n] is real and odd symmetric then X[k] are all imaginary and real parts are anti-symmetric Example: a (dc)



cj

ej

gj ....

.... -gj

-ej

-cj

Problem:

Frequency resolution of DFT: let x(n) = (1 2 3 4). 4-point 8-point

16-point

10.0000 + 0.0000i 10.0000 + 0.0000i 10.0000 + 0.0000i 6.4998 - 6.5822i -0.4142 - 7.2426i

-0.4142 - 7.2426i -4.0515 - 2.4383i

-2.0000 + 2.0000i

-2.0000 + 0.0000i

-2.0000 + 2.0000i

-2.0000 + 2.0000i 1.8088 + 1.8043i

2.4142 - 1.2426i

2.4142 - 1.2426i -0.2572 - 2.3396i

-2.0000 + 0.0000i

-2.0000 + 0.0000i -0.2572 + 2.3396i

-2.0000 - 2.0000i

2.4142 + 1.2426i

2.4142 + 1.2426i 1.8088 - 1.8043i

-2.0000 - 2.0000i

-2.0000 - 2.0000i -4.0515 + 2.4383i

-0.4142 + 7.2426i

-0.4142 + 7.2426i 6.4998 + 6.5822i

Page 12 of 22

 What do you mean by frequency resolution of DFT? Although DFT gives exact frequency response of a signal, sometimes it may not give the desired spectrum due to poor frequency resolution. The frequency resolution can be improved by padding zero to the end of x[n] to make N bigger. This is because zero padding in the time domain corresponds to

interpolation in the Fourier domain.

Page 13 of 22

 Basic Principle of FFT The basic principle of FFT is “divide and conquer” where a big problem is divided in to a number of smaller problems and tackle them individually. This process need to satisfy the following criterion



Example:If DFT of x[n]is

We separate it into two groups with odd and even n



Mathematical derivation of FFT

for k = 0, 1,…,N-1 Since

for k = 0, 1,…,N-1 It is noted that G[k] is the Length-N/2 DFT of data with even n, H[k] is the Length-N/2 DFT of data with odd n and 𝑊𝑁𝑘 is the Overhead

Page 14 of 22

 

Butterfly structure of decimation in time (DIT) FFT Butterfly structure of length-2 DIT FFT Stage-1

x(0)

x(1)

X(0)

X(1)

W20

-1

Description with example: Let x(n) = [8, 7]. Determine 2-point DFT components of x(n) using DIT FFT

X (0)  x(0)  x(1)w02  8  7  15 X (1)  x(0)  x(1)w20  8  7  1 Thus DFT components of x(n) is X(k) = [15, 1].  nk/ N

 e  j2 [Note: w nk N 

 w 20  e  j2 0/2  1]

Butterfly structure of length-4 DIT FFT Stage-1

x(0)

x(2)

X(0)

X11(0)

W20

-1

x(1)

x(3)

Stage-2

W20

-1

X(1)

X11(1)

X(2)

X12(0)

W40

-1

X12(1)

W41

-1

X(3)

Description with example: Let x(n) = [8, 7, 6, 5]. Determine 4-point DFT components of x(n) using DIT FFT Now, Output after 1st stage:

X11 (0)  x(0)  x(2)w20  8  6  14 Page 15 of 22

X11 (1)  x(0)  x(2)w20  8  6  2 X12 (0)  x(1)  x(3)w20  7  5  12 X12 (1)  x(1)  x(3)w20  7  5  2 Output after 2nd stage (Final output):

X (0)  x11 (0)  x12 (0)w04  14  12  26 X (1)  x11 (1)  x12 (1)w14  2  2e  j2  1/4  2  2( j )  2  2 j X (2)  x11 (0)  x12 (0)w04  14  12  2 X (3)  x11 (1)  x12 (1)w14  2  2e j 2 1/4  2  2e j /2  2  2(  j )  2  2 j Thus DFT components of x(n) is X(k) = [26, 2-2j, 2, 2+2j]. 

Butterfly structure of length-4 DIT IFFT

Description with example: Let X(k) = [26, 2-2j, 2, 2+2j]. Determine 4-point DFT components of x(n) using DIT FFT Now, Output after 1st stage:

02  26  2  28 X11 (0)  X (0)  x(2)w 20  26  2  24 X11 (1)  x(0)  x(2)w 20  2  2 j  2  2 j  4 X12 (0)  x(1)  x(3)w 20  (2  2 j )  (2  2 j )  4 j X12 (1)  x(1)  x(3) w Page 16 of 22

Output after 2nd stage (Final output):

1 1 40    28  4  8 x(0)   x11 (0)  x12 (0) w 4 4 1 1 1 41    24  (4 j )( j )   24  4  7 x(1)   x11 (1)  x12 (1) w 4 4 4 1 1 40    28  4  6 x(2)   x11 (0)  x12 (0) w 4 4 1 1 1 x(3)   x11 (1)  x12 (1) w41    24  ( 4 j )( j )   24  4  5 4 4 4 Thus IDFT of X(k) is x(n) = [8, 7, 6, 5].



Butterfly structure of length-8 DIT FFT Stage-1

x(0) x(4)

W 02

-1

x(2) x(6)

0

W2

-1

x(1) x(5)

W 02

-1

x(3) x(7)

0

W2

-1

Stage-2

Stage-3

X11(0)

X21(0)

X11(1)

X21(1)

X12(0)

W4

-1 X21(2)

X12(1)

W 41

-1

0

X(0) X(1) X(2) X(3)

X21(3)

X(4)

X13(0)

X22(0)

W80

-1

X13(1)

X22(1)

W81

-1

X14(0)

W 40

-1

X22(2)

W8

X14(1)

W4

1

-1

X22(3)

W8

2

3

X(5) X(6) -1 X(7) -1

Description with example: Let x(n) = [8, 7, 6, 5, 4, 3, 2, 1]. Determine 8-point DFT components of x(n) using DIT FFT [To know how to draw time vs x(n) and angular frequency vs magnitude or phase spectrum if sampling rate is given, just follow (b), (c) and (d) of a previous problem] Solution: Page 17 of 22

If x[n] has the values {8 7 6 5 4 3 2 1}, its spectrum can be calculated using FFT as follows: After 1st stage, the output is {12 4 8 4 10 4 6 4} After 2nd stage, the output is {20 4-j4 4 4+j4 16 4-j4 4 4+j4} After 3rd stage, the output is {36 4-j9.657 4-j4 4-j1.657 4 4+j1.657 4+j4 4+j9.657}

Note: x(n) = [8, 7, 6, 5, 4, 3, 2, 1] is a real valued sequence. Recall that If x[n] is real then X[k] have symmetric real part and anti-symmetric imaginary part. Example: a (dc) b+cj d+ej f+gj .... .... f-gj d-ej b-cj Thus, it is enough just to calculate first five DFT components {i.e., 36 4-j9.657 4-j4 4-j1.657 4 } and then to just write the another three. 

Give the butterfly structure of length-16 DIT FFT.

Page 18 of 22

Decimation in Frequency (DIF) FFT In decimation in frequency (DIF) FFT, X(k) is split with k even and k odd. Since the decimation is performed in frequency domain, the name is Decimation in frequency (DIF) FFT. In DIF N Point DFT is split into N/2 points DFTs. 

Butterfly structure of length-2 DIF FFT (same as DIT FFT) Stage-1 x(0)

x(1)

X(0)

X(1)

W20

-1

Description with example: Let x(n) = [8, 7]. Determine 2-point DFT components of x(n) using DIF FFT

X (0)  x(0)  x(1)w02  8  7  15 X (1)  x(0)  x(1)w20  8  7  1 Thus DFT components of x(n) is X(k) = [15, 1].  nk/ N

 e  j2 [Note: w nk N 

 w 20  e  j2 0/2  1]

Butterfly structure of length-4 DIF FFT

Let x(n) = [8, 7, 6, 5]. Determine 4-point DFT components of x(n) using DIF FFT Now, Output after 1st stage:

X1 (0)  x(0)  x(2)  8  6  14 X1 (1)  x(1)  x(3)  7  5  12 Page 19 of 22

X1 (2)  [ x(2)  x(0)]w40  6  8  2 X1 (3)  [ x(1)  x(3)]w41  [7  5]( j )  2 j Output after 2nd stage (Final output):

X (0)  x1 (0)  x1 (1)  14  12  26

X (2)  [ x1 (0)  x1 (1)]w20  14  12  2 X (1)  x1 (2)  x1 (3)  2  2 j

X (3)  x1 (2)  x1 (3)w20  2  2 j Thus DFT components of x(n) is X(k) = [26, 2-2j, 2, 2+2j]. Example: Given a sequence x(n) where x(0) = 1, x(1) = 2, x(2) = 3, x(3) = 4 and x(n) = 0 elsewhere ,find DFT for the first four points using DIF FFT.

Example: Given a DFT components X(k) where X(0) = 10, X(1) = -2+2j, X(2) = -2, X(3) = -2-2j and X(k) = 0 elsewhere ,find x(n) using DIF IDFT.

Page 20 of 22



Butterfly structure of length-8 DIF FFT

Description with example: Let x(n) = [8, 7, 6, 5, 4, 3, 2, 1]. Determine 8-point DFT components of x(n) using DIF FFT. (Exercise) 

Butterfly structure of length-8 DIF IFFT

Page 21 of 22

 Complexity comparison between N-point DFT and FFT DFT Total complex multiplication =N2 Total complex addition: N(N-1) Total complex operation = N2 + N(N-1) FFT Total complex multiplication=(N/2)log2N Total complex addition=Nlog2N Total complex operation =(N/2)log2N + Nlog2N

Example: Complexity comparison for 8-point DFT and FFT DFT Total complex multiplication =N2 = 82= 64 Total complex addition: N(N-1) =8*7=56 Total complex operation = 64+56 =120 FFT Total complex multiplication=(N/2)log2N =(8/2)log28=4*3=12 Total complex addition=Nlog2N=8log28=8*3=24. Total complex operation = 12+24 =36 Exercise: Compare the computational Complexity for 1024-point DFT and FFT.

Page 22 of 22...