Transcript presentation - Georgia Tech Savannah

Reduction in Space Complexity
And Error Detection/Correction of a Fuzzy controller
F. Vainstein
Georgia Institute of Technology
[email protected]
E. Marte
Pontificia universidad Católica Madre y Maestra
[email protected]
V. Osoria
Universidad Tecnológica de Santiago
[email protected]
R. Romero
Instituto Tecnologico de Santo Domingo
[email protected]
REC 2006 - Georgia Tech University
Savannah Feb 22-24
Agenda
Introduction
Fuzzification, Rule Base and Defuzzification
Address Generation
Variable Radix Numbers (Multi Radix)
Reduction in space complexity
Data compression and error correcting codes in Rule Base
Conclusion
REC 2006 - Georgia Tech University
Savannah Feb 22-24
Introduction
Fuzzy controllers prove to be very useful for practical applications,
especially in the cases when there is no appropriate mathematical
model of behavior of the controlled object. Control signal is
computed by fuzzy controller with the use of rule base table.
Fuzzy sets and some basic ideas pertaining to their theory were first
introduced in 1965 by Lofti A. Zadeh, a Professor of Electrical
Engineering at the University of California a Berkeley. The
development of fuzzy set theory and fuzzy logic experimented
changes since their introduction. Therefore the “Fuzzy Boom” (since
1989) has been characterized by a rapid increase in successful
industrial applications that have netted impressive revenues.
REC 2006 - Georgia Tech University
Savannah Feb 22-24
Braunstingl (1995) developed a wall-following robot that used a fuzzy logic
controller and local navigation strategy to determine its movement. The
fuzzy logic controller uses the input variables to control the firing of 33 rules.
A fuzzy system developed by Surmann (1995) controls the navigation of an
autonomous mobile robot. The entire system has about 180 fuzzy rules that
associate 30 fuzzy inputs with 11 outputs. Potentially, the number of fuzzy
rules can be very large.
REC 2006 - Georgia Tech University
Savannah Feb 22-24
The contribution of this paper is to tackle the space complexity of the
system by decreasing the number of addresses lines used to store If-Then
rules. Also the incorporation of error correcting codes in the memory used to
store If-Then rules without substantial increasing space complexity as well
as application of signatures analysis for error detection/location in a fuzzy
controller.
REC 2006 - Georgia Tech University
Savannah Feb 22-24
Fuzzification, Rule Base and Defuzzification
Fuzzy
Attributes
Sensor 0
Fuzzification
Fuzzification
Rule Base
Computational block
Values of Membership
Functions
0.0
r0 0.6
0.3
0.0
0.0
Sensor k
Address
generator
Fuzzification
rk
Rule Base
(1,2,..r)
Computational
Block
Crisp
Output
Defuzzification
0.0
0.0
0.7
0.5
0.0
0.0
0.0
Fig. 1 Basic Fuzzy Controller Block diagram
REC 2006 - Georgia Tech University
Savannah Feb 22-24
Address Generation
Sensor 0
(Position)
Position
r0  5
Sensor 1
(Velocity)
NM
NS
ZE
PS
PM
0.0
0.6
0.3
0.0
0.0
3
Address
generator
Fuzzification
r1  5
To Computational
Block
NM
NS
ZE
PS
PM
0.0
0.0
0.7
0.5
0.0
3
velocity
Fuzzification
NM
NS
ZE
PS
PM
NM
1
5
1
5
1
NS
4
2
3
5
2
ZE
3
1
2
3
5
PS
2
3
1
2
1
PM
1
2
4
1
2
to
computational
block
Rule Base
Fig. 3 Bidimensional Table for Decision
Take of the fuzzy Controller
Fig. 2 Example of Address Generation
REC 2006 - Savannah, Georgia
Feb 22-24
Number of Lines and Space Complexity
log 2 r0
k
N 0   [log 2 ri ]
(1)
log 2 rk
i 0
log 2 r
Rule Base
Fig. 4 Straight forward Address Generation
Example: Let k=9,
r0  r1  ...  r9  5
.
space
complexit
y
exponential
Using (1) we obtain
number of
address lines
N 0  30
Fig. 5 Space Complexity Vs Address Lines
REC 2006 - Savannah, Georgia
Feb 22-24
Variable Radix Numbers (Multi Radix)
By Definition Multy Radix number can be
written as follow:
ar  (ak ,..., a0 )
(2)
The Multy Radix number
ar
has the value
ar  a0  a1r0  a2r0r1  ...  ak r0r1...rk 1
r  {r0 ,..., rk }
Example:
Let’s assume that
a0  {0,..., r0  1}
r0  5, r1  2, r2  7
a1 {0,..., r1 1}
……………….
ak {0,..., rk  1}
Then the multi radix number 4123 it then has
the decimal value
ar  30310
REC 2006 - Savannah, Georgia
Feb 22-24
There exists natural one-to-one correspondence between the set of multi radix numbers and the set of
fuzzy rules. It is demonstrated on Fig. 6 and Fig. 7.
Sensor 0
Sensor 1
0
1
2
0
1
2
3
4
0
1
2
3
4
00
1
01
4
02
3
03
5
04
1
10
3
11
4
12
4
13
1
14
2
20
2
21
1
22
1
23
1
24
2
0
1
2
Fig. 6 Set of fuzzy Rules
Fig. 7 One-to-One Mapping
REC 2006 - Savannah, Georgia
Feb 22-24
Multi Radix to Binary Converter
r0  5, r1  5, r2  3, r3  6
Denote by
w1  r0 , w2  r0r1 ,..., wk  r0r1...rk
(4)
3
Then
a0
ar  a0  a1w1  a2 w2  ...  ak wk
a1
w0
3
w1
+
.
a2
a3
2
[log 2 r0 r1r2 r3 ]  9
w2
3
w3
Convertor
Fig. 8 Multi Radix to Binary Converter
REC 2006 - Georgia Tech University
Savannah Feb 22-24
Reduction in space complexity
Sensor 0
Fuzzification
r0
Sensor k
Address
generator in
noncompact binary
Fuzzification
[log 2 r0 ]
[log 2 rk ]
Multiradix to
Binary
Converter
N
Rule
Base
rk
Fig. 9 Rule Base with Multi radix to Binary Converter
N  [log 2 r0 r1 ...rk ]  [log 2 r0 ]  ...  [log 2 rk ]  N 0
REC 2006 - Georgia Tech University
Savannah Feb 22-24
(5)
Reduction in space complexity (cont.)
Example:
Let
k  9, r0  ..  r9  5
Then the number of initial addresses lines
N 0  30
The number of addresses lines after the Multi Radix to Binary Converter is equal to
.
REC 2006 - Georgia Tech University
Savannah Feb 22-24
N  [log 2 rk ]  24
Data compression and error correcting codes in Rule Base
Example:
Suppose we have 2 Sensors
r0  r  5
,
r 5
Normally, for this case it will take 15 bits for representing a single row as shown in Fig.10.
1
4
3
0 1
001 100 011 000 001
15 Bits
Fig. 10 Single Row 2 Sensors Representation
1
4
3
0
1
Fig. 11 Center Row
To convert it to binary we need
[log 2 55  1]  12
These bits can be used for error correction
bits. We saved 3 bits.
Data compression and error correcting codes in Rule Base
(cont.)
Example:
Suppose that we have 3 sensors,
r0  r1  r2  5;
r 5
In this case we have a number with 25 digits. The biggest possible number
To convert it to binary we need 59 bits. Therefore we saved 75-59=16
bits, see Fig. 12.
2
3
1
5
1
3
2 4
1 2
….
…...…
25 Positions
25*3=75 Bits
Fig. 12 3 Sensors representation
525 1
Rule Base with data compression and Error
Detection/correction
Address
generator
(noncompact binary)
[log 2 r0 ]
[log 2 rk ]
Variable
Radix to
Binary
Converter
N
Rule Base
with error
correction
code
Decoder
N0
check bits
(16)
…
Code Word
Code Word
Code Word
Decode
Fig. 13 Rule Base block Diagram with data compression and Error Detection/Correction
REC 2006 - Georgia Tech University
Savannah Feb 22-24
Testing of a Fuzzy Controller by signature Analysis of test
Response
Test
Patters
[log 2 r0 ]
Variable
Radix to
Binary
Converter
[log 2 rk ]
Rule Base
with error
correction
code
N
M
Decoder
Test
Responses
N0
Fig. 14 Testing by signature analysis
f :Z
N0
2

 Z
M
2
S f   x f (x)
S f   x f (x)
If the signatures
(6)
Z 2M Can be considered as a field
(7)
x  Z2 0 , x  F
N
(8)
Sf
and
Sf
are the same, the test is passed.
REC 2006 - Georgia Tech University
Savannah Feb 22-24
GF (2 m )  F
Conclusion and future work
In this paper we introduced a new representation of numbers – Variable Radix Number system.
Using a Variable Radix Number system we decreased the number of addresses lines in a ROM
that is used to store If-Then rules, thus reducing the space complexity of a fuzzy controller. Also
we incorporated error correcting codes in the memory used to store If-Then rules without
substantial increasing space complexity.
REC 2006 - Georgia Tech University
Savannah Feb 22-24