Ravi Shankara.M.N. Assoc. Professor ECE Dept SCE Bangalore ravi_shankar_mn@[Link].

in

Module 3(b) - Efficient Computation of the DFT- FFT Algorithms:

Direct Computation of DFT – Computational complexity of DSP
N−1

By definition X k = x n [WN ]kn = x 0 + x 1 [WN ]k + x 2 [WN ]2k + ⋯ . +x n − 1 [WN ](n−1)k

n=0

The input sequence can be real or imaginary and the twiddle factor WNkn is complex in nature. For any value
of k, there are (N – 1) complex additions and N complex multiplications.
Hence for N – point DFT, there are N(N) = N2 complex multiplications and N(N – 1) complex additions are
required.

For ex: If N = 1024 point DFT; Complex multiplications = 1024(1024) =1  106

Complex additions = 1024(1024 – 1)  1  106

Need for efficient Computation of DFT: If a processor executes one complex multiplication / complex
addition in 1 sec; then for N = 1024, the computation time is (1 + 1) = 2 sec. In reality, a 2 sec time for
processing is very large in-terms of processor time as processor has to do other jobs like fetching and storing
data, handling I/O and memory etc. Hence direct computation of DFT for large values of N is practically not
feasible.

Consider the case when both x(n) and [WN]kn both are complex, under this condition
N−1

Xk = [xR n + jxI n ] ([WR ]kn + j[W I ]kn )

N N
n=0

N−1

Xk = xR n [WR ]kn − xI n [W I ]kn + j xR n [W I ]kn + xI n [WR ]kn

N N N N
n=0

One complex multiplication  (a) 4 real multiplications (b) 2 real additions.

For N complex multiplications  (a) 4N real multiplications (b) 2N real additions
If k is varied from 0 to N – 1 and for N point DFT,

(NN) complex multiplications  (a) 4N2 real multiplications (b) 2N2 real additions are required.
Complex additions: Consider (a + jb) + (c + jd)
One complex addition = 2 real additions;
For k = 0 to (N – 1) , there are 2(N – 1) real additions.
For N point DFT, there are 2N(N – 1) = 2N2 – 2N.
2πkn 2πkn
The Twiddle factor [WN ]kn = cos + 𝑗 sin ; hence 2 trigonometric operations are required.
N N
For N point DFT with k ranging from 0 to (N – 1), there are 2N2 trigonometric operations are required.

Total real additions = 2N2 + 2N2 – 2N = N(4N – 2)

Total real multiplications = 4N2 Total trigonometric operations = 2N2

This is a supporting material for the SCE students. Any use for commercial purpose has to be permitted by the author ©Ravi Shankara.M.N. Page 1
Ravi Shankara.M.N. Assoc. Professor ECE Dept SCE Bangalore ravi_shankar_mn@[Link]

Operation Complex Complex Real Real Trigonometric

multiplications additions Multiplications additions operations
Number of N2 N2 – N 4N2 (4N2 – 2N) 2N2
Computations

FFT Algorithms and their Calculations:

In order to compute DFT efficiently, Fast Fourier Transforms (FFT) are used. FFT algorithms use properties of
phase factor (WN). FFT algorithms are based on two basic methods – Divide and Conquer approach and Linear
filtering. Figure shows the details.

Advantages of FFT Algorithms:

(1) Computational complexity is greatly reduced compared to direct computation.

(2) As the length of the DFT increases, the computation time decreases.
(3) Storage requirement of FFT algorithms is just 2N
(4) FFT algorithms can be used to calculate both DFT and IDFT very efficiently.
(5) Real time implementation of DFT is possible only because of FFT algorithms.

Frequency or Spectrum analysis using DFT Limitations of using DFT for Spectral
(Advantages of Using DFT for spectral analysis) analysis
Spectrum accuracy is limited as the input
(i) Since the spectrum of discrete signal is continuous, it cannot be directly
sequence is finite in length.
computed on a digital processor; hence by using DFT, spectrum can be analyzed.
(ii) Because of Windowing operations used in
(ii) Efficient FFT algorithms are available for fast computation of DFT. (iii) Other
analysis, there exists a power leakage
processing operations like power spectrum estimation, calculation of harmonics
(spreading of spectrum) (iii) With the
etc can also be done easily using DFT(iv) By increasing the number of sample
increasing in value of N, processing time
size, more accurate resolution can be obtained
increases.

