Computation of the Discrete Fourier Transform

08/10/2024 1
1
Introduction
Implement a convolution of two sequences
by the following procedure:
1. Compute the N-point DFT X 1 k  and X 2 k 
of the two sequence x1 n and x2 n
2. Compute X 3 k   X 1 k X 2 k  for 0  k  N  1
3. Compute x3 n  x1 n N x2 n as the inverse
DFT of X 3 k 
Why not convolve the two sequences directly?
There are efficient algorithms called Fast
Fourier Transform (FFT) that can be orders of
magnitude more efficient than others. 2
 9.1 Efficient Computation of Discrete Fourier
Transform
• The DFT pair was given as
N 1
 j  2 / N kn 1 N 1
j  2 / N kn
X k    x[n]e x[n]   X k  e
n 0
N k 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
3
3
 9.1 Efficient Computation of Discrete Fourier
Transform
N 1
 j  2 / N kn
X k    x[n]e
n 0

Complexity in terms of real operations

4N2 real multiplications
2N(N-1) real additions (approximate 2N2)

4
4
 9.2 The Goertzel Algorithm
• Makes use of the periodicity e j  2 / N  Nk  e j 2 k  1
• Multiply DFT equation with this factor
j  2 / N kN
N 1
 j  2 / N rk N 1
j  2 / N k  N r 
X k   e  x[r ]e   x[r ]e
r 0 r 0

j  2 / N k  n  r 
Define yk  n    x[r ]e u n  r 
r 

using x[n]=0 for n<0 and n>N-1

X  k   yk  n  n  N
X[k] can be viewed as the output of a filter to the input
x[n]
j  2 / N kn
Impulse response of filter: h[n]  e u n
X[k] is the output of the filter at time n=N
6
6
9.2 The Goertzel Algorithm
• Goertzel j  2 / N kn
Filter: h[n]  e u[n]  WN knu[n]

1
Hk  z  
1  WN k z 1

yk [n]  yk [n  1]WN k  x[n], n  0,1,..., N , yk [1]  0

X k   yk n  n  N , k  0,1,..., N
N 1
X k    x[n]WNkn
n 0
Computational complexity
4N real multiplications; 4N real additions
Slightly less efficient than the direct method
kn
But it avoids computation and storage of W N 7
7
Second Order Goertzel Filter
• Goertzel Filter
1
Hk  z   2
j k
1 e N z 1

Multiply both numerator and denominator

 j 2 k j
2
k
1 e N
z 1 1 e
N
z 1
Hk  z   
 j
2
k   2
 j k 1  2 k 1 2
 1  e N
z  1
 1  e N
z  1  2 cos z z
N
  
2 k
y[n]   y[n  2]  2 cos y[ n  1]  x[n], n  0,1,..., N
N
yk [ N ]  y[ N ]  WNk y[ N  1]  X k  , k  0,1, ..., N 8
8
 9.3 decimation-in-time FFT Algorithms

• Makes use of both periodicity and symmetry

• Consider special case of N an integer power of 2
• Separate x[n] into two sequence of length N/2
• Even indexed samples in the first sequence
• Odd indexed samples in the other sequence

N 1
 j  2 / N kn
X k    x[n]e
n 0

 j  2 / N kn  j 2 / N kn

  x[n]e
n even
  x[n]e
n odd
11
11
8-point DFT using decimation-in-time

14
Figure 9.3
 computational complexity
• Two N/2-point DFTs
• 2(N/2)2 complex multiplications
• 2(N/2)2 complex additions
• Combining the DFT outputs
• N complex multiplications
• N complex additions
• Total complexity
• N2/2+N complex multiplications
• N2/2+N complex additions
• More efficient than direct DFT
15
15
 9.3 decimation-in-time FFT Algorithms

• Repeat same process ,

Divide N/2-point DFTs into
• Two N/4-point DFTs
• Combine outputs

N=8

16
16
 9.3 decimation-in-time FFT Algorithms
• After two steps of decimation in time

Repeat until we’re left with two-point DFT’s

17
17
 9.3 decimation-in-time FFT Algorithms
• flow graph for 8-point decimation in time

Complexity:
Nlog2N complex multiplications and additions 18
18
 Butterfly Computation

• Flow graph constitutes of butterflies

We can implement each butterfly with one

multiplication
Final complexity for decimation-in-time FFT
(N/2)log2N complex multiplications and
additions
19
19
 9.3 decimation-in-time FFT Algorithms
• Final flow graph for 8-point decimation in time

Complexity:
(Nlog2N)/2 complex multiplications and Nlog2N addition
9.4 Decimation-In-Frequency FFT Algorithm
N 1
• The DFT equation X k    x[n]WNnk
n 0
Split the DFT equation into even and odd frequency
indexes
N 1 N / 2 1 N 1
X 2r    x[n]WNn 2 r   x[n]WNn 2 r   x[n]W Nn 2 r
n 0 n 0 n N / 2
N /2 1 N /2 1
Substitut
e
 
n 0
x[n]W n2r
N   x[n  N / 2]W
n 0
N
 n  N /2 2 r

variables N /2 1
   x[n]  x[n  N / 2]W
n 0
nr
N /2

N /2 1
 n 0
g (n)WNrn/2
31
31
9.4 Decimation-In-Frequency FFT Algorithm
N 1
• The DFT equation X k    x[n]WNnk
n 0
N 1 N /2 1 N 1
X 2r  1   x[n]W n (2 r 1)
N   x[n]W n (2 r 1)
N   n (2 r 1)
x[n]W
N
n 0 n 0 n  N /2
N /2 1 N /2 1
 
n 0
x[n]W n (2 r 1)
N  
n 0
x[n  N / 2]WN  n  N /2 (2 r 1)

N /2 1
   x[n]  x[n  N / 2]W
n 0
n (2 r 1)
N

N / 2 1 N /2 1
   x[n]  x[n  N / 2]W W n
N
rn
N /2
 n 0
h(n)WNnWNrn/2
n 0
N
n  2 r 1 (2 r 1)
W N W W W W
2 rn
N
n
N
rn
N /2
n
N W N
2
 WNNrWNN /2  1 32
32
 decimation-in-frequency decomposition of an N-point
DFT to N/2-point DFT

N /2 1 N /2 1
X  2r     x[ n ]  x[ n  N / 2]  N /2
W nr
n 0
g (n)WNrn/2
n  0N /2 1 N /2 1
X 2r  1  
n 0
 x[ n ]  x[ n  N / 2]  NW
W n rn
N /2
 
n 0
h(n)WNnWNrn/2
33
33
 decimation-in-frequency decomposition of an 8-point
DFT to four 2-point DFT

N / 4 1 N /4 1
X 2* 2 s    [ g (n)  g (n  N / 4)]WNsn/4  
n 0
p(n)WNsn/4
n 0
N / 4 1 N /4 1
X 2*(2 s  1)    [ g (n)  g (n  N / 4)]W W
2n
N
sn
N /4   q(n)WN2 nWNsn/4
34

n 0 n 0 34
 2-point DFT

X v ( p )  X v 1 ( p )  X v 1 (q )

X v (q )   X v 1 ( p )  X v1 (q )  W80 when N  8

35
35
Final flow graph for 8-point DFT decimation in
frequency

40
40