# Logic Circuit Design Class Notes EE242

## Preview text

Faculty of Engineering Electrical Engineering Department Communications and Electronics Program
Logic Circuit Design Class Notes EE242
SPRING 2015

LOGIC CIRCUIT DESIGN EE242
Term: SPRING 2015 Instructor: Dr. M. El-Banna, Room: EE-Building 4th floor Classes : Group1 SUN 10:10 – 11:40
Group2 SUN 2:00 – 03:30

Topics to be covered: Chapter 1: Implementation of Logic Functions Chapter 2: Design of Combinational Circuits Chapter 3: Sequential Circuits Chapter 4: Design of Synchronous Sequential Circuits Chapter 5: Introduction to Counters, Registers, and HDL language

Text Book: Fundamental Logic Design, Thomson, Charles Roth Further Reading: Contemporary Digital Design, Johnson and Karim

Midterm 30

LAB

30

Final

90

ILOs of the Logic Circuit Design EE242
1. Comprehend and use the main blocks of combinational circuits, MUXs, ROMs, PLAs, PALs, Decoders and Encoders
2. Design combinational circuits using different blocks. 3. Carry out a project using the NI- LabVIEW software package to design and test combinational
circuits, if time allows. 4. Differentiate between combinational and sequential circuits 5. Review all types of Flip Flops used in sequential circuits and represent their functions by state
diagrams. 6. Convert verbally stated design problems into state diagrams and hence state tables. 7. Differentiate between Mealy and Moore finite state machines. 8. Follow up the design procedure of sequential circuits starting from implication tables through
partition tables, state transition tables, excitations maps and eventually the hardware implementation. 9. Use the Verilog/VHDL language to design come known logic circuits, combinational and/or sequential 10. Comprehend and design synchronous and asynchronous counters

..

Implementation of

CHAPTER
FOUR

Logic Functions _ _ _ _----I

4.1 Introduction

The design mechanism of combinational logic circuits is usually a multi-step process. The realization, and the subsequent minimiza­ tion, of the logic function is not the end of the design. We are already familiar with the various schemes for coming· up with the reduced logic function either in the SOP or in the POS format. These forms can be translated easily into either a familiar AND­ OR or OR-AND pattern of logic circuits. However, we have also seen in the last chapter that digital ICs have several practicallimi­ tations that may affect the implementation of circuits. These
include the fan-in and fan-out lim. itationS and the fa. ct that ICs are
more frequently available in the NAND and NOR form than in the AND and OR form. NAND and NOR gates are easier to realize with electronic components and are, therefore, the basic ingredients used in ali of the logic families. Consequently, it is important for the designer to be familiar with the techniqueS for translating the reduced function so that either NAND gates or NOR gates may be used.
Combinational circuits may be realized using a standardized combinational unit called a multiplexer (MUX). In the MUX some of the input variables are used as input selectors for the unit and the remaining variables are entered as data inputs. Two other devices, read-only memories .(ROMs) and programmable logic arrays (PLAs), are also frequently used to implement combina­ tional networks. This chapter will explore the possibilities of using only one type of gate or one of the modules-MUX, ROM, PAL, or PLA-for the realiz~tion ofcombinational circuits. Such exploration is extremely useful ~use most· designers usually choose to use only one type of basic gate unless there is a particular reason for doing otherwise. After studying this chapter, you should be able to:
o Design combinational circuits using only NAND gates;
97

98

CHAPTER FOUR Implementation of Logic Functions

o Design combinational circuits using only NOR gates;
o Design combinational circuits using single- or multi­
level multiplexers (MUXs);
o Design combinational circuits using read-only memories
(ROMs);
o Design combinational circuits using programmable
logic arrays (PLAs);
o Construct a complex circuit using the outputs of a
known functional unit.

4.2 Universal Logic Elements

In practice many logic circuits are built using only NAND and NOR gates because the basic gates in some of the logic families such as TTL and CMOS are NAND and NOR, respectively. NAND and NOR gates are considered universal logic elements since they both can be easily manipulated to obtain all possible logic func­ tions. This simplification follows directly from, Boolean theorems that we have discussed in the earlier chapters.
A close inspection of the truth table of these two functions, as described in Section 1.7, reveals that the NAND and NOR opera­ tors are duals of each other. Recall also from Chapter 1 that the dual of a Boolean expression is obtained by replacing every OR with AND, AND with OR, 0 with 1, and 1 with O. Six of these dual properties are listed as follows:

NAND
l.a·O=l
2. a:l = a
3. a' a = a
4. a' h = a+ b
5. a. h = a + b
6. a' = a • b

NOR
a+l=O
a+ 0 =a
a+a= a
a + b = a' b
a+ b = a • b
a+b= a+ b

All of the logic functions may be generated using these properties of NAND and NOR logic. The corresponding NAND and NOR logic circuits for various functions are shown in Figure 4.1.
The circuits ofFigure 4.1 show how NAND-and NOR gates may be cascaded to form each of the logic functions NOT, AND, OR, . and X-OR Since either NANDs or NORs may be used to imple­ ment all of the logic operations, designers may prefer to use only . NANDs or only NORs in order to decrease the inventory oflSpare parts. One of the methods by which to realiZe this is the brute force

4.2 Universal Logic Elements

99

FIGURE 4.1 Logic Functions Using NANDs and NORs.

Gate

NAND Circuit

NOT A-QJ-A

NOR Circuit
A-£D-X

A AND
B

A OR
B

