Both machines you built last session get slower in exact proportion to how wide they are. Today, two separate ideas, each attacking a different half of the cost.
Collect the send-off: multiplying by 0111 in two operations. Somebody will have found 1000 minus 1.
The cost is a product of two numbers. So there are two things to attack.
the hour in two levers
Lever one: fewer rows to add. Booth recoding turns thirty two partial products into sixteen, and it needs the subtractor you built in Class 23.
Lever two: a cheaper way to add them. Carry-save adders and a Wallace tree turn a stack of rows into two numbers in logarithmic depth.
They are independent. Each works without the other, and together they multiply.
Draw the two levers on the board and keep them there. The hour is one lever, then the other, then both.
Last session ended at seventy five gate delays. Where are they?
the cost, factored
The array is thirty two rows deep, and each row costs a constant. Depth times cost per row.
Halve the number of rows and you halve one factor. Turn the stack into a tree and you attack the other.
Write it as a product on the board. Rows times cost. Two factors, two levers.
your send-off, collected
Multiplying by 0111 takes three additions. It should take two operations.
and this is why Class 23 mattered
A run of ones of any length is one add at the top and one subtract at the bottom. Fifteen ones become two operations.
You could not have done this before Class 23. Subtraction is what makes the shortcut available.
Let them see a run of fifteen ones collapse to two operations. That is the moment the idea sells itself.
click any bit of the multiplier
So recode the multiplier: look at each bit and the one below it.
try
Transitions are where the work is. A bit that matches the one below it costs nothing at all.
GOOD FOR ONE DESIGN, USELESS FOR THE OTHER
That helps design one enormously, and design two not at all.
why
The sequential machine skips a turn when a row is zero, so fewer nonzero rows really is fewer cycles.
The array has to be built for the worst case. Thirty two rows of hardware exist whether they carry zeros or not.
To help the array you need structurally fewer rows, not just emptier ones.
This honesty matters. Radix-2 Booth is a real technique with a real limit, and the limit motivates radix-4.
MODIFIED BOOTH, RADIX FOUR
So consume two bits of the multiplier per row instead of one.
remember
Three bit windows, overlapping by one, sliding two bits at a time. Sixteen windows cover a thirty two bit multiplier.
Sixteen windows, sixteen rows. Half the hardware, and the saving is structural, so the array gets it too.
The overlap is the part people miss. Each window shares its bottom bit with the window below.
click any row of the table
Eight possible windows, and every one of them is easy.
Derive two or three rows with them rather than reading the table out. The pattern is the transition idea again.
Five things a row can be, and not one of them is a multiplication.
remember
Times two is a shift, which is wiring. Negation is flip the bits and add one, exactly as in Class 23.
And the add-one is free again, because each row goes into the summing tree with its own carry-in position.
Class 23 pays for itself twice here: the subtract in the recoding, and the negation of the multiples.
One honest caveat, and it happens to suit you perfectly.
remember
Booth is a signed algorithm. On thirty two bit two's complement numbers it gives exactly sixteen rows.
On unsigned numbers you need a seventeenth window, because the top bit would otherwise be read as negative.
Since Class 23, every number in this machine is two's complement. The algorithm and the representation already agree.
Checked against all 65536 signed eight bit pairs. Mention that if anybody doubts the encoding.
Sixteen rows is better. They are still being added in a stack.
the second lever, independent of the first
Every adder in that stack settles its carries across sixty four columns and then hands the answer straight to another adder.
You are resolving carries over and over, when only the very last answer ever leaves the multiplier.
Same observation as in the array. Now you do something about it properly.
THE CARRY-SAVE ADDER
A full adder, from Class 19, doing a job you never asked it for.
remember
Sixty four full adders side by side, with nothing wired between them, take three numbers and give back two.
Two gate delays, and it stays two whatever the width is, because no carry ever travels sideways.
The carries are not lost. They are handed on as a second number, to be settled later.
Stress the independence of the columns. That is the entire reason the delay does not grow with width.
step through the levels
Group the rows in threes, squash, repeat.
rows
Run it from 32 and from 16 so they see what Booth bought: two whole levels, and half the tree.
Two numbers left, and a promise to keep.
remember
Every carry you deferred is still sitting in that second number. One carry-propagating addition settles all of them at once.
The adder from Class 22, used exactly once, doing the one job that genuinely cannot be deferred.
Deferring work is not avoiding it. You still pay, once, at the moment somebody needs the answer.
One variation worth knowing the name of.
remember
Wallace squashes as hard as it can at every level. Dadda squashes only as much as it must to stay on schedule.
Same number of levels, slightly fewer full adders, slightly more wiring. Real chips use both.
Thirty seconds on this. They need the name and the idea, not the construction algorithm.
Now pull both, and count.
remember
Booth halved the rows, which took the tree from eight levels to six. That is four gate delays, and half the tree's area.
Twenty six gate delays, 520 picoseconds, and about 4600 gates. Fewer gates than the plain array, and three times faster.
The two levers compose. Neither one needed the other, and together they beat both designs from last session.
Everything you have built for multiplication, on one chart.
the shape of the progress
The first two are linear in the width. The last two are logarithmic, and that is the whole difference.
Doubling to sixty four bits costs the sequential design thirty two more cycles, and costs the Wallace tree one extra level.
The linear against logarithmic distinction is the export. It is the same shape as Class 21 and 22.
Seven down, two to go.
the export from these two hours
When something costs rows times cost per row, there are two independent levers, and you should look for both.
Recoding the input can be cheaper than rebuilding the circuit. Booth changed no hardware in the adder at all.
And deferring carries is almost always allowed, right up until somebody reads the answer.
Name both exports. The two-levers instinct is the one that transfers furthest.
Seventy five delays, down to twenty six.
Half of it came from making fewer things to add. The other half came from refusing to finish adding until the very end. Neither idea touched the adder itself.
Next session: division. Both tricks today depended on every row existing before you started. Division cannot give you that, because you do not know the next digit of the answer until you have used the last one.
Stop here. Send off: long-divide 143 by 11 in binary. At each step write down exactly what you had to know before you could take the next one.