Virtual Lab - IIT Kharagpur

Booth's Multiplier :

Booth's multiplication algorithm is an algorithm which multiplies 2 signed integers in 2's complement. The algorithm is depicted in the following figure with a brief description. This approach uses fewer additions and subtractions than more straightforward algorithms.

The multiplicand and multiplier are placed in the m and Q registers respectively. A 1 bit register is placed logically to the right of the LSB (least significant bit) Q0 of Q register. This is denoted by Q-1. A and Q-1 are initially set to 0. Control logic checks the two bits Q0 and Q-1. If the twi bits are same (00 or 11) then all of the bits of A, Q, Q-1 are shifted 1 bit to the right. If they are not the same and if the combination is 10 then the multiplicand is subtracted from A and if the combination is 01 then the multiplicand is added with A. In both the cases results are stored in A, and after the addition or subtraction operation, A, Q, Q-1 are right shifted. The shifting is the arithmetic right shift operation where the left most bit namely, An-1 is not only shifted into An-2 but also remains in An-1. This is to preserve the sign of the number in A and Q. The result of the multiplication will appear in the A and Q.

Design Issues :

Booth's algorithm can be implemented in many ways. This experiment is designed using a controller and a datapath. The operations on the data in the datapath is controlled by the control signal received from the controller. The datapath contains registers to hold multiplier, multiplicand, intermediate results, data processing units like ALU, adder/subtractor etc., counter and other combinational units. Following is the schemetic diagram of the Booth's multiplier which multiplies two 4-bit numbers in 2's complement of this experiment. Here the adder/subtractor unit is used as data processing unit.M, Q, A are 4-bit and Q-1 is a 1-bit rigister. M holds the multiplicand, Q holds the multiplier, A holds the results of adder/subtractor unit. The counter is a down counter which counts the number of operations needed for the multiplication. The data flow in the data path is controlled by the five control signals generated from the controller. these signals are load (to load data in registers), add (to initiate addition operation), sub (to initiate subtraction operation), shift (to initiate arithmetis right shift operation), dc (this is to decrement counter). The controller generates the control signals according to the input received from the datapath. Here the inputs are the least significant Q0 bit of Q register, Q-1 bit and count bit from the down counter.

Booth's Multiplier :

Basic stage

Multiple choice questions:

Booth's Multiplier :

1. Start the simulator as directed.This simulator supports 5-valued logic.
2. To perform the experiment on the given modules, we need the datapath specified for booth's multiplication, a controller with a specified state chart, a clock input, bit switch (to give input, which will toggle its value with a double click), bit displays (for seeing output), wires.
3. Instantiating the controller: A control unit can be seen as a finite state machine, so its behavior can be represented in a state table. The controller of the simulator accepts the Moore type state chart and must contain an end state. State names will automatically be generated in the form of S. In the left pane of the simulator, click on the ASM chart button in the controller subsection. Give the required informations in the appeared form as follows:
   • Number of states: 7
   • Number of inputs: 3
   • Number of outputs: 5
   The controller will generate 5 output control signals. After entering these informations, the second form will appear where you can set the names of the inputs and outputs. Here inputs are the Q0, Q-1, count. Outputs control signals are load, add, sub, shift, dc. The order of given input/outputs are maintained while creating terminals of the controller. for example, the first output signal will appear in the left most output terminal (lower terminals), second output will appear in the second left most bit and so on. In case of input terminals, the left most bit is for clock input, so the first input appears in the second terminal, and then the order is maintained. Then the third form will appear where you actually specify the state chart i.e. state, outputs of that state and transition conditions . The fields of the chart will be generated dynamically according to previously given information on states, inputs and outputs.After entering the following state chart, click on the controller component in the palette of the simulator then click on the position of the design editor where you want to put the component (no drag and drop, simple click will serve the purpose).

   

