1

Design of Logic Circuits

1.1

Basic Revision of Logic Gates

In the following chapter, we assume a two input logic gate with inputs A and B.

1.1.1

Simple Gates

i.

AND Gate

The symbol and truth table for an AND gate is shown below:

A

B

A.B

0
0
1
1

0
1
0
1

0
0
0
1

Summary:

If inputs A AND B are high then the output is high

Abbreviations:

often a ‘.’ (dot) is used to signify the AND operator when writing Boolean equations. ii.

OR Gate (Sometimes referred to as an Inclusive OR)

The symbol and truth table for an OR gate is shown below:

A

B

A+B

0
0
1
1

0
1
0
1

0
1
1
1

Summary:

If inputs A OR B are high (or both) then the output is high

Abbreviations:

often a ‘+’ is used to signify the OR operator when writing Boolean equations. iii.

NOT Gate

The symbol and truth table for an NOT gate is shown below:

A
0
0

1

A
0
1

2
Summary:

Output is NOT what the input is. They are also called 'inverters'.

Abbreviations:

Many. Sometimes a line above the thing that is being notted, sometimes a dash ‘'’ and sometimes an ‘!’ exclamation mark

1.1.2

Complex Gates

i.

NAND Gate

Made by combining an AND gate and a NOT gate. The equivalent circuit is:

The symbol and truth table for an NAND gate is shown below:

A

A .B

0
0
1
1

0
1
0
1

1
1
1
0

A

B

A+ B

0
0
1
1

ii.

B

0
1
0
1

1
0
0
0

NOR Gate

Made by combining an OR gate and a NOT gate. The equivalent circuit is:

The symbol and truth table for an NAND gate is shown below:

iii.

XOR Gate (Exclusive OR)

This gate gives a high output when A OR B are high, but not both. The equivalent circuit is:

Digital Electronics – EEE3017W (2009)

3
The symbol for a XOR gate is:

A

A⊕ B

0
0
1
1
Summary:
Abbreviations:

B
0
1
0
1

0
1
1
0

A ⊕ B = A .B + A .B
XOR gates are represented with a ⊕ symbol.

1.2

Boolean Algebra

1.2.1

Basic Boolean Equations

When designing circuits it is useful to be able to simplify logic equations. By simplifying the equation of a circuit we can reduce the number of gates that will be needed to implement the circuit when it is constructed. This has cost and performance benefits.
The following equations are used to reduce logic equations:
OR:

AND:

A + 0 = A A.1 = A
A+1=1
A.0 = 0
A + A = A A.A = A
A + A = 1 A .A = 0

NOT:

A= A

ASSOCIATIVE

DISTRIBUTIVE

COMMUNTATIVE

A+(B+C)=(A+B)+C A.(B+C)=A.B+A.C
A+B=B+A
A.(B.C)=(A.B).C
A+B.C=(A+B).(A+C) A.B=B.A

Remember that the optimal solution is not always the solution with the fewest gates. In terms of cost the optimal solution is generally that solution which has the fewest logic chips, assuming that the cost of logic chips does not differ greatly for different logic gates. (A chip which contains four
AND gates costs roughly the same as a chip with four OR gates.) This has not always been the case.

1.2.2

De Morgan’s Rules

These can be a bit tricky to remember. An aid to memory is
“If you break the line you change the sign”.

A + B = A .B
A .B = A + B
The symbolic representation of de Morgan’s Rules is shown below:

University of Cape Town

4

1.2.3

Karnaugh Map Reduction

This method is a graphical aid to reducing logic equations. Its primary limitation is that is not effective for more than four variables.
The map takes the form of a table laid out as shown below. The order of the possible variable states is important. A Grey code must be used. A Grey code is a code in which at most one bit changes in successive numbers.

CD

00

01

11

10

AB

00
01
11
10
All the combinations which result in'1' as the result are marked in the table and grouped together.
See the class example for further information on grouping and reduction.

i.

Examples

Reduce the following equation using both Boolean algebra and Karnaugh Maps to a circuit with the fewest number of gates.

Y = A .B .C + A .B .C + B .C + A .B
Using Boolean algebra:
Y = A .B .C + A .B .C + B .C + A .B
Y = A .B .C + A .B .C + A .B .C + A .B .C + A .B .C + A .B .C (Expanding all terms by multiplyin g by
1. i.e. (A + A ))
Y = A .B .C + B .( A .C + A .C + A .C + A .C + A .C )

(( )
Y = A .B .C + B (A + A)

(

Y = A .B .C + B . A . C + C + A . C + C + C

))

(Take out the common factor)
(Group terms and take out the common factors)
(Simplify)

