# Tutorial 10 - Design and Simplification of Combinational Logic Systems

Learning Objectives

• design a logic system from a truth table, written description or Boolean algebra expression using combinations of gates;

• simplify a logic system using either Boolean algebra or Karnaugh maps;

• convert logic systems comprising mixed gates into either NOR or NAND gates only;

• describe and explain the operation of combinational logic systems.

Designing a Logic System

In Tutorial 9 we saw the principles of simple logic design.  We saw how we could produce a truth table from a combination of different logic gates.  The diagram shows another combination of logic gates: Question 1

Complete the truth table.

A

B

C

D

### Q

0

0

1

0

0

1

1

1

1

0

0

0

1

1

0

0 In drawing up the truth table, we notice that:

• C is A inverted, so that when A is a 1, C is a 0 and vice versa.

• D is a 1 when both C AND D are a 1.

• Q is a 1 when B is a 1.

Now let us do the reverse.  We are going to design a circuit having been given a description.

Design a circuit with two inputs A and B that will give an output that is high only when B is high and A is low.

 A B Q 0 0 0 0 1 1 1 0 0 1 1 0

1. We know that an AND gate will give a 1 only when both its inputs are high.  So we can connect B directly to the input, but not A.  We have a clue in the last sentence, NOT A.

1. So we need a NOT gate in the line from A.

 Question 2 Draw this circuit.  Is it consistent with the truth table? We can solve a problem if we are given a truth table rather than a written description.  Here is another truth table:

 A B Q 0 0 1 0 1 0 1 0 1 1 1 1

 Question 3 What three conditions are needed for the outputs to be 1? Question 4 Draw this circuit. Simplifying Logic Circuits with Boolean Algebra

The methods we have looked at above are OK for very simple systems, but with a more complex system we would find the truth tables very cumbersome, if not impossible.  So we can use Boolean algebra, which we first met in Tutorial 9.  Let us look at a few of the rules:

• A, B, and Q represent the variables which can only be 1 or 0.

• A (“A-bar”) is NOT A.  If A = 0, A = 1 and vice versa.  A is said to be complementary to A.

Important Note:  It is impossible using this web editor to place the bar above the A, so I have written the A-bar as a white letter on a black background, A.  In Word, I have put the bars above the letters using the line drawing function.  However it does not copy across at all well.  In some questions I have written "A-bar".  If you can do it any better, then please tell me, and then come and do the edits for me!  The double compliment "A bar-bar" I will write as A¯ ¯.

Go back to Tutorial 9 to revise the basic rules of Boolean Algebra.

A useful property of logic gates is that there is often more than one solution to a problem, and Boolean algebra helps to simplify the expressions required.  This allows us to use the minimum number of gates, desirable as that reduces the effort in design and wiring.  Here are some laws that will simplify matters:

 Name What it says De Morgan’s First Law De Morgan’s Second Law Double inversion Commutative Laws A + B = B + A Associative Laws A + (B + C) = (A + B) + C A.(B.C) = (A.B).C Distributive Laws A .(B + C) = (A.B) + (A.C) A + (B.C) = (A + B).(A + C) Product of Sums (A + B).(A + B) = A.A + A.B + B.A + B.B Redundancy A.B + A.B.C + A.B.D = A.B

De Morgan's laws were worked out by the British mathematician, Augustus de Morgan (1806 - 1871).

There are a lot of laws here, which we will use to simplify the circuit as shown in the example below:

 Simplify the Boolean expression for this circuit. The Boolean expression for this circuit is: The associative law says: See where the brackets have moved.  Well so what? Look at De Morgan I: Then De Morgan II gives us: The double bar gives us a double inversion, so we get: We can’t get much simpler than this.

Simplifying Circuits with Karnaugh Maps

Another way of finding the simplest solution to a logic gate problem is the use of the Karnaugh map (named after the American Physicist, Maurice Karnaugh (1924 - )).  Here is a truth table for an output with four different inputs, or a four-bit word.  You may wonder what this last term means:

• A word is a set of binary digits.  Computers use sixteen or thirty-two bit words, which means that they process groups of 16 or 32 binary digits.  8 binary digits is called a byte.  Here we have a group of four digits, not a very good medium for a computer.

• A bit is a binary digit, 1 or 0 (ON or OFF)

Look at this truth table:

DCBA

### Q

0000

0

0001

1

0010

0

0011

1

0100

0

0101

1

0110

0

0111

1

1000

0

1001

0

1010

1

1011

1

1100

1

1101

0

1110

0

1111

0

There are seven rows in this truth table where the output is 1.  So we can write the Boolean expression: This is a pretty ghastly expression.  Of course we can simplify it using the methods we saw above, but Karnaugh maps are much more helpful in this case.

