ALU Design and Multiplication: short notes (Computer Organization & Architecture)

Introduction

The arithmetic logic unit (ALU) is the combinational block of the datapath that performs integer arithmetic (add, subtract, compare), bitwise logic (AND, OR, XOR, NOT) and shifts on two operands, under the control of a function-select input, and reports the outcome in condition flags. Multiplication and division are built on top of the ALU's adder as sequences of add or subtract steps and shifts.

GATE asks you to set the flags for a given operation, to tell carry from overflow, to evaluate arithmetic against logical shifts, to trace Booth's algorithm step by step, and to count the additions and subtractions a multiplier needs. Gate-level adder design, including ripple-carry and carry-lookahead delay, belongs to Adders and Subtractors; overflow rules for two's complement are in Fixed-Point Arithmetic and Overflow.

Prerequisites

Adders and Subtractors: full adders, ripple-carry and carry-lookahead adders, and subtraction as $A + \overline{B} + 1$ .
Fixed-Point Arithmetic and Overflow: two's-complement ranges and when a sum overflows.

Core concepts

The ALU as a block

Port	Width	Meaning
A, B	$n$ bits each	Operands
F (function select)	$\lceil \lg(\text{number of functions}) \rceil$ bits	Chooses the operation
$c_{in}$	1	Carry in (used for subtraction and multi-word arithmetic)
Result	$n$ bits	Output
Flags	Z, N, C, V	Zero, Negative (sign), Carry, Overflow

A common construction is a bit slice: each bit position has an AND gate, an OR gate and a full adder, and a multiplexer driven by F picks one of them. Subtraction inverts B (an XOR with a control line) and sets $c_{in} = 1$ . Shifts are performed by a separate shifter (often a barrel shifter) in front of or beside the ALU.

Condition flags

Flag	Set when	Meaning
Z	every result bit is 0	Result is zero
N	result bit $n-1$ is 1	Result is negative if read as signed
C	carry out of bit $n-1$ is 1	Unsigned overflow in addition; in subtraction $A - B$ by $A + \overline{B} + 1$ , $C = 0$ means a borrow ( $A < B$ unsigned)
V	carry into bit $n-1$ $\ne$ carry out of bit $n-1$	Signed (two's-complement) overflow

C and V are independent: an addition can set either, both or neither. The hardware computes both; the program decides whether the operands were signed or unsigned.

Shifts

Shift	Vacated bits filled with	Arithmetic meaning
Logical left	0	Multiply by 2 (signed or unsigned, if no overflow)
Logical right	0	Unsigned divide by 2, rounding down
Arithmetic right	Copy of the sign bit	Signed divide by 2, rounding toward $-\infty$
Rotate	Bits shifted out at the other end	No arithmetic meaning

Multiplication

Unsigned shift-and-add. For $n$ -bit operands, examine the multiplier bits from the least significant: if the bit is 1, add the multiplicand into the upper half of the partial product; then shift the partial product right. After $n$ steps the $2n$ -bit product is complete. The number of additions equals the number of 1s in the multiplier.

Booth's algorithm (signed, two's complement). Booth's algorithm treats an interior run of 1s from bit $i$ through $j$ as $2^{j+1}-2^i$ : subtract at its start and add after its end. A run reaching the sign bit contributes $-2^i$ , so it needs only the opening subtraction. Each step looks at the pair $(Q_0, Q_{-1})$ , the current low multiplier bit and the bit shifted out last:

$Q_0$	$Q_{-1}$	Action, then arithmetic shift right of A, Q, $Q_{-1}$
0	0	none (inside a run of 0s)
1	1	none (inside a run of 1s)
1	0	$A \leftarrow A - M$ (start of a run of 1s)
0	1	$A \leftarrow A + M$ (end of a run of 1s)

Equivalently, bit $i$ of the multiplier is recoded as $Q_{i-1} - Q_i \in \{-1, 0, +1\}$ , with $Q_{-1} = 0$ .

Bit-pair recoding (radix-4 Booth). Grouping the Booth digits two at a time, the pair at positions $i + 1$ and $i$ (for even $i$ ) has weight $2^i$ and value $-2Q_{i+1} + Q_i + Q_{i-1}$ , read from the three bits $Q_{i+1} Q_i Q_{i-1}$ :

$Q_{i+1} Q_i Q_{i-1}$	000	001	010	011	100	101	110	111
Multiple of $M$	0	$+1$	$+1$	$+2$	$-2$	$-1$	$-1$	0

Every digit is in $\{-2, -1, 0, +1, +2\}$ , and $\pm 2M$ is just $M$ shifted left, so an $n$ -bit multiplier ( $n$ even) needs at most $n/2$ partial products instead of $n$ . The alternating multiplier that is Booth's worst case becomes cheap.

