Logic Lecture 08 PDF
Document Details
Uploaded by DexterousSuprematism
NUS
Aaron Tan
Tags
Summary
This document is a lecture presentation on MSI components, including decoders, encoders, multiplexers, and demultiplexers. The presentation is from Aaron Tan at NUS.
Full Transcript
Aaron Tan, NUS 1 Lecture 8 MSI Components Decoders, Encoders, Multiplexers and Demultiplexers Aaron Tan, NUS 2 Contents Decoders ▪ Implementing func...
Aaron Tan, NUS 1 Lecture 8 MSI Components Decoders, Encoders, Multiplexers and Demultiplexers Aaron Tan, NUS 2 Contents Decoders ▪ Implementing functions using decoders ▪ Decoder with enable ▪ Standard MSI decoder Encoders ▪ Priority encoders Multiplexers ▪ Standard MSI multiplexer ▪ Implementing functions using multiplexers ▪ Using smaller multiplexers Aaron Tan, NUS 3 DECODERS decoder code entity Aaron Tan, NUS 4 Decoding – the inefficient way 0 0 0 0 0 1 0 0 0 1 2 3 4 5 6 7 Aaron Tan, NUS 5 Decoding – the better way 1 0 1 Some device 0 1 2 3 4 5 6 7 Aaron Tan, NUS 6 2. Decoders (2/5) ▪ Example: If codes 00, 01, 10, 11 are used to identify four persons, we may use a 2-bit decoder. 2x4 F0 Person 0 2-bit X DEC F Person 1 1 code Y F2 Person 2 F3 Person 3 ▪ This is a 24 decoder which selects an output line based on the 2-bit code supplied. ▪ Truth table: X Y F0 F1 F2 F3 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 Aaron Tan, NUS 7 2. Decoders (3/5) X 0 Y 0 F0 1 F1 0 F2 0 F3 0 ▪ From truth table, circuit for 0 1 0 1 0 0 1 0 0 0 1 0 24 decoder is: 1 1 0 0 0 1 F0 = X'Y' F1 = X'Y Each output is a minterm (X'Y', X'Y, XY' or XY) of a F2 = XY' 2-variable function. F3 = XY X Y Aaron Tan, NUS 8 2. Decoders (4/5) ▪ Design a 38 decoder. F0 = x'y'z' x y z F0 F1 F2 F3 F4 F5 F6 F7 0 0 0 1 0 0 0 0 0 0 0 F1 = x'y'z 0 0 1 0 1 0 0 0 0 0 0 F2 = x'yz' 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 F3 = x'yz 1 0 0 0 0 0 0 1 0 0 0 F4 = xy'z' 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 F5 = xy'z 1 1 1 0 0 0 0 0 0 0 1 F6 = xyz' F7 = xyz Each output is a minterm of a 3-variable x y z function. Aaron Tan, NUS 9 2. Decoders: Implementing Functions (1/3) ▪ A Boolean function, in sum-of-minterms form ▪ decoder to generate the minterms, and ▪ an OR gate to form the sum. ▪ Any combinational circuit with n inputs and m outputs n can be implemented with an n:2 decoder with m OR gates. ▪ Good when circuit has many outputs, and each function is expressed with a few minterms. Aaron Tan, NUS 10 2. Decoders: Implementing Functions (2/3) x y z C S 0 0 0 0 0 ▪ Example: Full adder 0 0 1 0 1 0 1 0 0 1 S(x, y, z) = m(1,2,4,7) 0 1 1 1 0 C(x, y, z) = m(3,5,6,7) 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 3x8 0 DEC 1 S 2 x S2 3 y S1 4 5 C z S0 6 7 Aaron Tan, NUS 11 2. Decoders: Implementing Functions (3/3) S(x, y, z) = m(1,2,4,7) C(x, y, z) = m(3,5,6,7) x y z C S 3x8 0 1 0 0 DEC 1 0 1 0 0 0 0 0 0 S 0 11 0 0 1 0 1 2 000 0 1 0 0 1 0 0 1x S2 3 000 0 1 1 1 0 0 0 1y S1 4 000 1 0 0 0 1 5 000 C 0 01 0 1 1z 1 0 1 1 0 S0 6 000 1 1 0 1 0 7 001 1 1 1 1 1 BRAVO!!! Aaron Tan, NUS 12 2. Decoders with Enable (1/2) ▪ Decoders often come with an enable control signal, so that the device is only activated when the enable, E = 1. ▪ Truth table: F0 = EX'Y' E X Y F0 F1 F2 F3 1 0 0 1 0 0 0 F1 = EX'Y 1 0 1 0 1 0 0 1 1 0 0 0 1 0 F2 = EXY' 1 1 1 0 0 0 1 0 d d 0 0 0 0 F3 = EXY ▪ Circuit of a 24 decoder with enable: X Y E Aaron Tan, NUS 13 2. Decoders with Enable (2/2) ▪ In the previous slide, the decoder has a one-enable control signal, i.e. the decoder is enabled with E=1. ▪ In most MSI decoders, enable signal is zero-enable, usually denoted by E' or Ē. The decoder is enabled when the signal is zero (low). E X Y F0 F1 F2 F3 E' X Y F0 F1 F2 F3 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 0 d d 0 0 0 0 1 d d 0 0 0 0 Decoder with 1-enable Decoder with 0-enable Aaron Tan, NUS 14 2. Constructing Larger Decoders (1/4) ▪ Larger decoders can be 3x8 DEC 0 F0 = w'x'y' F1 = w'x'y constructed from smaller w S2 1 : : x S1 ones. y S0 : : 7 F7 = wxy ▪ Example: A 38 decoder can be built from two 2x4 24 decoders (with one- w DEC 0 F0 = w'x'y' x S1 1 F1 = w'x'y enable) and an inverter. y S0 2 F2 = w'xy' E 3 F3 = w'xy 2x4 DEC 0 F4 = wx'y' S1 1 F5 = wx'y S0 2 F6 = wxy' E 3 F7 = wxy Aaron Tan, NUS 15 2. Constructing Larger Decoders (2/4) 3x8 0 F0 = w'x'y' Dec w S2 1 F1 = w'x'y x S1 : : BRAVO!!! y S0 : 7 : F7 = wxy 2x4 0 0 1 w Dec 0 1 0 0 F0 = w'x'y' 0 0 1 x S1 1 0 1 0 F1 = w'x'y 0 0 0 0 1 0 y S0 2 F2 = w'xy' 0 0 0 E 3 F3 = w'xy 1 1 0 2x4 Dec 0 0 0 0 F4 = wx'y' S1 1 0 0 0 F5 = wx'y 0 0 1 S0 2 F6 = wxy' 0 0 0 E 3 F7 = wxy 0 0 1 Aaron Tan, NUS 16 2. Constructing Larger Decoders (3/4) ▪ Construct a 416 decoder 4x16 DEC 0 F0 w S3 from two 38 decoders x S2 1 F1 : : with one-enable and an y S1 : : z S0 15 F15 inverter. 3x8 w DEC 0 F0 x S2 1 F1 y S1 : : z S0 7 F7 E 3x8 DEC 0 F8 S2 1 F9 S1 : : S0 7 F15 E ▪ Note: The input w and its complement w' are used to select either one of the two smaller decoders. Aaron Tan, NUS 17 Exercise: How to construct a 416 decoder using five 24 decoders with enable? 2x4 Dec 0 F0 = (w'x')y'z' y S1 1 F1 = (w'x')y'z z S0 2 F2 = (w'x')yz' E 3 F3 = (w'x')yz 2x4 Dec 0 w S1 1 2x4 x S0 2 Dec 0 F4 = (w'x)y'z' E 3 y S1 1 F5 = (w'x)y'z z S0 2 F6 = (w'x)yz' E 3 F7 = (w'x)yz 1 2x4 Dec 0 F8 = (wx')y'z' y S1 1 F9 = (wx')y'z z S0 2 F10 = (wx')yz' E 3 F11 = (wx')yz 2x4 Dec 0 F12 = (wx)y'z' y S1 1 F13 = (wx)y'z z S0 2 F14 = (wx)yz' E 3 F15 = (wx)yz Aaron Tan, NUS 18 Negated outputs (active low outputs) decoders ▪ A decoder may be 1-enabled or 0-enabled. ▪ A decoder may also normal output or negated outputs. (See next two slides.) ▪ Normal outputs = active high outputs ▪ Negated outputs = active low outputs E X Y F0 F1 F2 F3 E X Y F0 F1 F2 F3 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 1 1 0 0 0 1 0 1 1 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 d d 0 0 0 0 0 d d 1 1 1 1 1-enabled, active high 1-enabled, active low outputs 2x4 decoder. outputs 2x4 decoder. Aaron Tan, NUS 19 2. Standard MSI Decoder (1/2) ▪ 74138 (3-to-8 decoder) 74138 decoder module. (a) Logic circuit. (b) Package pin configuration. Aaron Tan, NUS 20 2. Standard MSI Decoder (2/2) 74138 decoder module. (c) Function table. (c) 74138 decoder module. (d) Generic symbol. (e) IEEE standard logic symbol. Source:The Data Book Volume 2, Texas Instruments Inc.,1985 Aaron Tan, NUS 21 2. Decoders: Implementing Functions Revisit (1/2) ▪ Example: Implement the following function using a 38 decoder and an appropriate logic gate f(Q,X,P) = m(0,1,4,6,7) = M(2,3,5) ▪ We may implement the function in several ways: ▪ Using a decoder with active-high outputs with an OR gate: f(Q,X,P) = m0 + m1 + m4 + m6 + m7 ▪ Using a decoder with active-low outputs with a NAND gate: f(Q,X,P) = (m0' m1' m4' m6' m7' )' ▪ Using a decoder with active-high outputs with a NOR gate: f(Q,X,P) = (m2 + m3 + m5 )' [ = M2 M3 M5 ] ▪ Using a decoder with active-low outputs with an AND gate: f(Q,X,P) = m2' m3' m5' Aaron Tan, NUS 22 2. Decoders: Implementing Functions Revisit (2/2) f(Q,X,P) = m(0,1,4,6,7) = M(2,3,5) 0 0 3x8 1 3x8 1 Dec 2 Dec 2 Q A 3 f(Q,X,P) Q A 3 f(Q,X,P) B 4 B 4 X X 5 5 P C 6 P C 6 (m0'·m1'·m4'·m6'·m7)' 7 7 =m0+m1+m4+m6+m7 (a) Active-high decoder with OR gate. (b) Active-low decoder with NAND gate. 0 0 3x8 1 3x8 1 Dec 2 f(Q,X,P) Dec 2 f(Q,X,P) Q A 3 Q A 3 B 4 B 4 X X 5 (m2+m3+m5)' 5 m2'·m3'·m5' P C 6 = m2'·m3'·m5' P C 6 = M2·M3·M5 7 = M2·M3·M5 7 (c) Active-high decoder with NOR gate. (d) Active-low decoder with AND gate. Aaron Tan, NUS 23 ENCODERS encoder entity code Aaron Tan, NUS 24 3. Encoders (1/4) ▪ Encoding is the converse of decoding. ▪ Given a set of input lines, of which exactly one is high and the rest are low, the encoder provides a code that corresponds to that high input line. ▪ Contains 2n (or fewer) input lines and n output lines. ▪ Implemented with OR gates. ▪ Example: F0 D0 Select via F1 4-to-2 switches 2-bits F2 Encoder D1 code F3 Aaron Tan, NUS 25 Encoding – the inefficient way 0 1 2 3 4 5 6 7 0 0 0 0 0 1 0 0 Aaron Tan, NUS 26 Encoding – the better way 0 1 2 3 4 5 6 7 Some device 1 0 1 Aaron Tan, NUS 27 3. Encoders (2/4) F2 D1 ▪ Truth table: F0 F1 1 0 F2 F3 0 0 D1 0 D0 0 X 1 X 1 0 1 0 0 0 1 0 X X X ▪ With K-map, 0 0 1 0 1 0 X X X X F1 0 0 0 1 1 1 we obtain: 0 0 0 0 X X F0 0 X X X ▪ D1 = F2 + F3 0 0 0 1 1 1 0 1 X X X X F3 ▪ D0 = F1 + F3 0 1 1 0 X X 0 1 1 1 X X ▪ Circuit: 1 0 1 0 0 1 1 0 X X X X D0 F2 1 0 1 1 X X X 1 X 0 F0 1 1 0 0 X X F1 1 1 0 1 X X 1 X X X D0 1 1 1 0 X X F1 X X X X F2 1 1 1 1 X X F0 D1 0 X X X F3 F3 Simple 4-to-2 encoder Aaron Tan, NUS 28 3. Encoders (3/4) ▪ Example: 8-to-3 encoder. ▪ At any one time, only one input line of an encoder has a value of 1 (high), the rest are zeroes (low). Inputs Outputs D0 D1 D2 D3 D4 D5 D6 D7 x y z 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 Aaron Tan, NUS 29 3. Encoders (4/4) ▪ Example: 8-to-3 encoder. D0 D1 x = D 4 + D5 + D6 + D7 D2 D3 y = D 2 + D3 + D6 + D7 D4 D5 D6 D7 z = D 1 + D3 + D5 + D7 An 8-to-3 encoder ▪ Exercise: Can you design a 2n-to-n encoder without using K-map? Aaron Tan, NUS 30 3. Priority Encoders (1/2) ▪ A priority encoder is one with priority ▪ To allow for more than one input line to carry a 1. ▪ If two or more inputs or equal to 1, the input with the highest priority takes precedence. ▪ If all inputs are 0, this input combination is considered invalid. ▪ Example of a 4-to-2 priority encoder: Inputs Outputs D0 D1 D2 D3 f g V 0 0 0 0 X X 0 1 0 0 0 0 0 1 X 1 0 0 0 1 1 X X 1 0 1 0 1 X X X 1 1 1 1 Aaron Tan, NUS 31 3. Priority Encoders (2/2) ▪ Understanding “compact” function table Inputs Outputs Inputs Outputs D0 D1 D2 D3 f g V D0 D1 D2 D3 f g V 0 0 0 0 X X 0 0 0 0 0 X X 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1 1 X 1 0 0 0 1 1 1 1 0 0 0 1 1 X X 1 0 1 0 1 0 0 1 0 1 0 1 X X X 1 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 ◼ Exercise: Obtain the 0 0 1 1 1 1 1 0 1 0 1 1 1 1 simplified expressions 0 1 1 1 1 1 1 for f, g and V. 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 Aaron Tan, NUS 32 Hi Prof, please go through priority encoder and how to map out the expression using kmap. Slide 34 lect 18. ◼ Exercise: Obtain the simplified D2 D2 f g expressions for f, g and V. X 1 1 1 X 1 1 0 Inputs Outputs D0 D1 D2 D3 f g V 0 1 1 1 1 1 1 0 0 0 0 0 X X 0 0 1 1 1 D1 1 1 1 0 D1 1 0 0 0 0 0 1 D0 D0 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 1 D3 D3 0 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 0 1 D2 V 0 0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 D1 1 0 0 1 1 1 1 D0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 D3 1 1 1 1 1 1 1 Aaron Tan, NUS 33 MULTIPLEXERS mux data input select Aaron Tan, NUS 34 Multiplexers and Demultiplexers ▪ An application: ▪ Helps share a single communication line among a number of devices. ▪ At any time, only one source and one destination can use the communication line. Aaron Tan, NUS 35 5. Multiplexers (1/4) ▪ A multiplexer is a device that has ▪ A number of input lines ▪ A number of selection lines ▪ One output line n ▪ It steers one of 2 inputs to a single output line, using n selection lines. Also known as a data selector. n 2 :1 inputs Multiplexer output :... select Aaron Tan, NUS 36 5. Multiplexers (2/4) ▪ Truth table for a 4-to-1 multiplexer: I0 I1 I2 I3 S1 S0 Y S1 S0 Y d0 d1 d2 d3 0 0 d0 0 0 I0 d0 d1 d2 d3 0 1 d1 0 1 I1 d0 d1 d2 d3 1 0 d2 1 0 I2 d0 d1 d2 d3 1 1 d3 1 1 I3 Inputs Inputs I0 0 I0 I1 4:1 I1 1 4:1 MUX Y I2 2 Y Output I2 mux I3 3 I3 S1 S0 S1 S0 select select Aaron Tan, NUS 37 5. Multiplexers (3/4) S1 0 S0 0 Y I0 0 1 I1 ▪ Output of multiplexer is 1 0 I2 1 1 I3 “sum of the (product of data lines and selection lines)” ▪ Example: Output of a 4-to-1 multiplexer is: Y = ?I0∙(S1'∙S0') + I1∙(S1'∙S0) + I2∙(S1∙S0') + I3∙(S1∙S0) Note: Expressing I0∙(S1'∙S0') + I1∙(S1'∙S0) + I2∙(S1∙S0') + I3∙(S1∙S0) in minterms notation, it is equal to I0∙m0 + I1∙m1 + I2∙m2 + I3∙m3 This is useful later (eg: slide 45). Aaron Tan, NUS 38 5. Multiplexers (4/4) ▪ A 2n-to-1-line multiplexer, or simply 2n:1 MUX, is made n n from an n:2 decoder by adding to it 2 input lines, one to each AND gate. ▪ A 4:1 multiplexer circuit: I0 I0 I1 I1 Y Y I2 I2 I3 I3 0 1 2 3 2-to-4 Decoder S 1 S0 S1 S0 Aaron Tan, NUS 39 5. Multiplexer IC Package ▪ Some IC packages have a few multiplexers in each package (chip). The selection and enable inputs are common to all multiplexers within the package. A0 Y0 A1 Y1 A2 Y2 A3 Y3 B0 B1 E’ S Output Y 1 X all 0’s B2 0 0 select A B3 0 1 select B S (select) E' Quadruple 2:1 multiplexer (enable) Aaron Tan, NUS 40 5. Standard MSI Multiplexer (1/2) (b) 74151A 8-to-1 multiplexer. (a) Package configuration. (b) Function table. Aaron Tan, NUS 41 5. Standard MSI Multiplexer (2/2) (c) 74151A 8-to-1 multiplexer. (c) Logic diagram. (d) Generic logic symbol. (e) IEEE standard logic symbol. Source: The TTL Data Book Volume 2. Texas Instruments Inc.,1985. Aaron Tan, NUS 42 5. Multiplexers: Implementing Functions (1/3) ▪ Boolean functions can be implemented using multiplexers. ▪ A 2n-to-1 multiplexer can implement a Boolean function of n input variables, as follows: 1. Express in sum-of-minterms form. Example: F(A,B,C) = A'B'C + A'BC + AB'C + ABC' = m(1,3,5,6) 2. Connect n variables to the n selection lines. 3. Put a ‘1’ on a data line if it is a minterm of the function, or ‘0’ otherwise. Aaron Tan, NUS 43 5. Multiplexers: Implementing Functions (2/3) ▪ F(A,B,C) = m(1,3,5,6) This method works because: 0 0 1 0 1 2 Output = I0m0 + I1m1 + I2m2 + I3m3 1 0 3 mux 4 F + I4m4 + I5m5 + I6m6 + I7m7 1 5 1 6 Supplying ‘1’ to I1,I3,I5,I6 , and ‘0’ to the 0 7 rest: A B C Output = m1 + m3 + m5 + m6 From slide 34 (4:1 mux) Expressing I0∙(S1'∙S0') + I1∙(S1'∙S0) + I2∙(S1∙S0') + I3∙(S1∙S0) in minterms notation, it is equal to I0∙m0 + I1∙m1 + I2∙m2 + I3∙m3 Aaron Tan, NUS 44 5. Multiplexers: Implementing Functions (3/3) ▪ Example: Use a 74151A to implement f(x1,x2,x3) = m(0,2,3,5) Realization of f(x1,x2,x3) = m(0,2,3,5). (a) Truth table. (b) Implementation with 74151A. Aaron Tan, NUS 45 5. Using Smaller Multiplexers (1/6) ▪ Earlier, we saw how a 2n-to-1 multiplexer can be used to implement a Boolean function of n (input) variables. ▪ However, we can use a single smaller 2(n-1)-to-1 multiplexer to implement a Boolean function of n (input) variables. ▪ Example: The function F(A,B,C) = m(1,3,5,6) can be implemented using a 4-to-1 multiplexer (rather than an 8-to-1 multiplexer). Aaron Tan, NUS 46 5. Using Smaller Multiplexers (2/6) ▪ Let’s look at this example: F(A,B,C) = m(0,1,3,6) = A'B'C' + A'B'C + A'BC + ABC' 1 0 1 1 0 2 1 0 1 3 mux F C 1 F 0 4 mux 0 5 0 2 1 6 C' 3 0 7 A B C A B ▪ Note: Two of the variables, A and B, are applied as selection lines of the multiplexer, while the inputs of the multiplexer contain 1, C, 0 and C'. Aaron Tan, NUS 47 5. Using Smaller Multiplexers (3/6) ▪ Procedure 1. Express Boolean function in sum-of-minterms form. Example: F(A,B,C) = m(0,1,3,6) 2. Reserve one variable (in our example, we take the least significant one) for input lines of multiplexer, and use the rest for selection lines. Example: C is for input lines; A and B for selection lines. Aaron Tan, NUS 48 5. Using Smaller Multiplexers (4/6) 3. Draw the truth table for function, by grouping inputs by selection line values, then determine multiplexer inputs by comparing input line (C) and function (F) for corresponding selection line values. MUX A B C F input 0 0 0 1 1 0 1 0 0 1 1 C 1 F mux 0 1 0 0 0 2 C 0 1 1 1 3 1 0 0 0 0 1 0 1 0 A B 1 1 0 1 C' 1 1 1 0 Aaron Tan, NUS 49 5. Using Smaller Multiplexers (5/6) ▪ Alternative: What if we use A for input lines, and B, C for selector lines? A B C F Mux A B C F Input 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 A' (when BC = 00) 0 1 1 1 C 0 1 0 0 1 0 0 0 0 0 1 1 1 A' (when BC = 01) 1 0 1 0 1 1 0 1 1 0 0 0 C’ 1 1 1 0 1 0 1 0 A (when BC = 10) 1 1 0 1 A ? 0 1 1 1 0 ? 1 F A' (when BC = 11) mux ? 2 ? 3 B C Aaron Tan, NUS 50 5. Using Smaller Multiplexers (6/6) ▪ Example: Implement the function below with 74151A: f(x1,x2,x3,x4) = m(0,1,2,3,4,9,13,14,15) Aaron Tan, NUS 51 END
