Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Digital systems, linear algebra, introduction to formal proof / 4 / b / Solution

For an estimate, use the usual equal-device CMOS series-stack model: a $k$-input NAND gate or NOR gate has a worst-case propagation delay approximately $k$ times that of an inverter, because a conducting path contains $k$ series transistors. An AND gate or OR gate adds an output inverter. With a 1 ns inverter this gives, for $k\ge 2$,For $k=2$ it reproduces the stated 3 ns. This is a technology estimate under equal sizing and comparable loading, not a unique physical law inferable from a single measured delay. Actual propagation delay also depends on capacitance, fan-out and transistor sizing. If instead only the supplied two-input gates were allowed, a balanced tree would have worst-case depth $\lceil {\log }_{2}k\rceil$ and delay $3\lceil {\log }_{2}k\rceil$ ns; that is a different construction from a single $k$-input gate.

For the explicit circuit in part (a), the longest combinational logic path starts at $A$, passes through the shared inverter, either direction-match exclusive or, the AND gate, and the final exclusive or feeding $D_2$:The path $A\to D_1$ takes 5 ns, the paths from $B0$ or $B1$ to $D_2$ take at most 7 ns, and $B0\to D_0$ takes 1 ns. Both direction-match exclusive or gates act in parallel; their delays are not added together. The 8 ns excludes clock-to-Q delay, setup time, hold time and clock-distribution effects, because the question asks only for the combinational logic delay.