Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 10

A D flip-flop stores one bit. At its specified active clock edge, it samples $D$ and, after its clock-to-Q delay, makes $Q$ equal to that sampled value. Between active clock edges it retains the stored value. The input must meet the setup and hold time requirements around the sampling edge; a level-sensitive latch would have different behavior.

For a finite-state sequential circuit, encode the present state in a bank of D flip-flops. Feed their outputs $q$ and the external inputs $u$ to combinational logic computing the next-state function $F(q,u)$, and connect those outputs to the flip-flop $D$ inputs. A common clock signal then performs the simultaneous updateOutput combinational logic computes $H(q)$ for a Moore machine or $H(q,u)$ for a Mealy machine. Since any finite next-state and output table is a Boolean function, it has a Boolean circuit implementation. Initialization specifies the starting state, and unused state encodings require either a recovery rule or an initialization assumption. The clock period must accommodate propagation through the D flip-flops and intervening combinational logic before the next sampling edge.

A particularly transparent design uses six D flip-flops in a one-hot encoding. Let $Q_i=1$ mean that face $i$ is displayed. Initialize $Q_1=1$ and $Q_2=\cdots =Q_6=0$, and wire the next-state inputs as a ring:All six D flip-flops share the same active clock edge. Each pulse moves the single stored $1$ to the next position, giving the state-transition diagram cycle $1\to 2\to 3\to 4\to 5\to 6\to 1$. The representation invariant “exactly one $Q_i$ is high” holds after initialization and is preserved by rotation. Six D flip-flops are more than the three-bit theoretical minimum, but their simple wiring gives a complete implementation without requiring that minimum.

Decode the seven lamps by their positions, with $T,M,B$ denoting top, middle and bottom, and $L,R$ denoting left and right. Let $L_C$ be the center lamp. In the original figure, face 2 uses top-left and bottom-right, while face 3 uses top-right and bottom-left plus center; the two diagonals must therefore have different controls.^[ref] The required OR gate decoder isFor example, only the center is high in state $Q_1$, the first diagonal is high in state $Q_2$, and in state $Q_6$ both outer columns are high while the center is low. This verifies all six layouts directly.

To implement the switch behavior, use a rapid common clock signal and a sampled enable $S$, high while the switch is pressed. Each next-state input is then selected between its advancing value and its own stored value:One multiplexer per D flip-flop implements that selection. While enabled the electronic dice advances; otherwise every D flip-flop reloads its own value and the display holds. The enable supplied to this synchronous design must be stable at sampling edges. A reset or preset facility must establish the specified one-hot initial state: an all-zero ring does not start itself.

With a rapid clock signal, uncertainty in human release timing makes the final face practically unpredictable. The sequential circuit itself is deterministic; this observation alone is not a proof that its six outcomes have equal probabilities.