DFT and FFT Algorithms 5.

33

Let f1(n) contain even numbered samples of x(n) and f2(n) contain odd numbered

samples of x(n).
N
f1(n) = x(2n), n = 0,1 .......... –1
2
N
f2(n) = x(2n + 1), n = 0,1 .......... –1
2
The discrete Fourier transform of x(n)
N 1
X(k) = 
n0
bg
x n WNkn k = 0,1,........N – 1 .......(5.26)

N N
1 1
=
2
 b g
x 2m WN2mk 
2
 b
x 2m  1 WN g b
k 2m  1 g
m0 m0

Let f1(m) = x(2m) and f2(m) = x(2m + 1)

N N
1 1

=
2
 b ge j
f1 m WN2
km

2
 b ge j
f 2 m WN2
km
.WNk
m0 m 0

N N
1 1

=
2
 b g
f 1 m W Nkm  WNk
2
 b g
f 2 m W Nkm
m0 2 m 0 2

X(k) = F1(k) +WNk F2(k) .......(5.27)

where F1(k) is N point DFT of f1(m)

2
By periodicity property of DFT, we can write

FG N IJ
F1 k  = F1(k)
H 2K
F NI
F Gk  J
2
H 2K = F2(k)

Eq. (5.27) can be written as

FG N IJ FG
F1 k 
N IJ  W k N/ 2 FG
F2 k 
N IJ
X k
H 2 K =
H 2 K N H 2 K .......(5.28)
5.34 Digital Signal Processing

We know that WNk  N / 2 = WNk [Symmetry property]

X k
FG N IJ bg
F1 k  WNk F2 k bg
Now
H 2 K = .......(5.29)

We already have X(k) = bg

F1 k  WNk F2 k bg .......(5.27)

Let us consider the computation of 8 - point DIT - FFT, that is N = 8

x(0) X(0)
x(1) 8-point X(1)
x(2) .. DFT .. X(2)
.. ..
x(7) X(7)

Fig. 5.5 N - point DFT

From Eqs. (5.27) and (5.29), X(k) can be obtained from F1(k) and F2(k).

f1(m) = x(2n) = { x(0), x(2), x(4), x(6) }

f2(m) = x(2n + 1) = { x(1), x(3), x(5), x(7) }

Here f1(m) consists of even numbered samples and f2(m) contains odd numbered

samples.

It can be realized by combining two 4 - point DFTs.

f 1 (m)=x(2n)
F1 (0)
f 1 (0)=x(0) X(0)
N/2-point F1 (1)
f 1 (1)=x(2) X(1) X(0), X(1), X(2), X(3) ar e
DFT
F1 (2) obtai ned by substi tuti ng
f 1 (2)=x(4) (4-point X(2) k = 0, 1, 2, 3 i n Eq. (5.27)
DFT) F1 (3)
f 1 (3)=x(6) X(3)

f 2 (m)=x(2n+1)
F2 (0) W 0
f 2 (0)=x(1) 8 X(0+4)=X(4)
N/2-point -1
F2 (1) W 81
f 2 (1)=x(3) DFT X(1+4)=X(5) X(4), X(5), X(6), X(7) ar e
-1
F2 (2) W 82 obtai ned by substi tuti ng
f 2 (2)=x(5) (4-point X(2+4)=X(6) k = 0, 1, 2, 3 i n Eq. (5.29)
-1
DFT) F2 (3) W 83
f 2 (3)=x(7) X(3+4)=X(7)
-1

N
Fig. 5.6 Combining two - point DFTs
2
DFT and FFT Algorithms 5.35

Second stage of decimation of f1(n) and f2(n)

We know that f1(n) and f2(n) are N point sequences.

2
Let f1(n) be splitted into even numbered samples and odd numbered samples.
N
11(n) = f1(2n) n =0,1,.......... –1
4
N
12(n) = f1(2n+1) n = 0,1,.......... –1
4
Similarly f2(n) be splitted into
N
21(n) = f2(2n) n =0,1,.......... –1
4
N
22(n) = f2(2n+1) n = 0,1,.......... –1
4
From Eqs. (5.27) and (5.29), we can write
N
F1(k) = V11(k) +WNk / 2 V12(k), k = 0,1.... –1 .......(5.30)
4
FG
F1 k 
N IJ V11(k) –WNk / 2 V12(k), k = 0,1....
N
H 4 K =
4
–1 .......(5.31)

