IJCIIS March 2011 Vol. 2 No. 3

International Journal of Computational Intelligence and Information Security, March 2011, Vol. 2, No.
International Journal of
Computational Intelligence and
Information Security
ISSN: 1837-7823
March 2011
Vol. 2 No. 3
© IJCIIS Publication
1
International Journal of Computational Intelligence and Information Security, March 2011, Vol. 2, No. 3
IJCIIS Editor and Publisher

P Kulkarni
Publisher’s Address:
5 Belmar Crescent, Canadian
Victoria, Australia
Phone: +61 3 5330 3647
E-mail Address: [email protected]
Publishing Date: March 30, 2011
Members of IJCIIS Editorial Board

Prof. A Govardhan, Jawaharlal Nehru Technological University, India
Dr. A V Senthil Kumar, Hindusthan College of Arts and Science, India
Dr. Awadhesh Kumar Sharma, Madan Mohan Malviya Engineering College, India
Prof. Ayyaswamy Kathirvel, BS Abdur Rehman University, India
Dr. Binod Kumar, Lakshmi Narayan College of Technology, India
Prof. Deepankar Sharma, D. J. College of Engineering and Technology, India
Dr. D. R. Prince Williams, Sohar College of Applied Sciences, Oman
Prof. Durgesh Kumar Mishra, Acropolis Institute of Technology and Research, India
Dr. Imen Grida Ben Yahia, Telecom SudParis, France
Dr. Himanshu Aggarwal, Punjabi University, India
Dr. Jagdish Lal Raheja, Central Electronics Engineering Research Institute, India
Prof. Natarajan Meghanathan, Jackson State University, USA
Dr. Oluwaseyitanfunmi Osunade, University of Ibadan, Nigeria
Dr. Ousmane Thiare, Gaston Berger University, Senegal
Dr. K. D. Verma, S. V. College of Postgraduate Studies and Research, India
Prof. M. Thiyagarajan, Sastra University, India
Dr. Manjaiah D. H., Mangalore University, India
Dr.N.Ch.Sriman Narayana Iyengar, VIT University ,India
Prof. Nirmalendu Bikas Sinha, College of Engineering and Management, Kolaghat, India
Dr. Rajesh Kumar, National University of Singapore, Singapore
Dr. Raman Maini, University College of Engineering, Punjabi University, India
Dr. Seema Verma, Banasthali University, India
Dr. Shahram Jamali, University of Mohaghegh Ardabili, Iran
Dr. Shishir Kumar, Jaypee University of Engineering and Technology, India
Dr. Sujisunadaram Sundaram, Anna University, India
Dr. Sukumar Senthilkumar, National Institute of Technology, India
Prof. V. Umakanta Sastry, Sreenidhi Institute of Science and Technology, India
Dr. Venkatesh Prasad, Lingaya's University, India
Journal Website: https://sites.google.com/site/ijciisresearch/
2
Contents
1. An Implementation of Vector Control of Induction Motors (pages 4-11)
2. Evolutionary Image Segmentation By Pixel Classification Application To Medical Images

(pages 12-24)
3. A Modified Method for Order Reduction of Large Scale Systems (pages 25-34)
4. A New Approach to Overflow Detection in moduli set {2n-1, 2n, 2n+1} (pages 35-43)
5. DEPTH Data Emission by Parabolic Transaction Heights (pages 44-49)
6. Design of Adaptive Controller for a Robot Gripper using Support Vector Regression
(pages 50-54)
7. Effective String matching Model for Intrusion Detection System (pages 55-63)
3
AN IMPLEMENTATION OF VECTOR CONTROL OF INDUCTION

MOTORS
S.SATYANARAYANAN
PROFESSOR & HEAD – DEPARTMENT OF ELECRICAL AND ELECTRONICS ENGINEERING,

APOLLO ENGINEERING COLLEGE
CHENNAI, TAMIL NADU, INDIA.
Abstract
In order to understand and analyze vector control of induction motors, the dynamic model is necessary.
Unfortunately, the dynamic model equations are complex and there are many different forms of the model
depending on the choice of reference frame. It is the objective to explain various forms in a concise way to
understand clearly. In addition, the fundamental dynamic mechanism of the motor in the synchronous frame is
developed and the basic principles of vector control is discussed in general terms. Only a closed loop control of the
motor meets the requirements including fast dynamic response, accurate speed and torque control or even a higher
efficiency by means of flux optimization. However, the speed sensor has several disadvantages from the viewpoint
of drive cost, reliability and signal noise immunity. This paper deals with the speed control of induction motor
drives without a shaft sensor.
Keywords : Induction Motor, Vector Control, Field Oriented Control, Speed Controller
4
1. Introduction
Much attention has been given to induction motor control for starting, braking, speed reversal, speed change, etc.
When the drive requirements include fast dynamic response and accurate speed or torque control, it is necessary to
operate the motor in a closed loop mode with feedback of the motor speed. Here, the field oriented control (FOC)
technique is used, together with an estimation of the motor speed. Both rotor field value and angle are also estimated
by summation of rotor speed and slip frequency. The induction motor, which is the most widely used motor type in
the industry, has been favored because of its good self-starting capability, simple and rugged structure, low cost and
reliability, etc. Along with variable frequency AC inverters, induction motors are used in many adjustable speed
applications which do not require fast dynamic response. The concept of vector control has opened up a new
possibility that induction motors can be controlled to achieve dynamic performance as good as that of DC or
brushless DC motors. In order to understand and analyze vector control, the dynamic model of the induction motor
is necessary. It has been found that the dynamic model equations developed on a rotating reference frame is easier to
describes the characteristics of induction motors. It is the objective of the article to derive and explain induction
motor model in relatively simple terms by using the concept of space vectors and d-q variables. It will be shown that
when we choose a synchronous reference frame in which rotor flux lies on the d-axis, dynamic equations of the
induction motor is simplified and analogous to a DC motor.
The structure of the implemented sensorless control is based on the extended Kalman filter theory (EKF) using only
the measurement of motor currents for the on-line estimation of the rotor speed [5-10]. A block diagram of the
discrete motor model together with the speed estimator is shown in figure 1. The speed-controlled induction motor is
supplied by a voltage source PWM inverter. The PWM generation is performed by space vector modulation (SVM).
The motor voltages required for the Kalman algorithm are not measured, but calculated by means of the reference
voltages with consideration of the non-linearity of the inverter and the homopolar component generated by the
SVM [1-4]. The entire control system is implemented on a TMS320C31 DSP for the main control. The I/O
subsystem and the PWM generation are based on a TMS320P14 working as a slave-DSP.
There are many models of sensorless speed controllers described in literature dealing with the Extended Kalman
Filter theory. They are mostly based on the models of Brunsbach [5] or Vas [6]. The model of Vas, using the motor
equations in a stator-fixed reference frame, has shown a more stable behavior, but its disadvantage is its higher order
(5 states are observed). This will be a drawback when the EKF algorithm has to be implemented in real-time.
However, the model is much simpler than the first one, since it does not contain conversions between the stator and
field coordinate system, resulting in comparable execution times for both. Nevertheless, this model causes also some
problems, especially at low motor speed and speed reversal. Here, a new model for speed estimation is proposed.
5
2. System Model
The model of the induction motor, described in this paper, is based on the motor equations in a rotor flux reference
frame, choosing d- and q-axis current id, iq, rotor flux iµ, flux position γ and rotor speed ωr as state variable xk and
the fundamental voltage as input uk. This model (1-4) assumes the velocity ωr to be constant in a small time interval
(sampling time Ts):
6
3. Kalman Filter Algorithm
The induction motor torque is dependent both on the air-gap flux and the speed, but neither torque versus flux nor
torque versus speed relationship are linear. This complicates the design of control systems and speed estimation for
induction machines. Due to the lack of a system with linear equations, also the used state model of the induction
motor is non-linear. The mechanical speed and position of the flux are considered as both, state and parameter. The
model matrices B and C depend on the position of the rotor flux, the matrix A on q-axis current iq, rotor flux iµ and
rotor speed ωr.Therefore, the extended Kalman filter (EKF) has to be used to estimate the parameters of the model
matrices, as well. The EKF re-linearizes the non-linear state model for each new estimation step, as it becomes
available. Furthermore, the EKF provides a solution that directly cares for the effects of measurement or system
noise. The errors in the parameters of the system model are also handled as system noise. The used algorithm of the
EKF is based on Brammer [9]. The signal flow of the EKF in a recursive manner is shown in figure 2.
Figure 2: Block diagram of the extended Kalman filter.
All equations of the EKF algorithm can be written as a function of a system vector Φ (12) and an output vector h
(13) describing the re-linearized model of the induction motor. It has to be distinguished between the filter and
predictor equations. The predicted value of the state vector xk+1|k is corrected by multiplying the filter gain and the
difference between estimated and measured output vector yk to the state vector xk|k. In addition still the equation for
the corrected covarianz matrix Pk|k is required.
7
Note, that the flux speed can be written as a function of the rotor speed, q-axis and magnetizing current. This
property is neglected in many speed observers assuming the speed of the rotor flux to be constant during the small
sampling time Ts. In fact, the speed of the rotor flux changes directly with and as fast as the q-axis current. The
substitutions in the model matrices are made based on following equation:
which has to be considered by the derivation of the system vector of the EKF (12). Equation (10)
leads also to an expression of the flux position in discrete time domain:
Considering the mentioned substitutions, the system vector Φ and the output vector h
respectively can be derived from the model equations of the induction motor.
8
Also the derivation of system and output vector are required for the EKF algorithm. All equations of the EKF
algorithm can be written as a function of a system vector Φ (12) and an output vector h (13) describing the re-
linearized model of the induction motor. The derivation of both the system and output vector needed for the EKF
algorithm are given in by:
4. Vector Control of AC Induction Machines
Vector control is the most popular control technique of AC induction motors. In special reference frames, the
expression for the electromagnetic torque of the smooth-air-gap machine is similar to theexpression for the torque of
the separately excited DC machine. In the case of induction machines, the control is usually performed in the
reference frame (d-q) attached to the rotor flux space vector. That’s why the implementation of vector control
requires information on the modulus and the space angle (position) of the rotor flux space vector. The stator currents
of the induction machine are separated into flux- and torque-producing components by utilizing transformation to
the d-q coordinate system, whose direct axis (d) is aligned with the rotor flux space vector. That means that the q-
axis component of the rotor flux space vector is always zero:
The rotor flux space vector calculation and transformation to the d-q coordinate system require the high
computational power of a microcontroller. The digital signal processor is suitable for this task.
9
5. Phase Voltage
The extended Kalman filter algorithm requires the motor voltages as input quantities. An alternative o complex
measurement and filtering of the motor voltage is the use of the reference voltage for the PWM, available at the
output of the current control. The PWM generation is performed by space vector modulation (SVM). The SVM
minimizes the harmonic content, determining the copper losses of the machine, accounting for a major portion of the
machine losses. SVM also provides a more efficient use of the supply voltage in comparison with sinusoidal
modulation methods due to a resulting homopolar system in all three phases (multiple of third harmonics). This
homopolar system containing in the phase voltages, must be considered in the Park transformation. In case of an
ideal inverter, the filtered phase voltage U assumes the shape of the reference voltage Uref. Due to the delayed
reaction of almost all semiconductor switches at turn-on and turn-off, the phase voltages strongly deviate from the
reference voltages. This leads in the Kalman filter algorithm to large position and speed errors, especially at low
motor speed where the error voltage becomes a multiple of the reference voltage. With a positive current, the duty
cycles are shorter, with negative currents longer than required. Hence, the actual duty cycle of a bridge is always
different from the one of the reference voltage. It is either increased or decreased, depending on the load current
polarity. This effect is described by an error voltage ∆U
dependent on the dead-time td, the DC-bus voltage Uc, the PWM-frequency fPWM and the voltages UD and UT at
IGBT and diode [2]. These voltage values and the resistances RT and RD of the switch change the inverter output
from its intended value Uref to
used as input of the Kalman filter. Note that the calculation of the phase voltages described above, is only valid
without strong over-modulation. The voltage spectrum in normal operation consists of one fundamental and many
higher harmonics around the PWM frequency. Over-modulation leads to a voltage spectrum consisting of all uneven
harmonics. In fact, a current controller with an anti-windup system will automatically avoid these operation points
and low harmonics.
6. Summary and Scope for future Work
The field oriented control (FOC) technique is used together with an estimation of the motor and flux speed and field
angle. This paper presents the design and the implementation of a sensorless speed control of induction motor drives
based on the extended Kalman filter theory. Only measurements of motor current are required for the on-line
estimation of the rotor speed. The motor voltages required for the filter algorithm are not measured, but calculated
with consideration of the non-linearity of the inverter and homopolar component due to SVM. The availability of
fast digital signal processors has made it possible to compute the speed and other parameters such as rotor field on
line. Keeping the size of the program reasonable and still reach a very good performance was achieved by
optimizing the model with hand calculations and exploiting the symmetry of the matrices. The final algorithm can
be implemented with relatively few instructions. Results of the dynamic and steady state behavior of a sensorless
speed control of an induction motor are given. After the correct system model was chosen for the Extended Kalman
Filter, the results were satisfactory. Both at very low and at high motor speed with flux weakening the proposed
control scheme is working very well. The described control system is a solution without mechanical sensors for a
wide range of applications where good steady state and dynamic properties are required. At present, sensor-based
controls are still widely used in industrial and transportation applications. But in the near future, speed sensorless-
10
based drive systems will become a practical reality and will be used in many industrial applications. Sensorless-
based systems will provide higher reliability and operation in adverse environmental conditions at a lower cost.
References
[1] Leonhard, Control Of Electrical Drives, Springer-Verlag, 1985.

[2] B K Bose, "Power Electronics and Variable Frequency Drives", IEEE Press, New York, 1997.
[3] P Vas, "Vector Control of AC Machines", Oxford Science Publications, New York, 1990.
[4] J M D Murphy, F G Turnbull, "Power Electronic Control of AC Motors", Pergamon Press, New York, 1988.
[5]B-J Brunsbach, G Henneberger, Einsatz eines Kalman-Filters zum feldorientierten Betriebeiner
Asynchronmaschine ohne mechanische Sensoren, Archiv für Elektrotechnik, Springer-Verlag, 1990.
[6]G Henneberger, B-J Brunsbach, Th Klepsch “ Field Oriented Control of Synchronous and Asynchronous Drives
without mechanical Sensors using Kalman Filter”, EPE Firenze, pp. 664-671, 1991.
[7]T Du, P Vas, A F Stronach, Brdys, “Application of Kalman Filters and Extended Luenberger Observers in
Induction Motor Drives”, Intelligent Motion Proceedings, 1994.
[8] Motorola, Inc.(2001). DSP56F80x User’s Manual, DSP56F801-7UM/D, Rev. 3.0.
[9] K S Rajashekara, A Kawamura, "Sensorless Control of Permanent Magnet AC Motors", IEEE IECON
Proceedings, pp. 1589-1594, 1994.
[10]Brammer, Siffling, “Kalman-Bucy Filter, Deterministische Beobachtung und stochastische Filterung” R.
Oldenbourg Verlag München, Wien, 1994.
[11] T Ohtani, N Takada, K Tanaka, " Vector Control of Induction Motor without shaft encoder", IEEE IAS Annu.
Meet. Conf. Rec., pp. 500-507, 1989.
[12] A. M. Trzynadlowski, “The Field Orientation Principle in Control of Induction Motors,” Kluwer Academic
Publishers, 1994.
[13]J. Holtz, "Pulse Width Modulation for Electronic Power Conversion," Proceedings of IEEE, Vol.82, No.8,
pp.1194-1214, Aug. 1994.
11
Evolutionary Image Segmentation By Pixel Classification

Application To Medical Images
A.EL Allaoui1, M. Merzougui1, M. Nasri1, M. EL Hitmy2 and H. Ouariachi 1
1
LABO MATSI, ESTO, B.P 473, University of Mohammed I, OUJDA, MOROCCO.
2
LABO LETAS, FSO, University of Mohammed I, OUJDA, MOROCCO
[email protected]; [email protected]; [email protected]
Abstract
In this paper, we propose a segmentation method based on pixel classification and evolution strategies. The
application of this evolutionary method on synthetic and medical images help to validate this method and show its
interest in the problem of decision support in medical diagnosis.
Keywords: Segmentation, evolutionary segmentation, Classification, evolutionary strategies, Segmentation by pixel

classification.
12
1. Introduction
The segmentation is an essential stage in image processing. There are many consistent methods available today
for image segmentation, among these, there is the segmentation based on pixels classification as a function of their
grey level values [1][7][8][12]. Every pixel in the image holds an inherent relationship with the pixels in its
surrounding. The information at a particular pixel may be in relation with the information over the whole or part of
the image. We may be interested in the mean or the median values of the pixels grey level.
The process of segmentation by pixel classification consists of two stages: [1] [7] [8] [12].
• Acquisition of data for each pixels in order to form the attribute vector
• Pixel classification based on the acquired information
Acquisition stage
For each pixel, we compute two values, the mean value of the grey levels (MGL), and the difference between
the MGL and the maximum value of the grey levels surrounding the particular pixel (DMGL). For this purpose, we
use a square window centred at the particular pixel.
Classification stage
Kmeans and evolutionary Kmeans are used for this classification purpose. The two algorithms use the
information provided by the parameters MGL and the DMGL, associated with each and individual pixel in order
to classify the pixel with respect to centers that evolve at each iteration
In Section 2 image segmentation with Kmeans algorithm is presented. Section 3 gives an introduction to
evolution strategies approach. The proposed evolutionary Kmeans is presented in section 4, along with the image
evolutionary segmentation. In section 5, a validation of our approach is given, experimental results are obtained over
synthetic and medical images, noise has been added to the synthetic image in order to evaluate its effect. Finally we
give a conclusion.
2. Kmeans classification
2.1. Descriptive elements
Consider a set of M objects {O1, O2,..., OM} characterized by N attributes, grouped in a line vector form V = (a1
a2 ... aN). Let Ri = (aij) 1≤j≤N be a line vector of RN where aij is the value of the attribute aj for the object Oi. Let
mat_obs be a matrix of M lines (representing the objects Oi) and N columns (representing the attributes aj):
( )
mat _ obs = aij 1≤i≤ M (1)
1≤ j ≤ N
V is the attribute vector, Ri is the observation associated with Oi or the realization of the attribute vector V for this
object, RN is the observations space [1] and mat_obs is the observation matrix associated with V. The ith line of
mat_obs is the observation Ri. Ri belongs to a class CLs, s=1, …, C.
2.2. Kmeans algorithm
The Kmeans algorithm is one of the most common algorithms used for the classification. We are given maxobs
observations (Ri)1≤i≤M which must be associated with C classes (CLs)1≤s≤C of centers (gs)1≤s≤C. The centers (gs)1≤s≤C are
line vectors of N dimension.
The Kmeans is based on the minimization of the optimization criterion given by [10] [20] [21]:
1 M C
∑∑ Ri − g s
2
J= (2)
2 i =1 s =1
where . is a distance which is generally supposed to be Euclidean.
The KM algorithm supposes that the number of classes C is known a priori.
13
2.3. Kmeans segmentation

The objects that are processed by the KM algorithm are the pixels of the input image. The observation matrix in
this case is formed by two columns which represent the attributes associated with each pixel of the image: the
columns are associated with the MGL and the DMGL. The size of the square window used must have an odd length
(3 * 3, 5 * 5,...) [1][8][12][15]. In this process each pixel is attributed to a specific class. The resulting image is
segmented into C different regions where each region corresponds to a class.
3. Evolution strategies
Evolutionary strategies (ES) are particular methods for optimizing functions. These techniques are based on the
evolution of a population of solutions which under the action of some precise rules optimize a given behavior, which
initially has been formulated by a given specified function called fitness function [2].
An ES algorithm manipulates a population of constant size. This population is formed by candidate points called
chromosomes. Each of the chromosomes represents the coding of a potential solution to the problem to be solved, it
is formed by a set of elements called genes, these are reals.
At each iteration, called generation, is created a new population from its predecessor by applying the genetic
operators: selection and mutation. The mutation operator perturbs with a Gaussian disturbance the chromosomes of
the population in order to generate a new population permitting to further optimize the fitness function.
This procedure allows the algorithm to avoid the local optimums. The selection operator consists of constructing the
population of the next generation. This generation is constituted by the pertinent individuals [2] [3][11].
Figure 1 illustrates the different operations to be performed in a standard ES algorithm [2][3] :
Random generation of the initial population

Fitness evaluation of each chromosome
Repeat
Select the parents
Update the genes by mutation
Select the next generation
Fitness evaluation of each chromosome
Until Satisfying the stop criterion
Figure 1: Standard SE algorithm.
4. Evolutionary Kmeans classification

4.1. Proposed coding
The KM algorithm consists of selecting among all of the possible partitions the optimal partition by minimizing
a criterion. This yields the optimal centers (gs)1≤s≤C. Thus we suggest the real coding as:
chr =(g sj )1≤ s ≤C,1≤ j ≤ N
(
= g11..g1N g 21..g 2N ..g s1..g sN ..gC1..gCN
(3) )
The chr chromosome is a real line vector of dimension C×N. The genes (gsj)1≤j≤N are the components of the gs center:
g s =(g sj )1≤ j ≤ N =(g s1g s2..g sj..g sN ) (4)
To avoid that the initial solutions be far away from the optimal solution, each chromosome chr of the initial
population should satisfy the condition:
g sj∈[min aij1≤i ≤ M ,max aij1≤i ≤ M ] (5)
In the EKM algorithm, we discard any chromosome with a gene that does not satisfy this constraint. This gene, if
any, is replaced by an other one which complies with the constraint.
14
4.2. The proposed fitness function

Let chr be a chromosome of the population formed by the centers (gs)1≤s≤C, for computing the fitness function
value associated with chr, we define the fitness function F which expresses the behavior to be optimized (J
criterion):
1 M C 2
F (chr ) = ∑ ∑ Ri − g s (6)
M i =1 s =1
The chromosome chr is optimal if F is minimal.
4.3. The proposed mutation operator

The performances of an algorithm based on evolutionary strategies are evaluated according to the mutation
operator used [11]. One of the mutation operator form proposed in the literature [20] [21]is given by:
chr* = chr + σ × N(0,1) (7)
where chr* is the new chromosome obtained by a Gaussian perturbation of the old chromosome chr. N(0,1) is a
Gaussian disturbance of mean value 0 and standard deviation value 1, σ is the strategic parameter. σ is high when
the fitness value of chr is high. When the fitness value of chr is low, σ must take very low values in order to be not
far away from the global optimum.
We have been inspired from this approach to propose a new form of the mutation operator. The fact that we
have proposed a new mutation operator is motivated by our interest to reach the global solution in a small
computational time.
Let chr be a chromosome of the population formed by the centers (gs)1≤s≤C.

Let Ri ∈ CLs if Ri − g s = min s '=1,C Ri − g s ' , i.e. the class consisting of the Ri observations that are closest to the
center gs. Let g°s be the center of gravity of the CLs class
∑ Ri
Ri ∈CLs
g s° = where ls =card(CLs ) (8)
ls
The mutation operator which we propose in this work consists in generating, from the chr, the new chromosome
chr* formed by the centers (g*s)1≤s≤C, as:
g*s = gs + fm × ( g°s - gs) × N(0,1) (9)
where fm is a multiplicative constant factor taken to be randomly chosen between 0.5 and 1. The new strategic
parameter proposed σ’ = fm × ( g°s - gs ) is low when gs gets closer to g°s and is high when gs is far from g°s. The
proposed σ’ has two advantages:
- When chr is far from the global solution, chr is subjected to a strong Gaussian perturbation allowing chr to
move more quickly in the research space and in the same time to avoid local solutions.
- σ’ controls the Gaussian perturbation level. Indeed, as the chromosome chr gets closer to the global
solution, the Gaussian perturbation level is reduced until becoming null at convergence.
Generating children from parent chromosomes we have adopted the technique of selection by ordering. We have
also used the elitist technique [10].
15
4.4. The proposed EKM algorithm

Figure 2 shows the different steps of the proposed EKM algorithm. [10][11] [18] [19].
Stage 1:
1.1. Fix:
- The size of the population maxpop.
- The maximum number of generations maxgen.
- The number of classes C.
1.2. Generate randomly the population P:
P = {chr1, .., chrk, ..., chrmaxpop}
1.3. Verify for each chr of P the constraint:
gsj∈[min aij, max aij], 1≤i≤M
1.4. For each chr of P attribute, the observations Ri to the corresponding classes:
Ri ∈ CLs if Ri − g s = min s '=1,C Ri − g s '
1.5. Update the population P, for each chr of P do:
gs + ∑ Ri
Ri ∈CLs
g s' = where ls =card(CLs )
1+ls
1.6. Compute for each chr of P its fitness value F(chr).
Stage 2:
Repeat
2.1. Order the chromosomes chr in P from the best to the poor ( in an increasing order of F).
2.2. Choose the best chromosomes chr.
2.3. For each chr of P attribute, the observations Ri to the corresponding classes:
2.4. Generate randomly the constant fm (fm ∈ [0.5, 1]).

2.5. Mutation of all the chromosomes chr of P except the first one (elitist technique):
g*s = gs + fm × ( g°s - gs) × N(0,1)
2.6. For each chr of P attribute except the first one, the observations Ri to the corresponding classes:
2.7. Update the population P, for each chr of P except for the first one, do:
gs + ∑ Ri
Ri ∈CLs
g s' = where ls =card(CLs )
1+ls
(The population P obtained after the updating is the population of the next generation )
2.8. Compute for each chr of P its fitness value F(chr).
Until Nb_gen (generation number) ! maxgen
Figure 2: The proposed EKM algorithm.
4.5. EKmeans Segmentation

The procedure to be carried out here is exactly the same at that taken in (2.3) for the Kmeans segmentation. The
difference is in the classification algorithm which now is evolutionary.
16
5. Experimental results and evaluations

5.1. Introduction
In order to evaluate the performances of the proposed method we have considered three grey level images, a
synthesised image, the same synthesised image to which noise is added [1] [4], a real image of the brain taken by
MRI [6][9][13][14]. The segmentation is carried out by the two algorithms KM and EKM for different values of C.
5.2. Synthetic image
We have constructed a synthetic image which we name SYNTH1 of size 50 * 70. The image contains four
objects of different geometrical forms, figure 3.
Figure 3: Synthesised image SYNTH1

Table 1 shows the classes of SYNTH1 along with the grey level values and the number of pixels of each class.
Table 1: Information on SYNTH1
Number
Grey
Class Description of pixels
level GL
Np
Background
1 255 1604
of image
2 Rectangle 29 1036
4 Triangle 76 317
5 Disc 0 543
We considered for this test the attributes (MGL, DMGL) in a 3 * 3 window, and the number of classes is C =4.
Figure 4 shows the results of segmentation procedure by two algorithms KM and EKM
EKM KM
Figure 4: Result of image segmentation
17
The EKM algorithm converges quickly, in 3 generations, figure 5.
10000
8000
6000
4000
2000
0
0 5 10 15 20 25 30
Figure 5: Fitness value with respect to the generation.

Table 2 shows the results of the segmentation.
Table 2: Results of segmentation
Initial
Description EKM KM
image
1368 Background 1368 1368
1036 Rectangle 907 1224
317 Triangle 468 0
543 Disc 521 468
The results show that the EKM clearly detects the four objects of the image, background, triangle, rectangle and
disc. The KM was not able detect the triangle
The number of misclassified pixels for both methods EKM and KM is respectively 302, 580. The corresponding
error rate is:
302
τ EKM = = 9.25% (11)
3264
580
τ KM = = 17.76% (12)
3264
The two algorithms were run several times and we noticed that the EKM obtains each time the same result while
the KM obtains different results. We can conclude that the EKM is the most stable, it outperforms the KM and it
obtains good results
5.3. Noisy synthetic image

In this test, we add a "salt and pepper" type of noise to SYNTH1 and we obtained the noisy image SYNTH2,
figure 6.
18
.
Figure 6: Noisy image SYNTH2
Table 3 shows the classes of SYNTH2, the grey level values and the number of pixels in each class.
Table 3: Information on SYNTH2
Number
Grey
Class Description of pixels
level GL
Np
1 Background 255 2144
2 Rectangle 29 961
4 Triangle 76 298
5 Disc 0 630
We have considered for this test the attributes MGL, DMGL, a window of size 3 * 3, and the number of classes
C =5. Figure 7 shows the results of image segmentation applied to SYNTH2 by KM and EKM.
EKM KM
Figure 7: Result of image segmentation

The EKM algorithm converges quickly, in 2 generations, figure 8.
19
4500
4000
3500
3000
2500
2000
1500
1000
500
0 5 10 15 20 25 30

The results show that the segmentation EKM clearly detects the four image objects (triangle, rectangle and
disc) and gives good results. The KM method does not detect the triangle.
We notice her again that the EKM is the most stable procedure because it goes to the same convergence point
for several running times of the algorithm. The KM goes to different solutions when it is run again repeatedly.
5.4. Brain image IRM
We have considered for this test an MRI brain image of size 141 * 117, which contains a tumor, figure 9. We
considered a windows of size 9 * 9, and a number of classes, test A: C = 4, and test B: C = 7. The segmentation
objective in this case is to detect the tumor.
Figure 9: MRI Brain image sample containing a tumor indicated by a white small region.
Test A : C=4
EKM KM
20
EKM KM
EKM KM
Figure 10: Image segmented into 4 classes (3 times running the algorithm)
Table 4: Number of pixels for each class
Class
Trial 1 Trial 2 Trial 3
number
CL1 138 138 138
CL2 3102 3102 3102
EKM
CL3 4821 4821 4821
CL4 6436 6436 6436
CL1 1285 2112 2971
CL2 3225 2845 3239
KM
CL3 3558 3117 4108
CL4 6429 6423 4179
11
10
3
0 5 10 15 20 25 30

Figure 11 shows the rapid convergence of the EKM. Figure 10 and table 4 show the stability of the results
obtained by the EKM for different running of the algorithm, while the results obtained by KM contain many
changes. The tumor is clearer in the case of EKM.
21
Test B : C=7
EKM KM
EKM KM
EKM KM
Figure 12: Image segmented into 7 classes (3 times running the algorithm)
Tableau 5: Number of pixels for each class

Class
Trial 1 Trial 2 Trial 3
number
CL1 0 0 0
CL2 0 0 0
CL3 39 39 39
EKM CL4 99 99 99
CL5 3102 3102 3102
CL6 4821 4821 4821
CL7 6436 6436 6436
CL1 374 374 358
CL2 466 466 397
CL3 1463 2170 1323
KM CL4 2458 2505 2917
CL5 2505 2813 2967
CL6 3148 3004 3094
CL7 4083 3165 3441
22
6.5
5.5
4.5
3.5
0 5 10 15 20 25 30

