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

A disjunctive normal form, also called a sum of products, is an OR of AND terms, each made from Boolean literals such as $a$ or $\bar{a}$. For example,Here juxtaposition means logical conjunction, $+$ means logical disjunction, and a bar means negation. The expression need not be canonical: a term can omit variables, and need not name a single row of the truth table.

Implement each product by an AND gate and combine the products with an OR gate. Supply complemented inputs with NOT gates. ThusThis is the usual two-level combinational logic realization, counting complemented inputs as available. If NOT gates are counted, a complemented input can traverse three gates. The two-level depth statement also assumes sufficiently large gate fan-in: using only two-input logic gates requires trees for long products or sums. Constant, single-product and single-literal Boolean functions may need fewer levels, so the two-level construction is a general bound, not a claim that every expression requires exactly two layers.

A serial-in parallel-out shift register is a chain of digital registers driven by the same clock signal. At each active clock edge, the first stage captures the input and every later stage captures the preceding stage's old value. Its parallel outputs expose the successive delayed samples simultaneously.

Let $a_n$ be the current sample and, immediately before its sampling edge, let $h_1=a_{n-1},\dots ,h_{k-1}=a_{n-k+1}$. Feed these signals to combinational logic implementing $f$. ThenOnly $k-1$ stored history stages are needed if the current input is used directly. Alternatively, a $k$-stage shift register exposes all $k$ samples after the edge. A separate output digital register can capture the first arrangement at the edge, giving a fully sampled output. Initialize the history, or regard the first $k-1$ cycles as a filling interval.

Use two history D flip-flops. Write $a=a_n$, $b=a_{n-1}$ and $c=a_{n-2}$ for the signals just before the active clock edge; update the history by $b^{+}=a$ and $c^{+}=b$. Two or more of the three samples are one exactly when some pair are both one, so the majority function isThree two-input AND gates and one three-input OR gate implement this disjunctive normal form. If a registered output is wanted, feed the expression to the D input of another D flip-flop and capture it at the same edge as the history update. All right-hand sides use the pre-edge values, so no extra sample of delay is introduced.

The three terms are necessary in a minimal sum of products: the input triples $110$, $101$ and $011$ must each be covered, and a single product covering two of them would also cover a triple having only one one. Thus the minimum is three products, each with two Boolean literals.

Keep the two history D flip-flops and add an output D flip-flop with previous value $q=z_{n-1}$. Its next value $q^{+}=z_n$ is one if all three inputs are one, or if the output was one and at least one of the three inputs is one. In the latter case the samples are not all zero, so the previous one must be retained. This givesIf $abc=111$, the first product sets the output. If $abc=000$, every product vanishes and the output clears. For every mixed input triple, at least one of $aq,bq,cq$ equals $q$, so the output is retained. Feed this sum of products to the output D input, use $b^{+}=a,c^{+}=b$ for the history, and use asynchronous clear or an appropriate initialization to establish $q=0$.

Minimality can be seen directly from the truth table. At $q=0$, the only one-entry is $abc=111$, forcing the product $abc$ or a narrower term. At $q=1$, the triples $100$, $010$ and $001$ must all produce one; combining any two in one product would also admit $000$, which must produce zero. Thus three more products are needed. The displayed four products achieve the minimum; removing any Boolean literal from $abc,aq,bq,cq$ would include a zero-entry.

The unconstrained cases can be treated as don't-care conditions during Boolean function minimization. One particularly small, deliberately asymmetric choice isUse the same two history D flip-flops and one output D flip-flop, with this expression at the output D input. It requires two two-input AND gates and one OR gate.

To verify every required case, first set $q=0$. If zero occurs at least twice among $a,b,c$, then $ab=0$, so $q^{+}=0$ as required. If all three samples are one, then $ab=1$, so $q^{+}=1$. The remaining triples have exactly two ones and hence exactly one sample agreeing with the old zero; either output is allowed.

Now set $q=1$. If at least two samples are one, either $c=1$ or $a=b=1$, giving $q^{+}=1$. If all three samples are zero, both terms vanish, giving $q^{+}=0$. The remaining triples have exactly one one and are the allowed don't-care conditions. Thus the expression meets both requirements, including every constant-input triple.

For minimality, consider these required one-entries in $(a,b,c,q)$ order: $1110$, $1101$, $1011$ and $0111$ have no common literal. Therefore a product covering all four would be the constant one, which violates required zero-entries. Also no single-literal product is safe: each of $a,b,c,q$ is one at some required zero-entry, and each complemented literal is one at $0000$. Hence at least two products with at least two Boolean literals each are needed. The displayed expression attains two products and four literals.