Abstract:
An optimized method of computing the value of the degree of membership of a fuzzy variable defined within a universe of discourse that is discreted into a finite number of points by way of a membership function thereof, wherein the membership function is quantified into a finite number of levels corresponding to a finite number of degrees of truth, and is stored as a characteristic value of each subset of fuzzy variable values being all mirrored in one value of said degree of membership corresponding to one of said levels. The computing method includes generating a binary sequence; generating an address signal from the bits in the binary sequence; reading the contents of the memory storing the membership functions at each address signal to obtain a characteristic value; and comparing the characteristic value with the value of a fuzzy input variable. These steps are repeated until a characteristic value is found that is equal to or greater than the value of the fuzzy input variable, the degree of membership sought being correlated with the address value of the characteristic value.

Description:
BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   The present invention relates to a method of computing the degree of membership of a fuzzy variable relative to a membership function thereof. 
   Specifically, the invention relates to a method of computing the value of the degree of membership of a fuzzy variable defined within a universe of discourse that is discreted into a finite number of points relative to a membership function thereof, wherein the membership function is quantified into a finite number of levels corresponding to a finite number of degrees of truth and is stored by way of a characteristic value of each subset of fuzzy variable values being all mirrored in one value of said degree of membership corresponding to one of said levels. 
   The invention also relates to a calculator circuit for carrying into effect the inventive method. 
   2. Description of the Related Art 
   As is well known, a membership function (hereinafter also designated MF) is a single-variable function, and accordingly, can be expressed by a two-dimensional graph. 
   In particular, a membership function MF represents the degree of membership, MF(x), of a fuzzy variable x, and can be described by a graph where the fuzzy variable x is plotted along one axis and its degree of membership, hereinafter designated α, is plotted along the other axis. 
   Encoding the membership function MF has been an object of investigation because it uses up a large amount of memory area, for instance when the membership functions MF are to be stored into a calculator structure. 
   Especially with a digital calculator structure, a much-needed simplification consists in the first place of discreting the membership functions MF for integer values of the fuzzy variable x within the so-called universe of discourse (U.d.D.). 
   In particular, each membership function MF is defined at 0 to 2 n −1 levels, i.e., discreted into n bits. 
   Several techniques are known for storing membership functions MF. 
   A first conventional method uses a table for storing the value of the membership function MF point by point, meaning that a degree α of membership, corresponding to each discreted value of the fuzzy variable x, is stored. 
   This method has a major advantage in that membership functions MF of any forms can be stored, and another advantage in that the degrees α of truth can be extracted from a given fuzzy variable x at a fast rate. 
   It has, however, a serious disadvantage in that the punctual storing of all the membership functions MF involved claims a large amount of memory area. 
   Also known is to reduce the representable set of membership functions MF to a subset containing only certain geometric figures, and under this constraint, to use parameters for storing the membership functions MF. In particular, the degree α of membership of a membership function MF can be computed from these parameters as a function of the fuzzy variable x, and much memory area be saved. 
   This is accompanied, though, by a drastic reduction in the membership functions MF that can be represented accurately, i.e., easily led back to the admitted subset of geometric figures. 
   One such method of membership function encoding and storing is disclosed, for instance, in U.S. Pat. No. 5,875,438, granted on Feb. 23, 1999. 
   In addition, solutions of this kind require the provision of complicated hardware for computing the degree α of membership from a given fuzzy variable x, and long computation times for computing the degrees α of truth. 
   Known is also a method of encoding and storing membership functions MF, wherein the values of the degree α of membership of a membership function MF are stored in a table whose address is indicative of the degree α of membership. Stored in this table for each address value is a maximum, tantamount minimum value in a subset of membership degree values representing all the fuzzy variable values that are mirrored by the same value of the degree α of membership. 
   This membership function encoding and storing method forms the subject matter of a co-pending European patent application by this Applicant. 
   The membership function MF is split into a first or non-decreasing monotone part and a second or non-increasing monotone part, as shown schematically in FIG.  1 . In addition, the membership function MF is quantified into a series of subsets that correspond graphically to horizontal segments, each having the same value α corresponding to said subset of values for the fuzzy variable x. 
   Starting with the non-decreasing monotone part, i.e., from point 0, those subsets of values which give the value α for a result are created for the universe of discourse, and their minima considered. 
   Let it be, for the first or non-decreasing monotone part: 
   x 0  the minimum value in the set of values of the fuzzy variable, x[x ,x 1 [, whereby α=0; 
   x 1  the minimum value in the set of values of x[x 1 ,x 2 [ whereby α=1; 
   and so on to xk, being the minimum value in the set of values of x[xk,x(k+1)[ whereby α=k, i.e., the highest degree of membership max; 
   and for the second or non-increasing monotone part: 
   x (k+1)  the minimum value in the set of values of the fuzzy variable, X[X (k+1) ,X (k+2) [ whereby α=(k−1); 
   X (k+2)  the minimum value in the set of values of x[x (k+1) ,x (k+2) [ whereby α=(k−2); 
   and so on to x 2k , being the minimum value in the set of values of x[x (2k) ,max] whereby α=(k−k)=0, i.e., the lowest degree of membership. 
   The first value x 0  is known beforehand from that it coincides with the lowest value in the universe of discourse U.d.D., usually equal 0. 
   In this way, the universe of discourse is split into a number of contiguous ranges ([x i ,x (i+1) [), each having a single value of the degree of membership, MF(x 1 )=α i , where x i  is the lowest value of the fuzzy variable x within that range, associated therewith. 
   The membership function MF can now be encoded and stored into a membership function storage memory MMF, with x 0  being stored at address 0, x 1  at address 1, and so on to x k , which is stored at address k. 
   In a similar manner, x (k+1)  is stored at address k+1, x (k+2)  stored at address k+2, and so on to X 2k , which is stored at address 2k, as shown schematically in FIG.  2 . 
   Notice that the values x 0  x 1  x 2 , . . . , x (2k−1) , X 2k  are not continuous values, but rather discrete values included between 0 and the highest value max in the universe of discourse U.d.D. For example, with values of the degree of membership within the range of 0 to 3 and values of the universe of discourse U.d.D. within the range of 0 to 16, the following values are obtained:
 
x 0 =0, x 1 =4, x 2 =5, x 3 =8, x 4 =10, x 5 =13 and x 6 =15.
 
   The aforementioned patent application also discloses a method of computing the degree α of membership that corresponds to the degree of membership of the value x ing  of said fuzzy input variable, which method comprises reading sequentially from the memory MMF until a characteristic value x m , contained in the memory MMF, is found whereby the first values are higher than or equal to the value of a fuzzy input variable x ing , the location of the value x m  in the memory MMF being correlated with the value of the degree α of membership sought. 
   In particular, the computation time of the corresponding calculator circuit described in that European patent application is a multiple of the clock frequency of the internal counter of the calculator circuit. Thus, assuming the highest degree of membership to be k=(2 n −1), computing the degree of membership for a given value of the fuzzy input variable x ing  will require a time equal to 2k+1 clock beats, i.e., the time needed for the counter output signal to reach that maximum value. 
   In other words, the time for computing the degree of membership of a fuzzy input variable x ing  is directly proportional to the degree of membership, meaning that the more the bits needed to represent that degree of membership, the more will be the memory words needed to store the membership functions MF and the longer the time taken to compute the degree α of membership tied to the fuzzy input variable x ing . 
   The size of the memory MMF storing the membership functions MF will be dictated by the universe of discourse U.d.D. and the magnitude of the highest degree of membership. Mathematically, assuming the universe of discourse U.d.D. to be represented by n bits and a degree of membership by p bits, with k=2 P −1, the membership function storing table will have (2k+1) rows of n bits each. 
   With the calculator circuit described in the aforementioned European patent application, whereby the largest of the ranges is stored, the membership function storing table is read serially. In particular, the counter in the calculator circuit will keep generating read addresses to the table until a stored value x m  equal to or higher than the value of the fuzzy input variable x ing  is read, the location of this value in the table being correlated with the value of the degree α of membership sought. 
   In particular, the degree α of membership is computed from the address ADD according to the following relations:
 
α=ADD if ADD≦2 p −1, and
 
α=ADD−2 p +1 if ADD&gt;2 p −1.
 
   The computation time, therefore, amounts to (2k+1) read accesses to the memory MMF for the membership functions MF, with k=2 p −1. 
   The underlying technical problem of this invention is to provide an optimized method of computing the value of the degree MF(x) of membership of a fuzzy variable by way of its membership function MF, wherein the computation time is reduced and the limitations of the computing method according to the prior art are overcome. 
   BRIEF SUMMARY OF THE INVENTION 
   The solvent idea of the technical problem is achieved, according to the invention, by generating the following type of a binary sequence N: 
   N=100 . . . 0, 110 . . . 0, 111 . . . 0, . . . , 111 . . . 1 
   from which an address signal can be computed to read the contents of the membership function memory, and a corresponding degree of membership obtained, without the memory having to be read sequentially. 
   Based on this idea, the technical problem is solved by a method of computing the degree α of membership of a fuzzy variable by way of its membership function MF. The method includes generating a binary sequence of bits; generating an address signal from the bits in the binary sequence; reading the contents of the memory storing the membership functions on the occurrence of each address signal to obtain a characteristic value; comparing the characteristic value with the value of a fuzzy input variable; and repeating the foregoing steps until a characteristic value is found that is equal to or greater than the value of the fuzzy input variable, the degree of membership α sought being correlated with the address value ADD of the characteristic value according to the following relation:
 
α=ADD when ADD≦2 p −1, and
 
α=ADD−2 p +1 when ADD&gt;2 p −1,
 
   where p is the number of levels corresponding to a finite number of degrees of truth. 
   The technical problem is further solved by an optimized calculator circuit for computing the degree α of membership of a fuzzy variable by way of its membership function MF. The calculator circuit includes a memory table containing characteristic values of each subset of values of fuzzy variables being mirrored in one value of the degree of membership; a comparator connected to the input site of the table; a sequence generator having a clock terminal to receive a clock signal, a reset terminal to receive a reset signal, and an output terminal to supply a binary sequence; and an address generator by algorithm having an input terminal connected to the output terminal of the sequence generator, the sequence generator generating at each beat of the clock signal the binary sequence supplied to the address generator, the address generator generating an address signal to the table for reading the table of contents on the occurrence of the address signal and obtaining the characteristic value contained therein. 

   
     BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
     The features and advantages of the method and the calculator circuit according to the invention will appear from the following description of embodiments thereof, given by way of non-limitative examples with reference to the accompanying drawings. 
     In the drawings: 
       FIG. 1  illustrates a membership function MF as discreted and quantified for storing by a first conventional method; 
       FIG. 2  shows schematically a memory table for storing up the membership function MF of  FIG. 1 ; 
       FIG. 3  shows schematically a calculator circuit for carrying out the computing method of this invention; 
       FIG. 4  is a detail view of the calculator circuit shown in  FIG. 3 ; 
       FIG. 5  is another detail view of the calculator circuit shown in  FIG. 3 ; 
       FIG. 6  is a detail view of the circuit shown in  FIG. 5 ; and 
       FIG. 7  is another detail view of the circuit shown in FIG.  5 . 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   With reference to the encoding and storing method described hereinabove, a method of computing the value of the degree α of membership will be described, which is quite simple and can be carried out on hardware of moderate size. In particular, reference is made to storing the minimum values in the ranges that comprise the universe of discourse U.d.D. 
   As said before, the size of the memory MMF for the membership functions MF is dependent on the size of the universe of discourse U.d.D. and the highest possible value of the degrees of truth. 
   Assume the universe of discourse U.d.D to be represented with n bits, and the degree of membership with p bits. Given that k=2 p −1, a memory having (2k+1) rows of n bits will be employed to represent a membership function MF by the above encoding and storing method. 
   Advantageously, in accordance with an embodiment of this invention, a method of computing the degree α of membership of a fuzzy variable by way of its membership function MF, wherein the membership function MF is encoded and stored into a memory MMF as previously described, is provided. 
   Specifically, the computing method of this invention comprises generating a binary sequence N of the following type: 
   N=100 . . . 0, 110 . . . 0, 111 . . . 0, . . . 111 . . . 1 
   after an appropriate reset signal RST is received, which signal gives the start to the computing of the degree α of membership that corresponds to a fuzzy input variable x ing . 
   The binary sequence N is generated, from the value 100 . . . 0 to the value 111 . . . 1, by increasing the “1&#39;s”, from left to right at each beat of the clock signal CLK, so as to propagate a value “1” from the most significant bit (MSB) to the least significant bit (LSB). 
   The bits in the binary sequence N are processed by the following algorithm, to obtain an address signal ADD: 
   assuming ADD to be a binary number of i=(p+1) bits, ADD(i)=MSB, ADD(0)=LSB, and S an internal position signal, 
                        
 
   where CTRL is a control signal of the computation sequence. 
   The address signal ADD is used for reading the contents of the memory MMF storing the membership functions MF; a characteristic value x m  contained in the range [x 0 ,x 2k ] will be obtained at each address ADD. 
   This characteristic value x m  will correspond to the smallest or the largest of the ranges comprising the universe of discourse U.d.D., according to the storage method being used. In the instance under consideration, the characteristic value x m  corresponds to the smallest of said ranges. 
   This characteristic value x m  is compared with the value of the fuzzy input variable x ing , and the binary sequence N is increased up to a characteristic value x m  which is equal to or greater than the value of the fuzzy input variable x ing . 
   In particular, the control signal CTRL and a blocking signal BL to interrupt generation of the binary sequence N are generated based on the result of said comparison. 
   At the end of the search, the address signal ADD will include the location of the range sought in the memory MMF, whence the value of the degree α of membership can be computed conventionally. In particular, the degree α of membership is computed from the address signal ADD by the following relations:
 
α=ADD if ADD≦2 p −1, and
 
α=ADD−2 p +1 if ADD&gt;2 p −1.
 
   Briefly, the method of computing the degree of membership, according to this invention, comprises no sequential reading from the membership function memory but starts from a middle position, thereby reducing to p+1 the number of steps required in order to find the desired value. 
   Advantageously, the method of computing the degree of membership, according to this embodiment of the invention, provides for the use of a polarity signal POL to enable computation of the value of the degree α of membership or a negated value α′ of the degree of membership, according to the following criteria:
         when the polarity signal is null (POL=0), compute the value of the degree α of membership;   when the polarity signal is one (POL=1), compute the negated value α′ of the degree of membership.   It should be noted that, to compute the information sought, i.e., the value α or its negation α′, the following rules apply:   if the input x ing  occurs within the non-decreasing monotone part of the membership function MF, then the value ADD is coincident with the value α;   if the input x ing  occurs within the non-increasing monotone part of the membership function MF, then the value (ADD−2 p +1) is coincident with the negated value α′.       

   The negated value α′ is defined notionally as the highest value of the degree of membership from which the value α is subtracted, i.e.,:
 
α′=(Max degree of membership)−α.
 
   In the binary system, assuming the highest value of the degree of membership to be coincident with the highest value that can be represented by the available bits (a condition always adopted in order to optimize fuzzy systems), the negated value α′ may be simply computed by negating the value α bit by bit, and correspondingly, the value α computed by inverting the negated value α′ bit by bit. 
   A calculator circuit  10 , implementing the computing method of this invention, will now be described with reference in particular to FIG.  3 . 
   This calculator circuit  10  is used to compute, from the value of the fuzzy input variable x ing , either the value of the degree α of membership or its negated value α′, according to a polarity signal, and advantageously in this invention, has a computation time equivalent to (p+1) read accesses to the memory MMF storing the membership functions MF, with k=2 p −1 at the highest value of the degree of membership that can be represented with p bits. 
   Advantageously in this invention, the computation time is shorter than the computation time of conventional devices, being in particular equal to p+1, i.e., less than half the computation time of the calculator circuit described in the co-pending European patent application by this Applicant. 
   The calculator circuit  10  of this invention comprises basically a sequence generator  1 , which is cascade-connected to an address generator  2  by algorithm, in turn cascade-connected to a table  3  corresponding to the memory MMF storing the membership functions MF. 
   In particular, the sequence generator  1  has a clock terminal CLK 1 , a reset terminal RST 1  receiving a reset signal RST, and an output terminal N 1 , the latter being connected to a corresponding input terminal N 2  of the address generator  2  by algorithm. 
   The address generator  2  by algorithm has a clock terminal CLK 2  arranged to receive a clock signal CLK, a reset terminal RST 2  to receive the reset signal RST, a control terminal C 2 , and an output terminal P 2  connected to the table  3  containing the minima of the ranges [x i ,x j+1 ] and being adapted to supply an address signal ADD. 
   The calculator circuit  10  further comprises a comparator  4  receiving, on a first input A, the value of the fuzzy input variable x ing , and receiving, on a second input B, the characteristic value x m =MMF(ADD) read from the table  3  at the address ADD provided by the address generator  2 . 
   The comparator  4  also has a first output terminal C connected, through a first logic inverter NOT 1 , to the control terminal C 2  of the address generator  2  by algorithm, and has a second output terminal D connected to an input terminal of a logic gate  5  through a second logic inverter NOT 2 . The first output terminal C supplies a control signal CTRL, and the second output terminal D a blocking signal BL. 
   In particular, the logic gate  5  is an AND logic gate, receiving the clock signal CLK on another input terminal and having an output terminal connected to the clock terminal CLK 1  of the sequence generator  1 . 
   The comparator  4  operates according to the following logic (where the input and output terminals are specified instead of the signals, for simplicity): 
                        
 
   The control signal CTRL at the output terminal C is stored and used by the address generator  2  for the next address computations, and the blocking signal BL at the output terminal D is effective to stop the clock signal CLK through the logic gate  5  when the signal read from the table  3 , upon the occurrence of the address signal ADD on the input terminal B, corresponds to the value of the fuzzy input variable x ing  at the input terminal A. 
   In other words, the calculator circuit  10  of this invention allows the range ([x (i−1 ,x i [), containing the fuzzy input variable x ing , to be found within a number p+1 of clock beats. 
   More precisely, the sequence generator  1  comprises a plurality of cascaded flip-flops FF 1 , . . . , FFi, as shown schematically in FIG.  4 . In particular, said plurality of flip-flops FF 1 , . . . , FFi are all supplied a supply voltage Vdd and input the clock signal CLK and reset signal RST, and will output a binary sequence N of bits, as follows: 
   N=100 . . . 0, 110 . . . 0, 111 . . . 0, 111 . . . 1. 
   In other words, the sequence generator  1  generates a binary sequence N, from value 100 . . . 0 to value 111 . . . 1, by increasing the “1&#39;s” from left to right at each beat of the clock signal CLK, through the flip-flop chain FF 1 , . . . , FFi. On the occurrence of the reset signal RST, these flip-flops will store and propagate an input value “1”, from the most significant bit MSB to the least significant bit LSB. 
   The outputs from the flip-flop plurality FF 1 , . . . , FFi are combined, in an AND type of logic, with the corresponding bits of the binary sequence N, thereby providing address signals IND. 
   In particular, and as shown schematically in  FIG. 5 , the binary sequence N is fed to the address generator  2 , which operates by the following algorithm: 
   assuming ADD to be a binary number of i bits, ADD(i)=MSB, ADD( 0 )=LSB, and S a position signal internal of the address generator  2 , 
                        
 
   An example of an address generator  2  using the above algorithm is shown schematically in FIG.  5 . The address generator  2  comprises a selector  6  arranged to receive the binary sequence N and to generate the internal location signal S, comprising a sequence of 0&#39;s and one 1 at the location to be read, and comprises a controlled zero setter  7  arranged to receive the internal position signal S and the control signal CTRL. 
   In particular, the controlled zero setter  7  either leaves a value  1  or resets the output of a selected flip-flop FFn through the selector  6 , according to the value of the control signal CTRL. 
   Embodiments of the selector  6  and the controlled zero setter  7 , which comprise logic gates and flip-flops, are shown in  FIGS. 6 and 7  by way of examples. 
   In particular, the selector  6  shown in  FIG. 6  comprises a plurality of logic gates PL 1 , . . . , PLi being input the binary sequence N and outputting the internal position signal S. 
   The controlled zero setter  7  shown in  FIG. 7  comprises a plurality of flip-flops FF 71 , . . . , FF 7 i, having a first input terminal connected to one of a plurality of multiplexers MX 1 , . . . , MXi, a second input terminal receiving the clock signal CLK, a first output terminal connected to an input terminal of said multiplexers MX 1 , . . . , MXi, a second output terminal connected to a plurality of logic gates PL 71 , . . . , PL 7 i, and a control terminal receiving the reset signal RST. 
   The multiplexers MX 1 , . . . , MXi have another input terminal to receive a signal C′, which signal is the value of the signal at the output terminal C of the comparator  4  as negated through the first logic inverter NOT 1 , and have a control terminal to receive the internal position signal S from the selector  6 . 
   The logic gates PL 71 , . . . , PL 7 i are AND gates receiving, on another input terminal, the binary sequence N, and providing, on an output terminal, the address signal ADD. 
   The operation of the calculator circuit  10  will now be described. 
   The sequence generator  1 , after receiving a suitable reset signal RST indicating the start of the step of computing the degree α of membership corresponding to a fuzzy input variable x ing , will begin to generate the binary sequence N at each beat of the clock signal CLK. 
   This binary sequence N is filtered through the address generator  2 , the latter generating an address ADD to the table  3 , whereby the contents of the memory MMF is read at the address ADD and the characteristic value x m =MMF(ADD) obtained. 
   The characteristic value x m  from the table  3  is input to the comparator  4 , and the comparator  4  compares its value with the value of the fuzzy input variable x ing , and generates accordingly the control signal CTRL to the output terminal C of the comparator  4  and the blocking signal BL to the output terminal D of the comparator  4 . 
   At the end of the search, the address signal ADD will contain the location in the table  3 , and therefore in the memory MMF, of the range sought, from which the value of the degree α of membership can be computed, as explained before in connection with conventional calculator circuits. 
   In particular, it will be recalled that the following rule applies to computing the information sought, i. e., the value α or its negation α′: 
   if the input x ing  lies in the non-decreasing monotone part of the membership function MF, then the address signal ADD coincides with the value α; 
   if the input x ing  lies in the non-increasing monotone part of the membership function MF, then the value (ADD−2p+1) coincides with the value α. 
   It should be noted that the negated value α′ is defined notionally as the highest value of the degree of membership from which the value α is subtracted or, expressed in formulae:
 
α′=(Max degree of membership)−α.
 
   Assuming that in a binary representation the highest value of the degree of membership is coincident with the highest value that can be represented by the available bits (this being a condition that is always adopted in order to optimize fuzzy systems), the negated value α′ can be simply computed by negating the value α bit by bit, and conversely, the value α can be computed by inverting the negated value α′ bit by bit. 
   In addition, the applicability of the computing method of the invention can be readily extended to include membership functions MF having maxima and minima in larger numbers than one. This is achieved by splitting into several segments having one maximum and one minimum and applying the computation of the value α to each non-increasing or non-decreasing monotone segment. 
   Finally, it should be noted that the calculator circuit  10 , shown schematically in  FIG. 3 , is but one of many hardware circuits that can carry out the computing method of this invention. For example, by changing the operating propriety of the blocking signal BL that enables the sequence generator  1 , a comparator of the A&lt;B type may be used as the block  4 . 
   In conclusion, advantageously according to the invention, the computing method according to the invention takes less time to compute the degree α of membership, corresponding to the value of a given fuzzy variable x, than conventional calculator circuits. 
   From the foregoing it will be appreciated that, although specific embodiments of the invention have been described herein for purposes of illustration, various modifications may be made without deviating from the spirit and scope of the invention. Accordingly, the invention is not limited except as by the appended claims and the equivalents thereof.