Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-1Arithmetic Circuits(Part II)Randy H. KatzUniversity of California, BerkeleySpring 2004Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-2Overview•BCD Circuits•Combinational Multiplier Circuit•Design Case Study: 8 Bit Multiplier•Sequential Multiplier CircuitContemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-3BCD AdditionBCD Number RepresentationDecimal digits 0 thru 9 represented as 0000 thru 1001 in binaryAddition:5 = 01013 = 00111000 = 85 = 01018 = 10001101 = 13!Problemwhen digitsum exceeds 9Solution: add 6 (0110) if sum exceeds 9!5 = 01018 = 100011016 = 01101 0011 = 1 3 in BCD9 = 10017 = 01111 0000 = 16 in binary6 = 01101 0110 = 1 6 in BCDContemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-4BCD AdditionAdder DesignAdd 0110 to sum whenever it exceeds 1001 (11XX or 1X1X)F A F A F A F A F A F A Cin A 3 A 2 A 1 A 0 B 3 B 2 B 1 B 0 Cout S 3 S 2 S 1 S 0 0 CO CI S CO CI S CO CI S CO CI S CO CI S CO CI S 1 1XX A1 A2 1X1X Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-5Combinational MultiplierBasic Conceptmultiplicandmultiplier1101 (13)1011 (11)1101110100001101*10001111(143)Partial productsproduct of 2 4-bit numbersis an 8-bit numberContemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-6Combinational MultiplierPartial Product AccumulationA0B0A0 B0A1B1A1 B0A0 B1A2B2A2 B0A1 B1A0 B2A3B3A2 B0A2 B1A1 B2A0 B3A3 B1A2 B2A1 B3A3 B2A2 B3A3 B3S6S5S4S3 S2S1 S0S7Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-7Combinational MultiplierPartial Product AccumulationNote use of parallel carry-outs to form higher order sums12 Adders, if full adders, this is 6 gates each = 72 gates16 gates form the partial productstotal = 88 gates!A 0 B 0 A 1 B 0 A 0 B 1 A 0 B 2 A 1 B 1 A 2 B 0 A 0 B 3 A 1 B 2 A 2 B 1 A 3 B 0 A 1 B 3 A 2 B 2 A 3 B 1 A 2 B 3 A 3 B 2 A 3 B 3 HA S 0 S 1 HA F A F A S 3 F A F A S 4 HA F A S 2 F A F A S 5 F A S 6 HA S 7 Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-8Combinational MultiplierAnother Representation of the CircuitA3 B0SCA2 B0SCA1 B0SCA0 B0SCA3 B1SCA2 B1SCA1 B1SCA0 B1SCA3 B2SCA2 B2SCA1 B2SCA0 B2SCA3 B3SCA2 B3SA1 B3SA0 B3SB0B1B2B3P7 P6 P5 P4 P3 P2 P1 P0A3 A2A1A0Building block: full adder + and4 x 4 array of building blocksF A X Y A B S CI CO Cin Sum In Sum Out Cout Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-9Case Study: 8 x 8 MultiplierTTL MultipliersTwo chip implementation of 4 x 4 multipler2 8 4 A 3 A 2 A 1 A 0 B 3 B 2 B 1 B 0 Y 7 Y 6 Y 5 Y 4 G A G B 2 8 5 A 3 A 2 A 1 A 0 B 3 B 2 B 1 B 0 Y 3 Y 2 Y 1 Y 0 G A G B 7 7 A 2 13 14 13 14 5 5 A 0 6 6 A 1 4 4 A 3 3 15 B 0 2 1 B 1 1 2 B 2 15 3 B 3 12 Y 4 9 Y 3 9 Y 7 10 Y 6 1 1 Y 5 12 Y 0 1 1 Y 1 10 Y 2 Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-10Case Study: 8 x 8 MultiplierProblem DecompositionHow to implement 8 x 8 multiply in terms of 4 x 4 multiplies?A7-4B7-4A3-0B3-0*A3-0 * B3-0A7-4 * B3-0A3-0 * B7-4A7-4 * B7-4= PP0= PP1= PP2= PP3P15-12 P11-8 P7-4 P3-08 bit productsP3-0 = PP0P7-4 = PP0 + PP1 + PP2P11-8 = PP1 + PP2 + PP3P15-12 = PP33-03-03-0 3-07-4 7-43-07-4+ Carry-in+ Carry-in+ Carry-inContemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-11Case Study: 8 x 8 MultiplierCalculation of Partial ProductsUse 4 74284/285 pairs to create the 4 partial products4 x 4 Multiplier 74284/285A7A6A5A4B7B6B5B4PP37-4PP33-04 x 4 Multiplier 74284/285A3A2A1A0B7B6B5B4PP27-4PP23-04 x 4 Multiplier 74284/285A7A6A5A4B3B2B1B0PP17-4PP13-04 x 4 Multiplier 74284/285A3A2A1A0B3B2B1B0PP07-4PP03-0Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-12Case Study: 8 x 8 MultiplierThree-At-A-Time Adde rClever use of the Carry InputsSum A[3-0], B[3-0], C[3-0]:Two Level Full Adder CircuitNote: Carry lookahead schemes also possible!FAFAA0 B0C00S0FAFAA1 B1S1C1FAFAA2 B2C2S2FAA3 B3S3C3Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-13Case Study: 8 x 8 MultiplierThree-At-A-Time Adder with TTL ComponentsFull Adders(2 per package)Standard ALU configured as 4-bitcascaded adder (with internal carry lookahead)Note the off-set in the outputsB3 A3 B2 A2 B1 A1 B0 A0F3 F2 F1 F0CnGPCn+474181+Cn B ACn+1 S74183Cn B ACn+1 S74183Cn B ACn+1 S74183Cn B ACn+1 S74183S0S1S2S3A0B0C0A1B1C1A2B2C2A3B3C3Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-14Case Study: 8 x 8 MultiplierAccumulation of Partial ProductsJust a case of cascaded three-at-a-time adders!B3 A3 B2 A2 B1 A1 B0 A0F3 F2 F1 F0CnGPCn+474181+Cn B ACn+1 S74183Cn B ACn+1 S74183Cn B ACn+1 S74183Cn B ACn+1 S74183P4P5P6P7PP04PP10PP20PP05PP11PP21PP06PP12PP22PP07PP13PP23B3 A3 B2 A2 B1 A1 B0 A0F3 F2 F1 F0CnGPCn+474181Cn B ACn+1 S74183Cn B ACn+1 S74183Cn B ACn+1 S74183Cn B ACn+1 S74183P8P9P10P11PP14PP24PP30PP15PP25PP31PP16PP22PP32PP17PP27PP33B3 A3 B2 A2 B1 A1 B0 A0F3 F2 F1 F0CnGPCn+474181P13P14P15P12PP34PP35PP36PP37Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-15Case Study: 8 x 8 MultiplierThe Complete SystemPartial Product Calculation 4 x 74284, 742858A7-08B7-04PP37-44PP33-04PP27-44PP23-04PP17-44PP13-04PP07-44PP03-0P3-0+P4P5P6P7P8GPCn+4Cn2 x 7418374181P9P10P11P12GPCn+4Cn2 x 7418374181P13P14P15GPCn+4Cn741814 444440 PP34PP3PP3PP3756Cn+xCn74182G0P0G1P1G2 P2G3P3Cn+yCn+z+Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-16Case Study: 8 x 8 MultiplierPackage Count and Performance4 74284/74285 pairs = 8 packages4 74183, 3 74181, 1 74182 = 8 packages 16 packages total Partial product calculation (74284/285) = 40 ns typ, 60 ns maxIntermediate sums (74183) = 9 ns/20ns = 15 ns average, 33 ns maxSecond stage sums w/carry lookahead74LS181: carry G and P = 20 ns typ, 30 ns max74182: second level carries = 13 ns typ, 22 ns max74LS181: formations of sums = 15 ns typ, 26 ns max103 ns typ, 171 ns maxContemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 18-17Sequential Multiplier• 4-Bit Multiplier Example: 3 x 4 = 12– Four cycles to completionCycle Multiplier Multiplicand ProductInitialize 0011 0000 0100 0000 0000Cycle 0, Multiplier[0]=1 0001 0000 1000 0000 0100Cycle 1, Multiplier[0]=1 0000 0001 0000 0000 1100Cycle 2, Multiplier[0]=0 0000
View Full Document
Unlocking...