= Solution
Share the input-history <bits> of (a) between a high-run detector and a low-run detector. With $p,q$ the two preceding input samples, put
$$
c=a\land p\land q,\qquad d=\neg a\land\neg p\land\neg q.
$$
These detector outputs are mutually exclusive. Feed them into (b). An explicit four-<bit> <synchronous sequential circuit>, with initial state $(p,q,e,z)=(0,0,1,0)$, is
$$
\boxed{p'=a,\quad q'=p,\quad
e'=d\lor(e\land\neg c),\quad
z'=z\mathbin{\oplus}(e\land c).}
$$
Every right-hand side uses the old state and the current input. In particular, the run detectors' combinational outputs are sampled by the toggle module at that same edge; there is no extra pipeline stage.
The first three consecutive high samples make $c=1$ at the third edge, toggling $z$ and clearing $e$. Continuing high input cannot toggle it again. Only three consecutive low samples can make $d=1$ and rearm it; interrupted low runs do not suffice. After rearming, a new three-sample high run produces the next toggle. This proves the <debounced toggle switch> behaviour, including rejection of short high and low disturbances.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2023/digital-systems-linear-algebra-and-introduction-to-formal-proof-debounced-toggle.png]
{title=The <debounced toggle switch> rejects interrupted runs, toggles on the third consecutive high sample, and rearms only on the third consecutive low sample; stored outputs are shown just after each <clock edge>}
Back to article page
