Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

5.3 SQUARING

5.3.1 Base-B Squaring

Although any multiplication system could readily be used for squaring, specialized systems can provide both time and cost savings. Actually, normal multiplication requires n² partial products while the maximum depth of the adding tree reaches n (maximum column depth in Figure 5.1a). Squaring only needs n(n − 1)/2 partial products, plus n digit-squares. Moreover, the adding process is simplified by the fact that each nonsquare partial product digit appears twice. As far as partial products are multiplied by two beforehand, the maximum depth of the adding tree is reduced to n/2. The complexity of squaring in base B > 2 comes from the fact that digit double products could need up to three digits while squaring only needs two. So the saving in column depth is consumed by second-order carries. For the particular case B = 2, the digit squaring is trivial as double products are performed through straight shifts. Moreover, Boolean simplification provides further reductions in the depth of the adding tree.

5.3.1.1 Cellular Carry–Save Squaring Algorithm

Algorithm 5.16 is a modification of the cellular carry-save Algorithm 5.5. It computes X² + C + D; the main difference rests upon the (i, j)-cell loops, adding squares whenever i = j, and adding double products ...