Class Note for ENGIN 112 at UMass(14)
Class Note for ENGIN 112 at UMass(14)
Popular in Course
Popular in Department
This 20 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 14 views.
Reviews for Class Note for ENGIN 112 at UMass(14)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
College of Engineering University of Massachusetts Amherst ENGIN 112 Introduction to Electrical and Computer Engineering Fall 2008 Discussion A 4 Canonical Forms I Logic Gates 0 Binary logic is based on three operations AND OR and NOT We ve discussed the logic gates that implement those operations 0 Three other types of gates are commonly used in design NAND not AND NOR not OR and XOR exclusive OR 0 To describe the operation of these gates let X and y denote input bits and let 2 denote the output bit NAND The operation quotX NAND y is equal to z is denoted by x yz This operation is de ned by x y x 39y and has truth table x y zx y O O 1 NAND gate symbol 0 1 1 1 O 1 X 1 1 O QR NOR The operation quotX NOR y is equal to z is denoted by X yz This operation is de ned by x 4 y x y and has truth table NOR gate symbol x y zxby O O 1 O 1 O 1 O O 1 1 O X 30 2 y XOR The operation quotx XOR y is equal to z is denoted by X eayz This operation is de ned by x 69 y x y y x and has truth table zx 9y XOR gate symbol HHOOX HOHOV OHHO All of these gates can be de ned for more than two inputs X1 1 X2 1 1XN X1 39X2 39 39XN X1 X2 XN X1 X2WXN x1 EB x2 EB EB XN 1 if the number of 1 s in x1 XN is odd 0 if the number of 1 s in x1 XN is even NAND and NOR gates are especially easy to implement with transistor circuits so through the use of DeMorgan s Laws logic functions are often put in a form that can be computed using NAN D s or NOR s along with inverters Example For the function Fvvltyz WquotX y 392 i Find an implementation that uses only NAND gates and inverters Ans FW X V Z i Find an implementation that uses only NOR gates and inverters Ans FW X y z There are some systematic ways for representing logic functions that are useful for nding different types of implementations Canonical Forms 1 Minterms Suppose we have N bits x1 XN Let s consider all possible AN D s quotproductsquot of these variables or their complements That is m0 X1quotX2quot 39XN1quotXN 69 OOOO m1 X1quotX2quot XN1quotXN 69 0001 m2 X1quotX2quot 39XN1 39XN 69 OO1O mZquot 2 X1 39X2 39 39XN1 39XN 69 111O m2N1 X1 39X2 39 39XN1 39XN 69 1111 Each ofthese patterns is called a minterm Every logic function of xi XN can be expressed by a sum that is OR s of some set of minterms To nd the minterms in a function Draw the truth table Every combination of inputs that gives a 1 as output corresponds to a minterm Example Say we have 4 input variables wxyz Consider the function F w 39x y 392 With 4 variables there are 24 16 minterms m0 wquotxquoty 392 0000 to m15w39x39y 39z 1111 Truth Table I l l I I I l l OOOOOOOOE I l l I OOOOI I I l OOOOX I l OOI I OOI I OOI I OO I Ol OI Ol OI OI OI OI ON HOOOI OOOHOOOI I I H H So F m0mlm2m3m7mllm15 w X y z w X y zw X yz w x yzw xyzwx yz wxyz We write this in shorthand notation as F Z O12371115 This quotsum of minterms is one canonical form Example Write the function FXy2 X y 39 y 2 as a sum of minterms Ans F ZO 137 X y z X y z X yz xyz 2 Maxterms Again suppose we have N bits X1 XN Now let s consider all possible OR s quotsumsquot of these variables or their complements That is M0 X1X2XN1XN 69 OOOO M1 X1X2XN1XN 69 OO01 I2 X1X2XN1 XN 69 OO1O llIZ V2 X1 X2 XN1 XN 69 111O llIZN1 X1 X2 XN1 XN 69 1111 Each of these patterns is called a maxterm Note that the convention for numbering maxterms is the opposite of minterms that is a 1 in the kth position ofthe binary index indicates that we have xk in the minterm and xk in the maxterm Also note By applying DeMorgan s Law we can see that I Mk39mk Example Consider 4bit terms I I I I I I II II I I X1x2x3 x4 I I I I I I II I I I M13 V Now Suppose we have a function F that is written as a sum of minterms The complement of the function F is de ned by F 1whenFO F OwhenF1 Note that this implies that F is equal to a sum of the minterms that are not in F Example Say that FXyz ZO 137 x y z x y z x yz xyz Then F Xyz Z2456 X yz xy z xy z Xyz So F Z minterms not in F which implies that F F Z minterms not in F Z minterms in F But By DeMorgan s Law 2 minterms H minterms where H abc denotes a39b 39c As we ve just seen mk IVIk So we can write F H complements of minterms in F H maxterms in F where maxterm in F means a maxterm with an index whose minterm is not in F So every logic function can be written as a quotproduct of maxterms This is another canonical form Example Say that FXyz ZO 137 x y z x y z x yz xyz Then FXyz H 2456 VIZVI4IVI5M6 Xy zx yzx yz x y z check with x y z Z0137 l39l 2456 truth table 0 o o 1 1 o o 1 1 1 o 1 o o 0 V o 1 1 1 1 1 o o o o 1 o 1 o o 1 1 o o o 1 1 1 1 1 As we ll see Expressing a function in canonical form as a sum of minterms or product of maxterms will be a helpful rst step in developing methods for nding ef cient implementations However the canonical forms are not themselves ef cient for implementation since every term contains every possible literal Better forms for direct implementation are the standard forms of sum of products or product of sums in which each term can have any number of literals In the sum of products form the overall function is written as a sum OR s of terms formed by products AND s In the product of sums form the function is written as a product AND s of terms formed by sums OR s Either type of standard form leads to a twolevel logic gate implementation AND gates followed by an OR gate for sum of products and OR gates followed by an AND gate for product of sums Example Implement the function Fxyz z xyxy in standard forms i Sum of products F zxy xyxy x2 yz xy ii Product of sums F z xzyxy Postuate 4 XZ 39y2 39Xy Finally the standard forms can be converted to twolevel NAND or NOR implementations by applying DeMorgan s Laws Example Implement the function FXyz z xyxy using i Only NAND gates and inverters Use sum of products form F x2 yZXy XZyZXy XZ 39yz 39Xy M2 y39rz My ii Only NOR gates and inverters Use product of sums form F XZ 39yz 39Xy XZ yz Xy N ZNOIWZNMJ WJ Example Find implementations for the function FXyz XyyzzXXy i As a sum of products Ans Fxyyz i As a product of sums Ans F xyz i Using only NAND gates and inverters Ans Fx y x z i Using only NOR gates and inverters Ans Fx y z
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'