Principle of FFT Algorithm

In Radix 2 FFT, the value of N should be such that N = 2m so that N point sequence is decimated into
2 – point sequence and two point DFT for each decimated sequence is computed. From the results of 2 – point
DFT’s, the 4 – point DFT’s can be computed. From the results of 4 – point DFT’s, the 8 – point DFT’s can be
computed and so on, until we get N – point DFT.

Two approaches used – (i) Decimation In Time (DIT) and (ii) Decimation In Frequency (DIF)

This is a supporting material for the SCE students. Any use for commercial purpose has to be permitted by the author ©Ravi Shankara.M.N. Page 2
Ravi Shankara.M.N. Assoc. Professor ECE Dept SCE Bangalore ravi_shankar_mn@[Link]

Radix – 2 Decimation In Time FFT ( DIT – FFT) Algorithm

In DIT FFT algorithm, the N – point DFT can be realized from two numbers (N/2) point DFT’s, the (N/2) point
DFT can be realized from two numbers of (N/4) point DFT’s and so on.

Let x(n) be N – sample sequence and is split into two (N/2) sequences f1(n) and f2(n). Let f1(n) consists of even
numbered samples and f2(n) contains odd numbered samples of x(n).
N N
f1 n = x 2n ; 0≤n ≤ −1 and f2 n = x 2n + 1 ; 0≤n ≤ −1
2 2
N−1

X k = x n WN kn = x n WN kn + x n WN kn
Splitting of sequence is called
0 even odd decimation and is done in time
N N domain, hence the name
−1 −1
2 2 decimation in time.
2km
X k = x 2m WN + x 2m + 1 WN k 2m+1

m=0 m =0

N N
−1 −1
2 2
2km
X k = f1 m WN + f2 m WN 2mk WN k
m=0 m=0
Using the property of twiddle factor [WN]2 = WN/2
N N
−1 −1
2 2
km N
X k = f1 m WN + WN k f2 m WN mk = F1 k + WN k F2 k where 0 ≤ k ≤ ( − 1)
2 2 2
m=0 m=0
F1(k) and F2(k) are the (N/2) point DFT’s of f1(m) and f2(m) respectively. Hence N point DFT can be obtained
by two (N/2) point DFT’s.

8 – point DFT Using Radix -2 DIT FFT

The input sequence is 8 – point sequence, hence N = 8 = 23= rm . Here r = 2 and

m = 3. It can be concluded that computation of 8 – point DFT using radix- 2
DIT FFT requires 3 stages of computation. The given 8 point sequence is
decimated to 2 point sequences and for each 2-point sequence, the 2 – point
DFT is computed. From the results of 2 – point DFT, the 4 – point DFT can be
computed and from the results of 4 – point DFT, the required 8 point DFT is
obtained.

Let x(n) = { x(0), x(1), x(2), x(3), x(4), x(5), x(6), x(7) }

Let f1(n) = { x(0), x(2), x(4), x(6) } Even samples (4 point sequence)

f2(n) = { x(1), x(3), x(5), x(7) } Odd samples (4 point sequence)

The sequences are further decimated into 2-point sequences as

𝑖 𝑣11 𝑛 = 𝑥 0 , 𝑥 4 Even samples of f1(n) 𝑖𝑖 𝑣12 𝑛 = 𝑥 2 , 𝑥 6 odd samples of f1(n)

𝑖𝑖𝑖 𝑣21 𝑛 = 𝑥 1 , 𝑥 5 Even samples of f2(n) 𝑖𝑣 𝑣22 𝑛 = 𝑥 3 , 𝑥 7 odd samples of f2(n)

