Computer Arithmetic, MultiplexersSlide 2Bit-Serial and Ripple-Carry AddersSlide 4Slide 5Half-Adder ImplementationsSlide 7Full-Adder ImplementationsSlide 9Radix Conversion: Old-Radix ArithmeticSlide 11Slide 12Signed-Magnitude RepresentationTwo’s- and 1’s-Complement NumbersWhy 2’s-Complement Is the Universal ChoiceSigned-Magnitude vs 2’s-ComplementSome commonly used componentsMultiplexerMUXRemember the 2 – 4 Decoder?4 to 1 MUX4-to-1 MUX (Gate level)Slide 23Example: 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)Slide 31Slide 32Slide 33Slide 34AdderAdditionOne ImplementationBinary addition and our adderWhat about the second column?Truth Table for AdditionComputer Arithmetic, MultiplexersProf. Sin-Min LeeDepartment of Computer ScienceBit-Serial and Ripple-Carry Addersx y c s ---------------- 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 Inputs Outputs HA x y c s Half-adder (HA): Truth table and block diagramx y c c s ---------------------- 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 Inputs Outputs c out c in out in x y s FA Full-adder (FA): Truth table and block diagramHalf-Adder Implementationscs(b) NOR-gate half-adder.xyxy(c) NAND-gate half-adder with complemented carry.xycsscxyxy(a) AND/XOR half-adder.___cThree implementations of a half-adder.Full-Adder ImplementationsHAHAxycincout(a) Built of half-adders.s(b) Built as an AND-OR circuit.(c) Suitable for CMOS realization.coutscinxy0 1 2 30 1 2 3xycincouts01MuxConverting whole part w: (105)ten = (?)fiveRepeatedly divide by five Quotient Remainder 105 0 21 1 4 4 0Therefore, (105)ten = (410)five Converting fractional part v: (105.486)ten = (410.?)fiveRepeatedly multiply by five Whole Part Fraction .486 2 .430 2 .150 0 .750 3 .750 3 .750 Therefore, (105.486)ten (410.22033)five Radix Conversion: Old-Radix ArithmeticRadix Conversion: New-Radix ArithmeticConverting whole part w: (22033)five = (?)ten ((((2 5) + 2) 5 + 0) 5 + 3) 5 + 3 |-----| : : : : 10 : : : : |-----------| : : : 12 : : : |---------------------| : : 60 : : |-------------------------------| : 303 : |-----------------------------------------| 1518 Converting fractional part v: (410.22033)five = (105.?)ten (0.22033)five 55= (22033)five = (1518)ten 1518 / 55= 1518 / 3125 = 0.48576Therefore, (410.22033)five = (105.48576)ten Horner’s rule is also applicable: Proceed from right to left and use division instead of multiplicationHorner’s Rule for FractionsConverting fractional part v: (0.22033)five = (?)ten (((((3 / 5) + 3) / 5 + 0) / 5 + 2) / 5 + 2) / 5 |-----| : : : : 0.6 : : : : |-----------| : : : 3.6 : : : |---------------------| : : 0.72 : : |-------------------------------| : 2.144 : |-----------------------------------------| 2.4288 |-----------------------------------------------| 0.48576Horner’s rule used to convert (0.220 33)five to decimalSigned-Magnitude Representation 0000 0001 1111 0010 1110 0011 1101 0100 1100 1000 0101 1011 0110 1010 0111 1001 0 +1 +3 +4 +5 +6 +7 -7 -3 -5 -4 -0 -1 +2- + _ Bit pattern (representation) Signed values (signed magnitude) +2 -6 Increment Decrement Four-bit signed-magnitude number representation system for integersTwo’s- and 1’s-Complement Numbers 0000 0001 1111 0010 1110 0011 1101 0100 1100 1000 0101 1011 0110 1010 0111 1001 +0 +1 +3 +4 +5 +6 +7 -1 -5 -3 -4 -8 -7 -6 + _ Unsigned representations Signed values (2’s complement) +2 -2 Two’s complement = radix complement system for r = 2 M = 2k 2k – x = [(2k – ulp) – x] + ulp = xcompl + ulpRange of representable numbers in with k whole bits: from –2k–1 to 2k–1 – ulp A 4-bit 2’s-complement number representation system for integers.Why 2’s-Complement Is the Universal ChoiceMux Adder 0 1 x y y or y _ s = x y add/sub ___ c in Controlled complementation 0 for addition, 1 for subtraction c out Adder/subtractor architecture for 2’s-complement numbers.Signed-Magnitude vs 2’s-ComplementAdderccsxySign x Sign ySignSign sSelective ComplementSelective ComplementoutinComp xControl Comp sAdd/SubCompl x ___ Add/Sub Compl s Selective complement Selective complement Two’s-complement adder/subtractor needs very little hardware other than a simple adderFig. 2.7Mux Adder 0 1 x y y or y _ s = x y add/sub ___ c in Controlled complementation 0 for addition, 1 for subtraction c out Signed-magnitude adder/subtractor is significantly more complex than a simple adderSome 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
View Full Document