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 / 3

Use a three-sample run detector. Just before clock edge $t$, let two stored bits $p$ and $q$ hold the input values at edges $t-1$ and $t-2$. Initialise both to zero. With input $a_t$, definePrimes denote the next stored state, with all assignments simultaneous at the clock edge. The output is the logical conjunction of the present input and its two preceding samples. By induction on clock edges, the stated interpretation of $p,q$ is maintained, proving the required behaviour. Two bits of state suffice.

Store two bits: the output $z$, initially zero, and an armed bit $e$, initially one. Define the synchronous sequential circuit byHere $\oplus$ is exclusive or, and the input restriction $c\wedge d=0$ excludes conflicting commands. The output is the current stored $z$.

When armed, a sampled $c=1$ toggles $z$ and clears $e$. Further $c$ samples leave the output unchanged. A sampled $d=1$ sets $e=1$ without changing $z$, allowing a later $c$ to toggle it again. The same clock edge cannot both rearm and trigger because $c,d$ are never simultaneously high. Thus the first $c$ toggles from zero to one, and subsequent toggles each require a new $d$ followed by a later $c$.

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, putThese 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)$, isEvery 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.

Four state bits are necessary and sufficient. For each output value, distinguish three armed situations, remembering a trailing high run of length $0,1,2$, and three disarmed situations, remembering a trailing low run of length $0,1,2$. Thus a direct minimal behavioural description hasAll twelve situations are reachable. Different output values are immediately distinguishable. Within an armed group, a suitable number of high samples distinguishes the three run lengths by when the next toggle occurs. Within a disarmed group, a suitable number of low samples followed by three highs distinguishes the three rearming distances. An armed situation and a disarmed situation of the same output value are distinguished by an all-high continuation: the armed one eventually toggles and the disarmed one does not. Hence these twelve situations cannot be merged in a finite-state machine implementing the specification.

The shared-history design in (c) uses four bits, meeting this lower bound. Its sixteen encoded states have some behaviourally equivalent histories, so its encoding need not use only twelve combinations. Building two separate copies of (a) plus the two-bit module (b) would use six state-bearing elements; sharing the input history saves two.