Y = A .B .C + B

Digital Electronics – EEE3017W (2009)

5
Using Karnaugh Maps:
Y will equal 1 whenever any one of its terms equals 1. Therefore find the values of A, B and C that make any term equal 1.

AB

00

01

11

10

C

0

1

1

1

1
1

1

Grouping these terms yields a simpler result.

Y = A .C + B
Assume that the following logic chips exist and cost the same:
CD4081 quad two input AND gate
CD4011 quad two input NAND gate
CD4071 quad two input OR gate
CD4001 quad two input NOR gate
CD4069 hex inverter
Reduce the above equation to the lowest cost solution.
Our solution above gives would need 1 OR gate, 1 AND gate and 1 inverter. This amounts to 3 chips that would be needed.
We could replace the AND gate with a NAND gate followed by an inverter. We can make an inverter from a NAND gate by tying one input permanently high. Thus we can say:
Y = A .C + B

(

)( )

= A .C .1 + B .1

This circuit would need one quad NAND chip and one quad OR chip.
If you worked for a large company producing 20000 gadgets per month then this saving alone would justify your salary...
Exercise:
1. Draw circuit diagrams of the above solutions and check that you are satisfied with their correctness. University of Cape Town

6

1.3

Combinational and Sequential Circuits

There are two basic classes of digital circuits. These are combinational circuits and sequential circuits. They differ fundamentally.

1.3.1

Combinational Circuits

These circuits have no memory. At any point the output of the circuit depends purely on the inputs to the circuit. If you know the inputs only then you will be able to calculate the output. If you want to reverse engineer a combinational circuit then all that you need to do is to cycle through all possible inputs and observe the output. From the truth table that you draw up it is theoretically easy to design an equivalent circuit. (Although it might be tedious)

1.3.2

Sequential Circuits

These circuits have memory. At any point the output of the circuit is a function of the inputs and the
'state' of the circuit. This means that you can't simply apply some input and predict the output, rather you must know either the state of the circuit or you need information about all the previous inputs to the system. Expressed in another way, the output of a combinational circuit is a function of its inputs and its history. It is clear from the above that simple logic design tools (Karnaugh etc.) are of limited use in designing sequential circuits. We will examine other sequential logic design techniques later.

1.3.3

Popular Ready-made Digital Circuits

i.

Multiplexers

These are basically selector devices. They have k inputs and one output. They have log2k selection inputs. This is shown for the case of a multiplexer with 4 inputs (k = 4). The action of the multiplexer can be summarised as follows:

Sel1 Sel2

Action

0

0

Output = In0

0

1

Output = In1

1

0

Output = In2

1

1

Output = In3

Exercises:
1. Look at the datasheets for the following chips: 74HC157;74HC153;74HC356
2. Are multiplexers combinational or sequential? Why?

Digital Electronics – EEE3017W (2009)

7

ii.

Decoders

These are chips which decode a binary number into a '1 of n' output. Typically a decoder has n inputs and 2n outputs. One (only one) of the outputs will go high depending on the code present on the input lines. The truth table for a 3 to 8 line decoder is shown here:

In2

In1

In0

0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

Out7 Out6 Out5 Out4 Out3 Out2 Out1 Out0

0
1
0
1
0
1
0
1

0
0
0
0
0
0
0
1

0
0
0
0
0
0
1
0

0
0
0
0
0
1
0
0

0
0
0
0
1
0
0
0

0
0
0
1
0
0
0
0

0
0
1
0
0
0
0
0

0
1
0
0
0
0
0
0

1
0
0
0
0
0
0
0

Decoders are particularly useful to activate a device based on a code.
Exercises:
1. Look at the datasheets for the following chips: 74HC137; 74HC42; 74HC139
2. Are decoders combinational or sequential? Why?

iii.

Adders

This is a circuit which adds two bits together. Basic Boolean arithmetic gives us:
A0
+B 0
SUM 0

0
1
1

1
0
1

1
1
0 and 1 is carried to the next significant bit

If you examine the answer bit you will see that it is simply the XOR of the input bits. If you examine the carry bit you will see that it is simply the AND of the input bits. The circuit that implements this is as follows:

If you look carefully at this circuit you will see that it has one little problem. If you are implementing a proper addition then you will typically have two inputs, as well as a carry input, and you will have two outputs, sum and carry. The above circuit does not have any carry input. For this reason it is called a half adder.
A full adder is a circuit which has three inputs, one of which is a carry input, and it has two outputs, sum and carry. A full adder may be made by connecting two half adders as follows:
University of Cape Town

8