Figure 13 shows the rapid convergence of the EKM. Although the number of the classes considered has
increased in this test, the EKM shows its outperforming over the KM.
Figure 12 and table 5 show stability of convergence and clearer detection of the tumor for the EKM with respect
to KM for different running of the algorithm.
6. Conclusion
Kmeans image segmentation show some stability difficulties due to the initialisation problem of the KM. We
have proposed the evolutionary Kmeans image segmentation in order to get around this difficulty. The proposed
approach has been validated on two synthetic images and an MRI brain image containing a tumor.
The experimental results obtained show the rapid convergence and the good performance of this approach. The
instability problem has been eliminated.
This approach may be used for problems of decision support in medical diagnosis.
7. Références
[1] Cocquerez T.P. et Phillip S. "Analyse d'images : Filtrage et segmentation". Editions MASSON, Paris, 1995.
[2] Hall, L. Q., Özyurt, I. B. et Bezdek, J. C. " Clustering with a genetically optimized approach ". IEEE Trans. on
Evolutionary Computation, Vol.3, N°2, pp. 103-110, july 1999.
[3] Presberger, T., Koch, M. " Comparison of evolutionary strategies and genetic algorithms for optimization of
a fuzzy controller ". Proc. of EUFIT’95, Aachen, Germany, august 1995.
[4] Florence Huet et Sylvie Phlipp Etude de contours haute-échelle pour la segmentation et la fermeture de
contours en présence de zones texturées et/ou bruitées. Traitement du Signal 1998 Volume 15 - n° 1
[5] H.Ouariachi, Classification non –Supervisée de données par la réseaux de neurones et par une approche
évolutionniste : application à la segmentation d’images. . Thèse de doctorat. Université Mohammed premier
Oujda 2001.
[6] Barra, V. : Fusion d’Images 3D du Cerveau : Etude de Modèles et Applications : Ph.D. Thesis, Université
d'Auvergne, Clermont-Ferrand (France), 2000.
[7] Christophe Saint-Jean, Classification paramétrique robuste partiellement supervisée en reconnaissance des
formes, Thèse de Doctorat, université de La Rochelle - UFR Sciences Laboratoire d’Informatique et
d’Imagerie Industrielle 2001.
[8] N.Vandenbroucke, L.Macaire, J.G. Postaire, Color image segmentation by pixel classification in an adapted
hybrid color space. Application to soccer image analysis., Computer Vision and Image Understanding 90 (2),
190-216, (2003).
[9] Zitouni Rafik, Segmentation Contextuelle des images IRM du cerveau humain (Application de la
classification Semi Supervisée), Thèse d’ingéniorat, université de Sétif, institut d’informatique 2004.
[10] Nasri M. Contribution à la classification de données par Approches Evolutionnistes : Simulation et
Application aux images de textures’’. Thèse de doctorat. Université Mohammed premier Oujda 2004.
23
[11] Nasri M, M. EL Hitmy, H. Ouariachi and M.Barboucha. Optimization of a fuzzy classification by evolutionary strategies.
In proceedings of SPIE Conf.,6 th international conference on quality control by artificial vision,vol.5132,pp.
220230,USA, 2003.Repulished as an SME Technical Paper by The society of manufacturingn .
[12] L. Macaire, N. Vandenbroucke, J.G Postaire Segmentation d'images par classification spatio-colorimétrique
des pixels. Traitement du signal 2004 vol 21 N spécial L'image numérique couleur 423-437
[13] Z. Rafik1, B. Ihssen. Segmentation Contextuelle Des Images IRM Cérébrales par Le FCM Semi Supervisé.
Première Etape a l’Aide au Diagnostic. Journées Francophones d’Informatique Médicale, Lille 12-13 mai
2005
[14] Semchedine, M., Toumi, L., Moussaoui, A. : Nouvelle Approche de Classification Multimodale Hybride
d’Images IRM dans un SMA , Journées internationales sur l’informatique graphique .Tébessa 2006
[15] Dou, W. : Segmentation d'images multi spectrales basée sur la fusion d‘informations : application aux
images IRM. Thèse doctorat de l’université de Caen, Spécialité : Traitement du Signal et des Images, 2006
[16] Non-dominated Sorting Evolution Strategy-based K-means Clustering Algorithm for Accent Classification.
S. Ullah, F. Karray, and J.M. Won. 978-1-4244-2175-6/08/2008 IEEE
[17] J. Gadeyne & A. Nassar Segmentation d'image naturelle texturée localement par fusion bayesienne de
segmentation locale en deux classes.22 f_evrier 2009
[18] A. EL Allaoui, M. Merzougui, M. Nasri, M. EL Hitmy and H. Ouariachi. Optimization of Unsupervised
Classification by Evolutionary Strategies. IJCSNS International Journal of Computer Science and Network
Security, ISSN: 1738-7906, Vol. 10 No. 6 pp. 325-332 June, 2010.
[19] M. Merzougui, A. EL Allaoui, M. Nasri, M. EL Hitmy and H. Ouariachi. Unsupervised classification using
evolutionary strategies approach and the Xie and Beni criterion. IJAST International Journal of Advanced
Science and Technology, ISSN: 2005-4238, Vol. 19, pp 43-58 June, 2010.
[20] Bezdek, J. C. "Cluster validity with fuzzy sets". J. Cybernetics, Vol.3, N°3, pp. 58-73, 1974.
[21] Karayiannis, N. B., Bezdek, J. C. et Hathaway, R. J. "Repairs to GLVQ : a new family of competitive learning schemes".
IEEE Trans. on Neural Networks, Vol.7, N°5, pp. 1062-1071, 1996.
Biography
Ahmad EL ALLAOUI works on image processing and pattern recognition in MATSI laboratory of the
school of Technology, University of Oujda, Morocco. He has his master in the field of computer sciences at
University the Med Benabdellah at Fez. His main field of research interest is classification of texture based on
new methods (genetic and evolutionary approaches, neural networks, fuzzy logic).
Mohammed Merzougui works on image processing and pattern recognition in MATSI laboratory of the
school of Technology, University of Oujda, Morocco. He has his master in the field of computer sciences at
the same University. His main field of research interest is classification of texture images based on new
methods (genetic and evolutionary approaches, neural networks, fuzzy logic).
M’barek Nasri is a senior lecturer at the School of technology of Oujda University since 1996. He obtained
his Ph.D degree in 2004 in the field of data Classification from the University of Oujda, department of
M. Nasri physics. He obtained the habilitation degree in 2006 from the same university. His field of research interest is
in image processing and its application to the quality control by artificial vision and medical imaging.
24
A MODIFIED METHOD FOR ORDER REDUCTION OF LARGE SCALE

SYSTEMS
Dr. G.Saraswathi
Dept. of EEE, GIT, GITAM University
Visakhapatanam, India
[email protected]
Abstract
In this paper, an effective procedure to determine the reduced order model of higher order linear time
invariant dynamic systems is discussed. Numerator and denominator polynomials of reduced order model are
obtained by redefining the time moments of the original high order system. The proposed method has been verified
using numerical examples.
Keywords: order reduction, eigen values, large scale systems, modeling.
25
1. Introduction:
The rapid advancements in science and technology led to extreme research in large scale systems. As a result
the overall mathematical complexity increases. The computational procedure becomes difficult with increase in
dimension. Therefore high-order models are difficult to use for simulation, analysis or controller synthesis. So it is
not only desirable but necessary to obtain satisfactory reduced order representation of such higher order models.
Here the objective of the model reduction of high order complex systems is to obtain a Reduced Order Model(ROM)
that retains and reflects the important characteristics of the original system as closely as possible.
Several methods are available in the literature for large-scale system modeling. Most of the methods based on
the original continued fraction expansion technique [1, 2] fail to retain the stability of the original systems in the
reduced order models. To overcome this major draw back, alternative methods have been suggested but the common
limitation of such extension is that in some cases, they may generate models of order even higher than that of the
original system [1-3].
Modal-Padé methods [4] use the concept of the dominant poles and matching the few initial time moments of
the original systems. The major disadvantage of such methods is the difficulty in deciding the dominant poles of the
original system, which should be retained in the reduced order models. Retaining the poles closest to the imaginary
axis need not be always the best choice. Sinha et al, [5] used the clustering technique but the serious limitation of
this method is the number and position of zeros of the original system sometimes decides the minimum order of the
reduced order model. The major disadvantage of such methods is in deciding the clusters of poles hence cannot
generate unique models.
Some methods based on Eigen Spectrum which is the cluster of poles of high order system considered to derive
the approximant. Pal et al proposed [6] pole-clustering using Inverse Distance Criterion and time-moment matching.
Vishwakarma and R.Prasad [7,8] modified the pole clustering by an iterative method. The difficulty with these
methods is in selecting poles for the clusters. Mukherjee [9], suggested a method based on Eigen Spectrum Analysis.
The Eigen Spectrum consists of all poles of the high order system. The poles of the reduced model are evenly spaced
between the first and last poles. Parmar et al [10] proposed a mixed method using Eigen Spectrum Analysis with
Factor division algorithm to determine the numerator of the reduced model with known denominator. Parmar et al
[11] proposed another mixed method using Eigen Spectrum Analysis equation and Particle Swarm method to find
the reduced model. The methods based on eigen spectrum analysis cannot be applied to high order systems having
complex poles. Saraswathi et al [17] proposed a method retaining some of the properties of original system based on
eigenspectrum. The method can be applied for systems having both real and complex poles unlike the other existing
methods [9-11].
In the proposed reduced order method the Time moments and Markov parameters are redefined as function of
Residues and poles for strictly proper rational transfer functions having real and complex distinct poles. Poles of the
Reduced Order Model (ROM) are selected by considering the highest contribution of each pole in redefined Time
Moments (RTMs) and lowest contribution in Redefined Markov Parameters (RMPs).
2. Proposed method:
Let the original high order transfer function of a linear time invariant continuous system of nth order be
;m<n ...(1)
where ; n is the number of poles and ; m is the number of zeros,

of high order system G(s). The poles and zeros may be real and/or complex. If
they are complex, they occur in conjugate pairs.
The reduced order model of kth order using proposed new algorithm is defined as
;k<n … (2)
where ; k is the number of poles and ; r ≤ m, r is the number of zeros,

± of reduced order model . In the reduced model poles and zeros may be real
and/or complex. If they are complex, they occur in conjugate pairs as mentioned for original system.
We know that the power series expansion of G(s) about s = 0 is
26
…(3)
Where ; I = 0,1,2,3, …..
The expansion of G(s) about s = ∞ is

…(4)
Where I = 0,1, 2, 3, …..
Define the expressions for redefined time moments (RTMs) as
…(5)
where And Pj are residues.
Define Redefined Markov Parameters (RMPs) as

…(6)
where And Pj are residues.

The denominator polynomial Dk(s) of the kth reduced model are obtained by selecting the poles with the highest
contribution in RTMs and lowest contribution in RMPs according to their contribution weight age as shown in Table
I.
Table I : Contributions of individual poles
Parameters 1 2 3 … j … n Sum
RTMs xi1 xi2 xi3 … xij … xin RTMi
RMPs yi1 yi2 yi3 … yij … yin RMPi
Where xij is the contribution of pole j in RTMi and yij is the contribution of pole j in RMPi. The numerator
polynomial, Nk(s) of the kth order reduced model is obtained by retaining the first few initial RTMs and RMPs of the
original system as follows:
; r = r1 + r2, r ≤ m and r1 ≥ 1. …(7)
where ; j = 0, 1, 2, 3,…, r1 ; r1 is number of RTMs …(8)
and ; j = 0, 1, 2, 3,…, r2 ; r2 is number of RMPs …(9)
Example 1:
Let us consider an eighth order system described by the transfer function [11]:
The poles of the system are -λ1 = -1, -λ2 = -2, -λ3 = -3, -λ4 = -4, -λ5 = -5, -λ6 = -6, -λ7 = -7, -λ8 = -8. The zeros of the
system are –δ1 = -0.3195, -δ2 = -2.0188, -δ3 = -2.1902 – 1.2429i, -δ4 = -2.1902 + 1.2429i, -δ5 = -4.5825 – 4.7137i, -
δ6 = -4.5825 + 4.7137i, -δ7 = -12.6719.
For a second order model the contributions of individual poles in RTMs and RMPs are tabulated in Table II. Poles
having highest contribution in RTMs and lowest contribution in RMPs as per their absolute values are considered in
the reduced order model. The poles are and .
27
Table II : Contribution of poles in RTMs and RMPS of HOS

λ1 λ2 λ3 λ4 λ5 λ6 λ7 λ8 Sum
RTM0 =1.0 -3.00 2.02 -2.23 2.89 -0.74 -0.20 1.05 1.20 1.00
RMP0 =18.0 -3.00 4.04 -6.66 11.56 -3.68 -1.20 7.33 9.63 18.0
The denominator polynomial of the 2nd order reduced model is

D2(s) = (s+1)(s+6) = s2 + 7s + 6
Using equation (7) numerator of the second order model is obtained by matching first Redefined Time moment and
first Redefined Markov Parameter of the original system from Table II.
N2(s) = 18s + 6
The transfer function of the second order reduced model is
The second order model proposed by Mukherjee [9] is
The second order model proposed by Parmar [11] is
The Comparison of step responses of original system with proposed model is shown in Fig.1. Comparison of the
Mukherjee’s [9], Parmar [11] with original system and proposed method is shown in Fig.2 and their initial time
responses are compared in Fig.3. A comparison of outputs of step response with other methods is tabulated in Table
III.
Step Response
2.5
Original
Proposed
2
1.5
Amplitude
0.5
0
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
Time (sec)
Fig.1: Comparison of step responses of G1(s) and R2(s)
28
Step Response
2.5
Original
Proposed
2 Mukherjee
Parmar
1.5
Amplitude
0.5
-0.5
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
Time (sec)
Fig.2: Comparison of step responses of G1(s), R2(s), R2M(s) and R2P(s)
Step Response
2.5
1.5
Amplitude
0.5
Original
0 Proposed
Mukherjee
Parmar
-0.5
0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2
Time (sec)
Fig.3: Comparison of initial step responses of G1(s), R2(s), R2M(s) and R2P(s)
29
Table III : Comparison of outputs of step responses of various ROMs at 3 seconds

Method of order reduction Transfer Function Output
Original System G1(s) 1.14
Proposed algorithm 1.12
Mukherjee[9] 1.11
Parmar et al[10] 1.11
Parmar et al[11] 1.11
Prasad and Pal[11] 1
Hutton and Friedland[11] 1.52
Krishnamurthy and Seshadri[11] 7.92x103
Gutman et al[11] 0.413
Pal[12] 1.58
Mukherjee etal[13] 1.05
Shamash], Lucas[14] 1.22
Chen et al[15] 2.4
Mittal et al[16] 1.23
Example 2:
Considering the problem attempted by [6] and [15]
The poles of the system are -λ1 = -0.0919, -λ2 = -2.0244 – 0.9646i, -λ3 = -2.0244 + 0.9646i, -λ4 = -7.6744 -13.4461i,
-λ5 = -7.6744 +13.4461i, -λ6 = -32.0753 -38.8493i, -λ7 = -32.0753 +38.8493i. The lone zero of the system is δ1 = -
0.0833. The contributions of individual poles in RTMs and RMPs (non zero terms) are tabulated in Table IV and V.
Poles having highest contribution in RTMs and lowest contribution in RMPs as per their absolute values are
considered. For the third order model the poles of the original system are
and .
Table VI: Contribution of poles in RTMs and RMPs of HOS (λ1 to λ4)
λ1 λ2 λ3 λ4
RTM0 -0.01 0.06+ 0.16i 0.06- 0.16i 0.0002- 0.0021i
RTM1 -0.14 0.06+ 0.05i 0.06- 0.05i -1.12x10-4 -7.55 x10-5i
RMP6 7.5312x10-9 16.17+ 14.367i 16.17-14.36i -3.0x103+2.86x104 i
30
Table V: Contribution of poles in RTMs and RMPs of HOS (λ5 and λ7)
λ5 λ6 λ7 Sum
RTM0 0.2x10-3 + 0.002i -1.95x10-5-1.32x10-6i -1.95 x10-5 +1.32 x10-6i 0.11
-4 -5 -7 -7 -7 -7
RTM1 -1.12x10 +7.6x10 i -2.67x10 + 2.82x10 i -2.67 x10 -2.82 x10 i -0.03
3 4 5 5 5 5
RMP6 -3.0x10 -2.86x10 i 1.9x10 -2.57x10 i 1.9 x10 +2.57x10 i 3.75 x105
The denominator polynomial of the 3rd order reduced model is

D3(s) = (s + 0.0919)(s + 2.0244 – j0.9646)(s + 2.0244 + j 0.9646)
= s3 + 4.141s2 + 5.401s + 0.4623
Numerator of the ROM is obtained using equation (2.65) and matching first two RTMs (0.11 and -0.03) and one
RMP0 (0.0) of the original system.
N3(s) = (0.11 X 0.4623) + { (0.03 X 0.4623) + (0.11 X 5.401)}s + 0.0 X 1s2
= 0.0514 + 0.612s
The transfer function of the third order reduced model is
The step response of proposed method is closely following the original system as shown in the Fig.4. The step
responses of the proposed method and other methods along with original are compared in Fig.5 and their initial
responses in Fig.6. Output of step responses at 3 seconds is listed Table VI. The step response by proposed method
is very closely following the original response when compared with other methods.
Step Response
0.14
Original
0.12 Proposed
0.1
0.08
Amplitude
0.06
0.04
0.02
0
0 5 10 15 20 25
Time (sec)
Fig.4: Comparison of step responses of G2(s) and R3(s)
31
Step Response
0.14
0.12
0.1
Original
Proposed
0.08 Kw alji
Liu & Shih
Amplitude
0.06 Pal
Sinha & Pali
Marshall
0.04
0.02
-0.02
0 20 40 60 80 100 120
Time (sec)
Fig.5: Comparison of step responses of G2(s) with ROMs
Step Response
0.14
0.12
0.1
Original
Proposed
0.08 Kw alji
Liu & Shih
Amplitude
0.06 Pal
Sinha & Pali
Marshall
0.04
0.02
-0.02
0 1 2 3 4 5 6 7 8 9 10
Time (sec)
Fig.6: Comparison of initial step responses of G2(s) with ROMs
32
Table VI: Comparison of outputs of step responses of various ROMs at 3 seconds

Method Transfer function Output
Original System G2(s) 0.121
Proposed method 0.121
Kawaji et al[15] 0.121
Liu and Shih [15] 0.121
Pal[6] 0.116
Sinha & Pal[6] 0.122
Marshall[6] 0.111
Conclusions and Future Research: In this paper, an effective procedure to determine the reduced order
model of higher order linear time invariant dynamic systems is presented.
Numerator and denominator polynomials of reduced order model are obtained by redefining the time moments
of the original high order system. The stability of the original system is preserved in the reduced order model as the
poles are taken from the original system. The method produces a good approximation when compared with other
methods. The method is applied for real and complex poles and the work is in progress to make it generalize for
discrete and interval systems.
References:
[1] Sinha, N.K. and Pille,W., “A new method for order reduction of dynamic systems”, International
Journal of Control, Vo1.14, No.l, pp.111-118, 1971.
[2] Sinha, N.K. and Berzani, G. T., “Optimum approximation of high-order systems by low order
models”, International Journal of Control, Vol.14, No.5, pp.951-959, 1971.
[3] Davison, E. J., “A method for simplifying linear dynamic: systems”, IEEE Trans. Automat. Control,
vol. AC-11, no. 1, pp.93-101, 1966.
[4] Marshall, S. A., “An approximate method for reducing the order of a linear system”, International
Journal of Control, vol. 10, pp.642-643, 1966.
[5] Mitra, D., “The reduction of complexity of linear, time-invariant systems”, Proc. 4th IFAC, Technical
series 67, (Warsaw), pp.19-33, 1969.
[6] J.Pal, A.K.Sinha and N.K.Sinha, “Reduced order modeling using pole clustering and time moments
matching”, Journal of the Institution of engineers (India), Pt.EL, Vol pp.1-6,1995.
[7] C.B.Vishwakarma, R. Prasad, “Clustering methods for reducing order of linear systems using Padé
Approximation”, IETE Journal of Research, Vol.54, Issue 5, pp.326-330, 2008.
[8] C.B.Vishwakarma, R. Prasad, “MIMO system reduction using modified pole clustering and Genetic
Algorithm”, personal correspondence.
[9] S.Mukherjee, “Order reduction of linear systems using eigen spectrum analysis”, Journal of electrical
33
engineering IE(I),Vol 77, pp 76-79,1996.

[10] G.Parmar, S.Mukherjee, R.Prasad, “System reduction using factor division algorithm and eigen
spectrum analysis”, Applied Mathematical Modelling, pp.2542-2552, Science direct, 2007.
[11] G.Pamar, S.Mukherjee, “Reduced order modeling of linear dynamic systems using Particle Swarm
optimized eigen spectrum analysis”, International journal of Computational and Mathematical
Sciences, pp.45-52, 2007.
[12] Pal.J., “Stable reduced order Pade approximants using the Routh Hurwitz array,” Electronics Letters,
vol. 15, pp. 225-226, 1979.
[13] S. Mukherjee, Satakshi and R.C.Mittal, “Model order reduction using response- matching technique”,
Journal of Franklin Inst., Vol 342, pp 503-519, 2005.
[14] Lucas, ‘I’. N., “Model reduction by condensed continued fraction method,” Electronics Letters, vol.
21, no.16, pp. 680-681, 1985.
[15] T.C.Chen, C.Y.Chang, and K.W.Han, “Model reduction using the stability equation method and
continued fraction method”, International Journal of Control, Vol 32,No 1,pp.81-94,1980.
[16] A.K. Mittal, R. Prasad, S.P. Sharma, “Reduction of linear dynamic systems using an error
minimization technique”, Journal of IE(I), J.EL.84,pp.201-206, (March) 2004.
[17] G. Saraswathi, K.A. Gopala Rao and J. Amarnath, “A Mixed method for order reduction of interval
systems having complex eigenvalues”, International Journal of Engineering and Technology, Vol.2,
No.4, pp.201-206, 2008.
[18] G.Saraswathi, “Some aspects of order reduction in large scale and uncertain systems”, Ph.D. Thesis.
34
A new approach to Overflow detection in moduli set {2n-1, 2n, 2n+1}

Mehrin Rouhifar1, Mehdi Hosseinzadeh2, Mohammad Teshnehlab3
1
Dept. of Computer Engineering, Islamic Azad University Tabriz branch, Tabriz, Iran
2
Islamic Azad University, Science and Research branch, Tehran, Iran
3
Dep. of Computer Engineering Khajehnasir University, Tehran, Iran
[email protected], [email protected], [email protected]
Abstract
Residue Number System (RNS) is a non weighted number system, which supports the fast and parallel
computations, limited carry propagation and secure communication. RNS is used in many applications like Digital
Signal Processing (DSP), cryptography and image processing. Detecting overflow in RNS systems, similar to the all
numerical systems is very important, because if overflow is not detected properly, an incorrect answer may be
considered as a correct answer. The previously proposed algorithms for overflow detection in signed RNS need
transforming numbers from residue system to a weighted system in order to sign determination of operands and then
carry out a conventional comparison that, mentioned works can be performed using residue comparison. These
methods are suitable for odd dynamic range. We propose a new overflow detection approach for even dynamic
range {2n-1, 2n, 2n+1} which can be implemented by fewer components of circuits. Furthermore, delay in this circuit
is very low. Therefore, proposed method provides high speed, because unlike previously proposed methods no need
to reverse convert or number comparison in RNS.
Keywords: Residue number system, overflow detection, moduli set {2n-1, 2n, 2n+1}, sign detection
35
1. Introduction
Residue number system (RNS) is an unconventional and non weighted numeric system. For such system,
parallel processing and computations are performed upon residues by division the number into several special
moduli [1]. These residue numbers are smaller than the original number in the conventional system. So,
computations can be done with more speed and low power. Since the arithmetic operations in each moduli are
independent of the others, there is no carry propagation among them and so RNS lead to carry-free addition,
multiplication and borrow-free subtraction [2].
A residue number system is defined in terms of a relatively-prime moduli set {P1 , P2 ,..., Pn } that
is GCD( Pi , P j ) = 1 for i ≠ j and i,j = 1,2,…,n. A weighted number X can be represented as X = ( x1 , x 2 ,..., x n ),
where x i = X mod Pi , 0 ≤ x i < Pi [3]. Dynamic range M of the system is given as a product of the moduli Pi .
Hence a representation is unique for any integer X in the range [0, M - 1], where
n
M= ∏ Pi (1)
i =1
The representation range in the signed RNS divides to two fully equal intervals. The first half defines the range of
positive numbers or positive half and the second half defines the negative numbers.
To convert a residue number ( x1 , x 2 ,..., x n ) into its binary representation X, the Chinese Reminder Theory
(CRT) is widely used. In CRT, the binary X is computed by:
n
X = ∑ (x N )
i =1
i i Pi ×Mi (2)
M
where M i = M / Pi and N i = M i−1 is the multiplicative inverse Mi modulo Pi .

Pi
Due to its special features, the residue number system has many applications in arithmetic functions such as
Digital Signal Processing (DSP) [4], Digital Filtering, Coding [5], RSA ciphering system [6], digital
communications [7], Ad-hoc network, storing and retrieving information [8], Error detection and correction and
fault tolerant systems [9]. This system is generally used in those areas where addition, subtraction and multiplication
operations of numbers are being reported.
In this paper, we propose a new algorithm to detect overflow in moduli set {2n-1, 2n, 2n+1}. This moduli set is
one of the most popular three-module set, because a simple conversion from a positional binary number system as
well as an efficient implementation of some arithmetic operation. The set can also be extended to improve the RNS
dynamic range.
Section 2 describes the overflow definition and different approaches of overflow detection in RNS. In section 3
after describing the sign detection method, will be expressed a new algorithm for detect overflow in moduli set {2n-
1, 2n, 2n+1} and its hardware circuit will implement. In section 4 the proposed design is compared with RNS to
binary converters and residue comparators which can be used for sign detection of numbers and final comparison in
order to overflow detection in signed RNS. Finally, conclusion of paper is explained in Section 5.
2. Overflow Detection
Overflow detection, sign detection, number comparison and division in RNS are very difficult and time
consuming [10]. An overflow is said to have occurred as a result of arithmetic operations if a positive result falls in
the negative half and inverse, or if the result of a calculation exceeds M [3].
Assume a residue system having moduli set {3,4,5} . Therefore M = 60 ; the range of positive numbers is
[0 − 29] , and the range of negative numbers is [30 − 59] , representing -30 to -1. An example of overflow of the first
category is (20)10 + (13)10 = (33)10 which in residue addition has represented as (2,0,0) + (1,1,3) = (0,1,3) . In this
case, overflow has occurred because (33)10 is in the negative half and denotes -27 in this residue system.
Consider the whole dynamic range, [0, M), of positive numbers from 0 to (M - 1). Let all Pi ’s in the moduli set
{P1 , P2 ,..., Pn } be odd numbers, consequently the range M would be an odd number, and two integers X , Y ∈ [0, M )
36
for the RNS representation are X = ( x1 , x 2 ,..., x n ) and Y = ( y1 , y 2 ,..., y n ) , respectively. Suppose
Z = X + Y = ( z1 , z 2 ,..., z n ) , so existent methods for detect overflow are outlined below:
2.1 Parity Checking Technique

Let parity indicate whether an integer number is even or odd. We say two numbers are with the same parity if
they are both even or both even. Otherwise the two numbers are said to be of different parities. Parity checking
technique is used to compare numbers and detect overflow in the addition of two numbers. For the parity checking
technique, a redundant modulus 2 is required. The parity of a number is equal to 0 if it is even or is equal to 1 if is an
odd number. Hence we have the following theorems [11, 12]:
Theorem 1: let X and Y have the same parity and Z = X + Y . Therefore, the result Z must be an even number.
Otherwise we can conclude that an overflow has occurred.
Theorem 2: let X and Y have different parities and Z = X + Y . Therefore, result Z must be an odd number.
Otherwise we can conclude that an overflow has occurred.
According to the parity checking technique, to detect overflow in unsigned RNS is required a comparison
operation between parities of numbers. Therefore in such ROM-based algorithms, we must convert numbers from
residue system to binary system to detect overflow which is a time consuming process [13, 14].
2.2 Core Function Theory

In [15] has defined a function called the core function and included its properties as follows:
Let {P1 , P2 ,..., Pn } be the relatively prime moduli of a residue number system with product M. For fixed integers
w1 , w2 ,..., wn , the core R N of an integer is defined as follows:
n
N
RN = ∑ w  P 
i =1
i
i
(3)
Where  X  denotes the largest integer not greater than X. The coefficients wi ’s are fixed for the moduli set and do
not depend on the integer N.
Theorem 3: let the moduli Pi and the core R M be odd. Assume ( x1 , x 2 ,..., x n ) and ( y1 , y 2 ,..., y n ) be the
residue representations of integers X , Y ∈ [0, M ) . Then X + Y causes an overflow if
i) ( x1 + y1 ,..., xn + y n ) is odd, and X and Y have the same parity; or
ii) ( x1 + y1 ,..., xn + y n ) is even, and X and Y have different parities.
Theorem 4: For signed RNS, if the moduli Pi and the core R M are odd, and ( x1 , x 2 ,..., x n ) is the residue
representation of a nonzero integer X ∈ [0, M ) , then X is positive if and only if (| 2 x1 | m1 ,..., | 2 x n | mn ) is even [14,
16].
According to the theory of core function, if the core function of an RNS number is known, it is easy to detect
overflows and the signs of the numbers. However, it is very difficult to find the core function in RNS.
2.3 Sign Checking Method

∏
n
Definition1: given Pi ’s in the moduli set all odd, and the dynamic range M = P , the range of a positive
i =1 i
number X is defined as 0 ≤ X ≤ M / 2 , and the range of a negative number Y is defined as M / 2 < Y < M . For
any positive number X ≠ 0 , the additive inverse of X is represented by M - X.
The following definition is to define overflow in signed RNS addition.
Definition 2: given Pi ’s in the moduli set all odd, and two numbers in RNS such as X = ( x1 , x 2 ,..., x n )
and Y = ( y1 , y 2 ,..., y n ) , overflow exists if X + Y > ( M − 1) / 2 .
Note that the following cases need to be considered.
1) X and Y are with the same sign. The absolute value of the sum should be no greater than M / 2 .
2) X and Y have different signs. No overflow will occur [13, 16].
37
The overflow detection theory in definition 2 applies to the addition of only two numbers. Therefore, according to
the overflow definition in signed residue system, a comparison operation is required. Since the number comparison
in RNS is very difficult, so it can not to be used in many applications.
3. Proposed Method
In this paper, is presented a new approach to detect overflow in signed RNS based on sign of residue numbers.
This section is split into two parts. First, to determining the sign of numbers in RNS given by {2n-1, 2n, 2n+1}, we
use a fast algorithm that has been presented in [17]. Second, we propose a new algorithm to detect overflow in even
dynamic range and implement its circuit by a limited number of components.
3.1 Fast Sign Detection

The proposed sign detection algorithm for RNS in [17] is based on the New CRT II [18]. The main advantage
of the used sign detection function in this paper is limitation of the operand width to n bit.
Since the dynamic range of a residue system by moduli set {2n-1, 2n, 2n+1} is an even number as M = 2 3n − 2 n
and splits the range M into the almost symmetrical intervals, so the sign detection function is defined as
sgn( x1 , x 2 , x 3 ) = [| t ′ | 2 n ≥ 2 n −1 ] (4)
The values X ∈ [0,2 3n −1 − 2 n −1 ) represent positive numbers. Also the negative numbers are represented by
X ∈ [2 3n −1 − 2 n −1 ,2 3n − 2 n ) . Thus, sign function for X ≥ 2 3n −1 − 2 n −1 should be equal to 1.
The sign detection function is determined by the (n − 1) th bit of t ′ . The value of t ′ is given by t ′ = x 3 − x 2 + Y
as a sum of x 3 , − x 2 and Y . Also the value of Y is given by Y =| 2 n −1 ( x1 − x 3 ) | 2 n −1 . In order to implementation
the sign detection unit, the final form of t ′ can be rewritten as
 x* 
t ′ = x2 + | 2 n −1 x1 | 2n −1 +2 n −1 ( x3,0 + x3, n ) +  3  + x3,0 + W (5)
 2 
where x 2 is two’s complement of x 2 . The value of | 2 n −1 x1 | 2 n −1 is computed as the (n -1)-bit left cyclic shift of
 
x1 . Let x 3* =| x 3 | 2 n = x 3, n −1 ...x 3,0 then x 3* / 2 x 3* 2 = x 3,n −1 ...x 3,1 , because division into 2 be implemented by 1 bit
right shift. W is the output signal of prefix carry generation unit CG2 as W = G + P which G and P are the carry
generation and propagation functions.
x3 x1 x3 x2 x1
CG2 Multi-operand adder
C S
CG1
W
Post-processing
Sign
Figure1: Sign detection unit [17]
38
Eq. (5) is implemented as shown in Figure1. The circuit comprises four main blocks: the multioperand adder,
two carry generation units CG1 and CG2 which these are a part of a parallel prefix adder structure [19] and the final
post-processing unit to compute bit t n′ −1 .
The multioperand adder is used to compute the value of t ′ − W . The value is represented as two vectors, S and
C that are sum and carry of x1 + x 2 + x 3 addition respectively. The protected vectors are connected to the inputs of
the CG1 unit. The goal of the CG1 and post-processing units is to determine the (n − 1) th bit of t ′ = S + C + W . The
detailed description is presented in [17].
The area and delay of the circuits are estimated using the standard unit-gate model used in [19]. For each two-
input monotonic gate (e.g., AND, OR, NAND, NOR) area A = 1 and delay T = 1. So forth each two-input gate of
XOR/XNOR has A = 2 and T = 2.
The delay of circuit in Figure1 is determined by a path consisting multioperand adder and CG1 and post-
processing units. The propagation of W can be ignored. So, the area and delay of the used sign detection circuit are
ASDU = 19n − 4
(6)
T SDU = 2 log 2 n + 10
3.2 Overflow detection for {2n-1, 2n, 2n+1}
To detect overflow in moduli set {2n-1, 2n, 2n+1}, we use the sign of numbers. Overflow occurs for the signed
RNS, whenever the sign of the sum is different from the operands. So, overflow detection accomplish by the
following steps:
(1) Detect the sign of X and Y, and calculate Z = X + Y M .
(2) Detect the sign of Z.
(3) Determine overflow with the signs of X, Y, and Z.
In this case, if we add two numbers with same sign X and Y, the result Z must have alike sign with operands.
Otherwise, overflow occurs. Also, we know if X and Y have different signs, no overflow will occur. Thus, we can
express all the above issues as Eq. (7).
Assume: Moduli set {2n - 1, 2n, 2n + 1}

