Basic Concept Throughout this section, we will look only at multiplication techniques for unsigned numbers. Alternatively, the hardware we present is suitable for sign and magnitude multiplication, but we concentrate on the manipulation of the magnitude part. Recall that the two numbers involved in a multiplication are called the multiplicand and the multiplier.
)and the multiplier is 10112
For an n-bit multiplicand and multiplier, the resulting product will be 2n bits. Stated differently, the product of 2n and 2n is 2n + n = 22n, a 2n-bit number. Thus, the product of two 4-bit numbers requires 8 bits, of two 8-bit numbers requires 16 bits, and so on.
Partial Product Accumulation We can construct a combinational circuit that directly implements the process described by the preceding example. The method is called partial product accumulation.
To see how the partial products are accumulated, let's look at the circuit of Figure 5.28 in a little more detail. S1 is the straightforward sum of just two partial products, A1 · B0 and A0 · B1. S2 is the sum of three products. We implement this with two cascaded adders, one of which takes the carry-out from S1's column.
S3 is a little more complicated, because there are two different carry-outs from the previous column. We use three cascaded adders, two full adders and one half adder, to implement the sum. The two carry-outs from S2 are accumulated through the carry-in inputs of the two full adders.
S4 is the sum of three products and three possible carry-outs from S3. The carries make this case more complicated than the S2 sum. The solution is to implement the sum with three adders-two full adders and one half adder. The two full adders sum the three products and two of the carry-outs. The half adder adds to this result the third possible carry-in.
The logic for S5 is similar. Here we must sum two products and three carries. Two full adders do the job. Note that the second full adder sums two of the three carries from the previous column with the result of the first full adder. A similar analysis applies to S7 and S6.
The delay through the multiplier is determined by the ripple carries be-tween the adders. We can use a carry look-ahead scheme to reduce these delays.
Clearly, the full combinational multiplier uses a lot of hardware. The dominating costs are the adders-four half adders and eight full adders. To simplify the implementation slightly, a designer may choose to use full adders for all of the adder blocks, setting the carry input to 0 where the half adder function is required. Given the full adder schematic of Figure 5.7, this is 12 adders of six gates each, for a total of 72 gates. When we add to this the 16 gates forming the partial products, the total for the whole circuit is 88 gates. It is easy to see that combinational multipliers can be justified only for the most high performance of -applications.
)gives the basic building block, a full adder circuit that sums a locally computed partial product
(X · Y
), an input passed into the block from above
), and a carry passed from a block diagonally above. It generates a carry-out
)and a new sum
). Figure 5.29
)shows the interconnection of 16 of these blocks to implement the full multiplier function. The Ai values are distributed along block diagonals and the Bi values are passed along rows. This implementation uses the same gate count as the previous one: 16 AND gates and 12 adders
(the top row does not need adders