1/24/2014

Decimation in Frequency (DIF – FFT)

Algorithm
DIF – FFT Algorithm
 Output sequence X(k) is divided into smaller
and smaller subsequences
1
 Input sequence x(n) partitioned into two sequences each
of length N/2

o x1(n) – first N/2 samples of x(n)

o x2(n) – last N/2 samples of x(n)
N
x1 (n)  x(n) , n  0,1, 2, ........, 1 .....(10)
2
N N
x2 (n)  x(n  ) , n  0,1, 2, ........, 1......(11)
2 2
[email protected] [email protected] 2

when k is even, e  j k  1
The N - point DFT of x(n) can be written as N
1
2
N
2
1
N 1
X(2k)   [x 1 ( n )  x 2 ( n )] W N2nk
X(k)  
n 0
x(n) W nk
N   N
x(n) W nk
N N
n0

1
n 2
  [x ( n )  x 2 ( n )] W Nnk ........ (12) ( WN  WN 2 )
2 2
N N 1
1 1 N n0 2
2 2 (n 
 
)k
 x 1 ( n ) W Nnk  x2 (n) W N
2
This is the N/2-point
N/2 point DFT of the N/2-point
N/2 point sequence
n0 n0

N N
obtained by adding the first half and the last half of the
1 1
2 2 input sequence
 
Nk
X(k)  x1 ( n ) W nk
N  WN 2
x 2 ( n ) W Nnk N
1
2


n 0 n0
N N
X(2k)  f ( n ) W N2nk
1 1 n 0
2 2
 
n 0
x 1 ( n ) W Nnk  e  j  k n0
x 2 ( n ) W Nnk where f ( n )  x 1 ( n )  x 2 ( n ) n  0, 1, 2, ...,
N
1
2
[email protected] 3 [email protected] 4

when k is odd, e  j k   1
N
Eq. (12) and Eq. (13) show that the even and odd samples
1
2 of the DFT can be obtained from the N/2-point DFTs of
X(2k  1)   [x
n 0
1 ( n )  x 2 ( n )] W (2k  1)n
N
f(n) and g(n) respectively.
N
f ( n )  x 1 ( n )  x 2 ( n ) n  0, 1, 2, ..., 1
N
1 where
2
  [x
n 0
1 ( n )  x 2 ( n )] W 2kn
N W n
N
g ( n)  [ x1 (n)  x2 (n)] WN n  0, 1, 2, ...,
n N
2
1
2
N N
1 1
2 2 This can be represented by a butterfly:
 
n 0
[ x 1 ( n )  x 2 ( n )] W Nn W Nnk 
2

n 0
g ( n ) W Nnk ..... (13)
2

This is the N 2  point DFT of the sequence obtained by

subtracting the second half of the input sequence from
the first half & multiplying the resulting sequence by WNn
N
where g (n)  [ x1 (n)  x2 (n)] WNn n  0, 1, 2, ...,  1
2 This is the basic operation of DIF algorithm
[email protected] 5 [email protected] 6

1
 1/24/2014

For N  8, from Eq.(12) For N  8, from Eq.(13)

3 3 3 3
X (0)  [ x1 (n)  x2 (n)]W80   f(n) f (0)  f (1)  f (2)  f (3) X (1)  [ x1 (n)  x2 (n)]W8n   g(n) g(0)  g(1)  g(2)  g(3)
n 0 n 0 n 0 n 0
3 3 3 3
X (2)  [x1(n)  x2 (n)]W82n   f(n)W82n X (3)   [ x1 ( n )  x2 ( n )] W83 n   g(n)W 8
2n

n0 n0 n 0 n 0

 f (0)  f (1)W82  f (2)W84  f (3)W86  f (0)  f (1)W82  f (2)  f (3)W82  g (0)  g (1)W82  g ( 2)  g (3)W82
