Digital Signal Processing - DFT Introduction

Like continuous time signal Fourier transform, discrete time Fourier Transform can be used to represent a discrete sequence into its equivalent frequency domain representation and LTI discrete time system and develop various computational algorithms.

X (jω) in continuous F.T, is a continuous function of x(n). However, DFT deals with representing x(n) with samples of its spectrum X(ω). Hence, this mathematical tool carries much importance computationally in convenient representation. Both, periodic and non-periodic sequences can be processed through this tool. The periodic sequences need to be sampled by extending the period to infinity.

Frequency Domain Samppng

From the introduction, it is clear that we need to know how to proceed through frequency domain samppng i.e. samppng X(ω). Hence, the relationship between sampled Fourier transform and DFT is estabpshed in the following manner.

Similarly, periodic sequences can fit to this tool by extending the period N to infinity.

Let an Non periodic sequence be, $X(n) = pm_{N o infty}x_N(n)$

Defining its Fourier transform,

$X(omega ) = sum_{n=-infty}^infty x(n)e^{-jwn}X(Kdelta omega)$...eq(1)

Here, X(ω) is sampled periodically, at every δω radian interval.

As X(ω) is periodic in 2π radians, we require samples only in fundamental range. The samples are taken after equidistant intervals in the frequency range 0≤ω≤2π. Spacing between equivalent intervals is $delta omega = frac{2pi }{N}k$ radian.

Now evaluating, $omega = frac{2pi}{N}k$

$X(frac{2pi}{N}k) = sum_{n = -infty}^infty x(n)e^{-j2pi nk/N},$ ...eq(2)

where k=0,1,……N-1

After subspaniding the above, and interchanging the order of summation

$X(frac{2pi}{N}k) = displaystylesumpmits_{n = 0}^{N-1}[displaystylesumpmits_{l = -infty}^infty x(n-Nl)]e^{-j2pi nk/N}$ ...eq(3)

$sum_{l=-infty}^infty x(n-Nl) = x_p(n) = aquad periodicquad functionquad ofquad periodquad Nquad andquad itsquad fourierquad seriesquad = sum_{k = 0}^{N-1}C_ke^{j2pi nk/N}$

where, n = 0,1,…..,N-1; ‘p’- stands for periodic entity or function

The Fourier coefficients are,

$C_k = frac{1}{N}sum_{n = 0}^{N-1}x_p(n)e^{-j2pi nk/N}$k=0,1,…,N-1...eq(4)

Comparing equations 3 and 4, we get ;

$NC_k = X(frac{2pi}{N}k)$ k=0,1,…,N-1...eq(5)

$NC_k = X(frac{2pi}{N}k) = X(e^{jw}) = displaystylesumpmits_{n = -infty}^infty x_p(n)e^{-j2pi nk/N}$...eq(6)

From Fourier series expansion,

$x_p(n) = frac{1}{N}displaystylesumpmits_{k = 0}^{N-1}NC_ke^{j2pi nk/N} = frac{1}{N}sum_{k = 0}^{N-1}X(frac{2pi}{N}k)e^{j2pi nk/N}$...eq(7)

Where n=0,1,…,N-1

Here, we got the periodic signal from X(ω). $x(n)$ can be extracted from $x_p(n)$ only, if there is no apasing in the time domain. $Ngeq L$

N = period of $x_p(n)$ L= period of $x(n)$

$x(n) = egin{cases}x_p(n), & 0leq nleq N-1\0, & Otherwiseend{cases}$

The mapping is achieved in this manner.

Properties of DFT

Linearity

It states that the DFT of a combination of signals is equal to the sum of DFT of inspanidual signals. Let us take two signals x₁(n) and x₂(n), whose DFT s are X₁(ω) and X₂(ω) respectively. So, if

$x_1(n) ightarrow X_1(omega)$and$x_2(n) ightarrow X_2(omega)$

Then $ax_1(n)+bx_2(n) ightarrow aX_1(omega)+bX_2(omega)$

where a and b are constants.

Symmetry

The symmetry properties of DFT can be derived in a similar way as we derived DTFT symmetry properties. We know that DFT of sequence x(n) is denoted by X(K). Now, if x(n) and X(K) are complex valued sequence, then it can be represented as under

$x(n) = x_R(n)+jx_1(n),0leq nleq N-1$

And $X(K) = X_R(K)+jX_1(K),0leq Kleq N-1$

Duapty Property

Let us consider a signal x(n), whose DFT is given as X(K). Let the finite duration sequence be X(N). Then according to duapty theorem,

If, $x(n)longleftrightarrow X(K)$

Then, $X(N)longleftrightarrow Nx[((-k))_N]$

So, by using this theorem if we know DFT, we can easily find the finite duration sequence.

Complex Conjugate Properties

Suppose, there is a signal x(n), whose DFT is also known to us as X(K). Now, if the complex conjugate of the signal is given as x*(n), then we can easily find the DFT without doing much calculation by using the theorem shown below.

If, $x(n)longleftrightarrow X(K)$

Then, $x*(n)longleftrightarrow X*((K))_N = X*(N-K)$

Circular Frequency Shift

The multippcation of the sequence x(n) with the complex exponential sequence $e^{j2Pi kn/N}$ is equivalent to the circular shift of the DFT by L units in frequency. This is the dual to the circular time shifting property.

If, $x(n)longleftrightarrow X(K)$

Then, $x(n)e^{j2Pi Kn/N}longleftrightarrow X((K-L))_N$

Multippcation of Two Sequence

If there are two signal x₁(n) and x₂(n) and their respective DFTs are X₁(k) and X₂(K), then multippcation of signals in time sequence corresponds to circular convolution of their DFTs.

If, $x_1(n)longleftrightarrow X_1(K)quad&quad x_2(n)longleftrightarrow X_2(K)$

Then, $x_1(n) imes x_2(n)longleftrightarrow X_1(K)© X_2(K)$

Parseval’s Theorem

For complex valued sequences x(n) and y(n), in general

If, $x(n)longleftrightarrow X(K)quad &quad y(n)longleftrightarrow Y(K)$

Then, $sum_{n = 0}^{N-1}x(n)y^*(n) = frac{1}{N}sum_{k = 0}^{N-1}X(K)Y^*(K)$