Digital Signal Processing

UNIT II DISCRETE FOURIER SERIES &

FOURIER TRANSFORMS:
Properties of discrete Fourier series,
DFS representation of periodic sequences,
Discrete Fourier transforms: Properties of DFT,
linear filtering methods based on DFT,
Fast Fourier transforms (FFT) - Radix-2
decimation in time and decimation in frequency
FFT Algorithms,
Inverse FFT.
Digital Signal Processing

Discrete Time Fourier Series

DFS representation of periodic
sequences
 Introduction
Discrete-Time Fourier Series
The conventional (continuous-time) FS represent a periodic
signal using an infinite number of complex exponentials,
whereas the DFS represent such a signal using a finite
number of complex exponentials
 Example 1
 DFS of a periodic impulse train
~

1 n  rN
x[n]   n  rN  
r   0 else
 Since the period of the signal is N
~ N 1 N 1
Xk    ~x[n]e j2 / Nkn 
n0
 [n]e
n0
 j2  / N kn
 e  j2  / Nk 0  1

 We can represent the signal with the DFS coefficients

~

1 N1 j2  / Nkn
as x[n]   n  rN   e
r   N k 0
 Example 2
 DFS of an periodic rectangular pulse train

 The DFS coefficients

~ 1  e  j2  / 10 k5  j4 k / 10  sink / 2 

4
Xk   e  j2  / 10 kn
 e
n0 1e  j2  / 10 k
sink / 10
 Properties of DFS
 Linearity
~ ~
x1 n DFS
  X1 k 
~ ~
x n
2 DFS
 X2 k 
~ ~
a~
x1 n  b~
x2 n  aX1 k   bX2 k 
DFS
 

 Shift of a Sequence
~ ~
x n DFS
 Xk 
~ ~
x n  m  e  j2 km / NXk 
DFS

~
e j2 nm / N~
x n DFS
  Xk  m

 Duality
~ ~
x n DFS
 Xk 
~
Xn DFS
 N~
x  k 
Symmetry Properties
Symmetry Properties Cont’d
 Periodic Convolution
 Take two periodic sequences
~ ~
x1 n DFS
 X1 k 
~ ~
x n DFS
2  X2 k 
 Let’s form the product
~ ~ ~
X3 k   X1 k X2 k 

 The periodic sequence with given DFS can be written as

N 1
~
x n  ~
x m~
x n  m
3 
m0
1 2

 Periodic convolution is commutative

N 1
~
x3 n  ~ ~
 2 x1 n  m
x
m0
m
 Periodic Convolution Cont’d
N 1
~
x3 n  ~ ~
 1 x2 n  m
x
m0
m
 Substitute periodic convolution into the DFS equation
~ 
N 1 N 1

X3 k      ~ x1[m]~
x2[n  m]WNkn
n0  m0 
 Interchange summations
~ ~  N 1 ~
N 1
kn 
X3 k  
 x1 [m] 2
 x [n  m]WN 
m0  n0 
 The inner sum is the DFS of shifted sequence
km~
N 1
~
 x2[n  m]WN  WN X2 k 
n0
kn

 Substituting
~ N 1
~  N 1 ~  N 1
~ km~ ~ ~
X3 k    x1[m]  x2[n  m]WNkn    1
x [m]WN X 2 k  X1 k X2 k 
m0  n0  m0
Graphical Periodic Convolution
DTFT to DFT
Sampling the Fourier Transform
 Consider an aperiodic sequence with a Fourier transform
x[n] DTFT
 X e j  
 Assume that a sequence is obtained by sampling the DTFT
~
 
Xk   X e j 
 X e j2  / Nk
  2  / N k

 Since the DTFT is periodic resulting sequence is also periodic
 We can also write it in terms of the z-transform
~
 
Xk   Xz  z  e2  / N k  X e j2 / Nk

 The sampling points are shown in figure

~
 Xk could be the DFS of a sequence
 Write the corresponding sequence
~ 1 N 1 ~
x[n]   Xk e j2  / Nkn
N k 0
DFT Analysis and Synthesis
DFT
DFT is Periodic with period N
Example 1
DFT from DFS
 Properties of DFT
 Linearity
x1 n DFT
 X1 k 
x2 n DFT
 X2 k 