N
F2(k) = V21(k) +WNk / 2 V22(k), k = 0,1.... –1 .......(5.32)
4

FG
F2 k 
N IJ V21(k) –WNk / 2 V22(k), k = 0,1....
N
H 4 K =
4
–1 .......(5.33)

From Eqs. (5.30) and (5.31) F1(k) can be obtained from V11(k) and V12(k)

11(n) = f1(2n) = x(4n) = { x(0), x(4) }

12(n) = f1(2n + 1) = x(4n + 2) = { x(2), x(6) }

v11(n) = f1 (2n) = x(4n) V11(0)

N/4-point
v11(0) = f 1 (0) = x(0) F1 (0) These values are
DFT
V11(1) obt ained by put t ing
v11(1) = f 1 (2) = x(4) (2-point F1 (1) k = 0, 1 in Eq. (5.30)
DFT)

v12(n) = f 1 (2n+1) = x(4n+2) V12(0) 0

N/4-point W4
v12(0) = f 1 (1) = x(2) F1(0+2) = F1(2) These values are
DFT -1
obt ained by put t ing
V12(1) 1
W4
v12(1) = f 1 (3) = x(6) (2-point F1(1+2) = F1(3) k = 0, 1 in Eq. (5.31)
DFT) -1

Fig. 5.7 Combining two N/4 - point DFTs

5.36 Digital Signal Processing

From Eqs. (5.32) and (5.33) F2(k) can be obtained from V21(k) and V22(k)

21(n) = f2(2n) x(4n + 1) = { x(1), x(5) }

22(n) = f2(2n + 1) = x(4n + 3) = { x(3), x(7) }

v21(n) = f2 (2n) = x(4n+1)

V21(0)
v21(0) = f 2 (0) = x(1) N/4-point F2 (0)
DFT These values ar e
V21(1) obt ained by put t ing
v21(1) = f 2 (2) = x(5) (2-point F2 (1) k = 0, 1 in Eq. (5.32)
DFT)

v22(n) = f 2 (2n+1) = x(4n+3)

N/4-point V22(0) W4
0
v22(0) = f 2 (1) = x(3) F2(0+2) = F2(2) These values ar e
DFT -1
obt ained by put t ing
V22(1) 1
W4
v22(1) = f 2 (3) = x(7) (2-point F2(1+2) = F2(3) k = 0, 1 in Eq. (5.33)
DFT) -1

N
Fig. 5.8 Combining two - point DFTs
2
Computation of 2 - point DFTs
1
V11(k) =   11 bn gW2kn k = 0,1 .......(5.34)
n 0

The 2 - point DFT is drawn as

v11(0) = f 1 (0) = x(0) 2-point V11(0)

DFT
v11(1) = f 1 (2) = x(4) (N =2) V11(1)

Fig. 5.9 2 - point DFT

1
For k = 0, V11(0) = 
n0
bg
 11 n W20

= 11(0) + 11(1) [W20 = 1]

DFT and FFT Algorithms 5.37

1
For k = 1, V11(1) = 
n 0
bg
 11 n W2n

= 11(0)W20 + 11(1)W21

= 11(0) – 11(1) [W21 =e–j = –1]

Now V11(0) , V11(1) can be written as

V11(0) = 11(0) + W20 11(1)

V11(1) = 11(0) – W20 11(1)

v11(0) V11(0)
0
W2
v11(1) -1 V11(1)

Fig. 5.10 Computation of 2 point DFT

Signal flow graph for 8-point DIT - FFT

Generally N = 2M

log2N = M

For N - point DFT there are M stages of decimation.

For N = 8

M = log28

M = 3

For 8 - point DIT - FFT, there are three stages of decimation. The three stages

are combined in the signal flowgraph shown in Fig. 5.11.

 5.38

Fig 5.11 Signal flow graph for DIT - FFT algorithm

Digital Signal Processing
DFT and FFT Algorithms 5.39

In the signal flow graph computations are performed by butterfly computations.