Intuitively this makes sense; the carry in bit is added to the result of the addition of the two input bits. In order to make a multi-bit wide adder a series of full adders can be cascaded. The carry outputs are fed into the3 carry inputs of the next most significant adder. Cascading gates can lead to poor circuit performance (gates are not infinitely fast) and so other schemes are used in more sophisticated adders. These schemes generally rely on the fact that the addition of two numbers is a combinational operation and can be modeled with a truth table, Boolean equations or a Karnaugh map. Exercises:
1. Look at the datasheet for 74HC283
2. Draw a four bit wide adder based on full-adders
3. Design a 2 bit wide adder using a Karnaugh map. Your circuit have a 2 bit plus carry output. You will need to use a few Karnaugh maps.

iv.

RS-Flip Flops

This device can be made by cross-coupling two gates, either NAND or NOR, like this:

This device has memory. If you pull S low then Q will go high and stay high until R is pulled low.
This circuit forms a basis for other flip-flop types.
Exercise:
1. What is the difference between the NOR and the NAND implementation?

Digital Electronics – EEE3017W (2009)

9

v.

D-type Flip Flops

The D-type flip flop has got (at least) one input called D, one input called clock and one output called Q The symbol for a D flip flop is shown here:

On the edge of the clock pulse (in this case the positive edge), the input D, is transferred to the output Q and held there. Typically a Q output is also available. In addition there are set and reset inputs which can be used to place the flip-flop into a known state.
Exercise:
1. Look up the datasheet for CD4013 and 74HC74.

vi.

JK Flip Flops

If both 'set' and 'reset' inputs are asserted on a D flip flop then the outputs may go into some weird states. If both inputs are asserted on the CD4013 D type flip-flop (CD4013 is a common device) then Q = Q = 1.
A JK flip flop operates in a similar manner to a D type, except that it has two additional inputs, J and K. If the J input is asserted then the flip-flop performs a 'set' operation. If the K input is asserted then the flip-flop performs a 'reset' operation. If both J and K are asserted then the output simply toggles state. A JK flip flop is shown here:

Many JK flip flops also have conventional set and reset inputs.

vii.

Counters

If you take some D flip flops and connect them as follows you get a basic counter:

University of Cape Town

10
This counter counts through the 8 states that its outputs can have. Each flip flop is configured as a toggle element. This is known as a “divide by two” stage. These stages are cascaded to form a counter. Other variations are also common. up/down counters are available and presettable counters are also available. Some counters (e.g. CD4017) have got decoded outputs, internally containing a counter and a decoder.

The counter shown above is called a “ripple counter”. The reason for this is that the second flip flop can only begin toggling when the first counter has completed its state change. This means that the outputs don't all change at the same instant. This can cause problems in some circuits and for this reason ripple counters are no longer popular. We will cover non-ripple counter design later. A zoomed-in view of the transition from state “011” to state “100” is shown here.
Exercises:
1. By writing out a table prove that a count sequence can be made up by cascading toggle stages. 2. Look up the datasheet on 74HC4040.

viii.

Shift Registers

This circuit implements a device called a “shift register”. Data is put into the load input and for every clock pulse it moves across the Q outputs 1 bit to the right.

Shift Registers are useful for implementing serial to parallel conversion and parallel to serial conversion. They are used extensively in microprocessors for a variety of operations.

Digital Electronics – EEE3017W (2009)

11

1.3.4

Design of Sequential Circuits

i.

Designing Using D-type Flip Flops

The basic idea behind this type of design is to use D-type flip flops to hold the system's state and use combinational logic to make the system move from state to state. Schematically we have the following basic layout:

In order to design the combinational circuit to calculate the next state we use a present state/next state diagram. Suppose we have a system with four states and one input. Our diagram will typically look like this:

Input

Present 1

Present 0

0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

Next 1 Next 0

0
1
0
1
0
1
0
1

The next state columns will show the state that is to be entered given the current state and input condition. Once this table has been drawn up standard logic reduction tools are used to calculate the combinational circuitry.

University of Cape Town

12

ii.

Design Example

1. Design a counter that counts in the sequence 0-1-2-0-1-2 etc. The counter must not be a ripple type. Because the counter cannot be a ripple type forget about using a ripple counter and making it reset itself when it reaches 2.
We need to use a present state next state diagram. If we design the circuit using two D flip flops then there will be four possible states, even though we are only interested in 3 of them. We shall use
'Don't cares' to simplify our circuitry. This counter is made simpler by the fact that there are no external inputs.
Our present state/next state diagram is as follows:

Present 1 Present 0
(Q1)
0
0
1
1

Next 1
(D1)
0
1
0
X

(Q0)
0
1
0
1

Next 0
(D0)
1
0
0
X

