Combinational Circuits

Question 1 (10)

(a) Truth table SOP: $S = \overline{A}\,\overline{B}\,C_{in} + \overline{A}B\overline{C_{in}} + A\overline{B}\,\overline{C_{in}} + ABC_{in} = A \oplus B \oplus C_{in}$ (2 — 1 for SOP, 1 for XOR reduction) $C_{out} = AB + BC_{in} + AC_{in}$ (2 — minimal 3-term SOP; the majority function)

(b) Critical path: $C_0$ enters FA0. Carry ripples FA0→FA1→FA2→FA3, each stage adding carry delay (2). After the final carry into FA3 is stable, the last sum bit needs sum delay (3).

• Carry through 4 stages: but sum $S_3$ depends on carry-in to stage 3, i.e. $C_3$, which is produced by 3 carry propagations from $C_0$.
• Delay $= 3 \times (\text{carry delay}) + (\text{sum delay}) = 3\times 2 + 3 = 9$ gate delays. (4) (Accept: $(n-1)\times 2 + 3 = 9$ for $n=4$.)

(c) Delay grows linearly $O(n)$ with bit-width because each carry must ripple sequentially → slow for wide adders. Alternative: carry-lookahead adder (also accept carry-select/carry-save). (2)

Question 2 (12)

(a) $G_i = A_i B_i$ (carry generated), $P_i = A_i \oplus B_i$ (or $A_i + B_i$ for propagate; either accepted). (2)

(b) Unrolling $C_{i+1}=G_i+P_iC_i$:

• $C_1 = G_0 + P_0 C_0$
• $C_2 = G_1 + P_1 C_1 = G_1 + P_1 G_0 + P_1 P_0 C_0$
• $C_3 = G_2 + P_2 C_2 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$ (5 — 1 per correct term expansion)

(c) Each carry $C_i$ is expressed as a two-level SOP (AND-OR) directly from $G,P,C_0$, so every carry is produced in 2 gate levels regardless of $n$ — constant depth. Practical cost: fan-in and number of gates (product terms) grows with $n$, limiting full lookahead to small groups (hence hierarchical/block CLA). (3)

(d) $A=1011$, $B=0110$ → bits (LSB first): $A_0=1,A_1=1,A_2=0,A_3=1$; $B_0=0,B_1=1,B_2=1,B_3=0$.

• $G_0=A_0B_0=1\cdot0=0$, $P_0=1\oplus0=1$
• $G_1=1\cdot1=1$, $P_1=1\oplus1=0$
• $G_2=0\cdot1=0$, $P_2=0\oplus1=1$ $C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0 = 0 + (1)(1) + (1)(0)(0) + (1)(0)(1)(0) = 1$. (2)

Question 3 (10)

(a) $Y = \overline{S_1}\,\overline{S_0}D_0 + \overline{S_1}S_0 D_1 + S_1\overline{S_0}D_2 + S_1 S_0 D_3$. (2)

(b) Select $=A B$ (A=MSB=$S_1$, B=$S_0$). Group minterms by $AB$, residual on $C$:

• $AB=00$ (m0,m1): F=1 only at m1 (C=1) → $D_0 = C$
• $AB=01$ (m2,m3): F=1 at m2 (C=0) → $D_1 = \overline{C}$
• $AB=10$ (m4,m5): F=1 at m4 (C=0) → $D_2 = \overline{C}$
• $AB=11$ (m6,m7): F=1 at m7 (C=1) → $D_3 = C$

So $D_0=C,\ D_1=\overline C,\ D_2=\overline C,\ D_3=C$. (6 — mark ~1.5 each, or per correct data input)

(c) An $n$-select MUX routes one of $2^n$ data inputs per select combination; by placing the truth-table output value at each data input, any function of the $n$ select variables is realized (it directly implements the truth table). (2)

Question 4 (10)

(a) $A>B: A\overline{B}$; $A=B: \overline{A\oplus B} = \overline A\,\overline B + AB$; $A<B: \overline A B$. (3)

