Carry lookahead and width-safe Booth multiplication

Two ways to reorganize arithmetic

Carry lookahead reorganizes the Boolean dependence of addition. Booth recoding reorganizes a signed multiplier's bit contributions. Neither changes the exact mathematical answer. Both need explicit representation, width and hardware assumptions before a speed claim is meaningful.

Prerequisites: full adders, two's complement, integer multiplication and combinational timing. These are selected implementations within the official syllabus's broad circuit/arithmetic areas; the syllabus does not name these two algorithms individually. We teach a four-bit carry expansion and radix-two Booth algorithm, not an optimized commercial multiplier or a complete controller.

Derive carry lookahead rather than memorize it

Number bits from 0 at the least significant end. Define p_i=a_i XOR b_i and g_i=a_i AND b_i. Then s_i=p_i XOR c_i and c_(i+1)=g_i OR (p_i AND c_i). Here “+” in Boolean equations means OR and juxtaposition means AND.

Substitution eliminates the serial carry variables:

c_1=g_0+p_0c_0; c_2=g_1+p_1g_0+p_1p_0c_0; c_3=g_2+p_2g_1+p_2p_1g_0+p_2p_1p_0c_0; c_4=g_3+p_3g_2+p_3p_2g_1+p_3p_2p_1g_0+p_3p_2p_1p_0c_0.

Every term says either a lower bit generated a carry and intervening positions propagated it, or the external carry propagated through the whole prefix. Define group P=p_3p_2p_1p_0 and G=g_3+p_3g_2+p_3p_2g_1+p_3p_2p_1g_0. Then c_4=G+Pc_0. Groups can themselves be combined by the same generate/propagate reasoning.

Worked example 1: a=1011,b=0110,c_0=0. Written high bit first, p=1101 and g=0010. Bit 1 generates a carry, bits 2 and 3 propagate it, so G=1,P=0,c_4=1. Carries c_1,c_2,c_3,c_4 are 0,1,1,1. The sum bits are 0001, hence the full unsigned result is 10001=17. The fact that group P=0 does not imply carry-out zero; G may generate one.

Some designs instead define carry-propagate as a_i OR b_i, which also works in the carry recurrence. Do not substitute that OR-defined p into s_i=p_i XOR c_i: sum still needs a_i XOR b_i. This lesson consistently uses XOR-defined p for both formulas.

Logic depth depends on the gate model

If p/g have already settled, and arbitrary fan-in AND/OR gates each cost one time unit, the expanded c_4 has a two-level AND-OR bound, whereas four ripple carry stages have an eight-unit bound with one AND plus one OR each. This comparison excludes p/g generation and final sum XOR. It is a deliberately idealized model.

A five-input AND is not automatically available at the same delay as a two-input AND. Bounded fan-in requires decomposition or hierarchical lookahead; loading, wiring and physical implementation affect delay. The equations remove a serial dependency, but do not prove a width-independent physical delay or a universal fixed speedup.

Booth recoding from adjacent multiplier bits

Let the signed n-bit multiplier have bits q_(n−1)…q_0 and define q_−1=0. Its signed value equals Σ(q_(i−1)−q_i)2^i for i=0…n−1. Expanding the sum leaves positive weights for bits 0…n−2 and negative weight −2^(n−1) for the sign bit, proving the identity.

Thus each adjacent pair (q_i,q_(i−1)) requests: 00 or 11, no contribution; 01, add M·2^i; 10, subtract M·2^i. Example: signed 0011=3 has pairs 10,11,01,00 from low to high, so 3=−1+4. For M=−5, product=−(−5)+4(−5)=−15. Runs of ones can reduce nonzero partial terms, but alternating bits need not; no speed advantage is guaranteed for every multiplier.

A width-safe register version

Inputs M and Q are n-bit two's-complement values, n≥2. Sign-extend M to n+1 bits and keep it constant. Use an n+1-bit accumulator A initially zero, the original n-bit Q register, and a one-bit q_prev initially zero. At each of exactly n iterations:

1. Inspect old (Q_0,q_prev). For 01 set A←A+M; for 10 set A←A−M; for 00/11 hold A. Arithmetic is performed in the n+1-bit accumulator.
2. After that operation, arithmetic-right-shift the entire concatenated (A,Q,q_prev) register by one. Its total width is 2n+2 bits. Copy A's sign into the new top bit; old A_0 enters Q's top, and old Q_0 enters q_prev.
3. Do not shift the three registers independently. The sign bit and the two boundary transfers are part of one combined shift.

After n iterations, discard q_prev. The remaining A,Q is a 2n+1-bit sign extension of the exact 2n-bit product; discard its redundant top sign bit if a 2n-bit answer is requested. The extra A/M bit permits +2^(n−1) when negating a most-negative n-bit multiplicand. An unmodified n-bit accumulator version can fail at that boundary.

