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:


PIC

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

a b = a × b + a× b


PIC

which can be simplified to:


PIC

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

a × b = a × b + a × a = a × (a + b) = a × (a × b)

a× b = a× b + b× b = (a + b) × b = (a × b)× b

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


PIC

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


PIC

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 = abcin + abcin + ab

because we can reuse the output from (a × b) NAND gate and that from ((a b) × cin). Hence the cout is derived as follows:


PIC

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


PIC

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

a b = (a × b + a× b)

Hence, using the AND operation implemented using NOR we get:


PIC

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


PIC

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 × (a × b + a× b)

so that:


PIC

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


PIC

then we can implement XOR as:


PIC

The sum term is also implemented as cascaded XORs:


PIC

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

cout = a × (b + cin) + b × cin

which leads to:


PIC