4. Instantiate the Booth's multiplier datapath from the sequential ckt drawer in the palette (by clicking as mentioned previously).
5. The pin configuration of the component is shown whenever the mouse is hovered on any canned component of the palette or pressing the show pin configuration button on the toolbar will show it constantly in the left pane. Pin numbering starts from 1 and from the bottom left corner(indicating with the circle) and increases anticlockwise.
6. Pin configuration of the datapath module:
   • M : Multiplicand (4 bit), Q : Multiplier (4 bit)
   • Initialization : Inl:1, preset:1, set M, Q, start clock
   • Starting multiplication: Inl:0, preset:0, start clock
   • Result: FQ0 to FA3, at end state (here it is S6). These are the content of A(4bit) and Q(4bit) register, total 8 bit (FQ0 is LSB, FA3 is MSB)
   • I/P:
     • Clk:32, Inl:31, preset:30
     • Control pins: load:29, add:28, sub:27, shift:26, dc:25
     • Multiplicand: M3 : 24, M2 : 23, M1 : 22, M0 : 21
     • Multiplier: Q3 : 20, Q2 : 19, Q1 : 18, Q0 : 17
   • O/P: FQ-1 is output of Q-1 bit register, similarly FQ0 to FQ3 are for Q register and FA0 to FA3 are for A register.
     • Datapath to controller input: Count, clkToController, FQ-1, FQ0
     • Count : 16, clkToController : 15, FQ-1 : 14, FQ0 : 13
     • FQ1 : 12, FQ2 : 11, FQ3 : 10
     • FA0 : 9, FA1 : 8, FA2 : 7, FA3 : 6
7. To connect any two components select the Connection menu of Palette, and then click on the Source terminal and click on the target terminal. According to the following diagram connect all the components. Connect the controller outputs to the specified control input terminals of the datapath, specified datapath outputs to the inputs of the controller, the clock input, Bit switches with the inputs and Bit displays component with the outputs (from Display and Input drawer of the pallet,if it is not seen scroll down in the drawer). After the connection is over click the selection tool in the pallete.



8. At first initialize the multiplier by giving the specified inputs specified earlier, this will load the multiplier and multiplicand, then start the multiplication operation by giving the specified inputs specified earlier. At the end state (S6), the multiplication result will be seen through ports FQ0 to FA3 (FQ0 is LSB, FA3 is MSB). The current state of the controller is shown in the left pane as it transits from one state to another. The controller can be reset by clicking the reset controller button in the top toolbar, to start with a new input.

Circuit Diagram

Components :

To build the 4 bit Booth's multiplier, we need :

1. Controller
2. Rigisters, Adder/subtractor unit, multiplexer, down counter, logic gates to construct the datapath
3. Inputs
4. Outputs
5. Wires to connect

Objective of 4 bit Booth's multiplier:

1. Understanding behaviour of Booth's multiplication algorithm from working module and the module designed by the student as part of the experiment
2. Designing Booth's multiplier with a controller and a datapath. This will also help in the learning of control unit design as a finite state machine
3. Understanding the advantages of Booth's multiplier
   • It can handle signed integers in 2's complement notion
   • It decreases the number of addition and subtraction
   • It requires less hardware than combinational multiplier
   • It is faster than straightforward sequential multiplier

Examining behaviour of 4 bit Booth's multiplier for the working module and module designed by the student as part of the experiment (refer to the circuit diagram):

Set M as 0111 which is 7 and Q as 0101 which is 5. Now start the multiplication operation and observe the results including the intermediate results. The Booth's algorithm on those inputs works as the following diagram, so the circuit must behave according to it.

Recommended learning activities for the experiment: Leaning activities are designed in two stages, a basic stage and an advanced stage. Accomplishment of each stage can be self-evaluated through the given set of quiz questions consisting of multiple type and subjective type questions. In the basic stage, it is recommended to perform the experiment firstly, on the given encapsulated working module, secondly, on the module designed by the student, having gone through the theory, objective and procuder. By performing the experiment on the working module, students can only observe the input-output behavior. Where as, performing experiments on the designed module, students can do circuit analysis, error analysis in addition with the input-output behavior. It is recommended to perform the experiments following the given guideline to check behavior and test plans along with their own circuit analysis. Then students are recommended to move on to the advanced stage. The advanced stage includes the accomplishment of the given assignments which will provide deeper understanding of the topic with innovative circuit design experience. At any time, students can mature their knowledge base by further reading the references provided for the experiment.

Booth's Multiplier :

• Start the simulator as directed. For more detail please refer to the manual for using the simulator
• The simulator supports 5-valued logic
• To add the logic components to the editor or canvas (where you build the circuit) select any component and click on the position of the canvas where you want to add the component
• The pin configuration is shown when you select the component and press the 'show pinconfig' button in the top toolbar or whenever the mouse is hovered on any canned component of palette
• To connect any two components select the connection tool of palette, and then click on the source terminal and then click on the the target terminal. By pressing the 'change connection type' in the toolbar the type of the connection can be toggled between shortest path type or manhattan type. Default connection type is mahattan.
• To move any component select the component using the selection tool and drag the component to the desired position
• To give a toggle input to the circuit, use 'Bit Switch' which will toggle its value with a double click
• Use 'Bit Display' component to see any single bit value. 'Digital Display' will show the output in digital format
• undo/redo, delete, zoom in/zoom out, and other functionalities have been given in the top toolbar for ease of circuit building
• Use start/stop clock pulse to start or stop the clock input of the circuit
• Use 'plot graph' button to see input-output wave forms
• Users can save their circuits with .logic extension and reuse them
• After building the circuit press the simulate button in the top toolbar to get the output
• If the circuit contains a clock pulse input, then the 'start clock' button will start the simulation of the whole circuit. Then there is no need to again press the 'simulate' button
• If you are using linux platform then click on 'Linux(32 bit)' or if you are using then click on 'Windows(32 bit)'