Worked example 2: n=4,M=−5, so M=11011 in five bits, Q initially 0011. The table shows state after each combined shift.

Iteration	Old pair	Operation before shift	A after shift	Q after shift	q_prev
1	10	A−M	00010	1001	1
2	11	hold	00001	0100	1
3	01	A+M	11110	0010	0
4	00	hold	11111	0001	0

A,Q is 111110001; drop the redundant top sign bit to obtain 11110001=−15 in eight bits. Independently, −5×3=−15. The same width-safe algorithm handles four-bit M=−8,Q=−1 and returns eight-bit 00001000=+8.

Key points and common mistakes

Derive each carry term with the correct bit order. Distinguish generated carry from group propagation. Never mix OR-defined and XOR-defined propagate in sum equations. State fan-in assumptions before counting levels. In Booth, pair 10 subtracts and 01 adds; inspect before shifting, preserve sign, and keep cross-register transfers. Check the most-negative multiplicand rather than excluding it from tests. A correct recoding identity is not by itself a cycle-count or physical-speed claim.

Original practice

These six single-correct MCQs are original learning questions, not previous-year questions. Choose exactly one option.

C01. Using XOR-defined p and AND-defined g, which expression is c_2?

A. g_1+p_1g_0+p_1p_0c_0 B. g_1+p_0g_0+p_1c_0 C. p_1+p_0+c_0 D. g_0+p_0c_0

Answer: A

A is correct: substitute c_1=g_0+p_0c_0 into c_2=g_1+p_1c_1.

B is incorrect: the intervening bit-1 propagation factors are missing or misplaced.

C is incorrect: propagation alone does not generate a carry.

D is incorrect: this is c_1, not c_2.

C02. For four-bit a=1011,b=0110,c_0=0, what are group (G,P,c_4)?

A. (0,1,0) B. (0,0,0) C. (1,0,1) D. (1,1,1)

Answer: C

A is incorrect: bit 1 generates a carry, while not all bits propagate.

B is incorrect: generated carry reaches the output through bits 2 and 3.

C is correct: g_1=1,p_2=p_3=1 gives G=1, and p_1=0 gives P=0.

D is incorrect: group P requires every p_i=1, but p_1=0.

C03. In radix-two Booth recoding, what does old pair (Q_0,q_prev)=10 request before shifting?

A. A←A+M B. A←A−M C. Hold A D. Logical-right-shift M only

Answer: B

A is incorrect: addition corresponds to pair 01.

B is correct: q_prev−Q_0=0−1=−1, hence subtract M.

C is incorrect: hold corresponds to 00 or 11.

D is incorrect: M remains constant and the combined state is shifted after the operation.

C04. Why is A widened to n+1 bits in the stated Booth algorithm?

A. To change the signed product into an unsigned sum B. To eliminate every addition C. Because Q must have 2n bits D. To accommodate negation of the most-negative n-bit multiplicand without same-width overflow

Answer: D

A is incorrect: the algorithm still computes a signed product.

B is incorrect: some pairs still require addition or subtraction.

C is incorrect: Q remains n bits in this version.

D is correct: +2^(n−1) fits n+1 signed bits, not n signed bits.

C05. For n=4,M=−5,Q initially 0011, what is the final 8-bit product?

A. 00001111 B. 11110001 C. 11111011 D. 00010001

Answer: B

A is incorrect: this encodes +15, not −15.

B is correct: −5×3=−15 and 256−15=241=11110001.

C is incorrect: this is −5, the multiplicand alone.

D is incorrect: this is +17, unrelated to the signed product.

C06. When is the stated two-level c_4 versus eight-level ripple comparison valid?

A. For every physical gate library regardless of fan-in B. Only when no carry exists C. Under the declared settled-p/g and unit-delay arbitrary-fan-in AND/OR model D. It proves all n-bit adders have constant physical delay

Answer: C

A is incorrect: gate fan-in and implementation affect actual delay.

B is incorrect: the comparison concerns carry computation under the model.

C is correct: those assumptions justify the logic-level count, excluding p/g and sum generation.

D is incorrect: a simplified level model is not a universal physical scaling law.

Scope and sources

This is one bounded Digital Logic lesson, not complete GATE CS coverage. The official syllabus establishes relevance only; the derivations, examples and practice are original. Technical references were used to check representation and circuit conventions, not to reproduce their exercises.

• Official GATE 2027 CS syllabus Section 2
• University of Wisconsin carry-lookahead supplement
• MIT signed Booth multiplier and width caveat

Sources checked 14 October 2026.