Booth's Algorithm: How a Binary Multiplier Halves Its Rows

How can a binary multiplier use fewer partial-product rows? Booth’s algorithm does it by allowing digits to be negative, turning runs of ones into a simpler combination of additions and subtractions. Radix-4 Booth recoding takes the idea further by encoding pairs of bits, reducing the number of partial-product rows by half. This video works through the idea using 47 × 99, from the recoding process to the circuit that generates each partial-product row. At 32 bits, radix-4 Booth reduces the design from 32 rows to 16 and requires fewer than half as many full adders. It reduces the amount of hardware involved, but does not by itself make the multiplier faster. 0:33 Booth's algorithm 1:16 Two bits at a time 2:02 Every digit from minus two to two 2:44 Radix-4 Booth recoding 3:30 A row without an adder 4:32 Forty-seven times ninety-nine 5:02 What it saves 5:28 Booth recoding Music: Erik Satie, Gymnopédie No. 1, and Johann Pachelbel, Canon in D, arranged for piano, public domain, played for this video on the FreePats Upright Piano KW (CC0). #digitaldesign #computerarchitecture #logicgates #computerscience #electricalengineering