--- title: "Booth multiplication with hardware" subject: "Computer Organization and Architecture" chapter: 5 key: "semester_5/computer_organization_and_architecture:booth-hardware" source: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/booth-hardware site: BCT Engineering --- # Booth multiplication with hardware Computer Organization and Architecture · Chapter 5: Computer Arithmetic - Asked in: 2073 Chaitra, 10 marks - Video: [Booth's Algorithm (Hardware Implementation and Flowchart) | COA | booths | booths algo](https://www.youtube.com/watch?v=TR3Z1wOAtr8) — Always Learn More - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/booth-hardware - Whole chapter: https://www.bctengineer.com/md/semester_5/computer_organization_and_architecture/chapter-5 ## Question Explain Booth algorithm of multiplication with hardware implementation diagram and multiply -10×6. ## Short answer Booth algorithm multiplies signed 2's complement numbers by examining (Q0,Q-1) pairs; performs add/subtract and arithmetic shift right n times. Hardware includes A,Q,Q-1 shift register, adder/subtractor, M register, counter. For -10×6, with n=5 bits, result = -60 (11110 00100). ## Answer #### Booth algorithm Booth's algorithm multiplies two signed numbers in 2's complement form. It looks at the multiplier bit pair (Q0, Q-1) and treats a run of 1s as (next higher power − lowest power), so a block of 1s needs only one subtraction and one addition. 1. Load M = multiplicand, Q = multiplier, A = 0, Q-1 = 0, SC = n (number of bits). 2. Look at (Q0, Q-1): - 00 or 11: no arithmetic. - 10 (start of a run of 1s): A = A − M. - 01 (end of a run of 1s): A = A + M. 3. Arithmetic shift right the combined A, Q, Q-1 by one bit (the sign bit of A is kept). 4. SC = SC − 1. If SC ≠ 0 go to step 2; otherwise stop. 5. The 2n-bit product is in A:Q. #### Hardware implementation ```text +--------+ +----------------+ | M | | Control / SC | +---+----+ +----------------+ | n bits ^ Q0, Q-1 | add/sub, shift v | v +-----------------------------------+ | n-bit parallel adder / subtractor | +-----------------+-----------------+ | n bits v +----------+ +---------+ +----+ | A |-->| Q |-->|Q-1 | | (ASR -->)| | | | | +----------+ +---------+ +----+ ``` - **M** holds the multiplicand; **A** (accumulator) starts at 0 and **Q** holds the multiplier; **Q-1** is a one-bit flip-flop. - The adder/subtractor adds M or its 2's complement to A, as decided by the control unit from Q0 Q-1. - A, Q and Q-1 form one shift register that does an arithmetic shift right. - The sequence counter SC counts n cycles. #### Flowchart ```text +-----------------------+ | A=0, Q-1=0, SC=n | | M=multiplicand Q=mult | +-----------+-----------+ v +-----------------------+<-----------+ | Q0 Q-1 = ? | | +--+---------+--------+-+ | 10| 01| 00/11| | v v | | A = A - M A = A + M | | | | | | +----+----+---------+ | v | +-----------------------+ | | ASR (A, Q, Q-1) | | | SC = SC - 1 | | +-----------+-----------+ | v | SC = 0 ? --- No --------------+ | Yes v Product in A,Q ``` #### Multiply −10 × 6 Five bits are needed (−10 = 10110, 6 = 00110). Multiplicand M = -10 = 10110, multiplier Q = 6 = 00110, -M = 01010, n = 5 bits. ```text Step Action A Q Q-1 - Initial 00000 00110 0 1 Q0Q-1=00: no change 00000 00110 0 ASR 00000 00011 0 2 Q0Q-1=10: A = A - M 01010 00011 0 ASR 00101 00001 1 3 Q0Q-1=11: no change 00101 00001 1 ASR 00010 10000 1 4 Q0Q-1=01: A = A + M 11000 10000 1 ASR 11100 01000 0 5 Q0Q-1=00: no change 11100 01000 0 ASR 11110 00100 0 ``` Result in A,Q = 11110 00100 = -60. **Answer: -10 × 6 = -60** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In Booth's algorithm, what is done when (Q0, Q-1) = 10? A. A = A + M B. A = A - M C. No arithmetic, only shift D. A = A - Q Answer: B. A pair 10 marks the start of a run of 1s in the multiplier, so M is subtracted from A before the shift. (Key point: Booth pair 10) 2. Why does Booth's algorithm need fewer operations for a multiplier with a block of 1s? A. Every 1 bit is added once, but zeros are skipped B. The block of 1s is replaced by 0s C. A run of 1s is treated as (next higher power - lowest power): one subtraction and one addition D. The multiplicand is shifted left instead of the product shifting right Answer: C. The block of 1s is the difference of two powers of 2, so only one subtract (at 10) and one add (at 01) are needed. (Key point: Run of 1s idea) 3. What kind of shift is applied to A, Q, Q-1 after each step? A. Arithmetic shift right, keeping the sign bit of A B. Logical shift left C. Logical shift right, filling 0 into A D. Rotate right through carry Answer: A. A, Q and Q-1 form one shift register doing ASR so the sign of the partial product is preserved. (Key point: Arithmetic shift) 4. What is -10 x 6 by Booth's method with 5-bit registers, and where is it held? A. 60, in A:Q = 00001 11100 B. -60, in A alone C. -16, in A:Q = 11110 10000 D. -60, in A:Q = 11110 00100 Answer: D. After 5 cycles the 10-bit product is in A:Q: 11110 00100 = -60. (Key point: Result of -10 x 6) ## Related in Computer Organization and Architecture - [Booth multiplication algorithm and hardware](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-algorithm) — Computer Organization and Architecture, chapter 5, asked 8× - [Booth multiplication of -7 × -10](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-7x-10) — Computer Organization and Architecture, chapter 5, asked 5× - [Booth multiplication of 10 × (-5)](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-10x-5) — Computer Organization and Architecture, chapter 5, asked 5× - [Booth multiplication of -5 × -9](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-5x-9) — Computer Organization and Architecture, chapter 5, asked 5× - [Booth multiplication of 5 × -6](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-5x-6) — Computer Organization and Architecture, chapter 5, asked 5× - [Booth multiplication of -6 × -11](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-6x-11) — Computer Organization and Architecture, chapter 5, asked 5×