CS231: Computer Architecture IAnnouncementsReview/DiscussionBoolean Operations & Circuit AnalysisBoolean valuesFunctionsBasic Boolean operationsBoolean expressionsPrimitive logic gatesExpressions and circuitsCircuit analysisExampleSlide 13Slide 14Slide 15Slide 16Slide 17Slide 18Circuit analysis summaryBoolean AlgebraExpression simplificationFormal definition of Boolean algebraSimplification with axiomsSlide 24Slide 25Slide 26Slide 27The complement of a functionComplementing a function algebraicallySlide 30Slide 31Standard forms of expressionsMintermsSum of minterms formThe dual idea: products of sumsMaxtermsProduct of maxterms formSlide 38Minterms and maxterms are relatedConverting between standard formsSlide 41Slide 42SummaryCS231: Computer Architecture IFriday, February 1, 2008CS 231 - Computer Architecture I2Announcements•Homework 1 is due Monday @ 5:00pm–Turn in to TA Office 0212 SC (In Basement)–Slide it under the door! NOT Outside in bins!!!–Late homeworks accepted with penalty•By Tuesday @ 5:00pm: -10%•By Wednesday @ 5:00pm: -20%•No homework accepted after this. Solutions will be posted.–Mallard Quizzes•Posted after Monday and Wednesday classes•Due before class on Wednesday and Friday–Use Newsgroup and Office Hours for help with assignmentsCS 231 - Computer Architecture I3Review/DiscussionThis review consists of some of the more important lecture slides and new example problems with a walkthrough of the solutions.•Boolean Operations–Functions–Operators–Truth Tables–Logic Gates–Expression and Circuits•Circuit Analysis•Boolean Algebra–deMorgans Laws•Maxterms/MintermsBoolean Operations&Circuit AnalysisCS 231 - Computer Architecture I5Boolean values•Earlier, we used electrical voltages to representtwo discrete values 1 and 0, from which binary numberscan be formed.•It’s also possible to think of voltages as representingtwo logical values, true and false.•For simplicity, we often still write digits instead:–1 is true–0 is false•We will use this interpretation along with special operations to design functions and hardware for doing arbitrary computations.Volts1.80TrueFalseCS 231 - Computer Architecture I6Functions•Computers take inputs and produce outputs, just like functions in math!•Mathematical functions can be expressed in two ways:•We can represent logical functions in two analogous ways too:–A finite, but non-unique Boolean expression. –A truth table, which will turn out to be unique and finite.x y f (x,y)0 0 0… … …2 2 6… … …23 41 87… … …f(x,y) = 2x + y= x + x + y= 2(x + y/2)= ...An expression isfinite but not uniqueA function table isunique but infiniteCS 231 - Computer Architecture I7Basic Boolean operations •There are three basic operations for logical values.x y xy0 0 00 1 01 0 01 1 1x y x+y0 0 00 1 11 0 11 1 1x x’0 11 0AND (product)of two inputsOR (sum) of two inputsNOT(complement)on one inputxy, or x-y x + y x’Operation:Expression:Truth table:CS 231 - Computer Architecture I8Boolean expressions•We can use these basic operations to form more complex expressions:f(x,y,z) = (x + y’)z + x’•Some terminology and notation:–f is the name of the function.–(x,y,z) are the input variables, each representing 1 or 0. Listing the inputs is optional, but sometimes helpful.–A literal is any occurrence of an input variable or its complement. The function above has four literals: x, y’, z, and x’.•Precedences are important, but not too difficult.–NOT has the highest precedence, followed by AND, and then OR.–Fully parenthesized, the function above would be kind of messy:f(x,y,z) = (((x +(y’))z) + x’)CS 231 - Computer Architecture I9Primitive logic gates•Each of our basic operations can be implemented in hardware using a primitive logic gate.–Symbols for each of the logic gates are shown below.–These gates output the product, sum or complement of their inputs.Logic gate:AND (product)of two inputsOR (sum) of two inputsNOT(complement)on one inputxy, or x-y x + y x’Operation:Expression:CS 231 - Computer Architecture I10Expressions and circuits•Any Boolean expression can be converted into a circuit by combining basic gates in a relatively straightforward way.•The diagram below shows the inputs and outputs of each gate.•The precedences are explicit in a circuit. Clearly, we have to make sure that the hardware does operations in the right order!(x + y’)z + x’CS 231 - Computer Architecture I11Circuit analysis•Circuit analysis involves figuring out what some circuit does.–Every circuit computes some function, which can be described with Boolean expressions or truth tables.–So, the goal is to find an expression or truth table for the circuit.•The first thing to do is figure out what the inputs and outputs of the overall circuit are.–This step is often overlooked!–The example circuit here has three inputs x, y, z and one output f.ExampleCircuit Analysis – Try to find a Boolean expression for the function fExampleCircuit AnalysisxxyzzyExampleCircuit AnalysisxxyzzY’x’z’yExampleCircuit AnalysisxxyzzY’x’z’y(x + y’ )ExampleCircuit AnalysisxxyzzY’x’z’y(x + y’ )(x + y’ ) z(x’ y z’ )ExampleCircuit AnalysisxxyzzY’x’z’y(x + y’ )(x + y’ ) z(x’ y z’ )(x + y’ ) z + (x’ y z’ )ExampleCircuit AnalysisxxyzzY’x’z’y(x + y’ )(x + y’ ) z(x’ y z’ )(x + y’ ) z + (x’ y z’ )f(x,y,z) = xz + y’z + x’yz’CS 231 - Computer Architecture I19Circuit analysis summary•After finding the circuit inputs and outputs, you can come up with either an expression or a truth table to describe what the circuit does.•You can easily convert between expressions and truth tables.Find the circuit’sinputs and outputsFind a Booleanexpressionfor the circuitFind a truth tablefor the circuitBoolean AlgebraCS 231 - Computer Architecture I21Expression simplification•Normal mathematical expressions can be simplified using the laws of algebra•For binary systems, we can use Boolean algebra, which is superficially similar to regular algebra•There are many differences, due to–having only two values (0 and 1) to work with–having a complement operation–the OR operation is not the same as additionCS 231 - Computer Architecture I22Formal definition of Boolean algebra•A Boolean algebra requires–A set of elements B, which needs at least two elements (0 and 1)–Two binary (two-argument) operations OR and AND–A
View Full Document
Unlocking...