Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 3

The lower NMOS transistor network conducts through either the $a,b$ series branch or the $b,c$ series branch. Complete the upper PMOS transistor network by the series-parallel dual: between $V_{dd}$ and an intermediate node put $p(a)$ and $p(b)$ in parallel, and between that node and $z$ put $p(b)$ and $p(c)$ in parallel. There are four upper transistors, complementing the four lower transistors. Use the usual body ties to the corresponding supply rails. Each $p(x)$ denotes a PMOS transistor controlled by input $x$, so it conducts when $x=0$.

The upper conducting condition is $(\neg a\vee \neg b)\wedge (\neg b\vee \neg c)$, exactly the complement of $ab\vee bc$. Thus for every stable input the output has a conducting path to exactly one rail in the ideal static CMOS model. The left panel below specifies the added network independently of the source drawing; join its lower terminal to the existing output.

The pull-down Boolean function is $ab\vee bc=b(a\vee c)$. A conducting pull-down makes $z=0$, soIn particular, if $b=0$ the output is always high; if $b=1$, the output is high precisely when both other inputs are low. These cases give the truth table without confusing a network's conducting condition with the output voltage.

Factor the common input before constructing the networks. Use an NMOS transistor controlled by $b$ in series with parallel NMOS transistors controlled by $a$ and $c$. Its conducting condition remains $b(a\vee c)$. The complementary upper network is a PMOS transistor controlled by $b$ in parallel with a series chain of PMOS transistors controlled by $a$ and $c$; its conducting condition is $\neg b\vee \neg a\neg c$.

This is the right panel in part (a). It uses three lower plus three upper transistors, six in total instead of eight, and needs no separate inverter or complemented external input. The complementary CMOS network duality ensures the same static Boolean function and complementary rail connections.

Use a synchronous sequential circuit with four Moore machine states. $R$ is ready, $P$ is the one-cycle pulse state, $D$ is disabled with no qualifying final zero, and $Z$ is disabled after one sampled zero. Reset into $R$, so an initial sampled high generates a pulse immediately. The complete transition/output table is:

A particularly small implementation uses two D flip-flops with the next-state equationsBoth D flip-flops share the clock; their outputs feed the displayed logic gates. The output depends only on the stored state, not combinationally on the external input. At each edge, evaluate the right-hand sides using the old state and the sampled input, then update both flip-flops together. The resulting $z$ applies throughout the following clock period.

From $R$, a high enters $P$. The next edge always leaves $P$, so the pulse lasts exactly one period. In the disabled states, a high leads to $D$ and erases progress towards rearming. A zero enters $Z$, and a second successive zero enters $R$. A later high can then enter $P$. This proves both the two-zero requirement and the startup exception. For example, sampled inputs $1,1,0,1,0,0,1,0,0,1$ yield outputs $1,0,0,0,0,0,1,0,0,1$.

The construction is a synchronous pulse detector with two-zero rearming. Assume $a$ meets setup/hold requirements at the sampling edges. A genuinely asynchronous input would first require synchronization, with its associated latency; that is separate from this sampled-input specification.