How it works

ALU block with operands, function select, carry in, result and flags — Figure 1. An $n$ -bit ALU: operands A and B, a function-select input F and a carry in enter; the result and the flags Z, N, C and V leave; inside, a multiplexer driven by F picks the AND, OR or adder output of each bit slice.

Booth multiplication trace of 7 times minus 3 in 4 bits — Figure 2. Booth trace of $7 \times (-3)$ with 4-bit registers: four steps of subtract, add, subtract and no operation, each followed by an arithmetic right shift, end with A:Q = 1110 1011, which is $-21$ .

Algorithms and pseudocode

Text

BOOTH(M, Q, n)                    // M multiplicand, Q multiplier, n-bit two's complement
  A <- 0;  Q_1 <- 0               // Q_1 is the extra bit to the right of Q
  repeat n times
      if (Q[0], Q_1) = (1, 0)  then A <- A - M
      if (Q[0], Q_1) = (0, 1)  then A <- A + M
      arithmetic shift right the combined register A : Q : Q_1 by one bit
  return A : Q                    // 2n-bit product

Text

RESTORING-DIVIDE(N, D, n)         // unsigned N / D, n-bit quotient
  A <- 0;  Q <- N
  repeat n times
      shift A : Q left by one bit
      A <- A - D
      if A < 0 then  A <- A + D;  Q[0] <- 0     // restore
      else           Q[0] <- 1
  return (quotient Q, remainder A)

Mathematical explanation

Overflow. For two's-complement addition of $n$ -bit numbers, overflow occurs exactly when both operands have the same sign and the result has the other sign, which is the same as $V = c_{n} \oplus c_{n-1}$ , where $c_{n-1}$ is the carry into the sign bit and $c_n$ the carry out of it.

Why Booth works. With $Q_{-1} = 0$ , the value of a two's-complement multiplier satisfies

Q = -Q_{n-1}2^{n-1} + \sum_{i=0}^{n-2} Q_i 2^i = \sum_{i=0}^{n-1} (Q_{i-1} - Q_i)\,2^{i},

because the sum telescopes. So adding $(Q_{i-1} - Q_i)\,M\,2^i$ for every $i$ gives $M \times Q$ , and the sign bit needs no special step.

Operation counts. Booth performs one add or subtract per position where $Q_i\ne Q_{i-1}$ . An alternating multiplier can require $n$ operations. Each interior run of ones needs two operations; a run reaching the sign bit needs only its opening subtraction, so a run costs at most two.

Arithmetic right shift. For a two's-complement value $x$ , shifting right arithmetically by $k$ gives $\lfloor x / 2^k \rfloor$ .

Worked examples

Example 1: flags of 4-bit additions

Operation (4 bits)	Result	Z	N	C	V	Reading
0111 + 0001	1000	0	1	0	1	$7 + 1 = 8$ overflows the signed range $-8$ to 7
1111 + 0001	0000	1	0	1	0	Unsigned $15 + 1$ overflows; signed $-1 + 1 = 0$ is correct
1000 + 1000	0000	1	0	1	1	$-8 + (-8)$ overflows both ways
0011 + 0100	0111	0	0	0	0	$3 + 4 = 7$ , fine

Example 2: subtraction and the borrow

$0011 - 0101$ is computed as $0011 + 1010 + 1 = 1110$ with carry out 0. Unsigned: $C = 0$ signals a borrow, since $3 < 5$ . Signed: $1110 = -2$ , correct, $V = 0$ . Compare instructions use exactly this subtraction and keep only the flags.

Example 3: Booth trace (Figure 2)

$M = 7 = 0111$ , $Q = -3 = 1101$ , $-M = 1001$ , 4-bit registers.

Step	$Q_0 Q_{-1}$	Action	A after action	A, Q, $Q_{-1}$ after shift
Start				0000, 1101, 0
1	10	$A - M$	1001	1100, 1110, 1
2	01	$A + M$	0011	0001, 1111, 0
3	10	$A - M$	1010	1101, 0111, 1
4	11	none	1101	1110, 1011, 1

Product A:Q $= 1110\,1011 = -21$ . The recoded multiplier is $(0, -1, +1, -1)$ from bit 3 down to bit 0: $-4 + 2 - 1 = -3$ .

Example 4: counting Booth operations

For 8-bit multipliers:

$0101\,0101$ : every adjacent pair differs, so 8 operations (4 subtractions, 4 additions). Shift-and-add would need 4 additions; Booth is worse here.
$0011\,1100$ : a single run of 1s from bit 2 to bit 5, so 2 operations (subtract at bit 2, add at bit 6), against 4 additions for shift-and-add.
$1111\,1111 = -1$ : only bit 0 starts a run, so 1 operation (a subtraction): the product is $-M$ .

