Carry-lookahead adder: Question bank — Hardware deep dive

Before you start, keep three anchors from the parent in mind:

Generate $g_{i} = a_{i} b_{i}$ — "this bit makes a carry by itself."
Propagate $p_{i} = a_{i} \oplus b_{i}$ — "this bit passes a carry through."
The whole trick: $c_{i + 1} = g_{i} + p_{i} c_{i}$ , unrolled so no carry waits for another.

True or false — justify

Every reveal below is True/False + a one-line reason. Don't accept the verdict without the because.

CLA computes all carries in a delay that does not depend on the number of bits

n

True (idealised) — each carry is a fixed 2-level AND–OR of the

g

's,

p

's and

c_{0}

, so depth is constant; but this ignores the fan-in blow-up that forces hierarchy in real chips.

"Parallel carry computation" means CLA has zero delay.

False — parallel means constant depth (~4 gate levels), not instantaneous; the

g_{i}, p_{i}

still take a gate delay and the AND–OR still takes two.

Using

p_{i} = a_{i} + b_{i}

(OR) instead of XOR breaks the carry output.

False — the carry is fine, because OR and XOR differ only when

a_{i} b_{i} = 1

, and there

g_{i}

already forces

c_{i + 1} = 1

; it breaks the sum bit, not the carry.

The generate signal

g_{i}

can be 1 even when the incoming carry

c_{i}

is 0.

True —

g_{i} = a_{i} b_{i}

depends only on that bit's own inputs; generation is by definition independent of any incoming carry.

p_{i} = 0

for some bit, no carry can ever pass through that position.

True —

c_{i + 1} = g_{i} + p_{i} c_{i}

; with

p_{i} = 0

the term

p_{i} c_{i}

vanishes, so

c_{i + 1} = g_{i}

and the incoming carry is blocked (only local generation survives).

A CLA and a ripple-carry adder can give different final sums for the same inputs.

False — CLA only rearranges the same Boolean equations for speed; both implement identical logic, so the outputs are bit-for-bit equal.

Hierarchical (block) CLA uses completely different math from single-bit CLA.

False — it is the same recurrence

C_{out} = G + P C_{in}

one level up, with group

G, P

replacing per-bit

g, p

Increasing the CLA width from 4 to 64 bits keeps gate fan-in the same.

False — the

c_{i + 1}

formula's product terms grow with

i

, so wide flat CLA needs impractically large fan-in gates; that is exactly why designers stop at ~4-bit blocks.

Spot the error

Each item states a plausible-but-wrong claim. The reveal names the flaw.

p_{i} = a_{i} \oplus b_{i}

means 'either input is 1', so I'll write

p_{i} = a_{i} + b_{i}

XOR is "exactly one is 1", not "at least one"; OR wrongly makes

p_{i} = 1

when both are 1, which corrupts

s_{i} = p_{i} \oplus c_{i}

c_{2} = g_{1} + p_{1} g_{0}

, so I can drop the

c_{0}

term entirely."

Only valid when

c_{0} = 0

; the general expansion always ends with

c_{0} p_{1} p_{0}

, and forgetting it gives wrong answers whenever the adder has an incoming carry.

"Since

c_{i + 1} = g_{i} + p_{i} c_{i}

is recursive, CLA still waits for

c_{i}

like ripple does."

The recurrence looks serial, but CLA unrolls it into a flat sum of products of only

g, p, c_{0}

— no

c_{i}

appears on the right, so nothing waits.

s_{i} = a_{i} \oplus b_{i}

is the sum bit."

That's only

p_{i}

; the true sum is

s_{i} = p_{i} \oplus c_{i} = a_{i} \oplus b_{i} \oplus c_{i}

— you must XOR in the incoming carry.

"The 4-bit group propagate is

P = p_{3} + p_{2} + p_{1} + p_{0}

It's the product

P = p_{3} p_{2} p_{1} p_{0}

(AND) — a carry propagates through the whole block only if every bit propagates, not just one.

"CLA replaces the full adders, so we no longer compute

s_{i}

with XOR."

CLA only speeds up the carry path; the sum bits still use

s_{i} = p_{i} \oplus c_{i}

, reusing the same full-adder XOR logic (Full Adder).

"Group generate is

G = g_{3} + g_{2} + g_{1} + g_{0}

Wrong — a lower bit's generate only escapes the block if all higher bits propagate:

G = g_{3} + p_{3} g_{2} + p_{3} p_{2} g_{1} + p_{3} p_{2} p_{1} g_{0}

Why questions

Why must

g_{i}

and

p_{i}

depend only on

a_{i}, b_{i}

and never on

c_{i}

Because their whole purpose is to be available immediately (in 1 gate delay); if they depended on

