Numerical On Dft.pdf

NUMERICAL ON DFT Dr Malaya Kumar Hota (Prof., SENSE, VIT University)

Circular Convolution Example Determine the circular convolution of the following two sequences:





x1 (n)  1, 2,3,1 

and





x2 (n)  4,3, 2, 2 

Solution: Using Matrix method

1 2  3  1

1 1 2 3

3 1 1 2

2   4  4  3  6  4  17  3   3  8  3  2  6  19    1   2 12  6  2  2  22       1   2  4  9  4  2  19 

DR. MALAYA KUMAR HOTA (PROF., SENSE)

2

Circular Convolution By means of DFT and IDFT By means of DFT and IDFT, determine the sequence x3(n) corresponding to the circular convolution of the following two sequences





x1 (n)  2,1, 2,1 

and





x2 (n)  1, 2,3, 4 

Solution: Using DFT & IDFT method

 2 1  x41     2   1 

1   2 x42     3   4

W40  0 W4 W4   0 W4 W 0  4

W40 W40 W40  1 1 1 1  W41 W42 W43  1  j  1 j    2 4 6 1  1 W4 W4 W4  1  1   3 6 9 1 j  1  j  W4 W4 W4  

DR. MALAYA KUMAR HOTA (PROF., SENSE)

3

Circular Convolution By means of DFT and IDFT  10   2  j 2   X 42  W4 x42    2     2  j 2 

6 0 X 41  W4 x41     2   0





X1 (k )  6,0, 2,0 





X 2 (k )  10,  2  j 2,  2,  2  j 2

and



X 3 (k )  X 1 (k ). X 2 (k )





 60, 0,  4, 0 

DR. MALAYA KUMAR HOTA (PROF., SENSE)

4

Circular Convolution By means of DFT and IDFT  60  0 X 43     4    0

14  16  1  1  x43  W 4 X 43  W 4 X 43    14  N 4   16 





x3 (n)  14,16,14,16 

DR. MALAYA KUMAR HOTA (PROF., SENSE)

5

Linear Convolution Output through Circular Convolution By padding the sequences x(n) and h(n) with a sufficient number of zeros forces the circular convolution to yield the same output as linear convolution.

y(n)  x(n)  h(n) If the input or excitation x(n) is of length L and the inpulse response h(n) is of length M, then the oupput y(n) will be of length N=(L+M-1). Pad x(n) with (M-1) zeros and h(n) with (L-1) zeros.

Perform the circular convolution to yield the same output as linear convolution. DR. MALAYA KUMAR HOTA (PROF., SENSE)

6

Use of DFT in Linear Filtering Circular convolution is of no use if our objective is to determine the output of a linear filter to a given input sequences. In this case we use linear convolution.

Input x(n)

FIR Filter

Output y(n)

y(n)  x(n)  h(n) Impulse response h(n)

DR. MALAYA KUMAR HOTA (PROF., SENSE)

7

Use of DFT in Linear Filtering Example: By means of DFT and IDFT, determine the response of the FIR

 

filter with impulse response h(n)  1,2,3 

Solution: Response of the FIR filter,

 

to the input sequence x(n)  1,2,2,1 

.

y(n)  x(n)  h(n)

Length of y(n), N = 3+4-1 = 6. If





x(n)  1, 2, 2,1,0,0 

and

then response of the FIR filter,





h(n)  1, 2,3, 0, 0, 0 

y(n)  x(n)  h(n)

DR. MALAYA KUMAR HOTA (PROF., SENSE)

8

Use of DFT in Linear Filtering Steps: (i) Compute DFT of x(n) to obtain X(k). (ii) Compute DFT of h(n) to obtain H(k). (iii) Y(k)= X(k). H(k)

(iv) Compute IDFT of Y(k) to obtain y(n). NOTE: The efficient computation of the DFT via the fast Fourier transform (FFT) algorithm is usually performed for a length N that is a power of 2. For simplicity we compute eight point DFT i.e., N=8. This computation yields the result,





y(n)  1, 4,9,11,8,3, 0, 0 

The last two values are zero because we used an eight point DFT & IDFT, when, in fact, the minimum number of points required is six. DR. MALAYA KUMAR HOTA (PROF., SENSE)

9

Example Find the DFT of

x ( n)  a n 0  n  N  1 N 1

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

0  k  N 1

n 0

N 1

N 1

n 0

n 0

  a n e j 2 kn / N    ae  j 2 k / N  1  a N e j 2 kN / N 1 aN    j 2 k / N 1  ae 1  ae  j 2 k / N

