Lesson 6

The next task is to construct a counter that increments a number at each clock cycle. Counters constitute a fundamental component of a processor, as they govern the execution of instructions.

Problem. Construct a 16-bit counter. The two input bits are \(\texttt{st}\) and \(\texttt{cl}\). The label \(\texttt{x}\) is a hardcoded 16-bit input, so you may use it directly in gate lines. The output of your circuit must be a single 16-bit label.

The counter starts with output \(0\). Your circuit will be tested on many sequences of inputs \(\texttt{(st,x,cl)}\). The behavior is as follows:

• while \(\texttt{cl}\)=0, the next value is prepared;


• if \(\texttt{st}\)=1, then the next value is \(\texttt{x}\);


• if \(\texttt{st}\)=0, then the next value is the current output plus \(1\), modulo \(2^{16}\);


• when \(\texttt{cl}\) changes from \(1\) to \(0\), the prepared next value becomes the current output.

You may use only the following functions: \[\begin{aligned}\operatorname{NAND}(a,b) &= \neg(a \land b), \\ \operatorname{INV}(a) &= \neg a, \\ \operatorname{REGISTER}(st,x,cl) &= \text{the current output of a 16-bit register}, \\ \operatorname{INC}_{16}(x) &= x + 1 \pmod{2^{16}}, \\ \operatorname{SELECT}_{16}(s,d_1,d_0) &= \begin{cases} d_0, & s=0, \\ d_1, & s=1, \end{cases} \\ 0() &= 0.\end{aligned}\] For example, a line \(\texttt{y st x cl REGISTER}\) means that \(\texttt{y}\) is a new 16-bit label equal to the current output of a register with inputs \(\texttt{st}\), \(\texttt{x}\), and \(\texttt{cl}\).

The authors' solution uses \(5\) gates.