The general form of butterfly computation is shown in the figure below.

r
a a +W N b
Complex
r addit ions
WN r
b a - WN b
-1
Compl ex
mul t i plicat ion

Fig. 5.12 Basic butterfly for DIT - FFT algorithm

In the signal flow graph, V11(0) and V11(1) are computed from x(0) and x(4) by
butterfly computation. F1(0) and F1(2) are computed from V11(0) and V12(0). Similarly
X(0) and X(4) are computed from F1(0) and F2(0).
N N
In FFT algorithms, butterflies are required for every stage. Here = 4 and
2 2
hence 4 butterflies are used . There are three stages of computation. Hence the total
number of butterflies used in this signal flow graph is 4 x 3 = 12.
N N
The number of butterfly can also be found out by log2
2 2
For N = 8
8
Total number of butterflies = log2 8
2
= 4x3
= 12
Each butterfly requires one complex multiplication and two complex additions.
N
Number of complex multiplications l og 2 N = 12
2
Number of complex additions N log2 N = 24
If we use direct computation of DFT, it requires more number of complex
multiplications and complex additions.
Number of complex multiplications = N2 = 82 = 64
Number of complex additions = N2 –N = 56
5.40 Digital Signal Processing

If N (Samples) increases then the processing speed increases in FFT algorithms.

It can be found out by comparing the requirement of complex additions and
multiplications for FFT algorithm and direct computation of DFT.
In the signal flow graph time domain sequence x(n) is in the form of suffled
array. It is found out by
[Binary [Bit reversed
form] order]
0  000  000  0
1  001  100  4
2  010  010  2
3  011  110  6
4  100  001  1
5  101  101  5
6  110  011  3
7  111  111  7

Example 5.15 R|1, n  0, 7

Find the DFT of a sequence x(n) = S

|2, n  1, 6
using DIT - FFT algorithm.
||3, n  2, 5
T4 , n  3, 4
Solution
The given sequence x(n) can be written as
x(n) = {1, 2, 3, 4, 4, 3, 2, 1 }
WN values associated with 8 - point DIT - FFT signal flow graph are

W80 = W40  W20  1

2 
j j 1 1
W81 = e 8  e 4  j
2 2

j
W82 = W41  e 2   j
2 3
j .3 j 1 1
W83 = e 8  e 4    j
2 2
DFT and FFT Algorithms 5.41

5 5 10 10
x(0) = 1 X(0)

-3 -3 -3-j -3-j
x(4) = 4 X(1)
1 -1
5 5 0 0
x(2) = 3 X(2)
1 -1
1 -j -3+j -3+j
x(6) = 2 X(3)
1 -1 -j -1
5 10
5
x(1) = 2 X(4)
1 -1
-1 -1 -1-3j
x(5) = 3 X(5)
1 -1 1/ 2 - j 1/ 2 -1

5 5 0
x(3) = 4 X(6)
1 -1 -j -1
3 -3j -1+3j
x(7) = 1 X(7)
1 -1 -j -1 -1/ 2 - j 1/ 2 -1

Fig. 5.13 DIT - FFT signal flow graph for Example 5.14

X(k) values can be calculated from the above signal flow graph as
X(0) = 10 + 10 = 20

X(1) = –3–j+
FG 1
j
1IJ b1  3 j g
H 2 2K

= – 5.83 – j 2.41
X(2) = 0

–3+ j+ 
FG 1
j
1 IJ b1  3 j g
X(3) =
H 2 2K

= – 0.17 – j0.41
X(4) = 10 – 10 = 0

FG 1
j
1 IJ b1  3 j g
X(5) = –3– j –
H 2 2K

= – 0.17 + j0.41
X(6) = 0
5.42 Digital Signal Processing

X(7) = –3+ j–  1  j 1
FG IJ b1  3 j g
2 2 H K
= – 5.83 + j 2.41
X(k) = {20, – 5.83 – j2.41, 0, – 0.17 – j0.41, 0, – 0.17
+ j0.41, 0, – 5.83 + j2.41}

Example 5.16
Compute 4 - point DFT of a sequence x(n) = { 0, 1, 2, 3 }

