Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Digital systems, linear algebra, introduction to formal proof / 1

Use a Moore machine whose state records the longest suffix of the received stream that is also a prefix of the target word. The transitions areThe last row preserves overlap: after recognition, one more one leaves suffix $11$, giving $S_2$. Initialize to $S_0$ and update the state on each active clock edge; the output after that edge reports whether the word has just ended. This is a prefix-suffix sequence recognizer.

Five distinct states require three D flip-flops, since $2^2<5\le 2^3$. Choose the state encoding $S_i$ equal to the three-bit binary expansion of $i$. Write the present bits as $A,B,C$, in decreasing significance. The state transition table isThe dashes are don't-care conditions for minimizing the logic. They do not prescribe what the actual circuit will do in those unused states; part (e) determines that from the chosen equations.

With the encoding in part (b), $y=A$ is a valid Moore machine output equation. Among reachable states, $A=1$ exactly at $S_4$. This uses unused output-table entries as don't-care conditions. If one instead wants the output to be zero in every unused state, use $y=A\bar{B}\bar{C}$; that extra requirement does not change any output from a valid state.

Use four-variable Karnaugh maps with rows $AB=00,01,11,10$ and columns $Cx=00,01,11,10$, both in Gray code order. A dash denotes an unused present state. The maps for the three next-state bits areFor $A^{+}$, join its sole one with the dash directly below it. For $B^{+}$, use the four-cell groups $Ax$ and $B\bar{C}$, and the two-cell group $\bar{B}Cx$; the last group wraps between the top and bottom rows. For $C^{+}$, join the one at row $01$, column $00$ to the dash below it; the one at row $00$, column $01$ is isolated. These prime implicants giveHere products mean Boolean conjunction and sums mean Boolean disjunction. The $D$ inputs are the desired next-state bits of the three D flip-flops. The equations are independent of the unused values except for the explicitly chosen Karnaugh map groups.

Evaluate the implemented equations from part (d), rather than the don't-care entries of the original table:States $101$ and $110$ enter a valid state after one edge. State $111$ does so after one edge for zero, or moves to $110$ and enters a valid state on the following edge for either next input. Thus every unused state recovers within at most two clock edges, independently of the incoming bits. The machine cannot become trapped there. This self-starting finite-state machine property does not guarantee meaningful recognizer output during recovery; initialization to $S_0$ still establishes the intended stream history.