Booths Algorithm
The Booth’s algorithm is a multiplication algorithm used to perform signed binary
multiplication. It was invented by Andrew Donald Booth in 1951 and it is a more efficient way
of multiplying signed binary numbers as compared to other methods like the classical
multiplication algorithm.
The basic idea behind the Booth’s algorithm is to find a way to reduce the number of partial
products that need to be computed in the multiplication process. This is done by analyzing
the bit patterns of the two numbers being multiplied and identifying patterns of 1’s and 0’s
that can be used to eliminate unnecessary calculations.
The algorithm works as follows:
Step 1: Convert the two numbers into their binary representations.
Step 2: Extend the size of the two binary numbers to include an additional bit at the leftmost
position, which is set to 0 for both numbers.
Step 3: Begin at the rightmost position of the two binary numbers and move left, looking at
groups of three bits at a time. Identify the bit pattern in each group of three bits and apply
the following rules:
If the pattern is “000” or “111”, there is no change to the current partial product.
If the pattern is “001”, “010”, or “011”, add the second number to the current partial
product.
If the pattern is “100”, “101”, or “110”, subtract the second number from the current
partial product.
Step 4: After completing step 3 for all groups of three bits, the resulting partial product is the
EasyExamNotes.com Booths Algorithm
Booths Algorithm
product of the two binary numbers.
Step 5: If the leftmost bit of the resulting product is 1, then the product is negative.
Otherwise, it is positive.
Example, Booth’s algorithm.
Suppose we want to multiply the signed binary numbers -6 and 5.
Step 1: Convert -6 and 5 into their binary representations, which are 1010 and 0101
respectively.
Step 2: Extend the size of the two binary numbers to include an additional bit at the leftmost
position, which is set to 0 for both numbers. The extended binary numbers are 01010 and
00101.
Step 3: Begin at the rightmost position of the two binary numbers and move left, looking at
groups of three bits at a time. The first group of three bits is “010”, which corresponds to a
subtraction operation. The current partial product is -5. The next group of three bits is “101”,
which corresponds to an addition operation. The current partial product becomes -5 + 10 =
5. The final group of three bits is “001”, which corresponds to an addition operation. The final
partial product is 5 + 2 = 7.
Step 4: After completing step 3 for all groups of three bits, the resulting partial product is 7.
Step 5: Since the leftmost bit of the resulting product is 0, the product of -6 and 5 is positive
7.
EasyExamNotes.com Booths Algorithm
Booths Algorithm
The Booth’s algorithm is particularly useful when performing multiplication in hardware
circuits, as it can be implemented using simple logic gates and requires fewer partial
products to be computed than other multiplication algorithms.
Related posts:
1. Structure of Desktop computers
2. Logic Gates
3. Register Organization
4. Bus structure in Computer Organization
5. Addressing modes
6. Register Transfer Language
7. Numerical problem on Direct mapping
8. Registers in Assembly Language Programming
9. Array in Assembly Language Programming
10. Net 31
11. How to start with GNU Simulator 8085
12. Cache Updating Scheme
13. Cache Memory
14. Principle of Cache Memory
15. Cache Mapping
16. Addition and subtraction in fixed point numbers
17. PCI Bus
18. Write a short note on design of arithmetic unit ?
19. Write a short note on Array processors ?
20. Write a short note on LRU algorithm ?
21. What is the format of Micro Instruction in Computer Architecture explain ?
EasyExamNotes.com Booths Algorithm
Booths Algorithm
22. What is the layout of pipelined instruction in Computer Architecture ?
23. Explain the following interfaces in Detail:PCI Bus, SCSI Bus, USB Bus
24. What is Memory Organization ? Discuss different types of Memory Organization in
Computer System.
25. Computer Organization Q and A
26. Write short note on improving cache performance methods in detail ?
27. What is Multiprocessor ? Explain inter process communication in detail ?
28. Briefly explain the concept of pipelining in detail ?
29. Discuss the following in detail: RISC architecture, Vector processing ?
30. Define the instruction format ? Explain I/O System in detail ?
31. Explain the design of arithmetic and logic unit by taking on example ?
32. Explain how addition and subtraction are performed in fixed point number ?
33. Explain different modes of data transfer between the central computer and I/O device
?
34. Differentiate between Serial and parallel data transfer ?
35. Explain signed magnitude, signed l’s complement and signed 2’s complement
representation of numbers. Find the range of numbers in all three representations for
8 bit register.
36. If cache access time is lOOns, main memory access time is 1000 ns and the hit ratio is
0.9. Find the average access time and also define hit ratio.
37. Explain hardwired microprogrammed control unit ? What is address sequencer circuit ?
38. Explain how a stack organized computer executes instructions? What is Stack?
39. Draw and explain the memory hierarchy in a digital computer. What are advantages of
cache memory over main memory?
40. What is Associative memory? Explain the concept of address space and memory space
in Virtual memory.
41. What is Paging? Explain how paging can be implemented in CPU to access virtual
EasyExamNotes.com Booths Algorithm
Booths Algorithm
memory.
42. Explain SIMD array processor along with its architectural diagram ?
43. Write short notes on
44. Draw the functional and structural views of a computer system and explain in detail ?
45. Explain general register organization.
46. Compare and contrast DMA and I/O processors ?
47. Define the following: a) Flynn’s taxonomy b) Replacement algorithm
48. Explain the various pipeline vector processing methods ?
49. Describe the language features for parallelism ?
50. What are different addressing modes? Explain them.
51. Explain any page replacement algorithm with the help of example ?
52. What is mapping? Name all the types of cache mapping and explain anyone in detail.
53. Explain arithmetic pipeline ?
54. Write short notes on, a) SIMD, b) Matrix multiplication c) Instruction format
55. Differentiate: a) Maskable and non-maskable interrupt b) RISC and CISC
56. Computer Organization Previous Years Solved Questions
57. Booths algorithm to muliyiply +5 and -15
EasyExamNotes.com Booths Algorithm
