Class Note for ENGIN 112 at UMass(16)
Class Note for ENGIN 112 at UMass(16)
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 18 views.
Reviews for Class Note for ENGIN 112 at UMass(16)
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 5 Digital Circuits and Karnaugh Maps I Digital Integrated Circuits Logic circuits are constructed from transistors For digital circuits metaloxide semiconductor MOS transistors are most commonly used In digital circuits transistors act like voltagecontrolled switches The voltage level on a node called the gate determines whether or not current flows between two nodes called the source and drain Current flow closed switch between source and drain no current flow open switch between source and drain Typically we set some high voltage level say 5 V to represent logical 1 and some low voltage say 0 V to represent 0 We set a voltage source at each of those levels the high voltage source is often denoted VDD and the low voltage as ground Then we implement logic functions by using input bits to determine a set of gate voltages that open and close switches as needed to connect the output node to the appropriate source voltage again high for 1 and low for O nchannel MOS Symbol G Also G 8 Simplified operation Gate voltage high Gate voltage low Drain connected NO to Source connection pchannel MOS Symbol Gate voltage low Drain connected to source G l Also G cl 8 Simplified Operation Gate voltage high No connection CMOS Complementary MOS CMOS circuits have both nchannel and p channel MOS transistors connected to form logic circuits Examples i CMOS Inverter 5 V VDD5 V X21 L lt 5 V 39 y0 O V X y 0 V GNDO v 5 V x0 y1 O V 80 y X 5 V OV ii CMOS NAND Gate 3 y AB39 A1 B1 A 5V 5V 1 B039 1 5v 0V 0V 0V iii CMOS NOR Gate l39nn I39 h IBJ39 A1 B039 5V A0 30 1 5V 5V l V k CV 0V Example Draw a CMOS implementation of the function FABC A B C A BC A BC A BC A NAND B NOR C So can just connect the CMOS NOR with B and C as inputs and CMOS NAND with A and and the NOR gate output as inputs gates shown previously II Karnaugh Maps To save on circuit complexity power requirements space on an integrated circuit etc it is desirable to implement logic functions with as few and as simple logic gates as possible To do this we need to minimize the numbers of terms and literals used to represent logic functions One relatively simple method that has been developed for simplifying functions of up to four variable is the use of Karnaugh maps The map is a table with squares that correspond to minterms The function is expanded as a sum of minterms for every minterm in the function a 1 is placed in the map in the corresponding square Then the function can be simplified by summing the minterms that correspond to adjacent 1 s in the map this eliminates a term and a literal Twovariable map y X 0 1 O m0X y m1X y 1 m239Xy m339Xy Example Simplify the function FX y Xyx yx y m0m1m3 xyF Truth 001 Table 011 100 111 Karnaugh map X 0 1 y 0 1 m0 1 m1391 m 803 F m0m1m1m3 X y X YX yX X y Threevariable map Now say have three variables Xyz We set up the map so that the rows are indexed by X and the columns by yz For yz we use Grey Code ordering that is 00 O1 11 10 yz X 00 O1 11 10 0 m0 X y z m1X y z m3 X yz m2 X yz 1 m4 xy z m5 xy z m7 xyz m6 xyz We can group adjacent squares of 1 s in blocks of two or four Note that leftmost and rightmost columns are treated as being adjacent as if table were wrapped on a cylinder Sum of any block of ones is equal to the variables that do not change in that block Examples i Simplify the function f1abc ab ac a bc Truth table for this function was given in Discussion 3 it shows that f1 2 356 7 So K map Is bio a 00 O1 11 10 0 m3 1 1 m5 1 m7 1 m6 1 So f1 m3m7m5m7m6m7 a bcabcab cabcabc abc bcacab ii Simplify the function f2xyz 20 124 6 lelzIlelzlezlXylzlXyzl yz X 00 O1 11 10 0 m0 1 m1 1 m2 K map 803 f2 m0m1 m0m4m2m6 Xiyiz Xyz Xiyizi Xyz lel z Terminology An implicant is a block of ones in a K map A prime implicant is a block that contains the maximum possible number of adjacent squares An essential prime implicant is a prime implicant that includes a square that is not covered by any other prime implicant To minimize the number of terms in a function representation find a representation solely in terms of essential prime implicants Examples i In previous example Essential prime implicants are ZO246 and ZO1 x oo 01 11 1O ii What are the essential prime implicants of F 20 1245 6 7 yz X 00 O1 11 10 0 m0 1 m1 1 m2 1 Essential prime implicants are Z0145 and Z024 6 So Fy z Note that we do not decompose F into 20 145 and 22 6 why not Because 22 6 is not an essential prime implicant in fact it is not even a prime implicant because it is not the largest possible block covering the 1 s at m2 and ms If we did write F 20 145 22 6 we would get F y yz which is not the simplest possible representation Fourvariable map Now say we have four variables WXyz We set up the map so that the rows are indexed by WX and the columns by yz We use Grey Code ordering for both WX and yz yz WX OO 01 11 1O 00 m0 39 W X y z m1 W X y z m3 W X yz m2 39 W X yz 01 m4 39 W Xy z m5 W Xy z m7 W Xyz m6 39 W Xyz 11 m12 wxy z m13 wxy z m15 wxyz m14 wxyz 10 m8 39 WX y z m9 39 WX y z m11 39 WX yz mm 39 WX yz Now blocks implicants can have size 2 4 or 8 Also note that we treat top and bottom rows as being adjacent Example Simplify the function FWXyzWXyzW Xz Truth Table wxyz 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 OOOOOOOOn So F 25 6 7911 13 1415 K map yz WX OO 01 11 10 OO 01 m5 1 m7 1 me 11 quotquot7135 7 quot71539 7 quot714 10 m9 1 m 1 80 F 2571315 Z671415 29111315 xzxywz Further Notes We can use Karnaugh maps for more than 4 variables but it gets increasingly complicated and difficult to do by hand for more than 4 variable we usually use a computer program to do the minimization Sometimes there are certain combinations of inputs that are not allowed to occur so the value of the function for those inputs is not specified Those inputs are called don tcare conditions it s as if for those inputs we don t care whether the output is a O or a 1 In the K map boxes for don tcare conditions are marked with X s They can be grouped with blocks of 1 s if that leads to larger essential prime implicants that is simpler terms Example Say we have the function Fabc Z145 The inputs 000 and 111 never occur so we have the don tcare conditions 20 7 Simplify the function Kmap a So F 20 145 b
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'