BitFlow
← Academy·Fast Arithmetic: Lookahead, BCD and Multipliers
×GATE~45 min

Fast Arithmetic: Lookahead, BCD and Multipliers

Beat the ripple with carry lookahead, add in decimal, multiply in hardware, and see how Booth's algorithm handles signed numbers.

Carry lookahead

A ripple adder is slow because each carry waits for the one before it. But every carry is just a function of the inputs, so why not compute them all directly? For each bit, define two signals.

SignalEquationMeaning
Generategᵢ = aᵢbᵢThis column makes a carry, whatever comes in
Propagatepᵢ = aᵢ ⊕ bᵢThis column passes on a carry coming in

A column carries out if it generates, or if it propagates and a carry came in: cᵢ₊₁ = gᵢ + pᵢcᵢ. Now substitute each carry into the next until only g, p and c₀ remain.

c₁ = g₀ + p₀c₀
c₂ = g₁ + p₁g₀ + p₁p₀c₀
c₃ = g₂ + p₂g₁ + p₂p₁g₀ + p₂p₁p₀c₀
c₄ = g₃ + p₃g₂ + p₃p₂g₁ + p₃p₂p₁g₀ + p₃p₂p₁p₀c₀

Each line is two levels of logic, AND then OR, so every carry is ready after the same short time: 1 gate delay for g and p, plus 2 for the carry. Now race them.

Loading the animation…

You can see the catch in the equations: the terms get longer, and c₄ already needs a 5-input AND. That's why adders use 4-bit groups. Each group produces its own group generate and propagate, and a second lookahead unit works across groups, so the delay grows with the logarithm of the width, not the width.

WidthRipple: last carryLookahead: slowest carry
4 bits83
16 bits327
64 bits12811
In gate delays, counting each AND or OR as one, whatever its width.
Practice

For a column with a = 1, b = 0, what are g and p?

Practice

With a 4-bit lookahead adder, what does a sum bit take, counting XOR as one gate delay?

BCD adder

Chapter 4 said a BCD digit sum above 9 needs 6 added. In hardware, use a normal 4-bit adder, detect the bad cases, and pass the result through a second adder that adds 0 or 6.

correct = carry + s₃s₂ + s₃s₁
Sum above 15 sets the carry. Sums from 10 to 15 have s₃ = 1 and either s₂ or s₁ = 1.

Loading the circuit…

One BCD digit of a BCD adder. tens is the carry into the next digit. Input only 0 to 9 on a and b.
  • Set a = 7 and b = 5. The first adder gives 12, a bad digit, so 6 gets added: the display shows 2 with tens on, which reads 12.
  • Set a = 9 and b = 9. The sum is 18, and the display shows 8 with tens on.
Practice

What does a BCD adder output for 8 + 6?

Multipliers

Binary multiplication is shift and add. Each partial product is the top number ANDed with one multiplier bit, and the rest is addition. So you can choose: one adder and a clock cycle per bit, or a large block of gates and the answer at once.

Loading the animation…

A sequential multiplier uses one adder and a shift register, taking n clock cycles for n bits. An array multiplier lays out all the ANDs and adders as a grid of pure logic: it's fast, with no clock, but large. An n × n array takes n² AND gates and n − 1 rows of adders.

Loading the circuit…

A 2 × 2 array multiplier: four ANDs make the partial products, and two half adders add them. Displays are in hex.
  • Set a = 3 and b = 3. The product is 9.
  • Press Slow motion and change an input, to see the outputs settle at different times.
Practice

How many bits can the product of an 8-bit and a 6-bit unsigned number need?

Putting it together: the ALU

An arithmetic logic unit is an adder and some gates behind a MUX. An operation code selects which result reaches the output, and flags like zero and carry report what happened. It's the heart of a processor, and you now know every part inside it.

Loading the circuit…

A 4-bit ALU. The operation codes are: 0 add, 1 subtract, 2 AND, 3 OR, 4 XOR, 5 set-if-less-than, 6 NOT a, 7 pass a.
  • Set a = 5 and b = 5, then op = 1. The result is 0, and zero lights. That's how a processor checks equality.
  • Step through op with a = 12 and b = 10, and check each result by hand.

Booth's algorithmGATE: fine to skip at first

Plain shift and add doesn't handle two's complement multipliers directly, and it does an addition for every 1. Booth's idea uses a simple fact: a run of 1s equals one subtraction and one addition. For example, 0111 1110 = 1000 0000 − 0000 0010.

Q₀ Q₋₁MeaningAction
0 0Inside a run of 0sNothing
1 1Inside a run of 1sNothing
1 0A run of 1s startsA = A − M
0 1A run of 1s endsA = A + M
After each step, shift A, Q and Q₋₁ right together, copying A's sign bit.

Loading the animation…

Long runs make Booth quick. But alternating bits, such as 0101 0101, are its worst case, because every pair triggers an operation. Hardware often uses modified Booth, which looks at three bits at a time and halves the number of partial products.

Practice · GATE-style

How many additions or subtractions does Booth's algorithm do for the 8-bit multiplier 0111 1110?

Practice · GATE-style

How many does it do for the 8-bit multiplier 0101 0101?

Practice · GATE-style

What's the recoded form of 0110 under Booth?

To add many numbers at once, as a multiplier must, there's a neat trick: a carry-save adder doesn't propagate carries at all. It reduces three numbers to two, a sum word and a carry word, in a single full-adder delay. Stack these in a Wallace tree, and only the last two numbers need a real carry-propagate adder.

Practice · GATE-style

A 16-bit carry lookahead adder of 4-bit groups: what's the slowest carry, in gate delays, by this chapter's count?

Was this chapter helpful?