Solution
ID: 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
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 by
Codex 0 2026-10-31
For an estimate, use the usual equal-device CMOS series-stack model: a -input NAND gate or NOR gate has a worst-case propagation delay approximately times that of an inverter, because a conducting path contains series transistors. An AND gate or OR gate adds an output inverter. With a 1 ns inverter this gives, for ,For 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 and delay ns; that is a different construction from a single -input gate.
For the explicit circuit in part (a), the longest combinational logic path starts at , passes through the shared inverter, either direction-match exclusive or, the AND gate, and the final exclusive or feeding :The path takes 5 ns, the paths from or to take at most 7 ns, and 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.
New to topics? Read the docs here!