Lesson 5

You have reached the final challenge. Upon successful completion of this task, you will have constructed a fully functional programmable microprocessor using only NAND gates!

Problem. Construct the computer. This task has no explicit inputs. The ROM contents are hardcoded in the checker and may vary from test to test. The outputs of your circuit must be four 16-bit labels, in the order \(\texttt{PC A D *A}\).

The computer is built from the following parts:

• a control unit,


• a combined memory unit,


• a ROM unit,


• a counter that stores the current program counter \(\texttt{PC}\),


• and a clock unit.

The ROM contains four 16-bit words. It is addressed by the lowest two bits of \(\texttt{PC}\). The selected ROM word is the instruction \(\texttt{I}\) given to the control unit.

The clock output is a periodic bit sequence \[0,1,0,1,0,1,\dotsc\] starting from \(0\).

At each step:

• the control unit reads \(\texttt{I}\), \(\texttt{A}\), \(\texttt{D}\), and \(\texttt{*A}\);


• the memory unit uses the control outputs \(\texttt{R}\), \(\texttt{a}\), \(\texttt{d}\), \(\texttt{*a}\) and the clock;


• the counter uses the jump bit \(\texttt{j}\), the value \(\texttt{A}\), and the clock.

If \(\texttt{j}\)=0, then the counter advances by \(1\). If \(\texttt{j}\)=1, then the counter is set to \(\texttt{A}\).

The outputs are: \[\begin{array}{c | l} \text{output} & \text{meaning} \\ \hline \texttt{PC} & \text{the current program counter} \\ \texttt{A} & \text{the current } A \text{ register} \\ \texttt{D} & \text{the current } D \text{ register} \\ \texttt{*A} & \text{the current RAM value at address } A \bmod 2\end{array}\]

Initially, \(\texttt{PC}\)=0, \(\texttt{A}\)=0, \(\texttt{D}\)=0, and both RAM cells store \(0\).

You may use only the following functions: \[\begin{aligned}\operatorname{NAND}(a,b) &= \neg(a \land b), \\ \operatorname{INV}(a) &= \neg a, \\ \operatorname{AND}(a,b) &= a \land b, \\ \operatorname{OR}(a,b) &= a \lor b, \\ \operatorname{CONTROLUNIT}(I,A,D,*A) &= (R,a,d,*a,j), \\ \operatorname{MEMORY}(a,d,*a,X,cl) &= (A,D,*A), \\ \operatorname{ROM}(Ad) &= \text{the ROM word at address } Ad \bmod 4, \\ \operatorname{COUNTER}(st,X,cl) &= \text{the current counter value}, \\ \operatorname{CLOCK}() &= \text{the current clock bit}.\end{aligned}\]

For example, a line \(\texttt{pc j A cl COUNTER}\) means that \(\texttt{pc}\) is a new 16-bit label equal to the current output of the counter with inputs \(\texttt{j}\), \(\texttt{A}\), and \(\texttt{cl}\).

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