Shift and Add Multiplication Method in Computer Architecture

Shift and Add Multiplication Method – Multiplication is also one of the most important arithmetic functions. In some large scientific programs, multiplication occurs as frequently as addition and subtraction. Multiplication of two-bit numbers in its simplest form can be performed by adding partial products.

Multiplication with Signed Magnitude Data (Shift and Add Method)

Compared with addition and subtraction, multiplication is a complex operation, whether performed in hardware or software. Multiplication of signed-magnitude integer numbers might be carried out using paper and pencil. Several important observations can be made

1. Multiplication involves the generation of partial products, one for each digit in the multiplier. These partial products are then summed to produce the final product.
2. The partial products can easily be defined. When the multiplier bit is 0, the partial product is 0. When the multiplier bit is 1, the partial product is the multiplicand itself.
3. The final product is produced by summing the partial products. For this, each successive partial product is shifted one position to the left relative to the preceding partial product.
4. The sign of the product is determined from the signs of the multiplicand and multiplier. If they are similar, the sign is positive. If they are different, the sign of the product is negative,
5. The multiplication of two -bit numbers may result in a product of up to 2n bits in length.

Hardware Implementation

When multiplication is implemented in a computer, it is convenient to change the process slightly. First, provide an adder for the summation of two binary numbers and successively accumulate the partial products in a register. Second, instead of shifting the multiplicand to the left, the partial product is shifted to the right. Third, when the multiplier bit is 0, there is no need to add all zeros to the partial product since it will not make any change in its value. Only a shift is required in this case.

The figure below shows a possible implementation of the multiplication of two signed magnitude numbers. The multiplier and multiplicand are loaded into two registers, Q and M. The multiplier sign is stored in Qs, and the multiplicand sign is stored in M_s. There is one more register named the sequence counter. The sequence counter is initially set to the number of bits in the multiplier. The counter is decremented by 1 after completing each partial product. When the content of the counter reaches zero, the product is formed, and the process ends.

There is one more register named register A. This is also needed because the multiplication of two n-bit numbers may have 2n bit length. The register A is initially set to 0.

The operation of multiplication is as follows. Initially, the multiplicand is in register M and the multiplier in register Q. If the least significant bit of register Q (Q₀) is 1, then the multiplicand is added to register A, and the result is stored in register A and the E flip-flop. This is a partial product. Both the partial product and multiplier are shifted to the right. It means the E bit goes into A_n-1, A₀ goes into Q_n-1, and Q₀ is lost. If Q₀ is 0, then no addition is performed; just right shifting is done. This process is repeated for each bit of the original multiplier. The resulting 2n-bit product is contained in the register A and register Q.

Hardware Algorithm

The figure below shows the flow chart of the multiplication algorithm. Initially, the multiplicand is stored in register M, and the multiplier in register Q. Register A is cleared, and flip-flop E is reset. The sequence counter register (SC) is initialized with (n-1), where n is the number of bits in the number. The signs of multiplicand and multiplier are stored in M and Q, respectively.

Right most bit of the multiplier is checked; if it is 1, then the addition of the multiplicand with register A is performed. After that, all the bits of the E, A, and Q registers are shifted to the right by one bit. If right most bit of the multiplier is 0, only the shifting operation is performed. In the flow chart, it is shown with a micro operation, shr EAQ. This is repeated until the whole operation is repeated (n-1) times. The final result is stored in registers A and Q.

Multiplication with 2’s Complement Data (Shift and Add Method)

The 2’s complement multiplication is a pencil and paper method, also known as shift and add multiplication. This method adds the multiplicand to itself multiplier times. This is similar to the previous method as discussed in the previous section, except it ensures that the multiplier is positive. If the multiplier is negative, then replace the contents of the multiplier and multiplicand with their 2’s complement.

Hardware Implementation

Hardware implementation for 2’s complement multiplication is shown in the figure below.

Hardware Algorithm

The figure below shows the flow chart of the multiplication algorithm. Initially, the multiplicand is stored in register M and the multiplier in register Q. If the multiplier is negative, then replace the contents of the multiplier and multiplicand with their 2’s complement. In this way, it is ensured that the multiplier is always positive. Now the sign of the multiplicand is the sign of the final product. The remaining algorithm is identical to the signed magnitude multiplication.

---

Q&A section