By inspection we can tell that D1 = Q0. Note how the don't care case has simplified this. The
Karnaugh map for D0 is like this:

Q0

0

1

Q1

0
1

1
X

If we let the don’t care condition equal 0 we find D0 to be:
D0 = (Q0 + Q1 )
The overall circuit is as follows:

Notice over here that both flip flops are clocked simultaneously, avoiding the ripple effect.

Digital Electronics – EEE3017W (2009)

13
2. Design a light-chaser system. The system has four LED's, numbered from 0 to 3. When the system is running it sequences the LED's. There is also a direction input, called DIR. When DIR is low the LED's go in the sequence 0-1-2-3. When DIR is high the LED's are sequenced in the other direction, 3-2-1-0.
There are four states in this system, one per LED. We can use two bits of information to hold the system state. The present state/next state diagram is as follows:

Input

Present State

DIR
0
0
0
0
1
1
1
1

Q1
0
0
1
1
0
0
1
1

Next State

Q0
0
1
0
1
0
1
0
1

D1
0
1
1
0
1
0
0
1

D0
1
0
1
0
1
0
1
0

Comment
LED0 counting UP
LED1 counting UP
LED2 counting UP
LED3 counting UP
LED0 counting DOWN
LED1 counting DOWN
LED2 counting DOWN
LED3 counting DOWN

By inspection D0 = Q0 . We can draw the following Karnaugh map for D1.
Q1Q0

00

01

11

10

DIR

0
1

1
1

1
1

This simplifies to:
D1 = DIR .Q 1 .Q0 + DIR .Q 1 .Q0 + DIR .Q 1 .Q0 + DIR .Q 1 .Q0
= DIR ⊕ Q1 ⊕ Q 2

So far we have not handled the output decoding at all. We have four output bits but only two bits are used to encode the state information. Because of the way that we set up the states in the first instance we only need a 2-4 decoder to perform the output decoding. Note that a 2-4 decoder is available as a single chip, which saves space and cost.

University of Cape Town

14

1.4

Algorithmic State Machine Design

Some systems are too complex to simply draw up a present state/next state table. A complex system will have more than a few states and it may have many inputs, not all of which are relevant in all possible states. This makes it essential for us to have more sophisticated design techniques.
We can represent the operation of a sequential circuit by using an Algorithmic State Machine Chart
(ASM chart). We will do this by using the following elements:

1.4.1

State Box
State Entry Path

State Code

State Name

****
*

When using the state box please note the following: • There is always one entry point and one exit point only.
• Outputs that must be asserted while in that state are marked in the middle of the box
• Each state has a binary code associated with it. You may give your states names to add clarity. • A state generally lasts for one clock cycle of the system's operation.

State Output List
State Exit Path

1.4.2

Decision Box

Single Entry Path
Condition
(Boolean Expression)

●●●●

0

Condition
FALSE Exit
Path

When using the decision box please note the following: • There is always one entry point and two exit points. • Each box examines the state of exactly one variable. • A decision is not a state. No state number is assigned to it.

1
Condition TRUE Exit Path

Digital Electronics – EEE3017W (2009)

15
When using a conditional output box the following rules apply:
• There is always one entry point and one exit point. The entry point comes from a decision box. • The conditional output box is not a state. It is simply an output that is asserted briefly during the transition from one state to another. • The outputs asserted by conditional output boxes may be of variable length. This means that they may not be used where the duration of the output's assertion is critical.

From Conditional Exit
Conditional
Output List

Exit
Path

The behaviour of the system is modeled by combining the three types of blocks to form a chart which defines how the system will work.

i.

Examples

1. Show the ASM chart for a two bit counter. The counter has no inputs other than its clock.
00
Zero

Output = 00
01

One

Output = 01
10

Two

Output = 10
11

Three

Output = 11

Notice that we do not explicitly show the clock. We assume that there is a clock signal and we assume that the system moves from state to state synchronously with the clock.
From the ASM chart we can derive the following

University of Cape Town

16

Present 1 Present 0
(Q1)
0
0
1
1

(Q0)
0
1
0
1

Next 1

Next 0

(D1)
0
1
1
0

(D0)
1
0
1
0

From this we can derive logic as before.
This was a very simple example. We could have done this easily without the help of an ASM chart.
Consider this slightly more advanced example:
2. We wish to make a timing system for an athletic event. We are only interested in the first three runners in. We have a system of transponders which gives us a signal when each of the runner arrives. We also have a stopwatch system (separate) consisting of three stopwatches, which will do the timing. All that we need to implement is a system which links the stopwatch to the transponder system. In addition we would like a display of three LED's which indicates how many runners must still come in.
In summary we could say that the transponder system has an output called “arr”. This output goes high briefly when a runner arrives. The stopwatch system has three incoming signals, stor1, stor2 and stor3, each of which triggers a time capture.
We'll start this seemingly tricky task by drawing an ASM chart.