Notice the order of the letters.  D is the most significant bit, and A is the least.

In the Karnaugh map we split up the truth table into a 4 x 4 matrix, with the rows identified by DC, and the columns identified with BA.  Notice the order of the two bit words.  One bit is the same as the neighbours.  The sum of adjacent bits has to be different. If you can’t remember these, just learn the order, 00, 01, 11, 10.

We need to fill the table from the truth table above.  For example 00, 01 (Black arrows) gives a 1 and 01, 10 (Blue arrows) gives a 0. So we fill the table: We can identify clusters of 1s: These clusters have been marked P, R, S.  Let us look at group P.  We get a 1 in both cells when DC is 10.  We get a 1 in one of the cells when BA = 11, or when BA = 10. So we can write the Boolean expression for cluster P as: We can rewrite this as: Question 5 Explain why P = D.C.B Now let's do the same for R.

 Question 6 What is the Boolean expression for R? Question 7 Explain why we can write R = D.A. Now look at S.

 Question 8 What is the Boolean expression for S? Now we can put P, R, and S together: Can we simplify this any further?  No.

To design the circuit, we need to think of the three inputs to OR gates:

1. D AND NOT C AND B

2. NOT D AND A

3. D AND C AND NOT A AND NOT B

We will build this up bit by bit, starting with Q.  Q = P + R + S.  Q is equal to P OR R OR S. This is the output end of the circuit.  Now we will draw P = D.C.B Now we will draw R = D.A Then we can draw out S = D.C.B.A Finally we can put the whole thing together: In this last example, we have designed a rather complex system from a Karnaugh map.  We could test it out with a giant truth table, but it would get rapidly rather tedious.  For a more complex circuit it would be impossible.

Using NAND  or NOR gates to make up Circuits

The circuit we have designed above uses:

• 6 AND gates

• 4 NOT gates

• 2 OR gates.

We would need to buy two AND gate chips (each chip has four gates), one OR gate chip, and 1 NOT gate chip.  For this circuit, it would be not be vastly expensive, but you can see that there is a certain amount of redundancy.  You can also see that the more redundancy, the more expensive a complex system can become.

NAND gate chips are particularly easy to make and are very cheap.  So if we can make a circuit that consists of other gates entirely from NAND gates, then we can save a lot on redundancy of our resources.  So we use NAND gates as building blocks for circuits.

The NOT gate and the AND gate are simple.

 How do we get a NOT gate from a NAND gate?  Draw up a truth table to back up your answer. Show how an AND gate can be made from two NAND gates.  Draw up a truth table to back up your answer. The OR gate is not so obvious to work out from first principles.  However if we use De Morgan I, we can see that: Notice the double inversion here.  The basic circuit is shown in this diagram. Question 11 Answer the interactive question. Question 12 Use a truth table to prove that the circuit above is an OR gate. If we look at Q we can clearly see that we have an OR gate.  Now we can convert the circuit above into one made up of NAND gates only. However this is not an efficient use of resources.  We have an inverter followed by another inverter which is a waste.  So a more efficient circuit is: The NOR gate made up of NAND gates is the same as the OR gate, but with an extra inverter, shown below. The exclusive OR gate can be worked out again with Boolean algebra, but the derivation is rather tedious.  The NAND gate circuit is shown here. NOR gates can be used in a similar way to NAND gates.

 Question 13 How would you make a NOT gate from a NOR gate? We can use two NOR gates to produce an OR gate quite simply.

 Question 14 How would you make an OR gate from a NOR gate? NOR gates can be put together to from an AND gate, in the same way that NAND gates get put together to make an OR gate. We can check this out with a truth table:

 A B C D Q 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1

This is of course the pattern of an AND gate.

The Operation of Combinational Logic Systems

We have looked extensively at the combinations of logic gates, and how we can make circuits with a single gate as a unit.  What use is this, other than an academic exercise?  Logic gates are used extensively in calculators and computers.  Logic gates can be used to add binary numbers.  Computers are adding machines; they do subtraction by a process of complimentary addition, while they multiply by serial addition.

The circuits they use are based on the half-adder.  This copes with the rules for binary addition which are:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0 carry 1

(1 + 1 + 1 = 1 carry 1)

The circuit has two outputs, a sum and a carry.  The sum is the output of an exclusive OR gate (we can’t have 1 + 1 = 1), while the carry output is that of an AND gate.  The Boolean algebra is:

•                             sum = A + B

•                             carry = A.B

This gives an arrangement shown below: Question 15 Show how this circuit can be made with NAND gates. The truth table is as follows:

 A B Sum Carry 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0 1 Links Interactive logic gates simulator Electronics tutorials Video tutorial on Karnaugh Maps NAND gates