This is a supporting material for the SCE students. Any use for commercial purpose has to be permitted by the author ©Ravi Shankara.M.N. Page 3
Ravi Shankara.M.N. Assoc. Professor ECE Dept SCE Bangalore ravi_shankar_mn@[Link]

This can be achieved by writing the sequence x(n) in bit reverse order & is decimated 4 numbers of 2 – point
sequences as shown in the table
Sequence – 1 : v11(n) = {x(0), x(4)} Sequence – 2 : v12(n)= {x(2), x(6)}
Sequence – 3 : v21(n)= {x(1), x(5)} Sequence – 4 : v22(n) = {x(3), x(7)}
Using these decimated sequences, 8 – point DFT is computed as shown in figure

The 8 point sequence is decimated into 4 point sequence and 2 point sequence as shown below.
f1(n) , f2(n) = 4 point sequences obtained from x(n)
v11(n), v12(n) = 2 point sequences obtained from f1(n)
v21(n), v22(n) = 2 point sequences obtained from f2(n)
The relations between the samples of various sequences are given below
v11(0) = f1(0) = x(0) v11(1) = f1(2) = x(4) v21(0) = f2(0) = x(1) v21(1) = f2(2) = x(5)
v12(0) = f1(2) = x(2) v12(1) = f1(3) = x(6) v22(0) = f2(1) = x(3) v22(1) = f2(3) = x(7)

First Stage Computation

V11 k = DFT v11 n = v11 n W2 kn = v11 0 W2 0 + v11 1 W2 k ; for k = 0, 1

n=0
For k = 0; V11 0 = v11 0 + v11 1 = x 0 + x 4
For k = 1; V11 1 = v11 0 + W2 1 v11 1 = x 0 − x 4 = x 0 − W2 0 x 4
-------------------------------------------------------------------------------------------------------------------
1

V12 k = DFT v12 n = v12 n W2 kn = v12 0 W2 0 + v12 1 W2 k ; for k = 0, 1

n=0
For k = 0; V12 0 = v12 0 + v12 1 = x 2 + x 6
For k = 1; V12 1 = v12 0 + W2 1 v12 1 = x 2 − x 4 = x 2 − W2 0 x 6
------------------------------------------------------------------------------------------------------------------
1

V21 k = DFT v21 n = v21 n W2 kn = v21 0 W2 0 + v21 1 W2 k ; for k = 0, 1

n=0
For k = 0; V21 0 = v21 0 + v21 1 = x 1 + x 5
For k = 1; V21 1 = v21 0 + W2 1 v21 1 = x 1 − x 5 = x 1 − W2 0 x 5
------------------------------------------------------------------------------------------------------------------
1

V22 k = DFT v22 n = v22 n W2 kn = v22 0 W2 0 + v22 1 W2 k ; for k = 0, 1

n=0
For k = 0; V22 0 = v22 0 + v22 1 = x 3 + x 7
For k = 1; V22 1 = v22 0 + W2 1 v22 1 = x 3 − x 7 = x 3 − W2 0 x 7

This is a supporting material for the SCE students. Any use for commercial purpose has to be permitted by the author ©Ravi Shankara.M.N. Page 4
Ravi Shankara.M.N. Assoc. Professor ECE Dept SCE Bangalore ravi_shankar_mn@[Link]

Second Stage Computation:

In the second stage of computation, the 4 point DFTs are computed using the results of first stage as inputs

F1 k = DFT f1 n = V11 k + W4 k V12 k ; for k = 0, 1,2,3 V11(k) and V12(k)

0 are periodic with
For k = 0; F1 0 = V11 0 + W4 V12 0 periodicity of 2
For k = 1; F1 1 = V11 1 + W4 1 V12 1 samples
For k = 2; F1 2 = V11 2 + W4 2 V12 2 = V11 2 − V12 2 = V11 0 − W4 0 V12 0
V11(k+2) = V11(k)
For k = 3; F1 3 = V11 3 + W4 3 V12 3 = V11 1 − W4 1 V12 1 V12(k+2) = V12(k)

