Booth algorithm in computer architecture

Authors • Pam Smallwood Regis University Abstract In this activity, students will learn how to apply Booth’s algorithm to multiply two signed 2’s complement binary integers. Prior to this activity, students should know how to convert signed decimal values to and from their binary 2’s complement representation, and be able to determine the range of values that can be represented by 2’s complement within a specified number of bits. The activity was designed for use in a Computer Organization & Architecture course, but could be used in any course that covers how computers perform integer multiplication. After completing this activity, students will be able to: • Identify the multiplicand and multiplier for multiplication • Apply Booth’s algorithm to multiply signed 2’s complement binary integers This activity was developed with NSF support through IUSE-1626765. You may request access to this activity via the following link: • Level: Undergraduate • Setting: Classroom • Activity Type: Application • Discipline: Computer Science • Course: Computer Architecture • Keywords: Booth’s algorithm, binary multiplication, 2’s complement multiplication Author Biography Pam Smallwood, Regis University

• Xplore • • • • • • • A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2023 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

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, A n-1 is not only shifted into A n-2 but also remains in A n-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 regi...

Table of Contents • • • • • • • • • • What is the difference between Booth and modified booth? In comparison with the original Booth’s algorithm, which examines two bits at a time, the modified algorithm requires half the nutmber of iterations at the cost of somewhat increased complexity for each iteration. What are booth and modified Booth algorithms? It is a simple method to multiply binary numbers in which multiplication is performed with repeated addition operations by following the booth algorithm. Again this booth algorithm for multiplication operation is further modified and hence, named as modified booth algorithm. For which condition’s Booth’s algorithm performs better than the normal multiplication algorithm? When the ones in a multiplier are grouped into long blocks, Booth’s algorithm performs fewer additions and subtractions than the normal multiplication algorithm. READ: What code appears in Pixar movies? What are the advantages of Booth’s algorithm over other algorithms for multiplication? Advantages of booth’s multiplication: Easy calculation of multiplication problem. Consecutive additions will be replaced. Less complex and ease scaling. What is the advantage of using booth algorithm? What is the advantage of using Booth algorithm? 1) It handles both positive and negative multiplier uniformly. 2) It achieves efficiency in the number of additions required when the multiplier has a few large blocks of 1’s. 3) The speed gained by skipping 1’s depends on the da...

Booth’s algorithm is a multiplication algorithm that multiplies two signed binary numbers in 2’s complement notation. Booth used desk calculators that were faster at shifting than adding and created the algorithm to increase their speed. Booth’s algorithm is of interest in the study of computer architecture. Here’s the implementation of the algorithm. Examples: Input : 0110, 0010 Output : qn q[n+1] AC QR sc(step count) initial 0000 0010 4 0 0 rightShift 0000 0001 3 1 0 A = A - BR 1010 rightShift 1101 0000 2 0 1 A = A + BR 0011 rightShift 0001 1000 1 0 0 rightShift 0000 1100 0 Result=1100 first, before moving on to the solution. Algorithm : Put multiplicand in BR and multiplier in QR and then the algorithm works as per the following conditions : 1. If Q n and Q n+1 are same i.e. 00 or 11 perform arithmetic shift by 1 bit. 2. If Q n Q n+1 = 01 do A= A + BR and perform arithmetic shift by 1 bit. 3. If Q n Q n+1 = 10 do A= A – BR and perform arithmetic shift by 1 bit.