Solution
In the 4-point DFT, we require only two stages of decimation.
The WN values are
2
j
W40 = 1, W41  e 4   j

2 2
x(0) = 0 X(0) = 2+4 = 6

-2 -2
x(2) = 2 X(1) = -2+2j
1 -1
4 4
x(1) = 1 X(2) = 2-4 = -2
1 -1
-2 2j
x(3) = 3 X(3) = -2-2j
1 -1 -j -1

Fig. 5.14 DIT - FFT signal flow graph for Example 5.15

X(k) = { 6, – 2 + j2 , – 2, – 2 – j2 }

Computing IDFT using FFT algorithm

FFT algorithm can also be used to compute the IDFT. The IDFT is given by
N 1
x(n) =
1
N

k0
bg
X k WN nk , n = 0, 1,.... N – 1

.......(5.35)
DFT and FFT Algorithms 5.43

Taking complex conjugate of the above expression, we get

N 1
x*(n) =
1
N
 bg
X * k WNnk ......(5.36)
k0

The above equation can be written as

x*(n) =
1
N
{DFT X bkg } *

Taking complex conjugate on both sides of Eq. (5.36), we get the desired time
domain sequence

1 LM X bkgW
N 1 OP *

MN 
* nk
x(n) =
N k0
N
PQ
{DFT X bkg }
1 *
*
Hence x(n) = .......(5.37)
N
From the Eq. (5.37), we observe that the DFT values of X*(k) is complex conjugated
and divided by N gives the time domain sequence x(n).
To find the IDFT of the sequence X(k) by using DIT - FFT algorithm, the complex
conjugate values of X(k) is given as a input sequence in the bit reversed order. The
output is computed by using DIT - FFT signal flow graph. The complex conjugate
values of output are divided by N to get the sequence x(n).

Example 5.17
Compute the IDFT of X(k) = {6, –2 + j2, –2, –2, –j2} using DIT - FFT algorithm

Solution

We know that W40 = 1, W41 = – j

4 4 0
X *(0) = 6

8 8 4
X *(2) = -2
1 -1
-4 -4 8
X *(1) = -2 - j2
1 -1
-j4 -4 12
X *(3) = -2 + j2
1 -1 -j -1

Fig. 5.15 DIT - FFT signal flow graph for computing IDFT in Example 5.16
5.44 Digital Signal Processing

The output sequence is complex conjugated and divided by 4 gives

x(n) = {0, 1, 2, 3}
5.4.2 Decimation - in - frequency algorithm [DIF - FFT}
In the DIT - FFT algorithm, the time domain sequence x(n) is divided into smaller
subsequences. In this algorithm, the frequency samples X(k) are divided into smaller
and smaller subsequences.
Let us start with the DFT formula
N 1
X(k) = 
n0
bg
x n WNnk , k = 0, 1, .......... N – 1

N
Dividing the DFT into two summations consist of samples, we get
2
N
1
N 1
X(k) =
2

n 0
bg
x n WNkn  
N
bg
x n WNkn
n
2

N
Substituting r = n – in the second summation, we get
2
N N
2

1

bg
x n WNkn 
2

1
FG
x r
N IJ
k b r  N / 2g
X(k) =
n 0 r 0 H 2 K
WN

Replacing the variable r by n in the second summation, we get

N N
2

1

bg
x n WNkn 
2

1
FG
x n
N IJ
k b n  N / 2g
X(k) =
n0 n0 H 2 K
WN .......(5.35)

N N
2

1

bg
x n WNkn  WNkN / 2
2

1
FG
x n
N IJ
WNk n
=
n0 n 0 H 2 K
We know that WNkN/ 2 = e–jk= (–1)k
N
2
1


LMxbng  b1g xFG n  N IJ OP W
k kn
Hence, X(k) =
n0 N H 2 KQ N ......(5.36)
DFT and FFT Algorithms 5.45

The decimation - in - frequency is now done by taking the odd and even terms of
X(k). The even values of k are obtained by substituting k = 2r and
N
r = 0, 1, ......... – 1 in Eq. (5.36)
2
N
2

1
LMxbng  b1g xFG n  N IJ OP W
2r 2 rn
X( 2r) =
n0 N H 2 KQ N

