DECIMATION IN

TIME AND FREQUENCY

 INDEX

 INTRODUCTION TO FFT
 DECIMATION IN TIME(DIT)
 DECIMATION IN FREQUENCY(DIF)
 DIFFERENCES AND SIMILARITIES
 Fourier Transform
A fourier transform is an useful analytical
tool that is important for many fields of
application in the digital signal processing.
 In describing the properties of the fourier
transform and inverse fourier transform, it
is quite convenient to use the concept of
time and frequency.
 In image processing applications it plays a

critical role.
 Fast fourier transform
 Fast fourier transform proposed by Cooley
and Tukey in 1965.
 The fast fourier transform is a highly
efficient procedure for computing the DFT
of a finite series and requires less number
of computations than that of direct
evaluation of DFT.
 The FFT is based on decomposition and
breaking the transform into smaller
transforms and combining them to get the
total transform.
 Discrete Fourier Transform
The DFT pair was given as
N −1 1 N− 1
X [ k ] = ∑ x[n]e − j ( 2π / N ) kn x[n] = ∑ X[k ] e j( 2π / N) kn
N k=0
n= 0
Baseline for computational complexity:

Each DFT coefficient requires

N complex multiplications
N-1 complex additions

All N DFT coefficients require

N2 complex multiplications
N(N-1) complex additions
 What is FFT?
 The fast fourier is an algorithm used to
compute the DFT. It makes use of the
symmetry and periodicity properties of
twiddle factor wN to effectively reduce the
DFT computation time.
 It is based on the fundamental principle of
decomposing the computation of DFT of a
sequence of length N into successively
smaller DFT.
Symmetry and periodicity

kn ∗ − kn
Symmetry (W ) = W
N N
k (n+ N ) (k + N )n
Periodicity W kn
N =W N =W N
− kn k ( N −n) n( N −k )
W N =W N =W N

W nk
N =W mnk
mN , W nk
N =W nk / m
N /m
( k + N/ 2 )
W N
N/ 2
= −1, W N = −W k
N
 FFT algorithm provides speed increase
factors, when compared with direct
computation of the DFT, of approximately
64 and 205 for 256 point and 1024 point
transforms respectively.
 The number of multiplications and
additions required to compute N-point DFT
using radix-2 FFT are Nlog2N and N/2
log2N respectively.
 Example:

The number of complex multiplications

required using direct computation is
N2=642 =4096
The number of complex multiplications
required using FFT is
N/2log2 N=64/2log2 64=192
Speed improvement factor =4096/192=
21.33.
 FFT Algorithms
 There are basically two types of FFT
algorithms.
 They are:
1. Decimation in Time
2. Decimation in frequency
 Decimation in time
 DIT algorithm is used to calculate the DFT
of a N-point sequence.
 The idea is to break the N-point sequence
into two sequences, the DFTs of which
can be obtained to give the DFT of the
original N-point sequence.
 Initially the N-point sequence is divided
into N/2-point sequences xe(n) and x0(n) ,
which have even and odd numbers of x(n)
respectively.
 The N/2-point DFTs of these two
sequences are evaluated and combined to
give the N-point DFT.
 Similarly the N/2-point DFTs can be
expressed as a combination of N/4-point
DFTs.
 This process is continued until we are left
with two point DFT.
 This algorithm is called decimation-in-time
because the sequence x(n) is often split
into smaller sequences.
 Radix-2 DIT- FFT Algorithm
Radix-2: the sequence length N satisfied: N = 2L
L is an integer

 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.
 Radix-2 DIT- FFT Algorithm
1 signal of 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
points

2 signals of 8
0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15
points

4 signals of 4 0 4 8 12 2 6 10 14 1 5 9 13 3 7 11 15
points

8 signals of 2
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
points

16 signals of 1
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
point
 Radix-2 DIT- FFT Algorithm
 Algorithm principle
 To divide N-point sequence x(n) into two N/2-point
sequence x1(r) and x2(r)
N
x1 ( r ) = x( 2r ); x 2 ( r ) = x ( 2r + 1) , r = 0,1,2,  − 1
2
 To compute the DFT of x1(r) and x2(r)
