Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof (resit) / 2

Use a four-state Moore machine. In state $A$ wait for an outer-sensor activation; $B$ combines the outer-only and both-sensors phases; $C$ records that the visitor has reached the inner-only phase; $I$ emits the one-cycle count pulse. Only $I$ has INC = 1.

The complete state transition table, with input order $x_1{x}_0$, isFor a normal entry the states are $A\to B\to B\to C\to I$; retreat after the first sensor instead gives $A\to B\to A$ with no pulse. Repeated samples at one sensor remain in the corresponding phase. State $I$ always exits on the next edge, so its output lasts exactly one clock period; an outer activation on that next edge goes directly to $B$, allowing the next visitor to start immediately.

This follows the question's single-visitor entry model and merges the two outer-active phases as its hint requests. Inputs are sampled synchronously; the table also specifies deterministic recovery for other sampled combinations. It is not a specification of a bidirectional occupancy counter for arbitrary overlapping entry and exit traffic.

Encode $(q_1{q}_0)$ by $A=00$, $B=01$, $C=11$, $I=10$, with reset to $A$. Two positive-edge-triggered D flip-flops store the state. Minimizing the Boolean functions from the complete table givesEquivalently, the minimal sum of products form of $D_1$ is ${\bar{x}}_0{q}_0{x}_1+{\bar{x}}_0{q}_0{q}_1$. The displayed factorization saves duplicated logic. The equations use only AND gates, OR gates and NOT gates; connect $D_j$ to the corresponding flip-flop data input and use one common clock.

For example, $C$ with input $00$ gives $(D_1{D}_0)=10$, entering the pulse state. In $I$, either $x_0=1$ gives $01$ or $x_0=0$ gives $00$, independently of $x_1$; the pulse cannot persist. The four states are distinguishable by their current output or future response to inputs $00$ and $10,00$, so two state bits are also necessary.

Address a read-only memory with the two state bits and two input bits. Each word stores the two next-state bits and INC, so a direct replacement for all the combinational logic is $16\times 3$ bits, or 48 bits. Program its 16 words from the state table, duplicating a state's output over all four input addresses. The two D flip-flops and clock remain outside the ROM.

If INC retains its separate two-state-bit decoder, only the next-state logic needs a $16\times 2$-bit ROM, plus that output gate. Storing output in a separate state-only ROM would use $4\times 1$ further bits. These factored options have a different boundary from replacing all the combinational logic with one ROM.