Lesson 7

A processor stores the address of its next instruction in a special register called the program counter. After an ordinary instruction, this address is incremented so that execution proceeds to the following instruction. A jump must instead replace it with a target address supplied by the instruction or computed by the processor. Thus a program counter is a counter with an additional load operation: a control bit chooses between incrementing the current address and loading the jump target.

Problem. Synthesize a circuit of size \(3\) over \(\{\operatorname{NAND}_{2}, \operatorname{INV}_{1}, \operatorname{REGISTER}_{16}, \operatorname{INC}_{16}, \operatorname{SELECT}_{16}\}\) computing the 16-bit program-counter function: \[\operatorname{PROGRAMCOUNTER}_{16}(st,x,cl)=q.\] It starts at \(0\); on each falling clock edge, set \(q\) to the jump target \(x\) if \(st=1\), and otherwise increment it modulo \(2^{16}\). Thus \(x\) is ignored during ordinary sequential execution and is used only when the rest of the processor requests a jump by setting \(st=1\). Assume \(\texttt{st}\) and \(\texttt{x}\) do not change while \(\texttt{cl}\)=1.

In this task, cycles in the circuit are allowed.