Revision Problems 2Example of combinational and sequential logicBasicallySlide 4Slide 5Slide 6Some commonly used componentsMultiplexerMUXRemember the 2 – 4 Decoder?4 to 1 MUX4-to-1 MUX (Gate level)Slide 13Example: Quad 2-to-1 MUXImplementing Boolean functions with MultiplexersExampleEfficient Method for implementing Boolean functionsAnother ExampleMUX Example (cont.)MUX implementation of F(A,B,C) = m(1,3,5,6)1 input DecoderSlide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30AdderAdditionOne ImplementationBinary addition and our adderWhat about the second column?Truth Table for Addition1 bit adder (3 inputs!)New Component: 1 Bit AdderBuilding a 32 bit Adder4 Bit Ripple Carry AdderSlide 41SubtractionSlide 43Slide 44Slide 45Slide 46Two’s Complement NumbersSlide 48Slide 49Ripple Carry TimingCarry Look-aheadSlide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Combinational circuit implementation using MUXSlide 71Slide 72Slide 73Slide 74Example of MUX combo circuitSlide 76Slide 77Slide 78Revision Problems 2Prof. Sin-Min LeeDepartment of Computer ScienceBACClockExample of combinational and sequential logic•Combinational:–input A, B–wait for clock edge–observe C–wait for another clock edge–observe C again: will stay the same•Sequential:–input A, B–wait for clock edge–observe C–wait for another clock edge–observe C again: may be differentBasically•Combinational:–No internal state (or memory or history or whatever you want to call it)–Output depends only on input•Sequential:–Output depends on internal state–Probably not going to be on this midterm since formal lecture on it started last Thursday.Some commonly used components•Decoders: n inputs, 2n outputs.–the inputs are used to select which output is turned on. At any time exactly one output is on.•Multiplexors: 2n inputs, n selection bits, 1 output.–the selection bits determine which input will become the output.•Adder: 2n inputs, 2n outputs. –Computer Arithmetic.Multiplexer•“Selects” binary information from one of many input lines and directs it to a single output line.•Also known as the “selector” circuit,•Selection is controlled by a particular set of inputs lines whose # depends on the # of the data input lines.•For a 2n-to-1 multiplexer, there are 2n data input lines and n selection lines whose bit combination determines which input is selected.MUX2n DataInputsDataOutputInputSelectnEnableRemember the 2 – 4 Decoder?S1S0Sel(3)Sel(2)Sel(1)Sel(0)Mutually Exclusive(Only one O/P asserted at any time4 to 1 MUX2 - 4 DecoderControlDataFlowD3:D04Sel(3:0)4S1:S02Dout4-to-1 MUX (Gate level)Three of these signal inputs will always be 0. The other will depend on the data value selectedControl Section•Until now, we have examined single-bit data selected by a MUX. What if we want to select m-bit data/words? Combine MUX blocks in parallel with common select and enable signals•Example: Construct a logic circuit that selects between 2 sets of 4-bit inputs (see next slide for solution).Multiplexer (cont.)Example: Quad 2-to-1 MUX•Uses four 4-to-1 MUXs with common select (S) and enable (E).•Select line chooses between Ai’s and Bi’s. The selected four-wire digital signal is sent to the Yi’s•Enable line turns MUX on and off (E=1 is on).Implementing Boolean functions with Multiplexers•Any Boolean function of n variables can be implemented using a 2n-1-to-1 multiplexer. A MUX is basically a decoder with outputs ORed together, hence this isn’t surprising.•The SELECT signals generate the minterms of the function.•The data inputs identify which minterms are to be combined with an OR.Example•F(X,Y,Z) = X’Y’Z + X’YZ’ + XYZ’ + XYZ = Σm(1,2,6,7)•There are n=3 inputs, thus we need a 2222-to-1 MUX-to-1 MUX•The first n-1 (=2) inputs serve as the selection linesThe first n-1 (=2) inputs serve as the selection linesEfficient Method for implementing Boolean functions•For an n-variable function (e.g., f(A,B,C,D)):–Need a 2n-1 line MUX with n-1 select lines.–Enumerate function as a truth table with consistent ordering of variables (e.g., A,B,C,D)–Attach the most significant n-1 variables to the n-1 select lines (e.g., A,B,C)–Examine pairs of adjacent rows (only the least significant variable differs, e.g., D=0 and D=1).–Determine whether the function output for the (A,B,C,0) and (A,B,C,1) combination is (0,0), (0,1), (1,0), or (1,1).–Attach 0, D, D’, or 1 to the data input corresponding to (A,B,C) respectively.Another Example•Consider F(A,B,C) = m(1,3,5,6). We can implement this function using a 4-to-1 MUX as follows.•The index is ABC. Apply A and B to the S1 and S0 selection inputs of the MUX (A is most sig, S1 is most sig.)•Enumerate function in a truth table.MUX Example (cont.)A B C F0 0 0 00 0 1 10 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0When A=B=0, F=CWhen A=B=0, F=CWhen A=0, B=1, When A=0, B=1, F=CF=CWhen A=1, B=0, When A=1, B=0, F=CF=CWhen A=B=1, When A=B=1, F=C’F=C’MUX implementation of F(A,B,C) = m(1,3,5,6)AABBCCCCCCC’C’FF1 input DecoderDecod erIO1O0Treat I as a 1 bit integer i. The ith output will be turned on (Oi=1), the other one off.1 input DecoderIO1O02 input DecoderDecod erI0I1O0O2O1O3Treat I0I1 as a 2 bit integer i. The ith output will be turned on (Oi=1), all the others off.I1I0O0 = !I0 && !I12 input DecoderO1 = !I0 && I1O2 = I0 && !I1O3 = I0 && I13 Input DecoderDecoderI0I1O0O2O1O3O4O6O5O7I23-Decoder Partial ImplementationI2I1O0I0O1. . .2 Input MultiplexorInputs: I0 and I1Selector: SOutput: OIf S is a 0: O=I0If S is a 1: O=I1MuxI0I1OS2-Mux Logic DesignI1I0SOI0 && !SI1 && S4 Input MultiplexorInputs: I0 I1 I2 I3Selectors: S0 S1Output: OMuxI0I2OS0S0S1O0 0 I00 1 I11 0 I21 1 I3I1I3S1One Possible 4-Mux2-DecoderI0I1I2I3S0S1OAdder•We want to build a box that can add two 32 bit numbers.–Assume 2s complement representation•We can start by building a 1 bit adder.Addition•We need to build a 1 bit adder–compute binary addition of 2 bits.•We already know that the result is 2 bits.A B O0O10 0 0 00 1 0 11 0 0 11 1 1 0A + B O0 O1This is addition!One ImplementationABO0!ABA!BO1A && B(!A && B) || (A && !B)Binary addition and our adderWhat we really want is something that can be used to implement the binary addition algorithm. –O0 is the carry–O1 is the sum 01001+ 011011011011
View Full Document
Unlocking...