Carry Lookahead parallel addition · ALG 15.2

Add x + y the parallel way, one round at a time. Every cell of a round is computed at the same time, so the number of rounds is the parallel time. A block's behavior says what happens to a carry entering it from below: 0 = absorbs it, 1 = generates a carry, < = copies it. First find the behaviors of the 1-bit blocks, then combine them up the tree, then send the carries c_i down, then the sum bits z_i. Click a cell (or type 0, 1, <), then press Enter to finish the round.

n =

round 0 / 9

mistakes 0

time –

best (n=8) –

solved 0

Press New numbers or Timed round to start.

Combining blocks (ALG 15.2). Block B = higher part H on top of lower part D:

H absorbs → B absorbs. H generates → B generates. H copies → B behaves like D. It is just function composition.

A carry leaving block [i, j]: c_j+1 = behavior applied to c_i.

Sum bits: z_i = x_i ⊕ y_i ⊕ c_i, and z_n = c_n.

Rounds: parallel vs schoolbook

Each round has constant depth. The schoolbook adder chains n boxes, each waiting for the previous carry: depth Θ(n). Here: 1 + log n + (log n + 1) + 1 = 2 log n + 3 rounds, so depth Θ(log n), with Θ(n) gates.

Hardware designers call the three behaviors kill, propagate and generate; adders built on this idea are known as carry-lookahead adders. A fourth behavior, negation, would also be a function from one bit to one bit, but no block can have it.

← ADS2 Arcade