Class Note for ENGIN 112 at UMass(24)
Class Note for ENGIN 112 at UMass(24)
Popular in Course
Popular in Department
This 21 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 22 views.
Reviews for Class Note for ENGIN 112 at UMass(24)
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 3 Binary Logic and Boolean Algebra I Binary Codes 0 With n bits we can represent up to 2 objects The scheme for using bits to represent objects is called a binary code 0 For example with n bits and the standard binary code we represent the integers O 1 2 1 0 Alternatively with a signed 2 scomplement code we represent the integers 2 391 O 2 391 1 0 Other binary codes for representing integers are sometimes used In particular it is sometimes convenient to directly encode the digits in a decimal number this is called a binary coded decimal BCD representation Since there are 10 decimal digits we need to use 4 bits for each that is 0000 for 0 0001 for 1 0010 for 2 1000 for 8 and 1001 for 9 Note that the six binary patterns 1010 1011 1100 1101 1110 1111 are unused in this code Example The BCD representation for 237410 is 0010 0011 0111 0100 Important this is not the same thing as the binary representation for 237410 because it uses a different code It is possible to do addition directly in BCD the idea is to do binary addition of the codes for each digit If the sum is one of the patterns 0000 1001 we leave the sum as is If it is one of the unused patterns 1010 1111 we add binary6 0110 to the result to generate the correct digit and carry to the next digit Example Do BCD addition ofthe decimal numbers 84 and 57 1 1 8410 1000 0100 5710 0101 0111 14110 1110 1011 0110 0110 0001 0100 0001 Check BCD code for 14110 is 0001 0100 0001 Now suppose that we want a code that can represent text To represent the 10 decimal digits 52 upper and lowercase English letters and various punctuation marks symbols and control characters Need at least 7 bits because there are 27 128 different 7bit sequences The standard way to use bits to represent these characters is the American Standard Code for Information Interchange ASCII system shown in Table 17 in the book An 8th bit called a paritycheck bit is often placed as the leftmost bit of each ASCII symbol this bit is chosen so that the total number of 1 s in the 8bit symbol is even This helps detect any errors in the transmission of ASCII symbols Example The 7bit ASCII codes for H e I p and are as follows H 1001000 e 1100101 k 1101100 p l 1 1 10000 0100001 Using 8bit symbols for even parity what is the ASCII code for Help Ans 39 01001000 01100101 01101100 11110000 00100001 Example What is represented by the eight bits 10010110 if our binary code is i Standard 8bit binary representation Ans 27242221 128 164215010 i 8bit signed 2 s complement Ans 28 150 256 150 10610 i 4 bit BCD Ans 1001 0110 9610 i 8 bit ASCII with even parity Ans parity bit 7bit ASCII 0010110 SYN synchronous idle control character II Binary Logic Bits are stored in registers for example by using different voltage levels to represent quot0 and quot1 Binary processing converts some set of bits from input registers into a new bit value that is stored in an output register The processing that converts input bits to an output bit is based on binary logic There are three fundamental binary logic operations AN D OR and NOT The circuits that implement these operations and others that are based on them are called logic gates The action of a logic gate can be described using a truth table that shows what output bit results from each possible combination of input bits AND Let X and y denote input bits and let 2 denote the output bit The operation quotX AND y is equal to z is denoted by X39yz or xyz This operation has truth table X y z Xy O O O O 1 O 1 O O 1 1 1 AND gate symbol 2 0R Let X and y denote input bits and let 2 denote the output bit The operation quotX OR y is equal to z is denoted by This operation has truth table Important This is not the same as a binary sum OR gate symbol 1 Xyz zxy O HHOOX HOHO lt 1 1 1 NOT Let X denote an input bit and let 2 denote the output bit The operation quotNOTX is equal to z is denoted by X z This operation has truth table x z x 50 X is the complement or O 1 inverse of X 1 O NOT gate symbol also called inverter X X39 More complicated functions are formed by combinations of the basic logic operations Example Say that a patient undergoes three medical tests Tests A B and C The result of each test may be quothighquot or quotlowquot The patient is diagnosed as having condition D if a 39 b a 39 6 Test A is quothighquot and Test B is quothighquot or Test A is quothighquot and Test C is quothigh Or b 39C a Test B is quothighquot and Test C is quothighquot and Test A is quotlow and is diagnosed as not having condition D otherwise Leta b and c be binary values representing the outcomes of Tests A B and C respectively with a 1 denoting Test A is quothighquot and a O denoting Test A is quotlowquot etc Let d be a binary variable denoting the diagnosis with d 1 denoting quotdiagnosed as having condition Dquot Find a logic function logic gate implementation and the truth table for the diagnosis Function f1abc a 39b a 39C b 39C 39a d Logic Gate Implementation L Q D U VLJH Truth Table abc Q o 5 Q o h 5 o h a39ba39c b 39c 39a 000 O 001 010 011 100 101 110 111 I I OOOOOO I OI OOOOO I OOOI OOO OOOOI I I I Q I I I OOOO OOOOI OO I l l OI OOOQ Now consider a new function f2abc a 39 b c b 39c d Truth table a b c b 000 001 010 011 100 101 110 111 h 5 I h a 39 bc I I I OI I I Ol I I I OOOOO I OOOI OOO I I I Ol OOOD But This is exactly the same as the truth table for functioan looking at the input and output columns So f1a bl C f2ab C Logic Gate Implementation for f2abc This is much simpler than the implementation forf1abc but it does exactly the same thing In general How do we know how to nd equivalent logic functions and simpli ed implementations By using the principles of Boolean Algebra III Boolean Algebra An algebra just a set of elements and mathematical operations on those elements that satisfy some number of rules or postulates We are interested in twovalued Boolean algebra for which the elements are the two values in the set B 0 1 and the operations are 0 AND and OR along with the complement operator The rules that these operators obey are called the Huntington Postuates There are six postulates listed on p 38 The most important for simplifying logic functions are postulates 2 3 4 and 5 Let X y and 2 denote elements of B that is bits Then 2 XOX X 391X 3 XyyX39X 39yy 39X 4 X 39yz X 39yX 39239Xy 39zXy 39XZ 5 XX 139X 39X O Many other properties can be derived from these postulates some ofthese are given in Sec 24 One important property is Duality it says that any true logical expression remains true if all 0 s and s are interchanged and all 0 s and 1 s are interchanged il Example Verify DellIorgan s Laws i X 39y X y ii X y X 39y Verify i by using truth table X y X yy XIyI O O 1 1 So for each possible pair of values for x y we have 0 1 1 1 X39y X y V 10 1 1 1 1 O O To verify ii Just apply duality to i interchange and A term in a logic function is an expression that can be evaluated by one logic gate A literal is a variable inside a term In general we try to implement a function using as few terms and literals as possible since this means reduced system complexity For example we saw previously that f16LbC a 39b a 39C b 39C 39a 7 literals 6 terms is equivalent to f2abc a 0 b 0 b 39c 5 literals 4 terms Example Find an ef cient implementation of fxyz X y39X y Z 39 y 5 terms 6 literals by nding an equivalent expression that has only three literals Ans x y 0 x x y 0 x x Post 4 x y 0 1 Post 5 xy Post 2 Similarlyyz y VZ YY W Xyyz Thm4 xyz Thm 1 So fxyz x y V 2 So fxyz x y z using DeMorgan s Law this is also equal to x 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'