A simple strategy to solve complicated square root problem in DTC for FPGA implementation

A Simple Strategy to Solve Complicated Square Root Problem in DTC for FPGA Implementation

1Electrical Engineering Dept., Ahmad Dahlan University, Yogyakarta, Indonesia.

Tole Sutikno1, Aiman Zakwan Jidin2, Nik Rumzi Nik Idris3, Auzani Jidin4

2Ecole Supérieure d’Ingénieur en Electronique et Electrotechnique Paris, Paris, France. 3Energy Conversion Dept., Universiti Teknologi Malaysia, Johor Bahru, Malaysia. 4Power Elect. & Drives Dept., Universiti Teknikal Malaysia Melaka, Melaka, Malaysia.

Email: thsutikno@ieee.org, jidina@esiee.fr, nikrumzi@ieee.org, auzani@ieee.org

particularly found in electric drive system applications where square root calculation is normally required.

Specifically, in this paper, calculation of square root for the direct torque control drive will be addressed.

This paper proposes digit-by-digit calculation method as a simple strategy to solve complicated square root calculation implemented using FPGA. The proposed implementation strategy is slightly different from the strategies proposed in [25-29], as will be discussed later. An optimization is also done by eliminating circuitry that is not needed. The method is proposed as part of the development of the controller used in the DTC drive system which is fully based on FPGA.

II. DIGIT-BY-DIGIT CALCULATION METHOD

In digit-by-digit calculation method, each digit of the square root is found in a sequence where only one digit of the square root is generated at each iteration [27-29]. It has several advantages, such as: every digit of the root found is known to be correct and it will not has to be

changed later; if the square root has to be expanded, it will be terminated 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 [29]. 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 1, if the resulting remainder is positive, else it is 0, which the remainder must be restored by adding the quantity just subtracted. It is different from the non restoring algorithm where the subtraction is not restored if the result is

negative. Instead, it appends 11 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 it has to go back to the subtraction mode [30]. Figure 1 (a) and (b) gives an example on how take the binary square root of 01011101 (equivalent with 93 decimal) for restoring and non restoring algorithm respectively.

In this paper, a simple modification to the conventional non-restoring digit-by-digit algorithm is made in order to give a simpler implementation and faster calculation. The conventional method is shown in Figure 1(a) whereas the modification is shown in Figure 1(b). In this modification, only subtract operation with append 01 is used; add

Abstract —This paper presents a digit-by-digit calculation method to calculate the complicated square root problem faced in implementing the direct torque control (DTC) of induction motor drives using Field Programmable Gate Arrays (FPGA). The main principle of the proposed method is based on a two-bit shifter and a subtractor-multiplexor operation that gives simpler implementation and faster calculation. The proposed strategy was successfully

implemented on an FPGA device using unsigned 32 bit and 64-bit binary square root. The strategy can be easily expanded to larger number.

Keywords —Digit-by-Digit Calculation; FPGA; Square Root

I. INTRODUCTION

It is well-known that the direct torque control method (DTC) for AC motors has simple structure and excellent performance such as fast torque response, no requirements for PWM pulse generation and coordinate transformation, no position encoder and does not need current regulators [1-7]. The DTC algorithm is usually implemented based on serial calculations using Microcontroller or Digital Signal Processing (DSP) [8-11]. These are truly software- based platform which may be not fast enough for some applications. For instance, in DTC drive implementation, the stator flux and electric torque have to be estimated in real-time. For hysteresis-based DTC with digital

implementation, it is necessary to have several samplings as the torque error moves from lower to upper (or vice versa) bands in order to avoid large torque ripple. In space vector modulation -based (SVM-based) implementation, other than estimating the torque and flux, the processor has to implement the SVM algorithm as well. These all translate to the need of faster and hence more expensive processors. As an alternative solution to provide a faster calculation for real time flux and torque estimations is to use FPGA based system [12-14]. However, the main drawback in using FPGA in performing the estimation is the complexity. One problem which has been identified in DTC induction motor drive system based on FPGA

implementatio is the complicated square root calculations [15-17].

There are many algorithms which have been proposed to solve the square root calculation problem, such as using Rough estimation [18], Babylonian method [19], exponential identity [20], Taylor-Series Expansion Algorithm [21], Newton-Raphson method [22-24], and sequential algorithm (digit-by-digit calculation method) [25-29]. However, these proposed methods are not