ax1 n  bx2 n DFT
 aX1 k   bX2 k 

 Proof:
 Properties of DFT contd.

 Periodicity:

 Proof:
 Properties of DFT contd.

Shifting or Circular Shifting Property:

Proof:
Properties of DFT contd.
 Properties of DFT Contd.
 Circular frequency shift:

 Proof:
 Properties of DFT Contd.
Multiplication of two sequences:

Circular Convolution:
 Properties of DFT Contd.

 Parseval’s Theorem:
Linear Convolution
(II): Using Graphical Method:
III. Using Tabulation Method:
IV. Using Diagonal Method:
Circular Convolution
I. Concentric Circle Method:
I. Concentric Circle Method:
Illustration of circular convolution for N = 8:
•Example:
•Example (continued)
II. Using Matrix Multiplication Method:

X1(n)={1,-1,-2,3,-1}
X2(n)={1,2,3}
•Proof of circular convolution property:
•Multiplication:
Linear filtering methods based
on the DFT
DFT provides a discrete frequency
representation of a finite duration sequence
in the frequency domain.
Computational tool for linear system
analysis, especially for linear filtering.
DFT can be used to perform linear filtering
in the frequency domain.
Linear filtering methods based on the
DFT
1.Use of the DFT in Linear Filtering
2.Filtering of long data sequence
• Overlap-save method
• Overlap-add method
 Use of the DFT in Linear Filtering

• Our objective is to determine the output of a

linear filter to a given input sequence.

Linear Filter
h( n) y ( n) Output or
Input x( n) Response

• Linear Convolution
• By using DFT and IDFT
• Circular Convolution
 Linear Convolution
• A sequence x(n) of length L filtered by an
FIR filter h(n) of length M
M 1
y( n )   h( n ) x ( n  k )
k 0

Example x(n) =[1, 2, 2, 1] , h(n) =[1, 2, 3]

L=4,M=3
x(n)=[1 ,2,2,1] ,h(n)=[1, 2,3]

The length of sequence y(n) is N=L+M-1=6

y(n)={1,4,9,11,8,3}
 DFT and TDFT
• Therefore ,a DFT of size N  L+M-1 is required
to represent y(n) in the frequency domain.
• Using the DFT notation
Y (k )  H (k ) X (k ), k  0,1,.........( N  1)

X(k) and H(k) are the DFT (with zero padding)