Example 5: shifts of a negative number

$x = 1011 = -5$ (4 bits). Arithmetic right shift: $1101 = -3 = \lfloor -5/2 \rfloor$ . Logical right shift: $0101 = 5$ , which is $\lfloor 11/2 \rfloor$ for the unsigned reading 11. Left shift: $0110$ with a lost sign bit, so $-10$ overflows the 4-bit range.

Related material. Unsigned $7 \div 3$ with 4-bit registers: the quotient is $0010$ and the remainder $0001$ . Each of the 4 steps subtracts; the three steps that produce a 0 quotient bit must restore. Non-restoring division removes the restore additions by adding $D$ in the next step instead.

Example 7: bit-pair recoding

For $Q = -3 = 1101$ (4 bits, $Q_{-1} = 0$ ): the low pair reads $Q_1 Q_0 Q_{-1} = 010$ , digit $+1$ ; the high pair reads $Q_3 Q_2 Q_1 = 110$ , digit $-1$ with weight 4. So $Q = -1 \times 4 + 1 = -3$ , and $7 \times (-3) = -28 + 7 = -21$ from 2 partial products instead of the 4 steps of Figure 2.

For the 8-bit $0101\,0101 = 85$ , every pair reads $010$ , giving digits $+1, +1, +1, +1$ at weights 64, 16, 4, 1: 4 additions, against 8 operations for plain Booth (Example 4).

Important properties and observations

The ALU is combinational. The iterative multiplication and division algorithms described here are sequential, driven by the control unit over $n$ steps; other hardware implementations may be combinational or pipelined.
C reports unsigned overflow, V signed overflow; $V = c_n \oplus c_{n-1}$ .
In subtraction by two's complement, C = 0 means a borrow.
Arithmetic right shift rounds toward $-\infty$ ; it is not the same as C integer division for negative odd numbers.
Booth handles signed operands directly and saves work on runs of 1s, but alternating bits make it worst.
Booth needs an arithmetic, not a logical, shift so that negative partial products keep their sign.
Booth with an $n$ -bit A register fails for one multiplicand, $M = -2^{n-1}$ , because $-M$ is not representable in $n$ bits; widening A (and M) by one bit removes the problem.
Common misconceptions.
- "Carry out means overflow." Only for unsigned numbers.
- "Booth always uses fewer additions." It does not for alternating multipliers.
- " $Q_{-1}$ starts as the sign bit." It starts as 0.

GATE examination perspective

FLAGS. Add in binary, record $c_{n-1}$ and $c_n$ , then read Z, N, C and V.
BOOTH TRACE. Keep columns for A, Q and $Q_{-1}$ ; act on $(Q_0, Q_{-1})$ , then shift arithmetically.
BOOTH RECODING. Digit $i = Q_{i-1} - Q_i$ ; count non-zero digits for the operation count.
BIT-PAIR RECODING. Read overlapping triples $Q_{i+1} Q_i Q_{i-1}$ for even $i$ ; digit $= -2Q_{i+1} + Q_i + Q_{i-1}$ , at most $\lceil n/2\rceil$ partial products, sign-extending for odd $n$ .
SHIFTS. Arithmetic right shift copies the sign; logical inserts 0.
FUNCTION SELECT. Bits $= \lceil \lg(\text{functions}) \rceil$ .
ADDER DELAY. Rebuild from the gate model given; the derivations are in the Digital Logic note.

Summary

Adders and Subtractors: prerequisite. The adder inside the ALU and its delay.
Fixed-Point Arithmetic and Overflow: prerequisite. Ranges and overflow rules.
CPU Datapath and Instruction Cycle: dependent. Where the ALU sits and how its operands arrive.
Signed Number Representation: related. Two's complement, which Booth's algorithm relies on.

ALU Design and Multiplication

Introduction

Prerequisites

Core concepts

The ALU as a block

Condition flags

Shifts

Multiplication

How it works

Algorithms and pseudocode

Mathematical explanation

Worked examples

Example 1: flags of 4-bit additions

Example 2: subtraction and the borrow

Example 3: Booth trace (Figure 2)

Example 4: counting Booth operations

Example 5: shifts of a negative number

Example 7: bit-pair recoding

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

The ALU as a block

Condition flags

Shifts

Multiplication

How it works

Algorithms and pseudocode

Mathematical explanation

Worked examples

Example 1: flags of 4-bit additions

Example 2: subtraction and the borrow

Example 3: Booth trace (Figure 2)

Example 4: counting Booth operations

Example 5: shifts of a negative number

Example 6: restoring division (Related material)

Example 7: bit-pair recoding

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps