Wiktor Jakowluk
email: w.jakowluk@pb.edu.pl

Optimal input signal design for a second order dynamic system identification subject to D-efficiency constraints

Keywords: system identification, optimal input signal, D-optimality, D-efficiency

System identification, in practice, is carried out by perturbing processes or plants under operation. That is why in many industrial applications an optimal input signal would be preferred for system identification. In this case, the objective function was formulated through maximisation of the Fisher information matrix determinant (D-optimality) expressed in conventional Bolza form. As setting such conditions of the identification experiment we can only say about the D-suboptimality, we quantify the plant trajectories using the Defficiency measure. An additional constraint, imposed on D-efficiency of the solution, should allow to attain the most adequate contents of information from the plant which operating point is perturbed in the least invasive way. A simple numerical example, which clearly demonstrates the idea presented in the paper, is included and discussed.

Introduction

The choice of an input signal used for actuation of the system is critical in the task of model building and parameter identification. System identification is the process of constructing an accurate and reliable dynamic mathematical model of the system from observed data and available knowledge. It is a common practice to perturb the system of interest and use the resulting data to build the model [START_REF] Ljung | System identification: Theory for the user[END_REF][START_REF] Pintelon | System identification: A frequency domain approach[END_REF]. The accuracy of parameter estimates is increased by the use of optimal excitation signals [START_REF] Kalaba | Control, identification, and input optimization[END_REF].

The pertinence of a model is the critical factor for proper tuning of a controller, usually performed as a model-based optimisation task. Inaccurate model can significantly influence the performance of the control loop, and finally deteriorate the quality of the plant product. The control performance assessment has a large impact on the economic aspect of the production process. It was found that about 66% -80% of the advanced control systems are not able to achieve the desired performance [START_REF] Hugo | Process controller performance monitoring and assessment[END_REF].

The input design problem with respect to the intended model application, which is often a control task, has received considerable attention in the last two decades [START_REF] Hildebrand | Identification for control: Optimal input design with respect to worst-case v-gap cost function[END_REF][START_REF] Pronzato | Optimal experimental design and some related control problems[END_REF].

It was reported that model development absorbs about 75% of the costs associated with advanced control projects [START_REF] Hussain | Review of the applications of neural networks in chemical process controlsimulation and on-line implementation[END_REF]. System identification, in practice, is carried out by perturbing processes or plants under operation. In many industrial applications a plant friendly input signal would be preferred for system identification. Plant friendly identification experiments are those that satisfy plant or operator constraints on experiment duration, input and output amplitudes or input rate [START_REF] Narasimhan | Multi-objective input signal design for plant friendly identification of process systems[END_REF][START_REF] Narasimhan | Multi-objective optimal input design for plant friendly identification[END_REF]. Techniques for synthesising multi-harmonic signals with low crest factors, which are attractive from a plant friendly perspective, have been reported in [START_REF] Pintelon | System identification: A frequency domain approach[END_REF]. It was demonstrated that plant friendliness demands are often in conflict with requirements for accurate and reliable identification [START_REF] Rivera | Plant friendly system identification: A challenge for the process industries[END_REF]. Hence, plant friendly input design is inherently multi-objective in nature. There have been some reports on multi-objective optimisation based methods, applied to identification and control [START_REF] Steenis | Plant-Friendly Signal Generation for System Identification Using a Modified Simultaneous Perturbation Stochastic Approximation (SPSA) Methodology[END_REF][START_REF] El-Kady | Numerical treatment of multiobjective optimal control problems[END_REF].

However, the papers mentioned above present the optimisation methods of designing the parametric signals which meet the assumed friendliness criteria. In the experiments described in this paper we present different approacha design of an optimal input signal via the optimisation procedure with respect to the cost function D-efficiency constraint has been attempted. In some our previous works, in the design of optimal and plant friendly inputs for system identification the sensitivity of the state variable to the unknown parameter has been maximised. The results of optimal and plant friendly input signal design utilising Mayer's canonical formulation of the performance index for the simple first-order inertial system case study were presented in [START_REF] Jakowluk | Design of an optimal input signal for plant-friendly identification of inertial systems[END_REF][START_REF] Jakowluk | Plant friendly input design for parameter estimation in an inertial system with respect to D-efficiency constraints[END_REF]. In this study we present the formulation of the performance index for optimal dynamic system identification and assess the qualitative measure of accuracy of parameter estimation in the second-order torsional spring system case study. In order to design an optimal actuation signal for the one degree of freedom torsional spring system parameter estimation, it was necessary to scale the model of the system. One of the problems to be solved was to find the value of the scaling factor between the angular position and the angular velocity of the real plant.

2

The D-efficiency constraint formulation

In the paper the design of optimal inputs for system identification with multiple unknown parameters is considered. In the design of optimal excitation signals for estimating more than one parameter, a suitable scalar function of the Fisher information matrix M must be selected as the performance criterion. The criterion, which is often used, is the trace of the matrix M, wherein the sum of diagonal elements of the Fisher information matrix is maximised. Other measures of identification performance are as follows [START_REF] Atkinson | Optimum experimental design with SAS[END_REF]:

 A-optimality: tr(M -1 ), minimises the average variance of the parameters,  E-optimality: max(M -1 ), minimises the maximum eigenvalue of M -1 ,  D-optimality: minimises the volume of the ellipsoidal confidence region of parameter estimates.

However, the choice of the experiment criterion is important, as it is possible that inputs obtained based on some criteria may not be persistently perturbing [START_REF] Ljung | System identification: Theory for the user[END_REF].

The input signal employed in the identification experiment should simultaneously yield two results: the acceptable accuracy of the system parameter estimates and the system should be perturbed in the least invasive (the most friendly) way. Such a compromise can be reached applying an approach, which relies on the notion of the D-efficiency [START_REF] Atkinson | Optimum experimental design with SAS[END_REF]. Any optimality criterion can be associated with the efficiency function, defined as a measure of the relative performance of any given experiment e compared to that of the optimal experiment e * . The D-efficiency, which may be considered as a measure of the D-suboptimality of given input trajectories, is specified by

          , det det 1 * k D E        e M e M e ( 1
)
where k is the number of parameters to be identified, and e * stands for the D-optimal trajectories which can be determined earlier. Following the reasoning and derivations presented in [START_REF] Uciński | Sensor Motion Planning in Distributed Parameter Systems Using Turing's Measure of Conditioning[END_REF], we set a reasonable positive threshold  < 1 and impose the constraint on the D-efficiency value:

  .   e D E . (2)
Such an approach will yield a D-suboptimal, yet reasonable solution. The inequality (2) is equivalent to the constraint:

    , D   e M (3)
where

        e M e M det log   and        log * k D    e M
. The objective of such an experiment is formulated through maximisation of the FIM determinant (D-optimality) with respect to D-efficiency inequality constraint [START_REF] Kalaba | Control, identification, and input optimization[END_REF].

The purpose of the current work is to formulate the optimisation problem for optimal input design with respect to the D-efficiency constraint. In that way (i.e. by setting such a constraint to control the level of the D-optimality loss) we can obtain the friendliest input signal, reducing the rapid changes of the mass or energy inflow to the system.

Optimal input design with respect to the cost function Defficiency constraints

To illustrate the properties of the above approach to parameter identification, using the optimal input signal and with respect to the assumed level of D-optimality, we have selected the second-order linear dynamic system. The mass-spring damper system represents many similar physical plants. Thus the plant model order may be as high as six with either four, two, or no zeros.

The dynamic model for the one degree of freedom (1 DOF) plant is shown in below figure. The equation of motion is as follows:

 ,

1 1 1 1 1 t T k c J          ( 4
)
where J1, k1, c1, T(t), 1 are, respectively: disk inertia, spring coefficient, damping ratio, force signal, position of the first disk of the plant. For notational convenience, let us introduce

1 1   x and 1 1 2 x x     
. Then, the problem of synthesising an optimal input in the time domain for a torsional spring plant (1 DOF) can be described by the following single input, single output state space model:

       , ; 0 0 ; ; 0 ; 1 2 2 1 2 10 1 2 1 t x t y x cu bx ax x x x x x          (5)
where a = -k1/J1, b = -c1/J1, c = 1/J1. In order to design an optimal input signal, it was necessary to scale the model of the system as follows:

. 1

; 1 2 2 2 2 1 1 1 1         g x gx p x px       (6)
Utilising equation ( 6), the state space model ( 5) can be expressed as: . ;

2 1 2 2 1 cgu b p g a g p            . ( 7
)
Assuming that the parameter p = 1, from equation ( 6) we obtain 1 = x1. Then the above problem can be suitably modified by defining the state space model as:

   , ; ; 1 1 2 1 2 2 1 t x t y cgu bx agx x x g x        (8)
where x1 = x1(t; a, b, c), x2 = x2(t; a, b, c) and model parameters a, b, c are constant. The principle of the design of optimal input signals for system identification is to maximise the sensitivity of the state variable or the observation to the unknown parameter [START_REF] Kalaba | Control, identification, and input optimization[END_REF]. The justification for this approach is the Cramer-Rao lower bound, which provides a lower bound for the estimation error covariance. Providing this feature of the input, we obtain the parameter estimate or observation sensitivity which tends to be lowered for an optimal input

    . , , cov 1 M   c b a ( 9
)
The Fisher information matrix (FIM) for the torsional spring (1 DOF) model ( 8) can be expressed as:

    , 0 2 2 2 1 1 1 2 2 2 1 1 1                       T c b a c b a c b a c b a dt x x x x x x x x x x x x T M (10)
where: xia = xi/a, xib = xi/b, xic = xi/c, i = 1, 2.

Then the problem can be suitably modified by defining the augmented state equations as [START_REF] Kalaba | Control, identification, and input optimization[END_REF]:

                    . 0
                                x gu bx gax x x x x bx x ax g x x x x bx ax x g x x x x x g x x x x x g x x x x x g x x x x cgu bx agx x x x x x x g x x x c b a c b a         (11)
An optimal input for exciting the torsional spring (1 DOF) system is formulated through maximisation of the Fisher information matrix determinant (D-optimality) in the form of a conventional integral-criterion optimal control problem. The problem of synthesising an optimal input signal for an inertial system, utilising Mayer's canonical formulation of the performance index, has been solved in literature [START_REF] Jakowluk | Design of an optimal input signal for plant-friendly identification of inertial systems[END_REF][START_REF] Jakowluk | Plant friendly input design for parameter estimation in an inertial system with respect to D-efficiency constraints[END_REF]

    , // 0 2 2 2 1 1 1 2 2 2 1 1 1                       t c b a c b a c b a c b a dt d d x x x x x x x x x x x x t  M ( 12
)
the FIM can be modified as follows:

      , 0 0 , 2 2 2 1 1 1 2 2 2 1 1 1                       M M c b a c b a c b a c b a x x x x x x x x x x x x t  (13)
where

          , 66 61 16 11            t m t m t m t m t      M ( 14
)
and mij = mji.

