FPGA Based Modified Non-Restoring Method to Solve Square Root Problem (Essay Sample)

FPGA BASED MODIFIED NON-RESTORING METHOD TO SOLVE SQUARE ROOT PROBLEM IN DIRECT TORQUE CONTROL
Introduction
It is well-known that the direct torque control method (DTC) for AC motors has simple structure and good behaviours [1-7]. The DTC algorithm is usually implemented by serial calculations based on a Microcontroller or Digital Signal Processing (DSP) [8-11]. These are truly software-based platform and not adequate to implement a control methods which require very high speed response. As a suitable solution, FPGA is proposed to support execution very fast tasks [12-14]. However, it is not easy to implement DTC in FPGA hardware. One problem has been addressed mainly in complicated square root calculation, which is hard to be implemented on Field Programmable Gate Array (FPGA) [15-17].
Many square root calculation techniques have been proposed, such as Rough estimation, Babylonian method, exponential identity, Taylor-series expansion algorithm, Newton-Raphson method, Sweeney Robertson Tocher redundant and non redundant method, restoring and non-restoring algorithm (digit-by-digit method) [16-24]. However, the early processors carry out the square root operation of the algorithms above by software means, which have long delays for its completion [20]. With the rapid advancement of technology which allows the integration of large circuits on a single chip and the increase in demand for faster computational execution time, the hardware realization of square root became more attractive [20]. Unfortunately because of the complexity of the square root algorithms, the square root calculation is not easy to be implemented on FPGA technology [16, 18, 21, 25].
Many strategies or architectures have conducted to implement the non restoring digit-by-digit square root algorithm in FPGA hardware. Yamin and Wanming [18, 22, 24] have introduced a non restoring algorithm with fully pipelined and iterative version that requires neither multipliers nor multiplexors. They introduced the carry save adder (CSA) and the carry propagate adder (CPA) as basic building blocks.
In this section, a strategy to implement non restoring square root algorithm based on FPGA which adopt fully pipelined architecture, will be presented. The main principle of the method is only uses subtract operation and append 01 which is implemented in register transfer level (RTL) abstraction, but add operation and append 11 are not used. In the proposed strategy will needs fewer pipeline stages compared with the proposed algorithm in [26].
Non-restoring algorithm
In non-restoring algorithm, each digit of the square root is found in a sequence where only one digit of the square root is generated at each iteration [20, 22, 27]. It has several advantages, such as: every digit of the root found is known to be correct and it will not to be changed later; if the square root has to expand, it will terminate after the last digit is found; and the algorithm works for any number base (of course the process depends on number base).
In general, this method can be divided in two classes, i.e. restoring and non-restoring digit-by-digit algorithm [20]. In restoring algorithm, the procedure is composed by taking the square root obtained so far, appending 01 to it and subtracting it, properly shifted, from the current remainder. The 0 in 01 corresponds to multiplying by 2; the 1 is a new guess bit. The new root bit developed is truly 1, if the resulting remainder is positive, and vice versa is 0, which the remainder must be restored by adding the quantity just subtracted. While in non-restoring algorithm, the subtraction will not be restored if the result was negative. Instead, 11 will be appended to the root developed so far and on the next iteration it performs an addition. If the addition causes an overflow, then on the next iteration you go back to the subtraction mode [28].
Figure 4.1 (a) and (b) gives an example to take the binary square root of 01011101 (equivalent with 93 decimal) for restoring and non-restoring algorithm respectively. A little modification from the conventional non-restoring digit-by-digit algorithm in Figure 4.1 (b) can be conducted to give simpler implementation and faster calculation, as shown in Figure 4.2. In this modification, it only uses subtraction operation and appends 01, while adding operation and appending 11 is not used.
Figure 4.1 The example of digit-by-digit calculation to solve square root: (a) restoring algorithm; (b) non-restoring algorithm
Figure 4.2 The example of using modified non-restoring digit-by-digit calculation algorithm to solve square root
Modified Non-Restoring Square Root Algorithm
Samawi et al [20] has improved classical non-restoring digit-by-digit square root circuit by eliminate redundant blocks. Their circuit is referred to as the reduced area non restoring circuit. However, it still based on constant digit of 01 or 11 and add-subtract as the main building block (still refer to Figure 4.1 b). This thesis offers a simple alternative solution that it only uses subtracts operation and appends 01. As consequent, the subtract-multiplex is used as the main building block (refer to Figure 4.2). The principle of proposed algorithm can be described as shown in Figure 4.3.
Step 0.Start
Step 1.Initialization radicand (the n-bit number will be squared root), quotient (the result of squared root), and remainder. To calculate square root of a 2n bit number, it needs n stage pipelines to implement the proposed algorithm.
Step 2.Beginning at the binary point, divide the radicand into groups of two digits in both direction.
Step 3.Beginning on the left (most significant bit), select the first group of one or two digit (If n is odd then the first groups is one digit, and vice versa)
Step 4.Choose 1 squared, and then subtract.
Fist developed root is "1" if the result of subtract is positive, and vice versa is "0”
Step 5.Shift two bits, subtract guess squared with append 01.
Nth-bit squared is "1" if the result of subtract is positive, and Because of subtract operation is done
else
Nth-bit squared is "0”, and not subtract
Step 6.Go to step 5 until end group of two digits
Step 7.End
Figure 4.3. The principle of proposed algorithm to solve square root
A simple hardware implementation of the non-restoring digit-by-digit algorithm for unsigned 6-bit square root by an array structure is shown in Figure 4.4. The radicand is P (P5,P4,P3,P2,P1,P0), U (U2,U1,U0) as quotient and R (R4,R3,R2,R1,R0) as remainder. It can be shown that the implementation needs 3 stage pipelines. The main building blocks of the array are blocks called as controlled subtract-multiplex (CSM). Figure 4.5 present the de