Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

14.6 SQUARE ROOTERS

This section presents implementations of binary square rooters based on restoring shift-and-subtract Algorithm 7.12, nonrestoring shift-and-subtract Algorithm 7.13, and the Newton–Raphson method of Section 7.4.4.

14.6.1 Restoring Shift-and-Subtract Square Rooter (Naturals)

The circuits presented in Figures 14.20 and 14.21, implementing Algorithm 7.12, are somewhat similar to the restoring divider presented in Chapter 13. Binary 2's complement notation is assumed. The restoring process is achieved by a multiplexer selecting the previous remainder in case of a negative result from the subtraction step. The key difference rests on the expression P(i) to be subtracted from the successive remainder R(i − 1). The final result Q(−1) is built up by concatenation of the complemented sign bits, from q(n − 1) to q(0). The function P(i) is computed as (formula (7.82) of Chapter 7)

To achieve this function (14.38), pseudo-operators are displayed in Figure 14.20 as shifters: they stand for the rules to be respected to connect Q(n − i) to the subtractor input P(i); input P(i) is made up of Q(n − 1), followed, from left to right, by the string ‘01’ then by a string of 2.(n − i) zeros.

At step 1, registers are initialized as

Figure 14.20 Restoring 2n-bit square rooter, combinational ...