L11: Unsigned Arithmetic

Where we learn once again to add two numbers.

Objective
Develop a basic understanding of addition and multiplication of unsigned Boolean values.

Additional Materials & Formats
Check Box for the most up-to-date versions of this lecture’s materials.

Before the Lecture

Required Textbook Reading:

• 3.2 (Addition of Unsigned Numbers)

Optional Supplemental Instruction:

• How To Add and Subtract Binary Numbers – The Organic Chemistry Tutor on YouTube

Representation

An $n$-bit unsigned integer is an element of the set $\mathbb{Z}_{2^n} = {0,1,\dots,2^n-1}$.

A binary representation is a bit-vector $b_{n-1}b_{n-2}\dots b_0$ with $b_i\in{0,1}$. The numeric value is $$\operatorname{val}(b_{n-1}\dots b_0)=\sum_{i=0}^{n-1} b_i2^i.$$

Addition

Let’s start by looking at the mechanics behind decimal addition and then generalize to any base and to binary.

Decimal addition (column-wise)

• Addition proceeds from the least-significant column to the most-significant column, propagating carries.
• For base $10$, given digits $a,b\in{0,\dots,9}$ and incoming carry $c\in{0,1}$, $$ s ;=; (a+b+c) \bmod 10,\qquad c_{\text{out}} ;=; \left\lfloor\frac{a+b+c}{10}\right\rfloor. $$
• Example: $47+58$.
  • units: $7+8=15\Rightarrow s_0=5,;c_1=1$
  • tens: $4+5+1=10\Rightarrow s_1=0,;c_2=1$
  • result: $105$.

General base $b$

• For base $b$ and digit values $d_i,e_i\in{0,\dots,b-1}$ with carry $c_i\in{0,1}$, $$ s_i=(d_i+e_i+c_i)\bmod b,\qquad c_{i+1}=\left\lfloor\frac{d_i+e_i+c_i}{b}\right\rfloor. $$
• The only difference between bases is the modulus and the carry threshold.

Binary addition (base $2$)

• For bits $x,y\in{0,1}$ and incoming carry $c\in{0,1}$, $$ s = (x+y+c)\bmod 2 = x\oplus y\oplus c, $$ $$ c_{\text{out}} = \left\lfloor\frac{x+y+c}{2}\right\rfloor. $$
• Boolean forms of the carry:
  • Majority form: $c_{\text{out}}=1$ iff at least two of $x,y,c$ are 1, so $$ c_{\text{out}} = (x\land y)\lor(x\land c)\lor(y\land c). $$
  • Equivalent compact form using propagate/generate or XOR: $$ c_{\text{out}} = (x\land y);\lor;\big(c\land(x\oplus y)\big). $$
  • Using generate $g=x\land y$ and propagate $p=x\oplus y$, $$ c_{\text{out}} = g \lor (p\land c). $$

Ripple example (4-bit)

• Add $11_{10}=1011_2$ and $7_{10}=0111_2$:
  • bit0: $1+1=2\Rightarrow s_0=0,;c_1=1$
  • bit1: $1+1+1=3\Rightarrow s_1=1,;c_2=1$
  • bit2: $0+1+1=2\Rightarrow s_2=0,;c_3=1$
  • bit3: $1+0+1=2\Rightarrow s_3=0,;c_4=1$
  • low 4 bits = $0010_2$ (2), final carry $c_4=1$ → true sum $18$, low-4-bit result $2$.
• Interpretation: for $n$-bit unsigned addition, the final carry-out $c_n=1$ exactly when the true integer sum exceeds $2^n-1$. Thus unsigned overflow ⇔ final carry-out $=1$.

Takeaway

Decimal and binary addition use the same carry-propagation algorithm; for binary the sum bit is an XOR and the carry is the majority (or equivalently $g\lor(p\land c)$), and the final carry-out indicates unsigned overflow.

Adder Circuits

Half adder (HA)

A half adder takes two input bits a and b and produces a sum bit s and a carry-out bit $c_\text{out}$. The Boolean functions are $s = a \oplus b$ and $c_\text{out} = a \land b$. This can be implemented with one XOR gate (for s) and one AND gate (for $c_\text{out}$).

Truth table for the half adder:

Composing HAs into a full adder (FA)

A full adder has inputs x, y and carry-in $c_{\text{in}}$, and outputs the sum s and carry-out $c_{\text{out}}$. One common implementation composes two half adders and an OR gate:

1. HA1 on (x,y) produces intermediate propagate $p = x \oplus y$ and generate $g = x \land y$.
2. HA2 on (p,$c_{\text{in}}$) produces the final sum $s = p \oplus c_{\text{in}}$ and a carry $h = p \land c_{\text{in}}$.
3. The final carry is $c_{\text{out}} = g \lor h$.

Compact Boolean form:
$s = x \oplus y \oplus c_{\text{in}}, ~ c_{\text{out}} = (x \land y) \lor \big((x \oplus y)\land c_{\text{in}} \big)$

Truth table for the full adder:

See Figures 3.2 & 3.3 in the textbook.

Discussion & Practice
As a class, let’s draw the adder circuits and practice some Boolean addition.

Basic Multiplication

A naive option for arbitrary multipliers is repeated addition (A added to an accumulator k times). That is functionally simple but requires k additions (high latency) or k adder instances (high area).

Shift-and-add decomposition for constants:

• For small constant factors, rewrite the constant as a sum/difference of powers of two and use shifts plus a small number of add/sub operations. Shifts are wiring (negligible cost) so the only real cost is the adders.
• Example: A * 3 = (A « 1) + A. This uses one shifter (wiring) and one adder, much smaller than instantiating multiple full adders or a multi-operand adder tree.

Example (A * 3, revisited)

• Naive: add A + A + A (two adders if done combinationally, or repeated adds).
• Shift-and-add: compute (A « 1) + A — one shifter (wiring) + one adder, minimal area and simple wiring, same correct result (e.g., A=0101₂ → 1111₂).
• Serial reuse: use one adder and two cycles (accumulate A then add shifted A) to save area at the cost of latency.