Question

Part III -- Enrichment (if you have time) These problems are really good (demonstrate essential concepts), but are a little beyond what we got to in the lectures. El) The shift-and-add multipliers might seem a little slow because they require N iterations. How would you divide that number in half? Clearly you would have to process two multiplier bits every cycle rather than one. What else changes? E2) Our first fully combinational multiplier ("unrolled") is built from ripple carry adders. This basic design idea can be improved substantially by adding as many pairs of partial products in parallel as possible (instead of one at a time). Show such a design. For n-bit operands, how many adders are required? How long does it take? Hint: See Figure 3.7. From P&H 3.28 and B. 32

Answer 1

Solution: Note: Multiple questions asked, more information like mentioned figure is required to solve the problem E2. The answer for El is provided below. E1) In shift and multiply algorithm shift and add will happen "n"iterations since each bit of multiplier *If multiplier bit is "o" shift the product 1 bit right andif bit is "1" add the multiplicand to the left half of the product and place the result in the left half and shift the product to right by 1 bit. o If need to reduce the iteration number to "n/2": o Need to consider two bits of multiplier at a time. o If two bits are consider at a time, then instead of two possibilities we need to consider four possibilities. If bits are "00" .Shift the product two bits right If bits are "01":

Add the multiplicand to product and shift the product two bits * 1l If bits are "10" Shift the product 1 bit right Add the multiplicand to product and shift the product one bit right. * . - If bits are "11": *Add the multiplicand to product and shift the product one bit right, perform this op erationtwo times A special case also needs to be considered, if the length of the multiplier is odd, then last bit has to be processed as the original algorithm o