X( 2r)
2

1
LMxbn g  xFG n  N IJ OP W 2r n
=
n0 N H 2 KQ N .......(5.37)

The odd values of k are obtained by substituting k = 2r + 1 and

N
r = 0, 1, .......... – 1 in Eq. (5.36)
2
N
2

1
LMxbn g  b1g 2 r 1 FG
x n
N IJ OP W b
n 2 r 1 g
X( 2r+ 1) =
n0 N H 2 KQ N

X( 2r+ 1)
2

1
LMxbng  xFG n  N IJ OP W n
WN2r n
=
n 0 N H 2 KQ N .......(5.38)

From Eqs. (5.37) and (5.38) , we define

f(n) = b g FGH
x n x n
N
2
IJ
K .......(5.39)

LM xbng  xFG n  N IJ OP W n
g(n) =
N H 2 KQ N .......(5.40)

In the above Eqs. (5.39) and (5.40), the basic computational block is a butterfly
as shown in Fig. 5.16

a a+b

n
b (a - b) W N
-1 n
WN

Fig. 5.16 Basic butterfly for DIF - FFT algorithm

5.46 Digital Signal Processing

From Eqs. (5.39) and (5.40) , the values of f(n) and g(n) are calculated. We
assume N = 8.
f(n) values are obtained by substituting n = 0, 1, 2, 3, in Eq. (5.39)
f(0) = x(0) + x(4)
f(1) = x(1) + x(5)
f(2) = x(2) + x(6)
f(3) = x(3) + x(7)
g(n) values are obtained by substituting n = 0, 1, 2, 3, in Eq. (5.40)

g(0) = [ x(0) – x(4) ] W80

g(1) = [ x(1) – x(5) ] W81

2
g(2) = [ x(2) – x(6) ] W8
g(3) = [ x(3) – x(7) ] W83
N
The even and odd indexed X(k)s are determined from the - point DFTs of
2
f(n) and g(n) as shown in Fig. 5.17

f (0)
x(0) X(0)
f (1) 4- point
x(1) X(2)
DFT
f (2)
x(2) (N/2 X(4)
point )
x(3) f (3)
X(6)

g (0)
x(4) X(1)
-1 0
4- point
W8 g (1)
x(5) DFT X(3)
-1 1
W8
g (2) (N/2
x(6) X(5)
-1 2
W8 point )
g (3) X(7)
x(7)
-1 3
W8

Fig. 5.17 First stage of DIF - FFT algorithm

DFT and FFT Algorithms 5.47

N N
In a similar manner, each - point DFTs can be decomposed into two - point
2 4
DFTs by again decimating the frequency outputs. The complete 8 - point decimation-
in- frequency FFT signal flow graph is shown in Fig. 5.18.

f(0) f(0)+f(2)
x(0) X(0)

f(1) f(1)+f(3)
x(1) 0
X(4)
-1 W8
f(2) f(0)-f(2)
x(2) X(2)
-1 0
W8
f(3) [f(1)-f(3)] W 82
x(3) X(6)
-1 2 -1 0
W8 W8
g(0) g(0)+g(2)
x(4) 0
X(1)
-1 W8
g(1) g(1)+g(3)
x(5) X(5)
-1 1
W8 -1 0
W8
g(2) g(0)-g(2)
x(6) X(3)
-1 2 -1 0
W8 W8
2
g(3) [g(1)-g(3)] W 8
x(7) X(7)
3 -1
-1 W8 -1 2
W8
0
W8

Fig. 5.18 Signal flow graph for DIF - FFT algorithm

In the above signal flow graph X(0), X(4) are obtained by the butterfly
computation of f(0) + f(2) and f(1) + f(3). Similarly we can compute the values of
X(2), X(6), X(1), X(5), X(3) and X(7).
In this DIF - FFT signal flow graph, x(n) is in the regular order and the X(k)
values are in the form of shuffled bit reversed order.

Example 5.18
Compute a 8-point DFT of x(n) = { 1, 2, 3, 4, 4, 3, 2, 1 } using DIF - FFT
radix-2 algorithm.
5.48 Digital Signal Processing

Solution
The ‘WN’ values are