F2 k = DFT f2 n = V21 k + W4 k V22 k ; for k = 0, 1,2,3 V21(k) and V22(k)

0 are periodic with
For k = 0; F2 0 = V21 0 + W4 V22 1 periodicity of 2
For k = 1; F2 1 = V21 1 + W4 1 V22 1 samples
For k = 2; F2 2 = V21 2 + W4 2 V22 2 = V21 0 − V22 0 = V21 0 − W4 0 V22 0
V21(k+2) = V21(k)
For k = 3; F2 3 = V21 3 + W4 3 V22 3 = V21 1 − W4 1 V22 1 V22(k+2) = V22(k)

Third Stage Computation

In the third stage of computation, the 8 point DFT is computed using the results of second stage as inputs.

F1(k) and F2(k) are periodic

X k = DFT x n = F1 k + W8 k F2 k ; for k = 0, 1, 2, 3, 4, 5, 6, 7 with periodicity of 4 samples
For k = 0; X 0 = F1 0 + W8 0 F2 0 F1(k+4) = F1(k)
For k = 1; X 1 = F1 1 + W8 1 F2 1 F2(k+4) = F2(k)
For k = 2; X 2 = F1 2 + W8 2 F2 2
For k = 3; X 3 = F1 3 + W8 3 F2 3 j2π4
For k = 4; X 4 = F1 4 + W8 4 F2 4 = F1 0 − W8 0 F2 0 W8 4 = e− 8 = e−j π = −1

For k = 5; X 5 = F1 5 + W8 5 F2 4 = F1 1 − W8 1 F2 1 W8 = W8 W8 0 = −W8 0
4 4

W8 5 = W8 4 W8 1 = −W8 1
For k = 6; X 6 = F1 6 + W8 6 F2 6 = F1 2 − W8 2 F2 2
W8 6 = W8 4 W8 2 = −W8 2
For k = 7; X 7 = F1 7 + W8 7 F2 7 = F2 3 − W8 3 F2 3
W8 7 = W8 4 W8 3 = −W8 3

Figure below shows the butterfly diagram for computation of 8 point DFT using DIT FFT
algorithm.

This is a supporting material for the SCE students. Any use for commercial purpose has to be permitted by the author ©Ravi Shankara.M.N. Page 5
Ravi Shankara.M.N. Assoc. Professor ECE Dept SCE Bangalore ravi_shankar_mn@[Link]

Signal Flow Graph or Butterfly Diagram

It is observed that in every stage of computation of radix – 2 DIT FFT : - (a) In each computation, two complex
numbers a and b are considered. (b) The complex number b is multiplied by a phase factor WN r (c) The
product bWN r is added to complex number a to form a new complex number A (d) The product bWN r is
subtracted from complex number a to form a new complex number B The above operation is shown in the
signal flow graph (Butterfly diagram)

Butterfly computation is the fundamental basic computation in

FFT algorithms and the operation is represented using a signal
flow graph. The two input available values are a and b, and from
these two input values, the output values A and B are computed as
shown in the diagram. This operation is called basic Butterfly Operation.

Computation of IDFT Using Radix – 2 FFT Algorithm

N−1
1
The discrete time signal interms of its DFT is given as x n = X k WN −kn − − − −(A)
N
k=0

In the above equation, the quantity inside the bracket is similar to that of DFT computation of a discrete time
sequence with the following differences –
(i) Summation index is k instead of n (ii) Input sequence is X(k) instead of x(n) (iii) Phase factor is conjugate of
the one used in DFT (iv) and the quantity inside the bracket is divided by N

This is a supporting material for the SCE students. Any use for commercial purpose has to be permitted by the author ©Ravi Shankara.M.N. Page 6
Ravi Shankara.M.N. Assoc. Professor ECE Dept SCE Bangalore ravi_shankar_mn@[Link]

Computational Complexity of FFT Algorithms

The butterfly operation used in FFT algorithms is shown below.

Each butterfly operation requires one complex multiplication and
two complex additions.

There are (N/2) butterflies in every stage of decimation and there

