UNIT V

DISCRETE FOURIER TRANSFORM

EC T43-SIGNALS AND SYSTEMS ECE

DISCRETE FOURIER TRANSFORM

One of the main advantages of discrete-time signals is that they can be processed and
represented in digital computers. However, when we examine the definition of the Fourier
transform of discrete-time signal
   x n  e

X e j   j n
DTFT
n  

We notice that such a characterization in frequency domain depends on the continuous

variable  .

This implies that the Fourier transform is not suitable for the processing of discrete-time
signals in digital computers.

As a consequence we need a transform depending on a discrete-frequency variable. This can

be obtaining from the Fourier transform itself in very simple way, by sampling uniformly the
continuous-frequency variable  . In this way, we obtain a mapping of a signal depending on a
discrete-time variable n to a transform depending a discrete-frequency variable k , such a
mapping is referred to as the discrete Fourier transform (DFT).

DFT is given by
N 1 N 1
X  k    x n  e   x n  W Nnk , for 0  k  N  1
 j 2N kn

n 0 n0

IDFT

N 1 N 1
x n    X k e  X k W
j 2N kn  nk
 N , for 0  n  N  1
k 0 k 0

Twiddle factor

Most approaches for improving the efficiency of computation of DFT, exploits

the symmetry and periodicity property of i.e.

Properties of the DFT

EC T43-SIGNALS AND SYSTEMS ECE
1. Linearity : Ax ( n )  By ( n )  AX ( k )  BX ( k )

k m
2. Time Shift: x (n  m )  X ( k )e  j 2km / N  X ( k )WN

3. Frequency Shift: x ( n )e j 2km / N  X ( k  m )

4. Duality : N 1 x( n)  X ( k )
N 1
why? X (k )   x(m)e  j 2mk / N
m 0
N 1
DFT ( X ( n ))   X (n)e  j 2nk / N
n 0
DFT of x(m)

x( n )  x( N  n )
N 1
1

N
 X (k )e j 2k ( N  n ) / N
k 0
j 2k ( N  n ) / N
e  e j 2kN / N e  j 2kn / N
N 1
1
x( n ) 
N
 X (k )e  j 2kn / N
k 0
N 1
1
 DFT ( N 1 X ( n )) 
N
 X (n )e  j 2nk / N  x( k )
n 0

5. Circular convolution
N 1
 x(m) y (n  m)  x(n)y(n)  X (k )Y (k ) circular convolution
m0

6. Multiplication
N 1
x ( n) y ( n )  N
   
1
 X (m)Y (k  m)  N 1 X (k )Y (k )
new sequence m0
z ( n)  x( n) y ( n)

7. Parseval’s Theorem
N 1 N 1

 | x(n) | 2  N 1  | X (k ) | 2
n0 k 0

EC T43-SIGNALS AND SYSTEMS ECE

Summary of Properties of the Discrete Fourier Transform

Property Periodic signal Fourier Series Coefficients

Linearity Ax[n]  By[n] Aa k  Bbk
Time Shifting x[ n  n0 ]  2 
 jk   n0
 N 
ak  e
 
Conjugation x [n] a k
Time Reversal x[  n] ak
Frequency Shifting e jMw n x[ n]
0 ak M
First Difference x[ n]  x[ n  1] 1  e  jk  2 N  a
  k
 
Conjugate x[n] real a k  a  k
Symmetry for Real
Signals
Real & Even x[n] real and even a k real and even
Signals
Real & Odd signals x[n] real and odd a k purely imaginary and
odd
Even-Odd xe [n]  Ev x[n] [ x[n]real ] Re a k 
Decomposition xo [n]  Od  x[ n]
Of Real Signals
[ x[n]real ] j Im ak 
Parseval’s Relation 1 2 2

N
 x[ n]   ak
n N k N

EC T43-SIGNALS AND SYSTEMS ECE

 PROBLEMS

Example 1. : Find DFT of { 1 0 0 1}.

The DFT of the sequence { 1, 0, 0, 1} will be evaluated

x(0) = 1, x(T)= 0, x(2T) = 0, x(3T) = 1 , N=4

