O'Reilly logo

Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems by Gustavo D. Sutter, Gery J.A. Bioul, Jean-Pierre Deschamps

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 n2 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 imagen/2image. 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 X2 + C + D; the main difference rests upon the (i, j)-cell loops, adding squares whenever i = j, and adding double products ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required