are v = Log2N stages of decimation. Hence total number of butterfly operations for a N point DFT is given as
N N N 8
𝑧= v= Log 2 N For N = 8; z = Log 2 N = Log 2 8 = 12
2 2 2 2

N
Complex Multiplications CMFFT = Log 2 N ------------- each butterfly needs one multiplication.
2

N
Complex Additions CAFFT = 2 Log 2 N = NLog 2 N ----------each butterfly needs two additions
2

N 8
Ex: For N = 8; CMFFT = Log 2 N = Log 2 8 = 12 CAFFT = NLog 2 N = 8Log 2 8 = 24
2 2

Comparison between Direct Computation of DFT and Radix – 2 FFT Algorithms

Number Direct Computation of DFT Radix -2 FFT algorithms Improvement in processing

of Complex Complex Complex Complex speed for multiplications
points multiplications Additions multiplications Additions N2
N
(N) N2 N2 – N N
Log 2 N NLog 2 N 2
Log 2 N
2
8 64 52 12 24 5.3 times
16 256 240 32 64 8 times
32 1024 992 80 160 12.8 times
64 4096 4032 192 384 21.33 times
128 16384 16256 448 896 36.87 times
256 65536 65280 1024 2048 64 times
512 262144 261632 2304 4608 113.7 times
1024 1048576 1047552 5120 10240 204.8 times

Inplace Computations:

Consider the basic butterfly operation shown in figure. From the

inputs a and b, the outputs A and B are computed. Once A and B are
computed, there is no need to store the inputs a and b, the same
memory locations can be used to store the outputs where inputs were
stored. Since the inputs and outputs may be complex or real, one butterfly operations requires 4 memory
locations two for a or A and two for b or B. After the butterfly operation, A is stored in place of a and B is in
place of b, this is called Inplace computation. This reduces the memory requirement by half.

Solution: X(k) = { 12, (1+j0.414), 0, (1+j2.414), 0, (1 – j2.414), 0, (1 – j0,414) }

Solution: x(n) = { 1, 1, 1, 1, 0, 0, 0, 0 } as N = 8

X(k) = { 4, (1 – j2.414), 0, (1 – j0,414), 0, (1+j0.414), 0, (1+j2.414) }

This is a supporting material for the SCE students. Any use for commercial purpose has to be permitted by the author ©Ravi Shankara.M.N. Page 7
Ravi Shankara.M.N. Assoc. Professor ECE Dept SCE Bangalore ravi_shankar_mn@[Link]

1. Compute the DFT of x(n) = cos(2n/4) ; 0  n  3 using DIT FFT algorithm

Solution: x(n) = cos(2n/4) ; 0  n  3

x(n) = { 1, 0, –1, 0 } N = 4 = 2m or m = 2

Hence 2 stage computation is required.

Arrange the i/p in bit reverse order. The
implementation of 4 point DFT using 2 point
DFT with each stage output is shown below.

X(k) = { 0, 2, 0, -2}

2. Compute the DFT of the sequence x(n) = { 0, 1, 2, 3 } using DIT FFT algorithm.
Solution - x(n) = { 0, 1, 2, 3 } N = 4 = 2m  m =2
Hence 2 stage computation is required.
Arrange the i/p in bit reverse order. The
implementation of 4 point DFT using 2 point
DFT with each stage output is shown below.

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

3. Compute the 8 point DFT of the sequence x(n) ={ 2, 1, 2, 1, 1, 2, 1, 2 } using radix-2 DIT-FFT algorithm

Solution: N = 8 = 2m  m = 3 Hence 3stages of computation is required. Arrange the i/p in bit reverse
The implementation of 8 point DFT using 2 point DFT with each stage output is shown below order.

X(k) = { 12, (1+j0.414), 0, (1+j2.414), 0, (1 – j2.414), 0, (1 – j0,414) }

This is a supporting material for the SCE students. Any use for commercial purpose has to be permitted by the author ©Ravi Shankara.M.N. Page 8
Ravi Shankara.M.N. Assoc. Professor ECE Dept SCE Bangalore ravi_shankar_mn@[Link]