We desire to find X(k) for k = 0,1,2,3.

3 3
X (0)   x (nT )e j 0   x (nT )  x (0)  x (T )  x(2T )  x(3T )
n0 n0

For k = 0  1 0  0 1  2

3 3 6
j
X (1)   x(nT )e  jnT   x(nT )e  j 2n / N  1  0  0  1e 4
 1 j
k=1 n 0 n 0

3
X (2)   x(nT )e  j 2n 2 / N  1  0  0  1e  j 3  1  1  0
k=2 n0

3 9
j
X (3)   x(nT )e  j 2n 3 / N
 1  0  0  1e 2
 1 j
k=3 n 0

Ans: X(k) = { 2 , (1+j) , 0, (1-j) }

Example 2: What is the DFT of the signal[n]?

x[n] = [n]

X[k] = = k[0] = .

This means that all frequencies are equally strong present in the impulse signal. So its frequency
spectrum is flat.

Example 3: What is the DFT of a shifted impulse [n­1]?

x[n] = [n­1]

EC T43-SIGNALS AND SYSTEMS ECE

 ­ik0
X[k] = = k[­1] = e  with 0 = 

In this case again all frequencies X[k] are equally strong (they have the same modulus ), but now
the frequency spectrum consists of complex numbers.

Example 4: What is the DFT of cos(5 0) with  0 = ?

x[n] = cos(n 50).

We could calculate X[k] in the same way as in the previous examples, but we can also directly
find X[k] because we may write cos(50) as:

5 5
x[n] = cos(n50) = ein 0 + e­in 05[n] + ­5[n].

As k+N[n] = k[n] we obtain:

x[n] = 5[n] + N­5[n].

So X[5] = and X[N­5] = and all other frequencies are zero:

X[k] = 0, for 0 k < N and k  5 and k  N­5.

Example 5: What is the DFT of a shifted signal x[n­n0]?
Denote the DFT of the shifted signal by X'[k] and of the original signal by X[k].

X'[k] = = = 
­ik0n0 = 
= X[k] e X[k] k[­n0] with 0 = 

Example 6 : Compute the DFT of sequence

Ans.

EC T43-SIGNALS AND SYSTEMS ECE

Example 7: What is the relationship between Z transform and the Discrete
Fourier transform?
Ans. Let us consider a sequence x(n) having z-transforrn with ROC that includes the

unit circle. If X(z) is sampled at the N equally spaced points on the unit circle. If X(z) is
sampled at N equally spaced pomts on the unit circle.

We obtain

Expression is (2) identical to the Fourier transform X(w) evaluated at the N. equally spaced.
Frequencies

If the sequence x(n) has a finite duration of length N or less, the sequence can be
recovered from its N-point DFT. Hence its Z-transform is uniquely determined by its N-point
DFI’. Consequently, X(z) can be expressed as a function of the DFT {X(k)} as
follows

EC T43-SIGNALS AND SYSTEMS ECE

When evaluated on the unit circle (3) yields the Fourier transform of the finite duration
sequence in terms of its DFT in the form:

This expression for Fourier transform is a polynomial interpolation formula for X(w)
expressed in terms of the, values {x(k)) of the polynomial at a set of equally spaced
discrete frequencies

Example 8 : Perform circular, convolution of two sequences

Ans. Circular convolution is

EC T43-SIGNALS AND SYSTEMS ECE

EC T43-SIGNALS AND SYSTEMS ECE
 FFT algorithms –advantages over direct computation of DFT – radix 2
algorithms

What are the advantages of FFT algorithm?

Fast fourier transform reduces the computation time. In DFT computation, number of
multiplication is N2 and the number of addition is N(N-1). In FFT algorithm, number of
multiplication is only N/2(log2N) . Hence FFT reduces the number of elements (adder,
multiplier Z &delay elements). This is achieved by effectively utilizing the symmetric and
periodicity properties of Fourier transform.

(Preparation for Mathematical Derivation of FFT)

1. DFT Algorithm
 
N 1 N 1
X (k )   x(n)e  j 2kn / N   x( n) e  j 2 / N
nk

n 0 n0
 j 2 / N