M = (2n - 1). 2n. (2n + 1)
39
0 ≤ X ≤ M −1
0 ≤ Y ≤ M −1
X RNS
→( x1, x 2 , x 3 )
Y RNS
 →( y1, y 2 , y3 )
~
sgn( x1, x 2 , x 3 ) = sgn( X) = [| t′ |2 n ≥ 2n −1 ]
~
sgn( y1, y 2 , y3 ) = sgn( Y) = [| t′ |2 n ≥ 2n −1 ]
Z= X+Y
0 ≤ Z ≤ M −1
Z RNS
→( z1, z 2 , z3 )
zi = ( x i + yi ) mod mi , i = 1,2,3
~
sgn( z1, z 2 , z3 ) = sgn( Z) = [| t′ |2 n ≥ 2n −1 ]
~ ~ ~ ~
If ((sgn(X ) ⊕ sgn( Y ) == 0) & &(sgn(X ) & sgn( Y ) == 0))
{
~
sgn( Z) == 0
~
if (sgn( Z) == 1)
cout <<" overflow"
}
~ ~ ~ ~
If ((sgn(X ) ⊕ sgn( Y ) == 0) & &(sgn(X ) & sgn( Y ) == 1))
{
~
sgn( Z) == 1
~
if (sgn( Z) == 0)
cout <<" overflow"
}
~ ~ (7)
If (sgn( X ) ⊕ sgn( Y ) == 1)
cout <<" no overflow"
As we mentioned, overflow can be occurred in the process of addition of X and Y provided that, the operands have
the same signs. Therefore, by XOR-ing the sign of Z and the result of AND between the signs of operands such as X
and Y, we can detect overflow in dynamic range M (Eq.(8)).
~ ~
if (sgn( X ) ⊗ sgn(Y ) == 1)
~ ~ ~ (8)
overflow = sgn(Z ) ⊕ (sgn( X ) & sgn(Y ))
In the all above equations, the notations ⊗, ⊕ and & denote the exclusive-nor, exclusive-or and also AND
logical operation respectively. With regard to the Eq.(8), first we must obtain the sign of operands and result Z.
Then, based on them and using the proposed circuit, determine whether overflow is occurred or no. The
implementation of overflow detection circuit is shown in Figure2.
40
~ ~
sgn(Y ) sgn( X )
~
sgn(Z )
~ ~
sgn(Y ) sgn( X ) 0
1 0
Multiplexer
Overflow
Figure 2: Overflow detection circuit
The overflow detection unit consist of one AND gate, two gates of XOR and XNOR and also one Multiplexer.
The XNOR gate is as selecting line of Multiplexer and its goal is to compare the sign of operands together. If the
result of XNOR gate be zero namely operands of X and Y have different signs. So, zero number directly comes into
output signal of overflow. When, overflow signal value is equal to zero, indicates no overflow is occurred. Whereas,
if value of selecting line be one, is required the occurrence probability of overflow be checked. This work be
accomplished via AND/XOR gates and its result is characterized by overflow signal. Therefore, area and time (AT)
parameters of overflow detection circuit are
AODU = 5 + A2:1MUX = 8
(9)
TODU = 3 + T2:1MUX = 5
In order to estimate the total delay to detect overflow in the addition of two numbers such as X and Y is
necessary first, the sign of operand X be is detected and be maintained into 1 bit cell of ROM and afterward, the sign
of Y be detected. Next, simultaneous with sign determination of sum, the sign of operands becomes AND. So, total
delay reduce amount of one unit-gate. Consequently, total area and delay to detect overflow in signed RNS with
moduli set {2n-1, 2n, 2n+1} are
Atot = AODU + ASDU + AROM = 19n + 4 + AROM
(10)
Ttot = TODU + 3T SDU + T ROM = 6 log 2 n + 34 + T ROM
4. Comparison
The overflow detection methods for signed RNS detailed in [13, 16] consist of sign detection of operands and
comparison of sum with (M - 1) /2. These operations be generally performed to reverse convert to a weighted
representation or using the residue comparison. Since, proposed design does not require them, especially for large n,
we compare it with reverse converters and comparators. Also, it is possible to compare balanced moduli sets since,
generally all n-bit or n-1 bit or n+1 bit operations may need similar hardware and computation time with other of
complexity increasing from moduli values 2n, 2n - 1, 2n + 1, 2n - 3 to 2n + 3. For the sake of fair comparison, we
present the area and delay in terms of n using unit-gate model in RNS.
According to Table 1, [20] is based on ROM and in comparing to other methods, has the more area. The
converters for the moduli set {2n-3, 2n-1, 2n+1, 2n+3} have generally more conversion time and higher hardware
requirements than the converters for the moduli set {2n-1, 2n, 2n+1}.
The most efficient overflow detection circuit based on reverse converters can be built on the base on converter I
from [21]. Converter I and also converters II, III from [21] have delay of Ο (n) while, delay of proposed method is Ο
(log2 n). Therefore, conclude that our method has higher speed.
Also in [2, 22] to determination sign of residue numbers, should compare them with a suitable number, usually
is equal to 1/2 of RNS range while, our proposed method can solve it by using a fast sign detection algorithm.
41
Table 1: Comparison Area and Delay of proposed method with other methods using unit-gate model
Design Area Delay
[20] – CRT- high speed 574n + 262 + (12n + 8)2nAROM 48n + 84 + 4τROM
[20] - CRT- cost effective 382n + 166 + (12n + 8)2nAROM 192n + 168 + 4τROM
[21] - CI 56n + 22 + AROM 48n + 12 + τROM
[21] - CII 96n + 36 + AROM 12n + 12 + τROM
[21] - CIII 80n + 18 + AROM 12n + 12 + τROM
[22] (192 + 2logn2) n + 32 + AROM 24n + 3log2 n + 36 + τROM
[2] 230n + 372 + AROM 12n +3log2 n + 108 + τROM
Proposed method 19n + 4 + AROM 6 log2 n + 34 + τROM
The proposed method need only 1 bit cell of ROM and it is cost effective, because all the previous algorithms
require the hardware larger than the proposed method. Moreover, in methods based on converters, there is a certain
asymmetry of the range, what sometimes may be undesirable. To prevent this disadvantage, we have to use full
reverse converters with complete prefix adders and a final comparator with a suitable number. Whereas, the
proposed algorithm is free from that problem.
5. Conclusion
Overflow detection is one of the difficult arithmetic operations in RNS. In this paper, is presented an efficient
method to detect overflow in signed residue number system given by {2n-1, 2n, 2n+1}. The used sign detection unit
is based on the New CRT II and in comparison with the sign detection units based on reverse converters is smaller
and has less delay. The methods which so far have been reported by researchers for detect overflow, need to fully
reverse convert and comparison operation. The proposed approach instead of comparison, use a very simple circuit
in order to detect overflow. Therefore, presented technique can be implemented by a limited number of hardware
components and is faster than the previous methods.
References
[1] Parhami, B., (2000), “Computer arithmetic: algorithms and hardware designs”, Oxford University Press, New
York.
[2] Gholami, E., Farshidi, R., Hosseinzadeh, M. and Navi, K., (2009), “High speed residue number system
comparison for the moduli set {2n-1, 2n, 2n+1}”, Journal of communication and computer, Vol. 6, No. 3, pp.
40-46.
[3] Debnath, R. C., Pucknell, D. A., (1978), “On Multiplicative Overflow detection in Residue Number System”,
Electronics Letters, Vol. 14, No. 5.
[4] Ramirez, J., Garcia, A., Parrilla, L., Fernandez, P. G. and Lloris, A., (1999) “A Novel RNS-based SIMD RISC
processor for digital signal processing”, Conference Record of the Thirty-Third Asilomar, pp. 1307-1311.
[5] Conway, M., Siy, P., (2004) “A new Mixed Radix Conversion Algorithm MRC-II”, Journal of Systems
Architecture, Vol. 53, pp. 577-586.
[6] Bajard, J. C., Imbert, L., (2004), “Brief concontributions: a full RNS implementation of RSA”, IEEE
Transactions on Computers, Vol.53, Iss. 6, pp. 769-774.
[7] Ramirez, J. and et al., (2002), “Fast RNS FPL-Based Communications Receiver Design and Implementation”,
Proc. 12th Int’l Conf. Field Programmable Logic, pp. 472-481.
42
[8] Premkumar, A. B., Ang, E. L. and Lai, M. K., (2006), “Improved Memoryless RNS Forward Converter Based on
the Periodicity of Residues”, IEEE Transactions on Circuits and Systems—II: Express Briefs, Vol. 53, No. 2,
pp. 133-137.
[9] Baris, R., Avtar, K. and Trehan, (1973), “Binary Logic for Residue Arithmetic Using Magnitude Index”, IEEE
Transactions on Computers, Vol. C-19, No. 8.
[10] Szabo, N. S., Tanaka, R. I., (1967), “Residue Arithmetic and Its Application to Computer Technology”, New
York: McGraw-Hill.
[11] Askarzadeh, M., Hosseinzadeh, M. and Navi, K., (2009), “A New approach to overflow detection in moduli set
{2n-3, 2n-1, 2n+1, 2n+3}”, Second International Conference on Computer and Electrical Engineering, pp. 439-
442.
[12] shang, M., JianHao, H., Lin, Z. and Xiang, L., (2008), “An efficient RNS parity checker for moduli set {2n-1,
2n+1, 22n+1} and its applications”, Springer Journal of Science in China Series F: Information Sciences, Vol.
51, No. 10, pp. 1563- 1571.
[13] Mi Lu, (2004), “Arithmetic and Logic in Computer Systems”, John Wiley & Sons, Texas A&M University.
[14] Omondi, A, Premkumar, B., (2007), “Residue Number Systems: Theory and Implementation”, Imperial
College Press.
[15] Miller, D. D., Polky, J. N. and King, J. R., (1983), “A Survey of Soviet developments in residue number theory
applied to digital filtering”, in Proc. 26th Midwest Symp. Circuits Syst.
[16] Lu, M., Chiang, J. S., (1992), “A novel division algorithm for the residue number system”, IEEE Transactions
on Computer, pp. 1026-1032.
[17] Tomczak, T., (2008), “Fast Sign Detection for RNS {2n-1, 2n, 2n+1}”, IEEE Transactions on Circuits and
Systems I: Regular Papers, Vol. 55, Iss. 6, pp. 1502-1511.
[18] Cao, B., Chang, C. H. and Srikanthan, T., (2003), “An Efficient Reverse Converter for the 4-Moduli Set {2n-1,
2n, 2n+1, 22n+1} based on the New Chinese Reminder Theorem”, IEEE Transactions on Circuits and Systems-
I: Fundamental Theory and Applications, Vol. 50, No. 10, pp. 1296-1303.
[19] Zimmerman, R., (1999), “Efficient VLSI implementation of modulo (2n±1) addition and multiplication”, in
Proc. 14th IEEE Symp. Comput. Arithm. , Adelaide, Australia, pp. 158-167.
[20] Ananda Mohan, P.V., (2008), “New reverse Converters for the moduli set {2n-3, 2n-1, 2n+1, 2n+3}”,
International journal of electronics and communications, pp. 643-658.
[21] Wang, Y., Song, X., Aboulhamid, M. and Shen, H., (2002), “Adder based residue to binary number converters
for {2n-1, 2n, 2n+1}”, IEEE Transaction Signal Process, pp. 1772-1779.
[22] Shao-qiang, BI., Warren, J. and Gross, (2005), “Efficient residue comparison algorithm for general moduli
sets”, IEEE International Circuits and Systems, pp. 1601-1604.
43
DEPTH
Data Emission by Parabolic Transaction Heights
Author:
SarathChand P.V. B.E(cse),M.Tech(cs),(PhD) Professor and Research Scholar
Indur Institute of Eng. & Technology,Siddipet, Medak Dist.A.P. India.
Email id [email protected]
Co-Authors:
Benarji T. M.Tech(cs),(Ph.D) Assoc Professor and Research Scholar,
Indur Institute of Eng. & Technology,Siddipet, Medak Dist.A.P. India.
Parish Venkata Kumar K. M.Tech(cse) Lecturer and Research Scholar,
V.R.Siddhartha Engineering College,Vijayawada,A.P.India.
Abstract
The Organizations have been monitoring for accebility of data from the ware house. As the Data ware housing
increases the Organizations has to maintain many barriers for data accuracy, transaction anonymity, fraud risk,
security difficulties, expectations and small number of applications. The Data Emission in a secured manner by free
from problem creators is very important. For this purpose the Data is transmitted in the form of sequential kit and
monitored by a REDCOP algorithm. This algorithm plays a vital role in increasing the performance of Data bases. It
is proven to be quite useful as a transaction, authorization and identification. This improves the real time interaction
between the real world and the existing Data bases. The REDCOP algorithm is designed in mining applications, and
to predict the classes with definite examples or any new type of instances in the data streams by some knowledge on
the existing class memberships or previous instances of the data streams..The algorithm is specially designed to
learn the predictions from the labeled examples in automated fashions. In this paper we propose a general frame
work for data emission for mining data streams using weighted predictions. The algorithm improves the efficiency
in learning the model of mining, accuracy in performing the classifications.
Keywords: weighted predicates, entries, fact tables, dimension, main heights, segmentations, partitioning tilt.
44
1. Introduction
The biggest responsibility of modern days in the system is to record every transaction that is going, on every day. In
this process the very important system is to capture day to day activities in the life cycle of an organization. The
algorithm which was proposed in this paper is designed for quick access and correct decision based on the data. The
data is protected from unauthorized access, model for manual system and recovering the data in access of failure. To
manage day to day activities in on-line system, plays a vital role. These systems help in recording the transactions. It
is impossible to imagine an organization without an online transaction system. The REDCOP algorithm is based on
this, online system with a parabolic access mechanism in logical unit of work. The basic intention of this algorithm
is to take the data base from one consistent state to another state. While moving from one state to another the
database may pass through multiple discrete steps. At the end, the database may back to the original state in case of
failure or to the next logical state in case of success.
2. Parabolic Mining
It is similar to Batch processing system; a set of application programs will be working on a set of input data to
produce the desired output. In this process there will be absolutely no human interaction. The salary slip generation
program may read the data from the database and generates the salary slips. The mails will be sent to employees
automatically, without any intervention of the user. In OLTP system, the user will be continuously interacting with
the system through a terminal regularily.The parabolic mining is like referential integrity and is implemented using
the relationships between the primary key and the foreign key within the data warehouse. Especially the mining
requires the value of every foreign key in the table should be matched with the value of primary key in another table.
The Depth first search and the Breadth first search is a sequential searches performed on the data warehouse. It
means one in a Y-axis direction and another in X-axis direction. The parabolic mining is basically concentrates on
the origin of the first data available and availability of the required table. From, the point the mining starts with a
slice of distance to retrieve the required data in a parabolic fashion. This system is most complicated among all the
transaction system. It is capable of handling unexpected inputs to the expected outputs. The transaction should be
completely succeeded or completely failed. The parabolic mining is a mechanism of searching the data with
sequential heights. The data entered in to the data ware house must be validated for its correctness and adherence to
the organization rules
3. Data Emission by Parabolic Heights

3.1 The Emission mechanism under goes three types of integrity checks
3.1.1 Domain integrity check which involves business domain specific rules. The data warehouse has to undergo
the specified rules of the primary key and the foreign key mentioned according to the business strategies.
3.1.2 Entity integrity check which is also implemented using the primary key constraints. Basically the entity
refers to the facts that a particular attribute is uniquely identified by the physical entity.
3.1.3 Referential integrity which is implemented using the relationship between the data with the data ware
house. It ensures the data consistency. The referential integrity requires that the value of every foreign key
should be matched with the value of the primary key in another table. It is similar to a parent child
relationship.
The above all relation are considered and visualized by the algorithm in a COP fashion. It is renamed for brighter
look and called it as REDCOP. The basic monitoring of the algorithm is in the form of parabolic steps and
visualizing the effects to the user. It monitors the central fact tables which are surrounded by many dimension tables.
The data mart is includes one or more fact tables which measures the organization business operations. The
algorithm summarized to provide the information about the history of the operation of the organization. It is
visualized with multipart index that contains the foreign keys, primary keys of related dimension tables, containing
the attributes of the fact records and entities. Generally the fact table should not contain the descriptive information
or other than the numerical measurement fields and the index fields that are related to the fact table corresponds to
the entities in the dimension tables. The emission of tables from undergoing all these strategies is very difficult, so to
monitor for the safely passage of the data is done in the form sequential height or samples by the algorithm.
45
3.2 The parabolic mining constitutes with the description of REDCOP.

