Class Note for ENGIN 112 at UMass(26)
Class Note for ENGIN 112 at UMass(26)
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 18 views.
Reviews for Class Note for ENGIN 112 at UMass(26)
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 8 Comparators Encoders and Multiplexers We ve discussed a number of combinational circuits that are used for arithmetic adders subtractors an multipliers Several other combinational circuits perform operations that are important for digital computation these include magnitude comparators multiplexers and encodersdecoders A magnitude comparator determines which of two input binary numbers is larger A multiplexer has multiple input lines and a single output line that is connected to one of the inputs A set of control bits is used to determine which input line is mapped to the output An encoder is a circuit that maps some set of inputs into binary representations for example a BCD encoder would have ten input lines representing decimal digits 01 9 and four output bits A decoder reverses the encoding a BCD decoder would have four input bits and ten output lines each one representing a decimal digit I Magnitude Comparator Say we have two n digit binary numbers A An7An2 A0 and B Bn1Bn2B0 We want to determine which of the following is true 1 A B 2 A gt B or 3 A lt B How do we develop a circuit to do this First define three circuit outputs F 1 if and only ifA B F2 1 if and only ifA gt B and F3 1 if and only ifA lt B Then our goal is to design a combinational circuit having 2n inputs A and B and three outputs F7 F2 F3 Note that this is impractical to do with our standard method of truth tables and Karnaugh maps once n gets to be reasonably large since the truth table will have 22 rows 4bit words 28 256 rows 8 bit words 216 65536 rowsl Instead we develop an algorithm that is a stepbystep set of rules that the comparator must satisfy and design a circuit that performs the algorithm First Develop a circuit that computes F7 that is that indicates when A B Note that A B if and only if AK Bk for every k 01n1 For each k 01n1 define the bit xk by Xk1ifAkBk39Xk 0ifAk Bk Draw the Karnaugh map for in Bk AK 0 1 So xk AkBk Ak Bk O 1 AKXOR Bk AKIBK AkBk 1 1 this is sometimes written as xk AKXNOR Bk Then F1X0X1Xn1 Circuit for computing in A lt B Ak quot quot Ak Bk Ak Bk 0 Xk Bk W A gt B k k AkBk Block symbol A gt Ak Bk Now we can use these blocks in quot EN gt xk developing the rest of the circuit Bk gt A B k k Now consider F2 F2 1 if and only ifA gt B when does this occur A An1An2A0 gt B Bn1Bn2B0 when 1 An11 AND Bn10 gtAn1Bn7 OR 2 An1Bn1 AND An21 AND Bn20 gt Xn1An2Bn2 OR n An1Bn1 AND An2Bn2 AND AND A1B1 AND A01 AND 300 gt xn7x2 X1A0B0 803 F 2 An1Bn1 Xn 1An2Bn2 Xn1 Xn 2An3Bn3 Xn7Xn2 X7A0B0 To get F3 1 when B gt A just reverse A and B from F2 F3 An 1an1 Xn1An2an2 Xn1Xn2An3an3 Xn7Xn2 X7A0 B0 Magnitude comparator circuit for n 3 II Multiplexer A multiplexer MUX uses control bits to direct one of a set of multiple inputs into a single output for example an Arithmetic Logic Unit ALU uses a multiplexer that outputs the result of one of four possible operations on a pair of bits AND OR addition subtraction So it is a fourtoone multiplexer Let s consider the general design of a fourtoone multiplexer Let the inputs into the multiplexer be denoted l0 l7 l2 3 For example given two bits A and B being processed by an ALU we might set 0 A AND B I A OR B 2 sum bit forAB addition not OR 3 sum bit forAB Let Ybe the MUX output Since we need to select one of the inputs to direct to the output we must be able to make four choices so we need two control 80 and 87 bits to indicate which choice we make Suppose we use the following rule the input that is directed to the output is lk when k 8780 So 87 80 0 means Y I0 87 0 80 1 means Y 7 etc Note that this can be implemented by Fourto one MUX Block symbol for fourtoone MUX 4x1 MUX One important use of multiplexers is to implement logical functions in fact a fourtoone MUX can be used to implement any function of three bits Xyz Idea Set 87 X 80 y then set each of the inputs 0 l7 l2 and 3 to have one of the values 0 1 z or 2 as needed to agree with the truth table which variable is on which input line determines the function that is implemented Example Implement the function FXyz xz yz using a 4to1 MUX xyz F 4x1MUX 000 o y So FQ0 001 o x 81 010 o Flz 011 1 7 0 0 y F 100 1 z 1 Fl2z 101 0 2 2 110 1 FI31 7 I3 111 1 o In general Afunction of n binary variables can be implemented with a 2 7391 by 1 MUX using n1 control bits and 2 1 input lines So multiplexers provide a very flexible modular technique for function implementation III EncodersDecoders An encoder maps 2 or fewer input lines into n output lines Only one input line at a time can have value 1 all others are supposed to be 0 The output line values represent the binary code for the input line that has value 1 Example A BCD encoder has 10 input lines each representing a decimal digit and 4 output lines so the output is the binary code representing a given decimal digit Let the inputs be denoted DO D7 09 with Dk 1 meaning that we have decimal digit k1O Let the output bits be denoted as w X y 2 So we have wxyz 001 0000 011 0001 021 0010 031 0011 041 0100 051 0101 061 0110 071 0111 081 1000 091 1001 What functions generate the output bits from the inputs wDgDg xD4D5DsD7 yD2D3DeD7 zD1D3D5D7Dg BCD encoder circuits Priority and validity As noted the encoder assumes that exactly one input line has value 1 and all others are 0 However in real circuits the values on lines change over time and the timing synchronization may not be perfect This leads to two possible problems All input lines might be 0 The usual convention in this case is to set all output lines to O but in our BCD example this is also the binary code for the Do How do we distinguish the output for input D0 from the output for no input One approach Define an extra bit Vcalled a valid bit indicator We set V 0 when all inputs are 0 and V 1 othenvise So How is V represented as a function of the inputs Then we can distinguish the output for D0 wxyz v 0000 1 from the output for no input wxyz v 0000 0 c ii Two or more lines might have value 1 at the same time To resolve the conflict we can set a priority rule that establishes which input line is to be encoded when two or more have value 1 As one possibility we might say that numerically larger inputs have priority over those that are smaller for example in the BCD encoder if both D6 1 and D3 1 we will output the code for D6 and ignore D3 Then In the BCD example we have an encoding rule that looks like this X Don t Care D0D1D2D3D4D5D6D7D8D9 wxyz v 0000000000 00000 XXXXXXXXXl 10011 XXXXXXXXlO 10001 XXXXXXXlOO 01111 1000000000 00001 Example In the BCD encoder we saw that without priority ecoding the function for output bit X is X D4 D5 D6 D7 How is this changed when we use priority encoding V th priority encoding The output encodes D7 only when both 09 and 08 are 0 Similarly we encode D6 only when both 09 08 and D7 are all 0 etc So the new function for X becomes x D7081 06071381794 05061371381 04051761771381 07081 D6Dg Dg 05081 04081 D7 De D5 D4DBDQ o A decoder is the opposite of an encoder it maps n input lines whose values represent the binary code for some object into 2 or fewer output lines Only one output line has value 1 at any given time that is the output whose code is given by the values on the input lines Example A BCD decoder has four input bits w X y z and ten output bits DO D7 09 with Dk 1 when wXyz is the binary code for decimal digit k1O We have the inputoutput relation shown previously slide 13 So DO w x y z Note that the function generating each D7 w x y z output bit is a minterm of the set of inputs 09 WX y z In general We can think of a decoder having n inputs and 2quot outputs as a circuit that generates all of the possible minterms of the input bits these decoders are called n to 2quot line decoders Example 3to8 line decoder Block symbol for 3to8 ine decoder 3x8 Decoder m2 Note that since any function can be written as a sum of minterms an n to 2n ine decoder can be used along with OR gates to implement any function of n bits Example For the example considered previously FXyz xz yz X xy z x yzxyz m6m4m3m7 3x8 Decoder
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'