IsraelKoren.ppt

UNIVERSITY OF MASSACHUSETTS Dept. of Electrical Computer EngineeringDigital Computer Arithmetic ECE 666 Part 6b High-Speed Multiplication - II Israel Koren Accumulating the Partial Products After generating partial products either directly or using smaller multipliers Accumulate these to obtain final product A fast multi-operand adder Should take advantage of particular form of partial products - reduce hardware complexity They have fewer bits than final product, and must be aligned before added Expect many columns that include fewer bits than total number of partial products - requiring simpler counters Example - Six Partial Products Generated when multiplying unsigned 6-bit operands using one-bit-at-a-time algorithm 6 operands can be added using 3-level carry-save tree Number of (3,2) counters can be substantially reduced by taking advantage of the fact that all columns but 1 contain fewer than 6 bits Deciding how many counters needed - redraw matrix of bits to be added: Reduce Complexity - Use (2,2) Counters (HAs) Number of levels still 3, but fewer counters Further reduction in number of counters Reduce # of bits to closest element of 3,4,6,9,13,19,… 15 (3,2) and 5 (2,2) vs. 16 (3,2) and 9 (2,2) counters Modified Matrix for Negative Numbers Sign bits must be properly extended In row 1: 11 instead of 6 bits, and so on Increases complexity of multi-operand adder If twos complement obtained through ones complement - matrix increased even further Reduce Complexity Increase Twos complement number s s s s s s z4 z3 z2 z1 z0 with value Replaced by