c_{i}

we'd reintroduce the serial waiting CLA was built to kill.

Why does unrolling the recursion remove the speed problem?

Substitution replaces each

c_{i}

by inputs, turning a depth-

n

chain into a single 2-level AND–OR expression whose depth is fixed regardless of

n

Why does the carry equation tolerate

p_{i} = a_{i} + b_{i}

but the sum does not?

OR and XOR differ only at

a_{i} = b_{i} = 1

, where

g_{i} = 1

already sets the carry; but

s_{i} = p_{i} \oplus c_{i}

reads

p_{i}

directly, so the wrong

p_{i}

produces a wrong sum bit.

Why do real chips use 4-bit blocks instead of one giant flat CLA?

A flat

n

-bit CLA needs gates with fan-in up to

n + 1

; fan-in and gate count grow too large, so hierarchy keeps each gate small (Propagation Delay & Fan-in).

Why is CLA's delay called "constant" even though wider adders add hierarchy levels?

Each hierarchy level adds a fixed couple of gate delays; the total grows like

lo g n

at worst (as in Prefix Adders (Kogge-Stone)) — far below ripple's linear

2 n

Why is unrolling

c_{i + 1} = g_{i} + p_{i} c_{i}

"just Boolean algebra"?

It's repeated substitution plus the distributive law

p_{i} (g_{i - 1} + p_{i - 1} c_{i - 1}) = p_{i} g_{i - 1} + p_{i} p_{i - 1} c_{i - 1}

— no new axioms, see Boolean Algebra.

Why does one generate followed by all propagates make a carry "travel instantly" in CLA?

In the unrolled formula that single

g_{k}

is ANDed with the propagate product and ORed straight into every higher

c

, so all those carries are true in the same 2 gate levels — no rippling.

Edge cases

What is

c_{1}

when

c_{0} = 0

and

g_{0} = 0

c_{1} = g_{0} + p_{0} c_{0} = 0

; with nothing generated and no incoming carry, there is simply nothing for

p_{0}

to propagate.

If every

p_{i} = 1

across an

n

-bit adder and

c_{0} = 1

, what is the top carry-out?

c_{n} = 1

— the incoming carry propagates through all positions via the

c_{0} \prod p_{j}

term, riding straight to the top.

Both inputs zero everywhere (

a_{i} = b_{i} = 0

for all

i

c_{0} = 1

: what happens?

Every

g_{i} = 0

and every

p_{i} = 0 \oplus 0 = 0

, so no bit propagates;

c_{1} = 0

immediately and the incoming carry dies at bit 0.

Can

g_{i} = 1

and

p_{i} = 1

hold simultaneously for the same bit?

No —

g_{i} = 1

needs

a_{i} = b_{i} = 1

, but then

p_{i} = 1 \oplus 1 = 0

; generate and propagate are mutually exclusive per bit.

What does

c_{i + 1}

reduce to at a position where

g_{i} = 1

c_{i + 1} = 1

regardless of

c_{i}

p_{i}

, since

g_{i}

appears as a lone OR term — a generated carry is unconditional.

For a 1-bit CLA (

n = 1

), does CLA differ from a full adder at all?

Not meaningfully — with one bit there is no carry chain to shortcut, so

c_{1} = g_{0} + p_{0} c_{0}

is exactly the ordinary full-adder carry.

Zero-width degenerate case: if the "adder" has no bits, what is the carry-out?

It is just

c_{0}

passed through unchanged — with no positions there is nothing to generate or propagate, so out equals in.

Recall One-line self-test before you leave

Cover the reveals and answer three: (1) Why doesn't $c_{5}$ have to wait for $c_{4}$ in a CLA? (2) Why can OR stand in for XOR in the carry but not the sum? (3) Why do we chunk into 4-bit blocks? Answers ::: (1) Unrolling expresses $c_{5}$ purely in $g, p, c_{0}$ . (2) OR/XOR differ only when $g_{i} = 1$ , which already forces the carry, but the sum reads $p_{i}$ literally. (3) To keep gate fan-in small (Propagation Delay & Fan-in).

Connections

Carry-Lookahead Adder — the parent note this bank tests.
Full Adder — source of $s_{i} = a_{i} \oplus b_{i} \oplus c_{i}$ that many traps abuse.
Ripple-Carry Adder — the "still waits serially" misconception's origin.
Boolean Algebra — justifies that unrolling changes nothing about the output.
Propagation Delay & Fan-in — the real reason wide CLA is impractical.
Prefix Adders (Kogge-Stone) — where the $lo g n$ depth claim comes from.
Carry-Save Adder — a different speed trick, easy to confuse with CLA.