Lesson 2

The next step is to decode an instruction word and route its bits to the ALU, destination logic, and jump condition.

Problem. Construct the ALU-instruction decoder. The labels \(\texttt{I}\), \(\texttt{A}\), \(\texttt{D}\), and \(\texttt{*A}\) are hardcoded 16-bit inputs, so you may use them directly in gate lines. The outputs of your circuit must be five labels, in the order \(\texttt{R a d *a j}\), where \(\texttt{R}\) is 16-bit and the other four outputs are bits.

The instruction bits are interpreted as follows: \[\begin{array}{c | c | l} \text{bit} & \text{group} & \text{meaning} \\ \hline 10 & \text{ALU} & u \\ 9 & \text{ALU} & op_1 \\ 8 & \text{ALU} & op_0 \\ 7 & \text{ALU} & zx \\ 6 & \text{ALU} & sw \\ 5 & \text{destination} & a \\ 4 & \text{destination} & d \\ 3 & \text{destination} & *a \\ 2 & \text{condition} & lt \\ 1 & \text{condition} & eq \\ 0 & \text{condition} & gt\end{array}\] Bit \(12\) selects the second ALU operand: if \(\texttt{I[12]}\)=0, then the ALU input \(\texttt{Y}\) is \(\texttt{A}\); if \(\texttt{I[12]}\)=1, then \(\texttt{Y}\) is \(\texttt{*A}\). The first ALU operand \(\texttt{X}\) is always \(\texttt{D}\). Bits \(15,14,13,11\) are ignored in this task. The outputs are defined as follows:

• \(\texttt{R}\) is the result of the ALU operation specified by bits \(10,9,8,7,6\) on inputs \(\texttt{D}\) and the selected \(\texttt{Y}\);


• \(\texttt{a}\), \(\texttt{d}\), and \(\texttt{*a}\) are exactly instruction bits \(5,4,3\);


• \(\texttt{j}\) is \(1\) exactly when \(\texttt{R}\) satisfies the condition specified by instruction bits \(2,1,0\).

You may use only the following functions: \[\begin{aligned}\operatorname{NAND}(a,b) &= \neg(a \land b), \\ \operatorname{ALU}(u,op_1,op_0,zx,sw,x,y) &= \text{the ALU output}, \\ \operatorname{CONDITION}(lt,eq,gt,x) &= \text{the condition output}, \\ \operatorname{SPLIT}_{16}(x) &= (x_{15},x_{14},\dotsc,x_0), \\ \operatorname{AND}_{16}(a,b) &= a \land b, \\ \operatorname{ADD}_{16}(a,b) &= a+b \pmod{2^{16}}, \\ \operatorname{SELECT}_{16}(s,d_1,d_0) &= \begin{cases} d_0, & s=0, \\ d_1, & s=1, \end{cases} \\ \operatorname{INV}_{16}(a) &= \overline{a}, \\ 0() &= 0000000000000000.\end{aligned}\] For example, a line \(\texttt{b15 b14 … b0 I SPLIT16}\) means that \(\texttt{b15}\), \(\texttt{b14}\), …, \(\texttt{b0}\) are the bits of \(\texttt{I}\) from most significant to least significant.

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