Decimation in time and frequency

useful for pg students

1. DECIMATION IN DECIMATION IN
TIME AND FREQUENCYTIME AND FREQUENCY
Dr. C. SarithaDr. C. Saritha
Lecturer in ElectronicsLecturer in Electronics
SSBN Degree & PG CollegeSSBN Degree & PG College
ANANTAPUR ANANTAPUR

2. INDEX
INTRODUCTION TO FFTINTRODUCTION TO FFT
DECIMATION IN TIME(DIT)DECIMATION IN TIME(DIT)
DECIMATION IN FREQUENCY(DIF)DECIMATION IN FREQUENCY(DIF)
DIFFERENCES AND SIMILARITIESDIFFERENCES AND SIMILARITIES

3. Fourier TransformFourier Transform
A fourier transform is an useful analytical A fourier transform is an useful analytical
tool that is important for many fields of tool that is important for many fields of
application in the digital signal processing.application in the digital signal processing.
In describing the properties of the fourier In describing the properties of the fourier
transform and inverse fourier transform, it transform and inverse fourier transform, it
is quite convenient to use the concept of is quite convenient to use the concept of
time and frequency.time and frequency.
In image processing applications it plays aIn image processing applications it plays a
critical role. critical role.

4. Fast fourier transformFast fourier transform
Fast fourier transform proposed by Cooley Fast fourier transform proposed by Cooley
and Tukey in 1965.and Tukey in 1965.
The fast fourier transform is a highly The fast fourier transform is a highly
efficient procedure for computing the DFT efficient procedure for computing the DFT
of a finite series and requires less number of a finite series and requires less number
of computations than that of direct of computations than that of direct
evaluation of DFT.evaluation of DFT.
The FFT is based on decomposition and The FFT is based on decomposition and
breaking the transform into smaller breaking the transform into smaller
transforms and combining them to get the transforms and combining them to get the
total transform.total transform.

5. DiscrDiscrete Fourier Transformete Fourier Transform
The DFT pair was given asThe DFT pair was given as
Baseline for computational complexity: Baseline for computational complexity:
Each DFT coefficient requiresEach DFT coefficient requires
N complex multiplicationsN complex multiplications
N-1 complex additionsN-1 complex additions
All N DFT coefficients requireAll N DFT coefficients require
NN
22
complex multiplications complex multiplications
N(N-1) complex additionsN(N-1) complex additions
[]
( )
å
-
=
p
=
1N
0k
knN/2j
ekX
N
1
]n[x[]
( )
å
-
=
-
=
1
0
/2
][
N
n
knNj
enxkX
p

6. What is FFT?What is FFT?
The fast fourier is an algorithm used to The fast fourier is an algorithm used to
compute the DFT. It makes use of the compute the DFT. It makes use of the
symmetry and periodicity properties of symmetry and periodicity properties of
twiddle factor wtwiddle factor w
N N to effectively reduce the to effectively reduce the
DFT computation time.DFT computation time.
It is based on the fundamental principle of It is based on the fundamental principle of
decomposing the computation of DFT of a decomposing the computation of DFT of a
sequence of length N into successively sequence of length N into successively
smaller DFT.smaller DFT.

7. Symmetry and periodicitySymmetry and periodicity
Symmetry
Periodicity
)()(
)()(
)(
kNn
N
nNk
N
kn
N
nNk
N
Nnk
N
kn
N
kn
N
kn
N
WWW
WWW
WW
---
++
-*
==
==
=
k
N
N/k
N
N/
N
mnk
mN
nk
N
mnk
mN
nk
N
WWW
WWWW
-=-=
==
+)2(2
/
/
,1
,

8. FFT algorithm provides speed increase FFT algorithm provides speed increase
factors, when compared with direct factors, when compared with direct
computation of the DFT, of approximately computation of the DFT, of approximately
64 and 205 for 256 point and 1024 point 64 and 205 for 256 point and 1024 point
transforms respectively.transforms respectively.
The number of multiplications and The number of multiplications and
additions required to compute N-point DFT additions required to compute N-point DFT
using radix-2 FFT are Nlogusing radix-2 FFT are Nlog
22N and N/2 N and N/2
loglog
22N respectively.N respectively.

9. Example:Example:
The number of complex multiplications The number of complex multiplications
required using direct computation isrequired using direct computation is
NN
22
=64=64
22
=4096 =4096
The number of complex multiplications The number of complex multiplications
required using FFT is required using FFT is
N/2logN/2log
2 2 N=64/2logN=64/2log
2 2 64=19264=192
Speed improvement factor =4096/192= Speed improvement factor =4096/192=
21.33.21.33.

10. FFT AlgorithmsFFT Algorithms
There are basically two types of FFT There are basically two types of FFT
algorithms. algorithms.
They are:They are:
1.1. Decimation in Time Decimation in Time
2.2. Decimation in frequency Decimation in frequency

11. Decimation in timeDecimation in time
DIT algorithm is used to calculate the DFT DIT algorithm is used to calculate the DFT
of a N-point sequence.of a N-point sequence.
The idea is to break the N-point sequence The idea is to break the N-point sequence
into two sequences, the DFTs of which into two sequences, the DFTs of which
can be obtained to give the DFT of the can be obtained to give the DFT of the
original N-point sequence.original N-point sequence.
Initially the N-point sequence is divided Initially the N-point sequence is divided
into N/2-point sequences xinto N/2-point sequences x
ee(n) and x(n) and x
00(n) ,(n) ,
which have even and odd numbers of x(n) which have even and odd numbers of x(n)
respectively.respectively.

12. The N/2-point DFTs of these two The N/2-point DFTs of these two
sequences are evaluated and combined to sequences are evaluated and combined to
give the N-point DFT.give the N-point DFT.
Similarly the N/2-point DFTs can be Similarly the N/2-point DFTs can be
expressed as a combination of N/4-point expressed as a combination of N/4-point
DFTs.DFTs.
This process is continued until we are left This process is continued until we are left
with two point DFT.with two point DFT.
This algorithm is called decimation-in-time This algorithm is called decimation-in-time
because the sequence x(n) is often split because the sequence x(n) is often split
into smaller sequences.into smaller sequences.

13. Radix-2 DIT- FFT AlgorithmRadix-2 DIT- FFT Algorithm
Radix-2: the sequence length N satisfied:
L is an integer
L
N2=

To decompose an N point time domain
signal into N signals each containing a
single point. Each decomposing stage uses
an interlace decomposition, separating the
even- and odd-indexed samples;
 To calculate the N frequency spectra
corresponding to these N time domain
signals.

14. Radix-2 DIT- FFT AlgorithmRadix-2 DIT- FFT Algorithm
0 4 8 12 2 6 10 14 1 5 9 13 3 7 11 15
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
084122106141 9513311715
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 signal of 16
points
0 2 4 6 8 10 12 141 3 5 7 9 11 13 15
2 signals of 8
points
4 signals of 4
points
8 signals of 2
points
16 signals of 1
point

15. Radix-2 DIT- FFT AlgorithmRadix-2 DIT- FFT Algorithm
 Algorithm principle
To divide N-point sequence x(n) into two N/2-point
sequence x
1
(r) and x
2
(r)
1
2
,2,1,0 , )12()( );2()(
21 -=+==
N
rrxrxrxrx 
To compute the DFT of x
1
(r) and x
2
(r)
)1
2
~0( )12()()(
)1
2
~0( )2()()(
1
2
0 2
1
2
0 2
22
1
2
0 2
1
2
0 2
11
-=+==
-===
åå
åå
-
=
-
=
-
=
-
=
N
kWrxWrxkX
N
kWrxWrxkX
N
r
rk
N
N
r
rk
N
N
r
rk
N
N
r
rk
N

16. To compute the DFT of N-point sequence x(n)
)1,2,1,0( )()(
)()(
)12()2(
)()()()(
21
1
2
0 2
2
1
2
0 2
1
1
2
0
)12(
1
2
0
2
1
)(0
1
)(0
1
0
-=+=
+=
++=
+==
åå
åå
ååå
-
=
-
=
-
=
+
-
=
-
=
-
=
-
=
NkkXWkX
WrxWWrx
WrxWrx
WnxWnxWnxkX
k
N
N
r
rk
N
k
N
N
r
rk
N
N
r
kr
N
N
r
rk
N
N
oddn
nk
N
N
evenn
nk
N
N
n
nk
N


17. )1
2
,1,0( )()(
)
2
()
2
()
2
(
)1
2
,1,0( )()()(
21
2
)
2
(
1
21
-=-=
+++=+
-=+=
+
N
kkXWkX
N
kXW
N
kX
N
kX
N
kkXWkXkX
k
N
N
k
N
k
N


)(nx
)(
1rx
)(
2rx
)(
1kX
)(
2kX
)(kX

18. Butterfly computation flow graph
)1
2
,1,0( )()()
2
(
)1
2
,1,0( )()()(
21
21
-=-=+
-=+=
N
kkXWkX
N
kX
N
kkXWkXkX
k
N
k
N


)(
1kX
)(
2kX
k
N
W
)()(
21
kXWkX
k
N
+
)()(
21
kXWkX
k
N
-
1-
There are 1 complex multiplication and 2 complex additions

19. N/2-
point
DFT
N/2-
point
DFT
)0(
1
X
)1(
1
X
)2(
1
X
)3(
1X
)0(
2
X
)1(
2X
)2(
2
X
)3(
2
X
0
NW
1
NW
2
NW
3
NW
)0()0(
1
xx=
)2()1(
1
xx=
)4()2(
1
xx=
)6()3(
1
xx=
)1()0(
2
xx=
)3()1(
2 xx=
)5()2(
2
xx=
)7()3(
2
xx=
)(
1rx
)(
2
rx
)4(X
1-
)5(X
1-
)6(X
1-
)7(X
1-
)0(X
)1(X
)2(X
)3(X
N-point DFT

20. Radix-2 DIT- FFT AlgorithmRadix-2 DIT- FFT Algorithm
for
3
2=N
)(nx
2-point
DFT
2-point
DFT
2-point
DFT
2-point
DFT
Synthesize
the 2-point
DFTs into a
4-point DFT
Synthesize
the 2-point
DFTs into a
4-point DFT
Synthesize
the 4-point
DFTs into a
8-point DFT
)(kX
3-stage synthesize, each has N/2 butterfly computation
 The computation complexity

21. Radix-2 DIT- FFT AlgorithmRadix-2 DIT- FFT Algorithm
•At the end of computation flow graph at any
stage, output variables can be stored in the
same registers previously occupied by the
corresponding input variables.
•This type of memory location sharing is called
in-place computation which results in significant
saving in overall memory requirements.

22. The distance between two nodes in a butterfly
For there are L stages
L
N2=
Stage Stage DistanceDistance
stage 1stage 1 11
stage 2stage 2 22
stage 3stage 3 44
stage stage LL

1
2
-L

23. Radix-2 DIT- FFT AlgorithmRadix-2 DIT- FFT Algorithm
Bit-reversed order
In the DFT computation scheme, the DFT samples X(k)
appear at the output in a sequential order while the input
samples x(n) appear in a different order: a bit-reversed
order.
Thus, a sequentially ordered input x(n) must be reordered
appropriately before the fast algorithm can be implemented.
Let m, n represent the sequential and bit-reversed order in
binary forms respectively, then:
m: 000 001 010 011 100 101 110 111
n: 000 100 010 110 001 101 011 111

24. Why is the input bit-reversed order
1n
2n
)(
012nnnx
0
n
0
1
0
1
0
1
0
1
0
1
0
1
0
1
)000(x
)100(x
)010(x
)110(x
)001(x
)101(x
)011(x
)111(x
)(0x
)(4x
)(2x
)(6x
)(1x
)(5x
)(3x
)(7x

25. How to get the bit-reversed order
Let represent the natural order, the represent the
bit-reversed order, then:
n nˆ
)ˆ()(ˆ nxnxnn Û> , if
)0(A )1(A )2(A )3(A )4(A )5(A )6(A )7(A
)0(x )1(x )2(x )3(x )4(x )5(x )6(x )7(xn
nˆ )0(x )7(x)1(x)4(x )6(x)2(x )3(x)5(x

26. Decimation-In-FrequencyDecimation-In-Frequency
It is a popular form of FFT algorithm.It is a popular form of FFT algorithm.
In this the output sequence x(k) is divided In this the output sequence x(k) is divided
into smaller and smaller subsequences, into smaller and smaller subsequences,
that is why the name decimation in that is why the name decimation in
frequency,frequency,
Initially the input sequence x(n) is divided Initially the input sequence x(n) is divided
into two sequences x1(n) and x2(n) into two sequences x1(n) and x2(n)
consisting of the first n/2 samples of x(n) consisting of the first n/2 samples of x(n)
and the last n/2 samples of x(n) and the last n/2 samples of x(n)
respectivelyrespectively

27. Radix-2 DIF- FFT AlgorithmRadix-2 DIF- FFT Algorithm
 Algorithm principle
To divide N-point sequence x(n) into two N/2-point
sequence
1
2
0 ),
2
(
1
2
0 ),(
-££+
-££
N
n
N
nx
N
nnxThe former N/2-point
The latter N/2-point

28. 0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7
0 1 2 3 0 1 2 3
butterfly computation
0 1 2 3 0 1 2 3
butterfly computation butterfly computation
0 1 0 1 0 1 0 1
butterfly butterfly butterfly butterfly
0 4 2 6 1 5 3 7
0 1 0 1 0 10 1
)(nx
)(kX

29. To compute the DFT of N-point sequence x(n)
)1,1,0( )
2
()1()(
)
2
()(
)
2
()(
)()()()(
1
2
0
1
2
0
2
1
2
0
)
2
(
1
2
0
1
2
1
2
0
1
0
-=
ú
û
ù
ê
ë
é
+-+=
ú
û
ù
ê
ë
é
++=
++=
+==
å
å
åå
ååå
-
=
-
=
-
=
+
-
=
-
=
-
=
-
=
NkW
N
nxnx
W
N
nxWnx
W
N
nxWnx
WnxWnxWnxkX
N
n
nk
N
k
N
n
nk
N
k
N
N
N
n
k
N
n
N
N
n
nk
N
N
N
n
nk
N
N
n
nk
N
N
n
nk
N


30. Radix-2 DIF- FFT AlgorithmRadix-2 DIF- FFT Algorithm
To separate the even and odd numbered samples
of X(k)
)1
2
,,1,0 ( ,12 ,2let -=+==
N
rrkrk 
)1
2
,1,0( )
2
()( )2(
1
2
0 2
-=
ú
û
ù
ê
ë
é
++=å
-
=
N
rW
N
nxnxrX
N
n
nr
N 
)1
2
,1,0( )
2
()( )12(
1
2
0 2
-=
ú
û
ù
ê
ë
é
+-=+å
-
=
N
rWW
N
nxnxrX
N
n
nr
N
n
N 

31. Radix-2 DIF- FFT AlgorithmRadix-2 DIF- FFT Algorithm
)1
2
,1,0( )( )12(
)1
2
,1,0( )( )2(
1
2
0 2
2
1
2
0 2
1
-==+
-==
å
å
-
=
-
=
N
rWnxrX
N
rWnxrX
N
n
nr
N
N
n
nr
N


1
2
,1,0
)
2
()()(
)
2
()()(
let
2
1
-=
ï
ï
î
ï
ï
í
ì
ú
û
ù
ê
ë
é
+-=
++=
N
n
W
N
nxnxnx
N
nxnxnx
n
N


32. Radix-2 DIF- FFT AlgorithmRadix-2 DIF- FFT Algorithm
)(nx
)
2
(
N
nx+
n
NW
1-
)
2
()()(
1
N
nxnxnx ++=
n
N
W
N
nxnxnx )
2
()()(
2 ú
û
ù
ê
ë
é
+-=
Butterfly computation flow graph
There are 1 complex multiplication and 2 complex additions

33. for
3
2=N
N/2-
point
DFT
N/2-
point
DFT
)0(X
)2(X
)4(X
)6(X
)1(X
)3(X
)5(X
)7(X
)0(
1
x
)1(
1
x
)2(
1
x
)3(
1x
)0(x
)1(x
)2(x
)3(x
)4(x
)5(x
)6(x
)7(x
)3(
2x
3
NW
1-
)2(
2
x
2
NW
1-
)1(
2x
1
NW
1-
)0(
2x
0
NW
1-

34. for
3
2=N
)0(x
)2(x
)1(x
)3(x
)4(x
)6(x
)5(x
)7(x
)0(X
)4(X
)2(X
)6(X
)1(X
)5(X
)3(X
)7(X
1-
1-
1-
1-
0
NW
1
NW
2
NW
3
NW
1-
1-
1-
1-
1-
0
NW
1-
0
NW
0
NW
2
NW
1-
0
NW
1-
0
NW
0
NW
2
NW

35. Radix-2 DIF- FFT AlgorithmRadix-2 DIF- FFT Algorithm
 The comparison of DIT and DIF
 The order of samples
DIT-FFT: the input is bit- reversed order and the output
is natural order
DIF-FFT: the input is natural order and the output is bit-
reversed order
 The butterfly computation
DIT-FFT: multiplication is done before additions
DIF-FFT: multiplication is done after additions

36. Radix-2 DIF- FFT AlgorithmRadix-2 DIF- FFT Algorithm
Both DIT-FFT and DIF-FFT have the identical
computation complexity. i.e. for , there are
total L stages and each has N/2 butterfly
computation. Each butterfly computation has 1
multiplication and 2 additions.
L
N2=
Both DIT-FFT and DIF-FFT have the characteristic
of in-place computation.
A DIT-FFT flow graph can be transposed to a DIF-
FFT flow graph and vice versa.