Then the equivalent optimal control problem utilising Mayer's canonical formulation, which maximises the performance index with respect to the D-efficiency equality constraint, is

   , det f T J M  ( 15
)
subject to:

     , , 0 , 5 ) ( 5 ; det T t t u D T f      M ( 16
)
where D is D-efficiency constant.

Experimental results for torsional spring case study

For numerical solution of the above optimal control problems one of existing packages for solving dynamic optimisation tasks, such as Riots_95, Dircol or Miser, can be employed. We were employing the Riots_95 package [START_REF] Schwartz | A Matlab toolbox for solving optimal control problems[END_REF], which is implemented in Matlab, has efficient tools for solving the constrained problems of dynamic optimisation and can be easily merged with other Matlab facilities (e.g. simulation of models developed in Simulink environment, with graphical user interface). The Matlab toolbox Riots solves a very large class of finite-time optimal controls problems that includes: trajectory and end-point constraints, variable initial conditions, free final time tasks and problems with cost functions endpoint. System dynamics can be integrated with fixed step-size Runge-Kutta method, a discrete-time solver or a variable step-size method. The software automatically computes gradients for all functions with respect to the controls and any free initial conditions. The main program in Riots is based on thick sequential quadratic programming (SQP). Hence, the program is not well-suited for high discretisation levels. One of the major limitations of Riots is that it is not well-appointed to deal with problems whose dynamics are unstable.

All computations were performed using low-cost PC (Atom, 1.66 GHz, 1 GB RAM) running Windows 7 and Matlab 7.12 (R2011a). Optimal and sub-optimal signals are computed for nominal values of parameters a = -88.95, b = -0.42, c = 52.02 assumed termination time Tf = 10 seconds and the scaling factor g = 10 5 utilising SQP algorithm. The system is assumed to be at an initial state x1(0) = 0.393, the initial value of the input signal is u(0) = 1 and -5  u(t)  5. The system dynamics was integrated using the fixed step-size fourth-order Runge-Kutta method with grid intervals of 0.2 seconds. The D-optimal input signals obtained for different desired values of the D-efficiency constant D (according to (3)) are shown in below figures. As the minimisation algorithms implemented in RIOTS_95 guarantee convergence only to a local minimum, we made use of the typical way to reduce the risk of "trapping", i.e. repeating the computations several times, starting from different initial conditions from the range [-0.4, 0.4] around the 'nominal' initial state x1(0) = 0.393. The D-optimal excitation signal obtained when there was no constraint on the Defficiency value (i.e. the coefficient  = 1 in the inequality (2)), is shown in black colour in Figure 1. It corresponds to the optimal experiment e * , where the maximal possible value of the FIM determinant is obtained and in such a case the value Deff = 100%•Deff, opt. The control signals obtained for decreasing values of Defficiency from the interval [70%, 100%] of its maximum value are shown in Figures 2345. As we can see, when the desired value of D-optimality decreases, the shape of the optimal input signal substantially changes. While for the optimal experiment (in the sense of ( 2)) there are the abrupt changes of the input, the control signal obtained for Deff < 70%•Deff, opt is almost constant, so the FIM determinant component was dominated by D-efficiency constraint value of the maximised performance index. The optimal excitation signal obtained when there was no constraint on the Defficiency component (i.e., for Deff = 100% and J = 4.14  10 32 ) is shown in Figure 2. The D-efficiency constraint value increased (Fig. 5) to obtain the critical value of the maximised performance index J = 2.89  10 32 at the level of Deff = 70%. For comparison, Figure 3 shows the sub-optimal input signal, which corresponds to the objective function value J = 3.72  10 32 at the level of Deff = 90%. Figure 4 contains the graphical display of the non-optimal signal obtained for J = 3.10  10 32 , where the FIM determinant component was maximised to the level of Deff = 80%. According to expectation, the constraint [START_REF] Uciński | Sensor Motion Planning in Distributed Parameter Systems Using Turing's Measure of Conditioning[END_REF] was active in the optimal solution as shown in the above figures. The signals u(t) computed for different values of D-efficiency as solutions of the optimisation task [START_REF] Atkinson | Optimum experimental design with SAS[END_REF] with the set of constraints ( 16), were then used as inputs in the parameter identification procedure. Figure 6 summarises the flow of information in the system identification process: we act on the physical system through the input u(t) and collect information through the observations of its output y(t). The presence of the white noise with different variance from the interval 0.0   2  0.7 makes the observations random variables. The model corresponds to the theoretical representation of the system [START_REF] Narasimhan | Multi-objective input signal design for plant friendly identification of process systems[END_REF], which depends on a vector of unknown parameters  = [a, b, c] T . The objective of the system identification task is to find the best values

Conclusions

An optimal input signal design problem for system identification was formulated in the paper and the method of the problem solution was outlined. In the presented approach the input signal is a solution of a dynamic optimisation problem, where the FIM determinant is maximised, at the same time providing a guaranteed level of Defficiency. The second order dynamic system case study of optimal input signal design with guaranteed D-efficiency was presented in the paper. The experiments confirm that we can provide a compromise between the friendliness of the plant excitation in the identification process and the accuracy of estimates (observed as a reasonably small volume of the confidence ellipsoid) for a wide range of measurement noise at the system output. One of the most important steps in the approach presented in the paper was the transcription of the proposed problem formulation into an equivalent optimal control task expressed in the Lagrange form with the appropriate set of constraints. The optimal input trajectories were then computed using one of existing packages for solving dynamic optimisation problems. An optimal input signal design for solving free final time parameter estimation problem in the time domain will be presented.

Fig. 1 .

 1 Fig. 1. The dynamic model for the one degree of freedom plant (free-clamped).

Fig. 2 .

 2 Fig. 2. Optimal input signal to the torsional spring system.

Fig. 3 .

 3 Fig.3. Sub-optimal input signal to the torsional spring system for Deff = 90%•Deff, opt.

Fig. 4 .

 4 Fig.4. Sub-optimal input signal to the torsional spring system for Deff = 80%•Deff, opt.

Fig. 5 .

 5 Fig.5. Sub-optimal input signal to the torsional spring system for Deff = 70%•Deff, opt.

Fig. 7 .

 7 Fig. 7. Confidence regions of the torsional spring model parameter estimates; the model was excited utilising: (a) Optimal input signal (Deff = Deff, opt). (b) Sub-optimal input signal (Deff = 90%•Deff, opt). (c) Sub-optimal input signal (Deff = 80%•Deff, opt). (d) Sub-optimal input signal (Deff = 70%•Deff, opt).

Acknowledgement

The work was supported by the Dean's Project No. S/WI/1/13, Faculty of Computer Science, Department of Digital Media and Computer Graphics, Bialystok University of Technology.

. the optimal values of parameters a and b computed as results of optimisation for each run, when the system starts from different initial state condition and the measurement noise influencing the system output has different variance. Figure 7(a) shows the results with the input signal obtained for the maximal value of FIM determinant (i.e. Deff = 100%•Deff, opt), the successive figures show the results (for the same combinations of initial states and noise variance) with the input signals were computed when a certain loss of D-optimality was assumed as (Deff / Deff, opt = 90%, 80% and 70%, respectively). Analysis of the confidence regions of the torsional system parameter estimates confirms the following regularities. The optimal input signal, obtained for Deff / Deff, opt = 100%, yields the minimal volume of the ellipsoidal confidence region of parameter estimates. When the desired ratio of Deff / Deff, opt decreases (i.e. we accept bigger loss of D-optimality), the cluster occupied by the optimal values of identified model parameters increases its sizefor the same initial conditions and noise characteristics as in the above experiment. Decreasing the desired ratio of Deff / Deff, opt yields the input signal, which is more "friendly" for the plant, i.e. in that way we avoid abrupt changes of the control valve settings in the reallife identification experiments. The results of the simulation experiments for other combinations of the torsional system parameters a, b and c are very similar to those shown in Figure 7. The purpose of this case study was to show that the requirements of high friendliness of the input signal and the accuracy of parameter estimation are, in some sense, opposite.


Adam Klimowicz
email: a.klimowicz@pb.edu.pl

Valery Solov'ev

Experiments on Minimization Method of Incompletely Specified Finite State Machines for Low Power Design

Keywords: finite state machine (FSM), state minimization, low power design

This paper presents a heuristic method for minimization of incompletely specified finite state machine with unspecified values of output variables. The proposed method is based on two states merging. In this method, such optimization criteria as the power consumption and possibility of merging other states are taken into account already at the stage of minimizing internal states. In addition to reduction of the finite state machine (FSM) states, the method also allows reducing the number of FSM transitions and FSM input variables. Experimental results for various styles of state assignment are presented. The results show that this approach to minimization of FSM in most of cases is more effective than classical methods in respect of power consumption.

Introduction

A finite state machine (FSM) is a model used in the design of various computation structures like sequential circuits, digital control systems, microprocessor control circuits, digital communication systems, iterative networks, communication protocols, etc. For various reasons the transitions between the FSM states or the FSM outputs may be not completely specified. An incompletely specified finite state machine (ISFSM) is the one where either the next state or the output is not specified for at least one input vector. Minimization of ISFSMs is an important task in the optimal design of sequential circuits. A general theory for incompletely specified machines was first developed in [START_REF] Paull | Minimizing the number of states in incompletely specified state machines[END_REF]. The standard approach to solution of the problem of ISFSM's state reduction is based on a generation of sets of compatible states (or compatibles) and finding of a minimal closed cover. The problem of minimization of ISFSMs is an NP-complete problem [START_REF] Pfleeger | State reduction in incompletely specified finite state machines[END_REF] and has been studied by a number of authors. In [START_REF] Rho | Exact and heuristic algorithms for the minimization of incompletely specified state machines[END_REF], a program called STAMINA that runs in exact and heuristic modes and uses explicit enumeration for the solution of state minimization problem is presented. In [START_REF] Pena | A new algorithm for exact reduction of incompletely specified finite state machines[END_REF], an exact state minimization algorithm based on mapping of ISFSMs to FSMs tree is presented. In [START_REF] Gören | On state reduction of incompletely specified finite state machines[END_REF], a branch-and-bound search technique for the identification of sets of compatible states is described.

The conventional approach to the synthesis of FSMs includes the following stages, which are executed sequentially: minimization of the number of internal states, state assignment and synthesis of the combinational part of the FSM. However, classical approach often contradicts the FSM optimization goal at the stage of logic synthesis because both the minimization of the number of internal states and their assignment completely ignore the features of the technological base and the requirements of logic synthesis. In [START_REF] Xia | Genetic algorithm based state assignment for power and area optimization[END_REF][START_REF] Aiman | Finite state machine state assignment for area and power minimization[END_REF][START_REF] Chaudhury | Genetic algorithm-based FSM synthesis with area-power trade-offs[END_REF], the implementation cost is minimized simultaneously with the minimization of the power consumption at the stage of state assignment. In the majority of these works, genetic algorithms are used. In [START_REF] Lindholm | High frequency and low power semi-synchronous PFM state machine[END_REF], the minimization of power consumption and delay is considered for asynchronous FSMs. The concept of a low power semi-synchronous FSM operating on a high frequency is proposed that can be implemented and tested as an ordinary synchronous FSM. In [START_REF] Liu | An Embedded low power reconfigurable fabric for finite state machine operations[END_REF], a two-level structural model is proposed to minimize the power consumption, area, and delay. The first level of this model consists of sequential units, while the second level consists of combinational units of limited size.

The analysis of available studies showed that there are no works in which the number of internal states and power consumption are simultaneously minimized. In this paper, we propose a heuristic method for minimization of incompletely specified FSMs with unspecified values of output variables. This method is based on an operation of two states merging. In this method, such optimization criteria as the power consumption and possibility of merging other states are taken into account already at the stage of minimizing internal states. In addition to reduction of internal states this method minimizes the number of FSM transitions and FSM input variables.

Preliminaries

An ISFSM can have incompletely specified outputs and incompletely specified transitions. Incompletely specified outputs take place when the value of the output variable does not influence on functioning of the controlled object, e.g. when a carry voltage is not applied to the controlled object. Incompletely specified transitions arise when some input vectors never appear on FSM inputs, e.g. the codes of hexadecimal figures A-F at work in a decimal notation. In practice, designers usually redefine the unspecified transitions by transitions to the present state, or to the reset state, or to an additional state, where an error signal is generated. It makes it possible to increase the functional reliability of the digital systems. In the offered approach we define the unspecified values only of the output variables and do not change the unspecified transitions.

Let us denote by L the number of FSM input variables of a set X = {x 1 ,…,x L }, by N the number of FSM output variables of a set Y = {y 1 ,…,y N }, by M the number of FSM internal states of a set A = {a 1 ,…,a M }, and by R the minimal number of bits required to encode internal states, where R = intlog 2 M.

A FSM behavior is described by the transition list. The transition list is a table with four columns: a m , a s , X(a m ,a s ), and Y(a m ,a s ). Each row of the transition list corresponds to one FSM transition. The column a m contains the state where the transition begins (a present state), the column a s contains the state where the transition ends (a next state), the column X(a m ,a s ) contains the set of values of the input variables that initiates this transition (a transition condition or an input vector), and the column Y(a m ,a s ) contains the set of values of the output variables that is generated by FSM at this transition (an output vector). An ISFSM output vector is represented by ternary vector. For example, Y(a m ,a s )="01-0", where 0 denotes zero value, 1 denotes unity value, and dash ("-") denotes a don't care value of the corresponding output variable.

The transition condition may be described in the column X(a m ,a s ) in the form of conjunction of FSM input variables. The transition condition can also be represented by a ternary vector. For example, X(a m ,a s ) = "1-10-0" where unit [START_REF] Paull | Minimizing the number of states in incompletely specified state machines[END_REF] means that the corresponding input variable is included in conjunction in the direct form, zero (0) means that the corresponding input variable is included in conjunction in the inversed form, and dash ("-") means that the value of the input variable does not affect the FSM transition. Since the FSM behavior is deterministic, all the transition conditions from every FSM state should be mutually orthogonal. Two transition conditions are orthogonal if they have different significant values (0 or 1) at least in one position.

Two FSM states a i and a j can be merged, i.e. replaced by one state a i_j , if they are equivalent. Equivalency of two FSM states means that FSM behavior does not change when these states are merged in one. FSM behavior does not change after states a i and a j merge, if the transition conditions from the states a i and a j that lead to different states are orthogonal. If there are transitions from states a i and a j that lead to the same unique state, then the transition conditions for such transitions should be equal. Moreover, the output vectors that are generated at these transitions should be not orthogonal. Note also that under two FSM states merging wait states can be formed.

Under FSM states merging the output vectors with unspecified values can be merged only if they are not orthogonal. Thus the significant values (0 or 1) remain without changes, and the unspecified values are replaced by the corresponding significant values. For example, let Y(a i ,a s ) ="1-0-0" and Y(a j ,a s ) ="-1010", and let the states a i and a j assume merging, then the output vector Y(a i_j ,a s ) ="11010" will be formed at the transition from the new state a i_j to the state a s .

The main strategy of the offered approach consists in finding the set D of all the pairs of FSM states satisfying the merging conditions. Then for each pair of states from D the trial merging is carried out. Finally a pair (a i ,a j ) for merging is selected in such a way that it leaves the maximal possibilities for other pairs of FSM states merging. The given process repeats as long as there exists a possibility for at least one pair of FSM states merging. The method was described more precisely in paper [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF].

In distinction from [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF], in the present paper we chose for merging at each step the pair (a i , a j ) that best satisfies the optimization criteria in terms of power consumption, and leaves the maximum possibilities for merging other pairs in G. This procedure is repeated while at least one pair of states can be merged. Let (a s , a t ) be a pair of states in G, where P st is the estimate of power consumption, and M st is the estimate of the possibility to merge other states. Then, with regard to the above considerations, the FSM minimization algorithm can be described as follows.

Algorithm 1 (general algorithm for FSM minimization)

1. Using the method described in [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF], form the set G of pairs of states that admit merging. If G =  (no pairs can be merged), go to step 5 2. For each pair of states (a s , a t ) in G, calculate the estimates P st , and M st of the optimization criteria. 3. According to the specified order of optimization criteria, choose a pair of states (a i , a j ) for merging. Among all the pairs in G, choose a pair (a i , a j ) for which P ij = min; if there are several such pairs, then choose among them the one for which M ij = max. 4. Merge the pair of states (a i , a j ). Store the results of minimization (transition list and corresponding P st value ). Go to step 1. 5. Among all saved results of minimization select one with minimal P st value. 6. Minimize the number of transitions in the FSM. 7. Minimize the number of input variables in the FSM. 8. Stop.

Merging of the states a i and a j (step 4 of Algorithm 1), minimization of the number of transitions (step 6 of Algorithm 1) and minimization of the number of input variables (step 7 of Algorithm 1) are performed as described in [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF].

Algorithms of minimization of the number of transition an input variables are based on some observations. Suppose, for instance, that one transition from a state a 1 under condition x 1 leads to a state a 2 and the second transition from a 1 under condition 1

x leads to another state a 3 and on each of these transitions not orthogonal output vectors are formed ( 1x is an inversed form of the variable x 1 ). Suppose that the states a 2 and a 3 can be merged. After merging a 2 and a 3 , a new state a 23 is formed. Now two transitions lead from a 1 to a 2_3 , one under condition x 1 and the second under condition 1

x . The latter means that the transition from a 1 to a 23 is unconditional and two transi- tions can be replaced by one unconditional transition. Notice that in general transition conditions from a state a 1 can be much more complicated.

At minimization of the number of FSM transitions one can arrive at a situation when certain input variables have no impact on the transition conditions. Suppose, for instance, that one transition from a state a 1 under condition x 1 leads to a state a 2 and another transition from a 1 under condition 1 x leads to a state a 3 and the variable x 1 does not meet anywhere else in transition conditions of the FSM. Suppose that after the states a 2 and a 3 have been merged, the transition from the state a 1 to the state a 23 becomes unconditional, i.e. it does not depend on values of input variables. The latter means that the variable x 1 has no impact on any FSM transition and therefore it is redundant.

Estimation of optimization criteria

To estimate the optimization criteria, all pairs of states in G are considered one after another. For each pair of states (a s , a t ) in G, a trial merging is performed. For the resultant FSM, its internal states are encoded using one of the available methods that will later be used in the synthesis of the FSM, and the system of Boolean functions corresponding to the combinational part of the FSM is built. Next, for the pair (a s , a t ), power consumption P st , and the possibility of minimizing other states M st are estimated. The optimization criteria for each pair of states (a s , a t ) in G are estimated at step 2 of Algorithm 1 using the following algorithm.

Algorithm 2 (estimation of optimization criteria).

1. Sequentially consider the elements of the set G. 2. For each pair of states (a s , a t )  G, make a trial merging. 3. Encode the internal states using one of the available methods. 4. Estimate the power consumption P st . 5. Estimate the possibility of other states minimization M st . 6. Return to the original FSM (before merging at step 2). 7. Execute steps 2-9 for all pairs of states in G.

Stop.

The estimate M st is determined by the number of pairs of the FSM that can be merged after merging the pair (a s , a t ). To provide the best possibilities for merging other states, M st should be maximized. Using the method described in [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF], the set G st of pairs of states that can be merged upon merging the pair (a s , a t ) must me find. After that, the parameter M st can be calculated as the cardinality of the set G st (M st = | G st |).

To estimate the power consumption of an FSM, we use the procedure proposed in [START_REF] Tsui | Power estimation methods for sequential logic circuits[END_REF] because it is the most universal and suitable for any hardware components. In addition, this procedure is adapted for the CMOS technology. The procedure described in [START_REF] Tsui | Power estimation methods for sequential logic circuits[END_REF] makes it possible to calculate the dynamic power consumption of an FSM based on the encoding of its internal states and the probability of occurrence of one (zero) at each input of the FSM. The power consumption depends on the encoding of internal states. For performing experiments the binary and one-hot encoding styles are used. In the one-hot encoding only one bit of the code has '1' value and all other bits have '0' value. In addition, the sequential encoding algorithm for low power design [START_REF] Grzes | Sequential algorithm for low-power encoding internal states of finite state machines[END_REF] is proposed to use.

According to [START_REF] Tsui | Power estimation methods for sequential logic circuits[END_REF], the power consumption of the FSM is determined by the rule:

      R r R r r DD r N fC V P P 1 1 2 2 1 ( 1
)
where P r is the power consumed by the flip-flop r, V DD is the supply voltage, f is the frequency at which the FSM operates, C is the capacity of flip-flop output, and N r is the activity of the flip-flop r.

Let k i be a binary code of a state a i  A. Denote by i r k the value of the bit r in the code k i of the state a i . Then, the activity N r of switching the memory flip-flop r of the FSM satisfies the equation

         M m M s r s r m s m r k k a a P N 1 1 (2)
where P(a m  a s ) is the probability of transiting from the state a m to the state a s (a m , a s  A) and  is the XOR operation. The FSM must be encoded first to find the activity of each flip-flop.

The probability P(a m  a s ) of transiting from the state a m to the state a s (a m , a s  A) is given by the rule:

        s m m s m a a X P a P a a P ,   (3)
where P (a m ) is the probability of the FSM to be in the state a m and P(X(a m , a s ) is the probability of appearing the vector X(a m , a s ) initiating the transition from a m to a s at the input of the FSM. The probability P(X(a m , a s ) of the vector X(a m , a s ) to appear at the input of the FSM is given by the rule:

          L b b s m d x P a a X P 1 , (4)
where d  {0, 1, '-'} and P(x b = d) is the probability that the input variable x b in the input vector X(a m , a s ) takes the value d. In this paper, we assume that 0 and 1 appear at each input of the FSM with the same probability; therefore, P (x b = 0) = P (x b = 1) = 0.5 and P (x b = '-') = 1 (the probability that 0 or 1 appear at each input of the FSM is equal one because symbol '-' means logic zero or logic one and any other values cannot appear at input). For a specific FSM, P (x b = 0) and P (x b = 1) may be different; however, it must hold that P (x b = 0) + P (x b = 1) = 1. The probability P(a i ) to find the FSM in each state a i can be determined by solving the system of equations

           M m i m m i a a X P a P a P 1 , ,   M i , 1  (5)
If there are no transitions between the states a m and a i , then we set P (X (a m , a i )) = 0. If there are several transitions, then P(X (a m , a i )) is the sum of the probabilities of appearing each input vector initiating the transition from a m to a i . System (5) is a system of M linear equations with M unknowns P(a 1 ),…, P(a M ), which can be solved by any available method, for example, by the Gauss method. Since the FSM is always in one of its internal states, it holds that

     M m m a P 1 1 (6)
To simplify the solution of system ( 5), one equation in ( 5) can be replaced with ( 6).

Experimental results

The method for minimization of incompletely specified finite state machines was implemented in a program called ZUBR. To estimate the efficiency of the offered method we used MCNC FSM benchmarks [START_REF] Yang | Logic synthesis and optimization benchmarks user guide[END_REF]. Each of tested FSM benchmarks was encoded using binary and one-hot encoding and sequential low power algorithm [START_REF] Grzes | Sequential algorithm for low-power encoding internal states of finite state machines[END_REF].

A power consumption estimation parameter was calculated using following values: output capacitance C = 3pF, frequency f = 5MHz, supply voltage V CC = 5V, input probability P(x i = 1) = 0,5. The power was calculated for the initial FSM, the FSM after minimization using method described in paper [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF], the STAMINA program [START_REF] Rho | Exact and heuristic algorithms for the minimization of incompletely specified state machines[END_REF] and the method described in this paper.

The experimental results for binary encoding are presented in Table 1, where M 0 and P 0 are, respectively, the number of internal states and dissipated power (in mW) of the initial FSM; M 1 and P 1 are, respectively, the number of internal states and dissipated power (in mW) after minimization without taking in consideration power consumption (method described in [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF]); M 2 and P 2 are, respectively, the number of internal states and dissipated power (in mW) after minimization using STAMINA and M 3 , and P 3 are, respectively, the number of internal states and dissipated power (in mW) after minimization using proposed method (with taking in consideration power consumption). P 0 /P 3 , P 1 /P 3 , and P 2 /P 3 are ratios of the corresponding parameters; and Average is the geometric mean value. The analysis of Table 1 shows that application of the proposed method using binary encoding allows to reduce the number of internal states of the initial FSM. Similarly, the average reduction of the power consumption of the FSM makes 1.26 times, and on occasion (example lion9) 2.28 times. In comparison to method from [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF] the number of states is higher in 3 cases, but the average reduction of the power consumption of the FSM makes 1.04 times, and on occasion (example train11) 1.14 times. In comparison to STAMINA the number of states is higher in 4 cases but the average reduction of the power consumption of the FSM makes 1.04 times, and on occasion (example train11) 1.37 times.

The experimental results for one-hot encoding are presented in Table 2, where all parameters have the same meaning as in Table 1. The analysis of Table 2 shows that application of the proposed method using one-hot encoding allows to reduce the number of internal states of the initial FSM. Similarly, the average reduction of the power consumption of the FSM makes 1.05 times, and on occasion (example train11) 1.14 times. In comparison to method from [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF] the number of states is higher in two cases, but the average reduction of the power consumption of the FSM makes 1.03 times, and on occasion (example tma) 1.18 times. In comparison to STAMINA the number of states is higher in 3 cases but the average reduction of the power consumption of the FSM makes 1.01 times, and on occasion (example train11) 1.25 times. The experimental results for encoding using the sequential low power algorithm [START_REF] Grzes | Sequential algorithm for low-power encoding internal states of finite state machines[END_REF] are presented in Table 3, where all parameters have the same meaning as in Table 1 and Table 2. The analysis of Table 3 shows that application of the proposed method with low power encoding allows to reduce the number of internal states of the initial FSM on the average by 1.24 times, and on occasion (example lion9) by 1.75 times. Similarly, the average reduction of the power consumption of the FSM makes 1.02 times, and on occasion (example s27) 1.13 times. In comparison to method from [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF] the number of states is 1.28 times higher, occasionally even 2.5 times higher (example train11). The average reduction of the power consumption of the FSM makes 1.04 times, and on occasion (example train11) 1.12 times. In comparison to STAMINA the number of states is higher, occasionally even 2.5 times higher (example train11). The average reduction of the power consumption of the FSM makes 1.02 times, and on occasion (example train11) 1.36 times.

It can be noticed that the greater reduction of states in most cases leads to increased power consumption of FSMs (in 62.5% of cases). Only for one example (s27) a FSM of lesser power consumption was obtained using the method from [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF]. In contrast, using the method, taking into account the criterion of minimizing the power consumption, there are always obtained machines with less or the same power consumption as the initial machines. Additional minimization of the number of transitions in accordance with the method [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF] does not cause further reduction in power consumption.

Table 4 presents the average power consumption for all three encoding styles. P AV0 , P AV1 , P AV2 and P AV3 parameters stand for the average power consumption of the initial FSM, the FSM after minimization using the method [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF], the FSM after minimization using the STAMINA program and the method from this paper accordingly. The analysis of the Table 4 shows that results obtained using presented approach are better than results obtained from the STAMINA and method from paper [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF] in all styles of encoding used. Also, the one-hot encoding style was the most power consumable for all minimization algorithms used and sequential algorithm was the least power consumable method of encoding for all considered cases. Table 5 presents ratios of power consumption for sequential encoding method in relation to binary encoding (P AVB /P AVS ) and one-hot encoding (P AVO /P AVS ) styles for all considered minimization methods, where parameters P AVB , P AVO , P AVS are the average power consumption for binary encoding, one-hot encoding and sequential encoding, accordingly. The analysis of the Table 5 shows that sequential algorithm for low power encoding is the most efficient in comparison to one-hot encoding (similar values for all minimization methods and not minimized FSMs). For binary encoding style, the power consumed by FSM is higher for the initial FSM than for FSMs after minimization.

Conclusion

Minimization of incompletely specified finite state machines is an important step in the FSM synthesis. In this paper we presented an efficient method for FSM minimization. In contrast to traditional approaches, the proposed method allows to minimize not only the number of FSM states and consumed power, but also the number of FSM transitions and input variables.

The main goal of this method is not to find the minimal number of states but the such representation of the FSM, which consumes minimal amount of power. Of course we obtain in most cases the worse results for state minimization in comparison to methods [START_REF] Klimowicz | Minimization of incompletely specified Mealy finitestate machines by merging two internal states[END_REF] and [START_REF] Rho | Exact and heuristic algorithms for the minimization of incompletely specified state machines[END_REF], but much better for power consumption. The most important conclusion from experiments is that the FSM with minimal number of states is not in most cases the best solution in respect of power consumption.

In the offered method of FSM minimization only two states merging is considered. The given algorithm can be modified so to merge a group of states containing more than two states. Besides, the further perfection of the presented algorithm can be implemented by consideration of incompletely specified values for the transition functions as additional conditions for merging possibility of FSM internal states.

Performed experiments are only the part of work on the complex minimization method [START_REF] Solov'ev | Complex minimization method for finite state machines implemented on programmable logic devices[END_REF], where not only power consumption, but also speed and area parameters are taken in consideration. In future, this method will serve to diminish power and cost and increase speed for FSM realization on programmable logic devices.

Table 1 .

 1 The experimental results for binary encoding

	Name M0	P0	M1	P1	M2	P2	M3	P3	P0/P3 P1/P3 P2/P3
	bbara	10 62.141	7 62.090	7 57.812	8 61.706 1.01 1.01 0.94
	bbsse	16 226.014 13 226.014 13 232.976 13 226.014 1.00 1.00 1.03
	beecount	7 113.275	5 91.889	4 75.116	5 91.889 1.23 1.00 0.82
	lion9	14 192.569	4 93.750	4 109.375	4 84.375 2.28 1.11 1.30
	s27	6 192.751	5 163.078	5 157.300	5 163.078 1.18 1.00 0.96
	sse	16 226.014 13 226.014 13 232.976 13 226.014 1.00 1.00 1.03
	tma	20 158.348 18 135.475 18 122.372 19 126.884 1.25 1.07 0.96
	train11	12 101.902	4 78.125	4 93.750	6 68.452 1.49 1.14 1.37
	Average									1.26 1.04 1.04

Table 2 .

 2 The experimental results for one-hot encoding

	Name M0	P0	M1	P1	M2	P2	M3	P3	P0/P3 P1/P3 P2/P3
	bbara	10 83.476	7 82.325	7 82.236	7 82.325 1.01 1.00 1.00
	bbsse	16 252.442 13 252.442 13 252.443 13 252.442 1.00 1.00 1.00
	beecount	7 169.563	5 168.899	4 146.739	5 168.899 1.00 1.00 0.87
	lion9	14 129.522	4 140.625	4 156.250	6 128.906 1.00 1.09 1.21
	s27	6 255.251	5 226.102	5 226.103	5 226.102 1.13 1.00 1.00
	sse	16 252.442 13 252.442 13 252.443 13 252.442 1.00 1.00 1.00
	tma	20 130.134 18 140.384 18 99.033 19 119.320 1.09 1.18 0.83
	train11	12 124.320	4 109.375	4 136.364	4 109.375 1.14 1.00 1.25
	Average									1.05 1.03 1.01

Table 3 .

 3 The experimental resultS for encoding using the sequential algorithm

	Name M0	P0	M1	P1	M2	P2	M3	P3	P0/P3 P1/P3 P2/P3
	bbara	10 52.389	7 52.664	7 52.664	8 52.171 1.00 1.01 1.01
	bbsse	16 146.468 13 146.468 13 146.469 13 146.468 1.00 1.00 1.00
	beecount	7 89.421	5 91.889	4 75.116	6 89.339 1.00 1.03 0.84
	lion9	14 64.762	4 70.313	4 78.125	5 63.919 1.01 1.10 1.22
	s27	6 168.330	5 148.634	5 148.634	5 148.634 1.13 1.00 1.00
	sse	16 146.468 13 146.468 13 146.469 13 146.468 1.00 1.00 1.00
	tma	20 65.250 18 71.117 18 53.106 19 63.970 1.02 1.11 0.83
	train11	12 63.519	4 70.313	4 85.227 10 62.840 1.01 1.12 1.36
	Average									1.02 1.04 1.02

Table 4 .

 4 Average power comparison for all tested encodings

	Encoding	PAV0	PAV1	PAV2	PAV3
	Binary	159126.75 134554.38 135209.63 131051.50
	One-hot	174643.75 171574.25 168951.38 167476.38
	Sequential 99575.88 99733.25 98226.25 96726.13

Table 5 .

 5 Average power consumption ratios for all tested methods of minimization

	Ratio	Initial FSM Method [11] STAMINA This method
	PAVB/PAVS	1.60	1.35	1.38	1.35
	PAVO/PAVS	1.75	1.72	1.72	1.73

 The work was supported by Bialystok University of Technology grant S/WI/1/2013


Valery Salauyou
email: v.salauyou@pb.edu.pl

Marek Gruszewski
email: m.gruszewski@pb.edu.pl

Designing of Hierarchical Structures for Binary Comparators on FPGA/SoC

Keywords: binary comparator, synthesis, FPGA, SoC, hierarchical tree structure, Verilog language

The article considers the general synthesis technique of hierarchical tree structures on FPGA/SoC for binary comparators. Designing of first level comparators is given. The best hierarchical comparator structure for the specific FPGA/SoC family is found empirically by experimental researches. The offered method allows reducing an area from 5.3% to 43.0%, and for high bitwidth comparators (with an input word length 1024) by 2.225 times. In the conclusion additional opportunities of the offered method are marked, and main directions of further researches are presented.

Introduction

At present, there is a constant tendency to increase the length of words in computer systems. The length of words increases rapidly in telecommunication systems and data transmission and processing devices. On the other hand, integrated circuits of a programmable logic such as Complex Programmable Logic Devices (CPLDs), Field Programmable Gate Arrays (FPGAs), and System on Chips (SoCs) are widely used in building digital systems [START_REF] Salauyou | Designing of digital systems based on programmable logic integrated circuits. Hot line-Telecom[END_REF]. Digital systems as a rule include different standard functional blocks one of which is the comparator of binary numbers [START_REF] Salauyou | Designing of functional blocks of digital systems on programmable logic devices. Bestprint[END_REF]. The binary comparator is one of the fundamental components in digital systems with many applications such as the decoding of the microprocessor instruction sets, the renaming of the register files in a superscalar system, and the number magnitude comparison in an arithmetic logic unit. When high bitwidth comparators are constructed, it is sufficient to implement only function G "greater-than" and function E "equal", because function L "less-than" can always be determined on the basis of two first functions: L = G & E . The design problem of binary comparators is examined in many articles. In [START_REF] Guangjie | New efficient design of digital comparator[END_REF], the comparator is offered to build like an adder by using of a generate function and a propagate function which can be realized by the Manchester carry chain.

In some designs, a pipeline processing of signals and a mechanism of power off are used to increase performance and reduction of energy consumption. In [START_REF] Wang | 1 GHz 64-bit high-speed comparator using ANT dynamic logic with two-phase clocking[END_REF], the comparator using two-phase clocking dynamic CMOS logic with modified non-inverting all-N-transistor block is presented. The compared output of two 64-bit binary numbers is performed in 3.5 clock cycles. In [START_REF] Huang | High-performance and power-efficient CMOS comparators[END_REF], the comparator is based on the priorityencoding (PE) algorithm. The circuit is realized with a latch-based two-stage pipelined structure. The comparator designed with the proposed techniques is 16% faster, 50% smaller, and 79% more power efficient as compared with the all-n-transistor comparator [START_REF] Wang | 1 GHz 64-bit high-speed comparator using ANT dynamic logic with two-phase clocking[END_REF]. In [START_REF] Cheng | A high-speed magnitude comparator with small transistor count[END_REF], the prefix tree structure's area and power consumption can be improved by leveraging two-input multiplexers at each level and generate-propagate logic cells at the first level, which takes advantage of one's complement addition. In [START_REF] Lam | High performance single clock cycle CMOS comparator[END_REF], a priority encoding (parallel-MSB-checking) algorithm along with a new priority encoder design and a MUX-based comparator structure is proposed; the method allows to increase performance by 22% in comparison with [START_REF] Huang | High-performance and power-efficient CMOS comparators[END_REF]. In [START_REF] Lam | A MUX-based high-performance single-cycle CMOS comparator[END_REF], other architectures use a multiplexer-based structure to split a comparator into two comparator stages; the method allows to increase performance by 28% in comparison with [START_REF] Lam | High performance single clock cycle CMOS comparator[END_REF]. In [START_REF] Kim | Bitwise competition logic for compact digital comparator[END_REF], to reduce the long delays suffered by bitwise ripple designs, an enhanced architecture incorporates an algorithm that uses no arithmetic operations. This scheme detects the larger operand by determining which operand possesses the leftmost 1 bit after pre-encoding, before supplying the operands to a bitwise competition logic (BCL) structure. The BCL structure partitions the operands into 8-b blocks and the result for each block is input into a multiplexer to determine the final comparison decision. In [START_REF] Perri | Fast low-cost implementation of single-clock-cycle binary comparator[END_REF], the comparator project combines a tree structure with a two phase domino clocking structure for speed enhancement. In [START_REF] Frustaci | A new low-power highspeed single-clock-cycle binary comparator[END_REF], binary comparator is based on a novel parallel-prefix algorithm. The proposed design shows an energy dissipation reduction of 23% and a speed improvement of 7%. In [START_REF] Abdel-Hafeez | Scalable digital CMOS comparator using a parallel prefix tree[END_REF], the comparator exploits a novel scalable parallel prefix structure that leverages the comparison outcome of the most significant bit, proceeding bitwise toward the least significant bit only when the compared bits are equal. This method reduces dynamic power dissipation by eliminating unnecessary transitions in a parallel prefix structure.

All of the aforementioned works achieve high-performance operations using dynamic logic. While dynamic logic has demonstrated superior performance, as compared with static logic, it is not suitable for low-power operation. On the other hand, using of static logic allows reducing power consumption significantly. In [START_REF] Chuang | A low-power high-performance singlecycle tree-based 64-bit binary comparator[END_REF], a new tree structure comparator with a pre-encoding scheme is proposed; one is particularly suitable for implementation on static logic to ensure low-power consumption. In [START_REF] Hauser | High-Speed 64-Bit Binary Comparator using Two Stages[END_REF], some modifications have been done in binary comparator [START_REF] Chuang | A low-power high-performance singlecycle tree-based 64-bit binary comparator[END_REF] design to improve the speed of the circuit. In [START_REF] Chuang | A 167-ps 2.34-mW Single-Cycle 64-Bit Binary Tree Comparator With Constant-Delay Logic in 65-nm CMOS[END_REF], a single-cycle tree-based binary comparator with constant-delay (CD) logic is presented. The proposed comparator with CD logic is 20% faster or 17% more energy-efficient compared to a comparator implemented with just the static logic.

In [START_REF] Deb | High-speed comparator architectures for fast binary comparison[END_REF], the design of digital comparator with two different parallel architectures is proposed. These comparators are realized in Verilog and simulated with Xilinx ISE 8.2i platform. Simulation results show that the first proposed architecture has 23.769 % less combinational delay and the second proposed architecture has a combinational delay of 35.218 % less compared to the traditional design.

Reviewing of known methods of comparator designing showed that the majority of the methods (except for [START_REF] Deb | High-speed comparator architectures for fast binary comparison[END_REF]) are intended to implement of the comparators on application specific integrated circuits (ASICs) and are not suitable for designing the comparators on the programmable logic.

This paper presents a universal method for designing of hierarchical tree structures of comparators on the programmable logic. Universality of the offered method is that the design of the comparator is described entirely in Verilog language; it is applicable to all classes of the programmable logic: CPLD, FPGS and SoC; it is also applicable to all CMOS process. The offered method allows changing the number of logical levels in a tree structure of the comparator in a broad range, as a result the user can select a trade-off of cost against performance. The comparator diagram is completely combinatorial circuit which does not contain clock signals therefore it does not require additional circuits for generating clock signals (unlike the considered known methods). Besides, in the offered approach there are no bitwise carries, and parallelism of the diagram provides high speed.

Section 2 executes the review of related researches. Section 3 describes the general synthesis technique the hierarchical structures for the binary comparators. Section 4 considers synthesis the comparators of the first level. Section 5 discusses experimental results. Conclusions presents additional opportunities of the offered method and also represent the main directions of further researches.

Related Research

This work is a continuation of researches to find the effective design methods for binary comparators based on a programmable logic [START_REF] Salauyou | An implementation on programmable logic comparators with high bitwidth[END_REF][START_REF] Solov'ev | The hierarchical method of synthesis of large-capacity comparators with the use of programmable logic integrated circuits[END_REF][START_REF] Salauyou | An implementation on CPLD/FPGA hierarchical comparators by parallel-sequential synthesis[END_REF][START_REF] Salauyou | Hierarchical comparatorsdescribe styles, synthesis results[END_REF]. In [START_REF] Salauyou | An implementation on programmable logic comparators with high bitwidth[END_REF], the following methods of the comparator synthesis are considered: parallel, sequential, parallelsequential, and with adder using. For each method two ways of implementation are offered: graphic and in the AHDL (Altera Hardware Description Language) language.

The experimental researches are performed by the Altera MAX+PLUS II platform for 64-bit comparators and the results are compared to the Altera parametrized function lpm_compare.

In [START_REF] Solov'ev | The hierarchical method of synthesis of large-capacity comparators with the use of programmable logic integrated circuits[END_REF], the method of the comparator design in the form of a hierarchical structure is offered. The experimental researches are executed by Altera MAX+PLUS II platform. The offered method is compared to the sequential and parallel methods [START_REF] Salauyou | An implementation on programmable logic comparators with high bitwidth[END_REF], and also to the Altera parametrized function lpm_compare, and to the method that implemented in the AHDL language compiler. At the first level of the hierarchical structure the 4-bit comparators are used. These comparators are built by four methods: the lpm_compare function, the AHDL language, and the parallel and sequential method [START_REF] Salauyou | An implementation on programmable logic comparators with high bitwidth[END_REF].

In [START_REF] Salauyou | An implementation on CPLD/FPGA hierarchical comparators by parallel-sequential synthesis[END_REF], the hierarchical structures of 64-bit comparators were researched by Quartus II 13.1 platform for Altera CPLDs and FPGAs. The 4-bit comparators formed a first level of the hierarchical structure. Two methods for building the first level comparators are used: Verilog language and pm_compare function. A connection of the comparators in the hierarchical structures for different configurations was executed by the graphics editor of Quartus II platform. By this method 15 hierarchical structures of the 64-bit comparator were constructed. The second group of the comparators is made by similar structures, but LCELL [START_REF]Designing with Low-Level Primitives. User Guide[END_REF] buffers were set on outputs of the comparators of the first level. Such parameters as the implementation cost, the performance, and the power consumption were researched. Results were compared to the lpm_compare function. For CPLDs the offered method allows reducing the implementation cost by 32%, the delay by 44%, and the power consumption by 18%. For FPGAs the method allows reducing the implementation cost by 17% and the delay by 26%, thus power consumption does not change.

In [START_REF] Salauyou | Hierarchical comparatorsdescribe styles, synthesis results[END_REF], the combined technique was used for designing the 128-bit and 256-bit comparators. The 64-bit comparators made the first level. The 64-bit comparators were built by a parallel-sequential method [START_REF] Salauyou | An implementation on programmable logic comparators with high bitwidth[END_REF] from sections on 2-, 4-, 8-, 16-, and 32-bit. The hierarchical structure of the 128-bit and 256-bit comparators was designed by the graphics editor of Quartus II platform. The offered method, in comparison with the lpm_compare function, allows reducing the implementation cost by 13% and the delay by 18% for 128-bit comparators, and for 256-bit comparators, respectively, by 19% and by 54%.

In [START_REF] Solov'ev | The hierarchical method of synthesis of large-capacity comparators with the use of programmable logic integrated circuits[END_REF][START_REF] Salauyou | An implementation on CPLD/FPGA hierarchical comparators by parallel-sequential synthesis[END_REF][START_REF] Salauyou | Hierarchical comparatorsdescribe styles, synthesis results[END_REF], the methods of designing comparators generally on 64 bits were considered. In [START_REF] Solov'ev | The hierarchical method of synthesis of large-capacity comparators with the use of programmable logic integrated circuits[END_REF], for researches the outdated MAX+PLUS II platform and the AHDL language that supported only by Altera tools was used. In [START_REF] Solov'ev | The hierarchical method of synthesis of large-capacity comparators with the use of programmable logic integrated circuits[END_REF][START_REF] Salauyou | An implementation on CPLD/FPGA hierarchical comparators by parallel-sequential synthesis[END_REF], the lpm_compare function and the AHDL language were used to implement comparators of the first level. Besides, the graphics editor of Quartus II platform was used to design hierarchical structures of comparators. The specified shortcomings do not allow the synthesis method [START_REF] Solov'ev | The hierarchical method of synthesis of large-capacity comparators with the use of programmable logic integrated circuits[END_REF][START_REF] Salauyou | An implementation on CPLD/FPGA hierarchical comparators by parallel-sequential synthesis[END_REF][START_REF] Salauyou | Hierarchical comparatorsdescribe styles, synthesis results[END_REF] of the hierarchical comparator structures to be the universal method claiming for broad application.

This paper offers the synthesis method of the hierarchical structures of the high bitwidth comparators in Verilog language. This method has next distinctive features: all elements of hierarchical structure are described only in Verilog language, the graphics editor is not used, and the lpm_compare function is not used. Therefore the offered method is universal and can be used for the implementation of the binary comparators on any integrated circuits (CPLD, FPGA, SoC or ASIC) by design tools of any vendors. Single restriction is that these design tools must support the Verilog language.

A General Synthesis Technique of the Hierarchical Structures for Binary Comparators

The proposed hierarchical structure for binary comparators is shown in

The hierarchical structure in Fig. 1 is described by the formula:

C_M_NxT, ( 3
)
where C is the abbreviation of the word "Comparator", M is the width (the number of bits) of input words of the comparator, N is the number of the first level comparators, and T is the width of input words of first level comparators. In the formula (3) the following condition must be executed: M = NT.

The hierarchical two-level structure in Fig. 1 can be used as comparators of the first level. By similar way the hierarchical structure for the comparator with the high value of the M can be constructed. The example of the multi-level hierarchical design for the comparator C_16_2x8_2x4_2x2 is shown in Fig. 2. Here the 2-bit comparators C_2 are located at the first level, and the combinatorial circuits CL make all subsequent comparator levels. The generalized hierarchical structure of the binary comparators is described by the formula:

C_M_N Q xT Q _N Q-1 xT Q-1 _ … _N 1 xT 1 , ( 4
)
where Q is the number of levels in the comparator structure, N q is the number of the comparator modules on the level q, and T q is the bitwidth for comparators on the level q, q= Q , 1 . In a formula (4) the following conditions must always be satisfied:

M = N Q T Q ; T q = N q-1 T q-1 ,  q= Q , 1 .
(5)

The number Q of the levels in the formula (4) determines a depth of the combinatorial circuit CL in Fig. 1. Taking into account the first level comparators, the total number of the logic levels in the hierarchical structure ( 4) is equaled of the Q + 1.

The synthesis method of the hierarchical structures of comparators is based on the formula (4) and the conditions [START_REF] Huang | High-performance and power-efficient CMOS comparators[END_REF]. Note that several hierarchical structures can correspond to one comparator. These structures can have the different numbers of levels and vertices at each level. Besides, the hierarchical structures can have different comparators at the first level which are distinguished by the lengths of input words.

4

The Synthesis of the First Level Comparators

In the considered approach for all hierarchical structures of the comparators at the first level it is offered to use the 2-bit comparators. Let A = (a 2 , a 1 ) and B = (b 2 , b 1 ) be input words of the 2-bit comparator. The Boolean function "equal" for the 2-bit comparator is not minimized and it has the form:

E= a 2 & a 1 & b 2 & b 1 + a 2 &a 1 & b 2 &b 1 +a 2 &a 1 &b 2 &b 1 +a 2 & a 1 &b 2 & b 1 . (6)
The Boolean function "greater-than" for the 2-bit comparator after minimization has the following form:

G = a 2 & b 2 + a 1 & b 2 & b 1 + a 2 &a 1 & b 1 . (7)
The logical equations ( 6) and ( 7) for the 2-bit comparators of the first level, the logical equations ( 1) and ( 2) for the combinatorial circuit CL in Fig. 1, and the formula (4) with constraints (5) are used to build the hierarchical tree structures of the comparators.

The hierarchical structure by the nature has the smallest time delay of the signal passing in comparison with the linear decomposition or the sequential implementation. Therefore it is possible to expect that hierarchical structures of the designed comparator will have low implementation cost and high performance.

It is an open question: what formula of the hierarchical comparator structure is the best at implementation for a particular comparator bitwidth on specific FPGA family. The response to this question is defined empirically by experimental researches.

Experimental Results

The following designs of hierarchical comparator structures were developed in Verilog language to check the efficiency of the offered method: one structure of the For designing the hierarchical structures of comparators on 128 bits all the structures of comparators on 8, 16 and 32 bit, and the structure C_4_2x2 (in all 15 structures) were considered. From the structures of comparators on 64 bits the 6 structures, which are the best at an implementation cost at least for one family FPGA/SoC, were selected. Thus it was constructed 21 hierarchical structures of comparators on 128 bits. The hierarchical structures of comparators on 256-, 512-, and 1024 bits were similarly built.

All designed hierarchical comparator structures are described in Verilog and realized with Altera Quartus II 13.1 platform. The implementation cost was measured by the number of the functional generators LUT (Look-Up Table ). The results received by the hierarchical comparator structures were compared to the standard (traditional) description of the comparator in Verilog language [START_REF] Salauyou | Bases of the hardware description language Verilog. Hot line-Telecom[END_REF]. Note that the results obtained by the standard description exactly match the results received by the parametrized function lpm_compare. Some families FPGA/SoC have the identical implementation cost for the offered hierarchical structures of comparators and for the standard description. Therefore all FPGA/SoC families can be divided into three groups: group 1 -Arria II GX, Stratix III, and Stratix IV; group 2 -MAX II, MAX V, Cyclone III, and Cyclone IV; group 3 -Arria V GZ and Cyclone V. The results of experimental researches are given in Table 1, where C_m is the comparator with a width of words on m bits, C S is the implementation cost in case of standard approach, C H is the smallest implementation cost received by using hierarchical structures, and C S /C H is a relation of the corresponding parameters. 1 shows that in all groups for comparators C_2 and C_4 the standard approach and the proposed hierarchical method show identical results. In group 1 the hierarchical method is better for comparators C_16, C_32 and C_64, and the implementation cost decreases from 5.3% to 10.8%. For the comparator C_1024 the hierarchical method exceeds the standard method by 2.225 times. In group 2 since the comparator C_8 and to the comparator C_1024 the hierarchical method is better than the standard method, and the implementation cost decreases from 7.4% to 18.2%.In group 3 the hierarchical method is better than the standard method for comparators from C_32 to C_256, and the implementation cost decreases from 21.7% to 43.0%.

In this work the efficiency of the considered synthesis method of the comparators was researched only concerning the implementation cost. Similar approach can be also used to minimize the delay or the power consumption.

Conclusions

In the provided approach 2-bit comparators were used at the first level of hierarchical structures. Comparators with different number of bits (e.g. 3, 4, 5) can also be used at the first level.

The offered synthesis method of hierarchical comparator structures can be also used to implement of comparators in other languages of hardware description, for example VHDL and SystemVerilog. The provided method can be used to find the best hierarchical comparator structure of a certain size for a specific FPGA or SoC family. The offered method can be enhanced by using of architectural features of the FPGA/SoC, for example fast carry chains, fast cascade chains, buffers LCELL.

Fig. 1 .Fig. 1 .

 11 Fig. 1. The generalized hierarchical two-level structure of the comparator C_M_NxT The combinatorial circuit CL calculates values of the output functions "greaterthan" G and "equal" E for entire hierarchical structure. Inputs for the combinatorial circuit CL are values of output functions of first level comparators. For computing the values of the G and E functions the following equations are used: G = g N + e N & g N-1 + e N & e N-1 & g N-2 +…+ e N & e N-1 & … & e 2 & g 1 ;(1) and

Fig. 2 .

 2 Fig. 2. Implementation a multi-level structure of the comparator C_16_4x4_2x2

Table 1 .

 1 Research results of the hierarchical comparator structures for Altera FPGA/SoC the compiler issues the message: not enough external outputs The analysis of Table

	Comparator Arria II GX		MAX II			Arria V GZ
		Stratix III		MAX V			Cyclone V
		Stratix IV		Cyclone III
					Cyclone IV
		C S	C H	C S /C H C S	C H	C S /C H C S	C H	C S /C H
	C_2	2	2	1.000	2	2	1.000	2	2	1.000
	C_4	4	4	1.000	6	6	1.000	3	3	1.000
	C_8	8	9	0.889	13	11	1.182	6	6	1.000
	C_16	20	19	1.053	27	24	1.125	12	12	1.000
	C_32	41	37	1.108	53	48	1.104	28	23	1.217
	C_64	82	74	1.108	107	96	1.115	59	46	1.283
	C_128	141	149	0.946	213	194	1.098	119	96	1.240
	C_256	254	302	0.841	427	392	1.089	236	165	1.430
	C_512	521	587	0.888	853	794	1.074	(1)	(1)	-
	C_1024	2645	1189	2.225	1707	1590	1.074	(1)	(1)	-
	(1)

Acknowledgements. This research was partially supported by Bialystok University of Technology, Poland, grant no. S/WI/1/2013.