Lesson 5

Problem. Construct a component that adds \(1\) to an 8-bit number. The inputs are \(x_{7},x_{6},\dotsc,x_{0}\), where \(x_{7}\) is the most significant bit. The outputs are \(y_{7},y_{6},\dotsc,y_{0}\), where \(y_{7}\) is the most significant bit of the result. If the sum is larger than \(8\) bits, ignore the carry.

You may use only the following functions: \[\begin{aligned}\operatorname{NAND}(a,b) &= \neg(a \land b), & \operatorname{INV}(a) &= \neg a, \\ 0() &= 0, & \operatorname{XOR}(a,b) &= a \oplus b, \\ \operatorname{ADD}_{8}(a_7,\dotsc,a_0,b_7,\dotsc,b_0,c) &= (u,s_7,\dotsc,s_0).\end{aligned}\] Where the line of code \(\texttt{x 0}\) assigns the value \(0\) to the variable \(x\).

Here \(u\) is the carry bit, and \[\sum_{i=0}^{7}2^{i}s_{i} + 2^{8}u = \sum_{i=0}^{7}2^{i}a_{i} + \sum_{i=0}^{7}2^{i}b_{i} + c.\]

Examples: \[00000000 \mapsto 00000001,\] \[00000111 \mapsto 00001000,\] \[11111111 \mapsto 00000000.\]

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