DIGITAL
SIGNAL
PROCESSING
Part 3
Digital Signal Processing
A.S.Kayhan
IIR Filters:
Infinite impulse response (IIR) filters have rational transfer
M
functions as
k
H (z)
bk z
ak z k
k 0
N
k 0
Some IIR filter types are: Butterworth, Chebyshev,
Elliptical.
IIR filters have to be stable.
IIR filters may not have linear-phase.
Digital Signal Processing
A.S.Kayhan
Filter Specifications (Low-pass):
20 log
10
( )
Design analog filter transform to Digital filter
Digital Signal Processing
A.S.Kayhan
Analog Butterworth Filters:
Approximate ideal LPF with magnitude-squared response
H ( )
K ,
0,
c
c
by the following rational function:
H ( )
K 1 a 1 2 a n 1 2 n 2
,
1 b1 2 b n 2 n
bn 0
|H()|2 must be even function of , and denominator
degree must be higher than degree of numerator (lowpass).
Digital Signal Processing
A.S.Kayhan
For maximal flatness at the origin, =0, The first 2n-1
derivatives of |H()|2 must be zero. This requires
i 1, 2 , , n 1 .
a i bi ,
H ( )
K 1 b1 2 b n 1 2 n 2
,
1 b1 2 b n 2 n
bn 0
Maximal flatness also at , =, requires
i 1,2 , , n 1 .
a i bi 0,
Then, we have
2
H ( )
K
1 bn
2n
Digital Signal Processing
A.S.Kayhan
Let |H(=0)|2 = 1. Then
H ( )
1
1 bn
2n
At the half-power frequency
H ( )
1
1
2
1 bn
2n
o
bn
2n
Then, we have the Butterworth response
H ( )
1
1
o
Digital Signal Processing
2n
A.S.Kayhan
Consider the filter specifications:
20 log
10 log
10
/ 10
10
10
H ( ) dB .
2n
2n
dB .
To find n:
Using max and p
10
max
/ 10
10
/ 10
1/ 2n
Using min and s
p
o
2n
10
min
/ 10
Digital Signal Processing
s
o
2n
A.S.Kayhan
Dividing these equations
10
10
min
max
/ 10
/ 10
1
1
s
p
2n
Taking logarithm, we get the filter order as:
10 min / 10 1
log
10 max / 10 1
2 log s
p
Digital Signal Processing
A.S.Kayhan
We can normalize the frequency so that o = 1. Then
2
H ( )
1
1
2n
To find the filter poles, we let =s/j,
H (s) H ( s)
1
1
2n
1 (s / j)
1 ( 1) n s 2 n
then, set the denominator to zero
1 ( 1) n s 2 n 0
( 1) n s 2 n 1
If n is even, then
s 2n 1 e
sk e
1 2 k
j (
)
2n
j ( 2 k )
, k 0 ,1 ,..., 2 n 1 .
, k 0 ,1 ,..., 2 n 1 .
Digital Signal Processing
A.S.Kayhan
If n is odd, then
s 2n 1 e
sk e
k
n
j 2k
, k 0 ,1 ,..., 2 n 1 .
, k 0 ,1 ,..., 2 n 1 .
Note that all the poles lie on a circle with radius 1, because
the frequency is normalized. (If we want to design analog
filter we need to correct this).
Also, choose the poles in the left-half plane to get a stable
filter.
Digital Signal Processing
A.S.Kayhan
Example: Design specs. for a Butterworth LP filter:
At f = 2000 Hz, max= 3dB
At f = 3000 Hz, min= 10dB
Then, the filter order n is
n 2.7154 n = 3.
Poles are at
sk e
k
3
, k 0 ,1 ,..., 5 .
1
( s 1 )( s 2 s 1 )
1
.
1
3
1
3
( s 1 )( s ( j
))( s ( j
))
2
2
2
2
H (s)
Digital Signal Processing
A.S.Kayhan
Analog Chebyshev Filters:
We can generalize Butterworth response as:
H ( )
1
1
.
n
1 F n ( ) 2
1 ( ) 2
Fn() is a function of . Now, consider:
x cos( ) cos 1 ( x )
y n cos( n ) cos( n cos
( x ))
This is the Chebyshev polynomial of order n. When
x 1 , C n ( x ) cosh( n cosh
( x ))
When x 1 , Cn(x) 0.
Digital Signal Processing
A.S.Kayhan
Cn(x) has zeros in -1< x < 1 :
C1(x)
C2(x)
C3(x)
C4(x)
C5(x)
-1
-1
0
x
-1
1 -1
n 1
0
x
-1
-1
0
x
-1
1 -1
(x) 2 x C n (x) C
-1
1 -1
0
x
n 1
0
x
( x ),
C o ( x ) 1, C 1 ( x ) x .
Digital Signal Processing
A.S.Kayhan
Use Cn(.) in :
H ( )
1
1 2 C n2 ( )
1 , C n ( ) cosh( n cosh
1 , C n ( ) cos( n cos
2 1 ,
( ))
( ))
is known as the ripple factor.
Digital Signal Processing
A.S.Kayhan
Behaviour at =0:
C n2 ( ) 0 , H ( 0 )
C n2 ( ) 1 , H ( 0 )
1,
if n is odd
1
,
(1 2 )
if n is even
Behaviour at =1:
C n2 ( ) 1 ,
for all n
H ( 1)
1
(1 2 )
Digital Signal Processing
A.S.Kayhan
The attenuation is
10 log 1 2 C n2 ( )
10
max/ 10
When 2 C n2 ( ) 1 3 . 01 dB .
This defines the half-power frequency (3dB cut-off) hp.
Then,
1
cosh( n cosh
1
1
cosh 1 ( hp )
cosh 1 ( )
n
1
1
hp cosh(
cosh 1 ( )).
n
C n (
hp
Digital Signal Processing
hp
))
hp
1 ).
A.S.Kayhan
The specifications for a Chebyshev filter are max, min, s
(p=1). Bandpass is between 0 1 rad/s.
To find n:
min 10 log 1 2 C n2 ( s )
10 min
With
cosh( n cosh
Finally,
cosh
n
/ 10
10
1
1 2 C n2 ( s )
max/ 10
( s ))
10
/ 10
min
cosh
10
10
1
10
min
/ 10
max
/ 10
max
1
1
/ 10
( s )
Digital Signal Processing
A.S.Kayhan
To find the filter poles, we let =s/j,
H (s) H ( s)
then
1
1 C n2 ( s / j )
2
1 2 C n2 ( s / j ) 0 C n ( s / j ) j
Let
With
cos( x )
cos( w ) cos( u jv ) s / j
cos 1 ( s / j ) w
e
jx
e
2
jx
, cos( jx )
C n ( s / j ) cos( n cos
ex ex
cosh( x )
2
( s / j )) cos( nw )
C n ( s / j ) cos( nu ) cosh( nv ) j sin( nu ) sinh( nv )
Digital Signal Processing
A.S.Kayhan
With
cos( nu ) cosh( nv ) 0
C n (s / j) j
then
sin( nu ) sinh( nv )
cosh(nv) can never be zero, therefore cos(nu) must be
zero. It is possible for
3 5
,
,
,
2n 2n 2n
( 2 k 1 ), k 0 ,1 , , 2 n 1 .
2n
uk
uk
Digital Signal Processing
A.S.Kayhan
For these values of u, sin(nu) = 1, then
vk
Remember that
then
1
sinh
n
cos
1
) a.
( s / j ) w u jv
2 k 1 ja
s k j cos( w k ) j cos
2n
The poles are :
s k k j k , k 0 ,1 , , 2 n 1
2k 1
) sinh( a )
2n
2k 1
cos(
) cosh( a )
2n
sin(
Digital Signal Processing
Choose left
half poles.
A.S.Kayhan
10
Discrete Time Filter Design(IIR):
There are 3 approches:
1-Sampling (Impulse invariance)
2-Bilinear transformation
3-Optimal procedures
Impulse invariance method:
We can sample the impulse response hc(t) of an analog filter
with desired specifications as (Td is sampling interval):
then
h [ n ] T d h c nT
H ( )
H c(
k ).
Td
Td
Digital Signal Processing
If
then
A.S.Kayhan
/ Td
H c ( ) 0 ,
),
.
Td
Analog and digital frequencies have a linear relation:
Td .
H ( ) H c (
Consider the transfer function of a system expressed as
N
H c (s)
k 1
Ak
,
s sk
Then, the impulse response is
N
hc (t )
Ak e skt ,
t 0.
k 1
Digital Signal Processing
A.S.Kayhan
11
The impulse response of the discrete time filter is
h n T d h c ( nT
N
d
T d A k e s k nT d u n
k 1
h n
T d ( A k e s k T d ) n u n .
k 1
Transfer (or system) function of the discrete time filter is
N
H (z)
k 1
Poles are
Td Ak
.
1 e sk T d z 1
s s k z e skTd .
If Hc(s) is stable (k < 0), then H(z) is also stable (|z| < 1).
Digital Signal Processing
A.S.Kayhan
Example: Transfer function of analog filter is
1
( s 1 )( s 2 s 1 )
1
1
1
1
j
j
1
2
2
12
12
.
s 1
1
3
1
3
s ( j
)
s ( j
)
2
2
2
2
H c (s)
then
Td
1 z 1e Td
1
1
1
Td ( j
)
Td ( j
2
2
12
H (z)
1 z 1 e
Td (
1
3
j
)
2
2
1 z 1e
Digital Signal Processing
Td (
1
)
12
.
1
3
2
A.S.Kayhan
12
Bilinear Transformation:
Transformation needed to convert an analog filter to a
discrete time filter must have following properties:
1- j axis of the s-plane must be mapped onto the unit
circle of the z-plane,
2- stable analog filters must be tranformed into stable
discrete time filters (left hand plane of the s-plane must be
mapped into inside the unit circle of the z-plane).
Following BT satisfies these conditions:
1 z 1
s K
1 z 1
1 s / K
.
1 s / K
Digital Signal Processing
Let
s j ,
z re
A.S.Kayhan
then
r
(1 / K ) 2 ( / K ) 2
.
(1 / K ) 2 ( / K ) 2
Therefore
0
( LH plane ) r 1 ( inside
( j axis ) r 1 ( the u.c. )
( RH plane ) r 1 ( outside
Digital Signal Processing
the u.c. )
the u.c. )
A.S.Kayhan
13
Digital Signal Processing
Now, let
then
s j ,
z e
1 e j
e j / 2 ( e j / 2 e
j K
K j / 2
1 e j
e
( e j / 2 e
sin( / 2 )
j Kj
jK tan( / 2 ).
cos( / 2 )
or
A.S.Kayhan
j / 2
j / 2
)
.
)
K tan( / 2 ).
Digital Signal Processing
A.S.Kayhan
14
Observations:
1- According to Taylor series expansion of tan(), for small
K / 2 3 / 24 K / 2 .
2- For high frequencies, the relation is nonlinear causing a
distortion called warping effect. Therefore, BT is usually used
for the design of LPF to avoid this.
Digital Signal Processing
A.S.Kayhan
Discrete Butterworth Filter Design:
We convert a frequency normalized analog Butterworth filter
to a discrete filter using the BT.
Normalized half power frequecy HP=1 is mapped into the
discrete half power frequency HP. To do that, we set K to
K b ( HP 1) / tan(HP / 2) cot( HP / 2).
Digital Signal Processing
A.S.Kayhan
15
Then, we use
K b tan(0.5 ) tan(0.5 ) / tan(0.5HP ).
in
H
( )
1
1
2n
And get the discrete Butterworth Low Pass Filter as:
H
( )
tan( 0 . 5 )
1
tan( 0 . 5 HP )
2n
Using the design specifications, we find the filter order as
min / 10
1
log 10
max / 10
10
2 log tan( 0 . 5 s )
tan( 0 . 5 p )
Digital Signal Processing
A.S.Kayhan
The half-power freq. is
HP
2 tan
tan( 0 . 5
10
max
/ 10
1/ 2n
K b cot(0.5 HP ).
Example: Consider the second order analog filter
H
(s)
1
(s2
2 s 1)
Applying the BT, we get (Kb = 1)
( z 1) 2
H 2(z)
0 . 2929
( z 2 0 . 1716 )
Digital Signal Processing
A.S.Kayhan
16
Remarks:
1- Given the specs.:
a) find the filter order n
b) obtain the analog filter H(s)(using LHP poles)
c) calculate HP and Kb
d) use biliear transformation to find H(z).
2- H(z) is BIBO stable, because H(s) is stable.
3- Applying the BT to high order filters may be tedious.
Therefore, first express H(s) as product or some of first
and second order functions, then apply the BT.
Digital Signal Processing
A.S.Kayhan
Example: Design specs. for a LP digital Butterworth filter:
At f = 0 Hz, 1= 18dB
At f = 2250 Hz, 2= 21dB
At f = 2500 Hz, 3= 27dB
Sampling freq. fsmp= 9000 Hz
(ej0)= 18dB
fp
max = 2 1=3dB
fs
p 2
, s 2
min = 3 1=9dB
f smp
f smp
Filter order n 5.52,n = 6, Kb = 1 and a gain G for = 18dB
H 6(z)
(z2
0 . 0037 ( z 1 ) 6
0 . 59 )( z 2 0 . 17 )( z 2 0 . 0 . 02 )
Digital Signal Processing
A.S.Kayhan
17
Discrete Chebyshev Filter Design:
We find the constant K by transforming (normalized
passband freq.) P=1 into the discrete passband frequency
P. We get
K c 1 / tan(0.5P ) tan(0.5 ) / tan(0.5 P )
And get the discrete Chebyshev Low Pass Filter as:
H ( )
1 C
2
n
1
(tan( 0 . 5 ) / tan( 0 . 5
))
Digital Signal Processing
Using C1(1)=1, we let p ,
max 10 log 1
10 min
Also using s ,
We find the filter order
10
max
min
10
1
cosh 1 [tan( 0 . 5 s ) / tan( 0 . 5 p )]
cosh
/ 10
A.S.Kayhan
min
/ 10
Digital Signal Processing
max
/ 10
A.S.Kayhan
18
Example: Design specs. for a LP digital Chebyshev filter:
At f = 0 Hz, 1= 0dB
At f = 2250 Hz, max= 3dB
At f = 2500 Hz, min= 10dB
Sampling freq. fsmp= 9000 Hz
f smp
Filter order n = 3,
H 3(z)
fs
f smp
Kc = 1
(z2
0 . 09 ( z 1 ) 3
0 . 15 z 0 . 72 )( z 0 . 54 )
Digital Signal Processing
A.S.Kayhan
Example: Design specs. for a LP digital Chebyshev filter:
At = 2/5 rad, max= 1dB
At = /2 rad, min= 9dB
Filter order n = 3
H 3(z)
(z2
0 . 736 ( z 1 ) 3
0 . 505 z 0 . 619 )( z 0 . 472 )
Example: Design specs. for a LP digital Butterworth filter:
At = /2 rad, max= 3dB
= 0 rad, = 0dB
At = 5/9 rad, min= 10dB
Filter order n = 7,
H
(z)
z(z2
Kb = 1
0 . 01656 ( z 1 ) 7
0 . 636 )( z 2 0 . 232 )( z 2 0 . 052 )
Digital Signal Processing
A.S.Kayhan
19
Frequency Transformations:
The objective is to obtain transfer functions of other types of
dicrete filters from already available prototype Low Pass
Filters using tranformation functions g(z) as
H (z) H
LP
( g ( z ))
Example: Design specs. for a LP digital Chebyshev filter:
At f = 0 Hz, = 0dB
At f = 2250 Hz, 2= 21dB
At f = 2500 Hz, 3= 27dB
Sampling freq. fsmp= 9000 Hz
Digital Signal Processing
LPF
(z)
z3
A.S.Kayhan
0 . 09 ( z 1 ) 3
0 . 691 z 2 0 . 802 z 0 . 39
Digital Signal Processing
A.S.Kayhan
20
Now, we want a HPF with cutt-off at 3.6kHz, we use
following transformation
( z 1 0 . 5095 )
1
z
HPF
(z)
z3
(1 0 . 5095 z 1 )
0 . 0066 ( z 3 3 z 2 3 z 1 )
2 . 361 z 2 2 . 102 z 0 . 6884
Digital Signal Processing
A.S.Kayhan
Design of FIR Filters by Windowing:
Ideal frequency response and corresponding impulse
response functions are H ( e j ), h n .
d
Generally hd[n] is infinitely long. To obtain a causal practical
FIR filter, we can truncate it as
,0 n M
h n
h n d
, otherwise.
0
In a general form we can write it as
h n h d n w n
Where w[n] is window function.
Digital Signal Processing
A.S.Kayhan
21
In frequency domain, we have
H (e
1
)
2
(e
)W ( e
)d .
Digital Signal Processing
A.S.Kayhan
Some commonly used window functions are Rectangular,
Bartlett, Hamming, Hanning, Blackman, Kaiser.
Some important factors in choosing windows are:
Main lobe width and Peak side lobe level. For rectangular:
Digital Signal Processing
A.S.Kayhan
22
Main lobe width and transition region; Peak side lobe level
and oscillations of filter are related.
Digital Signal Processing
A.S.Kayhan
Digital Signal Processing
A.S.Kayhan
23
Digital Signal Processing
A.S.Kayhan
Digital Signal Processing
A.S.Kayhan
24
Discrete Time Fourier Series (DTFS):
~
Consider a periodic sequence x n with period N:
~
x n x n N .
Which can be represented by a Fourier series as:
N 1
1
x n
N
X [ k ]e
2
nk
N
k0
The DTFS coefficients are obtained as:
N 1 ~
x n e
X [k ]
2
nk
N
n0
Digital Signal Processing
Let
A.S.Kayhan
2
N
The DTFS analysis and synthesis equations are:
N 1 ~
x n W
X [k ]
nk
N
n0
x n
1
N
N 1
X [k ] W
nk
N
k 0
Example: Consider the periodic impulse train:
~
x n
[ n rN ]
The DTFS
~
X [k ]
N 1
n W
nk
N
for all k .
n0
Digital Signal Processing
A.S.Kayhan
25
Properties:
1- Linearity: It is linear.
2- Shift of a sequence: If
x n X [ k ]
x n m W
then
Similarly,
nl
N
km
N
X [k ]
x n X [ k l ]
3- Periodic convolution: Consider two periodic
sequences with period N
~
x 1 n X 1 [ k ]
x 2 n X 2 [ k ]
Then,
~
X 3[ k ] X 1[ k ] X 2 [k ]
x 3 n
N 1 ~
x 1 [ n m ] x 2 [ m ].
m0
Digital Signal Processing
A.S.Kayhan
Example: Consider periodic convolution of two sequences:
Digital Signal Processing
A.S.Kayhan
26
Sampling the Fourier Transform:
Consider signal x[n] with DTFT X() and assume by
sampling X() , we get
~
X [ k ] X ( ) |
2
k
N
X
k
N
X [ k ] could be the sequence of DTFS coefficients
of a periodic signal which may be obtained as
1
x n
N
~
N 1
X [k ] W
nk
N
k 0
Digital Signal Processing
A.S.Kayhan
Substituting,
X
x m
e j m ,
X k X ( ) | 2
then,
x n x n *
n rN
x n
Digital Signal Processing
rN .
A.S.Kayhan
27
If N is too small, then aliasing occurs in the time domain.
If there is no aliasing, we can recover x[n].
Digital Signal Processing
A.S.Kayhan
Discrete Fourier Tranform (DFT):
DFT is obtained by taking samples of the DTFT.
Remember DTFT is defined as:
X (e
x [ n ]e
j n
We take samples of X(ej) at uniform intervals as:
X [k ] X (e
We define:
W
2
k
N
j
, k 0 ,1 , N 1 .
2
N
Digital Signal Processing
A.S.Kayhan
28
Then the DFT is defined as (analysis equation):
N
X [k ]
x[ n ] W
kn
N
n0
for k=0,1,...,N-1.
The inverse DFT is defined as (synthesis equation):
x[ n ]
1
N
X [k ] W
kn
N
n0
for n=0,1,...,N-1.
Digital Signal Processing
A.S.Kayhan
Digital Signal Processing
A.S.Kayhan
Example:
N=5
29
N=10
Digital Signal Processing
Properties:
1- Linearity: DFT is a linear operation.
2- Circular shift:
x n m
N , 0
n N 1 e
Digital Signal Processing
A.S.Kayhan
2
km
N
X [ k ].
A.S.Kayhan
30
3- Circular convolution:
x 3 n x 1 n
x 2 n
N 1
x 1 [ n m
] x2[m ]
m 0
Example:
Digital Signal Processing
A.S.Kayhan
Digital Signal Processing
A.S.Kayhan
Example:
N=L
31
N=2L
Digital Signal Processing
A.S.Kayhan
4- Multiplication(Modulation):
x 3 n x 1 n x 2 n X
k .
Linear Convolution Using the DFT:
Since there are efficient algorithms to take DFT, like FFT,
we can use it instead of direct convolution as:
1. Compute N point DFTs, X 1 k and X 2 k .
2. Multiply them to get X 3 k X 1 k X 2 k .
3. Compute the inverse DFT, to get:
x 3 n x 1 n
x 2 n
Digital Signal Processing
A.S.Kayhan
32
Linear Convolution of Finite Length Signals:
Consider two sequences x1[n] of length L and x2[n] of
length P, and x3[n] = x1[n]* x2[n].
Observe that x3[n] will be of length (L+P-1).
Circular Convolution as Linear Convolution with
Aliasing :
Consider again x1[n] of length L and x2[n] of length P,
and x3[n] = x1[n]* x2[n].
X 3 (e
) X 1 (e
) X 2 (e
Digital Signal Processing
A.S.Kayhan
Taking N samples
X
k X 2 k .
Now, taking the inverse DFT, we have
x 3 n rN , 0 n N 1
x 3 p n r
0,
otherwise.
x 3 p n x 1 n
x 2 n
This circular convolution is identical to the linear
convolution corresponding to X1(ej) X2(ej),
if N (L+P-1).
Digital Signal Processing
A.S.Kayhan
33
Example:
Digital Signal Processing
A.S.Kayhan
Digital Signal Processing
A.S.Kayhan
Example:
34
Digital Signal Processing
A.S.Kayhan
LTI Systems Using the DFT :
Consider x[n] of length L and h[n] of length P, and y[n] =
x[n]* h[n] will be of length (L+P-1).
To obtain the result of linear convolution using the DFT,
we must use N ( (L+P-1))-point DFTs. For that x[n]
and h[n] must be augmented with zeros (zero-padding).
Overlap-Add Method :
Consider h[n] of length P, and length of x[n] is much
grater than P.
We can write x[n] as combination of length L segments:
x n rL , 0 n L 1
x r n
,
0
,
otherwise
Digital Signal Processing
x n
x r n rL
A.S.Kayhan
35
Since the system is LTI then
y n
y r n rL ,
y r n x r n * h n
Each output segment yr[n] can be obtained using (L+P-1)
point DFT.
Example:
Digital Signal Processing
A.S.Kayhan
Digital Signal Processing
A.S.Kayhan
36
Overlap-Save Method :
Consider again h[n] of length P, and length of x[n] is much
grater than P.
In this method L-point circular convolution (or DFT) is
used. Since the first (P-1) points will be incorrect,
input segments must overlap.
We can write each L sample segment of x[n] as :
x r n x n r ( L P 1 ) ( P 1 ) ,
y n
0 n L 1
y r n r ( L P 1 ) ( P 1 ) ,
y r n y rp n , P 1 n L 1
Digital Signal Processing
A.S.Kayhan
Digital Signal Processing
A.S.Kayhan
Example:
37
Efficient Computation of the DFT :
Remember the definition of the DFT and inverse DFT
N 1
x[ n ]
N 1
X [k ] W
kn
N
X [k ]
n0
x[n ] W
kn
N
n0
N2 comlex multiplications and N(N-1) additions or 4N2 real
mult. and 4N(N-2) real additions necessary:
Re{ x [ n ] } Re{ W Nkn }
kn
Im{ x [ n ] } Im{ W N }
Re{ x [ n ] } Im{ W Nkn }
j Im{ x [ n ] } Re{ W kn }
N
X [k ]
n0
Digital Signal Processing
A.S.Kayhan
To improve the efficiency, we can use some properties as:
1) W
2) W
k(N n)
N
k(N n)
N
W
W
kn
N
kn
N
(W
W
kn
N
)*
(k N )n
N
Example:
Re{ x [ n ] } Re{ W
kn
N
} Re{ x [ N n ] } Re{ W
Re{ x [ n ] } Re{ x [ N n ] } Re{ W
Digital Signal Processing
kn
N
k(N n)
N
}.
A.S.Kayhan
38
Fast Fourier Transform(FFT):
Fast Fourier Transform algorithms are used to implement
DFT efficiently to reduce the number of multiplication
and addition operations.
Two main algorithms are:
Decimation in time and Decimation in frequency. Both
these algorithms require that N=2m.
The number of operations using either of these will
require (N/2)log2N complex multiplications and Nlog2N
additions.
Direct implementation of DFT requires N2 complex
multiplications and additions. For N=1024= 210
N2=1048576
but
Nlog2N=10240.
Digital Signal Processing
A.S.Kayhan
Decimation in time FFT Algorithm:
Assume N=2m
N 1
X [k ]
kn
N
x[n ] W
, k 0 ,1 , , N 1
n0
Which can be written as
X [k ]
x[ n ] W
kn
N
n even
x[n ] W
kn
N
n odd
With n = 2r (even) and n = 2r+1 (odd)
N / 2 1
X [k ]
N / 2 1
x [ 2 r ] (W
2
N
) rk W
k
N
r0
x [ 2 r ] (W
rk
N / 2
r0
G k
2
N
) rk
r0
N / 2 1
x [ 2 r 1 ] (W
N / 2 1
) W
k
N
x[ 2 r 1] W
rk
N / 2
r0
k
N
k .
Digital Signal Processing
A.S.Kayhan
39
X [ k ] G k
k
N
k .
Requires N+2(N/2)2 multiplications
Digital Signal Processing
A.S.Kayhan
Since G[k] and H[k] requires 2(m-1)-point DFTs, each one can
be similarly decomposed until we reach 2-point DFTs.
Digital Signal Processing
A.S.Kayhan
40
Digital Signal Processing
A.S.Kayhan
Digital Signal Processing
A.S.Kayhan
Butterfly:
(in place comp.)
Bit reversed
order
41
Decimation in frequency FFT Algorithm:
Again assume N=2m
N 1
X [k ]
x[n ] W
kn
N
, k 0 ,1 , , N 1
n0
then
N 1
X [2 r ]
x[ n ] W
2 rn
N
r 0 ,1 , , ( N / 2 1 )
n0
N / 2 1
X [2 r ]
N 1
x[ n ] W
2 rn
N
n0
2 rn
N
N / 2 1
x[ n ] W
2 rn
N
n0
N / 2 1
X [2r ]
x[ n ] W
nN /2
N / 2 1
X [2 r ]
x[ n N / 2 ] W
2r(n N /2)
N
n0
N / 2 1
( x [ n ] x [ n N / 2 ]) W
rn
N /2
n0
rn
N /2
n0
Digital Signal Processing
Similarly for
g [n ] W
A.S.Kayhan
0 r ( N / 2 1)
N / 2 1
X [ 2 r 1]
( x [ n ] x [ n N / 2 ]) W
n
N
rn
N /2
n0
N / 2 1
h [ n ] W Nn W
rn
N /2
n0
Digital Signal Processing
A.S.Kayhan
42
Procedure is repeated until 2-point DFTs
Digital Signal Processing
A.S.Kayhan
Computation of Inverse DFT:
x[ n ]
1
N
X [ k ]W
kn
N
, n 0 ,1 , , N 1
n0
X [k ]
x[ n ] W
kn
N
, k 0 ,1 , , N 1
n0
1 N
1
x [n]
X * [ k ]W Nkn
DFT
N n0
N
*
1
x[ n ]
DFT X * [ k ]
N
*
[k ]
Digital Signal Processing
A.S.Kayhan
43
End of Part 3
Digital Signal Processing
A.S.Kayhan
44
