Exercises — ALU design fundamentals

The multiplexer (Multiplexer). Every operation (add, subtract, AND, OR, …) computes in parallel and all results arrive at the MUX at once. The select lines $S$ act like an address: for $k$ select bits the MUX chooses one of $2^k$ inputs to route to $F$. Nothing is "computed" by the MUX — it only steers an already-finished result. (See the amber MUX box in the figure.)

Combinational means the output depends only on the current inputs $A,B,S$ — there is no stored past. Because there is nothing to "remember", there is nothing to update on a clock edge, so the ALU needs no clock. State (registers) lives outside the ALU in the Datapath and Control Unit.

• $Z$ — result is exactly zero (all result bits are 0).
• $C=c_4$ — unsigned carry out of the MSB.
• $N=F_3$ — the sign bit; $N=1$ means negative in two's complement.
• $V=c_4\oplus c_3$ — signed overflow (the sign bit got corrupted).

Mnemonic from the parent note: Zebras Carry New Vans.

$S_{sub}=0$ leaves $B$ intact and $c_0=0$ — a pure add. Column carries (right to left): $c_0=0$, $c_1=0$, $c_2=0$, $c_3=0$, $c_4=0$. $0110+0001=0111(7),c_4=0.$ Flags: $Z=0$ (result nonzero), $C=c_4=0$, $N=F_3=0$, $V=c_4\oplus c_3=0\oplus 0=0$. Signed reading: $6+1=7$, inside $[-8,7]$, so no overflow — consistent with $V=0$. ✓

$1000+1111=10111.$ Keep the low 4 bits: $F=0111(7)$, and $c_4=1$. Column carries: $c_0=0$, $c_1=0$, $c_2=0$, $c_3=0$, $c_4=1$ → so $c_3=0$, $c_4=1$. Flags: $Z=0$, $C=c_4=1$, $N=F_3=0$, $V=c_4\oplus c_3=1\oplus 0=1$. Interpretation: signed we wanted $-8+(-1)=-9$, which is below $-8$, so it overflowed → $V=1$ ✓. The $C=1$ is the unsigned carry and is irrelevant when we read these as signed numbers.