W80 = 1, W81 = 1  j 1
2 2
1 1
W82 = –j, W83 = –  j
2 2
5 5 10
x(0) = 1 X(0)

5 5 10
x(1) = 2 X(4)
-1 1
5 5 0
x(2) = 3 X(2)
-1 1

5 5 0
x(3) = 4 X(6)
-1 -j -1 1

-3 -3 -3-j
x(4) = 4 X(1)
-1 1
-(1/ 2 + 3/ 2)
-1 -1/ 2 + j 1/ 2 + j(1/ 2 - 3/ 2)
x(5) = 3 X(5)
-1 1/ 2 - j 1/ 2 -1 1

1 -j -3+j
x(6) = 2 X(3)
-1 -j -1 1
-(1/ 2 - 3/ 2)
3 -3/ 2 - j 3/ 2 + j(1/ 2 + 3/ 2)
x(7) = 1 X(7)
-1 -1/ 2 - j 1/ 2 -1 -j -1 1

Fig 5.19 DIF - FFT signal flow graph for Example 5.17

X(0) = 10 + 10 = 20 X(4) = 10 – 10 = 0
X(2) = 0+0=0 X(6) = 0 – 0 = 0

FG 1  3 IJ  j FG 1  3 IJ = – 5.83 – j2.41
X(1) = –3 –j –
H 2 2K H 2 2K
–3 – j + G
F1 3 I
J  jG
F 1  3 IJ = – 0.17 – j0.41
X(5) =
H 2 2 K H 2 2K
–3 + j + G
F1 3 I
J  jG
F 1  3 IJ = – 0.17 – j0.41
X(3) =
H 2 2K H 2 2K
X(7) = –3 + j – G
F1 3 I
J  jG
F 1  3 IJ = – 5.83 + j2.41
H 2 2K H 2 2K
X(k) = {20, –5.83 – j2.41, 0, –0.17 – j0.41, 0, –0.17 + j0.41, 0, –5.83 + j2.41 }
DFT and FFT Algorithms 5.49

Example 5.19

Determine the 8-point DFT of the sequence x(n) =

RS1,  3  n  3
T0 , el sewher e
using i. DIT - FFT algorithm ii. DIF - FFT algorithm [AU, Apr’ 2004]

Solution

To find DFT of any sequence, x(n) must be in the range of 0 to N–1. So we have

to find the values of x(n) from 0 to 7. Since the discrete-time signal x(n) is periodic with

N = 8, it is plotted as shown in Fig. 5.20

x(n)

-3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 n

Per i odi c wi th N = 8

Fig. 5.20 Graph of a sequence in Example 5.18

Hence x(n) = { 1,1, 1, 1, 0, 1, 1, 1 }

A
From the above sequence, DFT can be determined by either DIT - FFT or

DIF - FFT method

i. DIT - FFT Method

x(n) = { 1, 1, 1, 1, 0, 1, 1, 1 }

W80 = 1
1 1
W81 =  j
2 2

W82 = –j
1 1
W83 = –  j
2 2
5.50 Digital Signal Processing

St age 1 St age 2 St age 3

1 3 7
x(0) = 1

1 1 1
x(4) = 0
0 -1
W8
2 -1 -1
x(2) = 1
0
W8 -1

0 1 1
x(6) = 1 1
0 -1 W8 -1
W8
2 4 -1
x(1) = 1 -1
0
W8
0 0 1
x(5) = 1
0 -1 1 -1
W8 W8
2 0 -1
x(3) = 1
0 -1 2 -1
W8 W8
0 0 1
x(7) = 1 1
0 -1 3 -1
W8 -1 W8 W8

Fig. 5.21 DIT - FFT signal flowgraph of Example 5.18

stage 3
input stage1 stage2
(output)

1 1+0=1 1 + 2(1) = 3 3+4=7 X(0)

0 1–0=1 1+0=1 1+0=1 X(1)

1 1+1=2 1 –2 = –1 –1 + 0 = –1 X(2)

1 1–1=0 1–0=1 1+0=1 X(3)

1 1+1=2 2+2=4 3 –4 = –1 X(4)

1 1–1=0 0+0=0 1–0=1 X(5)

1 1+1=2 2–2=0 –1 – 0 = –1 X(6)