N N
−1 −1
2 2
N
X 1 ( k ) = ∑ x1 ( r )W rk
N = ∑ x ( 2r )W rk
N (k = 0 ~ − 1)
r =0 2 r =0 2 2
N N
−1 −1
2 2
N
X 2 ( k ) = ∑ x 2 ( r )W rk
N = ∑ x ( 2r + 1)W rk
N (k = 0 ~ − 1)
r =0 2 r =0 2 2
 To compute the DFT of N-point sequence x(n)

N −1 N −1 N −1
X ( k ) = ∑ x( n)W nk
N = ∑ x(n)W nk
N + ∑ x(n)W nk
N
n= 0 n = 0 ( even ) n = 0 ( odd )
N N
−1 −1
2 2
= ∑ x
r =0
( 2 r )W 2 rk
N + ∑ x ( 2
r =0
r + 1)W ( 2 r +1 ) k
N

N N
−1 −1
2 2
= ∑ x (r )W
r =0
1
rk
N +W k
N ∑ x (r )W
r =0
2
rk
N
2 2

= X 1 ( k ) + W Nk X 2 ( k ) ( k = 0,1,2,  N − 1)
 N
X ( k ) = X 1 ( k ) + W X 2 ( k ) ( k = 0,1,  − 1)
k
N
2
N
N N ( k + ) N
X (k + ) = X 1 (k + ) + W N 2
X 2 (k + )
2 2 2
N
= X 1 (k ) − W N X 2 (k )
k
( k = 0,1,  − 1)
2

x1 ( r ) X 1 (k )
x(n) X (k )
x2 (r ) X 2 (k )
  Butterfly computation flow graph

N
X (k ) = X 1 (k ) + W X 2 (k )
k
N ( k = 0,1,  − 1)
2
N N
X ( k + ) = X 1 ( k ) − W Nk X 2 ( k ) ( k = 0,1,  − 1)
2 2

X 1 (k ) X 1 ( k ) + W Nk X 2 ( k )

W Nk
X 2 (k ) X 1 ( k ) − W Nk X 2 ( k )
−1

There are 1 complex multiplication and 2 complex additions

 X 1 ( 0)
x1 (0) = x (0) X ( 0)
X (1)
x1 (1) = x ( 2) N/2- 1
X (1)
x1 ( r ) point X ( 2)
x1 ( 2) = x (4) 1
X ( 2)
DFT
X 1 ( 3)
x1 ( 3) = x (6) X ( 3)
X 2 ( 0) W N0
x 2 (0) = x (1) −1 X ( 4)
X 2 (1) W N1
x 2 (1) = x ( 3) N/2-
−1 X ( 5)
x2 ( r ) point X 2 ( 2) W N2
x 2 ( 2) = x ( 5) −1 X ( 6)
DFT
X 2 ( 3) W N3
x 2 ( 3) = x ( 7 ) −1 X (7)

N-point DFT
 Radix-2 DIT- FFT Algorithm
 The computation complexity for N = 2 3
x (n) X (k )
2-point
Synthesize
DFT
the 2-point
2-point DFTs into a
DFT 4-point DFT Synthesize
the 4-point
2-point Synthesize DFTs into a
DFT the 2-point 8-point DFT
2-point DFTs into a
DFT 4-point DFT

3-stage synthesize, each has N/2 butterfly computation

 Radix-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.
 The distance between two nodes in a butterfly
For N = 2 L there are L stages
Stage Distance
stage 1 1
stage 2 2
stage 3 4

stage L 2 L −1
 Radix-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
 Why is the input bit-reversed order

n0 n1 n2
0 x (000) x (0)
0
0 1 x (100) x (4)
0
1 x (010) x (2)
x ( n2 n1n0 ) 1 x (110) x (6)
0
0 x (001) x (1)
1 1 x (101) x (5)
0
1 x (011) x (3)
1
x (111) x (7 )
  How to get the bit-reversed order

Let n represent the natural order, the n̂ represent the

bit-reversed order, then:

if nˆ > n , x ( n) ⇔ x ( nˆ )

A(0) A(1) A( 2) A( 3) A(4) A(5) A(6) A(7 )

n x (0) x (1) x ( 2) x ( 3) x ( 4) x ( 5) x ( 6) x(7)

n̂ x ( 0) x ( 4) x ( 2) x ( 6) x (1) x ( 5) x ( 3) x(7)
 Decimation-In-Frequency
 It is a popular form of FFT algorithm.
 In this the output sequence x(k) is divided