[Link] the 8 point DFT of the sequence x(n) ={ 1, 1, 1, 1 } using radix-2 DIT-FFT algorithm

Solution - Modify x(n) = [ 1, 1, 1, 1, 0, 0, 0, 0] it become N = 8 length sequence

N = 8 = 2m  m = 3 Hence 3stages of computation is required. Arrange the i/p in bit reverse order.

X(k) = { 4, (1 – j2.414), 0, (1 – j0,414), 0, (1+j0.414), 0, (1+j2.414) }

5. Compute the DFT of x(n) = { 1, 2, 3, 4, 4, 3, 2, 1 } using DIT FFT algorithm

Ans: X(k) = { 20, (–5.828 – j2.414), 0, (–0.171 – j0.414), 0, (–0.171 + j0.414), 0, (–5.828 + j2.414) }

6. Determine the IDFT of X(k) = {4, 1 – j2.414, 0, 1 – j0.414, 0, 1 + j0.414, 0, 1+ j2.414} using inverse
radix – 2 DIT FFT algorithm.
N−1 7
1 1
x n = X k WN −kn = X k W8 −kn
N 8
k=0 k=0

This is a supporting material for the SCE students. Any use for commercial purpose has to be permitted by the author ©Ravi Shankara.M.N. Page 9
Ravi Shankara.M.N. Assoc. Professor ECE Dept SCE Bangalore ravi_shankar_mn@[Link]

7. Compute the DFT of the sequence x(n) = { 1, 1, 0, 0, -1, -1, 0, 0 } using DIT FFT algorithm.

Ans: X(k) = { 0, (3.414 –j1.414), 0, (0.586 – j1.414), 0, (0.586 +j1.414), 0, (3.414 +j1.414) }

8. The first five points of 8 point DFT of a real valued sequence are { 0, (2 + j2), –j4, (2 – j2), 0 }.
Determine the remaining samples and find the discrete time sequence using DIT FFT algorithm.
Solution: For a real valued sequence X(N – k) = X*(k) Given N = 8

Put k = 3; X(8 – 3) = X(5) = X*(3) = 2 + j2

Put k = 2; X(8 – 2) = X(6) = X*(2) = j4

Put k = 1; X(8 – 1) = X(7) = X*(1) = 2 – j2

Hence X(k) = { 0, (2 + j2), –j4, (2 – j2), 0, (2 + j2), j4, (2 –j2) }

Ans: The discrete time signal x(n) = { 1, 1, –1, –1, 1, 1, 1, –1}

9. Find the discrete time sequence x(n) whose DFT is X(k) = { 1, 0, 1, 0}

Solution: Divide the sequence into even and odd samples as V11(k) = { 1, 1 } and V12(k) = { 0, 0}

The discrete time sequence x(n) = { 0.5, 0. 0.5, 0 }

10. Find the 4 point real sequence x(n) if its DFT samples are X(0) = 6, X(1) = –2+j2; X(2) = –2.
Use DIT –FFT algorithm.

Solution: For a real valued sequence X(N – k) = X*(k) Given N = 4

This is a supporting material for the SCE students. Any use for commercial purpose has to be permitted by the author ©Ravi Shankara.M.N. Page 10
Ravi Shankara.M.N. Assoc. Professor ECE Dept SCE Bangalore ravi_shankar_mn@[Link]

Put k = 1; X(4 – 1) = X(3) = X*(1) = –2 – j2

The discrete time signal is x(n) = { 0, 1, 2, 3 }

11. Find the circular convolution between the sequences x1(n) = { 1, 1, 1, 1 } and h(n) = { 1, 0, 1, 0 }
using DIT – FFT algorithm.

Solution: Given N = 4; Let x3(n) = x1(n) 4 x2(n)  DFTN  X3(k) = X1(k) . X2(k)

X3(k) = X(k). H(k) = { 8, 0, 0, 0 }

x3(n) = { 2, 2, 2, 2 }