Subtract means invert $B$ and set $c_0=1$ (Two's Complement): $\overline{B}=1001$, $c_0=1$. $0100+1001+1=01110.$ $F=1110$, $c_4=0$. As signed, $1110=-2$ — correct, since $4-6=-2$. Flags: $N=F_3=1$ (negative ✓), $Z=0$, $C=c_4=0$. Borrow: in a two's-complement subtractor, borrow $=\overline{C}$. Here $C=0$ so $\overline{C}=1$ — a borrow did occur, exactly right because $4<6$.

$0101+0100=1001.$ Carries: $c_0=0,c_1=0,c_2=0,c_3=1,c_4=0$. So $c_3=1$, $c_4=0$. $F=1001$; flags $C=c_4=0$, $V=c_4\oplus c_3=0\oplus 1=1$, $N=1$, $Z=0$. Why they disagree: unsigned $5+4=9$ fits in 4 bits (max $15$) → no carry out → $C=0$. But signed $5+4=9$ exceeds $+7$, so the sign bit flipped ($F=1001=-7$) → $V=1$. Same bits, two interpretations, two verdicts.

Carry rule per bit: $c_{i+1}=A_i{B}_i+c_i(A_i\oplus B_i)$.

• Bit 0: $A_0{B}_0=1\cdot 1=1\Rightarrow c_1=1$ (generate).
• Bit 1: $A_1{B}_1=1\cdot 0=0$, but $A_1\oplus B_1=1$ and $c_1=1\Rightarrow c_2=1$ (propagate).
• Bit 2: same pattern, $c_3=1$ (propagate).
• Bit 3: $A_3\oplus B_3=1$, $c_3=1\Rightarrow c_4$... wait $A_3{B}_3=0$, so $c_4=0\cdot ?+c_3\cdot (0\oplus 0)=0$.

Correcting bit 3: $A_3=0,B_3=0$, so $A_3\oplus B_3=0$ → $c_4=0$. The carry propagates $c_1\to c_2\to c_3$ then dies. Result: $0111+0001=1000$. Weakness exposed: the carry had to travel through three stages one after another — the delay of a Ripple Carry Adder grows with bit-width, which is why we invent the Carry Lookahead Adder.

$Z=\overline{F_7+F_6+\cdots +F_0}.$ With all $F_i=0$, the inner OR is $0$, so $Z=\overline{0}=1$ → zero detected ✓. Why NOR: $Z$ must be 1 only when every bit is 0. OR is 1 if any bit is 1; negating it gives 1 iff no bit is 1 — precisely the zero condition. A single OR-tree + inverter scales cleanly to any width.

$\text{NOT }A$ is a logic op, so route it through the logic unit and add it as one more MUX input; the select lines choose it. The logic unit produces $\overline{A}$ by inverting each bit in parallel (no carries involved). Verify on $A=1010$: $\overline{1010}=0101$. Flags: $Z=0$, $N=F_3=0$; $C$ and $V$ are meaningless for logic ops and ignored. Cost of the feature: one inverter bank + one MUX input — exactly the "add op = add circuit + one MUX line" principle from the parent note.

Two bits are equal iff $A_i\oplus B_i=0$; equality is $\overline{A_i\oplus B_i}$ (XNOR). For a 4-bit compare, use the subtract path: compute $A-B$ and read the $Z$ flag. If $A=B$ then $A-B=0$, so $Z=1$ — the ALU already NORs all result bits, so equality comes for free from subtraction. This is exactly how a CPU's CMP instruction works (see Status Flags and Condition Codes).

The signed less-than rule is $A<B⟺N\oplus V=1$ (sign of $A-B$, corrected for overflow). Compute $A-B$: $\overline{B}=1010$, $c_0=1$: $0011+1010+1=01110$, so $F=1110$, $c_4=0$. Carries: $c_3=0$, $c_4=0$ → $V=c_4\oplus c_3=0$. $N=F_3=1$. Then $N\oplus V=1\oplus 0=1$ → $A<B$ is TRUE. Sanity: $3<5$ ✓.

$\overline{B}=0111$, $c_0=1$: $1000+0111+1=10000$. $F=0000$, $c_4=1$. Carries: $c_3=1$ (the $0111+1$ ripple), $c_4=1$. Flags: $Z=1$ (result is zero!), $N=F_3=0$, $C=c_4=1$, $V=c_4\oplus c_3=1\oplus 1=0$. Surprise 1: $Z=1$ because $-8-(-8)=0$ — the inputs being negative is irrelevant; $Z$ only watches the result bits. Surprise 2: $C=1$ means no borrow ($\overline{C}=0$), correct since $A-B=0\ge 0$. And $V=0$ confirms no signed overflow — a fully consistent, clean subtraction.

$\overline{B}=0111$, $c_0=1$: $0000+0111+1=1000$. $F=1000$, $c_4=0$. Carries: $c_3=1$, $c_4=0$ → $V=0\oplus 1=1$. $N=F_3=1$, so the machine claims $0-(-8)=-8$. Deep reason: $+8$ has no 4-bit two's-complement representation (range is $[-8,7]$). Negating $-8$ should give $+8$ but can't fit, so overflow ($V=1$) fires — this is the famous "$-\text{INT\_MIN}$ overflows" case. The flag is the hardware honestly telling you the answer left the representable range.

$\overline{B}=1100$, $c_0=1$: $1110+1100+1=11011$. $F=1011$, $c_4=1$. Carries: $c_3=1$, $c_4=1$ → $V=1\oplus 1=0$. Flags: $N=F_3=1$, $Z=0$, $C=c_4=1$ (no borrow), $V=0$. Signed value of $F=1011$ is $-5$; check $-2-3=-5$ ✓ (in range, so $V=0$ as expected). Signed compare: $N\oplus V=1\oplus 0=1\Rightarrow A<B$, i.e. $-2<3$ — TRUE ✓. Every flag is mutually consistent: correct value, no overflow, borrow-free per $C$.

• Signed-less-than test? ::: $N\oplus V=1$
• Borrow flag in a two's-complement subtractor? ::: $\overline{C}$ (borrow when $C=0$)
• Which flag caught $5+4$ overflowing signed 4-bit? ::: $V$ (while $C=0$)
• Why does negating $-8$ overflow in 4 bits? ::: $+8\notin [-8,7]$, no representation exists