Linux(32 bit)

Windows(32 bit)

The combinational logic between the control signals of the controller and the control pins of the registers are to satisfy different operational conditions of individual components. In this design, the controller controls only the multiplication process, the initialization has been seperated, so a multiplexer is used to the clock port of the controller to deactivate ot during initialization. Except M, A, Q, Q-1 registers one more 4-bit register has been used which works as temporary storage. With the preset, the down counter is set to all one which is then decremented. The controller state chart is designed in such a way that at each state it activates only one control signal. The controller of this circuit behaves according to the state chart shown in the procedure section of this experiment. A and Q will hold the final multiplication result.

Back

Back

Click here to download the older version of simulator

Click here to download the new version of simulator

OR

Launch the older version of Simulator

Launch the new version of Simulator

Once the simulator is downloaded, open the command prompt, then go to the directory where you have saved it using cd command and then give the following command to run the simulator:
java -jar coaSimulator.jar

Click here to download the older version of simulator

Click here to download the new version of simulator

OR

Launch the older version of Simulator

Launch the new version of Simulator

Once the simulator is downloaded, open the command prompt, then go to the directory where you have saved it using cd command and then give the following command to run the simulator:
java -jar Simulator.jar

Booth's Multiplier :

References :

Books:

1. Computer Architecture and Organization - John P. Hayes
2. Computer Organization and Architecture - William Stallings
3. Digital Logic and Computer Design - M. Morris Mano. Pearson Education - Prentice Hall.
4. Digital Principles Foundation of Circuit Design and Application - Arun Kumar Singh. New Age Publishers.
5. The Art of Electronics - Paul Horowitz and Winfield Hill (1989). Cambridge University Press
6. Modern Dictionary of Electronics - Rudolf F. Graf (1999). Newnes

Web Sites:

• NPTEL (e-learning courses from IITs and IISC)

Virtual Lab is an initiative of Ministry of Human Resource and Development(MHRD) under National Mission of Education through ICT to provide an interactive environment over the internet for creating and conducting different laboratory experiments by sharing the costly equipments and the resources.

For more information about the Virtual Lab,please visit http://www.vlab.co.in/

Developers of Logic Design and Computer Organization Virtual Lab

• Dr. Chittaranjan Mandal
Professor, Computer Science & Engineering
Professor, Information Technology
IIT Kharagpur
• Gargi Roy
Senior Project Assistant
• Devleena Ghosh

Target Audience:

Under graduate students.

Courses Aligned With:

Computer organization and artitecture.

Pre-requisite Softwares:

• 32 bit java runtime environment and java 1.6 or above
• Recommended browser: mozilla firefox, google chrome

Objectives:

The Objective is to Expose the students to the various key aspects of Computer Organisation by enabling them to perform FPGA based prototyping of experiments with support of a virtual environment. The primary need for virtualisation here is multifold.

1. Digital Logic and Computer Organisation are core courses in most of the Undergraduate Curricula of the entire Electrical Sciences Discipline(Computer Science / Engg., Electronics, Electrical) etc.
2. Many colleges/institutes cannot procure sufficient number of FPGA boards for their students.
3. Even when such FPGA boards are available, making them available round the clock is difficult.
4. Expert help is required to effectively use these FPGA boards and such help can be easily channeled through a virtual environment.
5. Helps to standardize the set of Experiments to a large extent.

Feedback:

To give your feedback please visit the following link-

Sponsered by MHRD (NME-ICT) .

Tutorial on UI for lab:

Introduction:

1. The simulator contains a pallete on the right hand side. This pallete contains all the components and tools . Tools are used to act up on the components. Different tools:
   • Selection tool- used for selecting components
   • Marquee tool- used for selecting many components at a time by draggiung the mouse in the design area(editor).
   • Connection tool- used for connecting components
