ALU & control unit formulas

One bit-slice of any adder. Both outputs need all three inputs to be stable.

An adder/subtractor passes each $B_i$ through an XOR gate with a mode line $M$ and sets $C_0=M$: $M=0$ adds and $M=1$ subtracts. $V=1$ signals signed (2's complement) overflow. For unsigned numbers, $C_n=1$ after an addition means the result does not fit in $n$ bits. After a subtraction done as $A+\overline{B}+1$, $C_n=1$ means $A\ge B$ (no borrow).

$t_c$ is one FA's carry delay and $t_s$ is its sum delay, measured from when its carry-in is stable (its $A_i$, $B_i$ are already stable). If one figure $t_{FA}$ is given for both outputs, both times equal $n{t}_{FA}$. The delay grows linearly with $n$.

$G_i=1$: bit $i$ produces a carry whatever $C_i$ is. $P_i=1$: bit $i$ passes an incoming carry on to $C_{i+1}$. Some texts use $P_i=A_i+B_i$. The carry equations below still hold with that choice, but the sum can then no longer be formed as $P_i\oplus C_i$.

Each expanded carry is a two-level AND-OR expression in the $G$'s, $P$'s and $C_0$, so every carry is ready 2 gate delays after the $P$, $G$ signals, whatever its position. The cost is fan-in: $C_i$ has $i+1$ product terms and its largest AND gate has $i+1$ inputs.

This is independent of $n$ only because fan-in is assumed unlimited. If a question counts an XOR as more than one gate delay, substitute its figure in the first and last terms.

Fan-in limits force wide adders to be built from $k$-bit CLA blocks. Each block's $G^{\ast }$, $P^{\ast }$ take 2 gate delays after the bit-level $P_i$, $G_i$. A second-level look-ahead unit applies the same carry equations to the block signals, giving the carry into every block at once instead of rippling between blocks. With a fixed block size $k$, the number of look-ahead levels grows as ${\log }_{k}n$, so the delay grows as $O(\log n)$.

$W$ is the number of words (microinstructions) and $w$ is the width of one microinstruction. When a question gives the number of address bits $a$ of the CAR instead, $W=2^a$. Convert to bytes by dividing by 8, and to KB with K = $2^{10}$.

$W$ is the number of control-memory words that must be addressable. $c$ is the number of branch choices the field must select among, counting 'unconditional' (or 'no branch') as a choice when the question includes it.

Group $j$ holds $k_j$ mutually exclusive signals. The $+1$ is the code for 'none of this group active'. Drop it (use $\lceil {\log }_2{k}_j\rceil$) only if the question says exactly one signal of the group is always active, or says no-operation need not be encoded.