ix
PREFACE 1
11 12 13 14 15 16 17 18 19
2
1
BINARY SYSTEMS Digital Computers and Digital Systems Binary Nu...
5074 downloads
14022 Views
12MB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
ix
PREFACE 1
11 12 13 14 15 16 17 18 19
2
1
BINARY SYSTEMS Digital Computers and Digital Systems Binary Numbers 4 Number Base Conversions 6 Octal and Hexadecimal Numbers 9 Complements 10 Signed Binary Numbers 14 Binary Codes 17 Binary Storage and Registers 25 Binary Logic 28 References 32 Problems 33
1
36
BOOLEAN ALGEBRA AND LOGIC GATES 21 22 23
Basic Definitions 36 Axiomatic Definition of Boolean Algebra 38 Basic Theorems and Properties of Boolean Algebra
41 III
iv
Contents
24 25 26 27 28
3
49
SIMPLIFICATION OF BOOLEAN FUNCTIONS 31 32 33 34 35 36 37 38 39 310 311 312
4
Boolean Functions 45 Canonical and Standard FOnTIS Other Logic Operations 56 Digital Logic Gates 58 Integrated Circuits 62 References 69 Problems 69
The Map Method 72 Two and ThreeVariable Maps 73 FourVariable Map 78 FiveVariable Map 82 Product of Sums Simplification 84 88 NAND and NOR Implementation Other TwoLevel Implementations 94 Don'tCare Conditions 98 101 The Tabulation Method Determination of Prime Implicants 101 Selection of Prime Implicants 106 Concluding Remarks 108 References 110 Problems III
COMBINATIONAL LOGIC 41 42 43 44 45 46 47 48
72
Introduction 114 Design Procedure 115 Adders 116 121 Subtractors 124 Code Conversion Analysis Procedure 126 Multilevel NAND Circuits 130 Multilevel NOR Circuits 138
114
Contents
49
5
152
Introduction 152 Binary Adder and Subtractor 154 Decimal Adder 160 Magnitude Comparator 163 166 Decoders and Encoders Multiplexers 173 ReadOnly Memory (ROM) 180 187 Programmable Logic Array (PLA) 192 Programmable Array Logic (PAL) 197 References Problems 197
202
SYNCHRONOUS SEOUENTIAL LOGIC 61 62 63 64 65 66 67 68
7
142
MSI AND PLD COMPONENTS 51 52 53 54 55 56 57 58 59
6
ExclusiveOR Functions References 148 Problems 149
202 Introduction HipHops 204 210 Triggering of HipFlops Analysis of Clocked Sequential Circuits State Reduction and Assignment 228 HipFlop Excitation Tables 231 Design Procedure 236 Design of Counters 247 References 251 Problems 251
218
REGISTERS, COUNTERS, AND THE MEMORY UNIT 71 72
V
Introduction 257 Registers 258
257
vi
Contents
73 74 75 76 77 78 79
Shift Registers 264 272 Ripple Counters Synchronous Counters 277 Timing Sequences 285 RandomAccess Memory (RAM) Memory Decoding 293 299 ErrorCorrecting Codes References Problems
8
302 303
ALGORITHMIC STATE MACHINES IASMI 81 82 83 84 85 86
9
289
307
Introduction 307 ASM Chart 309 Timing Considerations 312 Control Implementation 317 Design with Multiplexers 323 PLA Control 330 References 336 Problems 337
ASYNCHRONOUS SEQUENTIAL LOGIC 91 92 93 94 95 96 97 98
Introduction 341 Analysis Procedure 343 Circuits with Latches 352 Design Procedure 359 Reduction of State and Flow Tables RaceFree State Assignment 374 Hazards 379 Design Example 385 References 391 Problems 392
341
366
Contents
10
DIGITAL INTEGRATED CIRCUITS 101 102 103 104 105 106 107 108 109
11
399
Introduction 399 Special Characteristics 401 BipolarTransistor Characteristics 406 RTL and DTL Circuits 409 412 TransistorTransistor Logic (TTL) EmmitterCoupled Logic (ECL) 422 MetalOxide Semiconductor (MOS) 424 Complementary MOS (CMOS) 427 CMOS Transmission Gate Circuits 430 References 433 Problems 434
LABORATORY EXPERIMENTS 110 111 112 113 114 115 116 117 118 119 1110 1111 1112 1113 1114 1115 1116 1117 1118
vii
436
Introduction to Experiments 436 Binary and Decimal Numbers 441 Digital Logic Gates 444 Simplification of Boolean Functions 446 447 Combinational Circuits Code Converters 449 Design with Multiplexers 451 Adders and Subtractors 452 FlipFlops 455 Sequential Circuits 458 Counters 459 Shift Registers 461 Serial Addition 464 Memory Unit 465 Lamp Handball 467 ClockPulse Generator 471 Parallel Adder 473 Binary Multiplier 475 Asynchronous Sequential Circuits 477
)
viii
12
Contents
STANDARD GRAPHIC SYMBOLS 121
122 123 124 125
126 127 128
RectangularShape Symbols 479 Qualifying Symbols 482 Dependency Notation 484 Symbols for Combinational Elements Symbols for FlipFlops 489 Symbols for Registers 491 Symbols for Counters 494 Symbol for RAM 496 References 497 Problems 497
479
486
APPENDIX: ANSWERS TO SELECTED PROBLEMS INDEX
499 512
\
Digital Design is concerned with the design of digital electronic circuits. The subject is also known by other names such as logic design, digital logic, switching circuits, and digital systems. Digital circuits are employed in the design of systems such as digital computers, control systems, data communications, and many other applications that require electronic digital hardware. This book presents the basic tools for the design of digital circuits and provides methods and procedures suitable for a variety of digital design applications. Many features of the second edition remain the same as those of the first edition. The material is still organized in the same manner. The first five chapters cover combinational circuits. The next three chapters deal with synchronous clocked sequential circuits. Asynchronous sequential circuits are introduced next. The last three chapters deal with various aspects of commercially available integrated circuits. The second edition, however, offers several improvements over the first edition. Many sections have been rewritten to clarify the presentation. Chapters I through 7 and Chapter 10 have been revised by adding new uptodate material and deleting obsolete subjects. New problems have been formulated for the first seven chapters. These replace the problem set from the first edition. Three new experiments have been added in Chapter II. Chapter 12, a new chapter, presents the IEEE standard graphic symbols for logic elements. The following is a brief description of the subjects that are covered in each chapter with an emphasis on the revisions that were made in the second edition.
Ix
f
X
Preface
Chapter 1 presents the various binary systems suitable for representing information in digital systems. The binary number system is explained and binary codes are illustrated. A new section has been added on signed binary numbers. Chapter 2 introduces the basic postulates of Boolean algebra and shows the correlation between Boolean expressions and their corresponding logic diagrams. All possible logic operations for two variables are investigated and from that, the most useful logic gates used in the design of digital systems are determined. The characteristics of integrated circuit gates are mentioned in this chapter but a more detailed analysis of the electronic circuits of the gates is done in Chapter 11. Chapter 3 covers the map and tabulation methods for simplifying Boolean expressions. The map method is also used to simplify digital circuits constructed with ANDOR, NAND, or NOR gates. All other possible twolevel gate circuits are considered and their method of implementation is summarized in tabular form for easy reference. Chapter 4 outlines the formal procedures for the analysis and design of combinational circuits. Some basic components used in the design of digital systems, such as adders and code converters, are introduced as design examples. The sections on multilevel NAND and NOR implementation have been revised to show a simpler procedure for converting ANDOR diagrams to NAND or NOR diagrams. Chapter 5 presents various medium scale integration (MS!) circuits and programmable logic device (PLD) components. Frequently used digital logic functions such as parallel adders and sub tractors, decoders, encoders, and multiplexers, are explained, and their use in the design of combinational circuits is illustrated with examples. In addition to the programmable read only memory (PROM) and programmable logic array (PLA) the book now shows the internal construction of the programmable array logic (PAL). These three PLD components are extensively used in the design and implementation of complex digital circuits. Chapter 6 outlines the formal procedures for the analysis and design of clocked synchronous sequential circuits. The gate structure of several types of flipflops is presented together with a discussion on the difference between pulse level and pulse transition triggering. Specific examples are used to show the derivation of the state table and state diagram when analyzing a sequential circuit. A number of design examples are presented with added emphasis on sequential circuits that use Dtype flipflops. Chapter 7 presents various sequential digital components such as registers, shift registers, and counters. These digital components are the basic building blocks from which more complex digital systems are constructed. The sections on the random access memory (RAM) have been completely revised and a new section deals with the Hamming error correcting code.
Chapter 8 presents the algorithmic state machine (ASM) method of digital design. The ASM chart is a special flow chart suitable for describing both sequential and parallel operations with digital hardware. A number of design examples demonstrate the use of the ASM chart in the design of state machines. Chapter 9 presents formal procedures for the analysis and design of asynchronous sequential circuits. Methods are outlined to show how an asynchronous sequential cir
\ Preface
xl
cuit can be implemented as a combinational circuit with feedback. An alternate implementation is also described that uses SR latches as the storage elements in an asynchronous sequential circuit. Chapter 10 presents the most common integrated circuit digital logic families. The electronic circuits of the common gate in each faruily is analyzed using electrical circuit theory. A basic knowledge of electronic circuits is necessary to fully understand the material in this chapter. Two new sections are induded in the second edition. One section shows how to evaluate the numerical values of four electrical characteristics of a gate. The other section introduces the CMOS transmission gate and gives a few examples of its usefulness in the construction of digital circuits. Chapter 11 outlines 18 experiments that can be performed in the laboratory with hardware that is readily and inexpensively available commercially. These experiments use standard integrated circuits of the TTL type. The operation of the integrated circuits is explained by referring to diagrams in previous chapters where siruilar components are originally introduced. Each experiment is presented informally rather than in a stepbystep fashion so that the student is expected to produce the details of the circuit diagram and formulate a procedure for checking the operation of the circuit in the laboratory. Chapter 12 presents the standard graphic symbols for logic functions recommended by ANSI/IEEE standard 911984. These graphic symbols have been developed for SSI and MSI components so that the user can recognize each function from the unique graphic symbol assigned to it. The best time to learn the standard symbols is while learning about digital systems. Chapter 12 shows the standard graphic symbols of all the integrated circuits used in the laboratory experiments of Chapter 11. The various digital componets that are represented throughout the book are similar to commercial MSI circuits. However. the text does not mention specific integrated circuits except in Chapters 11 and 12. The practical application of digital design will be enhanced by doing the suggested experiments in Chapter 11 while studying the theory presented in the text. Each chapter in the book has a list of references and a set of problems. Answers to most of the problems appear in the Appendix to aid the student and to help the independent reader. A solutions manual is available for the instructor from the publisher. M. Morris Mano
Binary' $ystems
1·1
DIGITAL COMPUTERS AND DIGITAL SYSTEMS Digital computers have made possible many scientific, industrial, and commercial advances that would have been unattainable otherwise. Our space program would have been impossible without realtime, continuous computer monitoring, and many business enterprises function efficiently only with the aid of automatic data processing. Computers are used in scientific calculations, commercial and business data processing, air traffic control, space guidance, the educational field, and many other areas. The most striking property of a digital computer is its generality. It can follow a sequence of instructions, called a program, that operates on given data. The user can specify and change programs and/or data according to the specific need. As a result of this flexibility, generalpurpose digital computers can perform a wide variety of informationprocessing tasks. The generalpurpose digital computer is the bestknown example of a digital system. Other examples include telephone switching exchanges, digital voltmeters, digital counters, electronic calculators, and digital displays. Characteristic of a digitaLsYstem is its manipulation. of discrete elements of information: SlicIi(JJscreteeiemenis may be . electric impulses, th;;decimaf x' (c) NOT gate or inverter
~~ABC ~~A+B+C+D (d) Three input AND gate FIGURE 16 Symbols for digital logic circuits
(e) Four input OR gate
32
Chapter 1
Binary Systems
°
x )'
AND: x . J'
OR,,+) NOT,
~,'
0
~
,O''0:..J1 ,O'_'0...JrT"l
0
0
~
n °
0
I
I
FIGURE 17 Inputoutput signF
4
(d)
F4
=
xy'
+ x'z.,
FIGURE 24 Implementation of Boolean functions with gates
shall narrow the minimization criterion to literal minimization. We shall discuss other criteria in Chapter 5. The number of literals in a Boolean function can be minimized by algebraic manipulations. Unfortunately, there are no specific rules to follow that will guarantee the final answer. The only method available is a cutandtry procedure employing the postulates, the basic theorems, and any other manipulation method that becomes familiar with use. The following examples illustrate this procedure.
Example 21
Simplify the following Boolean functions to a minimum number of literals. 1, x + x 'y ~ (x + x ')(x + y) ~ I  (x + y) ~ x 2. x(x' + y) = xx' + xy = 0 + xy = xy
+Y
48
Chapter 2
Boolean Algebra and Logic Gates
3. x'y'z + x'yz + xy' = x'z(y' + y) + xy 4. xy + x' z + yz = xy + x' z + yz (x + x') = xy + X 'z + xyz + X yz = xy(1 + z) + x'z(J + y)
=
x'z + xy
I
= xy
5. (x
+
+
y)(x'
+
z)(y
+ x1z z) = (x
+
y)(x'
+
z) by duality from function 4.
•
Functions I and 2 are the duals of each other and use dual expressions in corresponding steps. Function 3 shows the equality of the functions F3 and F4 discussed previously. The fourth illustrates the fact that an increase in the number of literals sometimes leads to a final simpler expression. Function 5 is not minimized directly but can be derived from the dual of the steps used to derive function 4.
Complement of a Function
The complement of a function F is F' and is obtained from an interchange of O's for I's and l's for D's in the value of F. The complement of a function may be derived algebraically through DeMorgan's theorem. This pair of theorems is listed in Table 2 I for two variables. DeMorgan's theorems can be extended to three or more variables. The threevariable form of the first DeMorgan's theorem is derived below. The postulates and theorems are those listed in Table 21. (A
+
B
+
C)'
= (A + =
letB
X)'
A'X'
+
C = X
by theorem 5(a) (DeMorgan)
= A'· (B +
C)'
substitute B + C = X
=A"(B'C')
by theorem 5(a) (DeMorgan)
= A'B'C'
by theorem 4(b) (associative)
DeMorgan's theorems for any number of variables resemble in form the two variable case and can be derived by successive substitutions similar to the method used in the above derivation. These theorems can be generalized as follows: (A
+
B
+
C
+
D
(ABCD ... Fl' =
+ ... + F)' = A'B'C'D'" . F' A' + B' + C' + D' + ... + F'
The generalized form of DeMorgan's theorem states that the complement of a function is obtained by interchanging AND and OR operators and complementing each literal.
Example 22
Find the complement of the functions F, = x'yz' + x'y'zandf; = x(y'z' + yz). By applying DeMorgan's theorem as many times as necessary, the complements are obtained as follows:
Section 25
Canonical and Standard Forms
49
F; = (x'yz' + x'y'z)' = (x'yz')'(x'y'z)' = (x + y' + z)(x + Y + z')
F; = =
+ yz)]' = x' + + (y + z)(y' + z ')
[x(y'z' x'
(y'z'
+
yz)' = x'
+
(y'z')'· (yz)'
•
A simpler procedure for deriving the complement of a function is to take the dual of the function and complement each literal. This method follows from the generalized DeMorgan's theorem. Remember that the dual of a function is obtained from the interchange of AND and OR operators and 1's and O's.
Example 23
Find the complement of the functions FJ and F, of Example 22 by taking their duals and complementing each literal. 1. FJ = x'yz' + x'y'z. The dual of FJ is (x' + Y
+ z')(x' + y' + z). + y' + z)(x + Y +
Complement each literal: (x 2.
F, = x(y'z'
The dual of F, is x + (y' + z')(y + z). Complement each literal: x' + (y + z)(y' 2·5
z ') = F; .
+ yz).
+ z ')
=
F; .
•
CANONICAL AND STANDARD FORMS
Minterms and Maxterms
A binary variable may appear either in its normal form (x) or in its complement form (x '). Now consider two binary variabes x and y combined with an AND operation. Since each variable may appear in either form, there are four possible combinations: x' y " x' y, xy', and xy. Each of these four AND terms represents one of the distinct areas in the Venn diagram of Fig. 21 and is called a minterm, or a standard product. In a similar manner, n variables can be combined to form 2" minterms. The 2" different minterms may be determined by a method similar to the one shown in Table 23 for three variables. The binary numbers from 0 to 2"  I are listed under the n variables. Each minterm is obtained from an AND term of the n variables, with each variable being primed if the corresponding bit of the binary number is a 0 and unprimed if a I. A symbol for each min term is also shown in the table and is of the form mj, where j denotes the decimal equivalent of the binary number of the min term designated. In a similar fashion, n variables forming an OR term, with each variable being primed or unprimed, provide 2" possible combinations, called maxterms, or standard sums. The eight maxterms for three variables, together with their symbolic designation, are listed in Table 23. Any 2" maxterms for n variables may be determined similarly. Each maxterm is obtained from an OR term of the n variables, with each variable being unprimed if the corresponding bit is a 0 and primed if a I. Note that each maxterm is the complement of its corresponding minterm, and vice versa.
50
Chapter 2
Boolean Algebra and Logic Gates
TABLE 23 Minterms and Maxterms for Three Binary VarIables
Minterms x
z
y
Term
Designation

0 0
a
0 0
a 0
I
I
0 0
0 I
0
Term
Designation
,,.
x'y'z' x'y'z X'yz' x'yz xy'z' xy'Z xyz I xyz
0
Maxterms
x + Y+ z
rn" rn, rn, m,
x
+
Y
+
z'
X+y'+Z X+y'+Z' x' + y + z x + Y + z' x' + y' + z x + y' + z'
m, m, m, m,
A Boolean function may be expressed algebraically from a given truth table by forming a min term for each combination of the variables that produces a 1 in the function, and then taking the OR of all those terms. For example, the function 11 in Table 24 is determined by expressing the combinations 00 1, 100, and III as x' y 'z, xy 'z ' , and xyz, respectively. Since each one of these minterms results in 11 = 1, we should have
il
+
= x'y'z
xy'z'
+
xyz = mt
+ m4 + m7
+
xyz = m,
+ ms + mo + m7
Similarly, it may be easily verified that }2
= x' yz +
xy' z
+
xyz'
These examples demonstrate an important property of Boolean algebra: Any Boolean function can be expressed as a sum of min terms (by "sum" is meant the ORing of terms) . TABLE 24 Functions of Three Variables .
x
_.__..
y
z
Function " ..
.

~.
Function .
0
0
0
0
0
0
0
I
I
0 0
1
a
0 0
0 0 I
0
1
0
0
a
1
0
0
0
'1
Section 2·5
Canonical and Standard Forms
51
Now consider the complement of a Boolean function. It may be read from the truth table by forming a min term for each combination that produces a 0 in the function and then ORing those terms. The complement of/I is read as
Ii
+ x'yz' + x'yz + xy'z + xyzl
= x'y'z'
If we take the complement of /:, we obtain the function /I:
/1
=
(x
+
y
+ z)(x +
y'
+ z)(x +
y'
+ z ')(x' + Y + z ')(x' +
y'
+ z)
= M o·M2 ·M,·M,·M,
Similarly, it is possible to read the expression for /' from the table:
f,
=
(x
+ Y + z)(x + Y + z ')(x + y' + z)(x' + Y + z)
= MoMIM,M4
These examples demonstrate a second important property of Boolean algebra: Any Boolean function can be expressed as a product of maxterms (by "product" is meant the ANDing of terms). The procedure for obtaining the product of maxterms directly from the truth table is as follows. Form a maxterm for each combination of the variables that produces a 0 in the function, and then form the AND of all those maxterms. Boolean functions expressed as a sum of min terms or product of maxterms are said to be in canonical form.
Sum of Minterms
It was previously stated that for n binary variables, one can obtain 2" distinct minterms,
and that any Boolean function can be expressed as a sum of min terms. The minterms whose sum defines the Boolean function are those that give the I 's of the function in a truth table. Since the function can be either I or 0 for each minterm, and since there are 2" min terms, one can calculate the possible functions that can be formed with n variables to be 2'". It is sometimes convenient to express the Boolean function in its sum of minterms form. If not in this form, it can be made so by first expanding the expression into a sum of AND terms. Each term is then inspected to see if it contains all the variables. If it misses one or more variables, it is ANDed with an expression such as x + x', where x is one of the missing variables. The following examples clarifies this procedure.
Example 24
Express the Boolean function F = A + B 'C in a sum of minterms. The function has three variables, A, B, and C. The first term A is missing two variables; therefore: A = A (B
This is still missing one variable:
+
B ') = AB
+
AB'
52
Chapter 2
Boolean Algebra and Logic Gates
+ C') + AB'(C + C') = ABC + ABC' + AB'C + AB'C' AB(C
A =
The second term B 'e is missing one variable:
B'C = B'C(A
+ A') =
AB'C
+ A'B'C
Combining all terms, we have F=A+B'C
+ ABC' + AB'C + AB'C' + AB'C + A'B'C But AB 'C appears twice, and according to theorem I (x + x = x), it is possible to re= ABC
move one of them. Rearranging the min terms in ascending order, we finally obtain
F = A'B'C
+ AB'C' + AB'C + ABC' + ABC
•
It is sometimes convenient to express the Boolean function, when in its sum of min terms , in the following short notation:
F(A, B, C) = L(l, 4, 5, 6, 7)
The summation symbol L stands for the ~Ring of terms: the numbers following it are the min terms of the function, The letters in parentheses following F form a list of the variables in the order taken when the min term is converted to an AND term, An alternate procedure for deriving the min terms of a Boolean function is to obtain the truth table of the function directly from the algebraic expression and then read the minterms from the truth table. Consider the Boolean function given in Example 24: F = A
+ B'C
The truth table shown in Table 25 can be derived directly from the algebraic expression by listing the eight binary combinations under variables A, B, and C and inserting
Section 25
Canonical and Standard Forms
53
I's under F for those combinations where A = I, and Be = 01. From the truth table, we can then read the five minterms of tbe function to be 1, 4, 5, 6, and 7. Product of Maxterms
Each of the 2'" functions of n binary variables can be also expressed as a product of maxterms. To express the Boolean function as a product of maxterms, it must fitst be brought into a form of OR terms. This may be done by using the distributive law, x + yz = (x + y)(x + z). Then any missing variable x in each OR term is ORed with xx'. This procedure is clarified by the following example. ~~
Example 25
Express the Boolean function F = xy + x'z in a product of maxterm form. First, con· vert the function into OR terms using the distributive law:
F
= xy + x' z = (xy + x ')(xy + z) = (x + x')(y + x')(x + z)(y + z) = (x' + y)(x + z)(y + z)
The function has three variables: x, y, and z. Each OR term is missing one variable; therefore: x'
+ Y = x' + Y + zz' = x + z = x + z + yy' = Y + z = Y + z + xx' =
(x' (x (x
+ Y + z)(x' + Y + z ') + y + z)(x + y' + z) + Y + z)(x' + Y + z)
Combining all the terms and removing those that appear more than once, we finally ob· tain: F = (x =
+Y+
z)(x
+
y'
+
z)(x'
+Y+
z)(x'
MoM,M.M,
A convenient way to express this function is as follows: F(x, y, z) =
n (0,
+ Y + z ')
•
2, 4, 5)
The product symbol, n, denotes the ANDing of maxterms; the numbers are the max· terms of the function. Conversion between Canonical Forms
The complement of a function expressed as the sum of minterms equals the sum of minterms missing from the original function. This is because the original function is expressed by those minterms that make the function equal to 1, whereas its comple· ment is a I for those minterms that the function is a O. As an example, consider the function
54
Chapter 2
Boolean Algebra and Logic Gates
F(A, 8, C)
= ~(1,
4, 5, 6, 7)
This has a complement that can be expressed as F'(A, 8, C) = ~«(), 2, 3) = rno
+ rn, + rn3
Now, if we take the complement of F' by DeMorgan's theorem, we obtain F in a different form: F = (rno
+ m, + m3)'
=
mi,'
m,·
m; = MuM2Ml = II(O, 2, 3)
The last conversion follows from the definition of min terms and maxterms as shown in Table 23. From the table, it is clear that the following relation holds true:
That is, the maxterm with subscript.i is a complement of the minterm with the same subscript j, and vice versa. The last example demonstrates the conversion between a function expressed in sum of minterms and its equivalent in product of maxterms. A similar argument will show that the conversion between the product of maxterms and the sum of minterms is similar. We now state a general conversion procedure. To convert from one canonical form to another, interchange the symbols ~ and n and list those numbers missing from the original form. In order to find the missing terms, one must realize that the total number of min terms or maxterms is 2", where n is the number of binary variables in the function. A Boolean function can be converted from an algebraic expression to a product of maxterms by using a truth table and the canonical conversion procedure. Consider, for example, the Boolean expression F
= xy +
x'z
First, we derive the truth table of the function, as shown in Table 26. The l's under F in the table are determined from the combination of the variable where xy = 11 and TABLE 2~6 Truth Table for F
~~
xy + x' z
x
y
z
F
0 0 0 0 1
0 0
0
0
I
0
0
I
I
I
0 0
0
0 0
0
Section 25
Canonical and Standard Forms
55
xz = 01. The minterms of the function are read from the truth table to be 1,3,6, and
7. The function expressed in sum of min terms is F(x, y, z) = L(l, 3, 6, 7)
Since there are a total of eight minterms or maxterms in a function of three variable, we determine the missing terms to be 0, 2, 4, and 5. The function expressed in product of maxterm is
F(x, y, z) = Il(O, 2, 4, 5)
This is the same answer obtained in Example 25. Standard Forms
The two canonical forms of Boolean algebra are basic forms that one obtains from reading a function from the truth table. These forms are very seldom the ones with the least number of literals, because each minterm or maxterm must contain, by definition, all the variables either complemented or uncomplemented. Another way to express Boolean functions is in standard form. In this configuration, the terms that form the function may contain one, two, or any number of literals. There are two types of standard forms: the sum of products and product of sums. The sum of products is a Boolean expression containing AND terms, called product terms, of one or more literals each. The sum denotes the ORing of these terms. An example of a function expressed in sum of products is F\ = Y I
+
xy
+
X'yzl
The expression has three product terms of one, two, and three literals each, respectively. Their sum is in effect an OR operation. A product of sums is a Boolean expression containing OR terms, called sum terms. Each term may have any number of literals. The product denotes the ANDing of these terms. An example of a function expressed in product of sums is F, = x(y'
+
z)(x'
+
Y
+ z' +
w)
This expression has three sum terms of one, two, and four literals each, respectively. The product is an AND operation. The use of the words product and sum stems from the smiilarity of the AND operation to the arithmetic product (multiplication) and the similarity of the OR operation to the arithmetic sum (addition). A Boolean function may be expressed in a nonstandard form. For example, the function
F3
= (AB + CD)(A'B' + CD')
is neither in sum of products nor in product of sums. It can be changed to a standard form by using the distributive law to remove the parentheses: F, = A'B'CD + ABC'D'
56
26
Chapter 2
Boolean Algebra and Logic Gates
OTHER LOGIC OPERATIONS
When the binary operators AND and OR are placed between two variables, x and y, they form two Boolean functions, x' y and x + y, respectively. It was stated previously that there are 22 ' functions for n binary variables. For two variables, n ~ 2, and the number of possible Boolean functions is 16. Therefore, the AND and OR functions are only two of a total of 16 possible functions formed with two binary variables. It would be instructive to find the other 14 functions and investigate their properties. The truth tables for the 16 functions formed with two binary variables, x and y, are listed in Table 27. In this table, each of the 16 columns, F" to F15 , represents a truth table of one possible function for the two given variables, x and y. Note that the functions are determined from the 16 binary combinations that can be assigned to F. Some of the functions are shown with an operator symbol. For example, FI represents the truth table for AND and F, represents the truth table for OR. The operator symbols for these functions are . and
+, respectively.
Truth Tables for the 16 Functions of Two Binary Variables
o o
0
1
U
0
o o o o o o o
o
o
o
0
o
1
o o
1
o o
o
o
o
o
I0
_~~:;~~~l . .
u
1
1
+
o
o
o
1
o
o
o
o
o
1
c
0
1
o .
__ t . __
..
The 16 functions listed in truth table form can be expressed algebraically by means of Boolean expressions. This is shown in the first column of Table 28. The Boolean expressions listed are simplified to their minimum number of literals. Although each function can be expressed in terms of the Boolean operators AND, OR, and NOT, there is no reason one cannot assign special operator symbols for expressing the other functions. Such operator symbols are listed in the second column of Table 28. However, all the new symbols shown, except for the exclusive·OR symbol, EEl, arc not in common use by digital designers. Each of the functions in Table 28 is listed with an accompanying name and a comment that explains the function in some way. The 16 functions listed can be subdivided into three categories:
1. Two functions that produce a constant 0 or 1. 2. Four functions with unary operations: complement and transfer.
3. Ten functions with binary operators that define eight different operations: AND, OR, NAND. NOR, exclusive·OR, equivalence, inhibition, and implication.
Section 26
Other Logic Operations
57
TABLE 28 Boolean Expressions for the 16 Functions of TWo Variables
Boolean functions
Operator
Name
Comments
sym.bol
Fo Fl F2 F3 F4 F, F6
=0 = = = =
xy xy' x x'Y =y =xy ' +X'y
F7 = x + Y F. = (x + y)' F9 = xy + x'y' FIO=y' Fll =x+y' Fl2 = x' F13=X'+Y F" = (xy) , Fis = 1
x'y x/y y/x x$y x+y
xh x8y y' xCy x' x :::J y xfy
Null AND Inhibition Transfer Inhibition Transfer
ExclusiveOR OR NOR Equivalence Complement Implication
Complement Implication
NAND Identity
Binary constant 0 x andy x but not y x Y but not x y x or y but not both xory
NotOR x equals y Noty If y then x Not x If x then y
NotAND Binary constant I
Any function can be equal to a constant, but a binary function can be equal to only I or O. The complement function produces the complement of each of the binary variables. A function that is equal to an input variable has been given the name transfer, because the variable x or y is tmnsferred through the gate that forms the function without changing its value. Of the eight binary opemtors, two (inhibition and implication) are used by logicians but are seldom used in computer logic. The AND and OR operators have been mentioned in conjunction with Boolean algebra. The other four functions are extensively used in the design of digital systems. The NOR function is the complement of the OR function and its name is an abbreviation of notOR. Similarly, NAND is the complement of AND and is an abbreviation of notAND. The exclusiveOR, abbreviated XOR or EOR, is similar to OR but excludes the combination of both x and y being equal to 1. The equivalence is a function that is I when the two binary variables are equal, i.e., when both are 0 or both are 1. The exclusiveOR and equivalence functions are the complements of each other. This can be easily verified by inspecting Table 27. The truth table for the exclusiveOR is F6 and for the equivalence is F" and these two functions are the complements of each other. For this reason, the equivalence function is often called exclusiveNOR, i.e., exclusiveORNOT. Boolean algebra, as defined in Section 22, has two binary operators, which we have called AND and OR, and a unary operator, NOT (complement). From the definitions,
58
Chapter 2
Boolean Algebra and Logic Gates
we have deduced a number of properties of these operators and now have defined other binary operators in terms of them. There is nothing unique about this procedure. We could have just as well started with the operator NOR (j, ), for example, and later defined AND, OR, and NOT in terms of it. There are, nevertheless, good reasons for introducing Boolean algebra in the way it has been introduced. The concepts of "and," "or," and "not" are familiar and are used by people to express everyday logical ideas. Moreover, the Huntington postulates refiect the dual nature of the algebra, emphasizing the symmetry of + and . with respect to each other. 2·7
DIGITAL LOGIC GATES
Since Boolean functions are expressed in terms of AND, OR, and NOT operations, it is easier to implement a Boolean function with these types of gates. The possibility of constructing gates for the other logic operations is of practial interest. Factors to be weighed when considering the construction of other types of logic gates are (I) the feasibility and economy of producing the gate with physical components, (2) the possibility of extending the gate to more than two inputs, (3) the basic properties of the binary operator such as commutativity and associativity, and (4) the ability of the gate to implement Boolean functions alone or in conjunction with other gates. Of the 16 functions defined in Table 28, two are equal to a constant and four others are repeated twice. There are only ten functions left to be considered as candidates for logic gates. Two, inhibition and implication, are not commutative or associative and thus are impractical to use as standard logic gates. The other eight: complement, transfer, AND, OR, NAND, NOR, exclusiveOR, and equivalence, are used as standard gates in digital design. The graphic symbols and truth tables of the eight gates are shown in Fig. 25. Each gate has one or two binary input variables designated by x and y and one binary output variable designated by F. The AND, OR, and inverter circuits were defined in Fig. 16. The inverter circuit inverts the logic sense of a binary variable. It produces the NOT, or complement, function. The small circle in the output of the graphic symbol of an inverter designates the logic complement. The triangle symbol by itself designates a buffer circuit. A buffer produces the transfer function but does not produce any particular logic operation, since the binary value of the output is equal to the binary value of the input. This circuit is used merely for power amplification of the signal and is equivalent to two inverters connected in cascade. The NAND function is the complement of the AND function, as indicated by a graphic symbol that consists of an AND graphic symbol followed by a small circle. The NOR function is the complement of the OR function and uses an OR graphic symbol followed by a small circle. The NAND and NOR gates are extensively used as standard logic gates and are in fact far more popular than the AND and OR gates. This is because NAND and NOR gates are easily constructed with transistor circuits and because Boolean functions can be easily implemented with them.
Section 2·7
Name
AND
OR
Inverter
Buffer
NAND
NOR
ExclusiveOR
(XOR)
Graphic symbol
:=OF
:=D F x
{» F
X{>F ~=DF ~=L>F
:=jDF
Exclus~tNOR ; ~ _F equivalence ~ FIGURE 25 Digital logic gates
Digital Logic Gates
Algebraic function
F= xy
Fx+y
Truth table
x
y
F
0 0 I I
0 I 0 I
0 0 0 I
x
y
F
0 0 I I
0 I 0 I
0 I I I
itt o
F x'
I 0
I
itt o
F=x
0 I
I
F  (xy),
F = (x
+ y)'
F= xy' + x'y x$y
F= xy
+ x'y'
=x0y
x 0 0 I I
Y
F
0 I 0 I
I I I 0
x 0 0 I I
Y
F
0 I 0 I
I 0 0 0
x 0 0 I I
Y
F
0 I 0 I
0 I I 0
~~ 001 010 100 I I I
59
60
Chapter 2
Boolean Algebra and Logic Gates
The exclusiveOR gate has a graphic symbol similar to that of the OR gate, except for the additional curved line on the input side. The equivalence, or exclusiveNOR, gate is the complement of the exclusiveOR. as indicated by the small circle on the output side of the graphic symbol. Extension to Multiple Inputs
The gates shown in Fig. 25, except for the inverter and buffer, can be extended to have more than two inputs. A gate can be extended to have multiple inputs i[ the binary operation it represents is commutative and associative. The AND and OR operations, defined in Boolean algebra, possess these two properties. For the OR function, we have commutative
x+y=y+x
and (x
+
y)
+
z = x
+ (y +
z) = x
+ \' +
associative
z
which indicates that the gate inputs can be interchanged and that the OR function can be extended to three or more variables. The NAND and NOR functions are commutative and their gates can be extended to have more than two inputs, provided the definition of the operation is slightly modified. The difficulty is that the NAND and NOR operators are not associative, i.e., (x ~ v) z '" x (y z), as shown in Fig. 26 and below:
t
t
(x
t y) ~ z =
x t(y tz)
x
t
=
[(x
[x
+ v)' + z]' = + (y + zJ,], =
(x
+
x'(y
= + z) = y)z'
+ \'z' x'y + x'z
xz'
_t, L."
)o(x lv) i :
(x  yl z'
x    _ _ _ _~...,
)Ox i (
~'~
;,:)  x' (y i :)
FIGURE 26
Dernonstratlnq the nOJldssoclativlty of trl(' Nor,.' operator: IX
i
yl 12 (
1/ l'
J .~I
Section 27
Digital Logic Gates
61
To overcome this difficulty, we define the multiple NOR (or NAND) gate as a complemented OR (or AND) gate. Thus, by definition, we have x
1 y 1z =
x l' y l' z
=
(x
+
+ z)'
y
(xyz) ,
The graphic symbols for the 3input gates are shown in Fig. 27. In writing cascaded NOR and NAND operations, one must use the correct parentheses to signify the proper sequence of the gates. To demonstrate this, consider the circuit of Fig. 27(c). The Boolean function for the circuit must be written as
F
=
[(ABC)'(DE)']'
=
ABC
+ DE
The second expression is obtained from DeMorgan's theorem. It also shows that an expression in sum of products can be implemented with NAND gates. Further discussion of NAND and NOR gates can be found in Sections 36, 47, and 48. The exclusiveOR and equivalence gates are both commutative and associative and can be extended to more than two inputs. However, multipleinput exclusiveOR gates are uncommon from the hardware standpoint. In fact, even a 2input function is usually constructed with other types of gates. Moreoever, the definition of the function must be modified when extended to more than two variables. The exclusiveOR is an odd function, i.e., it is equal to I if the input variables have an odd number of I's. The construction of a 3input exclusiveOR function is shown in Fig. 28. It is normally implemented by cascading 2input gates, as shown in (a). Graphically, it can be represented with a single 3input gate, as shown in (b). The truth table in (c) clearly indicates that the output F is equal to I if only one input is equal to 1 or if all three inputs are equal to I, i.e., when the total number of l's in the input variables is odd. Further discussion of exclusiveOR can be found in Section 49. x~
i'~(x+y+z)'
(a) Threeinput NOR gate
r=c>
(xyz)'
(b) Threeinput NAND gate
A    J .........
B
):>,
C.....,_~
~F=
[(ABC)' . (DE)'I' =ABC+ DE
D    J .........
E
»' (c) Cascaded NAND gates
FIGURE 2·7
Multipleinput and cascaded NOR and NAND gates
62
Chapter 2
Boolean Algebra and Logic Gates
'~ F="I;"'J'J"~
"
~
(a) Using 2input gates
0
0 0 I I I I
(b) 3input gate
F
r
0
0 0 I I 0 0 I I
0 I ()
0 I I
I 0 I
()
0
0
I 0
I
(e) Truth tahle
FIGURE 28 3input pxciuslveOR gate
28
INTEGRATED CIRCUITS Digital circuits are constructed with integrated circuits. An integrated circuit (abbreviated IC) is a small silicon semiconductor crystal, called a chip. containing the electronic components for the digital gates. The various gates are interconnected inside the chip to form the required circuit. The chip is mounted in a ceramic or plastic container, and connections are welded to external pins to form the integrated circuit. The number of pins may range from 14 in a small IC package to 64 or more in a larger package. The size of the IC package is very small. For example, four AND gates are enclosed inside a 14pin IC package with dimensions of 20 x 8 x 3 millimeters. An entire microprocessor is enclosed within a 64pin IC package with dimensions of 50 x 15 x 4 millimeters. Each IC has a numeric designation printed on the surface of the package for identification. Vendors publish data books that contain descriptions and all other information about the ICs thai they manufacture.
Levels of Integration
Digital ICs are often categorized according to their circuit complexity as measured by the number of logic gates in a single package. The differentiation between those chips that have a few internal gates and those having hundreds or thousands of gates is made by a customary reference to a package as being either a small, medium, large, or very largescale integration device. Smallscale integration (SSI) devices contain several independent gates in a single package. The inputs and outputs of the gates are connected directly to the pins in the package. The number of gates is usually fewer than 10 and is limited by the number of pins available in the IC. Mediumsale integration (MSI) devices have a complexity of approximately 10 to 100 gates in a single package. They usually perform specific elementary digital operations such as decoders, adders, or multiplexers. MSI digital components are introduced in Chapters 5 and 7.
Section 28
Integrated Circuits
63
Largescale integration (LSI) devices contain between 100 and a few thousand gates in a single package. They include digital systems such as processors, memory chips, and programmable logic devices. Some LSI components are presented in Chapters 5 and 7. Very largescale integration (VLSI) devices contain thousands of gates within a single package. Examples are large memory arrays and complex microcomputer chips. Because of their small size and low cost, VLSI devices have revolutionized the computer system design technology, giving the designer the capabilities to create structures that previously were uneconomical.
Digital Logic Families
Digital integrated circuits are classified not only by their complexity or logical operation, but also by the specific circuit technology to which they belong. The circuit technology is referred to as a digital logic fumily. Each logic fumily has its own basic electronic circuit upon which more complex digital circuits and components are developed. The basic circuit in each technology is a NAND, NOR, or an inverter gate. The electronic components used in the construction of the basic circuit are usually used as the name of the technology. Many different logic families of digital integrated circuits have been introduced commercially. The following are the most popular: TTL ECL MOS CMOS
transistortransistor logic emitercoupled logic metaloxide semiconductor complementary metaloxide semiconductor
TTL is a widespread logic family that has been in operation for some time and is considered as standard. ECL has an advantage in systems requiring highspeed operation. MOS is suitable for circuits that need high component density, and CMOS is preferable in systems requiring low power consumption. The analysis of the basic electronic digital gate circuit in each logic fumily is presented in Chapter 10. The reader familiar with basic electronics can refer to Chapter 10 at this time to become acquainted with these electronic circuits. Here we restrict the discussion to the general properties of the various IC gates available commercially. The transistortransistor logic fumily evolved from a previous technology that used diodes and transistors for the basic NAND gate. This technology was called DTL for diodetransistor logic. Later the diodes were replaced by transistors to improve the circuit operation and the name of the logic fumily was changed to TTL. Emittercoupled logic (ECL) circuits provide the highest speed among the integrated digital logic families. ECL is used in systems such as supercomputers and signal processors, where high speed is essential. The transistors in ECL gates operate in a nonsaturated state, a condition that allows the achievement of propagation delays of I to 2 nanoseconds.
64
Chapter 2
Boolean Algebra and Logic Gates
The metaloxide semiconductor (MOS) is a unipolar transistor that depends upon the flow of only one type of carrier, which may be electrons (nchannel) or holes (pchannel), This is in contrast to the bipolar transistor used in TTL and ECL gates, where both carriers exist during normal operation. A pchannel MOS is referred to as PMOS and an nchannel as NMOS. NMOS is the one that is commonly used in circuits with only one type of MOS transistor. Complementary MOS (CMOS) technology uses one PMOS and one NMOS transistor connected in a complementary fashion in all circuits. The most important advantages of MOS over bipolar transistors are the high packing density of circuits, a simpler procesing technique during fabrication, and a more economical operation because of the low power consumption. The characteristics of digital logic families are usually compared by analyzing the circuit of the basic gate in each family. The most important parameters that are evaluated and compared are discussed in Section 102. They are listed here for reference. Fanout specifies the number of standard loads that the output of a typical gate can drive without impairing its normal operation. A standard load is usually defined as the amount of current needed by an input of another similar gate of the same family. Power dissipation is the power consumed by the gate that must be available from the power supply. Propagation delay is the average transition delay time for the signal to propagate from input to output. The operating speed is inversely proportional to the propagation delay. Noise margin is the minimum external noise voltage that causes an undesirable change in the circuit output. IntegratedCircuit Gates
Some typical SS] circuits are shown in Fig. 29. Each IC is enclosed within a 14 or 16pin package. A notch placed on the left side of the package is used to reference the pin numbers. The pins are numbered along the two sides starting from the notch and continuing counterclockwise. The inputs and outputs of the gates are connected to the package pins, as indicated in each diagram. TTL Ie's are usually distinguished by their numerical designation as the 5400 and 7400 series. The former has a wide operating temperature range, suitable for military use, and the latter has a narrower temperature range, suitable for commercial use. The numeric designation of 7400 series means that IC packages arc numbered as 7400, 7401,7402, etc. Fig. 29(a) shows two TTL SSI circuits. The 7404 provides six (hex) inverters in a package. The 7400 provides four (quadruple) 2input NAND gates. The terminals marked Vee and GRD (ground) are the powersupply pins that require a voltage of 5 volts for proper operation. The two logic levels for TTL are 0 and 3.5 volts. The TTL logic family actually consists of several subfamilies or series. Table 29 lists the name of each series and the prefix designation that identifies the IC as being part of that series. As mentioned before, ICs that are part of the standard TTL have an
Vee 14
Vee
14
13
12
11
10
9
2
3
4
5
6
8
13
12
11
10
9
2
3
4
5
6
7
GND
8
7
GND
7404Hex inverters
7400 Quadruple 2input NAND gates (a) TTL gates. V CC2
VCC2
16
15
14
13
12
11
10
2
3
4
5
6
7
9
16
8
VCC ]
VEE
15
14
13
12
2
3
4
5
11
10
6
7
8 VEt:
NC'
VCCl
9
10107 Triple exclusiveOR/NOR gates 10102 ·Quadruple 2input NOR gates (b) ECL gates. VDD
14
NC 8
NC' 16
6 NC Vss 4002Dual4input NOR gates.
VDD
13
12
11
10
9
15
14
NC 13
12
11
10
9
4050Hex buffers.
(c) CMOS gates.
FIGURE 29
Some typical integratedcircuit gates
65
66
Chapter 2
Boolean Algebra and Logic Gates
TABLE 2~9 Various Series of the nL Logic Family
TTL Series
Prefix
Example
Standard TTL Highspeed TTL
74 74H 74L 74S 74LS 74AS 74ALS
7486 74H86 74L86 74S86 74LS86 74AS86 74ALS86
Lowpower TTL
Schottky TTL Lowpower Schottky TTL Advanced Schottky TTL Advanced Lowpower Schottky TTL         , .  . . .
,_.
.  . _   ..
identification number that starts with 74. Likewise, ICs that are part of the highspeed TTL series have an identification number that starts with 74H, rcs in the Schottky TTL series start with 74S, and similarly for the other series. The different characteristics of the various TTL series are listed in Table 102 in Chapter 10. The differences between the various TTL series are in their electrical characteristics, such as power dissipation,
propagation delay, and switching speed. They do not differ in the pin assignment or logic operation performed by the internal circuits. For example, all the rcs listed in Table 29 with an 86 number, no matter what the prefix, contain four exclusiveOR gates with the same pin assignment in each package. The most common EeL rcs are designated as the 10000 series. Figure 29(b) shows two ECL circuits. The 10102 provides four 2input NOR gates. Note that an ECL gate may have two outputs, one for the NOR function and another for the OR function. The 10 107 Ie provides three exclusiveOR gates. Here again there are two outputs from each gate; the other output provides the exclusiveNOR function. ECL gates have three terminals for power supply. VCCI and Ven are usually connected to ground, and VEE to a 5.2volt supply. The two logic levels for ECL are 0.8 and 1.8 volts. CMOS circuits of the 4000 series are shown in Fig. 29(c). Only two 4input NOR gates can be accommodated in the 4002 because of pin limitation. The 4050 Ie provides six buffer gates. Both ICs have unused terminals marked NC (no connection). The terminal marked VDD requires a powersupply voltage from 3 to 15 volts, whereas V's is usually connected to ground. The two logic levels are 0 and VVD volts. The original 4000 series of CMOS circuits was designed independently from the TTL series. Since TTL became a standard in the industry, vendors started to supply other CMOS circuits that are pin compatible with similar TTL rcs. For example, the 74C04 is a CMOS circuit that is pin compatible with TTL 7404. This means that it has six inverters connected to the pins of the package, as shown in Fig. 29(a). The CMOS series available commercially are listed in Table 210. The 74HC series operates at higher speeds than the 74C series. The 74HCT series is both electrically and pin compatible with TTL devices. This mearis that 74HCT ICs can be connected directly to TTL ICs without the need of interfacing circuits.
Section 28
Integrated Circuits
67
TABLE 2·10 Various Series of the CMOS Logic Family
CMOS series
Prefix
Example
Original CMOS Pin compatible with TIL High·speed and pin compatible with TIL High·speed and electrically compatible with TTL
40
4009 74C04 74HC04 74HCT04
74C
74HC 74HCT
Positive and Negative Logic
The binary signal at the inputs and outputs of any gate has one of two values, except during transition. One signal value represents logicl and the other logicO. Since two signal values are assigned to two logic values, there exist two different assignments of signal level to logic value, as shown in Fig. 210. The higher signal level is designated by H and the lower signal level by L. Choosing the highlevel H to represent logicI defines a positive logic system. Choosing the lowlevel L to represent logicI defines a negative logic system. The terms positive and negative are somewhat misleading since both signals may be positive or both may be negative. It is not the actual signal values that determine the type of logic, but rather the assignment of logic values to the relative amplitudes of the two signal levels. Integratedcircuit data sheets define digital gates not in terms of logic values, but rather in terms of signal values such as Hand L. It is up to the user to decide on a positive or negative logic polarity. Consider, for example, the TTL gate shown in Fig. 21I(b). The truth table for this gate as given in a data book is listed in Fig. 21I(a). This specifies the physical behavior of the gate when H is 3.5 volts and L is 0 volt. The truth table of Fig. 21I(c) assumes positive logic assignment with H = I and L = O. This truth table is the same as the one for the AND operation. The graphic symbol for a positive logic AND gate is shown in Fig. 21I(d). Now consider the negative logic assignment for the same physical gate with L = I and H = o. The result is the truth table of Fig. 21I(e). This table represents the OR operation even though the entries are reversed. The graphic symbol for the negative logic OR gate is shown in Fig. 21I(f). The sma)) triangles in the inputs and output Logic value
0
S
Signal value
Logic value
H
o
Signal value
L
(a) Positive logic FIGURE 2·10 Signal assignment and logic polarity
(b) Negative logic
68
Chapter 2
Boolean Algebra and Logic Gates )'
I. L /{ /{
L II L II
L L L /I
(a) Truth table with Ii and L
x
y
0 0
0 I
0
(h) C;ate hlock diagram
, 0 0 0
(e) Truth table for
(1 (rues
ORinvert
+ z)'
SectJon 36
NAND and NOR JmplementatJon
89
It should be pointed out that the alternate symbols for the NAND and NOR gates could be drawn with small triangles in all input terminals instead of the circles. A small triangle is a negativelogic polarity indicator (see Section 28 and Fig. 211). With small triangles in the input terminals, the graphic symbol denotes a negativelogic polarity for the inputs, but the output of the gate (not having a triangle) would have a positivelogic assignment. In this book, we prefer to stay with positive logic throughout and employ small circles when necessary to denote complementation. NAND Implementation
The implementation of a Boolean function with NAND gates requires that the function be simplified in the sum of products form. To see the relationship between a sum of products expression and its equivalent NAND implementation, consider the logic diagrams of Fig. 318. All three diagrams are equivalent and implement the function: F=AB+CD+E
The function is implemented in Fig. 3l8(a) in sum of products form with AND and OR gates. In (b) the AND gates are replaced by NAND gates and the OR gate is replaced by a NAND gate with an invertOR symbol. The single variable E is complemented and applied to the secondlevel invertOR gate. Remember that a small circle denotes complementation. Therefore, two circles on the same line represent double complementation and both can be removed. The complement of E goes through a small A B
C F
D E (a) AND·OR
A B
A B
C F
D E'
C
F
D E
(b) NANDNAND
(c) NANDNAND
FIGURE 318 Three ways to implement F = AB
+
CD
+E
90
Chapter 3
Simplification of Boolean FUnctions
circle that complements the variable again to produce the normal value of E. Removing the small circles in the gates of Fig. 318(b) produces the circuit in (a). Therefore, the two diagrams implement the same function and are equivalent. In Fig. 318(c), the output NAND gate is redrawn with the conventional symbol. The oneinput NAND gate complements variable E. It is possible to remove this inverter and apply E' directly to the input of the secondlevel NAND gate. The diagram in (c) is equivalent to the one in (b), which in turn is equivalent to the diagram in (a). Note the similarity between the diagrams in (a) and (c). The AND and OR gates have been changed to NAND gates, but an additional NAND gate has been included with the single variable E. When drawing NAND logic diagrams, the circuit shown in either (b) or (c) is acceptable. The one in (b), however, represents a more direct relationship to the Boolean expression it implements. The NAND implementation in Fig. 318(c) can be verified algebraically. The NAND function it implements can be easily converted to a sum of products form by using DeMorgan's theorem: F
=
[(AB)" (CD)', E']'
=
AB
+
CD
+
E
From the transformation shown in Fig. 318, we conclude that a Boolean function can be implemented with two levels of NAND gates. The rule for obtaining the NAND logic diagram from a Boolean function is as follows: 1. Simplify the function and express it in sum of products. 2. Draw a NAND gate for each product term of the function that has at least two literals. The inputs to each NAND gate are the literals of the term. This constitutes a group of firstlevel gates. 3. Draw a single NAND gate (using the ANDinvert or invertOR graphic symbol) in the second level, with inputs coming from outputs of firstlevel gates. 4. A term with a single literal requires an inverter in the first level or may be complemented and applied as an input to the secondlevel NAND gate.
Before applying these rules to a specific example, it should be mentioned that there is a second way to implement a Boolean function with NAND gates. Remember that if we combine the O's in a map, we obtain the simplified expression of the complement of the function in sum of products. The complement of the function can then be implemented with two levels of NAND gates using the rules stated above. If the normal output is desired, it would be necessary to insert a oneinput NAND or inverter gate to generate the true value of the output variable. There are occasions where the designer may want to generate the complement of the function; so this second method may be preferable.
Example 39
Implement the following function with NAND gates: F(x, y, z) = 2: (0,6)
The first step is to simplify the function in sum of products form. This is attempted with the map shown in Fig. 319(a). There are only two l's in the map, and they can
Section 3·6
.
y
yz x
00
01
11
10
a
1
a
a
a
a
91
NAND and NOR Implementation
.
a
a z•
F
=
x'y'z' + xyz'
F' = x'y
.
+ xy' + z
1
(a) Map simplification in sum of products.
x''
F
y,_./
x..r, F
1:>1
y'''/
z
(b)F=x'y'z' +xyzl (e)F' = x'y + xy' + z FIGURE 3·19 Implementation of the function of Example 39 with NAND gates
not be combined. The simplified function in sum of products for this example is
F
= X/y'z'
+
xyz'
The twolevel NAND implementation is shown in Fig. 3.l9(b). Next we try to simplify the complement of the function in sum of products. This is done by combining the O's in the map: F' = x'y + xy'
+
z
The twolevel NAND gate for generating F' is shown in Fig. 3l9(c). If output F is reo quired, it is necessary to add a one· input NAND gate to invert the function. This gives a threelevel implementation. In each case, it is assumed that the input variables are available in both the normal and complement forms. If they were available in only one form, it would be necessary to insert inverters in the inputs, which would add another level to the circuits. The oneinput NAND gate associated with the single variable z can be removed provided the input is changed to z ' . • NOR Implementation
The NOR function is the dual of the NAND function. For this reason, all procedures and rules for NOR logic are the duals of the corresponding procedures and rules devel· oped for NAND logic.
92
Chapter 3
Simplification of Boolean Functions
The implementation of a Boolean function with NOR gates requires that the function be simplified in product of sums form. A product of sums expression specifies a group of OR gates for the sum terms, followed by an AND gate to produce the product. The transformation from the ORAND to the NORNOR diagram is depicted in Fig. 320. It is similar to the NAND transformation discussed previously, except that now we use the product of sums expression F = (A
+
B)(C
+
D)E
The rule for obtaining the NOR logic diagram from a Boolean function can be derived from this transformation. It is similar to the threestep NAND rule. except that the simplified expression must be in the product of sums and the terms t,)r the firstlevel NOR gates are the sum terms. A term with a single literal requires a oneinput NOR or inverter gate or may be complemented and applied directly to the secondlevel NOR gate. A second way to implement a function with NOR gates would be to use the expression for the complement of the function in product of sums. This will give a twolevel implementation for F' and a threelevel implementation if the normal output F is required. To obtain the simplified product of sums from a map, it is necessary to combine the O's in the map and then complement the function. To obtain the simplified product of sums expression for the complement of the function, it is necessary to combine the l's in the map and then complement the function. The following example demonstrates the procedure for NOR implementation.
Example 310
Implement the function of Example 39 with NOR gates. The map of this function is drawn in Fig. 3l9(a). First, combine the O's in the map to obtain F
I
=
X '}'
+ x.v + z I
This is the complement of the function in sum of products. Complement F' to obtain the simplified function in product of sums as required for NOR implementation: A
A
B
B C
C
F
F D
/J
F
F'
(b) NORNOR
(a) ORAND FIGURE 320 fhwf' w"'Y\ to !!lI!J:crr~ent F"
!A
811 C
t.!I!
F
(e) NORNOR
Section 36
F = (x
93
NAND and NOR Implementation
+ y')(x' + y)z'
The twolevel implementation with NOR gates is shown in Fig. 321(a). The term with a single literal z' requires a oneinput NOR or inverter gate. This gate can be removed and input z applied directly to the input of the secondlevel NOR gate. A second implementation is possible from the complement of the function in product of sums. For this case, first combine the I's in the map to obtain F
=
Xly'ZI
+
xyzl
This is the simplified expression in sum of products. Complement this function to obtain the complement of the function in product of sums as required for NOR implementation: F'
= (x +
+ z)(x' +
y
y'
+ z)
The twolevel implementation for F 'is shown in Fig. 32I(b). If output F is desired, it can be generated with an inverter in the third level. • x x
F
y
y'
z
)o~F'
x'
x'
F
Y"'L_'
l z
z' (a) F = (x
+ y')
(x'
+ y)z'
(b) F' = (x
+ y + z)(x' + y' + z)
FIGURE 3·21 Implementation with NOR gates
Table 3·3 summarizes the procedures for NAND or NOR implementation. One should not forget to always simplify the function in order to reduce the number of gates in the implementation. The standard forms obtained from the mapsimplification procedures apply directly and are very useful when dealing with NAND or NOR logic. TABLE 3·3 Rules for NAND and NOR Implementation Number
of Case
(a) (b) (e)
(d)
Function to simplify
Standard form to use
How to derive
Implement with
levels to F
F F' F F'
Sum of products Sum of products Product of sums Product of sums
Combine 1's in map Combine 0' s in map Complement F' in (b) Complement F in (a)
NAND NAND NOR NOR
2 3 2 3
94
37
Chapter 3
Simplification of Boolean Functions
OTHER TWOLEVEL IMPLEMENTATIONS
The types of gates most often found in integrated circuits are NAND and NOR. For this reason, NAND and NOR logic implementations are the most important from a practical point of view. Some NAND or NOR gates (but not all) allow the possibility of a wire connection between the outputs of two gates to provide a specific logic function. This type of logic is called wired logic. For example, opencollector TTL NAND gates, when tied together, perform the wiredAND logic. (The opencollector TTL gate is shown in Chapter 10, Fig. 1011.) The wiredAND logic performed with two NAND gates is depicted in Fig. 322(a). The AND gate is drawn with the lines going through the center of the gate to distinguish it from a conventional gate. The wiredAND gate is not a physical gate, but only a symbol to designate the function obtained from the indicated wired connection. The logic function implemented by the circuit of Fig. 322(a) is F
~
(AB)' . (CD)'
~
(AB
+ CD)'
and is called an ANDORINVERT function. Similarly, the NOR output of ECL gates can be tied together to perform a wiredOR function. The logic function implemented by the circuit of Fig. 322(b) is F = (A
+
B)'
+ (C +
D)' ~ [(A
+
B)(C
+
D)]'
and is called an ORANDINVERT function. A wiredlogic gates does not produce a physical secondlevel gate since it is just a wire connection. Nevertheless, for discussion purposes, we will consider the circuits of Fig. 322 as twolevel implementations. The first level consists of NAND (or NOR) gates and the second level has a single AND (or OR) gate. The wired connection in the graphic symbol will be omitted in subsequent discussions. Nondegenerate Forms
It will be instructive from a theoretical point of view to find out how many twolevel combinations of gates are possible. We consider four types of gates: AND, OR, NAND, and NOR. If we assign one type of gate for the first level and one type for the second A B
A B\'I,....
Y.+_H
~~~~S
,.L.../} c
z' FIGURE 45
Implementation of a fulladder with two halfadders and an OR gate
one OR gate, as shown in Fig. 45. The S output from the second halfadder is the exclusiveOR of z and the output of the first halfadder, giving
S = z El1 (x El1 y) = = =
+ x'y) + z(xy' + x'y)' z'(xy' + x'y) + z(xy + x'y') xy'z' + x'yz' + xyz + x'y'z z'(xy'
and the carry output is C
4·4
=
z(xy'
+
x'y)
+ xy = xy'z +
x'yz
+
xy
SUBTRACTORS The subtraction of two binary numbers may be accomplished by taking the complement of the subtrahend and adding it to the minuend (Section 15). By this method, the subtraction operation becomes an addition operation requiring fulladders for its machine implementation. It is possible to implement subtraction with logic circuits in a direct manner, as done with paper and pencil. By this method, each subtrahend bit of the number is subtracted from its corresponding significant minuend bit to form a difference bit. If the minuend bit is smaller than the subtrahend bit, a 1 is borrowed from the next significant position. The fact that a 1 has been borrowed must be conveyed to the next higher pair of bits by means of a binary signal coming out (output) of a given stage and going into (input) the next higher stage. Just as there are half and fulladders, there are half and fullsubtractors.
HalfSubtractor
A halfsubtractor is a combinational circuit that subtracts two bits and produces their difference. It also has an output to specify if a 1 has been borrowed. Designate the min
122
Chapter 4
Combinational Logic
uend bit by X and the subtrahend bit by y. To perform x  y, we have to check the relative magnitudes of x and y. If x '3 y, we have three possibilities: 0  0 = 0, 1  0 = 1, and 1  1 = O. The result is called the difference bit. If x < y, we have o  1, and it is necessary to borrow a 1 from the next higher stage. The 1 borrowed from the next higher stage adds 2 to the minuend bit, just as in the decimal system a borrow adds 10 to a minuend digit. With the minuend equal to 2, the difference becomes 2  1 = 1. The halfsubtractor needs two outputs. One output generates the difference and will be designated by the symbol D. The second output, designated B for borrow, generates the binary signal that informs the next stage that a 1 has been borrowed. The truth table for the inputoutput relationships of a halfsubtractor can now be derived as follows:
~
x  Y
o o
0
B
0
~
0
0
1
1 0
1
I~O
0
I
I
1 0
1 1
The output borrow B is a 0 as long as x '3 y. It is a 1 for x = 0 and y = 1. The D output is the result of the arithmetic operation 2B + x  y. The Boolean functions for the two outputs of the halfsubtractor are derived directly from the truth table: D = x'y
+ xy'
B = x'y It is interesting to note that the logic for D is exactly the same as the logic for output S
in the halfadder.
FullSubtractor
A fullsubtractor is a combinational circuit that performs a subtraction between two bits, taking into account that a 1 may have been borrowed by a lower significant stage. This circuit has three inputs and two outputs. The three inputs, x, y, and z, denote the minuend, subtrahend, and previous borrow, respectively. The two outputs, D and B, represent the difference and output borrow, respectively. The truth table for the circuit is
Section 44 $ubtractors
x
y
z
8
D
0 0 0 0 1 1 1 1
0 0 1 1 0 0
0 1 0 1 0 1 0 1
(J)
0 1 1 0 1 0 0 1
1 1 1 0 0 0
123
The eight rows under the input variables designate all possible combinations of I's and O's that the binary variables may take. The I's and O's for the output variables are determined from the subtraction of x  y  z. The combinations having input borrow z = 0 reduce to the same four conditions of the halfadder. For x = 0, y = 0, and z = 1, we have to borrow a 1 from the next stage, which makes B = 1 and adds 2 to x. Since 2  0  1 = 1, D = l. For x = 0 and yz = 11, we need to borrow again, making B = 1 and x = 2. Since 2  1  1 = 0, D = O. For x = 1 and yz = 01, we have x  y  z = 0, which makes B = 0 and D = O. Finally, for x = 1, y = 1, z = I, we have to borrow 1, making B = 1 and x = 3, and 3  1  1 = 1, making D=l.
The simplified Boolean functions for the two outputs of the fullsubtractor are derived in the maps of Fig. 46. The simplified sum of products output functions are
+ x'yz' + xy'z' + xyz x'y + x'z + yz
D = x'y'z B =
yz
y
y
00
01
11
10
10
,'I
IIII
>1:1
,
l
D
=
x'y'z
+ x'yz + xy'Z' + xyz
FIGURE 4·6 Maps for a fuUsubtractor
B
=.0
x'y
+ x'z + yz
124
45
Chapter 4
Combinational Logic
CODE CONVERSION
The availability of a large variety of codes for the same discrete elements of information results in the use of different codes by different digital systems. It is sometimes necessary to use the output of one system as the input to another. A conversion circuit must be inserted between the two systems if each uses different codes for the same information. Thus, a code converter is a circuit that makes the two systems compatible even though each uses a different binary code. To convert from binary code A to binary code B, the input lines must supply the bit combination of elements as specified by code A and the output lines must generate the corresponding bit combination of code B. A combinational circuit performs this transformation by means of logic gates. The design procedure of code converters will be illustrated by means of a specific example of conversion from the BCD to the excess3 code. The bit combinations for the BCD and excess3 codes are listed in Table 12 (Section 17). Since each code uses four bits to represent a decimal digit, there must be four input variables and four output variables. Let us designate the four input binary variables by the symbols A, B, C, and D, and the four output variables by w, x, y, and z. The truth table relating the input and output variables is shown in Table 41. The bit combinations for the inputs and their corresponding outputs are obtained directly from Table 12. We note that four binarY'variables may have 16 bit combinations, only 10 of which are listed in the truth table. The six bit combinations not listed for the input variables are don'tcare combinations. Since they will never occur, we are at liberty to assign to the output variables either a 1 or a 0, whichever gives a simpler circuit. The maps in Fig. 47 are drawn to obtain a simplified Boolean function for each output. Each of the four maps of Fig. 47 represents one of the four outputs of this circuit as a function of the four input variables. The l's marked inside the squares are obtained TABLE 41 Truth Table for CodeConversion Example I Input BCD I
  
Output Excess3 Code

A
B
C
0
I
w
x
~
0 0 0 0 0 0
0 0 0 0
0 0
0 0
1 0 0
0
1 0 0
0 0
0
1
1
0 0
0 I
0 0 0 0 0
0
I I 0
0 0
y z I 0 0 0 1 1 0 1 1 0 0 0 1 1 0
0 0 ._
I 0
Section 45
C
CD 00
1
10 ,1
o1
1
1
00
AB
11
01
1
Code Conversion
C
CD AB
00
01
11
,
1
'1
1
1
1
X
1
X
X
0
o0
125
10
B 1 X
X
X
X
X
X
X
X
A
0
X
1
1
o0 o1
D
y
C
CD 00
II
II
01
II
1
1
10
I
1
AB
I

X
CD 00
+ CD'
CD
C
01
11
10
1
1
1
o0
X
X
I~
,
X
1
X
X
X
0
1
1
X

0
=
o1
1
1
~
D
;::=D'
AB
1
L
~
Ixi xl
+ B'D + BCD'
).
X
D
D
x = S'C FIGURE 47
X

w= A
+ BC+BD
Maps for a BCDtoexcess3code converter
from the minterms that make the output equal to 1. The l's are obtained from the truth table by going over the output columns one at a time. For example, the column under output z has five 1's; therefore, the map for z must have five 1's, each being in a square corresponding to the minterm that makes z equal to 1. The six don'tcare combinations are marked by X's. One possible way to simplify the functions in sum of products is listed under the map of each variable. A twolevel logic diagram may be obtained directly from the Boolean expressions derived by the maps. There are various other possibilities for a logic diagram that implements this circuit. The expressions obtained in Fig. 47 may be manipulated algebraically for the purpose of using common gates for two or more outputs. This manipulation, shown below, illustrates the flexibility obtained with multipleoutput systems when implemented with three or more levels of gates.
126
Chapter 4
Combinational Logic
z = D'
+ e'D' = CD + (C + D)' B'C + B'D + Be'D' = B'(C + D) + Be'D' B '(C + D) + B(C + D)' A + BC + BD = A + B(C +D)
y = CD X
= =
w =
The logic diagram that implements these expressions is shown in Fig. 48. In it we see that the OR gate whose output is C + D has been used to implement partially each of three outputs. Not counting input inverters, the implementation in sum of products requires seven AND gates and three OR gates. The implementation of Fig. 48 requires four AND gates, four OR gates, and one inverter. If only the normal inputs are available, the first implementation will require inverters for variables B, C, and D, whereas the second implementation requires inverters for variables Band D. D'
D C
z
CD
y
(C
+ D),
C+D 8 x
==__
A ______________
===t~W
FIGURE 4·8 Logic dia9ram for a BCOtoexcess3code wnverter
46
ANALYSIS PROCEDURE
The design of a combinational circuit starts from the verbal specifications of a required function and culminates with a set of output Boolean functions or a logic diagram. The analysis of a combinational circuit is somewhat the reverse process. It starts with a
Section 4·6 Analysis Procedure
127
given logic diagram and culminates with a set of Boolean functions. a truth table, or a verbal explanation of the circuit operation. If the logic diagram to be analyzed is accompanied by a function name or an explanation of what it is assumed to accomplish, then the analysis problem reduces to a verification of the stated function. The first step in the analysis is to make sure that the given circuit is combinational and not sequential. The diagram of a combinational circuit has logic gates with no feedback paths or memory elements. A feedback path is a connection from the output of one gate to the input of a sec()nd g~~ilatf()EJllspart QQlie jfJJititfo the:fir~tjllte.Feed: bacl<jfallisoiinemory elements in a digititlWeuitdefine a seqllentiat"ir!,uitand must beanalyZed according to procedures outlined in Chapter 6 or Chapter 9.   Once the logic diagram is verified as a combinational circuit, one can proceed to obtain the output Boolean functions and/or the truth table. If the circuit is accompanied by a verbal explanation of its function, then the Boolean functions or the truth table is sufficient for verification. If the function of the circuit is under investigation, then it is necessary to interpret the operation of the circuit from the derived truth table. The success of such investigation is enhanced if one has previous experience and familiarity with a wide variety of digital circuits. The ability to correlate a truth table with an informationprocessing task is an art one acquires with experience. To obtain the output Boolean functions from a logic diagram, proceed as follows:
1. Label with arbitrary symbols all gate outputs that are a function of the input variabies. Obtain the Boolean functions for each gate. 2. Label with other arbitrary symbols those gates that are a function of input variables and/or previously labeled gates. Find the Boolean functions for these gates. 3. Repeat the process .outlined in step 2 until the outputs of the circuit are obtained. 4. By' repeated substitution of previously defined functions, obtain the output Boolean functions in terms of input variables only. Analysis of the combinational circuit in Fig. 49 illustrates the proposed procedure. We note that the circuit has three binary inputs, A, B, and C, and two binary outputs, F, and F,. The outputs of various gates are labeled with intermediate symbols. The outputs of gates that are a function of input variables only are F" T.. and T,. The Boolean functions for these three outputs are
F, = AB + AC + BC T,=A+B+C T,
=
ABC
Next we consider outputs of gates that are a function of already defined symbols:
T,=F,T, F,
= T, + T2
The output Boolean function F, just expressed is already given as a function of the in
128
Chapter 4
Combinational Logic
A _,,. T,
~==t~~~~ A_Z..... B
T,
}~
__________
~
C._,
A B,_~
A C
r"___ >~F,
B C FIGURE 49 logic diagr B, A = B, or A < B. The circuit for comparing two nbit numbers has 2'" entries in the truth table and becomes too cumbersome even with n = 3. On the other hand, as one may suspect, a comparator circuit possesses a certain amount of regularity. Digital functions that possess an inherent welldefined regularity can usually be designed by means of an al
164
Chapter 5
MSI and PLD Components
gorithmic procedure if one is found to exist. An algorithm is a procedure that specifies a finite set of steps that, if followed, give the solution to a problem. We illustrate this method here by deriving an algorithm for the design of a 4bit magnitude comparator. The algorithm is a direct application of the procedure a person uses to compare the relative magnitudes of two numbers. Consider two numbers, A and B, with four digits each. Write the coefficients of the numbers with descending significance as follows:
A B
= =
A3A2A,Ao B,B 2B,B o
where each subscripted letter represents one of the digits in the number. The two numbers are equal if all pairs of significant digits are equal, i.e., if A3 = B3 and A2 = B2 and A, = B, and Ao = Bo. When the numbers are binary, the digits are either I or 0 and the equality relation of each pair of bits can be expressed logically with an equivalence function: Xi
=
AIBI
+
i = 0, I, 2, 3
Ai B i '
where Xi = I only if the pair of bits in position i are equal, i.e., if both are I's or both are D's. The equality of the two numbers, A and B, is displayed in a combinational circuit by an output binary variable that we designate by the symbol (A = B). This binary variable is equal to I if the input numbers, A and B, are equal, and it is equal to 0 otherwise. For the equality condition to exist, all Xi variables must be equal to I. This dictates an AND operation of all variables: (A = B) =
X3X2X,XO
The binary variable (A = B) is equal to I only if all pairs of digits of the two numbers are equal. To determine if A is greater than or less than B, we inspect the relative magnitudes of pairs of significant digits starting from the most significant position. If the two digits are equal, we compare the next lower significant pair of digits. This comparison continues until a pair of unequal digits is reached. If the corresponding digit of A is I and that of B is 0, we conclude that A > B. If the corresponding digit of A is 0 and that of B is 1, we have that A < B. The sequential comparison can be expressed logically by the following two Boolean functions: (A
>
B) = AJB~
+
XJA2Bf
+
(A
B) and (A < B) are binary output variables that are equal to I when > B or A < B, respectively. The gate implementation of the three output variables just derived is simpler than it seems because it involves a certain amount of repetition. The "unequal" outputs can use the same gates that are needed to generate the "equal" output. The logic diagram of the 4bit magnitude comparator is shown in Fig. 57. The four x outputs are generated with
A
Section 54
Magnitude Comparator
165
BJ
A,
x, B,
(A B)
Bo
~=====L
____
~~~=B)
FIGURE 5·7 4bit magnitude comparator
equivalence (exclusive·NOR) circuits and applied to an AND gate to give the output bi· nary variable (A = B). The other two outputs use the x variables to generate the Boolean functions listed before. This is a multilevel implementation and, as clearly seen, it has a regular pattern. The procedure for obtaining magnitude·comparator cir· cuits for binary numbers with more than four bits should be obvious from this example. The same circuit can be used to compare the relative magnitudes of two BCD digits.
166
55
Chapter 5
MSI and PLD Components
DECODERS AND ENCODERS
Discrete quantities of information are represented in digital systems with binary cndes. A binary code of n bits is capable of representing up to 2" distinct elements of the coded information. A decoder is a combinational circuit that converts binary information from n input lines to a maximum of 2" unique output lines. If the nbit decoded information has unused or don'tcare combinations, the decoder output will have fewer than 2" outputs. The decoders presented here are called ntomline decoders, where m 2345678910
FIGURE 5·30 PAL with four inputs, four outputs, and threewide ANDOR structure
193
194
Chapter 5
MSI and PLD Compone"ts
puts. Each input has a buffer and an inverter gate. Note that the two gates are shown with one composite graphic symbol with normal and complement outputs. There are four sections in the unit, each being composed of a threewide ANDOR array. This is the term used to indicate that there are three programmable AND gates in each section and one fixed OR gate. Each AND gate has to fused programmable inputs. This is shown in the diagram by to vertical lines intersecting each horizontal line. The horizontal line symbolizes the multipleinput configuration of the AND gate. One of the outputs is connected to a bufferinverter gate and then fed back into the inputs of the AND gates through fuses. Commercial PAL devices contain more gates than the one shown in Fig. 530. A typical PAL integrated circuit may have eight inputs, eight outputs, and eight sections, each consisting of an eightwide ANDOR array. The output terminals are sometimes bidirectional, which means that they can be programmed as inputs instead of outputs if desired. When designing with a PAL, the Boolean functions must be simplified to fit into each section. Unlike the PLA, a product term cannot be shared among two or more OR gates. Therefore, each function can be simplified by itself without regard to common product terms. The number of product terms in each section is fixed, and if the number of terms in the function is too large, it may be necessary to use two sections to implement one Boolean function. As an example of using a PAL in the design of a combinational circuit, consider the following Boolean functions given in sum of min terms: w(A, B, C, D) = 2:(2, 12, 13)
x(A, B, C, D) = 2:(7, 8, 9, 10,11, 12, 13, 14, 15)
y(A, B, C, D)
=
2:(0,2,3,4,5,6,7,8,10, II, 15)
z(A, B, C, D) = 2:(1, 2, 8. 12, 13)
Simplifying the four functions to a minimum number of terms results in the following Boolean functions: w = ABC'
x
=
+ A'B'CD'
A + BCD
y=A'B+CD+B'D'
z
=
ABC' + A'B'CD' + AC'D' + A'B'C'D
= w + AC'D' + A'B'C'D
SectIon 59
Programmable Array logIc (PAL,
195
Note that the function for z has four product terms. The logical sum of two of these terms is equal to w. By using w, it is possible to reduce the number of terms for z from four to three. The PAL programming table is similar to the one used for the PLA except that only the inputs of the AND gates need to be programmed. Table 56 lists the PAL programming table for the four Boolean functions. The table is divided into four sections with three product terms in each to conform with the PAL of Fig. 530. The first two sections need only two product terms to implement the Boolean function. The last section for output z needs four product terms. Using the output from w, we can reduce the function to three terms. The fuse map for the PAL as specified in the programming table is shown in Fig. 53!. For each lor 0 in the table, we mark the corresponding intersection in the diagram with the symbol for an intact fuse. For each dash, we mark the diagram with blown fuses in both the true and complement inputs. If the AND gate is not used, we leave all its input fuses intact. Since the corresponding input receives both the true and complement of each input variable, we have AA' = 0 and the output of the AND gate is always O. As with all PLDs, the design with PALs is facilitated by using computeraided design techniques. The blowing of internal fuses is a hardware procedure done with the help of special electronic instruments.
TABLE 56 PAL Programming Table AND Inputs
Product Term
1 2 3
4 5 6 7 8 9 10 11 12
B C D
W
Outputs
1 1 0 0 0 1 0

w = ABC' + A'B'CD'


x=A + BCD
A
1
1
y =A'B
0 1 
0

1 0 
+ CD +B'D' z=
1 
0 0 0 0 0 1 
w
+AC'D'
+A'B'C'D
AND gates inputs P TO d uet term
A
t
A'
B
B'
C
C'
D
DJ
W
w'
1
w
2
X
3
A
~1"
" :> v
4
5
X
6
L
>
B
All fuses intact (always == 0)
7
v
8
9
..... c
> 10
z
\I
12
D
" :> A
A'
B'
B'
FIGURE 531 Fuse map for PAL a'S specified in rable 56
C
("
D
D'
w
w'
X
Fuse intact
+
Fuse blown
Chapter 5
Problems
197
REFERENCES 1.
2. 3. 4_ 5_ 6. 7.
8. 9. 10. 11.
BLAKESLEE, T. R., Digital Design with Standard MSI and LSI, 2nd Ed. New York: John Wiley, 1979. SANDIGE, R. S., Digital Concepts Using Standard Integrated Circuits. New York: McGrawHill, 1978. MANO, M. M., Computer Engineering: Hardware Design. Englewood Cliffs, NJ: PrenticeHall, 1988. MANa, M. M., Computer System Architecture, 2nd Ed. Englewood Cliffs, NJ: PrenticeHall, 1982. SHIVA, S. G., Introduction to Logic Design. Glenview, IL: Scott, Foresman, 1988. The TTL Logic Data Book. Dallas: Texas InstrUments, 1988. TOCCI, R. J., Digital Systems Principles and Applications, 4th Ed. Englewood Cliffs, NJ: PrenticeHall, 1988. FLETCHER, W. I., An Engineering Approach to Digital Design. Englewood Cliffs, NJ: PrenticeHall, 1979. KITSON, B., Programmable Array Logic Handbook. Sunnyvale, CA: Advanced Micro Devices, 1983. Programmable Logic Data Manual. Sunnyvale, CA: Signetics, 1986. Programmable LogiC Data Book. Dallas: Texas Instruments, 1988.
PROBLEMS 51
Construct a 16bit parallel adder with four MSI circuits, each containing a 4bit parallel adder. Dse a block diagram with nine inputs and five outputs for each 4bit adder. Show how the carries are connected between the MSI circuits.
J 5·2
Construct a BCDtoexcess3code converter with a 4bit adder. Remember that the ex
cess3 code digit is obtained by adding three to the corresponding BCD digit. What must be done to change the circuit to an excess3toBCDcode converter?
53
The addersubtractor of Fig. 52(b) is used to subtract the following unsigned 4bit numbers: OlIO  1001 (6  9). (a) What are the binary values in the nine inputs of the circuit?
(b) What are the binary values of the five outputs of the circuit? Explain how the output is related to the operation of 6  9. 54
The addersubtractor circuit of Fig. 52(b) has the following values for mode input M and data inputs A and B. In each case, determine the values of the outputs: S4, S3, S2, Sl, and
C,. (a) (b) (c) (d) (e)
M 0 0 I I I
A 0111 1000 1100 0101 0000
B OlIO
100 I 1000 1010 000 I
198
Chapter 5
5·5
MSI and PLD Components
(a) Using the ANDORINVERT implementation procedure described in Section 37, show that the output carry in a fulladder circuit can be expressed as C,+l
= G, +
= (G; Pi +
PiC;
G: er)'
(b) Ie type 74182 is a lookahead carry generator MSI circuit that generates the carries with ANDOR INVERT gates. The MSI circuit assumes that the input terminals have the complements of the G's, the P's, and of C j • Derive the Boolean functions for the lookahead carries C 2 , C" and C4 in this Ie. (Hint: Use the equationsubstitution method to derive the carries in terms of C;.) 56
(a) Redefine the carry propagate and carry generate as follows: p,
~
A,
+
B,
G, = AiR;
Show that the output carry and output sum of a fulladder becomes
p:r = G; + PiC;
C;+l
=
(C: G,
s,
~
(P,G;) E!:l C,
+
(b) The logic diagram of the first stage of a 4bit parallel adder as implemented in Ie type 74283 is shown in Fig. P56. Identify the and G! terminals as defined in part (a) and show that the circuit implements a fulladder circuit. (c) Obtain the output carries C 3 and C4 as functions of PI, P2, P 3, Gj, G 2, G), and C 1 in ANDORJNVERT form, and draw the twolevel lookahead circuit for this Ie. [Hint: Use the equationsubstitution method as done in the text when deriving Fig. 54, but use the ANDORINVERT function given in part (a) for C+l']
P:
}I>C,
FIGURE P56 Fir >
~lB'
S
Q
I
c
I" > R Q'
CP FIGURE 630 logic diagram with RS flipflops
The other don'tcare terms in the maps come from the X's in the flipflop input columns of the table, The simplified functions are listed under each rnap. The logic diagram obtained from these Boolean functions is shown in Fig. 630. One factor neglected up to this point in the design is the initial state of a sequential circuit. When power is first turned on in a digital system, one does not know in what state the flipflops will settle. It is customary to provide a masterreset input whose purpose is to initialize the states of all flipflops in the system. Typically, the master reset is a signal applied to all flipflops asynchronously before the clocked operations start. In most cases, flipflops are cleared to 0 by the rnasterreset signal, but some may be set to 1. For example, the circuit of Fig. 6.30 may initially be reset to a state ABC = 001, since state 000 is not a valid state for this circuit. But what if a circuit is not reset to an initial valid state? Or worse, what if, because of a noise signal or any other unforeseen reason, the circuit finds itself in one of its invalid states? In that case, it is necessary to ensure that the circuit eventually goes into one of the valid states so it can resume normal operation. Otherwise, if the sequential circuit circulates among invalid states, there will be no way to bring it back to its in
246
Chapter 6
Synchronous Sequential Logic
tended sequence of state transitions. Although one can assume that this undesirable condition is not supposed to occur, a careful designer must ensure that this situation never occurs. It was stated previously that unused states in a sequential circuit can be treated as
don'tcare conditions. Once the circuit is designed, the m flipflops in the system can be in anyone of 2m possible states. If some of these states were taken as don'tcare conditions, the circuit must be investigated to determine the effect of these unused states. The next state from invalid states can be determined from the analysis of the circuit. In any case, it is always wise to analyze a circuit obtained from a design to ensure that no mistakes were made during the design process. Analysis of Previously Designed Circuit
We wish to analyze the sequential circuit of Fig. 630 to determine whether it operates according to the original state table and also determine the effect of the unused states on the circuit operation. The unused states are 000, 110, and Ill. The analysis of the circuit can be done by the method outlined in Section 64. The maps of Fig. 629 may also help in the analysis. What is needed here is to start with the circuit diagram of Fig. 630 and derive the state table or diagram. If the derived state table is identical to the statetable part of Table 614, then we know that the design is correct. In addition, we must determine the next states from the unused states 000, 11 0, and 111. The maps of Fig. 629 can help in finding the next state from each of the unused states. Take, for instance, the unused state 000. If the circuit, for some reason, happens to be in the present state 000, an input x = 0 will transfer the circuit to some next state and an input x = 1 will transfer it to another (or the same) next state. We first investigate minterm ABCx = 0000. From the maps, we see that this minterm is not included in any function except for SC, i.e., the set input of flipflop C. Therefore, flipflops A and B will not change, but flipflop C will be set to 1. Since the present state is ABC = 000, the next state will be ABC = 00 1. The maps also show that min term ABCx = 0001 is included in the functions for SB and RC. Therefore, B will be set and C will be cleared. Starting with ABC = 000 and setting B, we obtain the next state ABC = 0 J 0 (C is already cleared). Investigation of the map for output y shows that y will be 0 for these two minterms. The result of the analysis procedure is shown in the state diagram of Fig. 631. The circuit operates as intended, as long as it stays within the states 001, 010, 011, 100, and 101. If it ever finds itself in one of the invalid states, 000, 110, or 111, it goes to one of the valid states within one or two clock pulses. Thus, the circuit is selfcorrecting, since it eventually goes to a valid state from which it continues to operate as required. An undesirable situation would have occurred if the next state of 110 for x = 1 happened to be 111 and the next state of 111 for x = 0 or 1 happened to be 110. Then, if the circuit starts from 110 or J J 1, it will circulate and stay between these two states forever. Unused states that cause such undesirable behavior should be avoided; if they
Section 68
Design of Counters
247
0/0 0/0 0/0
1/0
0/0
1/1
I/O 1/1
1/1
1/1
FIGURE 631 State diagram for the circuit of fig. 630
are found to exist, the circuit should be redesigned. This can be done most easily by specifying a valid next state for any unused state that is found to circulate among invalid states.
68
DESIGN OF COUNTERS A sequential circuit that goes through a prescribed sequence of states upon the application of input pulses is called a counter. The input pulses, called count pulses, may be clock pulses or they may originate from an external source and may occur at prescribed intervals of time or at random. In a counter, the sequence of states may follow a binary count or any other sequ'?lce of states. Counters are found in almost all equipment containing digital logic. They are used for counting the number of occurrences of an event· and are useful for generating timing sequences to control operations in a digital system. Of the various sequences a counter may follow, the straight binary sequence is the simplest and most straightforward. A counter that follows the binary sequence is called a binary counter. An nbit binary counter consists of n flipflops and can count in binary from 0 to 2"  1. As an example, the state diagram of a 3bit counter is shown in Fig. 632. As seen from the binary states indicated inside the circles, the flipflop outputs repeat the binary count sequence with a return to 000 after 111. The directed lines between circles are not marked with inputoutput values as in other state diagrams. Remember that state transitions in clocked sequential circuits occur during a clock pulse; the flipflops remain in their present states if no pulse occurs. For this reason, the clockpulse variable CP does not appear explicitly as an input variable in a state diagram or state table. From this point of view, the state diagram of a counter does not have to show inputoutput values along the directed lines. The only input to the circuit is the count pulse, and the outputs are directly specified by the present states of the flip
248
Chapter 6
Synchronous Sequential Logic
~
~~
e
~

e e.. e ~
FIGURE 632 S[Clt'f' dlagr.'lnl of K
~'
I
./
.
Clear FIGURE 7·11 Second form of serial adder
•
272 74
Chapter 7
Registers Counters and the Memory Unit k
k
RIPPLE COUNTERS
MSI counters come in two categories: ripple counters and synchronous counters. In a ripple counter, the flipflop output transition serves as a source for triggering other flipflops. In other words, the CP inputs of all flipflops (except the first) are triggered not by the incoming pulses, but rather by the transition that occurs in other flipflops. In a

J
~
K
~
J
~
K
Q
Count pulses
~J
~
LOgIC~1
FIGURE 712 4bit binary ripple COUiltf'!
Q
K
~ J
~
Q
K
Q
Section 74
Ripple Counten
273
synchronous counter, the input pulses are applied to all CP inputs of all flipflops. The change of state of a particular flipflop is dependent on the present state of other flipflops. Synchronous MSI counters are discussed in the next section. Here we present some common MSI ripple counters and explain their operation. Binary Ripple Counter
A binary ripple counter consists of a series connection of complementing flipflops (T or JK type), with the output of each flipflop connected to the CP input of the next higherorder flipflop. The flipflop holding the least significant bit receives the incoming count pulses. The diagram of a 4bit binary ripple counter is shown in Fig. 712. All J and K inputs are equal to l. The small circle in the CP input indicates that the flipflop complements during a negativegoing transition or when the output to which it is connected goes from 1 to O. To understand the operation of the binary counter, refer to its count sequence given in Table 7 4. It is obvious that the lowestorder bit AI must be complemented with each count pulse. Every time AI goes from 1 to 0, it complements A,. Every time A, goes from 1 to 0, it complements A 3 , and so on. For example, take the transition from count 0111 to 1000. The arrows in the table emphasize the transitions in this case. AI is complemented with the count pulse. Since AI goes from I to 0, it triggers A, and complements it. As a result, A, goes from 1 to 0, which in turn complements A3. A3 now goes from I to 0, which complements A,. The output transition of A" if connected to a next stage, will not trigger the next flipflop since it goes from 0 to l. The flipflops change one at a time in rapid succession, and the signal propagates through the counter in a ripple fashion. Ripple counters are sometimes called asynchronous counters. TABLE 74
Count Sequence for a Binary Ripple Counter
Count Sequence
A,
A,
A,
A,
0 0 0 0
0 0 0 0
0 0
0
0 0 0 0
I
I
0
I
0 I
Conditions for Complementing FlipFlops Complement AI Complement AI Complement AI
AI will go from 1 to
Complement AI
AI will go from 1 to 0 and complement A2;
~~j, 0 0
I
0 I 0 I
Complement A1 Complement A I
0
and so on ...
~~",1 0
Complement AI Complement AI
a and complement A2
A2 will go from I to
a and complement A3
Al will go from I to
a and complement A2
Al will go from I to 0 and complement A2; A2 will go from I to 0 and complement A,; A, will go from I to 0 and complement A,
274
Chapter 7
Registers, Counters, and the Memory Unit
A binary counter with a reverse count is called a binary downcounter. In a downcounter, the binary count is decremented by 1 with every input count pulse. The count of a 4bit downcounter starts from binary 15 and continues to binary counts 14, 13, 12, ... , 0 and then back to 15. The circuit of Fig. 712 will function as a binary downcounter if the outputs are taken from the complement terminals Q' of all flipflops. If only the normal outputs of flipflops are available, the circuit must be modified slightly as described next. A list of the count sequence of a countdown binary counter shows that the lowestorder bit must be complemented with every count pulse. Any other bit in the sequence is complemented if its previous lowerorder bit goes from 0 to 1. Therefore, the diagram of a binary downcounter looks the same as in Fig. 712, provided all flipflops trigger on the positive edge of the pulse. (The small circles in the CP inputs must be absent.) If negativeedgetriggered flipflops are used, then the CP input of each flipflop must be connected to the Q' output of the previous flipflop. Then when Q goes from 0 to 1, Q' will go from I to 0 and complement the next flipflop as required. BCD Ripple Counter
A decimal counter follows a sequence of ten states and returns to 0 after the count of 9. Such a counter must have at least four flipflops to represent each decimal digit, since a decimal digit is represented by a binary code with at least four bits. The sequence of states in a decimal counter is dictated by the binary code used to represent a decimal digit. If BCD is used, the sequence of states is as shown in the state diagram of Fig. 713. This is similar to a binary counter, except that the state after 1001 (code for decimal digit 9) is 0000 (code for decimal digit 0). The design of a decimal ripple counter or of any ripple counter not following the binary sequence is not a straightforward procedure. The formal tools of logic design can serve only as a guide. A satisfactory end product requires the ingenuity and imagination of the designer. The logic diagram of a BCD ripple counter is shown in Fig. 714. The four outputs are designated by the letter symbol Q with a numeric subscript equal to the binary weight of the corresponding bit in the BCD code. The flipflops trigger on the negative
FIGURE 713 State didgram of ,:1 cieClm;'ti ReD counter
Section 74 Ripple Counters
~
J
275
Q
Count pulses

K
J
i
~ i
Q,
K
i J
i
Q
Q
K
J
Q
K
Q' I
Logicl FIGURE 714 BCD ripple counter
edge, Le., when the CP signal goes from I to O. Note that the output of QI is applied to the CP inputs of both Q, and Q, and the output of Q, is applied to the CP input of Q•. The J and K inputs are connected either to a permanent 1 signal or to outputs of flipflops, as shown in the diagram.
276
Chapter 1
Registers. Counters. and the Memory Unit
A ripple counter is an asynchronous sequential circuit and cannot be described by Boolean equations developed for describing clocked sequential circuits. Signals that affect the flipflop transition depend on the order in which they change from I to O. The operation of the counter can be explained by a list of conditions for flipflop transitions. These conditions are derived from the logic diagram and from knowledge of how a JK flipflop operates. Remember that when the CP input goes from I to 0, the flipflop is set if J = I, is cleared if K = I, is complemented if J = K = I, and is left unchanged if J = K = O. The following are the conditions for each flipflop state transition: L Q, is complemented on the negative edge of every count pulse. 2, Q, is complemented if Q, = 0 and Q, goes from I to o. Q, is cleared if Q, = and Q, goes from 1 to O. 3. Q4 is complemented when Q, goes from I to o. 4. Q, is complemented when Q4 Q2 = 11 and Q, goes from I to o. Q, is cleared if either Q4 or Qz is 0 and Q, goes from I to O. To verify that these conditions result in the sequence required by a BCD ripple counter, it is necessary to verify that the flipflop transitions indeed follow a sequence of states as specified by the state diagram of Fig. 713. Another way to verify the operation of the counter is to derive the timing diagram for each flipflop from the conditions just listed. This diagram is shown in Fig. 715 with the binary states listed after each clock pulse. Q, changes state after each clock pulse. Q2 complements every time Q, goes from I to 0 as long as Q, = O. When Q, becomes 1, Q, remains cleared at O. Q4 complements every time Q2 goes from 1 to O. Q8 remains cleared as long as Q2 or Q4 is O. When both Qz and Q4 become I's, Q, complements when Q, goes from I to O. Q, is cleared on the next transition of Q,. The BCD counter of Fig. 714 is a decade counter, since it counts from 0 to 9. To count in decimal from 0 to 99, we need a twodecade counter. To count from 0 to 999,
Q,~~Jllo_ Q2
Q4
Q8
0
0
II
0
0
0
0
II
0
0
0
0
0
1 0
0
0
l::__
It 0
FIGURE 1·15 Timing diagram for the decimal counter of Fig ;'/4
0
0
0
~ .. 0
0
II
Il.z.
Section 7·5 Synchronous Counters
I
BCD Counter
f I
BCD Counter
f I
10 2 digit
BCD Counter
277
Count pulses
10° digit
FIGURE 7·16
Block diagram of a threedecade decimal BCD counter
we need a threedecade counter. Multipledecade counters can be constructed by connecting BCD counters in cascade, one for each decade. A threedecade counter is shown in Fig. 716. The inputs to the second and third decades come from Q, of the previous decade. When Q, in one decade goes from I to 0, it triggers the count for the next higherorder decade while its own decade goes from 9 to O. For instance, the count after 399 will be 400.
75
SYNCHRONOUS COUNTERS Synchronous counters are distinguished from ripple counters in that clock pulses are applied to the CP inputs of all flipflops. The common pulse triggers all the flipflops simultaneously, rather than one at a time in succession as in a ripple counter. The decision whether a flipflop is to be complemented or not is determined from the values of the J and K inputs at the time of the pulse. If J = K = 0, the flipflop remains unchanged. If J = K = I, the flipflop complements. A design procedure for any type of synchronous counter was presented in Section 68. The design of a 3bit binary counter was carried out in detail and is illustrated in Fig. 634. In this section, we present some typical MSI synchronous counters and explain their operation. It must be realized that there is no need to design a counter if it is already availahle commercially in IC form.
Binary Counter
The design of synchronous binary counters is so simple that there is no need to go through a rigorous sequentiallogic design process. In a synchronous binary counter, the flipflop in the lowestorder position is complemented with every pulse. This means that its J and K inputs must be maintained at logicI. A flipflop in any other position is complemented with a pulse provided all the bits in the lowerorder positions are equal to I, because the lowerorder bits (when all I's) will change to D's on the next count pulse. The binary count dictates that the next higherorder bit be complemented. For example, if the present state of a 4bit counter is A.A,A 2 A I = 0011, the next count will be 0100. AI is always complemented. A2 is complemented because the present state
278
Chapter 7
Registers, Counters, and the Memory Unit
J
Q
,.< I> Count enable
K
J
J
Q
K
J
J
Q
K
J
J
Q
fflT
Q 1A 4
Q'
CP FIGURE 118 4bit updown counter
Section 75
281
Synchronous Counters
TABLE 75
Excitation Table for BCD Counter Present State
Next State
Output
FlipFlop Inputs
0,
0,
0,
0,
0,
0,
0,
0,
y
TO,
TO,
TO,
0 0 0 0 0 0 0 0
0 0 0 0
0 0
0 1 0
0 0 0 0 0 0 0
0 0 0
0
1 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0
0
0 0 0
0 0
0 0
0 0
0 0
0 0
0
I
0 1 0
1 0 0
1 0
0 0
0 1 0 1 0
I
1 0 0 0
1 0 0 0
0
0
TO,
0
pattern as in a straight binary count. To derive the circuit of a BCD synchronous counter, it is necessary to go through a design procedure as discussed in Section 68. The excitation table of a BCD counter is given in Table 75. The excitation for the T flipflops is obtained from the present and next state conditions. An output y is also shown in the table. This output is equal to I when the counter present state is 1001. In this way, y can enable the count of the nexthigherorder decade while the same pulse switches the present decade from 1001 to 0000. The flipflop input functions from the excitation table can be simplified by means of maps. The unused states for minterms 10 to 15 are taken as don'tcare terms. The simplified functions are TQI
=
I
1Q2 = Q,QI TQ4
= Q,QI
TQ, = Q,Q,
y
+
Q4Q,QI
= Q,QI
The circuit can be easily drawn with four T flipflops, five AND gates, and one OR gate. Synchronous BCD counters can be cascaded to form a counter for decimal numbers of any length. The cascading is done as in Fig. 716, except that outputy must be connected to the count input of the nexthigherorder decade. Binary Counter with Parallel Load
Counters employed in digital systems quite often require a parallelload capability for transferring an initial binary number prior to the count operation. Figure 719 shows the logic diagram of a register that has a parallelload capability and can also operate as
282
Chapter 7
l
,......,
Count
Load
Registers Counters. and the Memory Unit
~
L.I {>1' 0...1
Y> G
~
~'
1
ocg
'.
,
~
10...1' ~
{)
1
K
./
r
~
{)
Q
~
I' 1
l;
J
~"
J
:f' 0...1 {)
r
I
'I
~
Clear
I::=t
~
J
Q
K
~ rJ
Q
A;
K
~ rJ
Q
r K
CP < Co< ryout
FIGURE 119 4bit binary counter with parallel load
a counter. The input load control when equal to I disables the count sequence and causes a transfer of data from inputs II through 14 into flipflops Al through A 4, respectively _ If the load input is 0 and the count input control is I, the circuit operates as a counter. The clock pulses then cause the state of the flipflops to change according to the binary count sequence. If both control inputs are 0, clock pulses do not change the state of the register.
Section 7·5
Synchronous Counten
283
The carryout terminal becomes a I if all flipflops are equal to I while the count input is enabled. This is the condition for complementing the flipflop holding the nexthigherorder bit. This output is useful for expanding the counter to more than four bits. The speed of the counter is increased if this carry is generated directly from the outputs of all four flipflops instead of going through a chain of AND gates. Similarly, each flipflop is associated with an AND gate that receives all previous flipflop outputs directly to determine when the flipflop should be complemented. The operation of the counter is summarized in Table 76. The four control inputs: clear, CP, load, and count determine the next output state. The clear input is asynchronous and, when equal to 0, causes the counter to be cleared to all O's, regardless of the presence of clock pulses or other inputs. This is indicated in the table by the X entries, which symbolize don'tcare conditions for the other inputs, so their value can be either 0 or 1. The clear input must go to the I state for the clocked operations listed in the next three entries in the table. With the load and count inputs both at 0, the outputs do not change, whether a pulse is applied in the CP terminal or not. A load input of I causes a transfer from inputs III. into the register during the positive edge of an input pulse. The input information is loaded into the register regardless of the value of the count input, because the count input is inhibited when the load input is I. If the load input is maintained at 0, the count input controls the operation of the counter. The outputs change to the next binary count on the positiveedge transition of every clock pulse. but no change of state occurs if the count input is O. The 4bit counter shown in Fig. 719 can be enclosed in one IC package. Two ICs are necessary for the construction of an 8bit counter; four ICs for a 16bit counter; and so on. The carry output of one IC must be connected to the count input of the IC holding the four nexthigherorder bits of the counter. Counters with parallelload capability having a specified number of bits are very useful in the design of digital systems. Later. we will refer to them as registers with load and increment capabilities. The increment function is an operation that adds I to the present content of a register. By enabling the count control during one clock pulse period. the content of the register can be incremented by I. A counter with parallel load can be used to generate any desired number of count sequences. A moduloN (abbreviated modN) counter is a counter that goes through a repeated sequence of N counts. For example, a 4bit binary counter is a mod16 counter. A BCD counter is a modIO counter. In some applications, one may not be concerned with the particular N states that a modN counter uses. If this is the case, then a counTABLE 7·6
FUnction Table for the Counter of Fig. 7·19 Clear
CP
Load
Count
0
X X
X
X
i i
0
0 X
0
Function
Clear to 0 No change Load inputs Count next binary state
284
Chapter 7
Registers. Counters. and the Memory Unit
ter with parallel load can be used to construct any modN counter, with N being any value desired. This is shown in the following example.
Example
74
Construct a mod6 counter using the MSI circuit specified in Fig. 719. Figure 720 shows four ways in which a counter with parallel load can be used to generate a sequence of six counts. In each case, the count control is set to I to enable the count through the pulses in the CP input. We also use the facts that the load control inhibits the count and that the clear operation is independent of other control inputs. The AND gate in Fig. 720(a) detects the occurrence of state 0101 in the output. When the counter is in this state, the load input is enabled and an allO's input is loaded into the register. Thus, the counter goes through binary states 0, I, 2, 3,4, and 5 and then returns to O. This produces a sequence of six counts. The clear input of the register is asynchronous, i.e., it does not depend on the clock. In Fig. 720(b), the NAND gate detects the count of 01 10, but as soon as this count occurs, the register is cleared. The count 0110 has no chance of staying on for any ap
Load
Count = I Counter of Fig. 719
Clear
Count = I Counter of Fig. 719
Clear = I
CP Inputs =
a __.L..'_.L..I
CP
Inputs have no effect
(a) Binary statesQ, 1,2.3,4,5.
(b) Binary states 0, I, 2, 3,4,5.
Count = 1
Counter of Fig, 719
Counter of Fig. 719
Clear = 1
Load
CP
o
Clear:= 1
CP
o
o
(c) Binary states 10, 11, 12, 13, 14, 15.
Count:= I
0
(d) Binary states 3, 4. 5. 6.7.8.
FIGURE 7·20 Four ways to achieve a mod6 counter using a counter with parallel load
Section 76 Timing sequences
285
preciable time because the register goes immediately to O. A momentary spike occurs in output A, as the count goes from 0101 to 0110 and immediately to 0000. This momentary spike may be undesirable, and for this reason, this configuration is not recommended. If the counter has a synchronous clear input, it would be possible to clear the counter with the clock after an occurrence of the 0101 count. Instead of using the first six counts, we may want to choose the last six counts from 10 to 15. In this case, it is possible to take advantage of the output carry to load a number in the register. In Fig. 720(c), the counter starts with count 1010 and continues to 1111. The output carry generated during the last state enables the load control, which then loads the input, which is set at 1010. It is also possible to choose any intermediate count of six states. The mod6 counter of Fig. 720(d) goes through the count sequence 3, 4, 5, 6, 7, and 8. When the last count 1000 is reached, output A, goes to I and the load control is enabled. This loads the value of 0011 into the register, and the binary count continues from this state. •
76
TIMING SEQUENCES The sequence of operations in a digital system are specified by a control unit. The control unit that supervises the operations in a digital system would normally consist of timing signals that determine the time sequence in which the operations are executed. The timing sequences in the control unit can be easily generated by means of counters or shift registers. This section demonstrates the use of these MSI functions in the generation of timing signals for a control unit.
WordTime Generation
First, we demonstrate a circuit that generates the required timing signal for serial mode of operation. Serial transfer of information was discussed in Section 73, with an example depicted in Fig. 78. The control unit in a serial computer must generate a wordtime signal that stays on for a number of pulses equal to the number of bits in the shift registers. The wordtime signal can be generated by means of a counter that counts the required number of pulses. Assume that the wordtime signal to be generated must stay on for a period of eight clock pulses. Figure 721(a) shows a counter circuit that accomplishes this task. Initially, the 3bit counter is cleared to O. A start signal will set flipflop Q. The output of this flipflop supplies the wordtime control and also enables the counter. After the count of eight pulses, the flipflop is reset and Q goes to O. The timing diagram of Fig. 721(b) demonstrates the operation of the circuit. The start signal is synchronized with the clock and stays on for one clockpulse period. After Q is set to I, the counter starts counting the clock pulses. When the counter reaches the count of 7 (binary III), it sends a stop signal to the reset input of the flipflop. The stop signal becomes a I after the negativeedge transition of pulse 7. The next clock pulse switches the counter to the 000 state and also clears Q. Now the counter is disabled and the wordtime signal stays
286
Chapter 7
Registers. Counters. and the Memory Unit
Q 1.__ Wordtim"
Start _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 5
control
I~=D~R I Stop COllnt enable
CP
(a) Circuit diagram
CP 2345670
StartJlL
.JnL_ __
stor_ _ _ _ _ _ _ _ _ Q~_
,I
Word time = 8 pulses _~..L_ __ (b) Timing diagram
FIGURE 7·21 Generation of a wordtime control for )/"riClI operatiom
at O. Note that the wordtime control stays on for a period of eight pulses. Note also that the stop signal in this circuit can be used to start another wordcount control in another circuit just as the start signal is used in this circuit. Timing Signals
In a parallel mode of operation, a single clock pulse can specify the time at which an operation should be executed. The control unit in a digital system that operates in the parallel mode must generate timing signals that stay on for only one clock pulse period, but these timing signals must be distinguished from each other. Timing signals that control the sequence of operations in a digital system can be generated with a shift register or a counter with a decoder. A ring counter is a circular shift register with only one flipflop being set at any particular time; all others are cleared. The single bit is shifted from one flipflop to the other to produce the sequence of timing signals. Figure 7 22(a) shows a 4bit shift register connected as a ring counter. The initial value of the register is 1000, which produces the variable To. The single bit is shifted right with every clock pulse and circulates back from T3 to To. Each flipflop is in the 1 state once every four clock pulses and produces one of the four timing signals shown in Fig. 722(c). Each output becomes a 1 after the negativeedge transition of a clock pulse and remains 1 during the next clock pulse.
Section
7~6
Timing Sequences
287
(a) Ringcounter (initial value = 1000)
2x4 decoder
Count enableo.j
2bit counter
'' (b) Counter and decoder
CP
'I
L . .  _ _
T, _ _ _ _ _ _ _'
(c) Sequence of four timing signals FIGURE 722 Generation of timing signals
The timing signals can be generated also by continuously enabling a 2bit counter that goes through four distinct states. The decoder shown in Fig. 7 22(b) decodes the four states of the counter and generates the required sequence of timing signals.
288
Chapter 7
Registers r Counters r and the Memory Unit
The timing signals, when enabled by the clock pulses, will provide multiplephase clock pulses. For example, if To is ANDed with CP, the output of the AND gate will generate clock pulses at onefourth the frequency of the masterclock pulses. Multiplephase clock pulses can be used for controlling different registers with different time scales. To generate 2" timing signals, we need either a shift register with 2" flipflops or an nbit counter together with an nto2"line decoder. For example. 16 timing signals can be generated with a 16bit shift register connected as a ring counter or with a 4bit counter and a 4to16line decoder. In the first case, we need 16 flipflops. In the second case, we need four flipflops and 16 4input AND gates for the decoder. It is also possible to generate the timing signals with a combination of a shift register and a decoder. In this way, the number of flipflops is less than a ring counter, and the decoder requires only 2input gates. This combination is sometimes called a Johnson counter. Johnson Counter
A kbit ring counter circulates a single bit among the flipflops to provide k distinguishable states. The number of states can be doubled if the shift register is connected as a switchtail ring counter. A switchtail ring counter is a circular shift register with the complement output of the last flipflop connected to the input of the first flipflop. Figure 723(a) shows such a shift register. The circular connection is made from the complement output of the rightmost flipflop to the input of the leftmost flipflop. The register shifts its contents once to the right with every clock pulse, and at the same time, the complement value of the E flipflop is transferred into the A flipflop. Starting from a cleared state, the switchtail ring counter goes through a sequence of eight states, as listed in Fig. 723(b). In general, a kbit switchtail ring counter will go through a sequence of 2k states. Starting from all O's, each shift operation inserts I's from the left until the register is filled with all I 's. In the following sequences, O's are inserted from the left until the register is again filled with all O's. A Johnson counter is a kbit switchtail ring counter with 2k decoding gates to provide outputs for 2k timing signals. The decoding gates are not shown in Fig. 723, but are specified in the last column of the table. The eight AND gates listed in the table, when connected to the circuit. will complete the construction of the Johnson counter. Since each gate is enabled during one particular state sequence, the outputs of the gates generate eight timing sequences in succession. The decoding of a kbit switchtail ring counter to obtain 2k timing sequences follows a regular pattern. The allD's state is decoded by taking the complement of the two extreme flipflop outputs. The allI' s state is decoded by taking the normal outputs of the two extreme flipflops. All other states are decoded from an adjacent 1,0 or 0, I pattern in the sequence. For example, sequence 7 has an adjacent 0, I pattern in flipflops Band C. The decoded output is then obtained by taking the complement of Band the normal output of C, or B' C. One disadvantage of the circuit in Fig. 7 23(a) is that if it finds itself in an unused state, it will persist in moving from one invalid state to another and never find its way
Section 77
D Q ",A"'_iD
Q'
RandomAccess Memory (RAM)
Q ""C_ _I
Q"'B=_i D
A'
Q'
0'
Q'
C'
289
E
E' Q'I''
CP~~~~
(a) Fourstage switchtail ring counter
Sequence number
Flipflop outputs ABC
I
o
0
2 3
I I I I
0
4
5
6 7 8
o o o
o
0
I
0 0
0
I I I
AND gate required for output
0
o o
0
E
I I
o
A'E' AB' Be' CE' AE A'B B'C
C'E
(b) Count sequence and required decoding. FIGURE 723 Construction of a Johnson counter
to a valid state. This difficulty can be corrected by modifying the circuit to avoid this undesirable condition. One correcting procedure is to disconnect the output from flipflop B that goes to the D input of flipflop C, and instead enable the input of flipflop C by the function: DC = (A
+ C)B
where DC is the flipflop input function for the D input of flipflop C. Johnson counters can be constructed for any number of timing sequences. The number of flipflops needed is onehalf the number of timing signals. The number of decoding gates is equal to the number of timing signals and only 2input gates are employed.
77
RANDOMACCESS MEMORY (RAM' A memory unit is a collection of storage cells together with associated circuits needed to transfer information in and out of the device. Memory cells can be accessed for information transfer to or from any desired random location and hence the name randomaccess memory, abbreviated RAM. A memory unit stores binary information in groups of bits called words. A word in
290
Chapter 7
Registers, Counters, and the Memory Unit
memory is an entity of bits that move in and out of storage as a unit. A memory word is a group of I's and O's and may represent a number, an instruction, one or more alphanumeric characters, or any other binarycoded information. A group of eight bits is called a byte. Most computer memories use words that are multiples of 8 bits in length. Thus, a 16bit word contains two bytes, and a 32bit word is made up of four bytes. The capacity of a memory unit is usually stated as the total number of bytes that it can store.
The communication between a memory and its environment is achieved through data input and output lines, address selection lines, and control lines that specify the direction of transfer. A block diagram of the memory unit is shown in Fig. 724. The n data input lines provide the information to be stored in memory and the n data output lines supply the information coming out of memory. The k address lines specify the particular word chosen among the many available. The two control inputs specify the direction of transfer desired: The write input causes binary data to be transferred into the memory, and the read input causes binary data to be transferred out of memory. The memory unit is specified by the number of words it contains and the number of bits in each word. The address lines select one particular word. Each word in memory is assigned an identification number, called an address, starting from 0 and continuing with 1, 2, 3, up to 2k  I, where k is the number of address lines. The selection of a specific word inside the memory is done by applying the kbit binary address to the address lines. A decoder inside the memory accepts this address and opens the paths needed to select the word specified. Computer memories may range from 1024 words, requiring an address of 10 bits, to 232 words, requiring 32 address bits. It is customary to refer to the number of words (or bytes) in a memory with one of the letters K (kilo), M (mega), or G (giga). K is equal to 2 10 , M is equal to 220 , and G is equal to 230. Thus, 64K ~ 2 16 , 2M ~ 221, and4G ~ 232. Consider, for example, the memory unit with a capacity of IK words of 16 bits each. Since IK ~ 1024 ~ 2 10 and 16 bits constitute two bytes, we can say that the memory can accommodate 2048 ~ 2K bytes. Figure 725 shows the possible content of the first three and the last three words of this memory. Each word contains 16 bits, n data input lines
k address lines
Read
>1
Write >1
Memory unit 2k words n bit per word
n data output lines FIGURE 724 Block dlagrdm of ,1 memory Ullit
Section 77
RandomAccess Memory IRAMI
291
Memory address
Binary
0000000000
decimal
0
Memory content
1011010101011101 1010101110001001
0000000001 0000000010
2
0000110101000110
1111111101
1021
1001110100010100
1111111110
1022
0000110100011110
11111111I1
1023
1101111000100101
FIGURE 725
Content of a '024 x '6 memory
which can be divided into two bytes. The words are recognized by their decimal address from 0 to 1023. The equivalent binary address consists of 10 bits. The first address is specified with ten D's, and the last address is specified with ten I's. This is because 1023 in binary is equal to 1111111111. A word in memory is selected by its binary address. When a word is read or written, the memory operates on all 16 bits as a single unit. The lK x 16 memory of Fig. 725 has 10 bits in the address and 16 bits in each word. As another example, a 64K x 10 memory will have 16 bits in the address (since 64K = 2 16) and each word will consist of 10 bits. The number of address bits needed in a memory is dependent on the total number of words that can be stored in the memory and is independent of the number of bits in each word. The number of bits in the address is determined from the relationship 2' = m, where m is the total number of words, and k is the number of address bits.
Write and Read Operations The two operations that a randomaccess memory can perform are the write and read operations. The write signal specifies a transferin operation and the read signal specifies a transferout operation. On accepting one of these control signals, the internal circuits inside the memory provide the desired function. The steps that must be taken for the purpose of transferring a new word to be stored into memory are as follows: 1. lhmsfer the binary address of the desired word to the address lines. 2. Transfer the data bits that must be stored in memory to the data input lines. 3. Activate the write input.
292
Chapter 7
Registers, Counters, and the Memory Unit TABLE 77 Control Inputs to Memory Chip
,~
Memory Enable
Read/Write
Memory Operation
o
x
None
o
Write to selected word Read from selected word
The memory unit will then take the bits from the input data lines and store them in the word specified by the address lines. The steps that must be taken for the purpose of transferring a stored word out of memory are as follows:
1. Transfer the binary address of the desired word to the address lines. 2. Activate the read input. The memory unit will then take the bits from the word that has been selected by the address and apply them to the output data lines. The content of the selected word does not change after reading. Commercial memory components available in integratedcircuit chips sometimes provide the two control inputs for reading and writing in a somewhat different configuration. Instead of having separate read and write inputs to control the two operations. some integrated circuits provide two other control inputs: one input selects the unit and the other determines the operation. The memory operations that result from these control inputs are specified in Table 77. The memory enable (sometimes called the chip select) is used to enable the particular memory chip in a multichip implementation of a large memory. When the memory enable is inactive. the memory chip is not selected and no operation is performed. When the memory enable input is active. the read/write input determines the operation to be performed. Types of Memories
The mode of access of a memory system is determined by the type of components used. In a randomaccess memory, the word locations may be thought of as being separated in space, with each word occupying one particular location. In a sequentialaccess memory, the information stored in some medium is not immediately accessible, but is available only at certain intervals of time. A magnetictape unit is of this type. Each memory location passes the read and write heads in turn, but information is read out only when the requested word has been reached. The access time of a memory is the time required to select a word and either read or write it. In a randomaccess memory, the access time is always the same regardless of the particular location of the word. In a sequentialaccess memory, the time it takes to access a word depends on the position of the word with respect to the readinghead position and therefore, the access time is variable.
Section 7·8
Memory Decoding
293
Integratedcircuit RAM units are available in two possible operating modes, static and dynamic. The static RAM consists essentially of internal flipflops that store the binary information. The stored information remains valid as long as power is applied to the unit. The dynamic RAM stores the binary information in the form of electric charges that are applied to capacitors. The capacitors are provided inside the chip by MaS transistors. The stored charge on the capacitors tends to discharge with time and the capacitors must be periodically recharged by refreshing the dynamic memory. Refreshing is done by cycling through the words every few milliseconds to restore the decaying charge. Dynamic RAM offers reduced power consumption and larger storage capacity in a single memory chip, but static RAM is easier to use and has shorter read and write cycles. Memory units that lose the stored information when power is turned off are said to be volatile. Integratedcircuit RAMs, both static and dynamic, are of this category since the binary cells need external power to maintain the stored information. In con· trast, a nonvolatile memory, such as magnetic disk, retains its stored information after removal of power. This is because the data stored on magnetic components is manifested by the direction of magnetization, which is retained after power is turned off. Another nonvolatile memory is the readonly memory (ROM) discussed in Section 57. A nonvolatile property is desirable in digital computers to store programs that are needed while the computer is in operation. Programs and data that cannot be altered are stored in ROM. Other large programs are maintained on magnetic disks. When power is turned on, the computer can use the programs from ROM. The other programs residing on disks can be transferred into the computer RAM as needed. Before turning the power off, the user transfers the binary information from the computer RAM into a disk if this information must be retained.
7·8
MEMORY DECODING
In addition to the storage components in a memory unit, there is a need for decoding circuits to select the memory word specified by the input address. In this section, we present the internal construction of a randomaccess memory and demonstrate the operation of the decoder. To be able to include the entire memory in one diagram, the memory unit presented here has a small capacity of 12 bits arranged in 4 words of 3 bits each, In addition to internal decoders, a memory unit may also need external decoders. This happens when integratedcircuit RAM chips are connected in a multichip memory configuration. The use of an external decoder to provide a large capacity memory will be demonstrated by means of an example. Internal Construction
The internal construction of a randomaccess memory of m words with n bits per word consists of m x n binary storage cells and associated decoding circuits for selecting individual words. The binary storage cell is the basic building block of a memory unit.
294
Chapter 7
Registers .. Counters. and the Memory Unit
Select
),R
Input
4.jj
}js
Q 11
Output
Read/write (a) Logic diagram
Select
Output
Input
Read/write (b) Block diagram FIGURE 726 Merno! y cell
The equivalent logic of a binary cell that stores one bit of information is shown in Fig. 726. Although the cell is shown to include gates and a flipflop, internally, it is constructed with two transistors having multiple inputs. A binary storage cell must be very small in order to be able to pack as many cells as possible in the area available in the integratedcircuit chip. The binary cell stores one bit in its internal flipflop. It has three inputs and one output. The select input enables the cell for reading or writing and the read/write input determines the cell operation when it is selected. A I in the read/ write input provides the read operation by forming a path from the flipflop to the output terminal. A 0 in the read/write input provides the write operation by forming a path from the input terminal to the flipflop. Note that the flipflop operates without a clock and is similar to an SR latch (see Fig. 62). The logical construction of a small RAM is shown in Fig. 727. It consists of 4 words of 3 bits each and has a total of 12 binary cells. Each block labeled Be represents the binary cell with its three inputs and one output, as specified in Fig. 726(b). A memory with four words needs two address lines. The two address inputs go through a 2 X 4 decoder to select one of the four words. The decoder is enahled with the memoryenable input. When the memory enable is 0, all outputs of the decoder are 0
Section 1·8 Memory Decoding
295
Data inputs Word 0
Do~~~+~~+~~,
D\
Word I
Address inputs
2,4 decoder
D,
D,
Word 2
Word 3
Memory _ _ _ I
enable Read/write O.II+I+.....
+++ll
Data outputs FIGURE 1·27 Logical construction of a 4 x 3 RAM
and none of the memory words are selected. With the memory enable at I, one of the four words is selected, dictated by the value in the two address lines. Once a word has been selected, the read/write input determines the operation. During the read opera· tion, the four bits of the selected word go through OR gates to the output terminals. During the write operation, the data available in the input lines are transferred into the four binary cells of the selected word. The binary cells that are not selected are dis· abled and their previous binary values remain unchanged. When the memory· enable input that goes into the decoder is equal to 0, none of the words are selected and the contents of all cells remain unchanged regardless of the value of the read/write input.
296
Chapter 7
Registers Counters. and the Memory Unit l
Commercial randomaccess memories may have a capacity of thousands of words and each word may range from I to 64 bits. The logical construction of a large capacity memory would be a direct extension of the configuration shown here. A memory with 2' words of n bits per word requires k address lines that go into a k x 2' decoder. Each one of the decoder outputs selects one word of n bits for reading or writing. Array of RAM Chips
Integratedcircuit RAM chips are available in a variety of sizes. If the memory unit needed for an application is larger than the capacity of one chip, it is necessary to combine a number of chips in an array to form the required memory size. The capacity of the memory depends on two parameters: the number of words and the number of bits per word. An increase in the number of words requires that we increase the address length. Every bit added to the length of the address doubles the number of words in memory. The increase in the number of bits per word requires that we increase the length of the data input and output lines, but the address length remains the same. To demonstrate with an example, let us first introduce a typical RAM chip, as shown in Fig. 728. The capacity of the RAM is 1024 words of 8 bits each. It requires a 10bit address and 8 input and output lines. These are shown in the block diagram by a single line and a number indicating the total number of inputs or outputs. The chipselect (CS) input selects the particular RAM chip and the read/write (RW) input specifies the read or write operation when the chip is selected. Suppose that we want to increase the number of words in the memory by using two or more RAM chips. Since every bit added to the address doubles the binary number that can be formed, it is natural to increase the number of words in factors of 2. For example, two RAM chips will double the number of words and add one bit to the composite address. Four RAM chips multiply the number of words by 4 and add two bits to the composite address. Consider the possiblity of constructing a 4K x 8 RAM with four 1K x 8 RAM chips. This is shown in Fig. 729. The 8 input data lines go to all the chips. The outputs must be ORed together to form the common 8 output data lines. (The OR gates are not shown in the diagram.) The 4K word memory requires a 12bit address. The 10 least significant bits of the address are applied to the address inputs of all four chips. RAMIKX8 Input data Address
DATA (8) ADRS (10)
Chip select
CS
Read/write
RW
FIGURE 128 Block diagram of a ) K
>(
8 RAM dllp.
(8)
Output data
Section 7·8
Input data
Address Lines
Lines 110
y ~ 3
2
1
8 lines 01023 RAMIKX8
2X4 decoder
Memory enable +
297
Memory Decoding
~
0
DATA

ADRS
I
CS
Read/wn'te
RW 10242047 RAM IK X 8 ~
DATA
f
ADRS CS RW 20483071 RAMIKX8
f DATA ADRS
f
CS RW 30724095 RAM IK X 8
'
DATA
f
ADRS CS RW Output data FIGURE 729 Block diagram of a 4K x 8 RAM.
298
Chapter 7
Registers, Counters, and the Memory Unit
The other two most significant bits are applied to a 2 x 4 decoder. The four outputs of the decoder are applied to the CS inputs of each chip. The memory is disabled when the memoryenable input of the decoder is equal to O. This causes all four outputs of the decoder to be in the 0 state and none of the chips are selected. When the decoder is enabled, address bits 12 and II determine the particular chip that is selected. If bits 12 and II are equal to 00, the first RAM chip is selected. The remaining ten address bits select a word within the chip in the range from 0 to 1023. The next 1024 words are selected from the second RAM chip with a 12bit address that starts with 01 and follows by the ten bits from the common address lines. The address range for each chip is listed in decimal over its block diagram in Fig. 729. It is also possible to combine two chips to form a composite memory containing the same number of words but with twice as many bits in each word. Figure 730 shows the interconnection of two IK x 8 chips to form a IK x 16 memory. The 16 input and output data lines are split between the two chips. Both receive the same IObit address and the common CS and RW control inputs. The two techniques just described may be combined to assemble an array of identical chips into a largecapacity memory. The composite memory will have a number of bits per word that is a multiple of that for one chip. The total number of words will increase in factors of 2 times the word capacity of one chip. An external decoder is needed to 16 input data lines
~ (8)
~ (8)
(10)
Address
RAMIKX8

DATA
RAMIKX8

I
DATA
ADRS
ADRS
Chip select
cs
cs
Read/write
RW
.
(8)
~(8)
16 output data lines FIGURE 7·30 Block didgr ilrrl of
(j
11
fl
J r
rr'
~
Q E
t> K
J
Q
IF
> t> K
A,
A,
A,
Al Count
4bit counter with synchronous clear
CP
Clock pulses
Clear
FIGURE 810 Data processor for design example
such as registers, counters, multiplexers, and adders. The design of the control subsystem requires the application of design procedures based on the theory of sequential logic. The next three sections present some of the alternatives that are available for designing the control logic. 84
CONTROL IMPLEMENTATION The control section of a digital system is essentially a sequential circuit that can be designed by the procedure outlined in Chapter 6. However, in most cases, this method is impractical because of the large number of states and inputs that a typical control cir
318
Chapter 8
Algorithmic State Machines (ASM I
cuit may have. Except for very simple controllers. the design method that uses state and excitation tables is cumbersome and difficult to manage. Experienced digital designers use specialized methods for control logic design that may be considered an extension of the classical sequential method combined with other simplified assumptions. Two of these specialized methods are presented in this section. and a third method is explained in Section 85. Another alternative is to use a ROM or PLA to design the control logic. This is covered in Section 86. State Table
As mentioned previously. the ASM chart resembles a state diagram, with each state box representing a state. The state diagram can be converted into a state table from which the sequential circuit of the controller can be designed. First, we must assign binary values to each state in the ASM chart. For n flipflops in the control sequential circuit, the ASM chart can accommodate up to 2' states. A chart with three or four states requires a sequential circuit with two flipflops. With five to eight states, there is a need for three flipflops. Each combination of flipflop values represents a binary number for one of the states. A state table for a controller is a list of present states and inputs and their corresponding next states and outputs. In most cases, there are many don'tcare input conditions that must be included, so it is advisable to arrange the state table to take this into consideration. In order to clarify the procedure, we will illustrate by obtaining the state table of the controller defined in the example of the previous section. The ASM chart of the design example is shown in Fig. 89. We assign the following binary values to the three states: To = 00, T, = 01, T, = II. Binary state 10 is not used and will be treated as a don'tcare condition. The state table corresponding to the ASM chart is shown in Table 83. Two flipflops are needed, and they are labeled G, and G2 • There are three inputs and three outputs. The inputs are taken from the conditions in the decision boxes. The outputs are equivalent to the present state of the control. Note that there is a row in the table for each possible transition between states. Initial state 00 goes to state 01 or stays in 00, depending on the value of input S. The TABLE 8~3 State Table for Control of Fig. 810 ...
_"
PresentState Symbol
Present State
     _. .
G,
G,
5
A, "
0 0 0 0 0
"
Next State
Inputs _.
_.
To To T, T, T, T,
"
0 0
0 X X X X
X X 0
A, X X X 0
1 X
Outputs

1 X
G,
G,
0 0 0 0 1 0
0

       _...
T,
0 0
1 0
0 0
T,
T,
0 0 1 1 1 0
0 0 0 0 0 1
Section 8~
Control Implementation
319
other two inputs are marked with don'tcare X's, as they do not determine the next state in this case. While the system is in binary state 00, the control provides an output labeled To to initiate the required register operations. The transition from binary state 01 depends on inputs A, and A 4. The system goes to binary state II only if A,A4 = II; otherwise, it remains in binary state 01. Finally, binary state 11 goes to 00 independently of the input variables. This example demonstrates a state table for a sequential controller. Note again the large number of don'tcare conditions under the inputs. The number of rows in the state table is equal to the number of distinct paths between the states in the ASM chart. Logic Diagram with JK FlipFlops
The procedure for designing a sequential circuit starting from a state table is presented in Section 67. This procedure requires that we obtain the excitation table of the flipflop inputs and then simplify the combinationalcircuit part of the sequential circuit. If we apply this procedure to Table 83, we will need to use fivevariable maps (see Fig. 312) to simplify the input functions. This is because there are five variables listed under the "presentstate" and "input" columns. Since this procedure was explained in Chapter 6, we will not show the detail work here. The flipflop input functions obtained by this method, if we assume JK flipflops, are JG, = G,A,A 4 KG,
=
JG, = S KG, = G,
I
To derive the three output functions, we can utilize the fact that binary state 10 is not used and obtain the following simplified functions:
To = O 2 T,=G[G, T, = G,
The logic diagram of the control is shown in Fig. 811. This circuit replaces the control block in Fig. 810.
o FlipFlops and Decoder When the number of flipflops plus inputs in a state table is greater than 5, it is necessary to use large maps to simplify the input functions. This is cumbersome and difficult to achieve, as explained in Chapter 3. Therefore, it is necessary to find alternative ways to design controllers except when they are very simple. One possibility is to use Dtype flipflops and obtain the input functions directly from the state table without the need of an excitation table. This is because the next state is the same as the input requirement for the D flipflops (see Section 67). To design the sequential circuit with D flipflops,
320
Chapter 8
Algorithmic State Machines IASMJ
s
J
,
G2
Q
> G1
Q'
K
T [)
DA3
r'\.
A, II
Gli
Q
J
T
,
t> G'1
Q'
K
CP FIGURE 811 LogIC dlaqr
325
Design with MultJplexen
Qr
>
3
"
'0
2 x 4 decoder
MUX select

r
"
'0
G,
wO
x' I y
z
=fJ
MUX2
D

2
Q
I'
>
y' 3
CP FIGURE 816 Control implementation with multiplexers
transitions given in the ASM chart. For example, state 00 stays at 00 or goes to 01, de· pending on the value of input w. Since the next state of G, is 0 in either case, we place a signal equivalent to 10gic·O in MUXI input O. The next state of G, is 0 if w = 0 and I if w = I. Since the next state of G, is equal to w, we apply control intput w to MUX2 input O. What this means is that when the select inputs of the multiplexers are equal to present state 00, the outputs of the multiplexers provide the binary value that is trans· ferred to the register during the next clock pulse. To facilitate the evaluation of the multiplexer inputs, we prepare a table showing the input conditions for each possible transition in the ASM chart. Table 84 gives this in· formation for the ASM chart of Fig. 815. There are two transitions from present state 00 or 01 and three transitions from present state 10 or II. These are separated by hori· zontallines across the table. The input conditions listed in the table are obtained from the decision boxes in the ASM chart. For example, from Fig. 815, we note that present state 01 will go to next state 10 if x = I or to next state II if x = O. In the table, we mark these input conditions as x and x ' , respectively. The two columns under "multiplexer inputs" in the table specify the input values that must be applied to MUXI and MUX2. The multiplexer input for each present state is determined from the input conditions when the next state of the flip.flop is equal to 1. Thus, after present state 01, the next state of G, is always equal to I and the next state of G, is equal to the comple· ment value of x. Therefore, the input of MUXI is made equal to 1 and that of MUX2
326
Chapter 8
Algorithmic State Machines (ASM t
TABLE 8·4
,
Multiplexer '"put Conditions Present State
I
G,
G,
,I
Next State
Input Conditions
G,
G,
o o
o
w'
I
w
o
x x'
1
o
o 1 1
o
o 1
o
y yz' yz y'z )'
y'z'
Multiplexer Inputs
,I
MUXI
1
t
,
o
f I
+ I I
tI
i ____ l
i
1
r yz'
+ yz
= Y
y+y'ZI=y+ZI
i I
1
yz
I
to x' when the present state of the register is 01. As another example, after present state 10, the next state of G, must be equal to I if the input conditions are yz' or yz. When these two Boolean terms are ORed together and then simplified, we obtain the single binary variable y, as indicated in the table. The next state of G2 is equal to I if the input conditions are yz = II. If the next state of G, remains at 0 after a given present state, we place a 0 in the multiplexer input as shown in present state 00 for MUX I. If the next state of G, is always I, we place a I in the multiplexer input as shown in present state 01 for MUXI. The other entries for MUXI and MUX2 are derived in a similar manner. The multiplexer inputs from the table are then used in the control implementation of Fig. 816. Note that if the next state of a flipflop is a function of two or more control variables, the multiplexer may require one or more gates in its input. Otherwise, the multiplexer input is equal to the control variable, or the complement of the control variable, or 0, or I. Design Example
We will demonstrate the multiplexer control implementation by means of a second design example. The example will also demonstrate the formulation of the ASM chart and the implementation of the dataprocessor subsystem. The digital system to be designed consists of two registers, RI and R2, and a flipflop, E. The system counts the number of I's in the number loaded into register RI and sets register R2 to that number. For example, if the binary number loaded into RI is 10111001, the circuit counts the five I's in RI and sets register R2 to the binary count 101. This is done by shifting each bit from register RI one at a time into flipflop E. The value in E is checked by the control, and each time it is equal to I, register R2 is incremented by I.
Section 85
Design with Multiplexers
327
The control subsystem uses one external input S to start the operation and two status inputs E and Z from the data processor. E is the output of the flipflop. Z is the output of a circuit that checks the contents of register RI for all a's. The circuit produces an output Z = I when R I is equal to O. The ASM chart for the design example is shown in Fig. 817. The binary number is loaded into RI, and register R2 is set to an allI's value. Note that a number with all I's in a register when incremented produces a number with alia's. In state T .. register R2 is incremented and the content of RI is examined. If the content is zero, then Z = I, and it signifies that there are no I's stored in the register; so the operation terminates with R2 equal to O. If the content of RI is not zero, then Z = 0, and it indicates that
FIGURE 817 ASM chart for design example
328
Chapter 8
Algorithmic State Machines IASM)
there are some I' s stored in the register. The number in R I is shifted and its leftmost bit transferred into E. This is done as many times as necessary until a 1 is transferred into E. For every I detected in E, register R2 is incremented and register RI is checked again for more I's. The major loop is repeated until all the I's in RI are counted. Note that the state box of 1; has no register operations, but the block associated with it contains the decision box for E. Also note that the serial input to shift register R I must be equal to 0 because we don't want to shift external I's into RI. The dataprocessor subsystem is shown in Fig. 818. The control has three inputs
1
Start
To
S
L>
T, E
Control
Z
T, TJ

Z'" I if Ri = 0 Check for zero
Parallel output
S"iai inpul = 0
..
E
' Q
nH
L
Shift register R I
Shift left Load input
 II
(c) Unstable
Section '·2 Analysis Procedure
351
Stability Considerations Because of the feedback connection that exists in asynchronous sequential circuits, care must be taken to ensure that the circuit does not become unstable. An unstable condition will cause the circuit to oscillate between unstable states. The transitiontable method of analysis can be useful in detecting the occurrence of instability. Consider, for example, the circuit of Fig. 99(a). The excitation function is Y = (XIY)'X2 = (xi
+ Y')X2
= x,x2
+
X2Y'
The transition table for the circuit is shown in Fig. 99(b). Those values of Y that are equal to yare circled and represent stable states. The uncircled entries indicate unstable conditions. Note that column II has no stable states. This means that with input XIX2 fixed at 11, the values of Y and y are never the same. If y = 0, then Y ,;, 1, which causes a transition to the second row of the table with y = 1 and Y = O. This causes a transition back to the first row, with the result that the state variable alternates between o and I indefinitely as long as the input is 11. The instability condition can be detected directly from the logic diagram. Let XI = 1, X2 = 1, and y = 1. The output of the NAND gate is equal to 0, and the output of the AND gate is equal to 0, making Y equal to 0, with the result that Y y. Now if y = 0, the output of the NAND gate is I, the output of the AND gate is I, making Y equal to I, with the result that Y y. If it is assumed that each gate has a propagation delay of 5 ns (including the wires), we will find that Y will be 0 for 10 ns and I for the next 10 ns. This will result in a squarewave waveform with a period of 20 ns. The frequency of oscillation is the reciprocal of the period and is equal to 50 MHz. Uuless one
'*
'*
: ,SO c;;J, (a) Logic diagram
00
10
y
o
0 0
1
1
0
CD
0
0
(b) Transition table
FIGURE 99 Example of an unstable circuit
352
Chapter 9
Asynchronous Sequential Logic
is designing a squarewave generator, the instability that may occur in asynchronous sequential circuits is undesirable and must be avoided.
93
CIRCUITS WITH LATCHES Historically, asynchronous sequential circuits were known and used before synchronous circuits were developed. The first practical digital systems were constructed with relays, which are more adaptable to asynchronoustype operations. For this reason, the traditional method of asynchronouscircuit configuration has been with components that are connected to form one or more feedback loops. As electronic digital circuits were developed, it was realized that the flipflop circuit could be used as a memory element in sequential circuits. Asynchronous sequential circuits can be implemented by employing a basic flipflop commonly referred to as an SR wlch. The use of SR latches in asynchronous circuits produces a more orderly pattern, which may result in a reduction of the circuit complexity. An added advantage is that the circuit resembles the synchronous circuit in having distinct memory elements that store and specify the internal states. In this section, we will first explain the operation of the SR latch using the analysis technique introduced in the previous section. We will then proceed to give examples of analysis and implementation of asynchronous sequential circuits that employ SR latches.
SR Latch
The SR latch is a digital circuit with two inputs, Sand R, and two crosscoupled NOR gates or two crosscoupled NAND gates. This circuit was introduced in Section 62 as a basic flipflop from which other, more complicated flipflop circuits were obtained. The crosscoupled NOR circuit is shown in Fig. 91O(a). This circuit, and the truth table listed in Fig. 910(b), were taken directly from Fig. 62. In order to analyze the circuit by the transitiontable method, we redraw the circuit, as shown in Fig. 91O(c). Here we distinctly see a feedback path from the output of gate 1 to the input of gate 2. The output Q is identical to the excitation variable Y and the secondary variable y. The Boolean function for the output is Y
=
[(S
+ y)' +
RI'
=
(S
+
y)R'
=
SR'
+ R'y
Plotting Yas in Fig. 910(d), we obtain the transition table for the circuit. We can now investigate the behavior of the SR latch from the transition table. With SR = 10, the output Q = Y = 1 and the latch is said to be set. Changing S to 0 leaves the circuit in the set state. With SR = OJ, the output Q = Y = 0 and the latch is said to be reset. A change of R back to 0 leaves the circuit in the reset state. These conditions are also listed in the truth table. The circuit exhibits some difficulty when both S and R are equal to 1. From the truth table, we see that both Q and Q' are equal to 0, a condition that violates the requirement that these two outputs be the complement of
353
Section '3 Circuits with Latches
R
Q
R
1
0
0
0
0
0
Q
0
1
0
0
0
0
Q'
S
Q'
S
(After SR
~
10)
(AfterSR
~
01)
0
0
(b) Truth table
(a) Crossedcoupled circuit
SR
Rr......):)jp y r",,__'
S
l,"
~
Q
y 0
01
00
II
10
G) G) G) 1 G) 0 0 G)
y
Y = SR' + R'y y = S + R'y when SR = (c) Circuit showing feedback
a
(d) Transition table
FIGURE 9·10 SR latch with NOR gates
each other. Moreover, from the transition table, we note that going from SR = 11 to SR = ()() produces an unpredictable result. If S goes to 0 first, the output remains at 0, but if R goes to 0 first, the output goes to I. In normal operation, we must make sure that I's are not applied to both the Sand R inputs simultaneously. This condition can be expressed by the Boolean function SR = 0, which states that the ANDing of Sand R must always result in a o. Coming back to the excitation function, we note that when we OR the Boolean expression SR' with SR, the result is the single variable S. SR'
+ SR = S(R' + R) = S
From this we deduce that SR' = S when SR = O. Therefore, the excitation function derived previously, Y = SR' + R'y can be expressed as Y = S + R'y whenSR = 0 To analyze a circuit with an SR latch, we must first check that the Boolean condition SR = 0 holds at all times. We then use the reduced excitation function to analyze the
354
Chapter 9
Asynchronous Sequential Logic
s i,'b__~_ Q
S
R!
1
0
Q
Q'
~
1
RILJ
1
I
o )O'Q'
I ~
=
10)
(After SR
=
01 )
o
I
o
__ ~___ o_l __
(a) Crossedcoupled circuit
\After SR
(b) Truth table
SR sf~ )0, l'
c
00
Q
01
11
10
y
0
R'r""""\
(1 'I '''
/
y
Y
=
S'
+
R, with S'R'
=
0
(d) Tran:;ition table
(c) Circllit showing feedback FIGURE 9·11
SR latch with NAND gates
circuit. However, if it is found that both Sand R can be equal to I at the same time, then it is necessary to use the original excitation function.
The analysis of the SR latch with NAND gates is carried out in Fig. 911. The NAND latch operates with both inputs normally at I unless the state of the latch has to be changed. The application of 0 to R causes the output Q to go to 0, thus putting the latch in the reset state. After the R input returns to 1, a change of S to 0 causes a change to the set state. The condition to be avoided here is that both Sand R not be 0 simultaneously. This condition is satisfied when S'R' ~ O. The excitation function for the circuit is
y
~
[S(Ry)']'
~
S'
+
Ry
Comparing it with the excitation function of the NOR latch, we note that S has been replaced with S' and R' with R. Hence, the input variables for the NAND latch require the complemented values of those used in the NOR latch. For this reason, the NAND latch is sometimes referred to as an S'R' latch (or SR latch). Analysis Example
Asynchronous sequential circuits can be constructed with the use of SR latches with or without external feedback paths. Of course, there is always a feedback loop within the latch itself. The analysis of a circuit with latches will be demonstrated by means of a
Section 9J Circuits with Latches
355
specific example. From this example, it will be possible to generalize the procedural steps necessary to analyze other, similar circuits. The circuit shown in Fig. 912 has two SR latches with outputs Yl and Y2 • There are two inputs, Xl and X" and two external feedback loops giving rise to the secondary variables Yl and Y2. Note that this circuit resembles a conventional sequential circuit with latches behaving like flipflops without clock pulses. The analysis of the circuit requires that we first obtain the Boolean functions for the Sand R inputs in each latch. S2 = X,X2
Rl = XiX2
R2 = X2YI
We then check whether the condition SR = 0 is satisfied to ensure proper operation.
= XtY2xlx2 = 0 S2R 2 = XtX2X2 Yl = 0 X2X 2 = o. SIR t
The result is 0 because x, x i =
The next step is to derive the transition table of the circuit. Remember that the transition table specifies the value of Y as a function of y and x. The excitation functions are derived from the relation Y = S + R' y.
)O+y,
,"1_"
s, x,~i FIGURE '·12 Example of a circuit with SR latches
__'
356
Chapter 9
Asynchronous Sequential Logic
00
01
II
10
00
00; ~'
(001
01
~)
01
(oi"' , .l
(01)
11
11
II
00
,'II) (_I~) \
00
(ja)
}'lY2
~j
\.
,
10
/ ~
10
/
II
: 10 :' /
FIGURE 913 Transition t.'1blc tor HIe eucuit of Flg_ 9 12
YI
= SI + RrYI = XIYZ +
Y2
=
52 +
R~Y2 =
XIX2
+
(Xl
+
(Xl
+ Y[)Y2
X2)YI
= XIY2 + XIYI + X2Yl = XIXl + X2Y2 + y; Yl
We now develop a composite map for Y = Y\ y,. The y variables are assigned to the rows in the map, and the x variables are assigned to the columns, as shown in Fig. 913. The Boolean functions of Y\ and Y, as expressed above are used to plot the composite map for Y. The entries of Y in each row that have the same value as that given to Y are circled and represent stable states. From investigation of the transition table, we deduce that the circuit is stable. There is a critical race condition when the circuit is initially in total state y\y,x\x, = llOi and x, changes from I to O. If Y\ changes to 0 before Y" the circuit goes to total state 0100 instead of 0000. However, with approximately equal delays in the gates and latches, this undesirable situation is not likely to occur. The procedure for analyzing an asynchronous sequential circuit with SR latches can be summarized as follows:
1. Label each latch output with Y, and its external feedback path (if any) with y: for i=1,2, ...• k. 2. Derive the Boolean functions for the S: and R: inputs in each latch. 3. Check whether SR = 0 for each NOR latch or whether S 'R' = 0 for each NAND latch. If this condition is not satisfied, there is a possibility that the circuit may not operate properly. 4. Evaluate Y = S + R' Y for each NOR latch or Y = S' + Ry for each NAND latch. 5. Construct a map with the y's representing the rows and the x inputs representing the columns. 6. Plot the value of Y = Y\ Y2 • • • Y, in the map. 7. Circle all stable states where Y = y. The resulting map is then the transition table.
Section 9·3 Circuits with Latches
357
Implementation Example
The implementation of a sequential circuit with SR latches is a procedure for obtaining the logic diagram from a given transition table. The procedure requires that we deter· mine the Boolean functions for the Sand R inputs of each latch. The logic diagram is tben obtained by drawing the SR latches and the logic gates that implement the Sand R functions. To demonstrate the procedure, we will repeat the implementation example of Fig. 9·5. The output circuit remains the same and will not be repeated again. The transition table from Fig. 9·5(a) is duplicated in Fig. 9·14(a). The latch excita· tion table is shown in Fig. 9~14(b). Remember that the transition table resembles a state table with y representing the present state and Y the next state. Moreover, the ex· citation table for the SR latch is exactly the same as that of an RS flip·flop as listed pre·
y
o
00
01
10
II
CD CD CD 0
0
I
0) 0)
(a) Transition table y ~ xlxi + x\y
y
o
00
01
y
0
0
0
0
0
X
y
s
R
o o
o
o
x o
o
o x
I
o
(b) Latch excitation table
10
II
y
'1
o
X
~
00
0\
II
\0
X
X
X
0
I
I
0
0
(d) Map for R ::: x~
(c) MapforS=xjxi
y
s
R (e) Circuit with NOR latch
FIGURE 9·14 Derivation of a latch circuit from a transition table
(f) Circuit with NAND latch
y
358
Chapter 9
Asynchronous SequentIal Logic
viously in Table 610, except thaty is replaced by Q(t) and Yby Q(t + I). Thus, the excitation table for the SR latch is used in the design of asynchronous sequential circuits just as the RS flipflop excitation table is used in the design of synchronous sequential circuits as described in Section 67. From the information given in the transition table in Fig. 914(a) and from the latch excitation table conditions in Fig. 914(b), we can obtain the maps for the Sand R inputs of the latch, as shown in Fig. 914(c) and (d). For example, the square in the second row and third column (YX,X2 ~ III) in Fig. 914(a) requires a transition from y = I to Y = I. The excitation table specifies S = X, R ~ 0 for this change. Therefore, the corresponding square in the S map is marked with an X and the one in the R map with a O. All other squares are filled with values in a similar manner. The maps are then used to derive the simplified Boolean functions. and
R =
x;
The logic diagram consists of an SR latch and the gates required to implement the Sand R Boolean functions. The circuit is as shown in Fig. 914(e) when a NOR latch is used. With a NAND latch, we must use the complemented values for Sand R. S
=
(XIX;)'
and
R =
Xl
This circuit is shown in Fig. 914(f). The general procedure for implementing a circuit with SR latches from a given transition table can now be summarized as follows: 1. Given a transition table that specifies the excitation function Y = y, y, ... Y" derive a pair of maps for S, and R, for each i = 1,2, ... , k. This is done by us
ing the conditions specified in the latch excitation table of Fig. 914(b). 2. Derive the simplified Boolean functions for each S, and R,. Care must be taken not to make S, and R, equal to I in the same minterm square. 3. Draw the logic diagram using k latches together with the gates required to generate the Sand R Boolean functions. For NOR latches, use the Sand R Boolean functions obtained in step 2. For NAND latches, use the complemented values of those obtained in step 2. Another useful example of latch implementation can be found in Section 97 in conjunction with Fig. 938. Debounce Circuit
Input binary information in a digital system can be generated manually by means of mechanical switches. One position of the switch provides a voltage equivalent to logic I, and the other position provides a second voltage equivalent to logic O. Mechanical switches are also used to start, stop, or reset the digital system. When testing digital circuits in the laboratory, the input signals will normally come from switches. A common characteristic of a mechanical switch is that when the arm is thrown from one po
sition to the other, the switch contact vibrates or bounces several times before coming to a final rest. In a typical switch, the contact bounce may take several milliseconds to
Section 94
Design Procedure
359
s b+Q
A
) B
R Ground
b4.Q' A_B.~A_
FIGURE 915 Oebounce circuit
die out. This may cause the signal to oscillate between 1 and 0 because the switch contact is vibrating. A debounce circuit is one that removes the series of pulses that result from a contact bounce and produces a single smooth transition of the binary signal from 0 to I or from I to O. One such circuit consists of a singlepole doublethrow switch connected to an SR latch, as shown in Fig. 915. The center contact is connected to ground that provides a signal equivalent to logicO. When one of the two contacts, A or B, is not connected to ground through the switch, it behaves like a logicI signal. A resistor is sometimes connected from each contact to a fixed voltage to provide a firm logicI signal. When the switch is thrown from position A to position B and back, the outputs of the latch produce a single pulse as shown, negative for Q and positive for Q'. The switch is usually a pushbutton whose contact rests in position A. When the pushbutton is depressed, it goes to position B and when released, it returns to position A. The operation of the debounce circuit is as follows. When the switch rests in position A, we have the condition S = 0, R = 1 and Q = 1, Q' = 0 (see Fig. 911(b)). When the switch is moved to position B, the ground connection causes R to go to 0 while S becomes a 1 because contact A is open. This condition causes output Q to go to 0 and Q' to go to 1. After the switch makes an initial contact with B, it bounces several times, but for proper operation, we must assume that it does not bounce back fur enough to reach point A. The output of the latch will be unaffected by the contact bounce because Q' remains I (and Q remains 0) whether R is equal to 0 (contact with ground) or equal to 1 (no contact with ground). When the switch returns to position A, S becomes 0 and Q returns to 1. The output again will exhibit a smooth transition even if there is a contact bounce in position A. 94
DESIGN PROCEDURE
The design of an asynchronous sequential circuit starts from the statement of the problem and culminates in a logic diagram. There are a number of design steps that must be carried out in order to minimize the circuit complexity and to produce a stable circuit without critical races. Briefly, the design steps are as follows. A primitive flow table is obtained from the design specifications. The flow table is reduced to a minimum number of states. The states are then given a binary assignment from which we obtain the
360
Chapter 9
Asynchronous Sequential Logic
transition table. From the transition table, we derive the logic diagram as a combinational circuit with feedback or as a circuit with SR latches. The design process will be demonstrated by going through a specific example. Once this example is mastered, it will be easier to understand the design steps that are enumerated at the end of this section. Some of the steps require the application of formal procedures, and these are discussed in greater detail in the following sections. Design Example
It is necessary to design a gated latch circuit with two inputs, G (gate) and D (data), and one output, Q. Binary information present at the D input is transferred to the Q output when G is equal to I. The Q output will follow the D input as long as G = I. When G goes to 0, the information that was present at the D input at the time the transition occurred is retained at the Q output. The gated latch is a memory element that accepts the value of D when G = I and retains this value after G goes to O. Once G = 0, a change in D does not change the value of the output Q. Primitive Flow Table
As defined previously, a primitive flow table is a flow table with only one stable total state in each row. Remember that a total state consists of the internal state combined with the input. The derivation of the primitive flow table can be facilitated if we first form a table with all possible total states in the system. This is shown in Table 92 for the gated latch. Each row in the table specifies a total state, which consists of a letter designation for the internal state and a possible input combination for D and G. The output Q is also shown for each total state. We start with the two total states that have G = I. From the design specifications, we know that Q = 0 if DG = 0 I and Q = I if DG = I I because D must be equal to Q when G = I. We assign these conditions to states a and b. When G goes to 0, the output depends on the last value of D. Thus, if the transition of DG is from 01 to 00 to 10, then Q must remain 0 because Dis 0 at the time of the transition from 1 to 0 in G. If the transition of DG is from 11 to 10 to 00, then Q must remain I. This information results in six different total states, as shown in TABLE 92 GatedLatch Total States
out~I .
Input,> State
0
a
0
h c
0o
G
__ ~ Comments
D = Q because G =
I 0
d
0 I
l'
I
0
I
0
0
o o
0
             
_.
________ _
I
D= QbecauseG= A fter state a or d After state c After state b or I
L _ ~f"t~.r
_state e, _____
Section 94
Design Procedure
361
the table. Note that simultaneous transitions of two input variables, such as from 01 to 10 or from 11 to 00, are not allowed in fundamentalmode operation. The primitive flow table for the gated latch is shown in Fig. 916. It has one row for each state and one column for each input combination. First, we fill in one square in each row belonging to the stable state in that row. These entries are determined from Table 92. For example, state a is stable and the output is 0 when the input is 01. This information is entered in the flow table in the first row and second column. Similarly, the other five stable states together with their output are entered in the corresponding input columns. Next we note that since both inputs are not allowed to change simultaneously, we can enter dash marks in each row that differs in two or more variables from the input variables associated with the stable state. For example, the first row in the flow table shows a stable state with an input of 01. Since only one input can change at any given time, it can change to 00 or 11, but not to 10. Therefore, we enter two dashes in the 10 column of row a. This will eventually result in a don'tcare condition for the next state and output in this square. Following this procedure, we fill in a second square in each row of the primitive flow table. Next it is necessary to find values for two more squares in each row. The comments listed in Table 92 may help in deriving the necessary information. For example, state c is associated with input 00 and is reached after an input change from state a or d. Therefore, an unstable state c is shown in column 00 and rows a and d in the flow table. The output is marked with a dash to indicate a don'tcare condition. The interpretation of this is that if the circuit is in stable state a and the input changes from 01 to 00, the circuit first goes to an unstable next state c, which changes the present state value from a to c, causing a transition to the third row and first column of the flow DG 00
01
11
10
a
C,
~,o
b 
 
b
 
a, 
CiJ, 1
e, 
C
0.0
a, 
 
d,
d
C, 
, 
b 
0,0
e
f,


b 
(£)
f
0
a, 
 ,
"
1
FIGURE 9·16 Primitive flow table
1
362
Chapter 9
Asynchronous Sequential Logic
table. The unstable state values for the other squares are determined in a similar manner. All outputs associated with unstable states are marked with a dash to indicate don'tcare conditions. The assignment of actual values to the outputs is discussed further after the design example is completed. Reduction of the Primitive Flow Table
The primitive flow table has only one stable state in each row. The table can be reduced to a smaller number of rows if two or more stable states are placed in the same row of the flow table. The grouping of stable states from separate rows into one common row is called merging. Merging a number of stable states in the same row means that the binary state variable that is ultimately assigned to the merged row will not change when the input variable changes. This is because in a primitive flow table, the state variable changes every time the input changes, but in a reduced flow table, a change of input will not cause a change in the state variable if the next stable state is in the same row. A formal procedure for reducing a flow table is given in the next section. In order to complete the design example without going through the formal procedure, we will apply the merging process by using a simplified version of the merging rules. Two or more rows in the primitive flow table can be merged into one row if there are nonconflicting states and outputs in each of the columns. Whenever one state symbol and don'tcare entries are encountered in the same column, the state is listed in the merged
row. Moreover, if the state is circled in one of the rows, it is also circled in the merged row. The output value is included with each stable state in the merged row. We now apply these rules to the primitive flow table of Fig. 916. To see how this is done, the primitive flow table is separated into two parts of three rows each, as shown in Fig. 917(a). Each part shows three stable states that can be merged because there are no conflicting entries in each of the four columns. The first column shows state c in all the rows and 0 or a dash for the output. Since a dash represents a don'tcare condition, it can be associated with any state or output. The two dashes in the first column can be taken as 0 output to make all three rows identical to a stable state c with a 0 output. The second column shows that the dashes can be assigned to correspond to a stable state a with a 0 output. Note that if the state is circled in one of the rows, it is also circled in the merged row. Similarly, the third column can be merged into an unstable state b with a don'tcare output and the fourth column can be merged into stable state d and a 0 output. Thus, the three rows, a, c, and d, can be merged into one row with three stable states and one unstable state, as shown in the first row of Fig. 917(b). The second row of the reduced table results from the merging of rows b, e, and f of the primitive flow table. There are two ways that the reduced table can be drawn. The letter symbols for the states can be retained to show the relationship between the reduced and primitive flow tables. The other alternative is to define a common letter symbol for all the stable states of the merged rows. Thus, states c and dare replaced by state a, and states e and f are replaced by state b. Both alternatives are shown in Fig. 917(b).
Section 9·4 Design Procedure
DG 00
DG
01
11
10
00
01
11
10
a 
0, 1
e 
b 
0, 1
 ,
e, 
a
c 
@.O
b,
 ,
b
 
c
@,O
a 
,
d 
e
j, 
d
c, 
,
b 
0,0
j

363
0
1
a,
(a) States that are candidates for merging
DG 00
01
DG 11
10
00
01
11
10
b 
0,0
a, c, d
@, a 0,0 b, 
0. 0
a
0. 0
0,0
b, e,f
0 1
8 1
b
0,1
a,
a,
0,1
0,1 O,1
(b) Reduced table (two alternatives) FIGURE 9·17 Reduction of the primitive flow table
Transition Table and Logic Diagram
In order to obtain the circuit described by the reduced flow table, it is necessary to as
sign to each state a distinct binary value. This assignment converts the flow table into a transition table. In the general case, a binary state assignment must be made to ensure that the circuit will be free of critical races. The state· assignment problem in asynchronous sequential circuits and ways to solve it are discussed in Section 96. Fortunately, there can be no critical races in a two·row flow table, and, therefore, we can finish the design of the gated latch prior to studying Section 9·6. Assigning 0 to state a and I to state b in the reduced flow table of Fig. 9·17(b), we obtain the transition table of Fig. 9·18(a). The transition table is, in effect, a map for the excitation variable Y. The simplified Boolean function for Y is then obtained from the map. Y = DG
+ G'y
There are two don't·care outputs in the final reduced flow table. If we assign values to the output, as shown in Fig. 918(b), it is possible to make output Q equal to the exci· tation function Y. If we assign the other possible values to the don'tcare outputs, we can make output Q equal to y. In either case, the logic diagram of the gated latch is as shown in Fig. 919.
364
Chapter 9
Asynchronous Sequential Logic
DG 01
II
10
,
00
01
11
10
0
0
I
0
o
0
0
1
0
I
0
I
1
I
0
I
I
J'
o
DC
00
(a)
Y = lJG
+
G'.,",
(b)
Q
y
FIGURE 918 Transition table and output map for gated latch
Dr~ y
FIGURE 919 Gatedlatch logic diagram
DG y
o
00
01
11
10
0
0
1
0
X
0
X
X
y
01
00
o
'..""
11
10
X
I(i\1
0
X
0
llj
0
0
R "" D'G
la) S:= DG (a) Maps for Sand R
D    . .              {   \ )  _  " \ '   "_ _/
G1~
R
(b) logic diagram FIGURE 920 Circuit with SR latch
o.Q
Section 9·4 Design Procedure
365
The diagram can be implemented also by means of an SR latch. Using the procedure outlines in Section 9·3, we first obtain the Boolean functions for Sand R, as shown in Fig. 9·20(a). The logic diagram with NAND gates is shown in Fig. 9·20(b). Note that the gated latch is a level· sensitive D·type flip·flop with the clock pulses applied to input G (see Fig. 6·5). AssIgnIng Outputs to Unstable States
The stable states in a flow table have specific output values associated with them. The unstable states have unspecified output entries designated by a dash. The output values for the unstable states must be chosen so that no momentary false outputs occur when the circuit switches between stable states. This means that if an output variable is not supposed to change as the result of a transition, then an unstable state that is a transient state between two stable states must have the same output value as the stable states. Consider, for example, the flow table of Fig. 9·21(a). A transition from stable state a to stable state b goes through the unstable state b. If the output assigned to the unstable b is ai, then a momentary short pulse will appear on the output as the circuit shifts from an output of 0 in state a to an output of 1 for the unstable b and back to 0 when the circuit reaches stable state b. Thus the output corresponding to unstable state b must be specified as 0 to avoid a momentary false output. If an output variable is to change value as a result of a state change, then this vari· able is assigned a don't·care condition. For example, the transition from stable state b to stable state c in Fig. 9·21(a) changes the output from 0 to I. If a 0 is entered as the output value for unstable c, then the change in the output variable will not take place until the end of the transition. If a I is entered, the change will take place at the start of the transition. Since it makes no difference when the output change occurs, we place a don't·care entry for the output associated with unstable state c. Figure 9·21(b) shows the output assignment for the flow table. It demonstrates the four possible combinations in output change that can occur. The procedure for making the assignment to outputs associated with unstable states can be summarized as follows:
a
0, 0
b.
a
a
b
c ..
0, 0
x
a
d.
I
I
@I
X
I
c d
0 a.
1
(a) Flow table
(b) Output assignment
FIGURE 9·21 Assigning output values to unstable states
366
Chapter 9 Asynchronous Sequential Logic
1. Assign a 0 to an output variable associated with an unstable state that is a transient state between two stable states that have a 0 in the corresponding output variable. 2. Assign a I to an output variable associated with an unstable state that is a transient state between two stable states that have a I in the corresponding output variable. 3. Assign a don'tcare condition to an output variable associated with an unstable state that is a transient state between two stable states that have different values (0 and 1 or I and 0) in the corresponding output variable. Summary of Design Procedure
The design of asynchronous sequential circuits can be carried out by using the procedure illustrated in the previous example. Some of the design steps need further elaboration and are explained in the following sections. The procedural steps are as follows.
1. Obtain a primitive flow table from the given design specifications. This is the most difficult part of the design because it is necessary to use intuition and experience to arrive at the correct interpretation of the problem specifications. 2. Reduce the flow table by merging rows in the primitive flow table. A formal procedure for merging rows in the flow table is given in Section 95. 3. Assign binary state variables to each row of the reduced flow table to obtain the transition table. The procedure of state assignment that eliminates any possible critical races is given in Section 96. 4. Assign output values to the dashes associated with the unstable states to obtain the output maps. This procedure was explained previously. 5. Simplify the Boolean functions of the excitation and output variables and draw the logic diagram, as shown in Section 92. The logic diagram can be drawn using SR latches, as shown in Section 93 and also at the end of Section 97. 95
REDUCTION OF STATE AND FLOW TABLES The procedure for reducing the number of internal states in an asynchronous sequential circuit resembles the procedure that is used for synchronous circuits. An algorithm for state reduction of a completely specified state table is given in Section 65. We will review this algorithm and apply it to a statereduction method that uses an implication table. The algorithm and the implication table will then be modified to cover the state reduction of incompletely specified state tables. This modified algorithm will be used to explain the procedure for reducing the flow table of asynchronous sequential circuits.
Implication Table
The statereduction procedure for completely specified state tables is based on the algorithm that two states in a state table can be combined into one if they can be shown
Section 95
Reduction of State and Flow Tables
367
TABLE 93 State Table to Demonstrate Equivalent States
Present State
x=Q
x=!
a b c d
c d a b
b a d d
Next State
Output
x
x
0
0 0
1
1
0 0
to be equivalent. Two states are equivalent if for each possible input, they give exactly the same output and go to the same next states or to equivalent next states. Table 66 shows an example of equivalent states that have the same next states and outputs for each combination of inputs. There are occasions when a pair of states do not have the same next states, but, nonetheless, go to equivalent next states. Consider, for example, the state table shown in Table 93. The present states a and b have the same output for the same input. Their next states are c and d for x = 0 and b and a for x = I. If we can show that the pair of states (c, d) are equivalent, then the pair of states (a, b) will also be equivalent because they will have the same or equivalent next states. When this relationship exists, we say that (a, b) imply (c, ti). Similarly, from the last two rows of Table 93, we find that the pair of states (c, ti) imply the pair of states (a, b). The characteristic of equivalent states is that if (a, b) imply (c, d) and (c, d) imply (a, b), then both pairs of states are equivalent; that is, a and b are equivalent as well as c and d. As a consequence, the four rows of Table 93 can be reduced to two rows by combining a and b into one state and c and d into a second state. The checking of each pair of states for possible equivalence in a table with a large number of states can be done systematically by means of an implication table. The implication table is a chart that consists of squares, one for every possible pair of states, that provide spaces for listing any possible implied states. By judicious use of the table, it is possible to determine all pairs of equivalent states. The state table of Table 94 will TABLE 94 State Table to Be Reduced
Present State
a b c d
e
f g
Next State
Output
xo
xI
d
e
b a
g
f
a a c a
d d b
e
x
0
0 0 0
x 0 0 1
1
0
0
0 0
0
368
Chapter 9
Asynchronous Sequential Logic
be used to illustrate this procedure. The implication table is shown in Fig. 922. On thc left side along the vertical are listed all the states defined in the state table except the first, and across the bottom horizontally are listed all the states except the last. The result is a display of all possible combinations of two states with a square placed in the intersection of a row and a column where the two states can be tested for equivalence. Two states that are not equivalent are marked with a cross (X) in the corresponding square, whereas their equivalence is recorded with a check mark (I). Some of the squares have entries of implied states that must be further investigated to determine whether they are equivalent or not. The stepbystep procedure of filling in the squares is as follows. First, we place a cross in any square corresponding to a pair of states whose outputs are not equal for every input. [n this case, state c has a different output than any other state, so a cross is placed in the two squares of row c and the four squares of column c. There are nine other squares in this category in the implication table. Next, we enter in the remaining squares the pairs of states that are implied by the pair of states representing the squares. We do that starting from the top square in the left column and going down and then proceeding with the next column to the right. From the state table, we see that pair (a, b) imply (d, e), so (d, e) is recorded in the square defined by column a and row b. We proceed in this manner until the entire table is completed. Note that states (d, e) are equivalent because they go to the same next state and have the same output. Therefore, a check mark is recorded in the square defined by column d and rowe, indicating that the two states are equivalent and independent of any implied pair. The next step is to make successive passes through the table to determine whether any additional squares should be marked with a cross. A square in the table is crossed out if it contains at least one implied pair that is not equivalent. For example, the square
b
d
J g
d,
e; X
X
X
X
X
X
X
X
;
X
X
c, eX
c, dX a,b X
X
a FIGURE
Implication table
X
X d. eJ d.e; d
9~22
X
J
Section '5
Reduction of State and Flow Tables
369
TABLE 9·5 Reduced State Table Present State
Next State
Output
x=o
x=J
x=o
x=J
a
0
f
0
0 1
d
d d a
f
c
a
0
0
a
c
0
d
defined by a andfis marked with a cross next to c, d because the pair (c, d) defines a square that contains a cross. This procedure is repeated until no additional squares can be crossed out. Finally, all the squares that have no crosses are recorded with check marks. These squares define pairs of equivalent states. In this example, the equivalent states are
(a, b)
(d, e)
(d, g)
(e, g)
We now combine pairs of states into larger groups of equivalent states. The last three pairs can be combined into a set of three equivalent states (d, e, g) because each one of the states in the group is equivalent to the other two. The final partition of the states consists of the equivalent states found from the implication table together with all the remaining states in the state table that are not equivalent to any other state.
(a, b)
(c)
(d, e, g)
(J)
This means that Table 9·4 can be reduced from seven states to four states, one for each member of the above partition. The reduced table is obtained by replacing state b by a and states e and g by d. The reduced state table is shown in Table 9·5. Merging of the Flow Table
There are occasions when the state table for a sequential circuit is incompletely specified. This happens when certain combinations of inputs or input sequences may never occur because of external or internal constraints. In such a case, the next states and outputs that should have occurred if all inputs were possible are never attained and are regarded as don't·care conditions. Although synchronous sequential circuits may sometimes be represented by incompletely specified state tables, our interest here is with asynchronous sequential circuits where the primitive flow table is always incom· pletely specified. Incompletely specified states can be combined to reduce the number of states in the flow table. Such states cannot be called equivalent, because the formal definition of equivalence requires that all outputs and next states be specified for all inputs. Instead, two incompletely specified states that can be combined are said to be compatible. Two states are compatible if for each possible input they have the same output whenever specified and their next states are compatible whenever they are specified. All don't·
370
Chapter 9
Asynchronous Sequential Logic
care conditions marked with dashes have no effect when searching for compatible states as they represent unspecified conditions. The process that must be applied in order to find a suitable group of compatibles for the purpose of merging a flow table can be divided into three procedural steps. 1. Determine all compatible pairs by using the implication table. 2. Find the maximal compatibles using a merger diagram. 3. Find a minimal collection of compatibles that covers all the states and is closed.
The minimal collection of compatibles is then used to merge the rows of the flow table. We will now proceed to show and explain the three procedural steps using the primitive flow table from the design example in the previous section. Compatible Pairs The procedure for finding compatible pairs is illustrated in Fig. 923. The primitive flow table in (a) is the same as Fig. 9\6. The entries in each square represent the next state and output. The dashes represent the unspecified states or outputs. The implication table is used to find compatible states just as it is used to find equivalent states in the completely specified case. The only difference is that when comparing rows, we are at liberty to adjust the dashes to fit any desired condition. Two states are compatible if in every column of the corresponding rows in the flow table, there are identical or compatible states and if there is no conflict in the output values. For example, rows a and b in the flow table are found to be compatible, but rows a andfwill be compatible only if c andfare compatible. However, rows c andf 00
01
11
10
a
c, 
G,o
b 
 
b

a 
(£),

1
e, 
b
j
d, 
c
j
d, eX
j
d, eX
c
0,0
a, 

d
c, 
 
b 
0. 0
d
e
[,
 
b 
G, 1
e
cJ
X
j
f
CD,1
a,
 
[
c.fX
j

e, 
(a) Primitive flow table
a
b
j d, eX
c,Ix
X
X
c,fx
c
d, eX d
(b) Implication table FIGURE
9~23
Flow and Implic,ltlon tables
jl e
Section 95 Reduction of State and Flow Tables
371
are not compatible because they have different outputs in the first column. This information is recorded in the implication table. A check mark designates a square whose pair of states are compatible. Those states that are not compatible are marked with a cross. The remaining squares are recorded with the implied pairs that need further investigation. Once the initial implication table has been filled, it is scanned again to cross out the squares whose implied states are not compatible. The remaining squares that contain check marks define the compatible pairs. In the example of Fig. 923, the compatible pairs are
(a, b)
(a, c)
(a, d)
(b, e)
(b,J)
(c, d)
(e,J)
Maximal Compatibles
Having found all the compatible pairs, the next step is to find larger sets of states that are compatible. The maximal compatible is a group of compatibles that contains all the possible combinations of compatible states. The maximal compatible can be obtained from a merger diagram, as shown in Fig. 924. The merger diagram is a graph in which each state is represented by a dot placed along the circumference of a circle. Lines are drawn between any two corresponding dots that form a compatible pair. All possible compatibles can be obtained from the merger diagram by observing the geometrical patterns in which states are connected to each other. An isolated dot represents a state that is not compatible to any other state. A line represents a compatible pair. A triangle constitutes a compatible with three states. An nstate compatible is represented in the merger diagram by an nsided polygon with all its diagonals connected. The merger diagram of Fig. 924(a) is obtained from the list of compatible pairs derived from the implication table of Fig. 923. There are seven straight lines connecta
u
f+~~~b g
e
c
C
d
(a) Maximal compatible: (a. b) (a. c. d) (b. e, f)
FIGURE 924 Merger diagrams
e
(b) Maximal compatible: (a, b, e. f) (b. c, h) (c, d) (g)
372
Chapter 9 Asynchronous Sequential Logic
ing the dots, one for each compatible pair. The lines form a geometrical pattern consisting of two triangles connecting (a, c, d) and (h, e, f) and a line (a, b). The maximal compatibles are (a, h)
(a, c, d)
(h, e,f)
Figure 924(b) shows the merger diagram of an 8state flow table. The geometrical patterns are a rectangle with its two diagonals connected to form the 4state compatible (a, h, e,f), a triangle (h, c, h), a line (c, d), and a single state g that is not compatible to any other state. The maximal compatibles are (a, b, e,f)
(b, c, h)
(c, d)
(g)
The maximal compatible set can be used to merge the flow table by assigning one row in the reduced table to each member of the set. However, quite often the maximal compatibles do not necessarily constitute the set of compatibles that is minimal. In many cases, it is possible to find a smaller collection of compatibles that will satisfy the condition for row merging. Closed Covering Condition
The condition that must be satisfied for row merging is that the set of chosen compatibles must cover all the states and must be closed. The set wll cover all the states if it includes all the states of the original state table. The closure condition is satisfied if there are no implied states or if the implied states are included within the set. A closed set of compatibles that covers all the states is called a closed covering. The closedcovering condition will be explained by means of two examples. Consider the maximal compatibles from Fig. 924(a). If we remove (a, b), we are left with a set of two compatibles: (a, c, d)
(b, e,f)
All six states from the flow table in Fig. 923 arc included in this set. This satisfies the covering condition. There are no implied states for (a, c), (a, d), (c, d), (h, e), (b,f), and (e, f), as seen from the implication table of Fig. 923(b), so the closure condition is also satisfied. Therefore, the primitive flow table can be merged into two rows, one for each of the compatibles. The detailed construction of the reduced table for this particular example was done in the previous section and is shown in Fig. 917(b). The second example is from a primitive flow table (not shown) whose implication table is given in Fig. 925(a). The compatible pairs derived from the implication table are (a, b)
(a, d)
(b, c)
(c, d)
(c, e)
(d, e)
From the merger diagram of Fig. 925(b), we determine the maximal compatibles: (a, b)
(a, d)
(b, c)
(c, d, e)
Section 95
Reduction of State and Flow Tables
373
a
b
b, c.j b
c
X d,
d
b, c/
e
X a
e/ X a, d/
/
X b
b, c/
c
d
(a) Implication table
(b) Merger diagram
Compatibles
(a, b)
(a, d)
(b, c)
(c, d, e)
Implied states
(b, c)
(b, c)
(d, e)
(a, d)
(b, c)
(c) Closure ta hIe
FIGURE 925 Choosing a set of compatibles
If we choose the two compatibles
(a, b)
(c, d, e)
the set will cover all five states of the original table. The closure condition can be checked by means of a closure table, as shown in Fig, 925(c), The implied pairs listed for each compatible are taken directly from the implication table, The implied states for (a, b) are (b, c). But (b, c) is not included in the chosen set of (a, b) (c, d, e), so this set of compatibles is not closed. A set of compatibles that will satisfy the closed covering condition is (a, d)
(b, c)
(c, d, e)
The set is covered because it contains all five states. Note that the same state can be repeated more than once. The closure condition is satisfied because the implied states are (h, c) (d, e) and (a, d), which are included in the set. The original flow table (not shown here) can be reduced from five rows to three rows by merging rows a and d, b and c, and c, d, and e. Note that an alternative satisfactory choice of closedcovered compatibles would be (a, b) (b, c) (d, e). In general, there may be more than one possible way of merging rows when reducing a primitive flow table,
374
96
Chapter 9
Asynchronous Sequential Logic
RACEFREE STATE ASSIGNMENT Once a reduced flow table has been derived for an asynchronous sequential circuit, the next step in the design is to assign binary variables to each stable state. This assignment results in the transformation of the flow table into its equivalent transition table. The primary objective in choosing a proper binary state assignment is the prevention of critical races. The problem of critical races was demonstrated in Section 92 in conjunction with Fig. 97. Critical races can be avoided by making a binary state assignment in such a way that only one variable changes at any given time when a state transition occurs in the flow table. To accomplish this, it is necessary that states between which transitions occur be given adjacent assignments. Two binary values are said to be adjacent if they differ in only one variable. For example, 010 and Oil are adjacent because they only differ in the third bit. In order to ensure that a transition table has no critical races, it is necessary to test each possible transition between two stable states and verify that the binary state variables change one at a time. This is a tedious process, especially when there are many rows and columns in the table. To simplify matters, we will explain the procedure of binary state assignment by going through examples with only three and four rows in the flow table. These examples will demonstrate the general procedure that must be followed to ensure a racefree state assignment. The procedure can then be applied to flow tables with any number of rows and columns.
ThreeRow FlowTable Example
The assignment of a single binary variable to a flow table with two rows does not impose critical race problems. A flow table with three rows requires an assignment of two binary variables. The assignment of binary values to the stable states may cause critical races if not done properly. Consider, for example, the reduced flow table of Fig. 926(a). The outputs have been omitted from the table for simplicity. Inspection of row a
a
00
01
11
lea)
b
c ("\1
h
a
l')
c
a
(c)
10
a
=
00
b = 01
I(a)
~j
c
ICc) ICc) c = 11
(a) Flow table (b) Transition diagram FIGURE 926 Thref'row flnwtClble example
Section '6 RaceFree State Assignment
00
01
II
10
a
G)
b
d
G)
b
a
CD CD
c
d
Q Q Q
d
a

c
a = 00
b
d=IO
c=11
=
375
01
c

(a) Flow table
(b) Transition diagram
FIGURE 927
Flow table with an extra row
reveals that there is a transition from state a to state b in column 01 and from state a to state c in column I L This information is transferred into a transition diagram, as shown in Fig_ 926(b). The directed lines from a to b and from a to c represent the two transitions just mentioned. Similarly, the transitions from the other two rows are represented by directed lines in the transition diagram. The transition diagram is a pictorial representation of all required transitions between rows. To avoid critical races, we must find a binary state assignment such that only one binary variable changes during each state transition. An attempt to find such assignment is shown in the transition diagram. State a is assigned binary 00, and state c is assigned binary II. This assignment will cause a critical race during the transition from a to c because there are two changes in the binary state variables. Note that the transition from c to a also causes a race condition, but it is noncritical.
A racefree assignment can be obtained if we add an extra row to the flow table. The use of a fourth row does not increase the number of binary state variables, but it allows the formation of cycles between two stable states. Consider the modified flow table in Fig. 927. The first three rows represent the same conditions as the original threerow table. The fourth row, labeled d, is assigned the binary value 10, which is adjacent to both a and c. The transition from a to c must now go through d, with the result that the binary variables change from a = 00 to d = 10 to c = 11, thus avoiding a critical race. This is accomplished by changing row a, column II to d and row d, column II to c. Similarly, the transition from c to a is shown to go through unstable state d even though column 00 constitutes a noncritical race. The transition table corresponding to the flow table with the indicated binary state assignment is shown in Fig. 928. The two dashes in row d represent unspecified states that can be considered dont'tcare conditions. However, care must be taken not to assign 10 to these squares in order to avoid the possibility of an unwanted stable state being established in the fourth row. This example demonstrates the use of an extra row in the flow table for the purpose
376
Chapter 9
Asynchronous Sequential Logic
00
01
11
10
01
10
(001
"
a:;;;: 00
,00 \
I:
~
"j
.
(01
00
, )
"
/
011
11
(i}"'I
,:" It)
r


c = 1t d= ]0
10
I'll)
00

"

11

~

FIGURE 9·28 Transition tclble
of achieving a racefree assignment. The extra row is not assigned to any specific stable state, but instead is used to convert a critical race into a cycle that goes through adjacent transitions between two stable states. Sometimes, just one extra row may not be sufficient to prevent critical races, and it may be necessary to add two or more extra rows in the flow table. This is demonstrated in the next example. FourRow FlowTable Example
A flow table with four rows requires a minimum of two state variables. Although racefree assignment is sometimes possible with only two binary state variables, in many cases, the requirement of extra rows to avoid critical races will dictate the use of three binary state variables. Consider, for example, the flow table and its corresponding transition diagram, shown in Fig. 929. If there were no transitions in the diagonal direction (from b to d or from c to a), it would be possible to find an adjacent assignment for the remaining four transitions. With one or two diagonal transitions, there is no way of
"
a a
b
"
" ~a)
Flow table
FIGURE 9·29 Fourrow flow~table example
(b) Transition diagram
Section 96 RaceFree State Assignment a = 000
I
Y, 0
00
01
II
10
a
b
Ct
g
e
d
b =001
I e = 100
.J I
377
f
(a) Binary assignment
d= 101
f= III
c=Ol1
(b) Transition diagram FIGURE 930 Choosing extra rows for the flow table
assigning two binary variables that satisfy the adjacency requirement. Therefore, at least three binary state variables are needed. Figure 930 shows a state assignment map that is suitable for any fourrow flow table. States a, b, c, and d are the original states, and e,J, and g are extra states. States placed in adjacent squares in the map will have adjacent assignments. State b is assigned binary 001 and is adjacent to the other three original states. The transition from a to d must be directed through the extra state e to produce a cycle so that only one binary variable changes at a time. Similarly, the transition from c to a is directed through
000 = a
001
=
b
all = c
00
01
II
b
8
e
CD
d
CD
8
g
b
10
8 a
8
OIO=g

a


110




III =f
C


C
101 =d
f
e

100 =
0 0
f
d


FIGURE 931 State aSSignment to modified flow table
378
Chapter 9
Asynchronous Sequential Logic
g and the transition from d to c goes through f. By using the assignment given by the
map, the fourrow table can be expanded to a sevenrow table that is free of critical races, as shown in Fig, 931, Note that although the flow table has seven rows, there are only four stable states, The uncircled states in the three extra rows are there merely to provide a racefree transition between the stable states. This example demonstrates a possible way of selecting extra rows in a flow table in order to achieve a racefree assignment. A stateassignment map similar to the one used in Fig. 930(a) can be helpful in most cases. Sometimes it is possible to take advantage of unspecified entries in the flow table. Instead of adding rows to the table, it may be possible to eliminate critical races by directing some of the state transitions through the don'tcare entries. The actual assignment is done by trial and error until a satisfactory assignment is found that resolves all critical races.
MultipleRow Method
The method for making racefree state assignment by adding extra rows in the flow table, as demonstrated in the previous two examples, is sometimes referred to as the sharedrow method. There is a second method that is not as efficient, but is easier to apply, called the multiplerow method. In the multiplerow assignment, each state in the original flow table is replaced by two or more combinations of state variables. The stateassignment map of Fig. 932(a) shows a multiplerow assignment that can be used with any fourrow flow table. There are two binary state variables for each stable state, each being the logical complement of each other. For example, the original state a is replaced with two equivalent states a, = 000 and a2 = 111. The output values, not shown here, must be the same in a, and a2. Note that a, is adjacent to b" c" and d, and a, is adjacent to c" b" and d" and, similarly, each state is adjacent to three states of different letter designation. The behavior of the circuit is the same whether the internal state is at or az, and so on for the other states. Figure 932(b) shows the mUltiplerow assignment for the original flow table of Fig. 929(a). The expanded table is formed by replacing each row of the original table with two rows. For example, row b is replaced by rows b, and b2 and stable state b is entered in columns 00 and II in both rows b, and b,. After all the stable states have been entered, the unstable states are filled in by reference to the assignment specified in the map of part (a). When choosing the next state for a given present state, a state that is adjacent to the present state is selected from the map. In the original table, the next states of b are a and d for inputs 10 and 01, respectively. In the expanded table, the next states for b, are a, and d2 because these are the states adjacent to b,. Similarly, the next states for b, are a2 and d, because they are adjacent to h2. In the multiplerow assignment, the change from one stable state to another will always cause a change of only one binary state variable. Each stable state has two binary assignments with exactly the same output. At any given time, only one of the assignments is in use. For example, if we start with state a, and input 01 and then change the input to 11, 01, 00, and back to 01, the sequence of internal states will be aJ, d" Cl, and a2. Although the circuit starts in state a, and terminates in state a" as fur as the
Section 9·7
00
YzYJ 01 II
10
al
bl
ci
dl
C,
d,
",
b,
Hazards
379
YI
o
(a) Binary assignment
110 = b, 011 = Cl
00
01
II
10
bl
@
dl
@
b,
G
d,
G
@
d,
@
al
dl
®
",
",
hi
G
al
b,
8
6J G G CI
101
=
d,
C,
G @
®®
CI
c,
(b) Flow table FIGURE 9·32
Multiplerow assignment
inputoutput relationship is concerned. the two states, al and a" are equivalent to state a of the original flow table. 9·7
HAZARDS
When designing asynchronous sequential circuits, care must be taken to conform with certain restrictions and precautions to ensure proper operation. The circuit must be operated in fundamental mode with only one input changing at any time and must be free of critical races. In addition, there is one more phenomenon, called hazard, that may cause the circuit to malfunction. Hazards are unwanted switching transients that may appear at the output of a circuit because different paths exhibit different propagation de
380
Chapter 9
Asynchronous Sequential Logic
lays. Hazards occur in combinational circuits, where they may cause a temporary falseoutput value. When this condition occurs in asynchronous sequential circuits, it may result in a transition to a wrong stable state. It is therefore necessary to check for possible hazards and determine whether they cause improper operations. Steps must then be taken to eliminate their effect.
Hazards in Combinational Circuits A hazard is a condition where a single variable change produces a momentary output change when no ouput change should occur. The circuit of Fig. 933(a) demonstrates the occurrence of a hazard. Assume that all three inputs are initially equal to I. This causes the output of gate I to be I, that of gate 2 to be 0, and the output of the circuit to bc equal to I. Now consider a change of x, from I to O. The output of gate I changes to o and that of gate 2 changes to I, leaving the output at I. However, the output may momcntarily go to 0 if the propagation delay through the inverter is taken into consideration. The delay in the inverter may cause the output of gate I to change to 0 before the output of gate 2 changes to I. In that case, both inputs of gate 3 are momentarily equal to 0, causing the output to go to 0 for the short interval of time that the input signal from x, is delayed while it is propagating through the inverter circuit. The circuit of Fig. 933(b) is a NAND implementation of the same Boolean function. It has a hazard for the same reason. Because gates I and 2 are NAND gates, their outputs are the complement of the outputs of the corresponding AND gates. When x, changes from I to 0, both inputs of gate 3 may be equal to I, causing the output to produce a momentary change to 0 when it should have stayed at I. The two circuits shown in Fig. 933 implement the Boolean function in sum of products. This type of implementation may cause the output to go to 0 when it should remain a I. If the circuit is implemented in product of sums (see Section 35), Y = (Xl
+
x;)(x,
+
x,)
y
la) ANDOR circuit FIGURE 933 Circuits with hazards
(b) NAND circuit
Section 97 Hazards
(a) Static Ihazard
(b) Static Ohazard
381
(c) Dynamic hazard
FIGURE 934 Types of hazards
then the output may momentarily go to I when it should remain O. The first case is referred to as static lhazard and the second case as static Ohazard_ A third type of hazard, known as dynamic hazard, causes the output to change three or more times when it should change from I to 0 or from 0 to I. Figure 934 demonstrates the three types of hazards. When a circuit is implemented in sum of products with ANDOR gates or with NAND gates, the removal of static Ihazard guarantees that no static Ohazards or dynamic hazards will occur_ The occurrence of the hazard can be detected by inspecting the map of the particular circuit. To illustrate, consider the map in Fig. 935(a), which is a plot of the function implemented in Fig. 933_ The change in x, from I to 0 moves the circuit from minterm III to minterm 101. The hazard exists because the change of input results in a different product term covering the two minterms. Minterm III is covered by the product term implemented in gate I, and min term 101 is covered by the product term implemented in gate 2 of Fig. 933. Whenever the circuit must move from one product term to another, there is a possibility of a momentary interval when neither term is equal to I, giving rise to an undesirable 0 output. The remedy for eliminating a hazard is to enclose the two min terms in question with another product term that overlaps both groupings. This is shown in the map of Fig. 935(b), where the two minterms that cause the hazard are combined into one product term. The hazardfree circuit obtained by this configuration is shown in Fig. 936. The extra gate in the circuit generates the product term XIX,. In general, hazards in combinational circuits can be removed by covering any two min terms that may produce a hazard with a product term common to both. The removal of hazards requires the addition of redundant gates to the circuit. 00
10
'7' .... 0
'(I
(a) Y=x 1x 2 + x
I) 1x3
FIGURE 935 Maps demonstrating a hazard and its removal
382
Chapter 9
Asynchronous Sequential Logic
x, .1
x,
f~I
y XJf~~
FIGURE 936 HilZ,1rdfree circuit
Hazards in Sequential Circuits
In normal combinationalcircuit design associated with synchronous sequential circuits, hazards are not of concern, since momentary erroneous signals are not generally troublesome. However. if a momentary incorrect signal is fed back in an asynchronous se
quential circuit, it may cause the circuit to go to the wrong stable state. This is illustrated in the example of Fig. 937. If the circuit is in total stable state YX,X2 = III and input X2 changes from 1 to 0, the next total stable state should be 110. However, because of the hazard, output Y may go to 0 momentarily. If this false signal feeds back Xl
1
x, ......1 (a) Logic diagram
00
01
II
10
1
00
00
01
11
10
y
o
00 00 (I)
0
(I) (I)
(h) 'I f(Jllsitjon 1able
FIGURE 937 Hazard In
?lIl
asynchronous sequential cirCUit
o"
I
..
(I'
II ~
"~
1)
j
(c)
J\.lap for }"
Section 97
Hazards
383
into gate 2 before the output of the inverter goes to I, the output of gate 2 will remain at 0 and the circuit will switch to the incorrect total stable state 010. This malfunction can be eliminated by adding an extra gate, as done in Fig. 936. Implementation with SR Latches
Another way to avoid static hazards in asynchronous sequential circuits is to implement the circuit with SR latches. A momentary 0 signal applied to the S or R inputs of a NOR latch will have no effect on the state of the circuit. Similarly, a momentary I signal applied to the Sand R inputs of a NAND latch will have no effect on the state of the latch. In Fig. 933(b), we observed that a twolevel sum of product expression implemented with NAND gates may have a static Ihazard if both inputs of gate 3 go to I., changing the output from I to 0 momentarily. But if gate 3 is part of a latch, the momentary I signal will have no effect on the output because a third input to the gate will come from the complemented side of the latch that will be equal to 0 and thus maintain the output at I. To clarify what was just said, consider a NAND SR latch with the following Boolean functions for Sand R.
S
=
R
= A'C
AB
+ CD
Since this is a NAND latch, we must apply the complemented values to the inputs. S = (AB
+ CD)'
= (AB)'(CD)'
R=(A'C)'
This implementation is shown in Fig. 938(a). S is generated with two NAND gates and one AND gate. The Boolean function for output Q is Q = (Q'S)' = [Q'(AB)'(CD)'l'
This function is generated in Fig. 938(b) with two levels of NAND gates. If output Q is equal to I, then Q' is equal to O. If two of the three inputs go momentarily to 1, the NAND gate associated with output Q will remain at I because Q' is maintained at O. Figure 938(b) shows a typical circuit that can be used to construct asynchronous sequential circuits. The two NAND gates forming the latch normally have two inputs. However, if the S or R functions contain two or more product terms when expressed in sum of products, then the corresponding NAND gate of the SR latch will have three or more inputs. Thus, the two terms in the original sum of products expression for S are AB and CD and each is implemented with a NAND gate whose output is applied to the input of the NAND latch. In this way, each state variable requires a twolevel circuit of NAND gates. The first level consists of NAND gates that implement each product term in the original Boolean expression of Sand R. The second level forms the crosscoupled connection of the SR latch with inputs that come from the outputs of each NAND gate in the first level.
384
Chapter 9
Asynchronous Sequential Logic
Ar,
BI
Q C D
Q'
A' C (a)
A I B
c Dl
A 'I cI
IO+'Q'
( b)
FIGURE 9·38 Latcll implementation
Essential Hazards Thus far we have considered what are known as static and dynamic hazards. There is another type of hazard that may occur in asynchronous sequential circuits, called essential hazard. An essential hazard is caused by unequal delays along two or more paths that originate from the same input. An excessive delay through an inverter circuit in comparison to the delay associated with the feedback path may cause such a hazard. Essential hazards cannot be corrected by adding redundant gates as in static hazards. The problem that they impose can be corrected by adjusting the amount of delay in the affected path. To avoid essential hazards, each feedback loop must be handled with individual care to ensure that the delay in the feedback path is long enough compared to delays of other signals that originate from the input terminals. This problem tends to be specialized, as it depends on the particular circuit used and the amount of delays that are encountered in its various paths.
Section 98 Design Example
98
385
DESIGN EXAMPLE We are now in a position to examine a complete design example of an asynchronous sequential circuit. This example may serve as a reference for the design of other similar circuits. We will demonstrate the method of design by following the recommended procedural steps that were listed at the end of Section 94 and are repeated here: L 2_ 3. 4. 5. 6.
State the design specifications. Derive a primitive flow table. Reduce the flow table by merging the rows. Make a racefree binary state assignment. Obtain the transition table and output map. Obtain the logic diagram using SR latches.
Design Specifications
It is necessary to design a negativeedgetriggered T flipflop. The circuit has two inputs, T (toggle) and C (clock), and one output, Q. The output state is complemented if T = I and the clock C changes from I to 0 (negativeedge triggering). Otherwise, under any other input condition, the output Q remains unchanged. Although this circuit can be used as a flipflop in clocked sequential circuits, the internal design of the flipflop (as is the case with all other flipflops) is an asynchronous problem. Primitive Flow Table
The derivation of the primitive flow table can be facilitated if we first derive a table that lists all the possible total states in the circuit. This is shown in Table 96. We start with the input condition TC = 11 and assign to it state a. The circuit goes to state b and the output Q complements from 0 to I when C changes from I to 0 while T remains a 1. Another change in the output occurs when the circuit goes from state c to state d. In TABLE 96 Specification of Total States
Inputs State
T
a b
c d e
f g
h
0 0 0 0
Output
C
0
Comments
1 0
0 1 I
fnitial output is 0 After state a Initial output is ] After state c After state d or f After state e or a After states b or h After states gore
0 0 1
0
0 0
0
386
Chapter 9
Asynchronous Sequential Logic
TC
a


h
g, '"
II
j,
\(1) 0
h,
c, 
(h'j_ I
d
c'


Ji,
c
(',
I
,
"

(~) 0
(
I!.
(f).O
g
(g).
h
g, 
10
01
00
h,
~/;\
,
"
I: c
:,1,
a, 
I
eI, 
:I,:J';, 0 t
9~3
An asynchronous sequential circuit is described by the following excitation and output functions:
"
)'
(a) Draw the logic diagram of the circuit. (b) Derive the transition table and output map.
Chapter 9
Problems
393
(c) Obtain a 2state flow table. (d) Describe in words the behavior of the circuit. 9·4
An asynchronous sequential circuit has two internal states and one output. The excitation and output functions describing the circuit are as follows: Y1 = Y2
XIX2
=
+ XIYZ + XZYI
+ XIY'Y2 + XiYl
X2
(a) Draw the logic diagram of the circuit. (b) Derive the transition table and output map. (c) Obtain a flow table for the circuit. 9·5
Convert the flow table of Fig. P95 into a transition table by assigning the following binary values to the states: a ~ 00. b ~ II. and c ~ 01. (a) Assign values to the extra fourth state to avoid critical races. (b) Assign outputs to the don'tcare states to avoid momentary false outputs. (c) Derive the logic diagram of the circuit. 10
00 a
G). 0
b
a 
c
a, 
b,
c,
@,o @'O b 
0. 1 c 
0,1 0,0
FIGURE P95
96
Investigate the transition table of Fig. P96 and determine all race conditions and whether they are critical or noncritical. Also determine whether there are any cycles. 00
10
10
@
11
10
01
@
00
10
10
11
01
00
10
11
00
FIGURE P96
@ @ @ @
394
Chapter 9
Asynchronous Sequential Logic
97
Analyze the T flipflop shown in Fig. 67(a). Obtain the transition table and show that the circuit is unstable when both T and CP are equal to 1.
9·8
Convert the circuit of Fig. 630 into an asynchronous sequential circuit by removing the clockpulse (CP) signal and changing the flipflops into SR latches. Derive the transition table and output map of the modified circuit.
9·9
For the asynchronous sequential circuit shown in Fig. P99: (a) Derive the Boolean functions for the outputs of the two SR latches fl and f 2. Note that the S input of the second latch is x; y;. (b) Derive the transition table and output map of the circuit.
b 0.6 V. Assuming that VBE = 0.7, we calculate the base current: 5  0.7
22 k!1 The maximum collector current, assuming
Ies
.:.v,,,ec=·:,.V,,e",E
=
Re
VeE =
= 0.195
rnA
0.2 V, is
5  0.2 I kH = 4.8 rnA
We then check for saturation: 0.195 = IB
~
les 4.8  = = 0.096 rnA h,,: 50
and find that the inequality is satisfied since 0.195 > 0.096. We conclude that the transistor is saturated and output voltage V" = VeE = 0.2 V = L. Thus, the circuit behaves as an inverter.
Section 104
:~
RTL and DTL Circuits
409
IIJ (rnA)
(a) Transistor adapted for use as a diode
'___::""_::':_ Vi) 0.6
(b) Diode graphic symbol
(V)
0.7
(c) Diode charactemtlc
FIGURE 107 Silicon diode symbol and characteristic
The procedure just described will be used extensively during the analysis of the circuits in the following sections. This will be done by means of a qualitative analysis, i.e., without writing down the specific numerical equations. The quantitative analysis and specific calculations will be left as exercises in the Problems section at the end of the chapter. There are occasions where not only transistors but also diodes are used in digital circuits. An Ie diode is usually constructed from a transistor with its collector connected to the base, as shown in Fig. 1O7(a). The graphic symbol employed for a diode is shown in Fig. 1O7(b). The diode behaves essentially like the baseemitter junction of a transistor. Its graphical characteristic, shown in Fig. 1O7(c), is similar to the baseemitter characteristic of a transistor. We can then conclude that a diode is off and nonconducting when its forward voltage, VD , is less than 0.6 V. When the diode conducts, current ID flows in the direction shown in Fig. 1O7(b), and VD stays at about 0.7 V. One must always provide an external resistor to limit the current in a conducting diode, since its voltage remains fairly constant at a fraction of a volt.
104
RTL AND OTL CIRCUITS
RTL Basic Gate
The basic circuit of the RTL digital logic family is the NOR gate shown in Fig. 108. Each input is associated with one resistor and one transistor. The collectors of the transistors are tied together at the output. The voltage levels for the circuit are 0.2 V for the low level and from 1 to 3.6 V for the high level. The analysis of the RTL gate is very simple and follows the procedure outlined in the previous section. If any input of the RTL gate is high, the corresponding transistor is
410
Chapter 10
Digital Integrated Circuits Vee"" 3.6 V
64011
,+.0 Y = (A 45011
FIGURE
45011 B oYWYj
+ B + C)'
45011 C o"VWvj
10~B
RTL basIc Nor? gate
driven into saturation. This causes the output to be low, regardless of the states of the other transistors. If all inputs are low at 0.2 V, all transistors are cut off because VBF < 0.6 V. This causes the output of the circuit to be high, approaching the value of supply voltage Vee. This confirms the conditions stated in Fig. 102 for the NOR gate. Note that the noise margin for low signal input is 0.6  0.2 = 0.4 V. The fanout of the RTL gate is limited by the value of the output voltage when high. As the output is loaded with inputs of other gates, more current is consumed by the load. This current must flow through the 640fl resistor. A simple calculation (see Problem 102) will show that if hFF drops to 20, the output voltage drops to about 1 V when the fanout is 5. Any voltage below 1 V in the output may not drive the next transistor into saturation as required. The power dissipation of the RTL gate is about 12 mW and the propagation delay averages 25 ns. DTL Basic Gates
The basic circuit in the DTL digital logic family is the NAND gate shown in Fig. 109. Each input is associated with one diode. The diodes and the 5kfl resistor form an AND gate. The transistor serves as a current amplifier while inverting the digital signal. The two voltage levels are 0.2 V for the low level and between 4 and 5 V for the high level. The analysis of the DTL gate should conform to the conditions listed in Fig. 101 for the NAND gate. If any input of the gate is low at 0.2 V, the corresponding input diode conducts current through Vee and the 5kfl resistor into the input node. The voltage at point P is equal to the input voltage of 0.2 V plus a diode drop of 0.7 V, for a total of 0.9 V. In order for the transistor to start conducting, the voltage at point P must overcome a potential of one VBF drop in Q 1 plus two diode drops across D 1 and D 2, or 3 X 0.6 = 1.8 V. Since the voltage at P is maintained at 0.9 V by the input conducting diode, the transistor is cut off and the output voltage is high at 5 V. If all inputs of the gate are high, the transistor is driven into the saturation region.
Section 104
RTL and DTL Circuits
411
=5 V
Vee
2k SkU A
P DI
ro
D2
y= (ABC)'
QI B
SkU
c
.l FIGURE 109 OTL basic NAND gate
The voltage at P now is equal to VBE plus the two diode drops across D I and D 2, or 0.7 x 3 = 2.1 V. Since all inputs are high at 5 V and Vp = 2.1 V, the input diodes are reverse biased and off. The base current is equal to the difference of currents flowing in the two 5kO resistors and is sufficient to drive the transistor into saturation (see Problem 103). With the transistor saturated, the output drops to VCE of 0.2 V, which is the low level for the gate. The power dissipation of a DTL gate is about 12 mW and the propagation delay averages 30 ns. The noise margin is about I V and a fanout as high as 8 is possible. The fanout of the DTL gate is limited by the maximum current that can flow in the collector of the saturated transistor (see Problem 104). The fanout of a DTL gate may be increased by replacing one of the diodes in the base circuit with a transistor, as shown in Fig. 1010. Transistor Q I is maintained in
1.6kU
2kU 2kU A
014+1 Ql
B
c_'
FIGURE 1010 Modified DTL gate
y= (ABC),
D2
'~~~'1 Q2 SkU
412
Chapter 10
Digital Integrated Circuits
the active region when output transistor Q 2 is saturated. As a consequence, the modified circuit can supply a larger amount of base current to the output transistor. The output transistor can now draw a larger amount of collector current before it goes out of
saturation. Part of the collector current comes from the conducting diodes in the loading gates when Q 2 is saturated. Thus, an increase in allowable collector saturated current allows more loads to be connected to the output, which increases the fanout capability of the gate.
105
TRANSISTORTRANSISTOR LOGIC (TTL)
The original basic TTL gate was a slight improvement over the DTL gate. As the TTL technology progressed, additional improvements were added to the point where this logic family became the most widely used family in the design of digital systems. There are several subfamilies or series of the TTL technology. The names and characteristics of seven TTL series appear in Table 102. Commercial TTL lCs have a number designation that starts with 74 and follows with a suffix that identifies the series type. Examples are 7404, 74S86, and 74ALS161. Fanout, power dissipation and propagation delay were defined in Section 102. The speedpower product is an important parameter for comparing the various TTL series. This is the product of the propagation delay and power dissipation and is measured in picojoules (pJ). A low value for this parameter is desirable, because it indicates that a given propagation delay can be achieved without excessive power dissipation, and vice versa.
The standard TTL gate was the first version in the TTL family. This basic gate was then designed with different resistor values to produce gates with lower power dissipation or with higher speed. The propagation delay of a transistor circuit that goes into saturation depends mostly on two factors: storage time and RC time constants. Reducing the storage time decreases the propagation delay. Reducing resistor values in the circuit reduces the RC time constants and decreases the propagation delay. Of course, the tradeoff is higher power dissipation because lower resistances draw more current TABLE 102
rrL Series and Their Characteristics FanTTL Series Name
Prefix
out
Power Dissipation
(mW)
Standard Lowpower Highspeed Schottky Lowpower Schottky Advanced Schottky Advanced lowpower Schottky
74 74L 74H 74S 74LS 74AS 74ALS
10 20 10
10
20 40 20
10 I 22
19 2 10
Propagation Delay (ns) . ...
9 33 6
3 9.5 1.5 4
SpeedPower Product ~
__(pJ) .. _._
 .
90 33 132 57 19 15 4
SectIon 105 Translstor·Translstor logIc ,TTLI
413
from the power supply. The speed of the gate is inversely proportional to the propaga· tion delay . . In the lowpower TTL gate, the resistor values are higher than in the standard gate to reduce the power dissipation, but the propagation delay is increased. In the highspeed TTL gate, resistor values are lowered to reduce the propagation delay, but the power dissipation is increased. The Schottky TTL gate was the next improvement in the tech· nology {The effect of the Schottky transistor is to remove the storage time delay by preventing the transistor from going into saturation. This series increases the speed of op· eration without an excessive increase in power dissipation. The lowpower Schottky TTL sacrifices some speed for reduced power dissipation. It is equal to the standard TTL in propagation delay, but has only one·fifth the power dissipation. Recent innovations have led to the development of the advanced Schottky series. It provides an im· provement in propagation delay over the Schottky series and also lowers the power dis· sipation. The advanced lowpower Schottky has the lowest speedpower product and is the most efficient series. It is replacing all other low· power versions in new designs. All TTL series are available in SSI and in more complex forms as MSI and LSI components. The differences in the TTL series are not in the digital logic that they per· form, but rather in the internal construction of the basic NAND gate. In any case, TTL gates in all the available series come in three different types of output configuration:
I. Open collector output 2. Totempole output 3. Threestate (or tristate) output These three types of outputs will be considered in conjunction with the circuit description of the basic TTL gate. OpenCollector Output Gate
The basic TTL gate shown in Fig. \011 is a modified circuit of the DTL gate. The multiple emitters in transistor Q I are connected to the inputs. These emitters behave most of the time like the input diodes in the DTL gate since they form a pn junction with their common base. The basecol1ector junction of Q I acts as another pn junction diode corresponding to D I in the DTL gate (see Fig. \05). Transistor Q2 replaces the second diode, D 2, in the DTL gate. The output of the TTL gate is taken from the open col1ector of Q3. A resistor connected to Vee must be inserted external to the Ie package for the output to "pul1 up" to the high voltage level when Q 3 is off; otherwise, the output acts as an open circuit. The reason for not providing the resistor internally will be discussed later. The two voltage levels of the TTL gate are 0.2 V for the low level and from 2.4 to 5 V for the high level. The basic circuit is a NAND gate. If any input is low, the corresponding baseemitter junction in Q I is forward biased. The voltage at the base of Q 1 is equal to the input voltage of 0.2 V plus a VBE drop of 0.7 or 0.9 V. In order for Q 3 to start conducting, the path from Q 1 to Q 3 must overcome a potential of one diode drop
414
Chapter 10
Digital Integrated Circuits Vee = 5 V
FIGURE 1011 Opencollector ITL gate
in the basecollector pn junction of QI and two VBE drops in Q2 and Q3, or 3 X 0.6 = 1.8 V. Since the base of Q 1 is maintained at 0.9 V by the input signal, the output transistor cannot conduct and is cut off. The output level will be high if an external resistor is connected between the output and Vee (or an open circuit if a resistor is not used). If all inputs are high, both Q2 and Q3 conduct and saturate. The base voltage of Q 1 is equal to the voltage across its basecollector pn junction plus two VBE drops in Q 2 and Q3, or about 0.7 x 3 = 2.1 V. Since all inputs are high and greater than 2.4 V, the baseemitter junctions of Q 1 are all reverse biased. When output transistor Q 3 saturates (provided it has a current path), the output voltage goes low to 0.2 V. This confirms the conditions of a NAND operation. In this analysis, we said that the basecollector junction of Q I acts like a pn diode junction. This is true in the steadystate condition. However, during the turnoff transition, Q I does exhibit transistor action, resulting in a reduction in propagation delay. When all inputs are high and then one of the inputs is brought to a low level, both Q2 and Q 3 start turning off. At this time, the collector junction of Q 1 is reverse biased and the emitter is forward biased; so transistor Q 1 goes momentarily into the active region. The collector current of Q I comes from the base of Q2 and quickly removes the excess charge stored in Q2 during its previous saturation state. This causes a reduction in the storage time of the circuit as compared to the DTL type of input. The result is a reduction of the turnoff time of the gate. The opencollector TTL gate will operate without the external resistor when connected to inputs of other TTL gates, although this is not recommended because of the low noise immunity encountered. Without an external resistor, the output of the gate will be an open circuit when Q 3 is off. An open circuit to an input of a TTL gate behaves as if it has a highlevel input (but a small amount of noise can change this to a
Section 105
TransistorTransistor logic ITTL)
415
low level). When Q 3 conducts, its collector will have a current path supplied by the input of the loading gate through Vee, the 4kO resistor, and the forwardbiased baseemitter junction. Opencollector gates are used in three major applications: driving a lamp or relay, performing wired logic, and for the construction of a commonbus system. An opencollector output can drive a lamp placed in its output through a limiting resistor. When the output is low, the saturated transistor Q 3 forms a path for the current that turns the lamp on. When the output transistor is off, the lamp turns off because there is no path for the current. If the outputs of several opencollector TTL gates are tied together with asingle external resistor, a wired~AND logic is performed. Remember than positivelogic AND function gives a high level only if illl variables are high; otherwise, the function is low. With outputs of opencollector gates connected together, the common output is high only when all output transistors are off (or high). If an output transistor conducts, it forces the output to the low state. The wired logic performed with opencollector TTL gates is depicted in Fig. 1012. The physical wiring in (a) shows how the outputs must be connected to a common resistor. The graphic symbol for such a connection is demonstrated in (b). The AND function formed by connecting together the two outputs is called a wiredAND function. The AND gate is drawn with the lines going through the center of the gate to distinguish it from a conventional gate. The wiredAND gate is not a physical gate, but only a symbol to designate the function obtained from the indicated connection. The Boolean function obtained from the circuit of Fig. 1012 is the AND operation between the outputs of the two NAND gates: Y = (AB)' . (CD)' = (AB
+ CD)'
The second expression is preferred since it shows an operation commonly referred to as an ANDORINVERT function (see Section 37). Opencollector gates can be tied together to form acoOl!!lJln_hl!s. At any time, all gate outputs tied 10 thebus, except one, must be maintained in their high state. The se
A B
):>
TransistorTransistor Logic (TTL)
~
Y=AifC=high Y high impedance
A
ifC= low
C
C
(b) Threestate inverter gate
(a) Threestate buffer gate
h..
Data A input
,7Q0
Q5 h,Q4
jc Y .... Q2
Q3
Dl
Control input C
Q6
.....Q7
Q8
 '(c) Circuit diagram for the threestate inverter of (b) FIGURE 1016 Threestate TTL gate
Y=A'ifC=[ow Y high impedance if C = high
~
421
422
Chapter 10
Digital Integrated Circuits
another at the same time, the disabled gate enters the highimpedance state before the other gate is enabled. This eliminates the situation of both gates being active at the same time. There is a very small leakage current associated with the highimpedance condition in a threestate gate. Nevertheless, this current is so small that as many as 100 threestate outputs can be connected together to form a commonbus line.
106
EMITTERCOUPLED LOGIC
/Ec:Lt __
Emittercoupled logic (ECL) is a nonsaturated digital logic family. Since transistors do not saturate, it is possible to achieve propagation delays of 2 ns and even below Ins. This logic family has the lowest propagation delay of any family and is used mostly in systems requiring very highspeed operation. Its noise immunity and power dissipation, however, are the worst of all the logic families available. A typical basic circuit of the ECL family is shown in Fig. 10 I7. The outputs Internal temperature and voltagecompensated bias network
Differential input amplifier
"
VCC2 "'"
Emitterfollower outputs
,,
V CC1
GND
RC2
;:;;GND
907 U
245 U
Q8
OR output
Q6
Q5l_," V
BB
1.3
A
Rp
Rp
Rp
Rp
50kU
50kU
50kU
50kU
B
FIGURE 1017 Eel basic gate
c
D
;;=
v
VEE;:;;
5.2 V
NOR output
SectIon 10·6 EmlHer·Coupled logIc (ECLI
423
provide both the OR and NOR functions. Each input is connected to the base of a tran· sistor. The two voltage levels are about 0.8 V forthe high state and about 1.8 V for the low state. The circuit consists of a differential amplifier, a temperature· and voltage· compensated bias network, and an emitter·follower output. The emitter outputs require a pull·down resistor for current to flow. This is obtained from the input resistor, R p , of another similar gate or from an external resistor connected to a negative voltage supply. The internal temperature· and voltage.compensated bias circuit supplies a reference voltage to the differential amplifier. Bias voltage VBB is set at  1. 3 V, which is the midpoint of the signal logic swing. The diodes in the voltage divider, together with Q6, provide a circuit that maintains a constant VBB value despite changes in temperature or supply voltage. Anyone of the power supply inputs could be used as ground. However, the use of the Vcc node as ground and VEE at 5.2 V results in best noise immu· nity. If any input in the EeL gate is high, the corresponding transistor is turned on and Q 5 is turned off. An input of  0.8 V causes the transistor to conduct and places 1.6 V on the emitters of all transistors (VBE drop in EeL transistors is 0.8 V). Since VBB = 1.3 V, the base voltage of Q5 is only 0.3 V more positive than its emitter. Q 5 is cut off because its VBE voltage needs at least 0.6 V to start conducting. The current in resistor RC2 flows into the base of Q8 (provided there is a load resistor). This current is so small that only a negligible voltage drop occurs across R C2 • The OR output of the gate is one VBE drop below ground, or 0.8 V, which is the high state. The current flowing through RCI and the conducting transistor causes a drop of about 1 V below ground (see Problem 10·9). The NOR output is one VBE drop below this level, or at  I. 8 V, which is the low state. If all inputs are at the low level, all input transistors turn off and Q5 conducts. The voltage in the common·emitter node is one VBE drop below VBB , or 2.1 V. Since the base of each input is at a low level of 1.8 V, each baseemitter junction has only 0.3 V and all input transistors are cut off. RC2 draws current through Q 5 that results in a voltage drop of about 1 V, making the OR output one VBE drop below this, at 1.8 V or the low level. The current in RCI is negligible and the NOR output is one VBE drop below ground, at 0.8 V or the high level. This verifies the OR and NOR operations of the circuit. The propagation delay of the EeL gate is 2 ns, and the power dissipation is 25 mW. This gives a speedpower product of 50, which is about the same as for the Schottky TTL. The noise margin is about 0.3 V and not as good as in the TTL gate. High fun·out is possible in the EeL gate because of the high input impedance of the differential am· plifier and the low output impedance of the emitterfollower. Because of the extreme high speed of the signals, external wires act like transmission lines. Except for very short wires of a few centimeters, EeL outputs must use coaxial cables with a resistor termination to reduce line reflections. The graphic symbol for the EeL gate is shown in Fig. 1O18(a). Two outputs are available: one for the NOR function and the other for the OR function. The outputs of two or more EeL gates can be connected together to form wired logic. As shown in
424
Chapter 10
Digital Integrated Circuits
A    ' I.......Q+~~(A + B)' + (C + D)' = I(A +B)(C+D)I' • A~(A+B)'NOR B  L  /   ( A +B)
OR
BL_r,
C\.........~t1 D
y ....... ' I     (A + B)(C + D) (a) Single gate
(b) Wired combination of two gates
FIGURE 10·18
Graphic symbols of Eel gates
Fig. 1O18(b), an external wired connection of two NOR outputs produces a wiredOR function. An internal wired connection of two OR outputs is employed in some EeL Ies to produce a wiredAND (sometimes called dotAND) logic. This property may be utilized when EeL gates are used to form the ORANDINVERT and the ORAND functions. 10~!
M~"'AL·OXIDE SEMICON[)UCTOR IMOS~I_ _
The fieldeffect transistor (FET) is a unipolar transistor, since its operation depends on the flow of only one type of carrier. There are two types of fieldeffect transistors: the junction fieldeffect transistor (JFET) and the metaloxide semiconductor (MOS). The former is used in linear circuits and the latter in digital circuits. MOS transistors can be
fabricated in less area than bipolar transistors. The basic structure of the MOS transistor is shown in Fig. 1019. The pchannel MOS consists of a lightly doped substrate of ntype silicon material. Two regions are heavily doped by diffusion with ptype impurities to form the source and drain. The region between the two ptype sections serves as the channel. The gate is a metal plate separated from the channel by an insulated dielectric of silicon dioxide. A negative gate ()
(a) pcbannel
FIGURE 1019 Basic structure of MOS transistor
gate (+1
(b) nchannd
Section 107
425
MetalOxide Semiconductor (MOS)
voltage (with respect to the substrate) at the gate terminal causes an induced electric field in the channel that attracts ptype carriers from the substrate. As the magnitude of the negative voltage on the gate increases, the region below the gate accumulates more positive carriers, the conductivity increases, and current can flow from source to drain
provided a voltage difference is maintained between these two terminals. There are four basic types of MOS structures. The channel can be a p or ntype, depending on whether the majority carriers are holes or electrons. The mode of operation can be enhancement or depletion, depending on the state of the channel region at zero gate voltage. If the channel is initially doped lightly with ptype impurity (diffused channel), a conducting channel exists at zero gate voltage and the device is said to operate in the depletion mode. In this mode, current flows unless the channel is depleted by an applied gate field. If the region beneath the gate is left initially uncharged, a channel must be induced by the gate field before current can flow. Thus, the channel current is enhanced by the gate voltage and such a device is said to operate in the enhancement mode. The source is the terminal through which the majority carriers enter the bar. The drain is the terminal through which the majority carriers leave the bar. In a pchannel MOS, the source terminal is connected to the substrate and a negative voltage is applied to the drain terminal. When the gate voltage is above a threshold voltage VT (about 2 V), no current flows in the channel and the draintosource path is like an open circuit. When the gate voltage is sufficiently negative below VT , a channel is formed and ptype carriers flow from source to drain. Ptype carriers are positive and correspond to a positive current flow from source to drain. In the nchannel MOS, the source terminal is connected to the substrate and a positive voltage is applied to the drain terminal. When the gate voltage is below the threshold voltage VT (about 2 V), no current flows in the channel. When the gate voltage is sufficiently positive above VT to form the channel, ntype carriers flow from source to drain. ntype carriers are negative, which corresponds to a positive current flow from drain to source. The threshold voltage may vary from 1 to 4 V, depending on the particular process used. The graphic symbols for the MOS transistors are shown in Fig. 1020. The accepted symbol for the enhancement type is the one with the brokenline connection between source and drain. In this symbol, the substrate can be identified and is shown connected drain
gate
i oJ substrate
9
9
s
source
(a) pchannel FIGURE 10·20
Symbols for MOS transistors
D
drain
oJ substrate gate i
G1 ~
s
source
(b) nchannei
426
Chapter 10
Digital Integrated Circuits
to the source. We will use an alternative symbol that omits the substrate; in this symbol, the arrow is placed in the source terminal to show the direction of positive current flow (from source to drain in the pchannel and from drain to source in the nchannel). Because of the symmetrical construction of source and drain, the MOS transistor can be operated as a bilateral device. Although normally operated so that carriers flow from source to drain, there are circumstances when it is convenient to allow carrier flow from drain to source (see Problem 1012). One advantage of the MOS device is that it can be used not only as a transistor, but as a resistor as well. A resistor is obtained from the MOS by permanently biasing the
Y=A'
(a) Inverter
Y = (AB)'
(b) NAND gate
FIGURE 1021 nchannel MOS logic circuits
r  ......,r Y = (A + Bj'
(c) NOR gate
Section 108 Complementary MOS ,CMOS,
427
gate terminal for conduction. The ratio of the sourcedrain voltage to the channel current then determines the value of the resistance. Different resistor values may be constructed during manufacturing by fixing the channel length and width of the MOS device. Three logic circuits using MOS devices are shown in Fig. 1021. For an nchannel MOS, supply voltage VDD is positive (about 5 V) to allow positive current flow from drain to source. The two voltage levels are a function of the threshold voltage VT • The low level is anywhere from zero to VT , and the high level ranges from VT to VDD . The nchannel gates usually employ positive logic. The pchannel MOS circuits use a negative voltage for VDD to allow positive current flow from source to drain. The two voltage levels are both negative above and below the negative threshold voltage VT • Pchannel gates usually employ negative logic. The inverter circuit shown in Fig. 1021(a) uses two MOS devices. Q I acts as the load resistor and Q 2 as the active device. The load resistor MOS has its gate connected to VDD , thus maintaining it always in the conduction state. When the input voltage is low (below VT ), Q2 turns off. Since Q 1 is always on, the output voltage is at about VDD • When the input voltage is high (above VT ), Q2 turns on. Current flows from VDD through the load resistor Q I and into Q 2. The geometry of the two MOS devices must be such that the resistance of Q 2, when conducting, is much less than the resistance of Q 1 to maintain the output Y at a voltage below VT • The NAND gate shown in Fig. 1O21(b) uses transistors in series. Inputs A and B must both be high for all transistors to conduct and cause the output to go low. If either input is low, the corresponding transistor is turned off and the output is high. Again, the series resistance formed by the two active MOS devices must be much less than the resistance of the loadresistor MOS. The NOR gate shown in Fig. 1O21(c) uses transistors in parallel. If either input is high, the corresponding transistor conducts and the output is low. If all inputs are low, all active transistors are off and the output is high. 108
COMPLEMENTARY MOS (CMOS)
Complementary MOS circuits take advantage of the fact that both nchannel and pchannel devices can be fabricated on the same substrate. CMOS circuits consist of both types of MOS devices interconnected to form logic functions. The basic circuit is the inverter, which consists of one pchannel transistor and one n channel transistor, as shown in Fig. 1O22(a). The source terminal of the pchannel device is at VDD , and the source terminal of the nchannel device is at ground. The value of VDD may be anywhere from + 3 to + 18 V. The two voltage levels are 0 V for the low level and VDD for the high level. To understand the operation of the inverter, we must review the behavior of the MOS transistor from the previous section:
1. The nchannel MOS conducts when its gatetosource voltage is positive.
428
Chapter 10
Digital Integrated Circuits
Y=A'
(a) Inverter
A
A
o++.j
o..i
.+4.,.0 Y: (A
+ B)'
Bo+l
(b) NAND gate
(c) NOR gate
FIGURE 1022 CMOS logic circuits
2_ The pchannel MOS conducts when its gatetosource voltage is negative. 3_ Either type of device is turned off if its gatetosource voltage is zero. Now consider the operation of the inverter. When the input is low, both gates arc at zero potential. The input is at _. V"" relative to the source of the pchanncl device and at 0 V relative to the source of the nchannel device. The result is that the pchannel device is turned on and the nchannel device is turned off. Under these conditions, there is a lowimpedance path from Vno to the output and a very highimpedance path from output to ground. Therefore, the output voltage approaches the high level V"l' under normal loading conditions. When the input is high, both gates are at VOD and the situation is reversed: The pchannel device is off and the nchannel device is on. The result is that the output approaches the low level of 0 V. Two other CMOS basic gates are shown in Fig. 1022. A twoinput NAND gate consists of two ptype units in parallel and two ntype units in series, as shown in Fig. IO22(b). If all inputs arc high, both pchannel transistors turn off and both nchannel
Section 108
Complementary MOS (CMOSI
429
transistors turn on. The output has a low impedance to ground and produces a low state. If any input is low, the associated nchannel transistor is turned off and the associated pchannel transistor is turned on. The output is coupled to VDD and goes to the high state. Multipleinput NAND gates may be formed by placing equal numbers of ptype and ntype transistors in parallel and series, respectively, in an arrangement similar to that shown in Fig. 1O22(b). A twoinput NOR gate consists of two ntype units in parallel and two ptype units in series, as shown in Fig. 1O22(c). When all inputs are low, both pchannel units are on and both nchannel units are off. The output is coupled to VDD and goes to the high state. If any input is high, the associated pchannel transistor is turned off and the associated nchannel transistor turns on. This connects the output to ground, causing a lowlevel output. CMOS Characteristics
When a CMOS logic circuit is in a static state, its power dissipation is very low. This is because there is always an off transistor in the current path when the state of the circuit is not changing. As a result, a typical CMOS gate has a static power dissipation on the order of 0.01 mW. However, when the circuit is changing state at a rate of I MHz, the power dissipation increases to about 1 mW. CMOS logic is usually specified for a single powersupply operation over the voltage range between 3 and 18 V with a typical VDD value of 5 V. Operating CMOS at a larger value of supply voltage reduces the propagation delay time and improves the noise margin, but the power dissipation is increased. The propagation delay time with VDD = 5 V ranges from 8 to 50 ns, depending on the type of CMOS used. The noise margin is usually about 40 percent of the VDD supply voltage. The fanout of CMOS gates is 50 when operated at a frequency of less than I MHz. The fanout decreases with increase in frequency of operation. There are several series of the CMOS digital logic family (see Table 210). The original design of CMOS ICs is recognized from the 4000 number designation. The 74C series are pin and functioncompatible with TTL devices having the same number. For example, CMOS IC type 74C04 has six inverters with the same pin configuration as TTL type 7404. The performance characteristics of the 74C series are about the same as the 4000 series. The highspeed CMOS 74HC series is an improvement of the 74C series with a tenfold increase in switching speed. The 74HCT series is electrically compatible with TTL ICs., This means that the circuits in this series can be connected to inputs and outputs of TTL ICs without the need of additional interfacing circuits.
The CMOS fabrication process is simpler than TTL and provides a greater packing density. This means that more circuits can be placed on a given area of silicon at a reduced cost per function. This property of CMOS, together with its low power dissipation, excellent noise immunity, and reasonable propagation delay, makes it a strong contender for a popular standard as a digital logic fumily.
430
10·9
Chapter 10 Dlglta"ntegrated Circuits
CMOS TRANSMISSION GATE CIRCUITS A special CMOS circuit that is not available in the other digi tal logic families is the transmission gate. The transmission gate is essentially an electronic switch that is controlled by an input logic level. It is used for simplifying the construction of various digital components when fabricated with CMOS technology. Figure 1O23(a) shows the basic circuit of the transmission gate. It consists of one nchannel and one pchannel MOS transistor connected in parallel. The graphic symbol used here is the conventional symbol that shows the substrate, as indicated in Fig. 1020. The nchannel substrate is connected to ground and the pchannel substrate is connected to VDD . When the N gate is at V"" and the P gate is at ground, both transistors conduct and there is a closed path between input X and output Y. When the N gate is at ground and the P gate at VDD , both transistors are off and there is an open circuit between X and Y. Figure 1O23(b) shows the block diagram of the transmission gate. Note that the terminal of the pchannel gate is marked with the negation smallcircle symbol. Figure 1O23(c) demonstrates the behavior of the switch in terms of positivelogic assignment with VDD equivalent to logicl and ground equivalent to logicO. The transmission gate is usually connected to an inverter, as shown in Fig. 1024. N
I
N
I 7
X
TG
X
Y
VDD
1 P P (a)
(b)
Close switch
Open switch
X~"'Y N=Q
P= 1 (c)
FIGURE 1023 TransmisSion gate (TG)
Y
431
Section 109 CMOS Transmission Gate Circuits
crl
x
y
TG
FIGURE 1024 Bilateral switch
This type of arrangement is referred to as a bilateral switch. The control input C is connected directly to the nchannel gate and its inverse to the pchannel gate. When C = I, the switch is closed, producing a path between X and Y. When C = 0, the switch is open, disconnecting the path between X and Y. Various circuits can be constructed using the transmission gate. In order to demonstrate its usefulness as a component in the CMOS family, we will show three circuit examples. The exclusiveOR gate can be constructed with two transmission gates and two inverters, as shown in Fig. 1025. Input A controls the paths in the transmission gates and input B is connected to output Y through the gates. When input A is equal to 0, transmission gate TG I is closed and output Y is equal to input B. When input A is equal to I, TG 2 is closed and output Y is equal to the complement of input B. This results in the exclusiveOR truth table, as indicated in the table of Fig. 1025. A
TGI
B
()
r y TG2
FIGURE 1025 ExclusiveOR constructed with transmission gates
A
B
TGI
TG2
Y
0 0
0 0
open open close close
0
1
close close open open
1
1 0
432
Digital Integrated Circuits
Chapter 10
Another circuit that can be constructed with transmission gates is the multiplexer. A 4tolIine multiplexer implemented with transmission gates is shown in Fig. 1026. The TG circuit provides a transmission path between its horizontal input and output lines when the two vertical control inputs have the value of 1 in the uncircled terminal and 0 in the circled terminal. With an opposite polarity in the control inputs, the path disconnects and the circuit behaves like an open switch. The two selection inputs, S] and So, control the transmission path in the TG circuits. Inside each box is marked the
So
TG (So" 0)
TG (s] "0)
TG (So
~
I)
~
TG (So" 0)
TG (s] ~ I)
[
I
TG 3
(So
~
I)
FIGURE 1026 Multiplexer with transmission gates
y
Chapter 10 References
433
C~~,
D+1
TG
~~Q'
TG
~+Q
FIGURE 1027 Gated D latch with transmission gates
condition for the transmission gate switch to be closed. Thus, if So = 0 and SI = 0, there is a closed path from input 10 to output Y through the two TGs marked with So = 0 and SI = O. The other three inputs are disconnected from the output by one of the other TG circuits. The levelsensitive D flipflop commonly referred to as gated D latch can be constructed with transmission gates, as shown in Fig. 1027. The C input controls two transmission gates TG. When C = I, the TG connected to input D has a closed path and the one connected to output Q has an open path. This produces an equivalent circuit from input D through two inverters to output Q. Thus, the output follows the data input as long as C remains active. When C switches to 0, the first TG disconnects input D from the circuit and the second TG produces a closed path between the two inverters at the output. Thus, the value that was present at input D at the time that C went from 1 to 0 is retained at the Q output. A masterslave D flipflop can be constructed with two circuits of the type shown in Fig. 1027. The first circuit is the master and the second is the slave. Thus, a masterslave D flipflop can be constructed with four transmission gates and six inverters.
REFERENCES 1_ 2. 3.
4_ 5. 6_
HoDGES, D. A., and H. G. JACKSON, Analysis and Design of DigitalIntegrated Circuits, 2nd Ed. New York: McGrawHill, 1988. TAUB, H., and D. SCHILLING, DigitalIntegrated Electronics. New York: McGrawHill, 1977. GRINICH, V. H., and H. G. JACKSON, Introduction to Integrated Circuits. New York: McGrawHill, 1975. TOCCI, R. J., Digital Systems Principles and Applications, 4th Ed., Englewood Cliffs, NJ: PrenticeHall, 1988. The TTL Data Book. Dallas: Texas Instruments, 1988. CMOS Logic Data Book. Dallas: Texas Intruments, 1984.
434
Chapter 10
7.
S. 9.
Digital Integrated Circuits
MORRIS, R. L., and 1. R. MILLER, Designing with TTL Integrated Circuits. New York: McGrawHili, 1971. GLASER, A. B., and G. E. SUBAKSHARPE, Integrated Circuit Engineering. Reading, MA: AddisonWesley, 1977, HAMILTON, D. 1., and W. G. HOWARD, Basic Integrated Circuit Engineering. New York: McGrawHili, 1975.
PROBLEMS 101 The following are the specifications for the Schottky TTL 74S00 quadruple 2input NAND gates. Calculate the fanout, power dissipation, propagation delay, and noise margin of the Schottky NAND gate. _._
Parameter
Name
Value
Vee
Supply voltage Highlevel supply current (four gates) Lowlevel supply current (four gates) Highlevel output voltage (min) Lowlevel output voltage (max) Highlevel input voltage (min) Lowlevel input voltage (max) Highlevel output current (max) Lowlevel output current (max) Highlevel input current (max) Lowlevel input current (max) Lowtohigh delay Hightolow delay
SV lOrnA 20 rnA 2.7 V O.S V 2V 0.8 V I rnA 20 rnA O.OS rnA 2 rnA 3 ns 3 ns
heH feCI,
VOH VOL Vm
V" IOH /01 1m !,L tPLH tpHI_
. ._
    _...
1 0~2 (a) Determine the highlevel output voltage of the RTL gate for a fanout of 5. (b) Determine the minimum input voltage required to drive an RTL transistor to saturation when hFE = 20. (e) From the results in (a) and (b), determine the noise margin of the RrL gate when the input is high and the fanout is 5. 1 0~3 Show that the output transistor of the DTL gate of Fig. 109 goes into saturation when all inputs are high. Assume that hn = 20. 104 Connect the output Y of the DTL gate shown in Fig. 109 to N inputs of other similar gates. Assume that the output transistor is saturated and its base current is 0.44 rnA. Let hFF ~ 20. (a) (b) (c) (d) (e)
Calculate the current in the 2 kfl resistor. Calculate the current coming from each input connected to the gate. Calculate the total collector current in the output transistor as a function of N. Find the value of N that will keep the transistor in saturation. What is the fanout of the gate"
Chapter 10 Problems
435
105 Let all inputs in the opencollector TTL gate of Fig. 1011 be in the high state of 3 V.
(a) Determine the voltages in the base, collector, and emitter of all transistors.
(b) Determine the minimum hFE of Q2 that ensures that this transistor saturates. (c) Calculate the base current of Q3. (d) Assume that the minimum hn : of Q3 is 6.18. What is the maximum current that can be tolerated in the collector to ensure saturation of Q 3? (e) What is the minimum value of RL that can be tolerated to ensure saturation of Q 3? 106 (a) Using the actual output transistors of two opencollector TTL gates, show (by means
of a truth table) that when connected together to an external resistor and Vee. the wired connection produces an AND function. (b) Prove that two opencollector TTL inverters when connected together produce the
NOR function. 107 It was stated in Section 105 that totempole outputs should not be tied together to form
wired logic. To see why this is prohibitive, connect two such circuits together and let the output of one gate be in the high state and the output of the other gate be in the low state. Show that the load current (which is the sum of the base and collector currents of the sat
urated transistor Q4 in Fig. 1014) is about 32 rnA. Compare this value with the recommended load current in the high state of 0.4 rnA. 108 For the following conditions, list the transistors that are off and those that are conducting
in the threestate TTL gate of Fig. 1O16(c). (For Q I and Q6, it would be necessary to list the states in the baseemitter and basecollector junctions separately.)
(a) When C is low and A is low. (b) When C is low and A is high. (c) When C is high. What is the state of the output in each case?
h across RE in the ECL gate of Fig. 1OJ7 when: (a) At least one input is high at 0.8 V. (b) All inputs are low at 1.8 V. Now assume that Ie = h. Calculate the VOltage drop across the collector resistor in each
109 Calculate the emitter current
case and show that it is about 1 V as required. 1010 Calculate the noise margin of the ECL gate. 1011 Using the NOR outputs of two ECL gates, show that when connected together to an external resistor and negative supply voltage, the wired connection produces an OR function.
1012 The MOS transistor is bilateral, i.e., current may flow from source to drain or from drain to source. Using this property, derive a circuit that implements the Boolean function Y = (AB
+ CD +
AED
+ CEB) ,
using six MOS transistors. 1013 (a) Show the circuit of a fourinput NAND gate using CMOS transistors. (b) Repeat for a
fourinput NOR gate. 1014 Construct an exclusiveNOR circuit with two inverters and two transmission gates. 1015 Construct an 8tolline multiplexer using transmission gates and inverters. 1016 Draw the logic diagram of a masterslave D flipflop using transmission gates and inverters.
Laboratory Experiments ~~~~~
110
INTRODUCTION TO EXPERIMENTS
This chapter presents 18 laboratory experiments in digital circuits and logic design. They provide handson experience for the student using this book. The digital circuits can be constructed by using standard integrated circuits (Ies) mounted on breadboards that are easily assembled in the laboratory. The experiments are ordered according to the material presented in the book. A logic breadboard suitable for performing the experiments must have the following equipment: 1. 2. 3. 4.
LED (lightemitting diode) indicator lamps. Toggle switches to provide logicI and 0 signals. Pulsers with pushbuttons and debounce circuits to generate single pulses. A clockpulse generator with at least two frequencies, a low frequency of about one pulse per second to observe slow changes in digital signals and a higher frequency of about 10 kHz or higher for observing waveforms in an oscilloscope. S. A power supply of 5 V for TTL Ies. 6. Socket strips for mounting the Ies. 7. Solid hookup wire and a pair of wire strippers for cutting the wires. Digital logic trainers that include the required equipment are available from several manufacturers. A digital logic trainer contains LED lamps, toggle switches, pulsers, a variable clock, power supply. and Ie socket strips. Some experiments may require ad436
Section 110 Introduction to Experiments
437
ditional switches, lamps, or IC socket strips. Extended breadboards with more solderless sockets and plugin swLtches and lamps may be needed. Additional equipment required are a dualtrace oscilloscope (for Experiments I, 2, 8, and 15), a logic probe to be used for debugging, and a number of ICs. The ICs required for the experiments are of the transistortransistor logic (TTL) type, series 7400. The integrated circuits to be used in the experiments can be classified as smallscale integration (SSI) or mediumscale integration (MSI) circuits. SSI circuits contain individual gates or flipflops, and MSI circuits perform specific digital functions. The eight SSI gate ICs needed for the experiments are shown in Fig. III. They include 2input NAND, NOR, AND, OR, and XOR gates, inverters, and 3input and 4input NAND gates. The pin assignment for the gates is indicated in the diagram. The pins are numbered from I to 14. Pin number 14 is marked Vee, and pin number 7 is marked GND (ground). These are the supply terminals, which must be connected to a power supply of 5 V for proper operation. Each IC is recognized by its identification number; for example, the 2input NAND gates are found inside the IC whose number is 7400. Detailed descriptions of the MSI circuits can be found in data books published by the manufucturers. The best way to acquire experience with commercial MSI circuits is to study their description in a data book that provides complete information on the internal, external, and electrical characteristics of the integrated circuits. Various semiconductor companies publish data books for the TTL 7400 series. Examples are The TTL Data Book, published by Texas Instruments, and the Logic Databook, published by National Semiconductor Corp. The MSI circuits that are needed for the experiments are introduced and explained when they are used for the first time. The operation of the circuit is explained by referring to similar circuits in previous chapters. The information given in this chapter about the MSI circuits should be sufficient for performing the experiments adequately. Nevertheless, a reference to a data book will always be preferable, as it gives more detailed description of the circuits. We will now demonstrate the method of presentation of MSI circuits adopted here. This will be done by means of a specific example that introduces the ripple counter IC, type 7493. This IC is used in Experiment I and in subsequent experiments to generate a sequence of binary numbers for verifying the operation of combinational circuits. The information about the 7493 IC that is found in a data book is shown in Figs. 112(a) and (b). Part (a) shows a diagram of the internal logic circuit and its connection to external pins. All inputs and outputs are given symbolic letters and assigned to pin numbers. Part (b) shows the physical layout of the IC with its 14pin assignment to signal names. Some of the pins are not used by the. circuit and are marked as NC (no connection). The IC is inserted into a socket, and wires are connected to the various pins through the socket terminals. When drawing schematic diagrams in this chapter, we will show the IC in a block diagram form as in Fig. 112(c). The IC number 7493 is written inside the block. All input terminals are placed on the left of the block and all output terminals on the right. The letter symbols of the signals, such as A, RI, and QA, are written inside the block, and the corresponding pin numbers, such as 14, 2, and 12, are written along the external lines. Vee and GND are the power terminals connected to
438
Chapter 11
Laboratory Experiments
"
a
2Input NAl\O
(;M)
7400
Inverl~"
;'lJlpul NOR
r;vt;
7402
GND
2lnpul AND
7404
7408
3input NAND
4mplLt NAND
7410
7420
.~ cc
2lnpu! OR
7432
(,',\D
linpill XOR
7486
FIGURE 111 Digital gates in
Ie packages with
identification numbers and pin assignments
(,,\j)
439
Section 110 Introduction to Experiments
Inpu tA
A
12
J
Q
NC
QA
K CLR
7493
Y Inpu tB
QC
QA
14
J
QD GND QB
Q
9 QB
I
B
RI
R2
NC
Vee
NC
NC
(b) Physical layout (NC: no connection) K CLR
r
5
8
J
Q
QC
14
c I> K CLR
2
Y
3 J
I....c
Q
RI R2

_3]
}
QA
B
QB
9
7493 8
RI
QC
R2
QD
II GND
II
12
QD
10
> K CLR
2
Vee
A
(c) Schematic diagram
Y
(a) Internal circuit diagram FIGURE "·2 Ie type 7493 ripple counter
pins 5 and 10. The size of the block may vary to accommodate all input and output ter· minals. Inputs or outputs may sometimes be placed on the top or the bottom of the block for convenience. The operation of the circuit is similar to the ripple counter shown in Fig. 7·12 with an asynchronous clear to each flip·flop, as shown in Fig. 6·15. When inputs RI or R2
440
Chapter 11
Laboratory Experiments
or both are equal to logic 0 (ground for TTL circuits), all asynchronous clears are equal to 1 and are disabled. To clear all four flipflops to 0, the output of the NAND gate must be equal to O. This is accomplished by having both inputs Rl and R2 at logicl (about 3 to 5 V in TTL circuits). Note that the J and K inputs show no connections. It is characteristic of TTL circuits that an input terminal with no external connections has the effect of producing a signal equivalent to logic!. Also note that output QA is not connected to input B internally. The 7493 IC can operate as a 3bit counter using input B and flipflops QB, QC, and QD. It can operate as a 4bit counter using input A if output QA is connected to input B. Therefore, to operate the circuit as a 4bit counter, it is necessary to have .an external connection between pin 12 and pin!. The reset inputs, Rl and R2, at pins 2 and 3, respectively, must be grounded. Pins 5 and 10 must be connected to a 5V power supply. The input pulses must be applied to input A at pin 14, and the four flipflop outputs of the counter are taken from QA, QB, QC, and QD, at pins 12, 9, 8, and II, respectively, with QA being the least significant bit. Figure 112(c) demonstrates the way that all MSI circuits will be symbolized graphically in this chapter. Only a block diagram similar to the one shown in this figure will be shown for each IC. The letter symbols for the inputs and outputs in the IC block diagram will be according to the symbols used in the data book. The operation of the circuit will be explained with reference to logic diagrams from previous chapters. The operation of the circuit will be specified by means of a truth table or a function table. Other possible graphic symbols for the ICs are presented in Chapter 12. These are TABLE 11·1 Integrated Circuits Required for the Experiments Graphic Symbol 
Ie Number
7447 7474 7476 7483 7489 7493 74151 74155 74157 74161 74194 74195 7730 72555
Description
In Chap. "
In Chap. '2
Various gates BCDtosevensegment decoder Dual D type flipflops Dual JKtype flipflops
Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig.
Fig. 121
4bit binary adder 16 x 4 randomaccess memory 4bit ripple counter 8 x 1 multiplexer
3 x 8 decoder Quadruple 2 x I multiplexers 4bit synchronous counter Bidirectional shift register 4bit shift register
Sevensegment LED display Timer (same as 555)
11 118 1113 1112 1110 1118 112 119 117 1117 1115 1119 1116 118 1121
Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig.
129(b) 129(a) 122 1215 1213 127(a) 126 127(b) 1214 1212 1211
 _.. _    
section 11·1
Binary and Decimal Numbers
441
standard graphic symbols approved by the Institute of Electrical and Electronics Engineers and are given in IEEE standard 911984. The standard graphic symbols for SSI gates have rectangular shapes, as shown in Fig. 12\' The standard graphic symbol for the 7493 IC is shown in Fig. 1213. This symbol can be substituted in place of the one shown in Fig. 112(c). The standard graphic symbols of the other ICs that are needed to run the experiments are presented in Chapter 12. They can be used for drawing schematic diagrams of the logic circuits if the standard symbols are preferred. Table 111 lists the ICs that are needed for the experiments together with the figure numbers where they are presented in this chapter. In addition, the table lists the figure numbers in Chapter 12 where the equivalent standard graphic symbols are drawn. The rest of this chapter is divided into 18 sections, with each section covering one experiment. The section number designates the experiment number. Each experiment should take about two to three hours of laboratory time, except for Experiments 14, 16, and 17, which may take longer.
111
BINARY AND DECIMAL NUMBERS
This experiment demonstrates the count sequence of binary numbers and the binarycoded decimal (BCD) representation. It serves as an introduction to the breadboard used in the laboratory and acquaints the student with the cathoderay oscilloscope. Reference material from the text that may be useful to know while performing the experiment can be found in Section 12, on binary numbers, and Section 17, on BCD numbers. Binary Count. IC type 7493 consists of four cells called flipflops, as shown in Fig. 112. The cells can be connected to count in binary or in BCD. Connect the IC to operate as a 4bit binary counter by wiring the external terminals, as shown in Fig. 113. This is done by connecting a wire from pin 12 (output QA) to pin 1 (input B). Input A at pin 14 is connected to a pulser that provides single pulses. The two reset inputs, R I and R 2, are connected to ground. The four outputs go to four indicator lamps with the loworder bit of the counter from QA connected to the rightmost indicator lamp. Do not forget to supply 5 V and ground to the IC. All connections should be made with the power supply in the off position. Turn the power on and observe the four indicator lamps. The 4bit number in the output is incremented by one for every pulse generated in the pushbutton pulser. The count goes to binary 15 and then back to O. Disconnect the input of the counter at pin 14 from the pulser and connect it to a clock generator that produces a train of pulses at a low frequency of about one pulse per second. This will provide an automatic binary count. Note that the binary counter will be used in subsequent experiments to provide the input binary signals for testing combinational circuits. Oscilloscope Display. Increase the frequency of the clock to \0 kHz or higher and connect its output to an oscilloscope. Observe the clock output on the oscilloscope and
442
Chapter 11
Laboratory Experiments
15 14 Pushbutton pulser or clock

I
A
Vee
QB
B 7493
2
r

3
QA
QC
RI
QD R2
GND
12
JO. '.
~
':on from one binary code to another is common in digital systems. In this experiment, you will design and construct three combinationalcircuit converters. Code conversion is discussea in Section 45.
450
Chapter 11
Laboratory Experiments
Gray Code to Binary. Design a combinational circuit with four inputs and four outputs that converts a fourbit Gray code number (Table 14) into the equivalent fourbit binary number. Implement the circuit with exclusiveOR gates. (This can be done with one 7486 IC.) Connect the circuit to four switches and four indicator lamps and check for proper operation. 9's Complementer. Design a combinational circuit with four input lines that represent a decimal digit in BCD and four output lines that generate the 9's complement of the input digit. Provide a fifth output that detects an error in the input BCD number. This output should be equal to logicI when the four inputs have one of the unused combinations of the BCD code, Use any of the gates listed in Fig, llI, but minimize the total number of ICs used, SevenSegment Display A sevensegment indicator is used for displaying anyone of the decimal digits 0 through 9, Usually, the decimal digit is available in BCD, A BCDtosevensegment decoder accepts a decimal digit in BCD and generates the corresponding sevensegment code, This is shown pictorially in Problem 416, Figure 118 shows the connections necessary between the decoder and the display, The 7447 IC is a BCDtosevensegment decoder/driver. It has four inputs for the BCD digit. Input D is the most significant and input A the least significant. The 4bit BCD digit is converted to a sevensegment code with outputs a through g, The outputs of the 7447 are applied to the inputs of the 7730 (or equivalent) sevensegment display, This
16
Vee 7 I
2 6
a b
c
A B
47 n
7447
C
d e
D
r g
13
1
12
13
11
10
10
8
9
7
15
2
14
11
a b
c
a
{~Ib
d
e[Jc
e
d
f
CA
7730
g
GND 8
1 FIGURE 11,8 BCDtosevensegment decoder (7447) and sevensegment display (7730)
14
Section 116 Design with Multiplexers
451
IC contains the seven LED (lightemitting diode) segments on top of the package. The input at pin 14 is the common anode (CA) for all the LEOs. A 47 0 resistor to Vee is needed in order to supply the proper current to the selected LED segments. Other equivalent sevensegment display ICs may have additional anode terminals and may require different resistor values. Construct the circuit shown in Fig. 118. Apply the 4bit BCD digits through four switches and observe the decimal display from 0 to 9. Inputs 10 10 through 1111 have no meaning in BCD. Depending on the decoder, these values may cause either a blank or a meaningless pattern to be displayed. Observe and record the output displayed patterns of the six unused input combinations.
116
DESIGN WITH MULTIPLEXERS In this experiment, you will design a combinational circuit and implement it with multiplexers, as explained in Section 56. The multiplexer to be used is IC type 74151, shown in Fig. 119. The internal construction of the 74151 is similar to the diagram shown in Fig. 516 except that there are eight inputs instead of four. The eight inputs are designated DO through D7. The three selection lines, C, B, and A, select the particular input to be multiplexed and applied to the output. A strobe control, S, acts as an enable signal. The function table specifies the value of output Y as a function of the selection lines. Output W is the complement of Y. For proper operation, the strobe input S must be connected to ground. Design Specifications. A small corporation has 10 shares of stock, and each share entitles its owner to one vote at a stockholder's meeting. The 10 shares of stock are owned by four people as follows: Mr. W: Mr. X: Mr. Y: Mrs. Z:
I 2 3 4
share shares shares shares
Each of these persons has a switch to close when voting yes and to open when voting no for his or her shares. It is necessary to design a circuit that displays the total number of shares that vote yes for each measure. Use a sevensegment display and a decoder, as shown in Fig. 118, to display the required number. If all shares vote no for a measure, the display should be blank. (Note that binary input 15 into the 7447 blanks all seven segments.) If 10 shares vote yes for a measure, the display should show O. Otherwise, the display shows a decimal number equal to the number of shares that vote yes. Use four 74151 multiplexers to design the combinational circuit that converts the inputs from the stock owners' switches into the BCD digit for the 7447. Do not use 5 V for logicI. Use the output of an inverter whose input is grounded.
452
Chapter 11
Laboratory Experiments
I
16
g
1
4 3
, 1
Data iJlPlib
G:;\D
Vee
7
Strobe
S
DO /J1 1n
Y
])3
74151
15
1.3
12
Output
r
(,
h'
~1/
IJ4
14
5
=
y'
DS 1J(1 ])7
11
,1
IOj
111
('
"I
Seled
jnput~
hlJl(tion tOlbk Strobl'
Sl'iL'L'l
S
I!
.1
()
Output )
X
X
X
()
0
0
0
])0
0 0
J)~
0
0
0
(J
U
(J
fJ1
/)3
0
U
0
()
0 0
U
04 f)S
II
j)(l
1!7
FIGURE 119 Ie rype 741518/ 1 multiplexer
117
ADDERS AND SUBTRACTORS In this experiment, you will construct and test various adder and subtractor circuits. The subtractor circuit is then used for comparing the relative magnitude of two numbers. Adders are discussed in Section 43. Subtraction with 2's complement is ex
Section 11·7 Adden and Subtracton
453
plained in Section 15. A 4bit parallel adder is introduced in Section 52, and the comparison of two numbers is explained in Section 54. Design, construct, and test a halfadder circuit using one XOR gate and two NAND gates.
HalfAdder.
FullAdder.
Design, construct, and test a fulladder circuit using two ICs, 7486 and
7400. IC type 7483 is a 4bit binary parallel adder. Its internal construction is similar to Fig. 55. The pin assignment is shown in Fig. llIO. The two 4bit input binary numbers are Al through A4 and BI through B 4. The 4bit sum is obtained from Sl through S4. CO is the input carry and C4 the output carry. Test the 4bit binary adder 7483 by connecting the power supply and ground terminals. Then connect the four A inputs to a fixed binary number such as 100 I and the B inputs and the input carry to five toggle switches. The five outputs are applied to indicator lamps. Perform the addition of a few binary numbers and check that the output sum and output carry give the proper values. Show that when the input carry is equal to I, it adds 1 to the output sum.
Parallel Adder.
The subtraction of two binary numbers can be done by taking the 2's complement of the subtrahend and adding it to the minuend. The 2's complement can be obtained by taking the l' s complement and adding 1. To perform A  B,
AdderSUbtractor.
5 16 I 4 3 7 8 II
10 13
B4
Vee
C4
14
A4 B3
S4
A3 B2
S3 7483
A2
S2
BI
SI
Al CO
GND 112
FIGURE 1110 Ie type 7483 4bit binary adder
15 2 6 9
454
Chapter 11
Laboratory Experiments
15 1 3 Data input A
8
10
Data input
B
'~ II
B3
II
)21
14
Output carry
.12 Al
B4
II 'J2
C4
.13
'.r,II
Vee
.14
S4 S3
15 2
7483
S2 SI
6
Data output S
9
B2
B1 CO
GND
113 112
Mode select M
M = a for add M = I for subtract FIGURE "." 4brt adder subtractor
we complement the four bits of B, add them to the four bits of A, and add 1 through the input carry. This is done as shown in Fig. IIII. The four XOR gates complement the bits of B when the mode select M = I (because x EEl I = x ') and leave the bits of B unchanged when M = 0 (because x EEl 0 = x). Thus, when the mode select M is equal to I, the input carry CO is equal to I and the sum output is A plus the 2's complement of B. When M is equal to 0, the input carry is equal to 0 and the sum generates A + B. Connect the addersubtractor circuit and test it for proper operation. Connect the four A inputs to a fixed binary number 1001 and the B inputs to switches. Perform the following operations and record the values of the output sum and the output carry C 4.
+5
9  5
9+9
9 9
9
9
+ 15
9  15
Show that during addition, the output carry is equal to I when the sum exceeds 15. Also show that when A "'" B, the subtraction operation gives the correct answer, A  B, and the output carry C4 is equal to I. But when A < B, the subtraction gives the 2's complement of B  A and the output carry is equal to O.
Section 11·8 Fllp.Flops
455
Magnitude Comparator. The comparison of two numbers is an operation that de· termines whether one number is greater than, equal to, or less than the other number. Two numbers, A and B, can be compared by first subtracting A  B as done in Fig. 11II. lfthe output in S is equal to zero, we know that A = B. The output carry from C 4 determines the relative magnitude: when C 4 = I, we have A ;" B; when C 4 = 0, we have A < B; and whenC4 = landS 0, we have A > B. It is necessary to supplement the subtractor circuit of Fig. IIII to provide the comparison logic. This is done with a combinational circuit that has five inputs, S I through S 4 and C 4, and three outputs designated by x, y, and z, so that
*
x = I
if A = B
(S = 0000)
Y = I
if A < B
(C4 = 0)
z= I
if A > B
(C4
=I
and S
* 0000)
The combinational circuit can be implemented with the two ICs, 7404 and 7408. Construct the comparator circuit and test its operation. Use at least two sets of numbers for A and B to check each of the outputs x, y, and z.
118
FLIPFLOPS
In this experiment, you will construct, test, and investigate the operation of various flipflop circuits. The internal construction of the flipflops can be found in Sections 62 and 63. 5R latch. The SR latch is a basic flipflop made with two crosscoupled NAND gates. Construct a basic flipflop circuit and connect the two inputs to switches and the two outputs to indicator lamps. Set the two switches to logicI, then momentarily turn each switch separately to the logicO position and back to I. Obtain the truth table of the circuit. R5 FlipFlop. Construct a clocked RS flipflop with four NAND gates. Connect the S and R inputs to two switches and the clock input to a pulser. Verify the characteristic table of the flipflop. D FlipFlop. Construct a clocked D flipflop with four NAND gates. This can be done by modifying the circuit shown in Fig. 65 as follows. Remove gate number 5. Connect the output of gate 3 to the input of gate 4, where gate 5 was originally connected. Show that the modified circuit is identical to the original circuit by deriving the Boolean function for the output of gate 4 in each case. Connect the modified D flipflop circuit and verify its characteristic table.
Construct a clocked masterslave JK flipflop with one MasterSlave FlipFlop. 7410 and two 7400 ICs. Connect the J and K inputs to logicI and the clock input to a
456
Chapter 11
Laboratory Experiments
pulser. Connect the normal output of the master flipflop to one indicator lamp and the normal output of the slave flipflop to another indicator lamp. Press the push button in the pulser and then release it to produce a single positive pulse. Observe that the master flipflop changes when the pulse goes positive and the slave flipflop follows the change when the pulse goes negative. Repeat a few times while observing the two indicator lamps. Explain the transfer sequence from input to master and from master to slave. Disconnect the clock input from the pulser and connect it to a clock generator with a frequency of JO kHz or higher. Using a dualtrace oscilloscope, observe the waveforms of the clock and the master and slave outputs. Verify that the delay between the master and slave outputs is equal to the pulse width. Obtain a timing diagram showing the relationship between the clock waveform and the master and slave flipflop outputs. EdgeTriggered 0 FlipFlop. Construct aDtype positiveedgetriggered flipflop using six NAND gates. Connect the clock input to a pulser, the D input to a toggle switch, and the output Q to an indicator lamp. Set the value of D to the complement value of Q. Show that the flipflop output changes only in response to a positive transi7
2 4 .I
PR
Q
9
15
.I
6
('K 1('
Q'
K
12
14
PR Q
II VeL pin 5 G.\'IJ  pin 13
CK Q'
K
CLR
CLR
:3
g
10
Function tabk

,, Outputs
Inputs
Preset
Clear
Clock
J
K
X
X
X
0
X
X
X
0
X
X
r
0
0
Q
Q' 0
0

....IL Sl... ....IL ....IL FIGURE 1112
Ie typE' 7416
dual JK masterslave flipflops
0
0
No change
0
0
0
0 Toggle
SectIon 11·8
Fllp·Flops
457
tion of the clock pulse. Verify that the output does not change when the clock input is logicI, or when the clock goes through a negative transition, or when it is logicD. Continue changing the D input to correspond to the complement of the Q output at all times. Disconnect the input from the pulser and connect it to the clock generator. Connect the complement output Q' to the D input. This causes the output to complement with each positive transition of the clock pulse. Using a dualtrace oscilloscope, observe and record the timing relationship between the input clock and output Q. Show that the output changes in response to a positive edge transition.
Ie FlipFlops. IC type 7476 consists of two JK masterslave flipflops with preset and clear. The pin assignment for each flipflop is shown in Fig. 1112. The function table specifies the circuit operation. The first three entries in the table specify the operation of the asynchronous preset and clear inputs. These inputs behave like a NAND SR latch and are independent of the clock or the J and K inputs (the X's indicate don'tcare conditions). The last four entries in the function table specify the clock operation with both the preset and clear inputs maintained at logicI. The clock value is shown as a 4
2
3
D
10
PR Q 5
12
D 11
CK
Q'
PR
Q
Vee = pin 14 GND = pin 7
CK
6
Q'
CLR
9
8
CLR 13
Function table Inputs
Outputs
Q
Q'
X
1
0 1
Preset
Clear
Clock
D
0
1
X
1
0
X
X
0
0
0
X
X
1
1
1
1
I
0
0
1
1
1
I
1
1
0
1
1
0
X
No change
FIGURE 11·13 Ie type 7474 dual 0 positiveedgetriggered flipflops
458
Chapter 11
Laboratory Experiments
single pulse. The positive transition of the pulse changes the master flipflop, and the negative transition changes the slave flipflop as well as the output of the circuit. With J = K = 0, the output does not change. The flipflop toggles or complements when J = K = I. Investigate the operation of one 7476 flipflop and verify its function table. IC type 7474 consists of two D positiveedgetriggered flipflops with preset and clear. The pin assignment is shown in Fig. 1113. The function table specifies the preset and clear operations and the clock operation. The clock is shown with an upward arrow to indicate that it is a positiveedgetriggered flipflop. Investigate the operation of one of the flipflops and verify its function table.
119
SEQUENTiAl CIRCUITS In this experiment, you will design, construct, and test three synchronous sequential circuits. Use IC type 7476 JK flipflops (Fig. 1112) in all three designs. Choose any gate type that will minimize the total number of ICs. The design of synchronous sequential circuits is covered in Sections 6 7 and 68. UpDown Counter with Enable. Design, construct, and test a 2bit counter that counts up or down. An enable input E determines whether the counter is on or off. If E = 0, the counter is disabled and remains at its present count even though clock pulses are applied to the flipflops. If E = 1, the counter is enabled and a second input, x, determines the count direction. If x = 1, the circuit counts up with the sequence 00, 01, 10, 1J, and the count repeats. If x = 0, the circuit counts down with the sequence 11,10,01,00, and the count repeats. Do not use E to disable the clock. Design the sequen tial circui t wi th E and x as inputs. State Diagram. Design, construct and test a sequential circuit whose state diagram is shown in Fig. 1114. Designate the two flipflops as A and B, the input as x, and the output as y. Connect the output of the least significant flipflop B to the input x and predict the sequence of states and output that will occur with the application of clock pulses. Verify the state transition and output by testing the circuit. Design of Counter. Design, construct, and test a counter that goes through the following sequence of binary states: 0,1,2,3,6,7,10,11,12,13,14,15, and back to o to repeat. Note that binary states 4, 5, 8, and 9 are not used. The counter must be selfstarting; that is, if the circuit starts from anyone of the four invalid states, the count pulses must transfer the circuit to one of the valid states to continue the count correctly. Check the circuit operation for the required count sequence. Verify that the counter is selfstarting. This is done by initializing the circuit to each unused state by means of the preset and clear inputs and then applying pulses to see whether the coun ter reaches one of the valid states.
Section 1110
0/0
Counten
459
0/1 0/1
I/O I/O
1/1
0/0 FIGURE 11·14 State diagram for Experiment 9
1110
COUNTERS In this experiment, you will construct and test various ripple and synchronous counter circuits. Ripple counters are discussed in Section 7·4, and synchronous counters are covered in Section 7·5. Ripple Counter. Construct a 4·bit binary ripple counter using two 7476 ICs (Fig. 11·12). Connect all asynchronous clear and preset inputs to logic· I. Connect the count· pulse input to a pulser and check the counter for proper operation. Modify the counter so it will count down instead of up. Check that each input pulse decrements the counter by I. Synchronous Counter. Construct a synchronous 4·bit binary counter and check its operation. Use two 7476 ICs and one 7408 IC. Decimal Counter. Design a synchronous BCD counter that counts from 0000 to 1001. Use two 7476 ICs and one 7408 IC. Test the counter for the proper sequence. Determine whether it is self· starting. This is done by initializing the counter to each of the six unused states by means of the preset and clear inputs. The application of pulses must transfer the counter to one of the valid states if the counter is self· starting. Binary Counter with Parallel Load. IC type 74161 is a 4·bit synchronous binary counter with parallel load and asynchronous clear. The internal logic is similar to the circuit shown in Fig. 7·19. The pin assignment to the inputs and outputs is shown in Fig. 11·15. When the load signal is enabled, the four data inputs are transferred into four internal flip·flops, QA through QD, with QD being the most significant bit. There
460
Chapter 11
Laboratory Experiments
I 3 4 Dat
symbol indicates that the register shifts right (down in this case) when the mode is MI (SI So = 01). The /2 , 379 in combinational circuits, 380 dynamic, 381 essential, 384 in sequential circuits, 382 static, 381 Hexadecimal numbers, 5, 9 conversion to binary, 9 Highimpedance state, 420 Huntington postulates, 38
Ie, 62, 399 Ie flipflop, 457 Ie logic families, 62, 399 characteristics. 64, 4015 Ie RAM, 465 IC timer, 471 Identity element, 37 IEEE standard, 479 Implementation table, 177 Implication, 57 Implicationtable, 368 Implied states, 368 Incompletely specified function, 98 Inhibition, 57 Input device, 3 Input equation, 222 Input function, 22224 Integrated circuit, 62, 399 Integrated circuit gates, 65, 438 Inverse, 37 InvertAND, 88 Inverter, 31, 59 InvertOR, 88 JK HipHop. 208, 225 characteristic table, 209, 224 excitation table, 234 masterslave, 213
'\Iagnitud(' comparator, 16365 Majority logic, 448 Map method, 72 alternate versions, 109 Master clock, 203 Masterslave flipflop, 21114 Maximal compatible, 371 73 Maxterm, 4950 Mealy model, 22728 Medium scale integration, 62, 152 Mega, 290 Memory: access time, 292 cell,294 dynamic, 293 graphic symbol, 496 integrated circuit, 460 internal construction, 29396 random access, 289 readonly, 180 sequential access, 292 static, 293 volatile, 293 Memory address, 290 Memory enable, 295 Memory decoding, 29396 Memory expansion, 29698 Memory read, 292 Memory select, 294, 296 Memory unit, 3, 290 example, 29495 Memory write, 291 Merger diagram, 371 Merging of flow table, 36973 Metaloxide semiconductor (see MOS) Minterm, 4950 Minuend,6 Mode control, 268 ModN counter, 284
Moore model, 22728 MOS, 63,424 basic gate, 42426 MOS transistor, 424 MSI, 62, 257, 437 MSI circuits, 152,257 MSI components: adder, 155,453 addersubtractor, 15657 BCD adder, 16163 binary adder, 15556 counter, 272~82, 439 decoder, 16668,449,460 demultiplexer, 16870 encoder, 17075 Johnson counter, 288 lookahead carry generator, 15760 magnitUde comparator, 16365 multiplexer, 17380. 452, 463 mndomaccess memory, 289, 466 readonly memory, I gO register, 25862 shift register, 26468, 462, 46M Multilevel NAND circuit, 130 Multilevel NOR circuit, 138 Multiplexer, 17375 design with, 32330 implementation with, 17680 Multiplier, 33032,47577 MUX (see Multiplexer) '1A:"IiI),57 NANDAND, 95 NAND circuits, 8991 analysis, 134 multilevel, 130 NAND gate, 58 graphic symbol, 88 Negative edge, 210 Negation symbol, 483 Negative logic, 67 graphic symbol, 68 Next state, 206 Next state equation, 219 Noise margin, 64, 4045 Noncritical race, 348 Nondegenerate forms, 9495 NOR,57 NOR circuits, 9193 analysis, 140 multilevel, 138 NOR gate, 58 graphic symbol, 88 NOT,29 Number base conversion, 69 Number ~"'Ystems, 4 Octal numbt'r. 5. I) conversion to binary, 9 conversion to decimal, 68 Odd function, 61, 144 One flipflop per state, 321 Open collector gate, 413 common bus, 416 wired logic, 415
Index
Operator precedence. 43
Random access memory. 289
OR,29
Road, 29092
ORAND,95 ORANDINVERT,9697 OR gat" 31, 59 OR~invert. 88 ORNAND,95 Oscilloscope. 437 Output device, 3 Overflow. 16
Read only memory, 180 combinalionallogic with, 18285 truth table, 184 types, 18586 Rectangular shape symbols, 479 Reduction of state table, 22832, 36669 Register, 25, 25861 with paraUelload, 259 Register operations, 368, 31112 Register transfer, 26 Reset, 204 Resistor~transistor logic (see RTL) Ring counter, 286, 461 switch tail, 288 Ripple counter, 27277 ROM (see Read only memory) RS flipflop. 2056
PAL, 15354 Parallel adder. 155.473 with lookahead carry, 160 Parallel load, 259 Parallel transfer, 266 Parity bit, 20, 299 Parity check, 14748 Parity genemte, 14647 PLA. 15354 PLA program table, 18990 PLA control, 33436 PLD,153 Polarity indicator, 68, 484 Positive edge, 210 Positive logic, 67 Postulate. 36 Power dissipation, 64, 4023 Power supply, 461 Present state, 206 Prime implicant, 80, 101 essential, 8081, 107 Prime implicant table. 107 Primitive flow table, 346. 360 Priority encoder. 17273 Product of maxtenns, 53 Pr04uct of sums, 55 Product term. 55 Programmable array logic, 192 fuse map, 196 program table, 195 Programmable logic array. 187 control logic, 33436 field programmable, 187 program tatlle, 18889, 336 Programmable logic device (PLD), 153 Programmable ROM. 186 PROM,186 PROM progranuner, 186 Propagation delay, 64, 4034 Pulse generator. 436 Pulse transition, 210 Pulse~triggered flip~flop, 490 Pulser, 436 Qualifying symbols, 482 method, 101
Quine~McCluskey
Race condition. 34850 critical, 348 noncritical, 348 Racefree assignment, 37479 Radix, 4 RAM. 289, 2%
RfL,409 basic gate, 410 Saturation region, 407 Schottky transistor, 418 Schottky TIL. 41819 Secondary variable, 342 Selfcorrecting counter, 251 Sequential circuit, 202, 341 analysis, 21820, 34346 asynchronous, 341 clocked, 203 design. 23646. 35966 hazards in. 380 synchronous. 202 Sequential logic, 202 Serial addition, 26971 Serial input, 264, 268 Serial output, 264, 268 Serial transfer, 265 Set, 204 Sevensegment display. 150,450 Shared row method, 378 Shift register. 264. 461 bidirectional, 26768 with feedback, 461 graphic symbol. 49293 with paraJlelload, 267 Sign bit, 14 Signed binary numbers, 14 addition, 1517 subtraction, 17 Signed complement, 15 Signed magnitude, 15 Simplification, 8487 Small scale integration, 62 Socket strip, 436 Source, 424 Speedpower product, 412 SR latch, 35254 implementation with, 35758 SSI, 62, 437 Stable condition, 343, 350 Standard forms, 55 Standard graphic symbols, 479 adder, 480
515
coder, 481 counter, 49495 decoder, 487 flipflops, 489 gates, 480 memory, 496 multiplexer, 488 register, 491 shiftregister, 49293 State. 202 State assignment. 23233, 347 racefree, 37479 State box, 309 State diagram, 22122 State machine, 308 State table, 22021, 367 reduction, 22832, 36769 Static hazard, 381 Status condition. 307 Steady state condition, 343 Subtraction, 6 of signed numbers, 17 of unsigned numbers. 12 Subtractor, 121, 15657 Subtrahend, 6 Sum of minterms, 51 Sum of products. 55 Simplification, 8486 Switching circuit, 29 Switch tail ring counter, 288 Synchronous counter, 277 BCD,27981 binary, 27779 'with parallel load, 28183 updown, 27980 Synchronous sequential circuit, 20227 analysis, 21820 clocked, 203 design, 23646 Syndrome, 299 Tabulation method, 10l T flipflop, 210 Threestate gate, 42022 Timer circuit, 471 Timing sequence, 285, 315 Timing signals, 28687 Timing diagram, 32 Toggle,218 Toggle switch, 436 Total state, 345 Totempole gate, 41618 Tmnsfer,57 Transmission gate, 430 Transmission gate circuits, 430 D latch, 433 exclusiveOR, 431 multiplexer, 432 Transistor, 406 characteristics, 4067 circuit, 4068 Transistor~transistor logic (see TIL) Transition diagram, 375 Transition table, 344, 363 Trigger, 210
516
Index
Unidirectional shifl tel . .(>~ Unipolar, 424 Universal gate, 13031, 138 39 Unsigned binary numbers, 12 subtraction, 12 Unstable condition, 351 Unstable state, 365 Unused states, 243, 250 Updown counter, 27980
1hggering of ft.ipflop, 210
Tristate, 420 Truth table, 29. 45, 12829 TTL, 63, 66, 412 5400 series, 64
open collector, 41316 Schottky, 66, 41819 7400 series, 64, 412 standard. 65, 412 threestate, 42022 totempole, 41618 TTL data book, 437 Twolevel forms, 97 Twolevel Implementation,
~6,
9495
Veill'h dia~ram. 72 ·",·,f"'wf·yenq.,diagram.44 Very large sacale integration, 63, 153
VLSI, 63, 153 Volatile memory. 293 Waveform. 444 Weighted code, 1819 WiredAND, 94 Wiredlogic, 94, 415 WiredOR,94 Word. 180,289 Wordtime. 26566 generation of. 28586 Write, 29091 X()R
(St'l'
ExciusiveORl