(b) Equality: $E = (A_1 \odot B_1)(A_0 \odot B_0)$ where $\odot$ is XNOR, i.e. $E=(\overline{A_1\oplus B_1})(\overline{A_0\oplus B_0}).$ (2) Greater-than: $A>B = A_1\overline{B_1} + (\overline{A_1\oplus B_1})\,A_0\overline{B_0}.$ (compare MSB first; if MSBs equal, compare LSB.) (2)

(c) Priority encoder (X=don't care), $D_3$ highest:

$Y_1 = D_3 + D_2$; ($Y_0 = D_3 + \overline{D_2}D_1$, $V = D_3+D_2+D_1+D_0$). (3 — table 2, $Y_1$ 1)

Question 5 (10)

(a) A static-1 hazard: output should stay at logic 1 across a single-variable input change but momentarily glitches to 0. Cause: two paths of differing propagation delay converge; a change in one variable switches the covering product term off before the other turns on, leaving a gap. (3)

(b) $F=\overline A C + A B$. On K-map, the "1" cells $\overline A C$ (A=0,C=1) and $AB$ (A=1,B=1) are adjacent when $B=1,C=1$. Transition $A:0\to1$ with $B=C=1$: leaving cover of $\overline A C$, entering cover of $AB$ — no common product term spans the boundary → static-1 hazard. (4)

(c) Add consensus term $BC$: $F = \overline A C + AB + BC$. This term stays high throughout the $A$ transition when $B=C=1$, covering the gap. General rule: a two-level SOP is hazard-free for single-input changes iff every pair of adjacent 1-minterms is covered by a common product term (include all consensus/redundant primes needed to overlap covers). (3)

Question 6 (8)

(a) Partial products: $A_0B_0,\ A_1B_0,\ A_0B_1,\ A_1B_1$.

• $P_0 = A_0 B_0$
• $P_1 = A_1 B_0 \oplus A_0 B_1$, carry $c_1 = A_1B_0\cdot A_0B_1$
• $P_2 = (A_1 B_1) \oplus c_1$, carry $c_2 = A_1B_1\cdot c_1$
• $P_3 = c_2$ (HA/FA description acceptable.) (5)

(b) For $A-B$ in two's complement: XOR each $B_i$ with a control line $M=1$ to invert ($B_i \oplus 1 = \overline{B_i}$), forming one's complement; set carry-in $C_0 = 1$ to add 1, completing two's complement. Result $A + \overline B + 1 = A - B$. So per bit: FA computes $A_i + (B_i\oplus M) + \text{carry}$, with $C_0=M=1$ for subtract. (3)

[
  {"claim":"RCA n=4 delay = 3*carry+sum = 9","code":"carry=2; summ=3; n=4; result=((n-1)*carry+summ)==9"},
  {"claim":"C3 for A=1011,B=0110,C0=0 equals 1","code":"A=[1,1,0,1]; B=[0,1,1,0]; C0=0; G=[A[i]&B[i] for i in range(4)]; P=[A[i]^B[i] for i in range(4)]; C3=G[2] | (P[2]&G[1]) | (P[2]&P[1]&G[0]) | (P[2]&P[1]&P[0]&C0); result=C3==1"},
  {"claim":"MUX data inputs realize F=sum m(1,2,4,7)","code":"from sympy import symbols; C=symbols('C'); vals={}; mins={1,2,4,7}; ok=True; D={}; \nfor AB in range(4):\n    a=(AB>>1)&1; b=AB&1; d0=1 if (AB*2+0) in mins else 0; d1=1 if (AB*2+1) in mins else 0; D[AB]=(d0,d1)\nexp={0:(0,1),1:(1,0),2:(1,0),3:(0,1)}; result=(D==exp)"},
  {"claim":"2x2 multiplier: A=3,B=3 gives product 9","code":"A=[1,1]; B=[1,1]; P0=A[0]&B[0]; s1=(A[1]&B[0])^(A[0]&B[1]); c1=(A[1]&B[0])&(A[0]&B[1]); P1=s1; P2=(A[1]&B[1])^c1; c2=(A[1]&B[1])&c1; P3=c2; val=P0+2*P1+4*P2+8*P3; result=val==9"}
]