of x(n) and h(n), respectively.
• Performing the inverse DFT of Y(K)
y (n)  IDFT (Y (k )
• L=4,M=3,N=L+M-1=6
• Eight point DFT of x(n) is
• X(K)= {6,1.707 - 4.121j, -1 – j,0.2929 - j0.121, 0,0.292 + j0.121, -1+j,1.707 + j4.121}
• Eight point DFT of h(n) is
• H(K)={6,2.414 - j4.414, -2-j2,-0.4142+ j1.585,2,-0.414 -j 1.585,-2+j2,2.414 +
j4.4142}
• Y(k)=X(k).H(K)={36,-14.0-j17.48,j4,0.07+j0.515,0,0.07-j0.515,-j4,-14.07+j17.48}
• Eight point IDFT of Y(K) is
 Circular Convolution
• Example x(n) =[1, 2, 2, 1] , h(n) =[1, 2, 3]
• L=4,M=3
• The length of sequence y(n) is N=L+M-1=6
• Example x(n)=[1 ,2,2,1,0 ,0] ,h(n)=[1, 2,3,0,0 0]

• y(n)={1,4,9,11,8,3}
 Filtering of Long Data Sequences
• In practical applications involving linear
filtering of signals, the input sequence x(n) is
often a very long sequence.
• Real-time signal processing applications
concerned with signal monitoring and
analysis.
• Overlap-save method
• Overlap-add method
• x(n) 
DFT
 X(k) 
IDFT
 x(n)
• Properties of DFT
Circular Convolution N 1
x 3 (m)  x1 (n)  x 2 (n)   DFT
x1 (n)x 2 ((n  m)) N   X 3 (K)  X1 (K)X 2 (K)
• Linear Filtering Methodsn 0Based on the DFT
1.Use of the DFT in Linear Filtering
• By using DFT and IDFT
• Linear Convolution
x(n)  
DFT
 X(k)  H(K)
H(K)  Y(K)  X(K).H(K)  y(n
IDFT

• Circular Convolution
2.Filtering of Long Data Sequence
• Overlap-save method
• Overlap-add method
 Filtering of Long Data Sequences
• When the DFT is used to implement linear
filtering, a signal is processed in blocks. Due to
the real-time requirement (low delay) and the
limitation of physical memory, the size of the
block can not be arbitrarily large.
• The length of the FIR filter is M and the length of
on block of data is L (L>M)
• Each time a block of data of length L+M-1 is
filtered by using the DFT method.
Overlap-Add Method
x(n)={3,-1,0,1,3,2,0,1,2,1},h(n)={1,1,1}
ANS: y(n)={3,2,2,0,4,6,5,3,3,4,3,1}
x(n)={3,-1,0,1,3,2,0,1,2,1},h(n)={1,1,1}
Find the output y(n) of a filter. Assume block length as 3
 x(n)={3,-1,0,1,3,2,0,1,2,1},h(n)={1,1,1}
• Overlap-Add Method: N 1

• Let L=4,M=3,N=L+M-1=6 x3 (m)  x1 (n)  x 2 (n)   n 0

x1 (n)x 2 ((n  m)) N

x1(n)={3,-1,0,1,0,0}, x3(n)={2,1,0,0,0,0}
x2(n)={3,2,0,1,0,0} N 1
Perform y1(n)=x1(n) N h(n) y1 (m)  x1 (n)  h(n)   x1 (n)h((n  m)) N
n 0
N 1
y2(n)=x2(n) N h(n) y2 (m)  x 2 (n)  h(n)   x (n)h((n  m))
n 0
2 N

N 1
y3(n)=x3(n) N h(n) y3 (m)  x 3 (n)  h(n)   x (n)h((n  m))
3 N
n 0
• y(n)={3,2,2,0,4,6,5,3,3,4,3,1}
 Fast Fourier Transform
• A large amount of work has been devoted to
reducing the computation time of a DFT.
• This has led to efficient algorithms which are
known as the Fast Fourier Transform (FFT)
algorithms.
• Decimation In Time(DIT) Radix-2 Algorithm
• Decimation In Frequency(DIF) Radix-2 Algorithm
Fast Fourier Transform(FFT) X k   N 1
 
N 1 j
2
nk
 x n W nk
N

X k    xne N n 0

1 N 1

j
2
n 0
x n    X k WN nk
e N
 WN (TwiddleFac tor (or ) PhaseFactor ) N n 0
N 2 2 N 2 2
k j k j j k j k
 j
WN 2
e N
e N 2
e N
e  e N
 WNk , Symmetry Pr operty
N 2 2 N 2
k j k j j k
N 2 N 22 N 2
WN 2
e e e  W Nk , Periodicity Pr operty
2 2
N-Point DFT DFT FFT
N(N-1) N2 complex ‘×’ N/2 log2(N) N log2(N)
complex ‘+’ complex ‘×’. complex ‘+’.

8 56 64 12 24
16 240 256 32 64
32 992 1024 80 160
64 4032 4096 192 384
128 16256 16384 448 896
 DIT Radix-2 FFT Algorithm
• Let us consider the computation of the N-Point DFT

N  rm
,r-Radix, m- No. of Stages
First Step: x[n] = x[0], x[1], …, x[N-1]
Split the N-point data sequences into two N/2-point
data sequences f1(n) and f2(n)
Lets divide the sequence x[n] into even and odd
Sequences

N 
; n  0,1, 1 
f1(n) =x[2n] = x[0], x[2], …, x[N-2] 2    (1)
N 
f2(n) =x[2n+1] = x[1], x[3], …, x[N-1] ; n  0,1,   1
2 
 N 1
X k    xnWNnk ; 0  k  N  1 N-point DFT
n 0
N N
1 1
2 2
X k    x 2 n 
W N
2 nk
  x 2 n  1WN
 2 n 1k
n0 n 0
2 2
j 2 nk j nk
WN2 nk  e N
e N 2
 W Nnk
2

WN2 n 1k  WNk  W Nnk

2
N N
1 1

X k    x2nWNnk  WNk  x2n  1WNnk

2 2

n 0 2 n 0 2
N N
1 1
2 2
  f1 (n)WNnk  WNk  f 2 (n)WNnk
n 0 2 n 0 2

X k   F1 k   WNk F2 k ; k  0, N  1        (2)

• Where F1(k) and F2(k) N/2-point DFTs
N
1
2
F1 k    f1 ( n)W Nnk
n 0 2
N
1
2
F2 k    f 2 ( n)W Nnk
n 0 2

• Since F1(k+N/2)= F1(k) and F2(k+N/2)= F2(k), WNk  N / 2  WNk

Symmentry
N  Property
X k   F1 k   WNk F2 k ; k  0,   1      (3.1)
2 
 N N 
X  k    F1 k   WN F2 k ; k  0,   1      (3.2)
k

 2 2 
Second Step: Split the N/2-point data sequences into
two N/4-point sequences
 N 
 v11(n) =f1(2n) ; n  0,1,  
 4

 1



 v12(n) =f1(2n+1)--------------- (4.1)

 N 
 v21(n) =f2(2n) ; n  0,1,  
 4
 1


 v22(n) =f2(2n+1)----------------(4.2)
N
1
2
F1 k    f1 (n)WNnk
n 0 2
N N
1 1
4 4
  f1 (2n)W N2 nk   f1 (2n  1)WN( 2 n1) k
n 0 2 n 0 2
N N
1 1
4 4
  v11 (n)WNnk  WNk  v12 ( n)W Nnk  V11 k   W NkV12 k     (5)
n 0 4 2 n 0 4 2
 F 1 k   V11 k   W NkV12 k ; k  0,1,..........., ( N  1)
2
4

 N
F k    V11 k   W N V12 k     (6.1)
k

1 4  2
N
F 2 k   V21 k   W N V22 k 
k ; k  0,1,..........., (
4
 1)
2

 N
F k    V21
k   W  
N V22 k    (6.2)
k

2 4  2

• Where V11(k),V12(k),V21(k) and V22(k)

• N/4 point DFT of the sequences v11(n),v12(n),v21(n) and v22(n)
N N
1 1

V11 k    v11 (n)WN ;V12 k    v12 (n)WN

4 4
nk nk

n 0 4 n 0 4
N N
1 1

V21 k    v21 (n)WN ;V22 k    v22 ( n)W N

4 4
nk nk

n 0 4 n 0 4
 3
• N=8, N2 - Three Stages
• Four 2-point(N/4) DFT’s --->Two 4-point(N/2) DFT’s --->One 8-point (N)DFT
v11(n) =f1(2n)
 v11(0) = f1(0) = x(0) v12(n) =f1(2n+1)
 v11(1) = f1(2) = x(4) v21(n) =f2(2n)
v22(n) =f2(2n+1) ; n=0,1,…(N/4-1)
 v12(0) = f1(1) = x(2) f1(n) =x[2n]
 v12(1) = f1(3) = x(6) f2(n) =x[2n+1] ; n=0,1,…(N/2-1)
Bit Re versal  Shuffling ofData
 v21(0) = f2(0) = x(1) x0  x000  x000  x0
 v21(1) = f2(2) = x(5) x1  x001  x100  x4
x2  x010  x010  x2
 v22(0) = f2(1) = x(3) x3  x011  x110   x6
x4  x100  x001  x1
 v22(1) = f2(3) = x(7)
x5  x101  x101  x3
x6  x110   x011  x5
x7  x111  x111  x7
• FirstNStage-Four 82-point(N/4) DFT’s
1 1
4 4 1
V11 k    11
v ( n )W nk
N   11
v ( n )W 8
nk
  11
v ( n )W2
nk

n 0 4 n 0 4 n 0 V11 0

 v11 (0)W2( 0 ) k  v11 (1)W2(1) k V11 1

k  0;V11 0   v11 (0)W2( 0 ) 0  v11 (1)W2(1) 0
 v11 (0)  W20 v11 (1)  x (0)  W80 x(4) V12 0 

k  1;V11 1  v11 (0)W2( 0 )1  v11 (1)W2(1)1 V12 1

 v11 (0)  v11 (1)W21  x (0)  W80 x ( 4)

V12 0   x( 2)  W80 x(6) V21 0 

V12 1  x( 2)  W80 x(6) V21 1

V21 0   x (1)  W80 x(5)

V22 0 
V21 1  x (1)  W80 x (5)
V12 1
V22 0   x(3)  W x(7)
8
0
2 ( 0 )
V22 1  x(3)  W x(7)0 j
8 W80  e 8
1
 Second Stage-Two 4-point(N/2) DFT’s
F1 0 

F 1 k   V11 k   WNkV12 k   V11 k   W8kV12 k 

2 2
F1 1

k  0; F 1 0   V11 0   W40V12 0  V11 0   W80V12 0 

F1 2 
k  1; F 1 1  V11 1  W V 1  V11 1  W V 1
1
4 12
2
8 12

 N  8 F1 3
F  k    V11 k   WNkV12 k   F  k    V11 k   W8kV12 k 
1 4 2 1 4 2

k  0; F 1 2   V11 0   W40V12 k   V11 0   W80V12 k 

F2 0 
k  1; F 1 3  V11 1  W V 1  V11 0   W V k 
1
4 12
2
8 12

k  0; F 2 0   V21 0   W40V22 0   V21 0   W80V22 0  F2 1

k  1; F 2 1  V21 1  W41V22 1  V21 1  W82V22 1

F2 2 
k  0; F 2 2   V21 0   W40V22 0   V21 0   W80V22 0 
k  1; F 2 3  V21 1  W41V22 1  V21 1  W82V22 1 F2 3
2 2
j 2 nk j nk
WN2 nk  e N
e N 2
 W Nnk j
2 ( 0 )

2 W8  e
0 8
1
WN2 n 1k  WNk  W Nnk j
2 ( 2 )
j


2 W8  e
2 8
e 2
j
 Third Stage-One 8-point(N) DFT
X k   F1 k   WNk F2 k 
k  0; X 0   F1 0   W80 F2 0 
k  1; X 1  F1 1  W81 F2 1
k  2; X 2   F1 2   W82 F2 2 
k  3; X 3  F1 3  W83 F2 3
 N
X k    F k   W k
F2 k 
2
1 N

k  0; X 4   F1 0   W80 F2 0 
k  1; X 5  F1 1  W81 F2 1 2 ( 0 )
j

k  2; X 6   F1 2   W82 F2 2  W e 1
0 8
8
2  (1 ) 
j j

k  3; X 7   F1 3  W8 F2 3
3 W8  e
1 8
e 4
 0707  j 0.707
2 ( 3) 3
j j
W8   j;W8  e
2 3 8
e 4
 0707  j 0.707
 1st stage 2nd stage 3rd stage
x(0) X(0)

W 80
x(4) X(1)
-1
W 80
x(2) X(2)
-1
W 80 W8 1
x(6) X(3)
-1 -1
W8 0
x(1) X(4)
-1
W80=1 W 80 W8 1
x(5) X(5)
-1 -1
W 80 W8 2
x(3) X(6)
-1 -1
W 80 W 81 W8 3
x(7) X(7)
-1 -1 -1
Decimation In Frequency(DIF) Radix-2 Algorithm
• Frequency Domain sequence is decimated
• Butterfly Diagram
Decimation In Frequency(DIF) Radix-2 Algorithm
 DIT DIF

• Time Domain Sequence Frequency Domain

decimated Sequence decimated
• Input Sequence is bit Normal order
Reversal order
• Output sequence is Bit-reversal order
Normal order
• Phase factor is Multiplied After subtraction
Before addition & subtraction
 Problems
• x(n)={1,-1,-1,-1,1,1,1,-1}
• First Stage

V11 0

V11 (0)  x(0)  W80 x( 4)  1  1.1  2 V11 1

V11 1  x(0)  W80 x( 4)  1  1.1  0
V12 0   x (2)  W80 x (6)  1  1.1  0 V12 0 

V12 1  x( 2)  W80 x(6)  1  1.1  2 V12 1

V21 0   x (1)  W80 x(5)  1  1.1  0
V21 1  x(1)  W80 x(5)  1  1.1  2 V21 0 
V22 0   x (3)  W80 x(7)  1  1.( 1)  2
V21 1
V22 1  x (3)  W80 x(7)  1  1.( 1)  0
V22 0 

V12 1
2 ( 0 )
j
W80  e 8
1
 Second Stage
F1 0 

F1 1
F 1 0  V11 0  W80V12 0  2  1.0  2
F1 2 
F 1 1  V11 1  W8 V12 1  0  ( j )(2)  2 j
2

F 1 2  V11 0  W80V12 k   2  1.0  2 F1 3

F 1 3  V11 0  W82V12 k   0  ( j )(2)  2 j

F2 0 
F 2 0  V21 0  W8 V22 0  0  1.(2)  2
0

F 2 1  V21 1  W82V22 1  2  ( j ).0  2 F2 1

F 2 2  V21 0  W80V22 0  0  1(2)  2 F2 2 

F 2 3  V21 1  W82V22 1  2  ( j ).0  2 F2 3

2 ( 0 )
j
W8  e
0 8
1
2 ( 2 ) 
j j
W8  e
2 8
e 2
j
 Third Stage

X 0   F1 0   W80 F2 0   2  1.(2)  0
X 1  F1 1  W81 F2 1  2 j  (0.707  j 0.707)(2)
 1.414  j 3.414
X 2   F1 2  W82 F2 2   2  j 2
X 3  F1 3  W83 F2 3  1.414  j 0.585
X 4   F1 0  W80 F2 0   4
X 5  F1 1  W81 F2 1  1.414  j 0.585
X 6   F1 2  W82 F2 2   2  j 2
X 7   F1 3  W83 F2 3  1.4142  j 3.414
2 ( 0 )
j
W8  e
0 8
1
2  (1 ) 
j j
W8  e
1 8
e 4
 0707  j 0.707
2 ( 3) 3
j j
W8   j;W8  e
2 3 8
e 4
 0707  j 0.707
 Application of FFT Algorithm
• Linear Filtering
• Correlation
• Spectrum Analysis
 Use Of FFT in Linear Filtering and
Correlation
• Let h(n).0nM-1,be the sample response of the FIR
filter
• x(n)-Input data Sequence
Linear Filter
h( n) y ( n) Output or
Input x( n) Response
• The block size of the FFT Algorithm is N
• N=L+M-1 and L is the number of new data samples
being processed by the filter.
• N is a power of 2 . N  23
1. The N-point DFT of h(n),which is padded by L-1 zeros,
is denoted as H(K) using either DIT or DIF algorithm
2. The N-point DFT of x(n), is denoted as X(K) using
either DIT or DIF algorithm.
3. Multiply X(k) and H(K), Y(k)=X(k).H(K)
4. The inverse DFT can be computed by use of an FFT
algorithm
• Step 1: Conjugate of Y(K) *
1 N 1
nk 
y( n )  DIT 
• Step 2: DFT of Y*(k) using either
*
orYDIF( k )radix-2
WN 
N  n 0 
Algorithm
• Step 3:conjugate of result of step 2
• Step 4: The result of Step 3 Divided by N, we get y(n).
 Determine the response of LTI system when the input sequence
x(n)={-1,1,2,1,-1} by radix-2 DIT FFT. The impulse response of the
systems is h(n)={-1,1,1,-1}
• L=5,M=4,N=L+M-1=8
• x(n)= {-1,1,2,1,-1,0,0,0}
• h(n)={-1,1,1,-1,0,0,0,0}
• Determine X(K) using DIT or DIF algorithm
• X(K)={ 2,- 3.414j,-4,0.585j,-2,-0.5858j,-4,3.414j
• Determine H(K) using DIT or DIF algorithm
• H(K)={ 0,-1- 0.414j,0,-1-2.414j,-4,-1+2.414j,0,-1+0.414j}
• Y(k)={0,-1.413+3.414j,0,1.412-j0.585,8,1.12+0.585j,0,-1.413-3.414j}
• Y*(k)={0,-1.413-3.414j,0,1.412+j0.585,8,1.12-0.585j,0,-1.413+3.414j}
• DFT of Y*(k) using Either DIT or DIF
• The result of previous step divide by N=8
• y(n)={1,-2,0,-1,1,0,2,-1}
Inverse FFT
X[K]={2,-6j,2-8j,6j,2-6j,2+8j,6j,0}