**DFT representation and properties**

*Discrete Fourier Transform*

- It provides a frequency domain representation of a discrete time signal x[n].

- It converts sequence of numbers in time domain to another sequence of numbers in frequency domain.

- Mathematically, N point DFT of a sequence x[n] is given by:

X[k] = ∑k=0to N-1 {x[n] e-jkn.2π/N}

- The inverse fourier transform is given by:

x[n] = ∑k=0to N-1 {X[k] ejkn.2π/N}

*Comparison of DFT and DTFT*

- Discrete time fourier transform is given by:

X[w] = ∑k=-∞to∞ {x[n] e-jwn}

- Discrete fourier transform is given by:

X[k] = ∑k=0to N-1 {x[n] e-jkn.2π/N}

- This clearly shows that DFT is obtained from the samples of DTFT.

- DFT is better than DTFT because DTFT is a continuous function of frequency while DFT is frequency domain sample.

*Frequency Domain Sampling*

- According to definition of DTFT:

X[w] = ∑k=-∞to∞ {x[n] e-jwn}

- The range of w is from 0 to 2π or -π to π.

- It is not possible to compute X[w] on digital computer because of infinite range summation.

- X(w) is a continuous signal.

- A discrete signal is obtained by sampling X(w).

*DFT as Linear Transformation*

The DFT can be represented as a linear combination as shown below:

*Properties of DFT*

1. Periodicity

- If a discrete time signal is periodic then its DFT will also be periodic.

- If x[n] -------------> X[k], then:

x(n + N) = x(n) ; for all values of n

X(k + N) = X(k) ; for all values of k

2. Linearity

- DFT of linear combination of two or more signals is equal to the sum of linear combination of DFT of individual signals.

- If x1[n] ----> X1[k] and x2[n] ----> X2[k] ; then :

a x1[n] + b x2[n] -----------------> a X1[k] + b X2[k]

**Circular Convolution**

- The multiplication of two DFT's is equivalent to their circular convolution of their sequences in time domain.

- If x1[n] -----> X1[k] and x2[n] -----> X2[k], then:

x1[n] ⊗ x2[n] ----------> X1[k] . X2[k]

where,

⊗ indicates circular convolution.

*Proof of Circular Convolution*

Let X3[k] = X1[k] . X2[k] Then, by definition: x3[m] = 1/N . ∑k=0to N-1 {X3[k] ejkm.2π/N} = 1/N . ∑k=0to N-1 {{X1[k] . X2[k]} ejkm.2π/N} = 1/N . ∑k=0to N-1 {{(∑n=0to N-1 {{x1[n] e-jkn.2π/N}) . (∑l=0to N-1 {x2[l] e-jkl.2π/N})} ejkm.2π/N} = 1/N . ∑n=0to N-1 x1[n] . ∑n=0to N-1 x2[l] {∑k=0to N-1 ejk(m-n-l).2π/N}

Let a = ej(m-n-l).2π/N :

We get,

∑k= 0 to N-1 ak = N ; for a = 1

= 0 ; for a != 1

For a = 1, (m-n-l) must be integer multiple of N.

m-n-l = pN

or, l = m-n-pN

or, l = ((m-n))N

So,

∑k=0to N-1 ejk(m-n-l).2π/N = N ; for l = ((m-n))N

= 0 ; elsewhere

Using this:

x3[m] = 1/N . ∑n= 0 to N-1 {N x1[n] x2((m-n))N}

= ∑n= 0 to N-1 {x1[n] x2((m-n))N}

= x1[n] ⊗ x2[n]

**Fast Fourier Transform - Decimation in time and frequency algorithm**

- Fast fourier transform (FFT) is an algorithm that allows computation of DFT of Discrete time signals faster.

- It makes use of symmetry of DFT calculation.

*RADIX-2 FFT Algorithm*

- In radix 2, N = 2v

where,

N = no of points

v = no of stages

- It can be computed by:

1. Radix-2 Decimation in time (DIT) Algorithm

2. Radix-2 Decimation in frequency (DIF) Algorithm

**Computational Complexity of FFT**

- For DFT,

N2 = complex multiplications

N2 - N = complex additions

- For FFT,

For one butterfly, one complex multiplication and 2 complex additions

No of butterfly in each stage = N/2

No of stages = log2N

So,

No of complex multiplications = N/2 . log2N

No of complex additions = N . log2N

- Complexity of DFT is of order O(N2).

- Complexity of FFT is of order O(N log2N).

Ⓒ Copyright ESign Technology 2019. A Product of ESign Technology. All Rights Reserved.