3 3 3
X (5)   [ x1 ( n)  x2 ( n)] W85 n   g(n)W   g(n) ( 1) n
3 3
X (4)  [x1(n)  x2 (n)]W84n   f(n)W
4n
8
4n
 f (0)  f (1)  f (2)  f (3) 8
n 0 n 0 n 0
n0 n0
3 3  g (0)  g (1)  g ( 2)  g (3)
X (6)  [x1(n)  x2 (n)]W  8
6n
 f(n)(-W ) 8
2 n
 f (0)  f (1)W  f (2)  f (3)W
8
2
8
2
3 3 3
X (7)   [ x1 ( n)  x2 ( n)] W87 n   g(n)W   g(n) (-W82 ) n
n0 n0 6n
8
j 2 j 2 N n0 n 0 n 0
k
W84  (e )  e j  1, W88  (e
8 4 8 8
)  e j 2 1,Symmetry WN 2
 WNk  g (0)  g (1)W82  g ( 2)  g (3)W82
[email protected] 7 [email protected] 8

Reduction of an 8-point DFT to two 4-point DFTs

by decimation in frequency

 The even-valued samples of X(k) can be obtained

from the 4-point DFT of the sequence f(n):
N
where f ( n )  x 1 ( n )  x 2 ( n ) n  0, 1, 2, ..., 1
2

 The odd-valued samples of X(k) can be obtained

from the 4-point DFT of the sequence g(n):
g ( n)  [ x1 (n)  x2 (n)] WNn n  0, 1, 2, ..., N  1
2

[email protected] 9 [email protected] 10

Decimation in frequency decomposition of an 8-

point DFT into four 2-point DFT computations  2-point DFT can be found by adding and
 Each N/2-point DFT can be computed by subtracting the input points.
combining the first half and the last half of the
input points for each of the N/2-point DFTs and
then computing N/4-point DFTs.

[email protected] 11 [email protected] 12

2
 1/24/2014

Flow graph of Complete decimation in frequency Basic Computational diagram for DIF - FFT
decomposition of an 8-point DFT computation

[email protected] 13 [email protected] 14

Steps for Radix – 2 DIF-FFT Algorithm

1. The number of input samples, N = 2M , M is an integer 8. The twiddle factor exponents are functions of stage
Nt
index m, k t  0, 1, 2, ......, 2 M - m  1 ……. (14)
2. The input sequence is in natural order 2 M  m 1

3. The number of stages in the flow graph is M = log2N 9. The number of sets of sections of butterflies in each

4 Each stage consists of N/2 butterflies

4. stage is given by the formula 2m-1

5. Inputs/outputs for each butterfly are separated by 2M-m 10. The exponent repeat factor (ERF) – the number of

m represents the stage index. ie; for first stage m = 1 times the exponent sequence associated with m is

6. The number of complex multiplications = (N/2) log2N repeated - 2m-1

7. The number of complex additions = N log2N

[email protected] 15 [email protected] 16

DIT versus DIF

Differences:
1. For DIT, the input is bit reversed while the output is
natural order. For DIF, the input is in natural order
while the output is bit reversed.
2. The DIF butterfly is slightly different from the DIT.
In DIF, the complex multiplication takes place after
the add-subtract operation.
Similarities:
Both algorithms require N log2N operations to compute
the DFT. Both algorithms can be done in-place and both
need to perform bit reversal at some place during the
computation.
[email protected] 17 [email protected] 18

3
 1/24/2014

IDFT using FFT algorithm

The IDFT of an N - point sequence X(k),
where k  0, 1, 2 ...., N - 1 is defined as :
N 1  j 2  nk N 1
1 1
x(n) 
N

k 0
X (k ) e N 
N

k0
X ( k )W N- nk .... (15)
 j 2
where W N  e N

N 1
(15 )  Nx * ( n )  
k0
X * ( k )W Nnk .....( 16 )

The RHS of Eq. (16) is DFT of the sequence X * (k )

and can be computed using FFT algorithm
*
1  N 1 * 
Then x(n)   X ( k )W Nnk 
N  k  0
[email protected] 19