Notice over here that we have assigned the states 00, 01, 11, 10. Sometimes a Gray code will yield better circuitry.

Digital Electronics – EEE3017W (2009)

17
Notice immediately that this chart is quite good for showing to non-technical customers. From this chart we can draw a present state/next state diagram. A very important feature of this design tool is that it has clarified the task in our minds. In this diagram we have only shown the state transitions for simplicity.

Input

Present State

Arr
0
0
0
0
1
1
1
1

Q1
0
0
1
1
0
0
1
1

Q0
0
1
0
1
0
1
0
1

Next State
D1
0
0
1
1
0
1
1
1

D0
0
1
0
1
1
1
0
0

From this table we get the Karnaugh maps:

D0
Q1Q0

00

01

11

1

10

1

Arr

0
1

1

1

00

01

D0 = Arr .Q0 + Arr .Q1

D1
Q1Q0

11

10

1

1

1

1

Arr

0
1

1

D1 = Q1 + Arr .Q0

From this we can get the circuit for the state-sequencing system:

University of Cape Town

18

The clock inputs on the flip flops are tied together and tied to a clock source (square wave) with a frequency which is sufficiently high that the circuit responds fast to inputs.
So far we have not taken the conditional outputs into account. This is quite easy:
Stor1 is asserted if state = 00 and Arr = 1 therefore
Stor 1 = Arr .Q1 .Q0
Similarly Stor2 is asserted if state = 01 and Arr = 1 therefore
Stor 2 = Arr .Q1 .Q0 and also
Stor 3 = Arr .Q1 .Q0

These can be added to our existing circuit diagram:

Now all that is required is to add in the display for the LED's. We can draw the following table which maps the system state to the system outputs for the LED's.
Digital Electronics – EEE3017W (2009)

19
Q1

Q0

LED3

LED2

LED1

0
0
1
1

0
1
1
0

1
0
0
0

1
1
0
0

1
1
1
0

From this table:

LED3 = Q1 .Q0
LED2 = Q1

(

LED1 = Q1 .Q0

)

The final circuit for our system looks like this:

This circuit can be simplified by exploiting the commonality between the LED output circuit and the Stor outputs. This is left as an exercise.

1.4.3

Designing with One Flip Flop per State

Up until this point we have assumed that it is optimal to have the minimal number of flip flops in our ASM implementation. Sometimes we will find it easier to use one flip flop per state, resulting in more flip flops and (hopefully) less combinational logic. In addition this scheme will result in an easier design process. Using this system it is possible to design all of the circuitry without even drawing a present state/next state diagram.
The basis of the technique is to replace each element of the ASM chart with a circuit. Thus we have the following replacement rules:

University of Cape Town

20
The state box is replaced with a flip flop. The entry into the state box is modeled by the D input to the flip-flop. The execution flow out of the state box is modeled by the Q output of the flip flop.
State Entry Path

****

State Exit Path
State Entry Path

*
State Exit Path
We replace decision boxes like this:
Single Entry Path

Variable

0

Condition
FALSE Exit
Path

1
Condition TRUE Exit Path

And we replace conditional output boxes with the following circuit:
Incoming Flow

Variable

Conditional Output

Outgoing Flow
Lastly we must replace the junctions in signal flow with OR gates. Please note that it is not generally acceptable to simply connect two outputs together. This is because of the possibility of
‘contention’, which occurs when one signal attempts to pull a line high while another output is asserting a low on the same line.

Digital Electronics – EEE3017W (2009)

21

Entry 1

Entry 2

Exit
Now that we have the ground rules established we can do an example. We will do the example from page 16. Refer to that example for the ASM chart.
By substitution we arrive at the following circuit:

In the above circuit only one thing is missing. That is the power-on-reset circuit. When the system is powered up it is critical that it goes into the idle state (state 00) and it is also critical that only one state is active. In practice this means that one flip-flop is set (the idle state flip-flop) and all of the other flip-flops are cleared. This is achieved by using the set and reset inputs to each flip-flop.

University of Cape Town

22

1.5

Conclusion

It takes practice to become proficient at logic design. Half the trick to being a good designer lies in being able to think about the real system that must be made and converting that to an ASM chart. In order to get skills in this area consider the following examples:
Redo the “who was first' game from the laboratory. Use both ASM design methods outlined above.

Digital Electronics – EEE3017W (2009)