The procedure of the REDCOP is
3.2.1 Parse the statements and identify the particular data.
3.2.2 If a data has a catalog entry first does the local work and return to the caller.
3.2.3 If a cached catalog then the data indicate that a remote place x stores the catalog entry then it is set to x,
presumed is set to true and a recursive remote procedure call is issued.
3.2.4 If the data is supposed to store the catalog entry and the assumption is wrong, then return to the caller.
3.2.5 If the data is not born then the recursive procedure call is issued.
The data which is used by the REDCOP has been divided in to two major classes, Global data and Local data.
The Global data is common to all the data requirements like Master file containing the catalog, which describes
the structure of the data. The local data is instead relevant only for the data stored. The data base has been
distributed in the form of Global data as well as Local data. The Local data is horizontally fragmented and the
Global data is vertically fragmented. Generally all the Local data at different places have the same structure
although they store different data. The data distribution has been designed to satisfy continuous availability and
autonym.
3.3 The Data emission is basically designed in three subsystems.

3.3.1 Data Emission (samples) –
It manages the local data and provides to the transaction from reading the data from the local databases by
the local workspace assigned to each transaction. These samples can be moved between the workstations
and can be modified and writing the data back again into the Local databases.
3.3.2 Parabolic Transaction –
It plans and control the execution of the transaction and each Data language command is considered as a
separate transaction. It is also responsible for any query transaction and access planning, concurrency
control and distributed query execution.
3.3.3 Transaction heights-
It interconnects with Data Emission and Parabolic Heights and provides a guarantee in retrieving the data,
atomicity of transaction which are up or down at a particular time, and a global check on synchronized
accessibility.
3.4. Implementation of REDCOP

Generally the method to find the data is performed by Breadth first search and Depth first search. The BDF performs
in horizontal axis whereas the DFS performs in vertical direction. To search in combination of vertical and
horizontal method is done by parabolic methods which are very difficult to implement. The basic method of
parabolic degree is done by REDCOP.
The prediction formula is assumed as
y=a+bx+cx2
To minimize the predictions as
12 12
L=∑ c2i = ∑ (yi – a - bixi)2
i=1 i=1
Taking the partial derivative with respect to a and setting equal to zero, then we get
©L/©a is described as
12 12 12
-2∑ yi+ ∑ 2a + ∑ 2 bixi = 0
i=1 i=1 i=1
To simplify the notation, the range values for summation is
46
a = ∑yi - ∑ bixi
12
Now taking the partial value of L with respect to b and substitute the value for a and setting equal to zero we obtain
©L/©a=2∑(yi – a - bixi)(- xi) = 0
Solving for the values b we finally have
b =∑(x1, yi) - ∑xi∑yi
12
∑(x12) - (∑(x1)) 2
12
The similar equation is solved for c then For the class value is
y=a+bx+cx2
General form of the values is
Input; ®
®={™1, ….. , ™ }//Parameters to be estimated.
Xobs={x1,......,xk}//Expected values.
Xmissed = { xk+1,…..,xn }// Missed values
Output;
® // Estimation for ®
The algorithm is executed in the form
i:= 0;
Obtain initial parameters for ® 2
Repeat
Estimate missing data Xmiss2 ;
i++;
Obtain next parameter estimate ® 2 to maximize likelihood;
Until estimate coverage;
The above algorithm can be illustrated with some of predicted values
Let the axis points of x and y are indicated in Table 1
Table 1: x and y co-ordinates

X 1 1.5 2 2.5 3 3.5 4
Y 1.1 1.3 1.5 2 2.7 3.4 4.1
The location of searching may be considered as an origin be (2.5, 0) and take height as 0.5 as a unit. The amount of
data changes from x to X by the equation is X=2x-5.Let the availability of data is predicted as
y= .Then the value of and y is calculated as from the Table 1 and mentioned in Table 2
47
Table 2: Values of x and y

x X y XY X2 X 2y X3 X4
1 -3 1.1 -3.3 9 9.9 -27 81
2 -2 1.3 -2.6 4 5.2 -8 16
2 -1 1.5 -1.6 1 1.6 -1 1
3 0 2 0 0 0 0 0
3 1 2.7 2.7 1 2.7 1 1
4 2 3.4 6.8 4 13.6 8 16
4 3 4.1 12.3 9 6.9 27 81
Ex 0 16 14.3 28 69.9 0 196
Ex is expected values
The normal equations are
7a+28c=16.2
28b=14.3
28a+196c=69.9
Let the simultaneous equations are
a=2.07, b=0.511, c=0.061
Then
y =2.07+0.511X+0.061
Replace by X with (2x-5) then
y = 2.07 + 0.511(2x-5) + 0.061(
After simplification the calculated value of parabolic equation to find the path of the data is
y =1.04-0.198x+0.244
The above parabolic equation is
the best emission technique for data in a calculated prediction method. It can view in the form of a graph.
48
4. Comparison with Ant-Miner Optimization

There is a similarity between the Ant-Miner Optimization and Parabolic Mining by using REDCOP. The Path
Finding is one of the tasks for the retrieval of data. Although there are many approaches to effectively solve the
problem of path finding and one of them is Ant Miner. The REDCOP is also similar to it, but it is dynamically
change during the data retrieval. The Parabolic calculates the different heights for transmitting the particular data
where as the Ant Miner follow the particular path which does not have any steps or heights to calculate the required
data. Some of the improvements are implemented which are based on the existing research to enhance the
classification predictive solved examples and simplicity of rules. The discretization method is adopted and
parameters in the algorithm are adjusted in step wise fashion like heights. With these improvements the performance
analysis of the algorithm is advanced and classification of predictive accuracy is also enhanced. The final statement
is the REDCOP is a self development data mining algorithm based on swarm intellectual. The results are proposed
in this paper has better performance in predicating the accuracy and simplified rules.
5. Conclusion and Future Work

The Data Emission can be beneficial for business, governments, society as well as for the individuals. One of the
best advantages of data emission is that the users will be able to access a large amount of information which can be
used to solve large number of problems and it also increases the profits of Data Mining techniques. The cost
computing will be reduced and the data from different locations can be retrieved with parabolic line sequence. The
major flaw with this algorithm is, it is two dimension techniques that it increases the risk of privacy invasion. Many
business organizations do not have sufficient security systems to protect the data from un authorized access. In
future the algorithm should be developed for multi dimensional technique because the data ware house that uses the
multi dimensional technique tends to operate quickly. The storing of data is also called as normalization which is to
be done in multi dimensional technique for implementation of the algorithm. So the future work is to develop in the
multi dimensional methods
References:
[1]. http//www.google.com for study materials.
[2]. Infosys foundation programs me powered by intellect driven by values.
[3]. Silberschatz and A. Tuzhilin, ... Knowledge and Data Engineering, IEEE Transactions on, On page(s): 911
- 923, Volume: 20 Issue: 7, July 2008 .
[4]. 7 Aug 2006 ... [CrossRef] [Buy Via Ask*IEEE]; J. M. Smith "Multibase-Integrating Heterogeneous
Distributed Database Systems", Proc. Nat. .
[5]. A Theory of Attribute Equivalence in Databases with. Application to Schema Integration. JAMES A.
LARSON, MEMBER, IEEE, SHAMKANT B. NAVATHE,
[6]. Mar 2006 ... Chapter 15 - Algorithms for Query Processing and Optimization. 15.1 Translating SQL
Queries into ... 19.6 Recovery in Multidatabase Systems
[7]. 23 Jan 2006 ... [Buy Via Ask*IEEE]; W. Siedlecki and J. Sklansky, "On automatic feature selection", Int. J.
Pattern Recognit. Artif. Intell., 196 , 2004.
[8]. C.J.C. Burges A tutorial on support vector machines for pattern recognition 2007.
[9]. Anderson.J.A.”A simple neural network generating for interactive memory Mathematical Bio-sciences.
[10]. Bezdek J.C.Keller “Fuzzy models and algorithms for pattern recognition and Image
processing” 2010.
[11]. Distribited databases by Stefano ceri and gluseppe pelagatti
[12]. 20 Jun 2005 ... J.C. Bezdek, S.K. Pal (Eds.), Fuzzy Models for Pattern Recognition:
[13].M.P.Oakes,”Ant-Colony Optimization for stylometry: The federalist paper.
International Conference on soft computing Nov 2004
49
DESIGN OF ADAPTIVE CONTROLLER FOR A ROBOT GRIPPER

USING SUPPORT VECTOR REGRESSION
K.R.Sudha1
D.V.Pushpalatha1
1
Department of Electrical Engineering, Andhra University, Visakhapatnam, India
[email protected]
Abstract
Robotic grippers are commonly required to grasp and manipulate loads under a wide range of operating
conditions, without the load slipping from the end-effector and avoiding damage to the load. The increasing demand
on robotic gripper performance leads to the use of advanced control strategies. In the present paper, a novel
approach for on-line adaptive tuning of Support Vector Regression (SVR) based controller for a two finger robot
gripper using Multi layer Perception (MLP) kernel is presented. The efficacy of the controller is tested on Robot
gripper and compared with unsymmetrical triangular input fuzzy logic controller. It is observed that the proposed
controller results to a better response than the unsymmetrical fuzzy sets.
Keywords: Support vector regression, triangular fuzzy sets, robot gripper
50
1. Introduction:
Recently, significant developments have been made in the design of practical robot hands that can perform
tasks required in various industrial fields. However, most industrial robots have been designed to perform only
specific movements based on information of the object to be manipulated (e.g., object mass and size). Therefore,
little attention has been given to grasping strategy for unexpected force, such as an inertial force that arises when a
grasped object is moved quickly. In operations in which the load force of the grasped object varies, one possible
grasping strategy to prevent the object from slipping is for the robot to grip the object with a larger-than-necessary
force. However, if a delicate or fragile object is to be manipulated, excessive grasping force may damage the object.
Support Vector machine (SVM) is a new machine learning method that is developed on the basis of the
statistical learning theory. Based on the principle of structural risk minimization, SVM can solve the problem of
over-fitting effectively. Machine Learning is considered as a subfield of Artificial Intelligence and it is concerned
with the development of techniques and methods which enable the computer to learn. In simple terms development
of algorithms which enable the machine to learn and perform tasks and activities. Machine learning overlaps with
statistics in many ways. Over the period of time many techniques and methodologies were developed for the design
of PSS using machine learning tasks.The foundations of Support Vector Machines (SVM) have been developed by
Vapnik [4][5][6]. The SVM can be applied to both classification and regression problems. The SVM for regression
is called Support Vector Regression (SVR) and applied in regression analysis.
In the present paper a novel approach for on-line adaptive tuning of Support Vector Regression (SVR)
based controller for a two finger robot gripper using Multi layer Perception (MLP) kernel is presented. The efficacy
of the controller is tested on Robot gripper and compared with unsymmetrical triangular input fuzzy logic controller.
2. Support Vector Machine:
Support Vector Machines (SVM) has its solid mathematical foundation based on statistical learning theory
(Vapnik-Chervonenkis (VC) theory) . A major goal of VC theory is to characterize the generalization
error instead of the error on specific data sets, which enable SVM to generalize well to unseen data. Unlike
conventional regression techniques, the SVR attempts to minimize the upper bound on the generalization error based
on the principle of structural risk minimization rather than minimizing the training error. This approach is expected
to perform better than the empirical risk minimization principle employed in the conventional approaches.
Moreover, the SVR is a convex optimization, which ensures that the local minimization is the unique minimization.
SVM has three key features:
1) Better generalization capability;

2) Global optimal solution using optimization theory;
3) Kernel functions for nonlinearity.
There are many linear classifiers (hyper planes) that separate the data. However only one of these achieve maximum
separation.
Advantages and Limitations of SVR: Support vector regression (SVR) has many attractive features:
1. It has the ability to model non-linear relationships

2. It has the ability to select only the necessary data points (support vector) to solve the regression function ,
which results in a sparse solution;
3. The regression function is related to a quadratic problem (QP) which has a unique global solution in it that
has good generality capability and better classification accuracy.
4. VC theory characterizes properties the generalization error which enable SVR to generalize well to unseen
data;
5. The SVR technique can be used when there are few samples than variables, which is also called
small n large p problems .
3. Case Study: Robot gripper and control system

Robot gripper control in this paper is the control of the force exerted over the gripping area[1][2][3]. The
robot gripper used is shown in Fig.1. Two fingers were moved by DC servo motors through a ball screw, and each
finger could be shifted in one direction. Grasping forces were measured by attached strain gauges through a low pass
filter [cut off frequency: 200 Hz] and an amplifier. Fig. 2 shows the control system for the robot gripper. A block
diagram of the control system is shown in Fig 2. . F(α) represents the grasping force to compensate for the inertial
force, which is calculated from the observed acceleration. The sum of the reference input Fd and disturbance F(α) is
51
applied to the controlled element after being multiplied by the safety factor N(α), which is changed by the
acceleration. Taking into account the influence of inertia, the desired force Fi(t) is defined as follows:
Fi (t ) = N(α, t ){Fd + F(α, t )}
Input u(t) can be expressed by

u(t ) = K p {Fi (t ) − F(t )}
where F(t)is output, or the measured grasping force, and Kp indicates the proportional gain.
Figure 1: Robot gripper that can emulate human grasping motion
A system representing the complete model for Robot gripper control is considered. Fuzzy PI controller is applied to
F̂ (α)
it. For convenience the additional disturbance Inertia force is made equal to zero. Fig. represents Block
diagram for the control of robot gripper using SVR controller.
Inertiaforce
F̂(α )
+
+ F̂
F̂d K 1K 2 1
N(α) Kp
+ + - (1 + τs )s s
Controller Kp
Ki
Figure2: Block diagram of robot gripper

4. Performance Analysis:
From the graphs fig 3 and Fig 4 it can be observed that the rise time and settling time for the proposed controller
are less compared to rise time and settling time for the conventional controller. That is proposed controller gives the fast
response than fuzzy controllers with unsymmetrical input fuzzy sets[7] have better performance than fuzzy controller with
unsymmetrical fuzzy sets and conventional controller
52
SVR controller
PID controller
Fuzzy unsymmetrical
Figure 3: Unit step response of robot gripper controller using symmetrical and unsymmetrical fuzzy controller and
conventional controller for N(α)=1
SVR controller
PID controller
Fuzzy unsymmetrical
Figure 4: Unit step response of robot gripper controller using symmetrical and unsymmetrical fuzzy controller and
conventional controller for N(α)=1.2
Conclusions and Future Research:

In this paper a controller is designed using support vector Regression(SVR) technique to control the robotic
gripper. Obtained results are compared with the conventional controller. From the simulated results it can be concluded
that the performance of the proposed controller have better performance than a fuzzy controller with unsymmetrical
fuzzy sets and also that of the conventional controller.
References:
[1] Nobuaki Nakazawa, Il-hwan Kim, Hikaru Inooka, Ryojun Ikeura, "Force control of a robot gripper based on human
grasping schemes”, Control Engineering Practice, September 2001, pp 735-742.
[2] N.I.Glossas and N.A.Aspragthos , “Fuzzy Logic grasp control using tactile sensors”,,Mechatronics, Volume 11, Issue
7, October 2001, pp. 899-920.
[3] M.F.Barsky, D.K.Lmdner, R.O.Claus, “Robot Gripper Control System demonstrating PVDF piezoelectric sensors”,
Proceedings of IEEE International Ultrasonics Symposium, 1986, pp. 545-548.
[4] S. R. Gunn, “Support Vector Machines for Classification and Regression,” Technical Report, Image Speech and
Intelligent Systems Research Group, University of Southampton, 1997.
[5] V. Vapnik. The Nature of Statistical Learning Theory. Springer, N.Y., 1995. ISBN0-387-94559-8.
[6] V. Vapnik, S. Golowich, and A. Smola. “Support vector method for function approximation, regression estimation,
and signal processing” In M. Mozer, M. Jordan, and T. Petsche, editors, Advances in Neural Information
Processing Systems 9, pages281– 287, Cambridge, MA, 1997. MIT Press.
53
[7] D.V.Pushpalatha, K.R.Sudha and A.Staya Devi “Design of Adaptive Fuzzy Controller for a Robot gripper”
proceedings of IEEE Advances in Recent Technologies in Communication and Computing, 2009. ARTCom '09.
International Conference on 27-28 Oct. 2009 ,pp254 - 256
54
Effective String matching Model for Intrusion Detection System
Ruchika Rai#1, Abhishek sharma*2