Denote WN  e , then
N 1
X (k )   x(n)WN nk
n0

Properties of WN m :
(1) WN 0  (e  j 2 / N )0  e 0  1, WN N  e  j 2  1
N m m
(2) W N  WN
WN N  m  (e  j 2 / N ) N  m
 (e  j 2 / N ) N (e  j 2 / N ) m
 1  (e  j 2 / N ) m  WN m
(3) WN N / 2  e  j 2 /( N / 2) / N  e  j  1
WN N / 4  e  j 2 /( N / 4) / N  e  j / 2   j
 e  j 2 /(3 N / 4 ) / N  e  j 3 / 2  j
3N / 4
WN

RADIX 2

The FFT algorithm is most efficient in calculating N point DFT. If the number of point N
can be expressed as a power of 2 ie N= 2 M where M is an integer , then this algorithm is
known as radix-2 FFT algorithm.

Two-Point DFT

EC T43-SIGNALS AND SYSTEMS ECE

 1
x(0), x(1): X (k )   x(n)W2
nk
k  0,1
n0
1 1
X ( 0)   x(n)W2 n0   x(n)  x(0)  x(1)
n 0 n0
1 1

 x(n)W2  x(n)W
n1 n
X (1)   2
n0 n0
0 1
 x(0)W2  x (1)W2
(1 / 2 ) 2
 x(0)  x(1)W2
 x(0)  x(1)( 1)
 x(0)  x(1)

Four-point DFT
x(0), x(1), x(2), x(3)
3
X (k )   x(n)W4 nk k  0,1,2,3,
n0
3 3
X (0)   x(n)W4 n 0   x(n)  x(0)  x(1)  x(2)  x(3)
n0 n0
3
X (1)   x( n)W4  x (0)W4  x (1)W4  x (2)W4  x(3)W4
n 0 1 2 3

n 0

 x (0)  jx (1)  x(2)  jx(3)

3
X (2)   x(n)W4
2n 0 2 4 6
 x(0)W4  x (1)W4  x(2)W4  x(3)W4
n 0
2
 x(0)  x(1)(1)  x(2)(1)  x(3)W4
 x(0)  x(1)  x(2)  x(3)
3
X (3)   x (n)W4
3n 0 3 6 9
 x(0)W4  x (1)W4  x(2)W4  x(3)W4
n 0
3 2 1
 x(0)  x(1)W4  x (2)(1)W4  x (3)W4
 x(0)  jx (1)  (1) x (2)  ( j ) x(3)
 x(0)  jx (1)  x (2)  jx (3)

X (0)  [ x (0)  x ( 2)]  [ x (1)  x (3)]

X (1)  [ x (0)  x ( 2)]  (  j )[ x (1)  x (3)]
 X ( 2)  [ x (0)  x ( 2)]  [ x (1)  x (3)]
X (3)  [ x (0)  x ( 2)]  j[ x (1)  x (3)]

EC T43-SIGNALS AND SYSTEMS ECE

 Two – point DFT

If we denote z(0) = x(0), z(1) = x(2) => Z(0) = z(0) + z(1) = x(0) + x(2)
Z(1) = z(0) - z(1) = x(0) - x(2)

v(0) = x(1), v(1) = x(3) => V(0) = v(0) + v(1) = x(1) + x(3)
V(1) = v(0) - v(1) = x(1) - x(3)

Four – point DFT Two-point DFT

 X(0) = Z(0) + V(0)

X(1) = Z(1) + (-j)V(1)
X(2) = Z(0) - V(0)
X(3) = Z(1) + jV(1)

EC T43-SIGNALS AND SYSTEMS ECE

 Decimation-in-Time FFT Algorithm

x(0), x(1), … , x(N-1) N  2m

 N N
 g ( 0 ), g (1),  , g (  1)  enen po int s
2 2

