DFT (Frequency Domain Sampling) - Digital Signal Processing, Engineering - Computer Science Engineering (CSE) PDF Download

DFT (Frequency Domain Sampling)

The Fourier series describes periodic signals by discrete spectra, where as the DTFT describes discrete signals by periodic spectra. These results are a consequence of the fact that sampling on domain induces periodic extension in the other. As a result, signals that are both discrete and periodic in one domain are also periodic and discrete in the other. This is the basis for the formulation of the DFT.

Consider aperiodic discrete time signal x (n) with FT X(w) =

Since X (w) is periodic with period 2π , sample X(w) periodically with N equidistance samples with spacing 

K = 0, 1, 2…..N-1

The summation can be subdivided into an infinite no. of summations, where each sum 
contains 

Put n = n-lN

We know that xp(n) =  n= 0 to N-1

k=0 to N-1

Therefore   k=0 to N-1

DFT ------------ x_p (n) =  n = 0 to N-1

This provides the reconstruction of periodic signal x_p(n) from the samples of spectrum 
X(w).

The spectrum of aperiodic discrete time signal with finite duration L<N, can be exactly 

recovered from its samples at frequency Wk=

Prove: x(n) = xp (n) 0 ≤ n ≤ N-1

Using IDFT

If we define    p(w) = 

Therefore: X (w) =   

At w =2πk/N P (0) =1

And P (w 2πk/N)= 0 for all other values

Ex: x(n) = aⁿ u(n) 0<a<1

The spectrum of this signal is sampled at frequency W_k= k=0, 1…..N-1, determine reconstructed spectra for a = 0.8 and N = 5 & 50.

X (w) =

X (wk) =  k=0, 1, 2… N-1

0≤n≤N-1

Aliasing effects are negligible for N=50

If we define aliased finite duration sequence x(n)

xˆ(n)= x_p(n)        0≤n≤N-1

= 0                  otherwise

∴Although XÆ (w) ≠ X (w), the samples at Wk= are identical.

Ex: &  

Apply IDFT 

using Taylor series expansion

= 0  except r = n+mN

The result is not equal to x (n), although it approaches x (m) as N becomes ∞ .

Ex: x (n) = {0, 1, 2, 3} find X (k) =?

= -2+2j

X (2) = -2
X (3) = -2-2j

DFT as a linear transformation

k = 0 to N-1

n = 0, 1…N-1

Let x_N =  X_N =

The N point DFT may be expressed in matrix form as 

Ex: x (n) = {0, 1, 2, 3}

IDFT

Q.

Find y (n) = x (n) h (n) using frequency domain. Since y (n) is periodic with period 2.
Find 2-point DFT of each sequence.

X (0) = 1.5 H (0) = 1.5

X (1) = 0.5    H (1) = -0.5

Y (K) = X (K) H (K)

Y (0) = 2.25 Y (1) = -0.25

Using IDFT  y (0) = 1; y (1) = 1.25

= 1 * 0.5 + 0.5 * 1 = 1

= 1 * 1 + 0.5 * 0.5 = 1.25

 1 * 0.5 + 0.5 * 1 = 1

~y (n) ={1, 1.25, 1, 1.25…..}

Q. Find Linear Convolution of same problem using DFT

Sol. The linear convolution will produce a 3-sample sequence. To avoid time aliasing we convert the 2-sample input sequence into 3 sample sequence by padding with zero.

For 3- point DFT

X (0) = 1.5           H (0) = 1.5

X (1) = 1+0.5  H (1) = 0.5+ 

X (2) = 1+0.5 e H (2) = 0.5+ e

Y (K) = H (K) X (K)

Y (0) = 2.25

Y (1) = 0.5 + 1.25 + 0.5 e

Y (2) = 0.5 + 1.25+ 0.5 e 

Compute IDFT

y(0) = 0.5

y(1) =1.25

y(2) =0.5

y(n) = { 0.5, 1.25, 0.5} Ans