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

Use three positive-edge-triggered D flip-flops, all driven by the same clock signal $CLK$. Write the current binary representation as $B2B1B0$, with $B0$ the least significant bit. The next state is the current value plus one when $A=1$ and minus one when $A=0$, in each case modulo eight. A bit toggles under exclusive or with a one.

For upward counting, $B1$ toggles when $B0=1$, while $B2$ toggles when $B1=B0=1$, the respective carry conditions. For downward counting the corresponding borrow conditions are $B0=0$ and $B1=B0=0$. Define the shared inverted direction $N=\neg A$ and the two direction-match signalsEach $T_i$ is one exactly when $Bi=A$: it equals $Bi$ for upward counting and $\neg Bi$ for downward counting. Thus the Boolean functions for the three D inputs areImplement this with two NOT gates for $N,D_0$, four two-input exclusive or gates for $T_0,T_1,D_1,D_2$, and one two-input AND gate. Connect $D_i$ to the D flip-flop whose output is $Bi$; feed the three outputs back into the indicated gates. All three flip-flops capture simultaneously, so each equation uses the old state.

For completeness, the state transition table is

Every three-bit state is valid. A reset may initialize the binary counter to zero if required; counting itself needs no extra state. The direction input must meet the setup time and hold time requirements at the active clock edge.

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.