12. Find the circular convolution between the sequences x(n) = { 1, 2, 0, 1 } and h(n) = { 1, 3, 3, 1 } by
computing X(k) using DIT - FFT algorithm and H(k) using DIF – FFT algorithm.

This is a supporting material for the SCE students. Any use for commercial purpose has to be permitted by the author ©Ravi Shankara.M.N. Page 11
Ravi Shankara.M.N. Assoc. Professor ECE Dept SCE Bangalore ravi_shankar_mn@[Link]

Solution: Given N = 4; Let y(n) = x(n) 4 h(n)  DFTN  Y(k) = X(k).H(k)

Y(k) = X(k) . H(k) = { 32, –4, 0, –4 }

y(n) = IDFT [Y(k)] = { 6, 8, 10, 8 }

13. A designer is having a number of 8 point FFT chips. Show how explicitly he should interconnect three
chips in-order to compute 24 point DFT.

Solution : x(n) = { x(0), x(1), x(2), x(3), x(4), x(5), x(6), ……… x(22), x(23) }

Divide the sequences of length 8 such that

21 22 23
kn kn
X k = x n WN + x n WN + x n WN kn
n=0,3,6… n=1,4,7…. n=2,5,8…
7 7 7

X k = x 3n WN k3n + x 3n + 1 WN k(3n+1)
+ x 3n + 2 WN k(3n+2)
n=0 n=0. n=0
7 7 7
kn k kn 2k
X k = x 3n WN/3 + WN x 3n + 1 WN/3 + WN x 3n + 2 WN/3 kn
n=0 n=0. n=0
k
X k = X 1 (k) + WN X 2 (k) + WN 2k X 3 (k)
X1(k), X2(k) and X3(k) are 8 point DFT’s and their algebraic sum of these as per the above equation gives the
24 point DFT.

14. Calculate the % saving in calculations for 512 point radix 2 FFT algorithm when compared to direct
computation of DFT.

Number of Direct Computation of DFT Radix -2 FFT algorithms

points (N) Direct Computation FFT algorithm
Complex Complex Complex Complex
2
multiplications N Additions N2 – N multiplications Additions
N NLog 2 N
Log 2 N
2
512 262144 261632 2304 4608

This is a supporting material for the SCE students. Any use for commercial purpose has to be permitted by the author ©Ravi Shankara.M.N. Page 12
Ravi Shankara.M.N. Assoc. Professor ECE Dept SCE Bangalore ravi_shankar_mn@[Link]

CM FFT 2304
% saving in complex multiplications = 1 − CM × 100 = 1 − 262144 × 100 = 99.12%
direct
CA FFT 4608
% saving in complex Additions = 1 − CA × 100 = 1 − 261632 × 100 = 98.23%
direct

15. What is the speed improvement factor in calculating 64 point DFT of a sequence using direct computation and FFT
algorithms?

Number Direct Computation of DFT Radix -2 FFT algorithms Improvement in processing

of Complex Complex Complex Complex speed for multiplications
points multiplications Additions multiplications Additions N2
N
(N) N2 N2 – N N
Log 2 N NLog 2 N 2
Log 2 N
2
64 4096 4032 192 384 21.33 times

1. Develop DIT FFT algorithm and obtain the signal flow diagram for N = 8
2. What is inplace computation? What is the total number of complex additions and multiplications
required for N = 64 point , if DFT is computed directly and if FFT is used. Also find the number of
stages required and mention its memory requirement.
3. Find the number of complex multiplications and additions required to compute 128 point DFT using
Direct method and FFT- radix2 . What is the speed improvement factor?
4.
5. Find the DFT the following sequence using DIF FFT algorithm x1(n) ={1,1,1,0,0,1,1,1}. Using the
results, find the DFT of the signal x2(n) = {1,1,1,1,1,0,0,1}
x((n – m))N  DFT  X(k) e−j2πkm /N
6.
7.

This is a supporting material for the SCE students. Any use for commercial purpose has to be permitted by the author ©Ravi Shankara.M.N. Page 13