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

Let $a_k$ be the input sampled at clock edge $k$. The desired registered output after that edge is $z_k=a_{k-2}{a}_{k-1}(1-a_k)$. Only the last two high samples matter: a longer high run still has two high samples immediately before its first low sample.

A direct synchronous 110 detector uses three D flip-flops, holding $q_1,q_2,z$, with a common clock and initial state zero. Use the following next-state equations, all evaluated from the old state and the input at the active clock edge:After an edge, $q_1$ records the latest sample and $q_2$ records whether the latest two samples were high. The final equation consequently produces the required pulse from the preceding two-high state and the new low sample. A synchronous reset sets all three state bits to zero. The output is the stored z flip-flop value, so it changes only after clock edges; exposing the unregistered expression $q_2\wedge \neg a$ would let input transitions between edges alter the output.

An equivalent finite-state machine has states R (no current high run), H (one high), HH (at least two highs), and P (the pulse state). Its output is one only in P:

The pulse cannot last two cycles: after the low input that creates it, $q_2$ is zero, so the next output is zero regardless of the next input. The detector rearms without a global stop and handles repeated patterns indefinitely. The three-flip-flop construction is deliberately direct; minimum storage was not required.