Review of Binary Multiplication
This document provides a review of unsigned and 2's-complement multiplication. Although there are serial-based multiplication methods using shift registers for partial product addition, we will focus on higher performance methods for parallel addition of partial products. Examples are used to illustrate the methods.
Unsigned binary multiplication is reviewed first. Consider the multiplication of . In base-10, this is . The binary multiplication, by hand, is
In a circuit, the partial products (PPs) can be generated in parallel using AND gates. For example, with a 4-bit multiplicand, , and multiplier, , PP0 is computed as . The offset partial products must be adjusted prior to addition. There are various addition schemes for summing the partial products. One method adds the first two PPs together while adding the last two together using two separate parallel adders. Finally, the two PP sums are added to produce the unsigned product.
When adding the first two PPs, PP0 and PP1, a 5-bit adder is necessary, where a zero is added as the most significant bit (MSB) to the first partial product (PP0), and a zero is added to the second partial product (PP1) as the least significant bit (LSB), thereby bringing the PPs into alignment. The same zero padding is performed for PP2 and PP3, respectively. With carry-out, both adders will produce 6-bit sums. Denote each of these 6-bit sums as PP01 and PP23, respectively. From the example above, and . These PPs, PP01 and PP23, also require alignment before they can be added. Two 0-bits are added as the MSBs for PP01, and two 0-bits are added as low-order bits to PP23. Following alignment, PP01 and PP23 are summed using an 8-bit adder to generate the final 8-bit product. For the example above, the 8-bit product is . Note that for N-bit numbers, a 2N product result will have no carry-out.
Multiplication of 2's-complement numbers is slightly more complicated than unsigned multiplication. Using the same binary values as before, the multiplication is or . As in the unsigned case, we will first sum odd/even PP pairs. To generate the 8-bit 2's-complement product, the circuit must now extend the sign of PP0 and PP2, and, in general, every even-numbered partial product, in order to provide alignment with the next higher odd-numbered partial product. The odd-numbered PPs are padded on the right with a 0-bit. If the multiplier is negative, i.e., the MSB = 1, then the last PP is generated as the 2's-complement of the multiplicand. On paper, with alignment bits added for partial product pairs and the 2's-complement computed for PP3, the multiplication will appear as
Now, the 6-bit partial product sums for and can be computed in parallel using two 5-bit adders with a 6-bit sum. Summing and requires alignment by extending the sign-bit of PP01 by two bits and padding zeros on the right in PP23. PP01 and PP23 are summed using an 8-bit adder. The carry-out is ignored. For the example, the aligned partial products are and . Adding these PPs yields a final product, , with the carry-out of one being ignored.
A single hardware implementation of a signed/unsigned multiplier can be done with a slight degradation in overall speed. Only one input signal, U/S, is required to control the multiplier operation. The U/S signal is low for unsigned multiplication and high for signed or 2's-complement multiplication. The signal controls two basic operations, the extension of the partial product sign-bits and the formation of the 2's-complement of the multiplicand if the MSB of the multiplier is one. The sign extension is controlled as shown in Figure 1, where the -bit extension for PP0 is shown being generated along with the normal bits of PP0. Recall that the sign extension is only applied for even-numbered partial products.
Figure 1. Generation of PP0 for Signed/Unsigned Multiplier
The U/S signal also provides generation of the 2's-complement of the last partial product by first controlling the inversion or 1's-complement of the multiplicand and serving as the carry-in for the adder that adds the last two partial products, PPN-2 and PPN-1. Figure 2 shows the control gating for the last partial product. We assume here that N is even, so the last partial product, PPN-1, is odd-numbered. Adding PPN-2 and PPN-1 requires alignment or padding a low-order bit, PPN-1-1, for PPN-1, as well as, generating the carry-in necessary for the 2’s-complement. The U/S bit, which is high for signed multiplication, along with the multiplier sign bit, bN-1 can be used to provide the correct PPN-1-1 bit value for both unsigned and signed multiplication. The value of the pad bit also determines the correct carry-in value as shown with the AND gate in Figure 2.
Figure 2. Final Partial Product Generation for Signed/Unsigned Multiplier