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

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.