Digital Signal Processing with Field Programmable Gate Arrays

Chapter01 - Home
Exercises: 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - 13 - 14 - 15 - 16 - 17 - 18 - 19 - 20 - 21 - 22

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×{b}^{\prime }+{a}^{\prime }×b$

which can be simplified to:

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

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

${a}^{\prime }×b={a}^{\prime }×b+{b}^{\prime }×b=\left({a}^{\prime }+{b}^{\prime }\right)×b={\left(a×b\right)}^{\prime }×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×b+a×cin+b×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×b\right)}^{\prime }$ NAND gate and that from ${\left(\left(a\oplus b\right)×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×b+{a}^{\prime }×{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×b+cin×\left(a×{b}^{\prime }+{a}^{\prime }×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×\left(b+cin\right)+b×cin$