into smaller and smaller subsequences,
that is why the name decimation in
frequency,
 Initially the input sequence x(n) is divided
into two sequences x1(n) and x2(n)
consisting of the first n/2 samples of x(n)
and the last n/2 samples of x(n)
respectively
 Radix-2 DIF- FFT Algorithm
 Algorithm principle
 To divide N-point sequence x(n) into two N/2-point
sequence
N
The former N/2-point x( n), 0 ≤ n ≤ −1
2
N N
The latter N/2-point x( n + ), 0 ≤ n ≤ − 1
2 2
x (n) 0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7

butterfly computation

0 1 2 3 0 1 2 3

0 1 2 3 0 1 2 3

butterfly computation butterfly computation

0 1 0 1 0 1 0 1

0 1 0 1 0 1 0 1

butterfly butterfly butterfly butterfly

X (k ) 0 4 2 6 1 5 3 7
  To compute the DFT of N-point sequence x(n)

N
−1
N −1 2 N −1
X ( k ) = ∑ x ( n)W nk
N = ∑ x(n)W nk
N + ∑ x(n)W nk
N
n=0 n=0 N
n=
2
N N
−1 −1
2 2 N
N ( n+
∑ x(n)W + ∑ x ( n + )W N
)k
= nk
N
2

n=0 n=0 2
N
−1
2  N
N  nk
= ∑  x ( n) + W N x ( n + )W N
k
2

n=0  2 
N
−1
2
 N  nk
= ∑  x ( n) + ( −1) x ( n + )W N
k
( k = 0,1,  N − 1)
n=0  2 
 Radix-2 DIF- FFT Algorithm
 To separate the even and odd numbered samples
of X(k)
N
let k = 2r , k = 2r + 1, ( r = 0,1,  , − 1)
2
N
−1
2
 x ( n) + x ( n + N )W nr ( r = 0,1,  N − 1)
X ( 2r ) = ∑ 
n=0  2  N
 2 2
N
−1
2
 N  n nr N
X ( 2r + 1) = ∑  x ( n) − x ( n + )W N W N ( r = 0,1,  − 1)
n=0  2  2 2
 Radix-2 DIF- FFT Algorithm

 N
 x1 ( n) = x ( n) + x ( n + )
 2 N
let  n = 0,1,  − 1
 N  n 2
 x 2 ( n) =  x ( n) − x ( n + )W N

  2 
N
−1
2
N
X ( 2r ) = ∑ x (n)W
n= 0
1
nr
N
2
( r = 0,1,  − 1)
2
N
−1
2
N
X ( 2r + 1) = ∑ x (n)W
n=0
2
nr
N
2
( r = 0,1,  − 1)
2
 Radix-2 DIF- FFT Algorithm
 Butterfly computation flow graph

x(n) N
x1 ( n) = x( n) + x( n + )
2

N W Nn  N  n
x( n + ) x 2 ( n ) =  x ( n ) − x ( n + ) W N
2 −1  2 

There are 1 complex multiplication and 2 complex additions

 for N = 2 3

x1 (0)
x ( 0) X ( 0)
x1 (1)
x(1) N/2- X ( 2)
point
x1 ( 2)
x ( 2) X ( 4)
DFT
x1 ( 3)
x ( 3) X ( 6)
W N0 x 2 ( 0)
x ( 4) −1 X (1)
W N1 x 2 (1)
x ( 5) N/2- X ( 3)
−1
W N2 x 2 ( 2) point
x ( 6) −1 X ( 5)
DFT
W N3 x 2 ( 3)
x(7) −1 X (7)
 for N = 2 3

x ( 0) X ( 0)
W N0
x (1) X ( 4)
−1
W N0
x ( 2) X ( 2)
−1
W N2 W N0
x ( 3) X ( 6)
−1 −1
0
W N
x ( 4) X (1)
−1
W N1 W N0
x ( 5) X ( 5)
−1 −1
W N2 W N0
x ( 6) X ( 3)
−1 −1
W N3 W N2 W N0
x(7) X (7)
−1 −1 −1
 Radix-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
 Radix-2 DIF- FFT Algorithm

 Both DIT-FFT and DIF-FFT have the identical

computation complexity. i.e. for N = 2 L , there are
total L stages and each has N/2 butterfly
computation. Each butterfly computation has 1
multiplication and 2 additions.
 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.