A+B

~=L>O-A+B

X-DR A

A

B

B

EXAMPLE4.i
Implement A El) B using only NAND gates.

scheme, where each of the logic operations of the Boolean function is replaced by the corresponding NAND/NOR circuit. Note, how­ ever, that restricting the number of inputs to the gates will not cause any major problem if proper use of the involution and DeMorgan's laws are made.
SOLUTION
There are two different ways to implement this function: (a) using NAND equivalents ofan X-OR gate and ofa NOT gate, and (b) using the NAND equivalents of either the SOP or the POS tenns.
a. The first possibility results in the circuit of Figure 4.2.
h. Otherwise, A El) B can be ~ressed in the SOP fonn as AB
+ All Consequently: the circuit appears as in Figun: 4.3. The
circuit of Figure 4.3 can be reduced further since X = X. There­
fore, the circuit reduces to that of Figure 4.4. Note also that the function could be expressed in the POS form. Consequently, A El)
B = (A + B)(A + B), which leads to another variation of an X­
NOR circuit as shown in Figure 4.5. The circuit of Figure 4.5

100

CHAPTER FOUR Implementation of Logic Functions

FIGURE 4.2

A--'--i
B--+--;
FIGURE 4.3
A~~--~-------;~
B -!---.-------'-------i--i

X-OR

NOT D--A(±)B

NOT

AND

OR

FIGURE 4.4

A--~----------------------~ B--r~------~------------~

may be reduced further by making use of the law of involution. The resulting circuit is shown in Figure 4.6.
The first and the third fonns, as shown in Figures 4.2 and 4.4, require five NAND gates each, and the fifth, as shown in Figure 4.6, requires a total of six. NAND gates.

FIGURE 4.5

4.3 Function Implementation Using NANDs

101

\

A---e>--... NOT
B -......

OR AND

FIGURE 4.6

B - -.....

4.3 Function Implementation Using
NANDs

It is quite easy to realize any SOP function using two levels of NAND gates. This method makes use of the fact that comple­ menting a function twice returns the function to its original form. This result is achieved in two steps:
1. The function is complemented by complementing the ANDed terms and replacing the OR signs with AND signs.
2. The original function is then recovered by complementing the complement function.. "
It is not necessary to perform this operation each time a NAND realization is required. SOP forms always assume the same two­ level NAND form.
The output of a NAND gate is also equivalent to the ORed out­ put of the complements of the input. This statement follows directly from DeMorgan's theorem. Consequently, we are led to the follow­

102

CHAPTER FOUR Implementation of Logic Functions

ing set of rules for obtaining the output function of a multi-level NAND circuit:
Rule 1. Consider the gate from which the output signal is derived as the first level, the preceding gate as the second level, and so on.
Rule 2. In odd-numbered levels the NAND gates perform OR operations. All ungated input variables entering the odd-level NAND gates will appear complemented in the final expression.
Rule 3. In even-numbered levels the NAND gates perform AND operations. All input variables entering the even-level NAND gates will appear uncomplementedin the final expression.

EXAMPLE 4.2

SOLUTION

Using only NAND gates, implement the function given by
f(A,B,C,D) = ABC + ABc + CD

f = ABC + ABc + CD
which yidds
=~=~=
f = ABC' ABc· CD

The final circuit, therefore, is obtained as shown in Figure 4.7. The circuit requires three three-input NAND gates and one two-input NAND gate
provided Band C inputs are also available in the complemented form.

FIGURE 4.7

A B

\r,

C

A h

C

I"'"

f(A,B,C,D)

C

\.

D

4.4 Function Implementation Using
NORs

t,
The implementation of an SOP function using only NOR gates is
possible only if the function is first converted to the equivalent POS form. The process includes the following steps:
1. Plot the function on a K-map and obtain the comple­ mented function by grouping all zeros.

4.4 Function Implementation Using NORs

103

2. Expand each of the ANDed terms by using DeMorgan)s theorem.
3. Complement the whole Boolean expression.

NOR realizations of SOP functions always have the same two-level structure. Steps 1 through 3 should be followed until the designer is confident of the result.
DeMorgan's theorem may be used to interpret the NOR opera­ tion as well. The output of the NOR gate is equivalent to the ANDed output of the complements of the inputs. Rules for the interpretation of multi-level NOR circuits are listed as follows:

Rule 1. Consider the gate from which the output signal is derived

_L·C

as the first level, the preceding gate as the second level, and so on.

Rule 2. In odd-numbered levels the NOR gates perform AND
operations. All ungated input variables entering the odd-level NOR gates will appear complemented in the final-expression.

Rule 3. In even-numbered levels the NOR gates perform OR
operations. Input variables entering the even-level NOR gates will appear uncomplemented in the final Boolean expression.

EXAMPLE 4.3

SOLUTION

Using only NOR gates) implement the function given by
j(A)B)G,D) = ~m(O)2)4)5,8,1O,13)

The minterms are plotted in a four-variable K-map and the corresponding zeros are grouped as shown in Figure 4.8. This gives
J= CD + BC +BD + ABD
=c+D+B+c+B+ +A+B+D

Therefore,
j=C+D+B+C+B+D+A+B+D

FIGURE4.B

A
~

1 1
- W O 1

1
r0­
10

0 0 0 01
,......., I­
100 1

'----y----'
B

The equivalent NOR circuit, therefore, may be obtained as shown in Fig­ ure 4,9. It requires three two-input NOR gates, one three-input NOR gate,