1 1–1=0 0–0=0 1 – 0 =1 X(7)

Output X(k) = { 7, 1, –1, 1, –1, 1, –1, 1 }

DFT and FFT Algorithms 5.51

DIF - FFT Method

x(n) = { 1, 1, 1, 1, 0, 1, 1, 1 }

W80 = 1

W81 1 1
=  j
2 2

W82 = –j,

W83 1 1
= –  j
2 2

St age 1 St age 2 St age 3

1 3
x(k)=1 7

2 4 -1
1
-1

2 -1
1 -1
-1 0
W8
2 0
1 -1
-1 2
W8 -1

1 1
0 1
-1 0
W8
0 0
1 1
-1 1 -1
W8
0 1
1 1
-1 2 -1 0
W8 W8
0 0
1 1
-1 3
W8 -1 2
W8 -1

Fig. 5.22 DIF - FFT signal flowgraph of Example 5.18

5.52 Digital Signal Processing

input stage1 stage2 stage 3

1 1+0=1 1+2=3 3+4=7 X(0)

1 1+1=2 2+2=4 3 – 4 = –1 X(4)

1 1+1=2 1 –2 = –1 –1 + 0 = –1 X(2)

1 1+1=2 2–2=0 –1 – 0 = –1 X(6)

0 1–0=1 1+0=1 1+0=1 X(1)

1 1–1=0 0+0=0 1–0=1 X(5)

1 1–1=0 1–0=1 1+ 0 = 1 X(3)

1 1–1=0 0–0=0 1 – 0 =1 X(7)

X(n) = { 7, 1, –1, 1, –1, 1, –1, 1 }

DFT and FFT Algorithms 5.53

Short Questions and Answers

1. Define DTFT pair. [AU, Apr’ 2004]

The discrete-time Fourier transform of a sequence x(n) is


X() = 
n  
bg
x n e j n

The inverse discrete-time Fourier transform

z

X(n) = 1
2
bg
X  e j n d 


2. State and prove the frequency shifting property of DTFT

x(n) e j  0 n 
DTFT
 X(–0)

DTFT [x(n) e j  0 n ] = 
n  
bg
x n e j n e j  0 n


=  xn ebg b
 j   0 n g
n  
= X(–0)
3. Write the analysis and synthesis equations of DFT. [AU,Nov’ 2003]

The analysis equation is the direct transform given by

N 1 2 kn
j
X(k) =  bg
xn e N
, k = 0, 1, 2, ........... N–1
n0

The synthesis equation (or) inverse transform

N 1 2 kn
x(n) =
1
N
 bg
X k e
j
N , n = 0, 1, 2, ........... N–1
k0

4. Write the relationship between system function and frequency response

of LSI system. [AU, Nov’ 2003]

The system function H(z) is the z - transform of impulse response h(n) and

the frequency response H() is the DTFT of impulse response.

5.54 Digital Signal Processing


H(z) = 
n  
bg
h n z n


H() = 
n  
bg
h n e j n

H(z) and H() are related by

H() = H z bg z  ej 

5. State DFT pair interms of twiddle factor WN

2
j
Since WN = e N

The DFT of the sequence x(n)

N 1
X(k) = 
n0
bg
x n WNkn , k = 0, 1, 2, ........... N–1

N 1
x(n) =  bg
X k WN kn , n = 0, 1, 2, .......... N – 1
k0

6. Give the relationship between DTFT, DFT and z - transform.

The DTFT X() and z - transform X(z) are related by

X() = H z bg z  ej 

The DTFT X(k) and DTFT X() are related by

X(k) = H  bg e
j
2 k
N

7. How will you perform linear convolution through circular convolution?

[AU,Nov’ 2004]

To perform linear convolution through circular convolution, consider the

sequence x1(n) having length M1 and x2(n) having length M2. Before finding

circular convolution, both the sequences are made to the length M1 + M2 – 1.

Now the circular convolution of new sequences will give the linear convolution of

those sequences.
DFT and FFT Algorithms 5.55

8. Distinguish between DTFT and DFT. [AU, Apr’ 2004]

The spectrum of DTFT X() is continuous and it is not convenient to calculate

