Additional gatesAdditional Boolean operationsNANDs are special!Making NAND circuitsConverting to a NAND circuitConverting to NAND, concludedNOR gatesXOR gatesMore XOR tidbitsXNOR gatesDesign considerations, and where they come fromPrime implicantsEssential prime implicantsCovering the other mintermsPractice K-map 2Solutions for practice K-map 2I don’t care!Example: Seven Segment DisplaySlide 19Practice K-map 3Solutions for practice K-map 3SummaryBasic circuit designDesign example: Comparing 2-bit numbersStep 1: How many inputs and outputs?Step 2: Functional specificationStep 3: Simplified Boolean expressionsStep 4: Drawing the circuitsTesting this in LogicWorksExample wrap-upSlide 3101/14/19 Additional Gates and Decoders 1Additional gates•We’ve already seen all the basic Boolean operations and the associated primitive logic gates.•There are a few additional gates that are often used in logic design.–They are all equivalent to some combination of primitive gates.–But they have some interesting properties in their own right.01/14/19 Additional Gates and Decoders 2Additional Boolean operations x y (xy)’0 0 10 1 11 0 11 1 0x y (x+y)’0 0 10 1 01 0 01 1 0 NAND(NOT-AND) NOR(NOT-OR) XOR(eXclusive OR)(xy)’ = x’ + y’(x + y)’ = x’ y’ x y = x’y + xy’Operation:Expressions:Truth table:Logic gates:x y xy0 0 00 1 11 0 11 1 001/14/19 Additional Gates and Decoders 3NANDs are special!•The NAND gate is universal: it can replace all other gates!–NOT–AND–OR(xx)’ = x’ [ because xx = x ]((xy)’ (xy)’)’ = xy [ from NOT above ]((xx)’ (yy)’)’ = (x’ y’)’ [ xx = x, and yy = y ]= x + y [ DeMorgan’s law ]01/14/19 Additional Gates and Decoders 4Making NAND circuits•The easiest way to make a NAND circuit is to start with a regular, primitive gate-based diagram.•Two-level circuits are trivial to convert, so here is a slightly more complex random example.01/14/19 Additional Gates and Decoders 5Converting to a NAND circuit•Step 1: Convert all AND gates to NAND gates using AND-NOT symbols, and convert all OR gates to NAND gates using NOT-OR symbols.01/14/19 Additional Gates and Decoders 6Converting to NAND, concluded•Step 2: Make sure you added bubbles along lines in pairs ((x’)’ = x). If not, then either add inverters or complement the input variables.01/14/19 Additional Gates and Decoders 7NOR gates•The NOR operation is the dual of the NAND.•NOR gates are also universal.•We can convert arbitrary circuits to NOR diagrams by following a procedure similar to the one just shown:–Step 1:Convert all OR gates to NOR gates (OR-NOT), and all AND gates to NOR gates (NOT-AND).–Step 2:Make sure that you added bubbles along lines in pairs. If not, then either add inverters or complement input variables.01/14/19 Additional Gates and Decoders 8XOR gates•A two-input XOR gate outputs true when exactly one of its inputs is true:•XOR corresponds more closely to typical English usage of “or,” as in “eat your vegetables or you won’t get any pudding.” •Several fascinating properties of the XOR operation:x y xy0 0 00 1 11 0 11 1 0x y = x’ y + x y’x 0 = x x 1 = x’x x = 0 x x’ = 1x (y z) = (x y) z [ Associative ]x y = y x [ Commutative ]01/14/19 Additional Gates and Decoders 9More XOR tidbits•The general XOR function is true when an odd number of its arguments are true.•For example, we can use Boolean algebra to simplify a three-input XOR to the following expression and truth table.•XOR is especially useful for building adders (as we’ll see on later) and error detection/correction circuits.x (y z)= x (y’z + yz’) [ Definition of XOR ]= x’(y’z + yz’) + x(y’z + yz’)’ [ Definition of XOR ]= x’y’z + x’yz’ + x(y’z + yz’)’ [ Distributive ]= x’y’z + x’yz’ + x((y’z)’ (yz’)’) [ DeMorgan’s ]= x’y’z + x’yz’ + x((y + z’)(y’ + z)) [ DeMorgan’s ]= x’y’z + x’yz’ + x(yz + y’z’) [ Distributive ]= x’y’z + x’yz’ + xyz + xy’z’ [ Distributive ]x y z xyz0 0 0 00 0 1 10 1 0 10 1 1 01 0 0 11 0 1 01 1 0 01 1 1 101/14/19 Additional Gates and Decoders 10XNOR gates•Finally, the complement of the XOR function is the XNOR function.•A two-input XNOR gate is true when its inputs are equal:x y (xy)’0 0 10 1 01 0 01 1 1(x y)’ = x’y’ + xy01/14/19 Additional Gates and Decoders 11Design considerations, and where they come from•Circuits made up of gates, that don’t have any feedback, are called combinatorial circuits–No feedback: outputs are not connected to inputs–If you change the inputs, and wait for a while, the correct outputs show up.•Why? Capacitive loading: –“fill up the water level” analogy.•So, when such ckts are used in a computer, the time it takes to get stable outputs is important.•For the same reason, a single output cannot drive too many inputs–Will be too slow to “fill them up”–May not have enough power•So, the design criteria are:–Propagation delay (how many gets in a sequence from in to out)–Fan-out–Fan-in (Number of inputs to a single gate)June 17, 2002 Basic circuit analysis and design 12Prime implicants•The challenge in using K-maps is selecting the right groups. If you don’t minimize the number of groups and maximize the size of each group: –Your resulting expression will still be equivalent to the original one.–But it won’t be a minimal sum of products.•What’s a good approach to finding an actual MSP?•First find all of the largest possible groupings of 1s.–These are called the prime implicants.–The final MSP will contain a subset of these prime implicants.•Here is an example Karnaugh map with prime implicants marked:Y1 1 0 01 1 0 00 1 1 0XW0 0 1 1ZJune 17, 2002 Basic circuit analysis and design 13Essential prime implicants•If any group contains a minterm that is not also covered by another overlapping group, then that is an essential prime implicant.•Essential prime implicants must appear in the MSP, since they contain minterms that no other terms include.•Our example has just two essential prime implicants:–The red group (w’y’) is essential, because of m0, m1 and m4.–The green group (wx’y) is essential, because of m10.Y1 1 0 01 1 0 00 1 1 0XW0 0 1 1ZJune 17, 2002 Basic circuit analysis and design 14Covering the other minterms•Finally pick as few other prime implicants as necessary to
View Full Document
Unlocking...