#
Information Technology
Mahakal Institute of Technology, Ujjain, India
1
[email protected]
*
Information Technology
Mahakal Institute of Technology, Ujjain, India
2
[email protected]
Abstract
Primary aspects of network intrusion detection systems include the collection, management, and analysis of
intrusion data. Intrusion detection systems in particular now days have increasingly valuable role to play as network
grows and more information becomes available and administrators need better ways to monitor their systems. Most
current intrusion detection systems lack the means to accurately monitor and report on wireless segment within the
corporate network. In this paper we are going to present our survey on the new effective approaches of data
collection and their management, and detection of intruders. For this purpose we have gone through a paper which
discusses the data collection architecture using small, low cost embedded Linux devices as mobile, highly
configurable, and collaborative sensors. Moreover, since at the heart of every modern intrusion detection system is a
string matching algorithm, we have surveyed an approach that relies on a special purpose architecture that executes
novel string matching algorithms specially optimized for rule based intrusion detection system. We have surveyed
another approach regarding effective intrusion detection which is NeGPAIM model that will allow for the accurate
detection of attacks in proactive fashion. Finally, this works have proposed a new modified architecture for overall
intrusion detection system for wireless network.
Keywords: SMASH, Data Fusion, NIDS, WGPAIM
55
International Journal of Computational Intelligence and Information Security, March 2011 Vol. 2, No. 3
1. Introduction
Computer systems now operate in an environment of near ubiquitous connectivity, whether tethered to a Ethernet
cable or connected via wireless technology [2]. While the availability of always on communication has created
countless new opportunities for web based businesses, information sharing, and coordination, it has also created new
opportunities for those that seek to illegally disrupt, subvert, or attack these activities [2]. Everyday the more critical
data become more accessible over the network, and any publicly accessible system on the Internet is subjected to
more than one break in attempt per day [2]. So, there is widespread interest in combating these attacks at every level,
from end hosts and network taps to edge and core routers [2]. Given the importance of protecting information and
services, there is a great deal of work from the security community aimed at detecting and thwarting attacks in the
network [2]. Intrusion Detection Systems (IDS) and Intrusion Prevention Systems (IPS) have emerged as some of
the most promising ways of providing protection on the network. Network based intrusion detection systems can be
categorized as either misuse based or anomaly based. Both systems require sensors that perform real time
monitoring of network packets, either by comparing network traffic against a signature database or by finding out-
of-the-ordinary behavior, and triggering intrusion alarms [2]. To detect intruder the first step is to effectively collect
and manage data from outside or inside the network segment. Current methods are plagued by “false positive” and
“false negative” determinations about intrusions [1]. This paper talks about an implementation of an innovative
approach for network intrusion detection sensor platforms using gum stick-sized devices which contain an
embedded Linux operating system and both wired and wireless network connections [1]. The experiment performed
in the paper we have surveyed has demonstrated the proof of concept by successfully installing a single sensor
called Gumstix [4] into a network for intrusion data collection and by developing a software module for handling the
wireless data transfer. To define suspicious activities, most modern network intrusion detection/prevention systems
rely on a set of rules which are applied to matching packets. At minimum a rule consists of a type of packet to
search, a string of content to match, a location where that string is to be searched for, and an associated action to
take if all the conditions of the rule are met [2]. The problem is that for the detection to be accurate, we need to be
able to search every byte of every packet for a potential match from a large set of strings which requires significant
processing resources both in terms of the amount of time to process a packet, and the amount of memory needed. A
string matching engine must have bounded performance in the worst case so that a performance based attack cannot
be mounted against it [5]. A successful design must have the ability to be updated quickly and automatically all the
while maintaining continuous operation. In order to address these concerns, we have surveyed a paper which
describes an approach that relies on a simple yet powerful special purpose architecture for string matching to
achieve both high performance and high efficiency. The result of the efforts is a device that maintains tight worst
case bounds on performance, can be updated with new rules without interrupting operation, has configurations
generated in seconds instead of hours, and is ten times more efficient that the existing best known solutions [2]. We
have surveyed another paper which is an extension of to the NeGPAIM model that can accurately detect attacks
originating on wireless network segments. This will be done by the use of fuzzy logic and neural networks utilized
in the detection of intrusion attacks. The model is known as NeGPAIM-W2 and is based on the assumption that each
user has and leaves a unique footprint on a network when using it. This model is able to proactively detect intrusion
attacks in both wired and wireless environments [3].This paper is organized as follows. Section 2 illustrates our
background study about the investigation of a new approach to data collection, management and analysis for
network intrusion detection system, an overview of architecture for string matching with high performance and
efficiency, and finally the overview of the model NeGPAIM-W2 to detect intrusion attacks proactively. The section
also illustrates the methods of testing and validating those ideas mentioned. Section 3 presents our observations
regarding those papers which include weaknesses and our new idea. Finally we conclude with section 4.
2. Background study
Here we are going to illustrate our observations on effective intrusion detection systems into three different
subsections which have been derived after careful study of the corresponding literatures [1, 2, 3].
56
2.1 Investigating new approaches to data Collection, Management and Analysis for
network intrusion detection
The basic concept that was used in this paper was called SMASH (A Security Monitoring System for Information
Assurance, Analysis, and Survivability of Network Hazards). SMASH is a concept which unites the technologies
and fields of Network Security, Wireless Networking and Statistical Analysis.
2.1.1 Need for SMASH
The most basic need for implementing SMASH was network security. And the focus of this security, which
includes intrusion detection, was to prevent unauthorized access to the information, which might cause great loss
and in some extreme case even render the systems unstable or unreliable.
2.1.2 Wireless Networking ideal for SMASH sensors
The basic requirements for implementing SMASH sensors should be low cost, no extreme bandwidth
requirements, flexible and scalable. These requirements can be easily fulfilled by a wireless network. The
fundamental information necessary for intrusion data are IP addresses, which can be strongly encrypted along with
all alert data. Therefore, the alert data will have a much smaller volume and the monitoring network need not be a
high bandwidth network. And an additional advantage would be that the sensors can be moved at will without
disruption of the operational network. So this last observation allows us to connect wireless-enabled sensors on an
as-needed basis simply by locating them within the physical distance required. All that is needed is an 802.11
wireless hub connected to the operational network. This means that security and monitoring operations can have
their own physical security over the sensors, and need not share wiring closet and rack space with operational
network elements.
The monitoring network depends on the geographic distances involved. If the monitoring network can be located
within a building or campus area, then 802.11 technologies may be all that is needed. If larger distances are involved
(e.g., multiple offices in different metropolitan areas, or across the world), then any other suitable cost-efficient
connectivity could be used to connect multiple monitoring sub-networks together – for example fractional T1, frame
relay, or satellite services – to connect multiple monitoring sub-networks together.
2.1.3 Collecting data using Gumstix
After setting up the network, we need a separate computer, called a sniffer, to sniff and collect the data, or in other
words monitor the traffic. The sniffer on sniffing an attack should inform, so that some sort of logging and/or
blocking of the attack can take place.
Communication among network sensors is essential to do the job completely. If one network sensor classifies an
attack from location X and blocks all traffic, then all the other sensors should block location X before an attack
occurs; thereby blocking the attacker before he or she gets any information about those subnets. Since it is essential
for this communication to occur, such decision making could be performed by a central management station, which
could then send out a message about an ongoing attack to all of its sensors. The sensors could then take any other
decision regarding the attack by configuring the rules.
In this paper, the Gumstix device was chosen as the network sensor primarily for its reliability. Gumstix devices
are Linux computers that fit into the palm of your hand! This way there is no problem regarding cost and size. The
Gumstix provides easy design flexibility and open source at nearly half the price of and a third the size of all other
offerings. Full size workstations which are required to process large amounts of data are very expensive.
Office space can be expensive and storage for full sized workstations, costly. Using an embedded system like
Gumstix is more cost efficient.
Because the Gumstix runs Linux, a great deal of open source software becomes available for use in the test
environment including web servers, SSH servers, Java Virtual Machines, and network monitoring software such as
tcpdump and the popular open-source NIDS application, Snort. For communicating with the sensors, a Java
57
application using socket programming was developed to control the Gumstix device. A simple server management
station application was written to allow many connections from different sensors, and set up to send messages to any
subset of them. Therefore, the Gumstix sniffer with Snort installed is connected via a wired connection to its
network, and is connected wirelessly to the management workstation
2.1.4 Managing data over wireless
In case the sensor goes under a denial of service (Dos) attack, it will have problems communicating with the
server. So for that it may have to communicate with a server on a separate network. But it becomes too complicated
to have a second network running in parallel. So it is better to use a wireless network, as it creates less complication.
The Gumstix sniffer with Snort installed is connected via a wired connection to its network, and is connected
wirelessly to the management workstation, or possibly a management cluster.
2.1.5 Analyzing data with Data Fusion and Data Mining Techniques
Data fusion is generally defined as the use of techniques that combine data from multiple sources and gather that
information in order to achieve inferences, which will be more efficient than if they were achieved by means of a
single source. Data mining is the principle of sorting through large amounts of data and picking out relevant
information . The combination of data fusion and data mining techniques has the greatest potential to solve a major
drawback of IDS: the unacceptable numbers of false positives and false negatives.
2.2 High throughput string matching architecture for intrusion detection and prevention
This sub section begins by briefly describing the requirements that have driven the design, the main ideas behind
the string matching technique, and the details of the architecture. The section ends up with the analysis of the design.
2.2.1 IDS requirements
The followings requirements were identified for Intrusion Detection/Prevention Systems [2]. Worst case
performance: IDS needs string matching algorithms that can keep up with the speed of checking incoming packets in
real time which will have stringent worst case performance. on-interrupting rule update: The architecture should also
be able to update the rules quickly and provide uninterrupted service during an update. High through per area: The
design that is small enough can fit completely on a chip which consumes fewer resources and can operate much
faster than one relies on off chip memory [2].
2.2.2 String matching engine
At a high level the set of string should be broken down into a set of small state machines where each state machine
recognizes a subset of the strings from the rule set. The architecture is built hierarchically around the way that the
sets of strings are broken down. It shows the highest level as a full device which holds the entire set of strings that
are to be searched and reads in a character from an incoming packet and computes the set of matches [2]. Each
device consists of a set of rule modules each of which holds a subset of the rule database. The rule modules can
interact each other. Each rule module is a large state machine which takes bytes as input and returns string match
result. When a packet comes in the system, it is broadcast to all of the rule modules for the checking purpose. The
broadcast has the limited overhead which increases the throughput [2]. When a match is found in one or more of the
rule modules, that match is reported to the IDS for appropriate action to take which gives the approach high
efficiency and throughput [2]. Each rule module consists of a set of tiles. Tiles work together and implement the
actual state machine that can recognize a string in the input which is different than a naïve mannered state machine.
The naïve machine may have 256 different possible transitions from each state which will make the storage of each
node in kilobyte range. So, there is tradeoff for this naïve state that either we can states off the chip or we can
compress the data. The first case loses the bounds on worst case performance. But the approach presented in the
paper [2] splits the state machines apart from into a set of new state machines each of which matches only some of
the bits of the input stream. So we can say that each new state is a filter and the given input string can pass the filter
only when it matches. All of the filters have to agree to declare a match. Each tile can be termed as a table consists
of a number of entries where each row in the able can be termed as a state. The tile has the ability to encode the state
58
transition and also has a partial match vector – a bit vector responsible for a match for every rule. When all of the
partial match vectors agree, we can do the and operation on them to find the full match vector which indicates that a
match for a particular rule has been found [2].The system works like this. Initially, all the tiles are set to state 0.
Then when transmission starts, each input byte is partitioned into groups of bits. Each group is then sent to the
corresponding tile [2]. There is an internal state in each tile which is used to point a line in the memory tile. Then the
possible state transitions take place and at the same time the match vector is read out. To get the new next state the
input bits are used as selection bits. Then the partial match vector is combined with others by passing through the
AND unit. Finally, to find out the matched strings all the full match vectors of all modules are put together [2].
2.2.3 Support for Non-interrupting Update
The old technique that uses FPGA reconfiguration has a major drawback is that during rule update (rule database
reconfiguration) it needs the system remain off which is simply unwanted to the users [2]. But in this approach,
automated systems are used in proper locations that can detect new attacks in real time which is supported by this
architecture by adding a temporary tile for the purpose of update. If we want to replace the contents of one rule
module, the rules are first updated and copied to the temporary rule module [2]. When the next new packet comes in,
the control bit for the module is set to override with the results from the replacement rule module [2]. Later without
any interruption of the services the main rule module can be written. After a complete update of the rule module, the
control bit is switched back and the replacement module is reset to the state machine for the next module in line [2].
According to the authors of the paper [2], the writing to the rule module needs an order of 1.6 microseconds and to
finish an update needs 108 microseconds to complete which is pretty much faster than other old techniques.
2.2.4 Analysis of the design
Here we are going to present an analysis of several important design options given by the authors in the paper [2].
Theoretical optimal partitioning

Here the authors have given a theoretical idea of dividing up the original state machine by partitioning the strings
into groups of different size e.g. 8, 16, 32, 64 or 128 strings per group [2]. For a set of strings S each with L
characters per string, the total number of bits the architecture requires is
Tn,g = n floor(S/g)2floor(log2(gL))(floor(log2(gL)))28/n +g)
Where n is number of state machine per rule module and g is the group size. From the formula, it is seen that the
smaller the group size g is the smaller Tn.g is [2].
Throughput analysis
This architecture of string matching supports incremental and no interrupting update. Furthermore the design can
achieve worst case throughput of over 10 Gbit/sec even if only 1 byte is read in each cycle which is better than
FPGA-based techniques [2].
2.3 Utilizing fuzzy logic and neural networks for intrusion detection
2.3.1 Problem with current Intrusion detection system
There are several commercial IDS in the market without intrusion detection capability. There are currently three
kinds of IDS in the market. HIDS (Host based IDS), NIDS (Network Based IDS) and Hybrid IDS. Both the HIDS
and NIDS need database of previous known attacks to detect most attacks. The problem with these two approached
is that there is little to no correlation between networks based and host-based intrusion events. This mainly because
intrusion information is stored in separate database.
There are two main methodologies of detection to which most ISDS subscribe:
1. Misuse Detection and
2. Anomaly Detection.
59
The problem with the Misuse Detection is that, database need to be updated and to combat the missed attack
database need to collect in a long period of time and analyze. A problem with Anomaly Detection is that a user over
time can train the system to accept anomalous behavior as normal, by slowly adding to the attack. Hence, with many
problems associated with modern IDS, a new model for IDS has been formulated known as Next Generation
Proactive Identification Model with ‘Wired and Wireless (NeGPAIM-W2) developed at NMMU.
2.3.2 The NEWGPAIM-W2 Model
It has nine main components, three of them are directly involved in the detection of intrusion attacks, namely the
fuzzy, neural and CAE engines detection engines and known as low-level and high level detection engines [3].
1. Fuzzy Engine: The fuzzy engine is responsible for implementation the Misuse Detection methodology. It
will compute a template firstly and the user action graph will be mapped against it to determine whether or
not an intruder has been or in performing an intrusion attack. It will give the percentage of potential attack
to CAE [3].
2. Neural Engine: The neural engine uses a user’s wireless and wired network usage patterns to determine
whether or not the user is acting abnormally on the system. The percentage of probability sent to CAE [3].
3. Central Analysis Engine: Since today’s trend is moving towards intrusion prevention and proactive
intrusion detection both of which attempt to limit or completely stop an attack dead in its track. CAE
analyze and interpret the resultant output values from the fuzzy and neural engines as well as managing the
other units of the model, it includes four critical operations [3].
2.3.3 Analysis
The three key elements of the NewPAIM-W 2 model has been fully implemented in a test bed in this paper. The
results obtained from the experiment performed shows that NewPAIM-W 2 is 98% accurate in detection of intrusion
attack with a false alarm rate of only 2%. Figure 1 depicts that Fuzzy Engine sending 5 or 8 or 70 percent probability
of attack to CAE and Neural Engine also sending 7 or 10 or 80 percent of probability of attack to CAE. CAE then
analyzes 6 or 9 or 75 percent, it is calculated by (Fuzzy + Neural)/2 [3].
In another paper [6] show that the experimental result in the neural approach was implemented through an initial
working prototype. Although the prototype was done on a small scale, favorable results were obtained. The network
was more than 97% accurate in detecting unusual activities, with less than a 5% false alarm rate.
Fuzzy Engine
5/8/70% risk Central Analysis