n

e j 2 k  cos (2 k )  j sin(2 k )  1

DR. MALAYA KUMAR HOTA (PROF., SENSE)

10

Find the N-point DFT x ( n)   ( n) N 1

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

k  0,1,2,......., ( N  1)

n 0

N 1

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

1 DFT  (n)  1 N

DR. MALAYA KUMAR HOTA (PROF., SENSE)

11

Find the N-point DFT x(n)   (n  n0 ) N 1

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

,

0  n0  N  1

k  0,1,2,......., ( N  1)

n 0

N 1

   (n  n0 )e  j 2kn / N  1.e  j 2k ( n0 ) / N n 0

 e  j 2k ( n0 ) / N  WNkn0

DR. MALAYA KUMAR HOTA (PROF., SENSE)

12

Find the IDFT X (k )   (k ) 1 x ( n)  N

N 1

j 2kn / N X ( k ) e 

n  0,1,2,......., ( N  1)

k 0

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

DR. MALAYA KUMAR HOTA (PROF., SENSE)

13

Note Point 1 DFT    (k ) N N DFT 1  N (k ) N

N 1

N 1

n 0

n 0

 j 2kn / N  j 2kn / N 1 . e  e  N ( k )   DFT e j 2k0 n / N   N (k  k0 ) N

N 1

N 1

n 0

n 0

j 2k 0 n / N  j 2kn / N  j 2 ( k  k 0 ) n / N e . e  e  N ( k  k 0 )  

DR. MALAYA KUMAR HOTA (PROF., SENSE)

14

Example Find the DFT of

x(n)  e j (2 / N ) K0n N 1

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

0  n  N 1 0  k  N 1

n 0

N 1  j 2 k n 0  j 2 kn / N N

 e

e

n 0

N 1

  e  j 2 ( k  k0 ) n / N  N . (k  k0 ) n 0

DR. MALAYA KUMAR HOTA (PROF., SENSE)

15

Example Find the DFT of  2  x(n)  cos  K0n   N 

0  n  N 1

 2  x(n)  cos  K0n  0  n  N 1 N   1  j 2N K0 n  j 2N K0 n   e e  2 

Using linearity and time shifting property,

1 X (k )   N .  (k  k0 )  N  N .  (k  k0 )  N  2 DR. MALAYA KUMAR HOTA (PROF., SENSE)

16

Example Find the DFT of  2  x(n)  sin  K0 n   N 

0  n  N 1

 2  x(n)  sin  K0n  0  n  N 1  N  1  j 2N K0n  j 2N K0n   e e  2j  

Using linearity and time shifting property,

X (k ) 

1  N .  (k  k0 )  N  N .  (k  k0 )  N  2j DR. MALAYA KUMAR HOTA (PROF., SENSE)

17

Example If X(k) is the DFT of the sequence x(n), determine N point DFTs of xc(n) and xs(n) in terms of X(k).

2k0 n xc (n)  x(n) cos N

,

0  n  N 1

2k0 n xs (n)  x(n) sin N

,

0  n  N 1

18

Solution 2k0 n xc (n)  x(n) cos N 2k 0 n j  j 2Nk0 n  1 N  x ( n ) e e  2  

1 X c (k )  X ((k  k0 )) N  X ((k  k0 )) N  2

19

Solution 2k0 n xs (n)  x(n) sin N 2k 0 n j  j 2Nk0 n  1 N  x ( n ) e e  2j  

1 X ((k  k0 )) N  X ((k  k0 )) N  X c (k )  2j

20

Example For the sequence x1(n) and x2(n), determine N point circular convolution and circular correlation.

2n x1 (n)  cos N

2n x2 (n)  sin N

21

Solution 2n 2n j  j   2n 1 N N x1 (n)  cos  e e  N 2 

N X 1 (k )   ((k  1)) N   ((k  1)) N  2 2n 2n j  2n 1  jN N x2 (n)  sin  e e  N 2j  

N  ((k  1)) N   ((k  1)) N  X 2 (k )  2j 22

Solution X 3 (k )  X 1 (k ). X 2 (k ) N2  ((k  1)) N   ((k  1)) N   4j

Convolution

N 2n x3 (n)  sin 2 N

23

Solution Rx1x2 (k )  X 1 (k ). X 2 (k ) *

N2  ((k  1)) N   ((k  1)) N   4j

Correlation

N 2n rx1x2 (n)  sin 2 N

24