Unformatted text preview:

Lecture 3:GatesCS105: Great Insights in Computer ScienceMichael L. Littman, Fall 2006Name These GatesAB CDELast Times• Defined “and”, “or”, “not” gates by their truth tables.• Explained how to construct them out of switches and relays.• Gave an example of their use in the Nimbot.• This time: Demonstrate their generality by providing more complex examples.• But first... how do you make a bit?How to Make a Gate• switches/relays• hydraulic valves• tinkertoys• silicon: semiconductors/transistors• soap bubble• DNA• quantum material• optics• nanotubes• neurons• dominoes• legos/marblesMovieNOT Gate (v3)0101Or Gate (v4)010101Release bottom row first Wire, transmitting bits (v1)0011Could It Work?• My domino “or” gate requires 24 dominoes.• The first Pentium processor had 3.3M transistors, or roughly 800K gates.• So, perhaps 19M dominoes needed.• World record for domino toppling: 4M.• Oh, and the Pentium did its computations 60M times a second, whereas dominoes might require a week to set up once. OR4A Few New GatesA BANDCANDdef AND3(A, B, C):x = A and By = x and Creturn yAND3A BORCORdef OR4(A, B, C,D):return (A or B) or (C or D)DORyIFTHENELSE5control bitchar1char2group of 5 bits eachANDANDORNOT00ANDANDORNOT11ANDANDORNOT22ANDANDORNOT33ANDANDORNOT440 1 2 3 4IFTHENELSE5Textual Versiondef IFTHENELSE5(bit, char1, char2): return [(char1[0] and bit) or (char2[0] and not bit), (char1[1] and bit) or (char2[1] and not bit), (char1[2] and bit) or (char2[2] and not bit), (char1[3] and bit) or (char2[3] and not bit), (char1[4] and bit) or (char2[4] and not bit)]• Takes 11 bits as input and makes 5 as output. For clarity, the bits are grouped.•char1[0] means the leftmost bit of the group called “char1”.• “bit” selects char1 (True) or char2 (False).Why “Or”, “And”, “Not”?• In addition to being familiar, these gates are “universal”. That is, all other logical functions can be expressed using these building blocks.• How many distinct logic functions on 2 bits?Some Truth TablesABCFalseFalseFalseFalseTrueFalseTrueFalseFalseTrueTrueFalseABCFalseFalseFalseFalseTrueFalseTrueFalseFalseTrueTrueTrueABCFalseFalseFalseFalseTrueFalseTrueFalseTrueTrueTrueFalseABCFalseFalseFalseFalseTrueFalseTrueFalseTrueTrueTrueTrueABCFalseFalseFalseFalseTrueTrueTrueFalseFalseTrueTrueFalseABCFalseFalseFalseFalseTrueTrueTrueFalseFalseTrueTrueTrueABCFalseFalseFalseFalseTrueTrueTrueFalseTrueTrueTrueFalseABCFalseFalseFalseFalseTrueTrueTrueFalseTrueTrueTrueTrueMore Truth TablesABCFalseFalseTrueFalseTrueFalseTrueFalseFalseTrueTrueFalseABCFalseFalseTrueFalseTrueFalseTrueFalseFalseTrueTrueTrueABCFalseFalseTrueFalseTrueFalseTrueFalseTrueTrueTrueFalseABCFalseFalseTrueFalseTrueFalseTrueFalseTrueTrueTrueTrueABCFalseFalseTrueFalseTrueTrueTrueFalseFalseTrueTrueFalseABCFalseFalseTrueFalseTrueTrueTrueFalseFalseTrueTrueTrueABCFalseFalseTrueFalseTrueTrueTrueFalseTrueTrueTrueFalseABCFalseFalseTrueFalseTrueTrueTrueFalseTrueTrueTrueTrueUniversal Gate• Take two inputs, A and B.• Take four more inputs defining what the gate should output for each combination of A and B.• Output the right bit!OR4A Bd00d01d10d11NOTAND3NOTAND3AND3AND3UNIV2Textual Versiondef UNIV2(A, B, d00, d01, d10, d11):w = AND3(not A, not B, d00)x = AND3(not A, B, d01)y = AND3(A, not B, d10)z = AND3(A, B, d11)return OR4(w,x,y,z)Bit Equalitydef equal(bit1, bit2): return ((bit1 and bit2) or (not bit1 and not bit2))equalORbit1bit2NOTANDNOTAND• Output True if either bit1 = True and bit2 = True, or bit1 = False and bit2 = False (they are equal).Group Equality• Now that we can test two bits for equality, we would like to test a group of 5 bits for equality (two alphabetic characters).• Two groups are equal if each of their bits are equal: bit 0 = bit 0, bit 1 = bit 1, etc.def equal5(char1, char2): return (equal(char1[0],char2[0]) and (equal(char1[1],char2[1]) and (equal(char1[2],char2[2]) and (equal(char1[3],char2[3]) and equal(char1[4],char2[4])))))Equal5 DiagramequalORANDANDANDANDchar1ANDchar2equalORANDANDANDANDequalORANDANDANDANDequalORANDANDANDANDequalORANDANDANDANDANDANDAND0123401234equal5EQUALEQUALEQUALEQUALEQUALGates in EQUAL5• 10 inputs (2 groups of 5), 1 output bit.• The equal5 gate consists of- 4 “and” gates- 5 “equal” gates- 2 “and”, 2 “not”, 1 “or” (5 total)- Total = 29 gatesGates: Could Create• And-k: k ins, 1 out (True if all ins are True)• Or-k: k ins, 1 out (True if any ins are True)• Ifthenelse-k: 1 control bit in, k then ins, k else ins, k outs (outs match then if control bit is True, else otherwise)• Equal-k: 2 k-bit blocks in, 1 out (True if blocks same)• Universal-k: 2k table in, k control bits in, 1 out (equal to the value in the table specified by the control bits)Counting Boolean Functions• With 2 input bits, there are 22=4 rows of the truth table (combinations of truth assignments to these variables).• Each row can take an output of true or false, for a total of 24=16 tables.•For n inputs: 22n.n22n01142163256465536542949672966718446744073709551616340282366920938463463374607431768211456Can Represent Them All• Almost all multi-input functions require an enormous number of logic gates.• However, the most useful ones can be represented succinctly.Next Time• Read Hillis, remainder of Chapter


View Full Document

Rutgers University CS 105 - Gates

Download Gates
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Gates and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Gates 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?