978-1-4244-7647-3/10/$26.00 ©2010 IEEE691

operation and append 11 is not used. This paper adopts this modification to implement unsigned 32 and 64-bit binary square root based on FPGA.

III. PROPOSED SQUARE ROOT ALGORITHM Samavi, et al. [29] has improved classical non-restoring digit-by-digit square root circuit by eliminating the redundant blocks. Their circuit is referred to as the reduced area non restoring circuit. However, it is still

based on constant digit of 01 or 11 and add-subtract as the main building block (Figure 1 b). This paper offers a simple alternative solution that only uses subtract operation and appends 01. Consequently, the subtract- multiplex is used as the main building block (refer to Figure 2). The principle of the proposed algorithm can be described as shown in Figure 3.

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 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. 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 5 present the details of a CSM. Input of the building block is x,y,b and u, and as an output is bo (borrow) and d (result). If u=0, then d<=x-y-b else d<=x.

(a)

Figure 4. A simple hardware implementation of the non-restoring

digit-by-digit algorithm for unsigned 6-bit square root

(b)

Figure 1. The example of digit-by-digit calculation to solve square

root: (a) restoring algorithm; (b) non restoring algorithm

Figure 5. Internal structure of a CSM block

Figure 2. The example of using modified non restoring digit-by-digit

calculation algorithm to solve square root

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.

Figure 6. A simple hardware implementation of the non-restoring

digit-by-digit algorithm for unsigned n-bit square root

692

The generalization of simple implementation of the non-restoring digit-by-digit algorithm for unsigned n-bit square root by an array structure is shown in Figure 6. Each row (stage) of the circuit in Figure 6 executes one- iteration of the non-restoring digit-by-digit square root algorithm, where it only uses subtracts operation and appends 01.

To optimize hardware resource utilization of the implementation, specialized entities can be created as building block components. It will eliminate circuitry that is not needed. As an example, the implementation in Figure 6 for unsigned 6-bit square root can be optimized to become as shown in Figure 7 (in this case, the

remainder is ignored, because in the DTC drive, it is not required). The specialized entities A, B, C, D and E are minimized CSM when input ybu=100, yu=00, u=0,

yu=10, and y=0 respectively, and the remainder is

such that the estimated angle δ exceeds the limit value, the

nd thus can lead to torque may fall with increasing δ a

instability.

The d-q axes components of the stator flux

k-thlinkage,ϕD(k) and ϕQ(k), at the sampling instant can

be calculated as follows:

−+=−−ϕϕ (1) sD1kD1kDDT)iRv()k(

−+=−−ϕϕ (2) sQ1kQ1kQQT)iRv()k(

)k()k()k(2Q2Ds ϕϕϕ+= (3)

ignored. The generalization of optimized simple

implementation of the non-restoring digit-by-digit algorithm for unsigned n-bit square root is shown in Figure 8.

In this paper, equation (3) is addressed as complicated square root problem in DTC for FPGA implementation [15-17]. In Figure 9 which shows the torque and flux estimator design based on FPGA, the need for the 64-bit square root calculation is specifically shown. To solve this problem, optimized simple hardware implementation method of the non-restoring digit-by-digit algorithm is proposed.

Figure 7. Optimized simple hardware implementation of the non- restoring digit-by-digit algorithm for unsigned 6-bit square root

Figure 8. Optimized simple hardware implementation of the non- restoring digit-by-digit algorithm for unsigned n-bit square root

IV. THE CALCULATION OF STATOR FLUX LINKAGE IN DTC OF AC MACHINE DRIVE The most important and difficult task in DTC of AC machine drive in the d-q stationary reference frame is to accurately calculate the stator flux linkage [4-5, 7]. This is because the performance of the DTC drive is highly

dependent on the control of the amplitude and phase of the stator flux linkage, ϕ s and thus require an accurate estimation of these quantities. If the calculation error is

Figure 9. Block diagram of torque and flux estimator design based on

FPGA in fixed point term

V. RESULTS AND ANALYSIS

In the previous sections, optimized simple hardware implementation method of the non-restoring digit-by-digit algorithm for square root and the difficult task in DTC to calculate square root were explained. In this section, simulation results of 32-bit and 64-bit square root based

693