Chapter01 - Home

Exercise. This is the solution to exercise 1.1 in the book.

Solution. This is a trivial digital design problem. It is actually easier to start with showing that two-input NAND gate is universal. Hence:

We then implement XOR using two-input NAND gates as:

$$a\otimes b=a\times {b}^{\prime}+{a}^{\prime}\times b$$

which can be simplified to:

However the inputs to the middle NAND gates can be written from:

$$a\times {b}^{\prime}=a\times {b}^{\prime}+a\times {a}^{\prime}=a\times \left({a}^{\prime}+{b}^{\prime}\right)=a\times {\left(a\times b\right)}^{\prime}$$$${a}^{\prime}\times b={a}^{\prime}\times b+{b}^{\prime}\times b=\left({a}^{\prime}+{b}^{\prime}\right)\times b={\left(a\times b\right)}^{\prime}\times b$$

Hence we don’t need two NAND gates to invert each of $a$ and $b$, but rather only one shared in common:

Then we can implement the $sum$ term of the full adder by cascading two XOR structures as:

Even though the simplest expression for $cout$ is

$$cout=a\times b+a\times cin+b\times cin$$in this case the following expression allows reuse of some of the logic in $sum$ calculation:

$$cout=a{b}^{\prime}cin+{a}^{\prime}bcin+ab$$because we can reuse the output from ${\left(a\times b\right)}^{\prime}$ NAND gate and that from ${\left(\left(a\oplus b\right)\times cin\right)}^{\prime}$. Hence the $cout$ is derived as follows:

Let’s repeat now for two-input NOR gate. First we show that it is a universal gate:

Then, if we want to express XOR using a NOR operation we’d have:

$$a\oplus b={\left(a\times b+{a}^{\prime}\times {b}^{\prime}\right)}^{\prime}$$Hence, using the AND operation implemented using NOR we get:

To obtain the $sum$ term of the full adder we can chain two XOR structures based on NOR gates:

and to obtain the $cout$ term we reuse some of the partial terms from $sum$ calculation and use the fact that:

$$cout=a\times b+cin\times \left(a\times {b}^{\prime}+{a}^{\prime}\times b\right)$$so that:

Let’s repeat now for 2:1 MUX. First we show that the 2:1 MUX is a universal gate:

then we can implement XOR as:

The $sum$ term is also implemented as cascaded XORs:

and for $cout$ the expression requiring minimum number of muxes is:

$$cout=a\times \left(b+cin\right)+b\times cin$$which leads to: