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