EECC341 - ShaabanEECC341 - Shaaban#1 Final Review Winter 2001 2-20-2002Final Exam Review• Combinational Logic Building Blocks:– Decoders, Encoders, Multiplexers, Demultiplexers– Implementing functions using decoders, multiplexers.• Combinational Arithmetic Circuits:– Adders, Subtractors, Multipliers, Comparators, shifters.• Sequential Logic Circuits:– Latches, Flip-Flips.• Clocked Synchronous State Machines:––State Machine AnalysisState Machine Analysis––State Machine DesignState Machine Design• Registers & Counters.EECC341 - ShaabanEECC341 - Shaaban#2 Final Review Winter 2001 2-20-2002Binary n-to-2Binary n-to-2nn Decoders Decoders• A binary decoder has n inputs and 2n outputs.• Only the output corresponding to the input value is equalto 1.::ninputsn to 2ndecoder2noutputsEECC341 - ShaabanEECC341 - Shaaban#3 Final Review Winter 2001 2-20-20023-to-8 Binary Decoder3-to-8 Binary Decoderx y z F0F1F2F3F4F5F6F70 0 0 1 0 0 0 0 0 0 00 0 1 0 1 0 0 0 0 0 00 1 0 0 0 1 0 0 0 0 00 1 1 0 0 0 1 0 0 0 01 0 0 0 0 0 0 1 0 0 01 0 1 0 0 0 0 0 1 0 01 1 0 0 0 0 0 0 0 1 01 1 1 0 0 0 0 0 0 0 1F1 = x'y'zx zyF0 = x'y'z'F2 = x'yz'F3 = x'yzF5 = xy'zF4 = xy'z'F6 = xyz'F7 = xyzTruth Table: 3-to-8DecoderXYF0F1F2F3F4F5F6F7ZEECC341 - ShaabanEECC341 - Shaaban#4 Final Review Winter 2001 2-20-2002Implementing Functions Using Decoders• Any n-variable logic function, in canonical sum-of-mintermsform can be implemented using a single n-to-2n decoder togenerate the minterms, and an OR gate to form the sum.– The output lines of the decoder corresponding to the mintermsof the function are used as inputs to the or gate.• Any combinational circuit with n inputs and m outputs can beimplemented with an n-to-2n decoder with m OR gates.• Suitable when a circuit has many outputs, and each outputfunction is expressed with few minterms.EECC341 - ShaabanEECC341 - Shaaban#5 Final Review Winter 2001 2-20-2002Implementing Functions Using Decoders• Example: Full adderS(x, y, z) = Σ (1,2,4,7)C(x, y, z) = Σ (3,5,6,7)3-to-8DecoderS2S1S0xyz01234567SCx y z C S0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1EECC341 - ShaabanEECC341 - Shaaban#6 Final Review Winter 2001 2-20-2002Encoders• If the a decoder's output code has fewer bits than theinput code, the device is usually called an encoder. e.g. 2n-to-n, priority encoders.• The simplest encoder is a 2n-to-n binary encoder, where ithas only one of 2n inputs = 1 and the output is the n-bitbinary number corresponding to the active input.• For an 8-to-3 binay encoder with inputs I0-I7 the logicexpressions of the outputs Y0-Y2 are: Y0 = I1 + I3 + I5 + I7 Y1= I2 + I3 + I6 + I7 Y2 = I4 + I5 + I6 +I7......2ninputsn outputsBinaryencoderEECC341 - ShaabanEECC341 - Shaaban#7 Final Review Winter 2001 2-20-20028-to-3 Binary Encoder8-to-3 Binary EncoderAt any one time, only one input line has a value of 1.Inputs OutputsI0I1I2I3I4I5I6I7y2y1y01 0 0 0 0 0 0 0 0 0 00 1 0 0 0 0 0 0 0 0 10 0 1 0 0 0 0 0 0 1 00 0 0 1 0 0 0 0 0 1 10 0 0 0 1 0 0 0 1 0 00 0 0 0 0 1 0 0 1 0 10 0 0 0 0 0 1 0 1 1 00 0 0 0 0 0 0 1 1 1 1I0I1I2I3I4I5I6I7Y0 = I1 + I3 + I5 + I7y1 = I2 + I3 + I6 + I7Y2 = I4 + I5 + I6 + I7EECC341 - ShaabanEECC341 - Shaaban#8 Final Review Winter 2001 2-20-2002Multiplexers• A multiplexer (MUX) is a digital switches whichconnects data from one of n sources to the output.• A number of select inputs determine which data source isconnected to the output.Multiplexerb bitsb bitsb bits..Dataoutputn DataSourcess bitsSelectEnable ENSELD0D1Dn-1YEN...D0D1Dn-1...1Y2YbYSELEECC341 - ShaabanEECC341 - Shaaban#9 Final Review Winter 2001 2-20-20024-to-1 MUXTruth table for a 4-to-1 multiplexer:mux YInputsselectS1 S0I0I1I2I3I0I1I2I3S1S0Yd0d1d2d30 0 d0d0d1d2d30 1 d1d0d1d2d31 0 d2d0d1d2d31 1d3S1S0Y0 0 I00 1 I11 0 I21 1I34:1MUXYInputsselectS1 S0I0I1I2I30123OutputEECC341 - ShaabanEECC341 - Shaaban#10 Final Review Winter 2001 2-20-20024-to-1 MUX CircuitS1S00 1 2 32-to-4DecoderI0I1I2I3YS1S0I0I1I2I3YEECC341 - ShaabanEECC341 - Shaaban#11 Final Review Winter 2001 2-20-2002Larger Multiplexers• Larger multiplexers can be constructed from smaller ones.• An 8-to-1 multiplexer can be constructed from smallermultiplexers as shown:4:1MUXI0I1I2I3S1 S04:1MUXI4I5I6I7S1 S02:1MUXS2YS2S1S0Y0 0 0 I00 0 1 I10 1 0 I20 1 1 I31 0 0 I41 0 1 I51 1 0 I61 1 1 I7EECC341 - ShaabanEECC341 - Shaaban#12 Final Review Winter 2001 2-20-2002Larger Multiplexers• A 16-to-1 multiplexer can beconstructed from five 4-to-1multiplexers:EECC341 - ShaabanEECC341 - Shaaban#13 Final Review Winter 2001 2-20-2002Demultiplexers• Digital switches to connect data from one input source to oneof n outputs.• Usually implemented by using n-to-2n binary decoders wherethe decoder’s enable line is used for data input of thedemultiplexer. 2X4DecoderSelectlinesInputdata (1bit)EnableOne offour 1-bitoutputsOne of n DataSourcesselecteds bitsSelectb bitsb bitsb bits..DataInputDemuxOne of n outputs1-bit 4-output demultiplexer using a 2x4 binary decoder.EECC341 - ShaabanEECC341 - Shaaban#14 Final Review Winter 2001 2-20-20021-to-4 1-to-4 DemultiplexerDemultiplexerS1SoY0Y1Y2Y30 0 D 0 0 00 1 0 D 0 01 0 0 0 D 01 1 0 0 0 DdemuxData DOutputsselectS1 S0Y0 = D.S1'.S0'Y1 = D.S1'.S0Y2 = D.S1.S0'Y3 = D.S1.S02x4DecoderDS1S0Y0 = D.S1'.S0'Y1 = D.S1'.S0Y2 = D.S1.S0'Y3 = D.S1.S0EEECC341 - ShaabanEECC341 - Shaaban#15 Final Review Winter 2001 2-20-2002Implementing n-variable Functions Using2n-to-1 Multiplexers• Any n-variable logic function, in canonical sum-of-minterms form can be implemented using a single 2n-to-1multiplexer:– The n input variables are connected to the muxselect lines.– For each mux data input line Ii ( 0 ≤≤ i ≤ ≤ 2n - 1):• Connect 1 to mux input line Ii if i is a minterm of thefunction.• Otherwise, connect 0 to mux input line Ii (because i isnot a minterm of the function thus the selected inputshould be 0).EECC341 - ShaabanEECC341 - Shaaban#16 Final Review Winter 2001 2-20-2002Example: 3-variable Function Using 8-to-1 mux• Implement the function F(X,Y,Z) = ΣΣ(1,3,5,6) usingan 8-to-1 mux.– Connect the input variables X, Y, Z to mux select lines.– Mux data input lines 1, 3, 5, 6 that correspond to functionminterms are connected to 1.– The remaining mux data input lines 0, 2, 4, 7 are connected to 0.muxX Y Z0123456701010110 FMux