(( x(0), x(2),, x( N  2)) ( g ( r )  x(2r ))
=> 
h(0), h(1),, h( N  1)  odd
N
po int s
 2 2
(( x(1), x(3),, x( N  1)) (h( r )  x(2r  1))

N 1
X (k )   x (n)W N
kn

n 0
N / 2 1 N / 2 1

 g (r )WN  h(r )W
k ( 2r ) k ( 2 r 1)
  N (k  0,1,..., N  1)
r 0 r 0
N / 2 1 N / 2 1

 g (r )W  h(r )W
2 kr k 2 kr
 N  WN N
r 0 r 0

 (e  j 2 . / N ) 2 kr  (e  j 2 /(. N / 2 ) ) kr  W N
2 kr kr
WN
2
N / 2 1 N / 2 1

 g (r )W  h(r )W
kr k kr
 X (k )  N/2  WN N /2
r 0 r 0
k
 G (k )  W N H (k )
( G(k): N/2 point DFT output (even indexed), H(k) : N/2 point DFT
output (odd indexed))

X ( k )  G ( k )  WN k H ( k ) k  0,1,..., N  1
N / 2 1 N / 2 1
G (k )   g ( r )WN / 2 kr   x ( 2 r )WN / 2 kr
r 0 r 0
N / 2 1 N / 2 1
H (k )   h ( r )WN / 2
kr
  x ( 2 r  1)WN / 2
kr

r 0 r 0

Question: X(k) needs G(k), H(k), k=… N-1

How do we obtain G(k), H(k), for k > N/2-1 ?
G(k) = G(N/2+k) k <= N/2-1
H(k) = H(N/2+k) k <= N/2-1

EC T43-SIGNALS AND SYSTEMS ECE

Future Decimation
g(0), g(1), …, g(N/2-1) G(k)
h(0), h(1), …, h(N/2-1) H(k)
N / 2 1
N
 g (r )W
kr
g (0), g (2),  , g (  2) G (k )  ( N / 2)
2 r 0
N N / 4 1
ge(0), ge(1),...ge(  1)
 ge(m)W
km
4  ( N / 4)
m 0
N
g (1), g (3),  , g (  1) N / 4 1

 go(m)W
k km
2  W( N / 2 ) ( N / 4)
N m 0
go(0), go(1),...go(  1) k
4  GE (k )  W( N / 2 ) Go(k )

even indexed g odd indexed g

(N/4 point) (N/4 point)

WN / 2 k  WN 2 k ?
WN / 2 k  ( e  j 2 /( N / 2 ) ) k
 ( e  j 2 2 / N ) k  ( e  j 2 / N ) 2 k
 WN 2 k
=> G ( k )  GE ( k )  WN 2 k Go(k )

EC T43-SIGNALS AND SYSTEMS ECE

Similarly,
H (k )  HE (k )  WN 2 k Ho( k )
even indexed odd indexed
h (N/4 point) h (N/4 point)

For 8 – point

g ( 0) g (1) g ( 2) g (3) h ( 0) h (1) h ( 2) h (3)

       
x ( 0) x ( 2) x ( 4) x ( 6) x (1) x (3) x (5) x ( 7)
   
ge(0)  ge(1)  he( 0)  he(1) 
go(0) go(1) ho( 0) ho(1)

EC T43-SIGNALS AND SYSTEMS ECE

Decimation-in-Frequency FFT Algorithm

x(0), x(1), … , x(N-1) N  2m

N 1
X (k )   x( n)W N
nk

n 0
N / 2 1 N 1

 x(n)WN  x(n)W
nk nk
  N
n0 n N / 2

let m = n-N/2 (n = N/2+m) n = N/2 => m = N/2-N/2 = 0

EC T43-SIGNALS AND SYSTEMS ECE

 n = N-1 => m = N-1-N/2 = N/2-1
N / 2 1 N / 2 1
 X (k )   x (n )WN nk   x ( N / 2  m )WN ( N / 2  m ) k
n 0 m0
N / 2 1 N / 2 1 N
  x (n )WN nk   x ( N / 2  m)WN mkWN 2 k
n 0 m 0

N N
k
WN 2  1  WN 2  ( 1) k
N / 2 1 N / 2 1
X (k )   x ( n )WN nk   ( 1) k x ( N / 2  m )WN mk
n 0 m 0
N / 2 1
  [ x ( n )  ( 1) k x ( N / 2  n )]WN nk
n 0
N / 2 1
k : even (k  2r )  X (k )  X (2r )   [ x(n)  x( N / 2  n)]W
n0
N
2 rn

 j 2 / N
) 2 rn  (e  j 2 /( N / 2) ) rn  W N / 2
2 rn rn
WN  (e
N / 2 1

N/2 point DFT

 X ( k )  X ( 2r )   [x(n )  x( N / 2 n)]W
n0
N /2
rn

y (n)
N / 2 1
Y (r)   y ( n )WN / 2 rn Z (r )
n 0
k : odd  k  2r  1
 X (k )  X (2r  1)
N / 2 1
  [ x(n)  x( N / 2  n)]W
n 0
N
n ( 2 r 1)

N / 2 1
  [x(n) x(N / 2  n)]W
n 0
N
n
WN
2 rn

z ( n)
N / 2 1
  z (n)W
n 0
N
2 rn

N / 2 1
  z (n)W
n 0
N /2
rn

N / 2 1
N N
 z (n)W rn
Z (r )  N /2  po int DFT of z (0),  , z(  1)
n0 2 2

X(k) : N-point DFT of x(0), …, x(N)  two N/2 point DFT

EC T43-SIGNALS AND SYSTEMS ECE

One N/2 point DFT => two N/4 point DFT
… two point DFTs

EC T43-SIGNALS AND SYSTEMS ECE

 Efficiency of FFT
N – point DFT : 4N(N-1) real multiplications
4N(N-1) real additions

N – point FFT : 2Nlog2N real multiplications

(N = 2m) 3Nlog2N real additions
Computation ration

FFT ' s computations 5 log2 N


DFT ' s computations 8( N  1)
N  212  4096 5  12
  0.18%
8  4095

EC T43-SIGNALS AND SYSTEMS ECE

Example 1 Eight-Point FFT Using Decimation-in-Frequency of
x(n) = {1 1 1 1 0 0 0 0}

x(0) = x(1) = x(2) = x(3)= 1, and x(4) = x(5) = x(6) = x(7) = 0.

Eight-point FFT flow graph using decimation-in-frequency.

1. At stage 1:

where x,(0), x,(1), . . . , x,(7) represent the intermediate output sequence afterthe
first iteration that becomes the input to the second stage.

2. At stage 2:

EC T43-SIGNALS AND SYSTEMS ECE

The resulting intermediate, second-stage output sequence x,,(0), x,,(1), . . .
X,,(7) becomes the input sequence to the third stage.
3. At stage 3:

Answer

X(k) = { 4 , 1-j2.41 , 0 , 1 – j0.41 , 0 , 1 + j0.41 , 0 , 1 + j2. 41 }

DIT radix-2 FFT DIF radix-2 FFT

1.When the input is bit reversed order, the 1.When the input is normal order, the
output will be in normal order . output will be in bit reversed order .
2.In each stage of computation the phase 2.In each stage of computation the phase
factor are multiplied before add and factor are multiplied after add and subtract
subtract operation operation
3.The value of N should be expressed such 3.The value of N should be expressed such
that N=2 m and this algorithm consists of that N=2 m and this algorithm consists of
m stage of computation. m stage of computation.
4.Total number of arthemetric operations is 4.Total number of arithmetic operations is
N log N complex addition and N/2logN N log N complex addition and N/2logN
complex multiplications. complex multiplications

EC T43-SIGNALS AND SYSTEMS ECE

 COMPUTATION OF IDFT USING FFT

The inverse DFT of an N point sequence X (K); K=0, 1…N-1 is defined as

N-1
x (n) =1/N ∑ X (K) e+j2 ‫ה‬nk/N for n=0, 1,2,…N-1
K=0
Take complex conjugate and multiply by N, we get
N-1
Nx *(n) = ∑X *(K) e+j2 ‫ה‬nk/N for n=0, 1, 2 …N-1
K=0
The desired output sequence x (n) can then be obtained by complex conjugating
the DFT and divided by N
N-1
x (n) =1/N [ ∑X* (K) e+j2 ‫ה‬nk/N ]* K=0

EC T43-SIGNALS AND SYSTEMS ECE