Performance Analysis of Approximate

8-point FFT of radix 2 using Multiplier

A report submitted in partial fulfilment of the requirements

for the degree of B.Tech. Electronics and Communication Engineering
with specialization in Design and Manufacturing

by

Student Y.Avinash
(Roll No: EDM16B038)
Guide: Noor Mahammad SK

DEPARTMENT OF ELECTRONICS AND COMMUNICATION ENGINEERING

INDIAN INSTITUTE OF INFORMATION TECHNOLOGY,
DESIGN AND MANUFACTURING, KANCHEEPURAM

June 2020
 Certificate

This is to certify that the B.Tech Project titled ”Performance analysis of

Approximate 8-point FFT of radix 2 using Multipler” submitted by Y.Avinash
(EDM16B038) to the Indian Institute of Information Technology Design and
Manufacturing, Kancheepuram for the award of ”Bachelor of Technology in
Electronics and Communication Engineering”, is a bonafide record of the project
work done by him under my supervision. The contents of the project, in full or in parts,
have not been submitted to any other Institute or University for the award of any degree
or diploma.

Project Guide’s Name: Project Guide’s Signature

i
 Abstract
Fast Fourier Transform and inverse fast fourier transform are used in DSP.Butterfly
diagram consists of multipliers and adders they are important for calculating the FFT.In
this report my main aim to control the hardware complexity and increase the
performance
 Acknowledgements
I would like to extend my sincerest gratitude to various people, who directly or indirectly
contributed in the development of this work and who influenced my thinking, behavior,
and acts during the course of study.

I consider myself as a lucky individual as I was provided with an opportunity to be a part

of the project under the supervision of Noor Mahammad sir.

I would like to thank M.tech brother, who helped me when I was stuck at a point finding
for references or when I am not sure of the implementation to be done further. They
clarifies the basic doubts that I have and encourages me all the time.

I perceive this opportunity as a big milestone in my career development. I will strive to

use gained skills and knowledge in the best possible way, and I will continue to work on
their improvement, in order to attain desired career objectives.

iii
Contents

Certificate i

Abstract ii

Acknowledgements iii

Contents iv

List of Figures vi

List of Tables vii

Abbreviations viii

Symbols ix

1 Performance Analysis of Approximate 8-point FFT of radix 2 using

Booth Multiplier 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Discrete Fourier Transform (DFT) . . . . . . . . . . . . . . . . . . . 1
1.1.2 Fast Fourier Transform(FFT) . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 few applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.4 Work done . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.5 Image compression through FFT using MATLAB . . . . . . . . . . . 2
1.1.6 Design Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.7 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Performance Analysis of Approximate 8-point FFT of Radix-2 using

Booth Multiplier 6
2.1 Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Radix-2 Booth multiplier:- . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.2 Radix-4 Booth multiplier:- . . . . . . . . . . . . . . . . . . . . . . . . 7

iv
Contents v

2.1.3 Advantage:- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.4 Wallance tree multiplier . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.5 8-point DIT FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Work done and Results 11

3.1 Work done . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

Bibliography 14
List of Figures

1.1 structural flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 After computing FFT in MATLAB . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Output results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1 Radix 2 Booth multiplier example . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Radix 4 Booth multiplier example . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Output for a Wallace tree multiplier . . . . . . . . . . . . . . . . . . . . . . 9
2.4 8-point DIT FFT Butterfly structure . . . . . . . . . . . . . . . . . . . . . . 10

3.1 RTL schematic view in Xlink . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.2 eight point schematic view in cadence . . . . . . . . . . . . . . . . . . . . . 13

vi
List of Tables

vii
Abbreviations

DFT Discrite Fourier Transform

FFT Fast Fourier Transform
DIT Discrimination In Time
IFFT Inverse Fast Fourier Transform

viii
Symbols

ix
For/Dedicated to/To my. . .

x
Chapter 1

Performance Analysis of
Approximate 8-point FFT of radix
2 using Booth Multiplier

1.1 Introduction

A Fast Fourier transform (FFT) is an algorithm that can be used to computes the
discrete Fourier transform (DFT) of a sequence.To know what is meant by FFT in
detailed manner first we should know what is DFT and and what are the different
between these two terminologies and how FFT is used in computing DFT.

So fist talk about what is DFT for next few sections.

1.1.1 Discrete Fourier Transform (DFT)

When the given signal is form of discrete and periodic, we don’t need the continuous
Fourier transform.

The discrete Fourier transform of a, also known as the spectrum of a, is:which can
commonly written as

1
chapter I 2

consider this as equation(1)

as we increase the value further the level of complexity increase much more higher. Now
let’s see how FFT comes to play.

1.1.2 Fast Fourier Transform(FFT)

1.1.3 few applications

1) audio processing
2) Image compression
3) Voice recognition etc

1.1.4 Work done

1.1.5 Image compression through FFT using MATLAB

This report is divided into two sections. In the first session I observed one of the application
FFT by considering a reference image.

In this paper an application is considered how FFT actually works. Let’s consider a sample
image of M x N matrix size where M = 413 and observe how image compression happens
through MATLAB using FFT.
chapter I 3

1.1.6 Design Flow

Figure 1.1: structural flow

Step 1:- Involves considering an reference image initially in Pixels.At first convert the
image from RGB to gray.The converted image looks in this manner.

Step 2:- Computing FFT for the image using MATLAB inbuilt commands. The image is
now converted to frequency domain and looks like in the below diagram.
chapter I 4

Figure 1.2: After computing FFT in MATLAB

In the above diagram the center part is bright. This is because the all the higher coefficients
are in that located. Remaining portion is light colour due to of lower coefficients.

Step 3:- Involves removing the lower coefficient and storing the higher coefficients that are
required for us. This can be done by setting an threshold in such a way that all the values
that are higher than the threshold are to be stored and the remaining smaller coefficients
are removed.

Step 4:- After removing all the lower coefficients the above the compressed image was still
in frequency domain and get stored in our disk.When we wants to see the compressed the
the system gets apply inverse FFT and get displayed. Below diagram is the compressed
image after applying inverse FFT.
chapter II 5

Figure 1.3: Output results

The above figure explains the comparison of original image to the compressed image.

Fourier techniques have proven themselves to be invaluable in a wide range of applications

as they allow us to decompose complicated objects such as functions, signals or images
into simpler components. For the purposes of image compression this allows us to remove
redundant information and retain only the most important components of the image.

1.1.7 Results

These results are based on compression techniques with different rates of compression i.e.
Compression rates are 27 percent, 4 percent and 2 percent This is one application of FFT..
Chapter 2

Performance Analysis of
Approximate 8-point FFT of
Radix-2 using Booth Multiplier

2.1 Literature

In order to increase the performance of FFT further an approximate radix-2 Booth

multiplers using approximate full recoding adder and Kogge-stone adder is proposed
here.By using proposed multiplier performance of the FFT is increased by 20 percent
when compared with conventional FFT using normal radix-2 multiplier.

2.1.1 Radix-2 Booth multiplier:-

To explain what is a Booth multiplier that best way to explain through consider an
example.

consider a signed multiplication. Let me show you how booth Multiplier is different from
normal multiplication by considering an example

Booth multiplier is used for reduce the number of multiplication by making the
multiplicand containing more number of Zeroes

6
chapter II 7

Figure 2.1: Radix 2 Booth multiplier example

2.1.2 Radix-4 Booth multiplier:-

This is also called as Bit- pair Recording multiple for further reduce of multiplication
making much more easier

Here is the same example how multiplication happens in radix-4

chapter II 8

Figure 2.2: Radix 4 Booth multiplier example

As we can see that with increase in radix the multiplications becomes much more easier

2.1.3 Advantage:-

Number of Partial Product or Action is reduced. There the there is a reduce of delay as
radix is increased

2.1.4 Wallance tree multiplier

Wallace tree is is used to reduce the partial products. This is done in sequence of steps:
By multiplying the bits by bit to get the result from the any used the half adders and full
address the partial products gets shifts and adding those results withe next sequence of
steps we can obtain the final wallance tree multiplier Take any three wires with the same
weights and input them into a full adder. The result will be an output wire of the same
weight and an output wire with a higher weight for each three input wires.

If there are two wires of the same weight left, input them into a half adder. If there is just
one wire left, connect it to the next layer.
chapter II 9

this is observed in iverilog software.How the multiplication works

Figure 2.3: Output for a Wallace tree multiplier

2.1.5 8-point DIT FFT

An approximate FFT algorithm achieves lower communication requirements for parallel

computing with the help of fast multiple method.The structure of a 8-point DIT FFT
looks like
chapter II 10

Figure 2.4: 8-point DIT FFT Butterfly structure

Chapter 3

Work done and Results

3.1 Work done

I used Xlink software for calculating 8 point fft of radix 2. A verilog code has been
executed for calculating the 8 point fft. In general fft is used to calculate the fft value. In
DFT the inputs are take in sequential manner.The results in DFT are obtained by
considering the inputs one after the other.This results to increase in time and even in
delay. A faster calculating is needed and, It is the reason we go with FFT. In FFT the
input is taken all a time and outputs are obtained in parallel manner.This would reduce
the time and increase the performance.

Using multiplier and adder and considering the bit reveral i.e using discrimination in time
I built a 8 point fft for radix 2 in xlink software. The code has been compiled and waveform
has been generated and the required rtl form syematic view is obtained.

The required area and delay has been reduced and the power value has been increased.

3.2 Results

The required results for the proposed architecture:-

For the gate level behaviour the obtained area, power and delay are
AREA = 4.176(um2 )
11
chapter II 12

P OW ER = 1310.09(uw)
DELAY = 2300.40(ps)
Device = Spartan − 5
speed − 3

The required LUT’s are = 752

Total cell usage are = 1297

Total input and outputs are = 264

The required schematic view in Xlink software:-

Figure 3.1: RTL schematic view in Xlink

chapter I 13

The device used is spartan 5 with speed -3 and required LUT’s are with 1297 and total
number of gates used are 1297 and with inputs and outputs are 264.The obtained values
are obtained from Xlink software

eight point fft in cadence software is are used to calculated the area, power and delay.

Figure 3.2: eight point schematic view in cadence

Existing results
AREA(um2 ) POWER(uw) DELAY(ps)
8088 8.021 15017
7394 7.242 18124
8304 7.040 20287

These results are from the existed research architecture

Bibliography

[1] H. Jiang, J. Han, F. Qiao, and F. Lombardi, “Approximate radix-8 booth multipliers
for low-power and high-performance operation,” IEEE Transactions on Computers,
vol. 65, no. 8, pp. 2638–2644, 2015.

[2] J.-P. Wang, S.-R. Kuang, and S.-C. Liang, “High-accuracy fixed-width modified booth
multipliers for lossy applications,” IEEE transactions on very large scale integration
(VLSI) systems, vol. 19, no. 1, pp. 52–60, 2009.

[3] C.-Y. Li, Y.-H. Chen, T.-Y. Chang, and J.-N. Chen, “A probabilistic estimation bias
circuit for fixed-width booth multiplier and its dct applications,” IEEE Transactions
on Circuits and Systems II: Express Briefs, vol. 58, no. 4, pp. 215–219, 2011.

[4] Y.-H. Chen, C.-Y. Li, and T.-Y. Chang, “Area-effective and power-efficient fixed-width
booth multipliers using generalized probabilistic estimation bias,” IEEE Journal on
Emerging and Selected Topics in Circuits and Systems, vol. 1, no. 3, pp. 277–288,
2011.

14