2. Components have been catagorized according to their functionality and put into different drawers in the pallete. The area under every drawer is scrallable, if you are unable to see all the components in a particular drawer just click on the area and scroll. Different drawers:
• Circuits- contains 8 and 16 terminal circuits and flow container which can hold other circuit components.
• Logic gates- contains all kinds of basic logic gates.
• Display and inputs- contains all kinds of component needed to give input to the circuit and displaying outputs of the circuit.
• Adders- contains different types of adder circuits.
• Sequential ckt- contains basic flipflops for designing sequential circuits.
• Other Components- contains different kinds of components like decoders, multiplexers, arithmetic logic units(ALU), memory elements(RAM cell) required to design combinational circuits.
3. To add the components to the editor select any component(first click on the selection tool then click on the desired compoent) then finally click on the position of the editor window where you want to add the component.
4. The pin configuration of a component is shown whenever the mouse is hovered on any canned component of the palette. Pin numbering starts from 1 and from the bottom left corner(indicating with the circle) and increases anticlockwise.
5. To connect any two components select the Connection tool in the palette, and then click on the Source terminal and click on the target terminal(no drag and drop, simple click will serve the purpose). After the connection is over click the selection tool in the pallete.
6. To move any components select the Selection Mode and drag the component after selecting it.
7. If needed select any component in the editor while designing your circuit and use Undo, Redo, Delete,Zoom in, Zoom out buttons to get corresponding functionalities. Open and Save options are under development.
8. As the automated clock is under development and the simulator is under modification for sequencial circuits, for the time being please use individual clock(Bit switch which toggle its value with a double click) for each flipflop.
9. The simulator is currently under modification for sequential circuits, now it is working properly for combinational circuits but may not give proper output for sequential circuits.

Description of Components:

1. Digital display: it can be used to give input and as well as to see the output in the decimal format, its right most terminal is the LSB(least significant bit) and the left most terminal is the MSB(most significant bit), in the editor after selecting a particular digital display you can use 'Increment LED' and 'Decrement LED' buttons in the top left corner of the simulator to increment and decrement its value respectively.
2. Bit display: it displays a single bit value.
3. V+: it gives 1 as input.
4. Ground: it gives 0 as input.
5. Bit switch: it gives 1/0 input, it toggels its value with a double click.

Testing process:

1. To test your circuit give some input(through Digital display or Bit switch or V+ or Ground), if you use the Digital display or Bit switch you can then give different input to you circuit through incrementing/decrementing the Digital display or double clicking the Bit switch, the other two gives constant inputs.
2. to see the output, connect Digital display or Bit display to the output terminals of your circuit.

Frequently Asked Questions:

What is virtual lab?

The Virtual Laboratory is an interactive environment for creating and conducting simulated experiments: a playground for experimentation. It consists of domain dependent simulation programs, experimental units called objects that encompass data files, tools that operate on these objects.

What are the advantages of virtual lab?

Virtual Logic Design and Computer Organisation lab enables students to perform FPGA based prototyping of experiments with support of a virtual environment. The primary need for virtualisation here is multifold.

1. Digital Logic and Computer Organisation are core courses in most of the Undergraduate Curricula of the entire Electrical Sciences Discipline ( Computer Science / Engg., Electronics, Electrical ] etc.
2. Many colleges/institutes cannot procure sufficient number of FPGA boards for their students.
3. Even when such FPGA boards are available, making them available round the clock is difficult.
4. Expert help is required to effectively use these FPGA boards and such help can be easily channeled through a virtual environment.
5. Helps to standardize the set of Experiments to a large extent.

What is eclipse platform?

Eclipse is a Java-based, extensible open source development platform. By itself, it is simply a framework and a set of services for building a development environment from plug-in components. Eclipse comes with a standard set of plug-ins, including the Java Development Tools (JDT).

Which framework is used to develop the application?

We have used the eclipse gef framework. The Graphical Editing Framework (GEF) allows developers to take an existing application model and quickly create a rich graphical editor.

What is platform independent application?

Applications that run under particular operating systems and/or particular hardwares are called platform dependent application whereas platform independent applications can run in any operating environment.

What are the experiments which can be performed by the Virtual Logic Design and Computer Organization lab?

The experiments that will be supported by this lab are given below:

1. Design of a ripple carry adder
2. Design of a carry-look-ahead adder
3. Design of registers and counters
4. Design of a wallace tree adder
5. Design of combinational multipliers
6. Design of a Booth’s multiplier
7. Design of an ALU
8. Design of memory units
9. Design of direct mapped cache
10. Design of associative cache
11. Design of combinational dividers
12. CPU design