ONES AND ZEROS
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`IEEE Press Understanding Science & Technology Series
`The IEEE Press Understanding Series treats important topics in science and
`technology in a simple and easy-to-understand manner. Designed expressly for
`the nonspecialist engineer, scientist, or technician, as well as the
`technologically curious-each volume stresses practical information over
`mathematical theorems and complicated derivations.
`
`Books in the Series
`
`Blyler, J. and Ray, G., What's Size Got to Do With It? Understanding
`Computer Rightsizing
`
`Deutsch, S., Understanding the Nervous System: An Engineering Perspective
`
`Evans, B., Understanding Digital TV: The Route to HDTV
`
`Gregg, J., Ones and Zeros: Understanding Boolean Algebra, Digital Circuits,
`and the Logic of Sets
`
`Hecht, J., Understanding Lasers: An Entry-Level Guide, 2nd Edition
`
`Kamm, L., Understanding Electro-Mechanical Engineering: An Introduction
`to Mechatronics
`
`Kartalopoulos, S. V., Understanding Neural Networks and Fuzzy Logic: Basic
`Concepts and Applications
`
`Lebow, I., Understanding Digital Transmission and Recording
`
`Nellist, J. G., Understanding Telecommunications and Lightwave Systems, 2nd
`Edition
`
`Sigfried, S., Understanding Object-Oriented Software Engineering
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`ONES AND ZEROS
`
`Understanding Boolean Algebra,
`Digital Circuits, and the Logic ofSets
`
`John Gregg
`
`IEEE Press Understanding Science & Technology Series
`Dr. Mohamed E. El-Hawary, Series Editor
`
`+IEEE
`
`The Institute of Electrical and Electronics Engineers, lnc.,NewYork
`
`ffiWILEY-
`~INTERSCIENCE
`
`A JOHN WILEY & SONS,INC.,PUBLICATION
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`IEEE Press
`445 Hoes Lane, P.O. Box 1331
`Piscataway, NJ 08855·1331
`
`IEEE Press Editorial Board
`Roger F. Hoyt, Editor in Chief
`s. Furui
`A. H. Haddad
`R. Herrick
`S. Kartalopoulos
`D. Kirk
`
`P. Laplante
`M. Padgett
`W. D. Reeve
`G. Zobrist
`
`J. B. Anderson
`P. M. Anderson
`M. Eden
`M. E. El-Hawary
`
`Kenneth Moore, Director of IEEE Press
`John Griffin, Senior Acquisitions Editor
`Linda Matarazzo, Assistant Editor
`Denise Phillip, Associate Production Editor
`
`Cover design: Caryl Silvers, Silvers Design
`
`Technical Reviewers
`
`Sherif Embabi, Texas A&M University
`Starn Kartalopoulos, Lucent Technologies, Bell Labs Innovations
`Richard S. Muller, University of California, Berkeley
`Kevin D. Taylor, Purdue University at Kokomo
`Neal S. Widmer, Purdue University, EET Department
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`To Susan, without whom this book
`would have been finished a lot sooner.
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`<0 1998THE INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, INC.
`3 Park Avenue,17th Floor,New York, NY 10016-5997
`
`Publishedby John Wiley& Sons, Inc., Hoboken, NewJersey.
`
`No part of this publication may be reproduced, stored in a retrieval system,or
`transmitted in any formor by any means,electronic,mechanical, photocopying,
`recording,scanning,or otherwise, except as permittedunderSection 107or 108 of the
`1976United StatesCopyrightAct, withouteither the prior written permission of the
`Publisher,or authorization throughpaymentof the appropriate per-copyfee to the
`CopyrightClearanceCenter, Inc., 222 Rosewood Drive,Danvers, MA01923, 978-750-
`8400, fax 978-750-4470, or on the web at www.copyright.com. Requests to the Publisher
`for permissionshouldbe addressedto the Permissions Department, John Wiley& Sons,
`Inc., 111 RiverStreet, Hoboken, NJ 07030, (201) 748-6011,fax (201) 748-6008,e-mail:
`permreq@wiley.com.
`
`For general information on our other products and services please contact our Customer
`Care Department withinthe U.S.at 877-762-2974, outsidethe U.S.at 317-572-3993 or
`fax 317-572-4002.
`
`10 9 8 7 6
`
`ISBN 0-7803-3426-4
`
`Library of Congress Cataloging-in-Publication Data
`
`Gregg, John.
`Ones and zeroes : understanding Boolean algebra, digital circuits,
`and the logic of sets / John Gregg.
`p.
`em.
`Includes bibliographical references and index.
`ISBN 0-7803-3426-4
`1. Electronic digital computers-Circuits-Design.
`3. Algebra, Boolean.
`Symbolic and mathematical.
`I. Title.
`TK7888.4.G74 1998
`511.3'24-dc21
`
`2. Logic,
`4. Set theory.
`
`97-34932
`CIP
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`Contents
`
`BEFORE WE BEGIN
`
`xiii
`
`CHAPTER 0 NUMBER SYSTEMS AND COUNTING
`O. 1 Numbers: Some Background
`1
`0.2 The Decimal System: A Closer Look
`3
`0.3 Other Bases
`0.4 Converting from Base 7 to Base 10
`0.5 Converting from Base 10 to Base 7
`10
`0.6 Addition in Other Bases
`12
`0.7 Counting
`0.8 The Binary Number System
`16
`0.9 Combinatoric Examples
`0.9.1 U.S. Presidential Election Example
`0.9.2 Pizza Example
`16
`0.9.3 Hypercube Example
`0.9.4 Binary Trees
`19
`
`14
`
`17
`
`2
`
`5
`7
`
`1
`
`16
`
`CHAPTER 1 THE BASIC FUNCTIONS OF BOOLEAN ALGEBRA:
`AND, OR, AND NOT
`22
`24
`1.1 Boolean Functions
`25
`1.2 AND
`
`vii
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`viii
`
`Contents
`
`27
`
`2S
`
`28
`
`1.2.1 Logical Interpretation of Bits
`26
`1.2.2 Truth Table for AND
`1.2.3 Numbering of Rows in Truth Tables
`28
`1.2.4 The Principle of Assertion
`1.2.5 Some Notational Conventions
`29
`1.2.6 Circuit Symbol for AND
`30
`1.3 OR
`1.3.1 Truth Table for OR
`1.3.2 Circuit Symbol for OR
`33
`1.4 NOT
`1.4.1 Truth Table for NOT
`1.4.2 Circuit Symbol for NOT
`
`31
`
`31
`
`33
`
`34
`
`37
`
`CHAPTER 2 COMBINATIONAL LOGIC
`37
`2.1 AND and NOT
`39
`2.2 Grouping with Parentheses
`47
`2.3 AND and OR with More Than Two Inputs
`2.4 Algebraic Examples of Arbitrary-Input AND and OR
`48
`Functions
`2.5 Truth Tables for Arbitrary-Input AND and OR
`48
`Functions
`2.6 Creating Arbitrary-Input AND and ORGates from the
`50
`Old Two-Input Kind
`2.7 An Arbitrary-Input AND Gate
`2.8 An Arbitrary-Input OR Gate
`
`51
`53
`
`CHAPTER 3 THE ALGEBRA OF SETS AND VENN
`59
`DIAGRAMS
`59
`The Set
`60
`Venn Diagrams
`Set Complementation
`62
`The Null Set
`Subsets and Supersets
`63
`Intersection
`65
`Union
`Example of Union and Intersection
`
`61
`
`62
`
`3.1
`3.2
`3.3
`3.4
`3.5
`3.6
`3.7
`3.8
`
`66
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`Contents
`
`ix
`
`66
`Combinatorics of Venn Diagrams
`3.9
`3.10 Numbering Regions in Venn Diagrams
`68
`3.11 Combinational Logic in Venn Diagrams
`70
`3.12 Set Algebraic Interpretation of Combinational
`71
`Logic
`
`CHAPTER 4 OTHER BOOLEAN FUNCTIONS 77
`
`78
`
`The Constant Functions 0 and 1
`79
`NAND
`81
`NOR
`81
`XOR
`COIN
`84
`4.5.1
`Interesting Properties of XOR and COIN
`
`86
`
`4.1
`4.2
`4.3
`4.4
`4.5
`
`4.6
`
`4.7
`
`90
`
`91
`
`88
`Implication
`4.6.1 Arithmetic Interpretation of Implication
`4.6.2 Algebraic Realization of Implication
`4.6.3 Circuit Symbol for Implication
`91
`92
`4.6.4 Asymmetry of the Implication Function
`4.6.5
`Interpreting Implication of Terms of the Algebra
`of Sets
`93
`96
`Other Complete Systems
`4.7.1 XOR, NOT, and 1 as a Complete System
`4.7.2 NAND as a Complete System
`97
`
`96
`
`CHAPTER 5 REALIZING ANY BOOLEAN FUNCTION WITH
`AND, OR, AND NOT
`101
`
`101
`5.1 Minterms
`5.1.1 Decoder Example
`
`104
`
`5.2 Realizing Any Boolean Function Using
`107
`Minterms
`109
`5.3 Sum-of-Products Expressions
`5.3.1 Realization of Any Boolean Function Using a
`Decoder
`110
`5.4 The Seven-Segment Display
`117
`5.5 Maxterms
`
`111
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`x
`
`Contents
`
`5.6 Realizing Any Boolean Function with Maxterms
`120
`5.7 Product-oF-Sums Expressions
`
`122
`123
`
`5.8 The Three-Input Maiority Voter
`
`CHAPTER 6 MORE DIGiTAL CIRCUITS
`
`126
`
`128
`
`130
`
`126
`6.1 The Multiplexer: Data Versus Control
`6.1.1 AND as Controllable Pass-Through Gate
`6.1.2 Decoder-Based Realization of the
`129
`Multiplexer
`6.1.3 Multiplexer with the Decoder Built In
`6.1.4 Realizing Any Boolean Function with a
`131
`Multiplexer
`6.2 Vectors and Parallel Operations
`137
`6.3 The Adder
`137
`6.3.1 Adding in Base 10
`138
`6.3.2 Adding in Base 2
`6.3.3 The Binary Adder Function
`142
`6.4 The Comparator
`145
`6.5 The ALU
`
`134
`
`139
`
`CHAPTER 7 LAWS OF BOOLEAN ALGEBRA
`
`150
`
`7.1
`7.2
`
`7.3
`7.4
`
`Sets of Axioms
`
`IS3
`154
`
`151
`152
`Perfect Induction
`7.2.1
`Special Properties of 0 and 1
`7.2.2 The Complementation Laws
`ISS
`7.2.3 The Law of Involution
`7.2.4 Commutative Laws of AND and OR
`7.2.5 Distributive Laws of AND and OR
`159
`
`ISS
`IS6
`
`159
`
`Deduction
`
`Allowed Manipulations of Boolean Equations
`160
`7.4.1
`Idempotence
`7.4.2 Absorption Laws
`7.4.3 Associativity Laws
`7.4.4 DeMorgan's Laws
`
`163
`164
`16S
`
`7.5
`
`Principle of Duality
`
`169
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`Contents
`
`xi
`
`178
`
`173
`CHAPTER 8 BOOLEAN LOGIC
`173
`8.1
`Opposition
`174
`8.2
`Consensus
`176
`8.3
`Canonical Form
`8.4
`Blake Canonical Form
`180
`8.5
`Prime Implicants
`8.6
`A New Realization of the Implication
`182
`Function
`182
`Syllogistic Reasoning
`8.7
`Premises That Are Not Implications
`8.8
`187
`Clausal Form
`8.9
`189
`8.10 video Game Example
`8. 11 Equivalent Formulations of Results
`8.12 Specific Results Derived from General
`193
`Results
`8.13 Karnaugh Maps
`8.13.1 Gray Code
`
`195
`195
`
`184
`
`193
`
`APPENDIX A: COUNTING IN BASE 2
`
`203
`
`APPENDIX B: POWERS OF 2
`
`204
`
`APPENDIX C: SUMMARY OF BOOLEAN FUNCTIONS
`
`205
`
`FURTHER READING
`
`213
`
`ANSWERS TO EXERCISES
`
`219
`
`INDEX
`
`277
`
`ABOUT THE AUTHOR
`
`281
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`Before We Begin
`
`This book is primarily about Boolean algebra, a remarkable system of mathemati-
`cal logic through which its inventor, George Boole, sought to characterize all of
`human intelligence in precise symbolic form. He failed, as have all who came
`after him. He did succeed, however, in accomplishing two things. First, he created
`the entire field of symbolic logic, and thereby rescued logic as an active field of
`inquiry from a 2000-year lull that began when Aristotle died. Secondly, many
`decades after his death, Boole's system of symbolic logic was used as the concep-
`tual basis for certain types of electrical relays and switches. We now know these
`types of devices by the name "digital circuits," and they form the basis of all
`modem computing machinery.
`It is important to understand that a working computer consists of both hard-
`ware and software, and the digital circuits discussed in this book comprise only
`the former, Software consists of commands, written by human programmers, that
`reside in a computer's memory. It is the job of the hardware to fetch those
`commands in the correct sequence and act on them. Writing software is by no
`means a trivial exercise, and there are many good books available on the subject
`of software engineering, although this book is not one of them.
`Boole's system and the circuits built on it that are described in these
`pages are surprisingly simple. Furthermore, this book is about logic (often as
`applied to electrical engineering), but not about electrical engineering per see
`You will not find words like watt, ohm, capacitance, or resistance in this
`book. I assume no more than a high-school
`level of familiarity with general
`mathematical concepts.
`
`xiii
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`xiv
`
`Before We Begin
`
`I encourage you to read through the exercises as you read the book. There
`are some interesting wrinkles in them that extend the ideas presented in the text.
`Remember, of course, that the answers are all in the back of the book.
`If this book strikes you as at all interesting, I would also encourage you to
`glance through the reading list in the back. It is categorized by topic and, among
`other things,
`lists many introductory electrical engineering and digital circuits
`texts. These texts tend to cover much of the same material that this book does,
`but in more detail and depth. The reading list also contains several readable and
`fascinating books about mathematics in general and the history of its development.
`
`John Gregg
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`6 M
`
`ore Digital Circuits
`
`In this chapter we will examine some more examples of Boolean algebra applied
`to digital circuit design. These circuits and the decoder introduced in chapter 5
`are some of the fundamental building blocks of complex digital systems including
`computers. In addition to providing insight into the seemingly magical world of
`high technology that surrounds us, an exploration of the design of these circuits
`provides an opportunity to apply the techniques and principles we have learned
`about in previous chapters. The daunting term "digital circuit design" aside, the
`specific, hands-on focus of this chapter ought to be reassuringly down-to-earth
`after the abstractions we have covered up to now. Moreover, the approaches that
`we must take to design such circuits and the new ways in they force us to think
`about Boolean functions will broaden our understanding of Boolean algebra in
`a purely mathematical sense as well.
`
`6.1 THE MULTIPLEXER: DATA VERSUS CONTROL
`
`The first circuit that we will look at in this chapter is somewhat similar in concep(cid:173)
`tion to the decoder in chapter 5. It is called a multiplexer, or MUX for short.
`The multiplexer has one output line and two different kinds of inputs: data inputs
`and control inputs. For a number n (which depends on the desired size of the
`multiplexer) there are n control input bits and 2n data input bits. The control bits
`(collectively called the control signal) choose which of the 2n data input bits is
`to be patched through to the single output line in the same way the decoder input
`signal chose which output line would be 1.
`
`126
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`Section 6.1
`
`The Multiplexer: Data Versus Control
`
`127
`
`For example, a MUX with a control signal consisting of two control bits
`(let us call them Co and CI) would have 22 = 4 data input lines (let us call them
`do, d., d2 , and d3 ) . There is exactly one data input bit for each of the four possible
`combinations of the two control bits, and the particular combination of control
`bits chooses which of the data bits will be sent through to the output line. Thus,
`the single output bit of such a multiplexer will be the same as data input do if
`(co, CI) = (0, 0), d, if (co, CI) = (0, 1), d2 if (co, CI) = (1, 0) and d3 if
`(co, CI) = (I, 1). We do not know or care whether the data input bits (or the
`output bit) is 0 or 1 as long as the bit on the output line is the same as the bit
`on the data line we select with the control signal. If (co, c I) = (1, 0) and d2 =
`1, then the output bit is 1. If (co, CI) = (1,0) and d2 = 0, then the output bit
`is O.Conceptually, the multiplexer functions like the device shown in Figure 6.1.
`
`\o
`
`utput
`
`do-----+-~
`
`d1
`
`--+--I-----t--o
`
`d2
`d3 -+-+-+----+---0
`
`datainputs
`
`Figure 6.1 Conceptually. the multiplexer may be thought to contain an actual switch, under the
`control of the control inputs, that connects one of the data inputs to the output.
`
`The multiplexer has many uses for electrical engineers. It may be thought
`of as a controllable data path. A particular combination of control bits may func(cid:173)
`tion as a command to let certain data through while withholding other data. Later
`we will see how this controllable aspect of the multiplexer allows it to be used
`to construct the number-crunching heart of a computer's central processing unit
`(CPU).
`How can we build the multiplexer out of our favorite three functions? We
`could simply treat a four-data, two-control MUX as a Boolean function with six
`input bits and one output bit, write out its truth table, and derive a mintenn or
`maxterm realization of it. However, at 26 = 64 lines long, a six-input truth table
`would be unwieldy, to say the least. Fortunately, there is a way of thinking about
`this problem that allows us to break it down into manageable parts.
`Although the data and control lines are all just bits, there is an important
`conceptual difference between them. The control bits never appear as output.
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`128
`
`Chapter 6
`
`More Digital Circuits
`
`Rather, they steer the whole circuit inside, controlling its operation. The data
`bits, however, are simply herded like cattle through the circuit. They are the raw
`material that is processed or filtered by the circuit under the direction of the
`control signal. The somewhat abstract distinction between the two different kinds
`of data, data-as-data and data-as-control, is crucial to digital circuit design and
`is the key to the construction of the multiplexer.
`
`6. 1. 1 AND as Controllable Pass-Through Gate
`
`To understand this distinction, we will take a momentary detour away from
`the multiplexer and revisit the simple two-input AND gate (Fig. 6.2).
`
`x
`
`y
`
`Figure 6.2 x 1\ y.
`
`By arbitrarily deciding that one of the AND gate's inputs bits (x) is a control
`input and the other of its inputs (y) is a data input, we find that we have created
`a simple controllable data path in which y is the bit being controlled and x is the
`bit doing the controlling (Fig. 6.3).
`
`x ~Olinput
`
`y-----.....
`
`\data input
`
`Figure 6.3
`
`x 1\ y, with x arbitrarily designated the control
`
`input and y the data input.
`
`How does x exert control over the output? Look at the truth table for AND,
`paying particular attention to the rows in which x = 0 (Table 6.1). Note that
`when x = 0, the output of the AND gate is 0 as well. However, consider what
`happens when x = 1 (Table 6.2).
`When x = 1, the output bit becomes whatever y is. Thus the AND gate acts
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`Section 6.1
`
`The Multiplexer : Data Versus Control
`
`129
`
`TABLE 6.1
`
`TABLE 6.2
`
`I~
`<I
`
`y o
`
`x o
`
`as a controllable gate for data input y. If x = 0, the gate is shut off like a faucet
`and only 0 comes out no matter what y is. If x = I, the gate simply passes y
`through unchanged. When an input is used to control another input in this way,
`we often speak, for example, of x enabling y (in the case in which x = I) or
`disabling y (as in the case in which x = 0). Because AND is symmetric, we
`could just as easily have declared y to be the control bit and x to be the data bit.
`It is just a matter of perspective as a review of the truth table for AND will show.
`We will employ this "controllable" aspect of AND to realize our multiplexer.
`
`6.1.2 Decoder-Based Realization of the
`Multiplexer
`
`A possible approach to the design of the multiplexer would be to feed the
`multiplexer's control signals into a decoder. Each output line from the decoder
`could then be ANDed with a different data bit, and all the resulting bits ORed
`together. This solution is shown in Figure 6.4.
`For each particular combination of control bits, only one of the decoder's
`output lines will be 1: the other three will be O. The "on" decoder output line
`will then enable only the data line that it gets ANDed with; the other three data
`lines will be ANDed with O's, and thus be disabled. Finally, the OR gate will
`receive as input three O's and the enabled data bit. It will pass the data through,
`since ORing any bit with any number of O's has no effect; the data bit is simply
`passed along unchanged as the output bit of the OR. Thus we have achieved our
`desired goal: we can select anyone of the four data lines with our two control
`lines, and the output of the entire circuit is the bit being carried on the selected
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`130
`
`Chapter 6
`
`More Digital Circuits
`
`do- -t--- - - - - ---1
`
`Figure 6.4 Decoder-based realization of 4-data, 2-control multiplexer.
`
`data line. For example, if (co, CI) = (0, 1), then whatever data input d, is will
`appear on the output line as shown in Figure 6.5.
`
`do-.......-----~
`
`Figure 6.5 Decoder-based realization of 4-data, 2-control multiplexer given (0, 1) as control input.
`
`However, each output line ofa decoder is realized by the minterm ofthe partic(cid:173)
`ular combination of input bits that makes that output line 1. Thus, the above realiza(cid:173)
`tion of the multiplexer could be drawn more specifically as shown in Figure 6.6.
`
`6. 1.3 Multiplexer with the Decoder Built In
`
`In the decoder-based realization of the multiplexer described in Section 6.1.2,
`each input data bit goes through two levels of ANDs before it gets to the final
`OR. Thinking literally about what the multiplexer does, however, we can combine
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`Section 6.1
`
`The Multiplexer: Data Versus Control
`
`131
`
`do--+------~
`
`d1--+--..,II'---~
`
`o
`
`Figure 6.6 Decoder-based realization of 4-data, 2-control multiplexer given (0, I) as control input
`with realization of decoder shown.
`
`the logic in the decoder with the rest of the multiplexer circuit, thereby simplifying
`things a bit.
`We want a circuit that yields do as output when Co AND CI, d, when Co
`AND c.. d2 when Co AND c" and d3 when Co AND CI. Just writing it out in this
`way points strongly to the final function. Indeed, the circuit we are looking for
`is realized in the following expression:
`(do /\ Co /\ CI) V (d, /\ Co /\ CI) V (d2 /\ Co /\ CI) V u,». Co /\ c.).
`We simply ANDed each data input with the particular combination of control
`inputs that we wanted to select that data input and ORed all the results together.
`Effectively, this realization of the multiplexer has a decoder built in. The different
`combinations of Co and C. ensure that only one of the four ORed together expres(cid:173)
`sions will ever be 1 at any given time. For example, if (co, Cl) = (0, 1), of the
`four expressions above that are ORed together, all would be 0 except the second,
`(d, /\ Co /\ Cl). The combination of (co, CI) = (0, 1) would enable the d, in
`this expression, which would be passed alone to the OR along with three O's.
`The output of the entire expression would then be the result of the three O's ORed
`with d., as shown in Figure 6.7.
`
`6. 1.4 Realizing Any Boolean Function with a
`Multiplexer
`
`In chapter 5 we learned how to use a decoder to realize any Boolean function
`in addition to the minterm and maxterm realization methods. Now we will exam(cid:173)
`ine a way of realizing any Boolean function using a multiplexer.
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`132
`
`Chapter 6
`
`More Digital Circuits
`
`do
`
`a,
`
`d2
`
`d3
`
`Co
`C1
`
`Co
`c1
`
`Co
`c1
`
`Co
`c1
`
`(co' C1) = (0,1)
`
`d1
`
`0
`
`Figure 6.7
`
`Simpler realization of 4-data, 2-control multiplexer given (0, I) as control input.
`
`Consider the three-bit Boolean function shown in Table 6.3. Instead of using
`mintenns (or in this case, more likely maxtenns) to realize this function, we can
`use a three-control, eight-data multiplexer. We simply feed the inputs of the
`desired function into the control inputs of the multiplexer so that each combination
`of input bits (x, y, z) chooses a different one of the multiplexer's eight data
`lines. Then we "hardwire'
`the data lines to be the proper output bits for each
`combination of inputs bits exactly as they appear in the output column of the
`truth table, resulting in the circuit shown in Figure 6.8.
`The data lines shown in the multiplexer in Figure 6.8 do not have variable
`inputs. They are hardwired, meaning that they are permanently set to be a particu(cid:173)
`lar value. Specifically, each data input bit is set to be the desired output from
`the function for a different combination of inputs. For instance, according to the
`
`TABLE 6.3
`
`x
`
`0
`
`0
`
`0
`
`0
`
`I
`
`I
`
`I
`
`I
`
`y
`
`0
`
`0
`
`I
`
`I
`
`0
`
`0
`
`I
`
`I
`
`z
`
`0
`
`1
`
`0
`
`I
`
`0
`
`I
`
`0
`
`I
`
`I
`
`0
`
`0
`
`I
`
`0
`
`I
`
`I
`
`I
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`Exercise 6.1
`
`133
`
`MUX
`
`I
`
`x
`
`I
`
`y
`
`I
`
`z
`
`o o
`
`o
`
`Figure 6.8
`
`8-data, 3-control multiplexer "hardwired" to realize a panicular three-input function.
`
`truth table, when the function's inputs are (x, y, z) = (1, 0, 1), the output of the
`function should be 1. In the circuit shown in Figure 6.8, when (x, y, z) = (1, 0,
`1), data line five is selected to be the output from the multiplexer. We have
`hardwired data line five always to be a l , so when (x, y, z) = (1, 0, 1), the output
`of the circuit is a 1. This method can be used for any Boolean function. Given
`any n-bit function, its truth table will be 2n bits long, and we would need an n(cid:173)
`control, 2n-data multiplexer to realize it in this way.
`This is a rather unintelligent, or "brute force," use of a multiplexer. By
`hardwiring the data inputs just the way we want them for the particular function
`we want to realize, we have just trained the multiplexer to memorize the truth
`table and look up the output bit for the row specified by a given value of the
`control signal. In this sense, however, we have implemented a sort of primitive
`computer memory that allows us access to the bit stored at a given memory
`address as specified by the multiplexer's control signal. It is, however, a read(cid:173)
`only memory; we cannot change the bit at a given address, we can only read it.
`
`EXERCISE 6. 1
`
`I. Draw a circuit diagram and write the corresponding algebraic expression for a three(cid:173)
`control, eight-data multiplexer.
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`134
`
`Chapter 6
`
`More Digital Circuits
`
`2. Derive full maxterm and mintenn realizations of a one-control, two-data multiplexer.
`3. Recallingour interpretation of the AND gate as a controllablepass-through gate, exam(cid:173)
`ine and describe in your own words how the two-input OR, NAND, NOR, XOR, and
`COIN behave when one input is considered a control input and the other a data input.
`What is the effect on the data input when the control input is turned on and off?
`
`6.2 VECTORS AND PARALLEL OPERATIONS
`
`Thus far we have dealt only with data that consisted of a single bit. The multiplex(cid:173)
`ers we have looked at take individual data bits in and switch between them on
`the basis of the control signal. Sometimes, however, we want to switch between
`binary numbers that are many bits long. This is especially true in computer circui(cid:173)
`try in which data is almost always considered in groups of 8, 16, 32, or more
`bits at a time.
`For instance, suppose we wanted to build a multiplexer that selected one of
`four eight-bit numbers on the basis of a control signal. Because there are still
`only four things we are choosing among, we only need two bits of control to
`select one of them uniquely, even though each data input consists of more than
`one bit. Conceptually, this case is no different from the single-bit data case.
`However, at the logic gate level, it is slightly more complex.
`Each of the four data input signals is to be eight bits wide, as is the output
`signal. That is, each of these data paths consists of eight bits going side by side
`into (or out of) the multiplexer. Bits that travel
`together and are meant to be
`interpreted as a single multi-bit number are bits that are taken in parallel (this
`parallelism of data transmission is not to be confused with that meant when we
`speak of parallel-processing computers).
`We describe data paths as being a certain number of bits' 'wide" in the same
`sense that we speak of highways being four lanes wide. The width of the data path
`refers to its capacity in parallel bits. In diagrams of digital circuits, we indicate sin(cid:173)
`gle-bit paths with the single arrow or the line that we have been using all along, and
`indicate multi-bit data paths with double-wide arrows. Sometimes a slash across
`the data path tells how many bits in parallel the data path accommodates.
`Sometimes values consisting of many bits taken in parallel are known as
`vectors. Furthermore, single bits of data are usually represented with lowercase
`letters, while uppercase letters indicate multi-bit vectors. A high-level diagram
`of the multiplexer with eight-bit data paths is shown in Figure 6.9.
`Such a diagram is called a block diagram. It depicts a circuit abstractly as
`a block or box, as well as its inputs and outputs, but does not bother with the
`details of the circuit's implementation in terms of AND, OR, and NOT gates.
`We will use block diagrams throughout this chapter to illustrate the different
`common circuits we will discuss.
`How would we implement this vector-input multiplexer circuit using the
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`Section 6.2
`
`Vectors and Parallel Operations
`
`13S
`
`°1
`
`~
`
`~
`
`~
`
`~
`
`\
`
`\
`
`\
`
`\
`
`MUX
`
`~
`
`\
`
`'-
`,
`
`output
`
`".
`
`2 '
`
`Figure 6.9
`
`4-data, 2-control multiplexer in which data paths are eight-bit wide vectors.
`
`circuits we already know about? The bits in a particular data vector only interact
`with the corresponding bits in other data vectors and not with each other. There(cid:173)
`fore, to build a multiplexer with four eight-bit vectors as data inputs, we would
`build eight multiplexers that each take four single bits as data inputs and feed
`each of these eight multiplexers the same control signal. Each of the eight multi(cid:173)
`plexers (we will call them MUXO through MUX7) handles one bit for the multi(cid:173)
`bit multiplexer. MUXO will take the first bit of each of the four eight-bit input
`data vectors as its four data inputs, MUX 1 will take the second bit of each eight(cid:173)
`bit vector as its inputs, and so on. Each of the eight multiplexers produces a
`single output bit. Taken together as an eight-bit number, these eight bits are the
`desired result of our eight-bit multiplexer.
`The fourth such single-bit-input multiplexer in such an arrangement, MUX3,
`is shown in Figure 6.10. Note that it takes as its four single-bit inputs the fourth
`bit of each of the four eight-bit data vectors, Do-D3 • The bit it produces as output
`is taken to be the fourth bit in the eight-bit output vector of the vector multiplexer.
`Constructing multi-bit circuits in this way from single-bit circuits (or multi(cid:173)
`bit circuits from smaller-capacity multi-bit circuits) is known as bit slicing. All
`vector operations are split apart into single-bit operations that are carried out in
`parallel, and the single-bit results are put together in parallel to form an output
`vector. Each single-bit circuit constitutes a slice of the final multi-bit circuit.
`Any Boolean operation we have performed on single bits also can be per(cid:173)
`formed on vectors in parallel. For example, to form an eight-bit vector that is
`the result of a parallel AND performed on two eight-bit vectors, simply AND
`the first bit of the two vectors together to form the first bit of the result, then
`AND the second bit of the two vectors together to form the second bit of the
`result, and so on.
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`136
`
`Chapter 6
`
`More Digital Circuits
`
`0 - (cid:173)
`0====
`
`0 - (cid:173)
`1====
`
`0 - (cid:173)
`2====
`
`0 - (cid:173)
`3====
`
`Figure 6.10 Block diagram of the circuit that produces the fourth output bit of the output vector
`from a 4-data/2-control multiplexer that operates on eight-bit data vectors.
`
`It is important to realize that by allowing ANDs and other Boolean functions
`to perform parallel operations, we are not redefining them as much as we are
`using a shorthand so we do not have to write out the more confusing reality of
`the situation in which there are several single-bit path AND gates operating in
`parallel as shown in Figure 6.11.
`
`R =
`
`4
`
`A B
`
`Figure 6.11 Four-bit vector AND: vector representationand single-bit reality.R is the output vector
`(R for "result").
`
`A simple Boolean operation performed in parallel on each bit in multi-bit
`vectors is known as a bitwise operation. Figure 6.11 shows a circuit that performs
`a four-bit bitwise AND. Any time we use diagrams in which double arrows
`(multi-bit vectors) are shown going into and coming out of a Boolean gate, it is
`understood that the output vector is the result of the Boolean operation being
`performed on the input vector(s) in a bitwise or parallel fashion.
`
`IPR2017-01819
`NVIDIA v. Polaris
`Polaris Ex. 2005
`
`

`

`Section 6.3
`
`The Adder
`
`6.3 THE ADDER
`
`137
`
`How could we use the techniques we have learned to create a function that would
`add two eight-bit numbers in base 21 Such a function would have to have enough
`input bits to accommodate both eight-bit input numbers, or 16 bits. Just to write
`the truth table for such a function would involve 2 16 = 65,536 lines.
`How many output bits would the function have? To answer this, we need
`to know the largest number that can result from the addition of two eight-bit
`numbers. The largest eight-bit number is 111111112 = 255, so the largest sum
`of two eight-bit numbers we could possibly have is 255 + 255 = 510, or
`1111111102 , a nine-bit number. So the adder must have nine output bits (each
`a separate function itself), each having a truth table with 65,536 lines-hardly
`an inviting prospect. However, if we look closely at the mechanics of adding
`base-2 numbers together, we will find an easier way to build our adder.
`To create a Boolean function that adds two base-2 numbers together, we
`must develop an algorithm for adding in base 2. That is, we need to determine
`a specific sequence of steps for adding two base-2 numbers. It is useful at this
`point to take a hard look at the method we use when we add two base-l 0 numbers
`together.
`
`6.3. 1 Adding in B