X() in digital signal processor. The spectrum of DFT X(k) is discrete and it is

more convenient for computations.

9. State and prove the periodicity property of DFT.

X(k + N) = X(k)

Proof
N 1
X(k + N) = 
n0
bg
x n WNkn

=
N 1
 bg
x n WN
b k  N gn
n0

N 1
= 
n0
bg
x n WNkn WNNn

Nn
Since WN = 1
N 1
X(k + N) = 
n0
bg
x n WNkn = X(k)

10. Determine the DTFT of the sequence x(n) = {1, –1, 1, –1}

[AU, Nov’ 2004]

Solution

X() =  bg
x n e j n
n  

3
= 
n0
bg
x n e j n

X() = e–j– e–j2+ e–j3– e–j4

5.56 Digital Signal Processing

11. Define correlation. [AU, Nov’ 2004]

Correlation gives a measure of similarity between two signals (or) sequences. For

two sequences x1(n) and x2(n), the cross correlation is defined as


bg
 x1 x 2 l =  bg b g
x1 n x 2 n  l
n  

12. What is the need for FFT. [AU, Nov’ 2003]

Fast Fourier transform (FFT) algorithms are required for the efficient

computation of DFT. The direct computation of DFT requires N2 complex

multiplications and N2 – N complex additions whereas FFT requires only

N N
log2 N complex multiplications and log2 N complex additions. If N increases
2 2
then the processing speed increases in FFT algorithms.

13. How many multiplications and additions are required to compute

N - point DFT using radix - 2 FFT?

N
Number of multiplications = log2 N
2
Number of additions = N log2 N

14. Give the computation efficiency of 1024 point FFT over 1024 point DFT.

The direct computation of 1024 point DFT requires

N2 = (1024)2 = 1048576 multiplications.

N 1024
The 1024 point requires log2 N = log 2 1024 = 5120 multiplications.
2 2

15. Draw the radix - 2 Butterfly diagram for DIT and DIF algorithms.

For DIT algorithms

For DIF algorithms

DFT and FFT Algorithms 5.57

Review Questions

1. State DTFT pair.

2. Give the relation between DTFT, DFT and Z - transform

3. Define twiddle factor (or) phase factor.

4. Write the bit reversal order for 8 point DIF - FFT.

5. Compare the computations in FFT and direct computation.

6. Derive DFT pair interms of WN

7. State and prove time shifting property of DFT.

8. Distinguish between DIT and DIF algorithms.

9. Draw the basic butterfly diagram for DIT and DIF algorithms.

10. How will you perform linear convolution through circular convolution?

11. State and prove convolution theorem of DFT.

12. State and prove modulation theorem of DTFT.

13. Draw the power density spectrum.

14. Write the analysis and synthesis equations of DFT.

15. What is the need for FFT?

16. Derive the relationship between DFT and Z - transform.

17. Derive the Parseval’s relation for non periodic finite energy signals.

18. Find the sequence x(n) whose Fourier transform is given by

X(w) =
|RS1,  w
c  w  wc
|T0 , w c  w 

19. Compute 8 - point DFT of the signal x(n) = { 0.5, 0.5, 0.5, 0.5 }

20. Determine the circular convolution of two sequences x1(n) = { 1, 2, 1, 4, 3}

x2(n) = { 3, 2, 1 }

21. Find the sequence x(n) for X(k) = { 10, –2 + j2, – 2, – 2 – 2j } by DIT - FFT

algorithm.
5.58 Digital Signal Processing

22. Compute 8 - point DFT of the sequence by DIF - FFT algorithm

x(n) = {2, 1, 2, 1, 2, 1, 2, 1 }

23. Explain circular time shift and frequency shift properties of DFT.

24. Explain the interrelationship between DTFT, DFT and Z - transform.

25. With an example explain the algorithm involved to get bit reversed binary form

from the normal binary form.

26. Derive DIT - FFT algorithm and draw the signal flow graph. Also find the DFT

for x(n) = { 1, –1, 1, –1, 1, –1, 1, –1 }

27. Find the response of the system for the input signal x(n) = { 1, 2, 1, 4, 3, 2} and

impulse response h(n) = { 1, 4, 3, 2 }