Combinational Circuits

Question 1

(a) (6 marks) Recurrence: $c_{i+1} = g_i + p_i c_i$. Substitute $c_i = g_{i-1} + p_{i-1}c_{i-1}$:

$c_{i+1} = g_i + p_i(g_{i-1} + p_{i-1}c_{i-1}) = g_i + p_i g_{i-1} + p_i p_{i-1} c_{i-1}.$

Continuing recursively down to $c_0$:

$c_{i+1} = g_i + \sum_{j=0}^{i-1}\left(\prod_{k=j+1}^{i}p_k\right)g_j + \left(\prod_{k=0}^{i}p_k\right)c_0.$

Marks: recurrence stated (1); first substitution (2); recursive continuation (2); closed form (1).

(b) (5 marks)

• $g_i,p_i$ generated in parallel: $1\tau$ (AND / XOR).
• Each carry is a 2-level AND-OR expression → $2\tau$.
• All carries produced simultaneously: total $= 1\tau + 2\tau = 3\tau$, independent of $n$ ⇒ $O(1)$ carry delay. (2 marks)
• Ripple-carry: each stage's carry waits for previous; carry chain $= 2\tau$ per bit ⇒ $\approx 2n\,\tau = O(n)$. (2 marks)
• Conclusion: CLA is $O(1)$ vs ripple $O(n)$ (constant vs linear). (1 mark)

(c) (5 marks)

• $g,p$ generation: $1\tau$.
• Within block 0 carries ready after $+2\tau$; block carry-out logic $2\tau$ ⇒ block0 cout at $1+2=3\tau$.
• Blocks ripple: each subsequent block adds $2\tau$ (block carry-out). For 4 blocks the carry into block 3 arrives at $1 + 2\times3 = 7\tau$; then intra-block carries $2\tau$ then sum XOR $1\tau$.
• Worst-case sum bit (MSB): $1\tau (g,p) + 2\tau\times3 (\text{ripple through 3 block-carries}) + 2\tau (\text{intra-block carry}) + 1\tau (\text{sum XOR}) = 10\tau$.

Accept $10\tau$. Marks: g/p (1); block carry model (1); ripple 3 blocks = 6τ (2); +intra+sum = 10τ (1).

(d) (6 marks)

function carry_lookahead(a, b, cin):
    n = length(a)
    g = array(n); p = array(n)
    for i in 0..n-1:
        g[i] = a[i] AND b[i]
        p[i] = a[i] XOR b[i]
    c = array(n+1)
    c[0] = cin
    for i in 0..n-1:               # closed-form, no dependence chain
        term = g[i]
        prodP = 1
        for j from i down to 0:    # build products of p's
            prodP = prodP AND p[j]... 
        # explicit closed form:
        c[i+1] = g[i]
        acc = 1
        for j from i-1 down to 0:
            acc = acc AND p[j+1]           # product p_{j+1..i}
            c[i+1] = c[i+1] OR (acc AND g[j])
        acc = acc AND p[0]
        c[i+1] = c[i+1] OR (acc AND c[0])
    sum = array(n)
    for i in 0..n-1:
        sum[i] = p[i] XOR c[i]
    return (sum, c[n])

Marks: g/p generation (1); parallel carry via closed form / no ripple dependency (3); sum = p XOR c (1); return cout (1).

Question 2

(a) (8 marks) A $2^n{:}1$ MUX with select $= (x_1\ldots x_n)$ outputs $Y=\sum_{k}(m_k \cdot D_k)$ where $m_k$ is the minterm selecting data input $D_k$. Setting each $D_k$ to the desired functional value ($0$ or $1$) reproduces the truth table exactly ⇒ any $n$-var function realizable (Shannon expansion over all $n$ vars). (3)

For $2^{n-1}{:}1$: apply Shannon expansion on first $n-1$ variables; each residue $f|_{x_1..x_{n-1}}$ is a function of the single remaining variable $x_n$, hence equals one of $\{0,1,x_n,\overline{x_n}\}$. Feed that residue to the corresponding data input. (3)

Example $f(A,B,C)=\Sigma m(1,2,4,7)$, select $=A,B$; residues in $C$:

So $D_0=C,\ D_1=\overline C,\ D_2=\overline C,\ D_3=C$. (2)

(b) (6 marks) Logarithmic barrel shifter for 4 bits needs $\log_2 4 = 2$ stages. Stage 1 rotates by $2^0=1$ (controlled by $s_0$); stage 2 rotates by $2^1=2$ (controlled by $s_1$). Each stage uses one $2{:}1$ MUX per bit = 4 MUXes/stage ⇒ 2 stages, 8 MUXes total. Each MUX selects between the un-rotated bit and the rotated-in bit. (stages 2 —2 marks; count 8 —2 marks; justification of $2^k$ per stage —2 marks).

(c) (6 marks) Input 1011, rotate-left-by-3 ⇒ $s_1 s_0 = 11$.

• Stage 1 (rotate-left by 1, $s_0=1$): 1011 → 0111. (rotate left: MSB wraps to LSB: 0111) (3)
• Stage 2 (rotate-left by 2, $s_1=1$): 0111 → 1101. (2)
• Result 1101. Check: rotate-left-by-3 of 1011 = 1101. ✓ (1)

Question 3

(a) (6 marks) Truth table of $F=AB+\overline A C$:

Static-1 hazard on transition $A:0\to1$ with $B=1,C=1$ (i.e. $ABC=011\to111$, both output $=1$). The term $\overline A C$ covers the $011$ side, $AB$ covers the $111$ side; no single product covers both, so during the switch a momentary $0$ glitch can occur. (transition ID 3; explanation 3).

(b) (6 marks) Consensus of $AB$ and $\overline A C$ (on variable $A$) is $BC$. Hazard-free: $F = AB + \overline A C + BC$.

Redundancy proof: $BC = BC(A+\overline A) = ABC + \overline A BC$. But $ABC \subseteq AB$ and $\overline A BC \subseteq \overline A C$, so $AB+\overline A C+BC = AB+\overline A C$. Function unchanged. (consensus term 2; hazard-free expr 1; algebraic redundancy proof 3).

(c) (6 marks) Forward: If every pair of adjacent 1-minterms is covered by a common product term, then during a single-variable transition between two 1-cells, that common product term stays at 1 throughout (its literals don't include the changing variable), holding $F=1$ ⇒ no static-1 hazard. (3)

Reverse (contrapositive): If some adjacent 1-pair has no common product term, the two minterms are covered only by distinct terms whose activating literals differ in the changing variable; there is a delay window where the falling term is already 0 and the rising term not yet 1, producing a momentary 0 ⇒ static-1 hazard exists. Hence hazard-freedom ⇔ every adjacent 1-pair shares a covering prime implicant. (3)

[
{"claim":"16-bit block CLA worst-case delay = 10 tau","code":"gp=1; ripple=2*3; intra=2; sumx=1; result=(gp+ripple+intra+sumx)==10"},
{"claim":"Flat CLA carry delay is 3 tau constant","code":"result=(1+2)==3"},
{"claim":"f=Sigma m(1,2,4,7) residues for MUX select A,B are C,~C,~C,C","code":"m={0:0,1:1,2:1,3:0,4:1,5:0,6:0,7:1}; A,B,C=symbols('A B C'); rows=[( (m[0],m[1]),'C'),((m[2],m[3]),'~C'),((m[4],m[5]),'~C'),((m[6],m[7]),'C')]; ok=[(r[0]==(0,1) and r[1]=='C') or (r[0]==(1,0) and r[1]=='~C') for r in rows]; result=all(ok)"},
{"claim":"rotate-left-by-3 of 1011 = 1101","code":"v=0b1011; n=4; r=((v<<3)|(v>>(n-3)))&0b1111; result=r==0b1101"},
{"claim":"AB+~A C+BC == AB+~A C (consensus redundant)","code":"A,B,C=symbols('A B C'); from sympy.logic.boolalg import simplify_logic; lhs=simplify_logic((A&B)|(~A&C)|(B&C)); rhs=simplify_logic((A&B)|(~A&C)); result=lhs==rhs"}
]