Notice: Exam Form BE IV/II & BAR V/II (Back) for 2076 Magh
Routine: BE IV/II & BAR V/II - 2076 Magh
Result: BCE I/II exam held on 2076 Bhadra
Result: All (except BCE & BEI) I/II exam held on 2076 Bhadra
Notice: Exam Center for Barrier Exam (2076 Poush), 1st Part
View All
View Old Questions
Computer Engineering(BCT)
Electrical Engineering(BEL)
Electronics and Communication(BEX)
View All
View Syllabus
Computer Engineering(BCT)
Electrical Engineering(BEL)
Electronics and Communication(BEX)
View All

Notes of Digital Signal Analysis and Processing [CT 704]

Discrete Fourier Transform


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]
⊗ 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

∑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
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
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).

Sponsored Ads