Morris Mano Digital Design 3rd Edition.pdf

PREFACE ix 1 BINARY SYSTEMS 1 1-1 Digital Computers and Digital Systems 1 1-2 Binary Numbers 4 1-3 Number Base Conversions 6...

PREFACE ix 1 BINARY SYSTEMS 1 1-1 Digital Computers and Digital Systems 1 1-2 Binary Numbers 4 1-3 Number Base Conversions 6 1-4 Octal and Hexadecimal Numbers 9 1-5 Complements 10 1-6 Signed Binary Numbers 14 1-7 Binary Codes 17 1-8 Binary Storage and Registers 25 1-9 Binary Logic 28 References 32 Problems 33 2 BOOLEAN ALGEBRA AND LOGIC GATES 36 2-1 Basic Definitions 36 2-2 Axiomatic Definition of Boolean Algebra 38 2-3 Basic Theorems and Properties of Boolean Algebra 41 III iv Contents 2-4 Boolean Functions 45 2-5 Canonical and Standard FOnTIS 49 2-6 Other Logic Operations 56 2-7 Digital Logic Gates 58 2-8 Integrated Circuits 62 References 69 Problems 69 3 SIMPLIFICATION OF BOOLEAN FUNCTIONS 72 3-1 The Map Method 72 3-2 Two- and Three-Variable Maps 73 3-3 Four-Variable Map 78 3-4 Five-Variable Map 82 3-5 Product of Sums Simplification 84 3-6 NAND and NOR Implementation 88 3-7 Other Two-Level Implementations 94 3-8 Don't-Care Conditions 98 3-9 The Tabulation Method 101 3-10 Determination of Prime Implicants 101 3-11 Selection of Prime Implicants 106 3-12 Concluding Remarks 108 References 110 Problems III 4 COMBINATIONAL LOGIC 114 4-1 Introduction 114 4-2 Design Procedure 115 4-3 Adders 116 4-4 Subtractors 121 4-5 Code Conversion 124 4-6 Analysis Procedure 126 4-7 Multilevel NAND Circuits 130 4-8 Multilevel NOR Circuits 138  Contents V 4-9 Exclusive-OR Functions 142 References 148 Problems 149 5 MSI AND PLD COMPONENTS 152 5-1 Introduction 152 5-2 Binary Adder and Subtractor 154 5-3 Decimal Adder 160 5-4 Magnitude Comparator 163 5-5 Decoders and Encoders 166 5-6 Multiplexers 173 5-7 Read-Only Memory (ROM) 180 5-8 Programmable Logic Array (PLA) 187 5-9 Programmable Array Logic (PAL) 192 References 197 Problems 197 6 SYNCHRONOUS SEOUENTIAL LOGIC 202 6-1 Introduction 202 6-2 Hip-Hops 204 6-3 Triggering of Hip-Flops 210 6-4 Analysis of Clocked Sequential Circuits 218 6-5 State Reduction and Assignment 228 6-6 Hip-Flop Excitation Tables 231 6-7 Design Procedure 236 6-8 Design of Counters 247 References 251 Problems 251 7 REGISTERS, COUNTERS, AND THE MEMORY UNIT 257 7-1 Introduction 257 7-2 Registers 258 vi Contents 7-3 Shift Registers 264 7-4 Ripple Counters 272 7-5 Synchronous Counters 277 7-6 Timing Sequences 285 7-7 Random-Access Memory (RAM) 289 7-8 Memory Decoding 293 7-9 Error-Correcting Codes 299 References 302 Problems 303 8 ALGORITHMIC STATE MACHINES IASMI 307 8-1 Introduction 307 8-2 ASM Chart 309 8-3 Timing Considerations 312 8-4 Control Implementation 317 8-5 Design with Multiplexers 323 8-6 PLA Control 330 References 336 Problems 337 9 ASYNCHRONOUS SEQUENTIAL LOGIC 341 9-1 Introduction 341 9-2 Analysis Procedure 343 9-3 Circuits with Latches 352 9-4 Design Procedure 359 9-5 Reduction of State and Flow Tables 366 9-6 Race-Free State Assignment 374 9-7 Hazards 379 9-8 Design Example 385 References 391 Problems 392  Contents vii 10 DIGITAL INTEGRATED CIRCUITS 399 10-1 Introduction 399 10-2 Special Characteristics 401 10-3 Bipolar-Transistor Characteristics 406 10-4 RTL and DTL Circuits 409 10-5 Transistor-Transistor Logic (TTL) 412 10-6 Emmitter-Coupled Logic (ECL) 422 10-7 Metal-Oxide Semiconductor (MOS) 424 10-8 Complementary MOS (CMOS) 427 10-9 CMOS Transmission Gate Circuits 430 References 433 Problems 434 11 LABORATORY EXPERIMENTS 436 11-0 Introduction to Experiments 436 11-1 Binary and Decimal Numbers 441 11-2 Digital Logic Gates 444 11-3 Simplification of Boolean Functions 446 11-4 Combinational Circuits 447 11-5 Code Converters 449 11-6 Design with Multiplexers 451 11-7 Adders and Subtractors 452 11-8 Flip-Flops 455 11-9 Sequential Circuits 458 11-10 Counters 459 11-11 Shift Registers 461 11-12 Serial Addition 464 11-13 Memory Unit 465 11-14 Lamp Handball 467 11-15 Clock-Pulse Generator 471 11-16 Parallel Adder 473 11-17 Binary Multiplier 475 11-18 Asynchronous Sequential Circuits 477 ) viii Contents 12 STANDARD GRAPHIC SYMBOLS 479 12-1 Rectangular-Shape Symbols 479 12-2 Qualifying Symbols 482 12-3 Dependency Notation 484 12-4 Symbols for Combinational Elements 486 12-5 Symbols for Flip-Flops 489 12-6 Symbols for Registers 491 12-7 Symbols for Counters 494 12-8 Symbol for RAM 496 References 497 Problems 497 APPENDIX: ANSWERS TO SELECTED PROBLEMS 499 INDEX 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 re- quire 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 de- sign 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 combi- national circuits. The next three chapters deal with synchronous clocked sequential cir- cuits. 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 up-to-date material and deleting ob- solete 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 illus- trated. A new section has been added on signed binary numbers. Chapter 2 introduces the basic postulates of Boolean algebra and shows the correla- tion 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 inte- grated 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 expres- sions. The map method is also used to simplify digital circuits constructed with AND- OR, NAND, or NOR gates. All other possible two-level 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 combina- tional 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 multi- level NAND and NOR implementation have been revised to show a simpler procedure for converting AND-OR diagrams to NAND or NOR diagrams. Chapter 5 presents various medium scale integration (MS!) circuits and pro- grammable logic device (PLD) components. Frequently used digital logic functions such as parallel adders and sub tractors, decoders, encoders, and multiplexers, are ex- plained, and their use in the design of combinational circuits is illustrated with exam- ples. 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 syn- chronous sequential circuits. The gate structure of several types of flip-flops is pre- sented together with a discussion on the difference between pulse level and pulse tran- sition 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 D-type flip-flops. 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 ac- cess 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 paral- lel 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 imple- mentation is also described that uses SR latches as the storage elements in an asyn- chronous 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 sec- tion 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 exam- ples 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 cir- cuits is explained by referring to diagrams in previous chapters where siruilar compo- nents are originally introduced. Each experiment is presented informally rather than in a step-by-step fashion so that the student is expected to produce the details of the cir- cuit 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 91-1984. 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 cir- cuits 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 inde- pendent 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 ad- vances that would have been unattainable otherwise. Our space program would have been impossible without real-time, continuous computer monitoring, and many busi- ness 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, general-purpose digital computers can perform a wide variety of informa- tion-processing tasks. The general-purpose digital computer is the best-known 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' (a) Two-input AND gate (b) Two-input OR gate (c) NOT gate or inverter ~~ABC ~~A+B+C+D (d) Three -input AND gate (e) Four -input OR gate FIGURE 1-6 Symbols for digital logic circuits 32 Chapter 1 Binary Systems x ° 0 )' ----,O'------'0:..J1 ~ AND: x. J' ---,O'--_-'0...Jr-T"l 0 0 OR,,+) ~ NOT, ~,' -n ° 0 I I FIGURE 1-7 Input-output sign----F 4 (d) F4 = xy' + x'z., FIGURE 2-4 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 cut-and-try procedure em- ploying the postulates, the basic theorems, and any other manipulation method that be- comes familiar with use. The following examples illustrate this procedure. Example Simplify the following Boolean functions to a minimum number of literals. 2-1 1, x + x 'y ~ (x + x ')(x + y) ~ I - (x + y) ~ x +Y 2. x(x' + y) = xx' + xy = 0 + xy = xy 48 Chapter 2 Boolean Algebra and Logic Gates 3. x'y'z + x'yz + xy' = x'z(y' + y) + xy = x'z + xy 4. xy + x' z + yz = xy + x' z + yz (x + x') = xy + X 'z + xyz + X yz I = xy(1 + z) + x'z(J + y) = xy + x1z 5. (x + y)(x' + z)(y + 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 al- gebraically 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 three-variable form of the first DeMorgan's theorem is derived below. The postu- lates and theorems are those listed in Table 2-1. (A + B + C)' = (A + X)' letB + C = X = A'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 +... + F)' = A'B'C'D'". F' (ABCD... Fl' = 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 Find the complement of the functions F, = x'yz' + x'y'zandf; = x(y'z' + yz). By 2-2 applying DeMorgan's theorem as many times as necessary, the complements are ob- tained as follows:  Section 2-5 Canonical and Standard Forms 49 F; = (x'yz' + x'y'z)' = (x'yz')'(x'y'z)' = (x + y' + z)(x + Y + z') F; = [x(y'z' + yz)]' = x' + (y'z' + yz)' = x' + (y'z')'· (yz)' = x' + (y + z)(y' + z ') 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 inter- change of AND and OR operators and 1's and O's. Example Find the complement of the functions FJ and F, of Example 2-2 by taking their duals 2-3 and complementing each literal. 1. FJ = x'yz' + x'y'z. The dual of FJ is (x' + Y + z')(x' + y' + z). Complement each literal: (x + y' + z)(x + Y + z ') = F;. 2. F, = x(y'z' + yz). The dual of F, is x + (y' + z')(y + z). Complement each literal: x' + (y + z)(y' + z ') = F;. 2·5 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. 2-1 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 2-3 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 be- ing 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 de- notes 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 2-3. 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 2-3 Minterms and Maxterms for Three Binary VarIables Minterms Maxterms x y z Term Designation Term Designation ------- --,-,--.- 0 0 a x'y'z' rn" x + Y+ z 0 0 x'y'z rn, x + Y + z' a 0 X'yz' rn, X+y'+Z 0 I I x'yz m, X+y'+Z' 0 0 xy'z' m, x' + y + z 0 I xy'Z m, x + Y + z' 0 xyz I m, x' + y' + z xyz m, x + y' + z' 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 func- tion, and then taking the OR of all those terms. For example, the function 11 in Table 2-4 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 Similarly, it may be easily verified that }2 = x' yz + xy' z + xyz' + xyz = m, + ms + mo + m7 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 2-4 Functions of Three Variables -----_._---_.--. '1. -. - ~.---- x y z Function " Function ---.---.- --.- 0 0 0 0 0 0 0 I I 0 0 1 a 0 0 0 1 0 I 0 0 1 0 0 0 0 a  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'y'z' + x'yz' + x'yz + xy'z + xyzl 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 ex- pression 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 Express the Boolean function F = A + B 'C in a sum of minterms. The function has 2-4 three variables, A, B, and C. The first term A is missing two variables; therefore: A = A (B + B ') = AB + AB' This is still missing one variable: 52 Chapter 2 Boolean Algebra and Logic Gates A = + C') + AB'(C + C') AB(C = ABC + ABC' + AB'C + AB'C' 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 + 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- 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 2-4: F = A + B'C The truth table shown in Table 2-5 can be derived directly from the algebraic expres- sion by listing the eight binary combinations under variables A, B, and C and inserting  Section 2-5 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 Express the Boolean function F = xy + x'z in a product of maxterm form. First, con· 2-5 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' + Y + z)(x' + Y + z ') x + z = x + z + yy' = (x + y + z)(x + y' + z) Y + z = Y + z + xx' = (x + 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' + Y + z ') = MoM,M.M, A convenient way to express this function is as follows: F(x, y, z) = n (0, 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 dif- ferent 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 2-3. 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 simi- lar. 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 func- tion. 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 2-6. 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 0 0 I 0 0 0 0 I I I 1 0 0 0 0 0 0  Section 2-5 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 2-5. 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 ex- ample 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, respec- tively. 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 func- tion 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 Chapter 2 Boolean Algebra and Logic Gates 2-6 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 2-7. 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 func- tions 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 0 0 o o o o o o o 1 o o o o u 1 o o o o 1 1 U 0 o 1 o o 1 o o 1 o 0 1 I0 o o o o o o o _~~:;~~~l.. + o c. 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 2-8. 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 ex- pressing the other functions. Such operator symbols are listed in the second column of Table 2-8. However, all the new symbols shown, except for the exclusive·OR sym- bol, EEl, arc not in common use by digital designers. Each of the functions in Table 2-8 is listed with an accompanying name and a com- ment 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 2-6 Other Logic Operations 57 TABLE 2-8 Boolean Expressions for the 16 Functions of TWo Variables Boolean functions Operator Name Comments sym.bol Fo =0 Null Binary constant 0 Fl =xy x'y AND x andy F2 =xy' x/y Inhibition x but not y F3 =x Transfer x F4 =x'Y y/x Inhibition Y but not x F, =y Transfer y F6 =xy ' +X'y x$y Exclusive-OR x or y but not both F7 = x + Y x+y OR xory F. = (x + y)' xh NOR Not-OR F9 = xy + x'y' x8y Equivalence x equals y FIO=y' y' Complement Noty Fll =x+y' xCy Implication If y then x Fl2 = x' x' Complement Not x F13=X'+Y x :::J y Implication If x then y F" = (xy) , xfy NAND Not-AND Fis = 1 Identity 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 vari- ables. 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 with- out 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 opera- tors have been mentioned in conjunction with Boolean algebra. The other four func- tions are extensively used in the design of digital systems. The NOR function is the complement of the OR function and its name is an abbrevi- ation of not-OR. Similarly, NAND is the complement of AND and is an abbreviation of not-AND. The exclusive-OR, abbreviated XOR or EOR, is similar to OR but ex- cludes 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 exclusive-OR and equivalence functions are the complements of each other. This can be easily verified by inspecting Table 2-7. The truth table for the exclusive-OR 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 exclusive-NOR, i.e., exclusive-OR-NOT. Boolean algebra, as defined in Section 2-2, 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 fea- sibility and economy of producing the gate with physical components, (2) the possibil- ity 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 im- plement Boolean functions alone or in conjunction with other gates. Of the 16 functions defined in Table 2-8, 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, trans- fer, AND, OR, NAND, NOR, exclusive-OR, and equivalence, are used as standard gates in digital design. The graphic symbols and truth tables of the eight gates are shown in Fig. 2-5. 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. 1-6. 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 particu- lar 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 equiv- alent 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 be- cause NAND and NOR gates are easily constructed with transistor circuits and because Boolean functions can be easily implemented with them.  Section 2·7 Digital Logic Gates 59 Name Graphic Algebraic Truth symbol function table x y F 0 0 0 AND :=O-F F= xy 0 I 0 I 0 0 I I I x y F 0 0 0 OR :=D-- F F-x+y 0 I I I 0 I I I I Inverter x ----{»-- F F- x' itto I I 0 Buffer X---{>---F F=x x itto I Y 0 I F 0 0 I NAND ~=D----F F - (xy), 0 I I 0 I I I I 0 x Y F 0 0 I NOR ~=L>-F F = (x + y)' 0 I I 0 0 0 I I 0 x Y F Exclusive-OR (XOR) :=jD-F F= xy' + x'y -x$y 0 0 I 0 I 0 0 I I I I 0 Exclus~tNOR ; ~ equivalence ~ _F F= xy =x0y + x'y' ~~ 001 010 100 I I I FIGURE 2-5 Digital logic gates 60 Chapter 2 Boolean Algebra and Logic Gates The exclusive-OR 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 exclusive-NOR, gate is the complement of the exclusive-OR. as indicated by the small circle on the out- put side of the graphic symbol. Extension to Multiple Inputs The gates shown in Fig. 2-5, 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 x+y=y+x commutative and (x + y) + z = x + (y + z) = x + \' + z associative 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) t z '" x (yt t z), as shown in Fig. 2-6 and below: (x t y) ~ z = [(x + v)' + z]' = (x + y)z' = xz' + \'z' x t(y tz) = [x + (y + zJ,], = x'(y + z) = x'y + x'z x _---t-, )o---(x lv) i : (x -- yl z' -------L.-" x - - - -_ _ _ _~-..., )O--x i ( ~'~ ;,:) - x' (y --i- :) FIGURE 2-6 Dernonstratlnq the nOJldssoclativlty of trl(' Nor,.' operator: IX i yl 12 ( 1/ l' J.~I  Section 2-7 Digital Logic Gates 61 To overcome this difficulty, we define the multiple NOR (or NAND) gate as a comple- mented OR (or AND) gate. Thus, by definition, we have x 1 y 1z = (x + y + z)' x l' y l' z = (xyz) , The graphic symbols for the 3-input gates are shown in Fig. 2-7. 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. 2-7(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 ex- pression in sum of products can be implemented with NAND gates. Further discussion of NAND and NOR gates can be found in Sections 3-6, 4-7, and 4-8. The exclusive-OR and equivalence gates are both commutative and associative and can be extended to more than two inputs. However, multiple-input exclusive-OR gates are uncommon from the hardware standpoint. In fact, even a 2-input 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 exclusive-OR is an odd func- tion, i.e., it is equal to I if the input variables have an odd number of I's. The con- struction of a 3-input exclusive-OR function is shown in Fig. 2-8. It is normally imple- mented by cascading 2-input gates, as shown in (a). Graphically, it can be represented with a single 3-input 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 exclusive-OR can be found in Section 4-9. x~ i'~(x+y+z)' r=c>- (xyz)' (a) Three-input NOR gate (b) Three-input NAND gate A - - - J -......... B ):>----, C-.....,_~ ~--F= [(ABC)'. (DE)'I' =ABC+ DE »----' D - - - J -......... E (c) Cascaded NAND gates FIGURE 2·7 Multiple-input and cascaded NOR and NAND gates 62 Chapter 2 Boolean Algebra and Logic Gates '~ F="I;"'J'J"~ " -~ 0 0 0 0 r 0 I F 0 I 0 I () I (a) Using 2-input gates 0 I I () I 0 0 I I 0 I 0 I I 0 0 I I I (b) 3-input gate (e) Truth tahle FIGURE 2-8 3-input pxciuslve-OR gate 2-8 INTEGRATED CIRCUITS Digital circuits are constructed with integrated circuits. An integrated circuit (abbrevi- ated IC) is a small silicon semiconductor crystal, called a chip. containing the elec- tronic 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 14-pin IC package with dimensions of 20 x 8 x 3 millimeters. An entire mi- croprocessor is enclosed within a 64-pin 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 in- formation 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 large-scale integration device. Small-scale 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. Medium-sale integration (MSI) devices have a complexity of approximately 10 to 100 gates in a single package. They usually perform specific elementary digital opera- tions such as decoders, adders, or multiplexers. MSI digital components are introduced in Chapters 5 and 7.  Section 2-8 Integrated Circuits 63 Large-scale 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 large-scale integration (VLSI) devices contain thousands of gates within a sin- gle package. Examples are large memory arrays and complex microcomputer chips. Because of their small size and low cost, VLSI devices have revolutionized the com- puter 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 opera- tion, but also by the specific circuit technology to which they belong. The circuit tech- nology is referred to as a digital logic fumily. Each logic fumily has its own basic elec- tronic 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 elec- tronic 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 transistor-transistor logic ECL emiter-coupled logic MOS metal-oxide semiconductor CMOS complementary metal-oxide semiconductor TTL is a widespread logic family that has been in operation for some time and is con- sidered as standard. ECL has an advantage in systems requiring high-speed 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 pre- sented 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 transistor-transistor logic fumily evolved from a previous technology that used diodes and transistors for the basic NAND gate. This technology was called DTL for diode-transistor logic. Later the diodes were replaced by transistors to improve the cir- cuit operation and the name of the logic fumily was changed to TTL. Emitter-coupled logic (ECL) circuits provide the highest speed among the integrated digital logic families. ECL is used in systems such as supercomputers and signal pro- cessors, where high speed is essential. The transistors in ECL gates operate in a nonsat- urated state, a condition that allows the achievement of propagation delays of I to 2 nanoseconds. 64 Chapter 2 Boolean Algebra and Logic Gates The metal-oxide semiconductor (MOS) is a unipolar transistor that depends upon the flow of only one type of carrier, which may be electrons (n-channel) or holes (p-channel), This is in contrast to the bipolar transistor used in TTL and ECL gates, where both carriers exist during normal operation. A p-channel MOS is referred to as PMOS and an n-channel 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 cir- cuits. 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 evalu- ated and compared are discussed in Section 10-2. They are listed here for reference. Fan-out 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. Integrated-Circuit Gates Some typical SS] circuits are shown in Fig. 2-9. Each IC is enclosed within a 14- or 16-pin 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. 2-9(a) shows two TTL SSI circuits. The 7404 provides six (hex) inverters in a package. The 7400 provides four (quadruple) 2-input NAND gates. The terminals marked Vee and GRD (ground) are the power-supply 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 2-9 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 Vee 14 13 12 11 10 9 8 14 13 12 11 10 9 8 2 3 4 5 6 7 2 3 4 5 6 7 GND GND 7404-Hex inverters 7400 Quadruple 2-input NAND gates (a) TTL gates. VCC2 V CC2 16 15 14 13 12 11 10 9 16 15 14 13 12 11 10 9 2 3 4 5 6 7 8 2 3 4 5 6 7 8 VCC ] VEE VCCl NC' VEt: 10102 ·Quadruple 2-input NOR gates 10107 Triple exclusive-OR/NOR gates (b) ECL gates. VDD NC NC' NC 14 13 12 11 10 9 8 16 15 14 13 12 11 10 9 6 NC Vss VDD 4002-Dual4-input NOR gates. 4050-Hex buffers. (c) CMOS gates. FIGURE 2-9 Some typical integrated-circuit 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 74 7486 High-speed TTL 74H 74H86 Low-power TTL 74L 74L86 Schottky TTL 74S 74S86 Low-power Schottky TTL 74LS 74LS86 Advanced Schottky TTL 74AS 74AS86 Advanced Low-power Schottky TTL 74ALS 74ALS86 - - - - - - - - ,. - -...- -,-------_.. -. _ - -..- identification number that starts with 74. Likewise, ICs that are part of the high-speed 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 10-2 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 2-9 with an 86 number, no matter what the prefix, contain four exclusive-OR gates with the same pin assignment in each package. The most common EeL rcs are designated as the 10000 series. Figure 2-9(b) shows two ECL circuits. The 10102 provides four 2-input 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 exclusive-OR gates. Here again there are two outputs from each gate; the other output provides the exclusive-NOR function. ECL gates have three terminals for power supply. VCCI and Ven are usually connected to ground, and VEE to a -5.2-volt supply. The two logic levels for ECL are -0.8 and -1.8 volts. CMOS circuits of the 4000 series are shown in Fig. 2-9(c). Only two 4-input NOR gates can be accommodated in the 4002 because of pin limitation. The 4050 Ie pro- vides six buffer gates. Both ICs have unused terminals marked NC (no connection). The terminal marked VDD requires a power-supply 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. 2-9(a). The CMOS series available commercially are listed in Table 2-10. The 74HC series operates at higher speeds than the 74C series. The 74HCT series is both electrically and pin com- patible with TTL devices. This mearis that 74HCT ICs can be connected directly to TTL ICs without the need of interfacing circuits.  Section 2-8 Integrated Circuits 67 TABLE 2·10 Various Series of the CMOS Logic Family CMOS series Prefix Example Original CMOS 40 4009 Pin compatible with TIL 74C 74C04 High·speed and pin compatible with TIL 74HC 74HC04 High·speed and electrically compatible with TTL 74HCT 74HCT04 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 logic-l and the other logic-O. 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. 2-10. The higher signal level is designated by H and the lower signal level by L. Choosing the high-level H to represent logic-I defines a positive logic system. Choosing the low-level L to represent logic-I 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. Integrated-circuit 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 pos- itive or negative logic polarity. Consider, for example, the TTL gate shown in Fig. 2-1I(b). The truth table for this gate as given in a data book is listed in Fig. 2-1I(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. 2-1I(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. 2-1I(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. 2-1I(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. 2-1I(f). The sma)) triangles in the inputs and output Logic Signal Logic Signal value value value value H o 0 S L (a) Positive logic (b) Negative logic FIGURE 2·10 Signal assignment and logic polarity 68 Chapter 2 Boolean Algebra and Logic Gates )' I. L L L II L /{ L L /{ II /I (a) Truth table (h) C;ate hlock diagram with Ii and L x y , 0 0 0 0 I 0 0 0 (e) Truth table for (-x' x----{J-x' x--[>-x' Buffer-invert AND-invert OR-invert (c) Three graphic symbols for inverter. FIGURE 3-17 GrdphlC symbols for NAND and NOf>1 (rues  SectJon 3-6 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 negative-logic polarity indicator (see Section 2-8 and Fig. 2-11). With small triangles in the input terminals, the graphic symbol denotes a negative-logic po- larity for the inputs, but the output of the gate (not having a triangle) would have a pos- itive-logic 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 dia- grams of Fig. 3-18. All three diagrams are equivalent and implement the function: F=AB+CD+E The function is implemented in Fig. 3-l8(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 re- placed by a NAND gate with an invert-OR symbol. The single variable E is comple- mented and applied to the second-level invert-OR 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 A B B C C F F D D E' E (b) NAND-NAND (c) NAND-NAND FIGURE 3-18 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. 3-18(b) produces the circuit in (a). Therefore, the two diagrams implement the same function and are equivalent. In Fig. 3-18(c), the output NAND gate is redrawn with the conventional symbol. The one-input NAND gate complements variable E. It is possible to remove this in- verter and apply E' directly to the input of the second-level 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. 3-18(c) can be verified algebraically. The NAND function it implements can be easily converted to a sum of products form by us- ing DeMorgan's theorem: F = [(AB)" (CD)', E']' = AB + CD + E From the transformation shown in Fig. 3-18, 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 lit- erals. The inputs to each NAND gate are the literals of the term. This constitutes a group of first-level gates. 3. Draw a single NAND gate (using the AND-invert or invert-OR graphic symbol) in the second level, with inputs coming from outputs of first-level gates. 4. A term with a single literal requires an inverter in the first level or may be com- plemented and applied as an input to the second-level 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 de- sired, it would be necessary to insert a one-input 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 Implement the following function with NAND gates: 3-9 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. 3-19(a). There are only two l's in the map, and they can-  Section 3·6 NAND and NOR Implementation 91 yz. y x 00 01 11 10 a 1 a a a F = x'y'z' + xyz' F' = x'y + xy' + z a a a. 1. z (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 3-9 with NAND gates not be combined. The simplified function in sum of products for this example is F = X/y'z' + xyz' The two-level 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 two-level NAND gate for generating F' is shown in Fig. 3-l9(c). If output F is reo quired, it is necessary to add a one· input NAND gate to invert the function. This gives a three-level 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 one-input 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 OR-AND to the NOR-NOR diagram is depicted in Fig. 3-20. 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 three-step NAND rule. except that the simplified expression must be in the product of sums and the terms t,)r the first-level NOR gates are the sum terms. A term with a single literal requires a one-input NOR or inverter gate or may be complemented and applied directly to the second-level NOR gate. A second way to implement a function with NOR gates would be to use the expres- sion for the complement of the function in product of sums. This will give a two-level implementation for F' and a three-level implementation if the normal output F is re- quired. 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 Implement the function of Example 3-9 with NOR gates. 3-10 The map of this function is drawn in Fig. 3-l9(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 F D /J F F' (a) OR-AND (b) NOR-NOR (e) NOR-NOR FIGURE 3-20 fhwf' w"'Y\ to !!lI!J:crr~ent F" !A 811 C t.!I!  Section 3-6 NAND and NOR Implementation 93 F = (x + y')(x' + y)z' The two-level implementation with NOR gates is shown in Fig. 3-21(a). The term with a single literal z' requires a one-input NOR or inverter gate. This gate can be removed and input z applied directly to the input of the second-level 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 ob- tain the complement of the function in product of sums as required for NOR implemen- tation: F' = (x + y + z)(x' + y' + z) The two-level implementation for F 'is shown in Fig. 3-2I(b). If output F is desired, it can be generated with an inverter in the third level. x x y F y' z )o-~----F' x' x' F l Y-"'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