Engine
6/9/75% risk
Neural Engine 7/10/80%
Figure 1: Risk analysis
2.3.4 Method of Testing
Key elements of the NeGPAIM-W2 model have been implemented in a fully functional prototype named Sentinel
IDS. These elements are namely the reporting, Fuzzy, Neural and Central Analysis Engines. The reason these
elements were chosen is that they form the core backbone of detection and the feedback processes allowing for the
proactive detection of attacks. Responses, both passive and active, have been implemented as well as remote sensors
(smart agents). The Microsoft Windows environment was chosen as the test bed for the NeGPAIM-W2 Model. The
tools used were as follows: Airodump, Aireplay, Aircrack, Super-Scan and Brutus. Some of the tools utilized are
60
Linux-based, while others are Windows-based. As mentioned previously, the environment in which this experiment
occurs is a Microsoft Windows client/server environment, with two windows-based hosts that were known as Host1
and Host2 for the experiment. Host1 was the host installed with the Sentinel IDS wireless sensors and is also the
DHCP and FTP server. Host2 was the host housing the main Sentinel IDS application. AP1 was the wireless access
point with which Host1 and Host2 communicate. Intruder1 was the malicious intruder running a Linux-based
notebook, who wanted to steal information from Host1. Now that the background has been given, the next step is to
simulate a typical simple attack through an experiment.
3. Our observations
Here we are going present our observations we have found after doing the survey on making the IDS/IPS effective.
3.1 Complications over managing various networks
It becomes quite cumbersome and unwieldy to manage 2 or maybe more networks. The monitoring is done on one
network and the data is sent for analysis to the server through a separate network. The Gumstix sensors should be
managing all the networks.
3.2 String matching architecture
Even though the architecture has been developed focusing on improving string matching performance for rule
based intrusion detection, we can detach the bit-split finite state machine from string matching and can apply to
general search problems on general state machines. This may improve the performance of the search. We can also
improve the throughput by reading in more than one byte at a time. Currently there are only two next states for each
node in bit-split FSMs. We can extend it by reading in more than one byte at a time. But in this case we need to
multiply throughput with reasonable increase in storage size.
3.3 Intrusion detection with fuzzy logic and neural network
The benefit to wireless IDS is numerous and we have seen that the accuracy of the system is seamlessly countable.
But there are couples of drawback found in this implementation. The NeGPAIM-W2 technology is the research
output of a NMMU and it need rigorous test before implementation Because speed of computer and network
technology growing abnormally, how this system will associate with upcoming attacker invented technology also
accountable. There may be bugs and worse vulnerabilities which could potentially weaken the WLAN security. A
potential turn of to a wireless IDS solution may be costly. Also the cost of the wireless IDS solution will grow in
conjunction with the size of the WLAN to monitored, due to requirement for a greater number of sensors. Therefore,
the larger the WLAN, the more expensive the wireless IDS deployment will be.
3.4 New modified architecture for IDS
Observing those weaknesses, here we are going to propose a new modified architecture for overall intrusion
detection system for wireless network segment that is a collaboration of Gumstix [1], high throughput string
matching architecture [2] and proactive intrusion detection architecture [3]. Figure 2 shows the new architecture:
61
Database
High Throughput
String Matching Rule
based Architecture
Central Analysis 5/8/70% Fuzzy Engine
Engine
6/9/75% risk 7/10/80%

risk Neural Engine
Sticky GUM
Architecture for Data
Collection
Access Point Logs
Figure 2: Modified architecture for Intrusion Detection System
Here in this architecture we have included high throughput string matching segment and Sticky GUM segment
inside database module. This insertion of Sticky GUM will help the architecture to collect the data more effectively
and efficiently. It can reduce false negative and false positive determinations of intrusions. The insertion of High
Throughput String Matching segment helps the architecture check the string stream with rules promptly, can keep
updating the rules for new attacks without any interruption of the services. The se of fuzzy engine and neural engine
can implement misuse detection methodology. They can also determine the user behavior to find out whether he/she
is a legitimate or illegal user of the system which leads to proactive mode of operation.
4. Conclusion
The value of Intrusion Detection Systems has been growing tremendously to play an important role as networks
grow and more information is becoming available for access from outside or inside the network segment. The
primary requirement for detecting intruders in a network that the whole intrutsion detection systems should be able
to collect data from the network and manage them efficiently, and analyze them in such a way so that any type of
attacks can be caught promptly. But the problem with current existing intrusion detection systems is that most of
them are no well enough to accurately monitor attacks and report on wireless segment. This works have studied
some literatures which helped us understand effective low cost architecture for collecting, managing, and analyzing
network data through highly configurable and collaborative sensors Gumstix [1, 4]. Since to detect attacks most of
the intrusion detection systems use string matching algorithm, we have also studied this area that gave us idea on
special purpose architecture for novel string matching architecture [2]. Moreover, we have surveyed another
literature regarding effective intrusion detection model NeGPAIM [3] that allows the detection of the attacks in
proactive mode. Finally, we have found some limitations of those approaches and also some extended ideas in some
cases. Observing those weaknesses, this works have also proposed a new modified architecture for overall intrusion
detection system for wireless network segment that is a collaboration of Gumstix [1], high throughput string
matching architecture [2] and proactive intrusion detection architecture [3]. This new architecture will be able to
collect network data more effectively, analyze them proactively and can detect the attacks very quickly.
5. References
[1] E. Derrick, R. Tibbs, L. Reynolds. Investigating new approaches to data collection, management and analysis for
network intrusion detection. In Proc. of the 45th annual southeast regional conference ACM- SE 45, Pages:
283 - 287, Publisher: ACM Press, 2007.
[2] L. Tan, T. Sherwood. A high throughput string matching architecture for intrusion detection and prevention, In
Proc. of the 32nd International Symposium on Computer Architecture, Vol. 33,Issue 2, Pages: 112-122,
Publisher: IEEE Computer Society, 2005.
[3] R. Goss, M. Botha, R. Solms. Utilizing fuzzy logic and neural networks for effective, preventative intrusion
detection in a wireless environment. In Proc of the 2007 annual research conference of the South African
institute of computer scientists and information technologists on IT research in developing countries SAICSIT
'07, Vol. 26, Pages: 29 - 35, Publisher: ACM Press, 2007.
62
[4] Gumstix, Inc. Gumstix – Way small computing. Accessed at http://gumstix.com/index.html.

[5] S. A. Crosby and D. S. Wallach. Denial of service via algorithmic complexity attacks. In Proc. Of USENIX
Annual Technical Conference, June 2003.
[6] http://portal.acm.org/citation.cfm?id=1292491.12924 95.
[7] Ashif Adnan, Muhammad Omair Alam andA.K.M. Aktaruzzaman , Department of Computer Science University
of Windsor .
63
IJCIIS Reviewers
A. Govardhan, Jawaharlal Nehru Technological University, India
Ajay Goel, Haryana Institute of Engineering and Technology, India
Ajay Sharma, Raj Kumar Goel Institute of Technology, India
Akshi Kumar, Delhi Technological University, India
Alok Singh Chauhan, Ewing Christian Institute of Management and Technology, India
Amandeep Dhir, Helsinki University of Technology Finland, Denmark Technical University, Denmark
Amit Kumar Rathi, Jaypee University of Engineering and Technology, India
Amol Potgantwar, Sandip Institute of Technology and Research Centre, India
Anand Sharma, MITS, India
Aos Alaa Zaidan Ansaef, Multimedia University, Malaysia
Arash Habibi Lashkari, University of Technology, Malaysia
Arpita Mehta, Christ University, India
Arul Lawrence Selvakumar, Kuppam Engineering College, India
Ayyappan Kalyanasundaram, Rajiv Gandhi College of Engineering and Technology, India
Azadeh Zamanifar, Iran University of Science and Technology University and Niroo Research Institute,
Iran
Bilal Bahaa Zaidan, University of Malaya, Malaysia
Binod Kumar, Lakshmi Narayan College of Technology, India
B. L. Malleswari, GNITS, India
B. Nagraj, Tamilnadu News Prints and Papers, India
Chakresh Kumar, Galgotias College of Engineering and Technology, India
C. Suresh Gnana Dhas, Vel Tech Multitech Dr.Rengarajan Dr.Sagunthla Engg. College, India
C. Sureshkumar, J. K. K. M. College of Technology, India
Deepankar Sharma, D. J. College of Engineering and Technology, India
Dhirendra Pandey, Babasaheb Bhimrao Ambedkar University, India
Durgesh Kumar Mishra, Acropolis Institute of Technology and Research, India
D. S. R. Murthy, SreeNidhi Institute of Science and Technology, India
G. N. K. Suresh Babu, SAMS College of Engineering and Technology, India
Hafeez Ullah Amin, KUST Kohat, NWFP, Pakistan
Hanumanthappa Jayappa, University of Mysore, India
Himanshu Aggarwal, Punjabi University, India
Jagdish Lal Raheja, Central Electronics Engineering Research Institute, India
Jatinder Singh, UIET Lalru, India
J. Samuel Manoharan, Karunya University, India
Iman Grida Ben Yahia, Telecom SudParis, France
Kanwalvir Singh Dhindsa, B. B. S. B. Engineering College, India
K Padmasree, Yogi Vemana University, India
K. V. N. Sunitha, G. Narayanamma Institute of Technology and Science, India
Leszek Sliwko, CITCO Fund Services, Ireland
M. Azath, Anna University, India
Md. Mobarak Hossain, Asian University of Bangladesh, Bangladesh
64
Mohd Nazri Ismail, University of Kuala Lampur, Malaysia

Mohammed Salem Binwahlan, Hadhramout University of Science and Technology, Yemen
Mohamed Elshaikh, Universiti Malaysia Perlis, Malaysia
M. Surendra Prasad Babu, Andhra University, India
M. Thiyagarajan, Sastra University, India
Manjaiah D. H., Mangalore University, India
Nahib Zaki Rashed, Menoufia Univesity, Egypt
Nagaraju Aitha, Vaagdevi College of Engineering, India
Natarajan Meghanathan, Jackson State University, USA
Navneet Sikarwar, B. S. A. College of Engineering and Technology, India
N. Jaisankar, VIT University, India
Ojesanmi Olusegun Ayodeji, Ajayi Crowther University, Nigeria
Oluwaseyitanfunmi Osunade, University of Ibadan, Nigeria
Perumal Dananjayan, Pondicherry Engineering College, India
Piyush Kumar Shukla, University Institute of Technology, Bhopal, India
Poonam Garg, Institute of Management Technology, India
P. Ramesh Babu, Rajamahendri Institute of Engineering and Technology, India
Praveen Ranjan Srivastava, BITS, India
P. V. Sarathchand, Indur Institute of Engineering and Technology, India
Rajesh Kumar, National University of Singapore, Singapore
Rajeshwari Hegde, BMS College of Engineering, India
Rakesh Chandra Gangwar, Beant College of Engineering and Technology, India
Raman Kumar, D A V Institute of Engineering and Technology, India
Raman Maini, University College of Engineering, Punjabi University, India
Ramveer Singh, Raj Kumar Goel Institute of Technology, India
Sateesh Kumar Peddoju, Vaagdevi College of Engineering, India
Shahram Jamali, University of Mohaghegh Ardabili, Iran
Sriman Narayana Iyengar, India
Suhas Manangi, Microsoft, India
Sujisunadaram Sundaram, Anna University, India
Sukumar Senthilkumar, National Institute of Technology, India
S. Murugan, Alagappa University and Centre for Development for Advanced Computing, India
S. S. Mehta, J. N. V. University, India
S. Smys, Karunya University, India
S. V. Rajashekararadhya, Adichunchanagiri Institute of Technology, India
Thipendra P Singh, Sharda University, India
T. Ramanujam, Krishna Engineering College, Ghaziabad, India
T. Venkat Narayana Rao, Hyderabad Institute of Technology and Management, India
Vasavi Bande, Hyderabad Institute of Technology and Management, India
Vishal Bharti, Dronacharya College of Engineering, India
Vuda Sreenivasarao, St. Mary's College of Engineering and Technology, India
V. Umakanta Sastry, Sreenidhi Institute of Science and Technology, India
Yee Ming Chen, Yuan Ze University, Taiwan
65

IJCIIS March 2011 Vol. 2 No. 3

Uploaded by

Copyright:

Available Formats

IJCIIS March 2011 Vol. 2 No. 3

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

IJCIIS March 2011 Vol. 2 No. 3

Uploaded by

Copyright:

Available Formats

International Journal of Computational Intelligence and Information Security, March 2011, Vol. 2, No.

Computational Intelligence and

IJCIIS Editor and Publisher

Publishing Date: March 30, 2011

Members of IJCIIS Editorial Board

Journal Website: https://sites.google.com/site/ijciisresearch/

2. Evolutionary Image Segmentation By Pixel Classification Application To Medical Images

5. DEPTH Data Emission by Parabolic Transaction Heights (pages 44-49)

AN IMPLEMENTATION OF VECTOR CONTROL OF INDUCTION

PROFESSOR & HEAD – DEPARTMENT OF ELECRICAL AND ELECTRONICS ENGINEERING,

3. Kalman Filter Algorithm

Figure 2: Block diagram of the extended Kalman filter.

4. Vector Control of AC Induction Machines

6. Summary and Scope for future Work

[1] Leonhard, Control Of Electrical Drives, Springer-Verlag, 1985.

Evolutionary Image Segmentation By Pixel Classification

[email protected]; [email protected]; [email protected]

Keywords: Segmentation, evolutionary segmentation, Classification, evolutionary strategies, Segmentation by pixel

where . is a distance which is generally supposed to be Euclidean.

The KM algorithm supposes that the number of classes C is known a priori.

2.3. Kmeans segmentation

Random generation of the initial population

4. Evolutionary Kmeans classification

4.2. The proposed fitness function

4.3. The proposed mutation operator

Let chr be a chromosome of the population formed by the centers (gs)1≤s≤C.

4.4. The proposed EKM algorithm

2.4. Generate randomly the constant fm (fm ∈ [0.5, 1]).

4.5. EKmeans Segmentation

5. Experimental results and evaluations

Figure 3: Synthesised image SYNTH1

Figure 4: Result of image segmentation

The EKM algorithm converges quickly, in 3 generations, figure 5.

Figure 5: Fitness value with respect to the generation.

5.3. Noisy synthetic image

Figure 7: Result of image segmentation

Figure 8: Fitness value with respect to the generation.

Table 4: Number of pixels for each class

Figure 11: Fitness value with respect to the generation.

Tableau 5: Number of pixels for each class

Figure 13: Fitness value with respect to the generation.

A MODIFIED METHOD FOR ORDER REDUCTION OF LARGE SCALE

where ; n is the number of poles and ; m is the number of zeros,

where ; k is the number of poles and ; r ≤ m, r is the number of zeros,

Where ; I = 0,1,2,3, …..

The expansion of G(s) about s = ∞ is

where And Pj are residues.

Define Redefined Markov Parameters (RMPs) as

where And Pj are residues.

where ; j = 0, 1, 2, 3,…, r1 ; r1 is number of RTMs …(8)

and ; j = 0, 1, 2, 3,…, r2 ; r2 is number of RMPs …(9)

Table II : Contribution of poles in RTMs and RMPS of HOS

The denominator polynomial of the 2nd order reduced model is

The second order model proposed by Mukherjee [9] is

The second order model proposed by Parmar [11] is

Fig.1: Comparison of step responses of G1(s) and R2(s)

Fig.2: Comparison of step responses of G1(s), R2(s), R2M(s) and R2P(s)

Table III : Comparison of outputs of step responses of various ROMs at 3 seconds

Parmar et al[10] 1.11

Parmar et al[11] 1.11