= Solution
Let $a_k$ be the input sampled at clock edge $k$. The desired registered output after that edge is \b[$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:
$$
q_1^+=a,\qquad q_2^+=q_1\land a,\qquad z^+=q_2\land\neg a.
$$
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\land\neg a$ would let input transitions between edges alter the output.
\Image[/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-clocked-pulses.png]
{title=Original sampled-input and registered-output trace for a <synchronous 110 detector>}
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`:
|| State
|| Next on 0
|| Next on 1
|| Output
| `R`
| `R`
| `H`
| 0
| `H`
| `R`
| `HH`
| 0
| `HH`
| `P`
| `HH`
| 0
| `P`
| `R`
| `H`
| 1
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.
Back to article page
