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

Use three D flip-flops whose stored bits $A,B,C$ represent $4A+2B+C$. Initialize them to $000$. The Moore machine's output is this stored binary representation, and its state transition table is:

Treat the two unused state encodings $110,111$ as don't-care conditions when minimizing the sum of products. With juxtaposition for AND, $+$ for OR and a bar for NOT, one minimal choice isFor $D_A$, the required ones at $011$ and $100$ cannot share one valid implicant: their differing bits would force inclusion of required zeros. Pair $011$ with the unused $111$ to get $BC$, and $100$ with unused $110$ to get $A\overline{C}$. Neither term can lose a Boolean literal without covering a required zero.

For $D_B$, state $001$ is isolated from every other required one and from the unused states by required zeros, so it forces the three-Boolean literal term $\overline{A}\overline{B}C$. State $010$ pairs with unused $110$ to give $B\overline{C}$. Finally $D_C=\overline{C}$ is a single Boolean literal. Thus the three expressions are minimal sum of products expressions under the stated unused-state convention. In fact these choices also recover from $110\to 111\to 100$, so initialization into an unused state eventually joins the intended modulo-six counter cycle.