Hardware multipliers, based directly on adder architectures, have become indispensable in modern computers. Multiplier circuits are modeled after the “shift and add” algorithm as shown below. In this algorithm, one partial product is created for each bit in the multiplier—the first partial product is created by the LSB of the multiplier, the second partial product is created by the second bit in the multiplier, etc. Partial products are a copy of the multiplicand if the corresponding multiplier bit is a '1', and all 0's if the corresponding multiplier bit is '0'. Each successive partial product is shifted one bit position to the left.
This specific multiplication example is recast in a generalized example on the left below. Each input, partial product digit, and result have been given a logical name, and these same names are used as signal names in the circuit schematics. By comparing the signal names in the multiplication example with the schematics, the behavior of the multiply circuit can be confirmed.
In the circuit above, each bit in the multiplier is AND'ed with each bit in the multiplicand to form the corresponding partial product bits. The partial product bits are fed to an array of full adders (and half adders where appropriate), with the adders shifted to the left as indicated by the multiplication example. The final partial products are added with a CLA circuit. Note that some full-adder circuits bring signal values into the carry-in inputs (instead of carrys from the neighboring stage). This is a valid use of the full-adder circuit; the full adder simply adds any three bits applied to its inputs. You are encouraged to work through a few examples on your own to confirm the adder array and CLA work together to properly sum the partial products. In the lab project, you are asked to implement a multiplier circuit.
As the number of multiplier and multiplicand bits increase, so does the number of adder stages required in the multiplier circuit. It is possible to develop a faster adding array for use in a multiplier by follow a similar line of reasoning as was used in the development of the CLA circuit.