Abstract:
The invention relates to a method that makes it possible to automatically and exactly calculate the probabilities associated with a Boolean function. The probability of an event represented by a Boolean function (f) is determined by constituting a binary decision diagram of the function and by making recursive traversals through the diagram.

Description:
This is a Continuation of application Ser. No. 08/256,088, filed as PCT/FR93/01055 Oct. 27, 1993, published as WO94/10640 May 11, 1994, now abandoned. 
    
    
     FIELD OF THE INVENTION 
     The invention relates to a method for automatically determining the probabilities associated with a Boolean function, with the aid of a data processing machine. 
     BACKGROUND OF THE INVENTION 
     Boolean functions are manipulated in many fields. By way of example, synthesis and optimization of electronic circuits and system fault analysis can employ the manipulation of Boolean functions. 
     In fault analysis, for example, the occurrence of a fault as a function of external events capable of causing this fault can be analyzed with the aid of a Boolean function. 
     More generally, in any system, the occurrence of a reference event or of an action, when it is a function of one or more concomitant events, also called microscopic events, can thus be analyzed. Each microscopic event is accordingly a variable of the function. 
     For comprehension of the ensuing description, it is appropriate to recall some concepts and definitions relating to Boolean functions, and the terminology used. 
     Let us assume a Boolean function f is defined by the following formula: f=x 1  x 2  *+x 1  *x 2  x 3 . This is said to be a propositional formula, and x 1 , x 2 , x 3  are propositional variables, corresponding to atomic events capable of causing the appearance of the reference event symbolized by the letter f and represented by the formula. 
     Hence in the analysis of system faults the atomic events are the fault causes, and the reference event is a particular fault associated with these causes combined with one another in certain ways. 
     The terms &#34;x 1  &#34;, &#34;x 2  &#34; &#34;x 3  &#34; and &#34;x 1  *&#34; &#34;x 2  *&#34; &#34;x 3  *&#34;, which appear in the formula, are literals corresponding to the propositional variables x 1 , x 2 , x 3 . A literal shows how the propositional variable is involved in the function, or in other words whether the occurrence or nonoccurrence of the associated event is decisive or unimportant. x 1  x 2  * and x 1  * x 2  x 3  are products of literals. A product is accordingly a conjunction of variables and negations of variables. 
     The first product, x 1  x2*, means that the presence or absence of the third variable x 3  is unimportant. 
     The formula means that the reference event occurs (f=1) when simultaneously the first atomic event x 1  occurs (x 1  =1) and the second event x 2  does not occur (x 2  =0), or when simultaneously the first event x 1  does not occur and the second and third events x 2  and x 3  do occur. 
     Such a formula is in fact the result of either simulation or analysis done with a prototype. 
     In analysis of a system (in terms of function or for faults), such a formula is conventionally shown in the form of a table that shows the various products of the function. The table associated with the function given in this example would accordingly contain the products x 1  x 2  * and x 1  * x 2  x 3 . 
     In the field of system fault analysis, a table of this kind is called a fault tree. More generally, it may be called an event tree. 
     Such a tree may be used to perform various analyses or calculations relating to the behavior of the system. In particular, one may contemplate calculating the probability of occurrence of a reference event as a function of that of each of the atomic events. 
     To that end, the table shows not only the products contributing to the occurrence of the function but also the probability of occurrence of each atomic event. This probability has been determined, for instance during simulation or analysis. 
     Nevertheless, calculating the probability of each reference event, such as a fault, must be done after that analysis or simulation. This calculation needs to be automated, because either the table includes an extremely large number of products, or a large number of reference events must be analyzed. 
     Methods known thus far do not provide satisfaction. In fact, they begin with approximation formulas that require calculation of the implicants of the function. 
     It will be recalled that an implicant of a function is a product that implies that function. It will also be recalled that a first product P &#34;contains&#34; a second product P&#39;, if the relation P implies P&#39; (this is written P→P&#39;) is true, and finally, a prime implicant is an implicant such that there is no other implicant that contains it. 
     The use of approximation formulas does not make it possible to attain an exact result. Moreover, this approximate calculation requires processing equipment with a large computational and memorization capacity, because these implicants must be calculated and stored in memory, and numerous intermediate results, originating from these approximative calculations with the implicants, must also be calculated and stored, so that later these implicants or these intermediate results can be combined to obtain the final result. 
     SUMMARY OF THE INVENTION 
     The objects of the invention are accordingly to obtain a method that makes it possible to automatically obtain the exact probability of a reference event, without requiring large memorization capacity. 
     According to the invention, a method for automatically, with the aid of a data processing machine, determining the probability of a reference event depending on atomic events combined with one another, each atomic event having a probability of occurrence known in advance, is characterized in that it consists of working out the binary decision diagram corresponding to the function representative of the reference event, and recursively traversing this diagram to obtain the probability P(f) of the reference event by applying the formula P(f)=(1-P(x 1 ))·P(L)+P(x 1 )·P(H), in which P(x 1 ) is the probability, known in advance, of the root event of the diagrams, and P(L) and P(H), respectively, are the probabilities of the negative branch and positive branch of the tree, these latter being obtained in the course of recursive traversals of the binary decision diagram. 
     In a known manner, a binary decision diagram or graph is made up of a certain number of labels, connected to one another by branches. Each label represents a predetermined variable of the function, from which two branches begin. The set constituted by a label, or in other words a variable, and the two branches that begin at it constitute a node, sometimes called a vertex. Each branch may be either a terminal branch, which ends at a terminal leaf having the value &#34;0&#34; or &#34;1&#34; or an intermediate branch, which ends at the label of a different node. One of the branches that begins at a label is called the low or negative branch and represents what happens when the value of the associated variable is &#34;0&#34; (by using the conventions recalled above), while the other branch, called the high or positive branch, shows what happens when the variable is &#34;1&#34;. In fact, the tree begins at a unique root variable (or label) called the root, from which two branches begin to which other nodes or leaves are connected in cascade. 
     In traversing the tree from the root to the terminal leaf of value 1, a combination of literals is determined for which the function has the value 1, that is, a combination (product) of variables causing the appearance of the reference event shown is reconstituted. Consequently, by making each of the traversals from the root to each of the terminal leaves of value 1, one determines each of the combinations of variables that cause the appearance of the reference event. 
     Such a diagram or graph accordingly makes it possible to visualize all the combinations of variables of one function, in an extremely complete and concise way. The memory space occupied is less by comparison with the tables, and the processing time for the functions shown in the form of binary decision graphs are much faster. 
     Various approaches to binary decision diagrams have been contemplated. Randal E. Bryant, for instance, in a publication appearing in IEEE Transactions on Computers, Vol. C-35, No. 8, August 1986, has shown how the variables and accordingly the nodes can be ordered so as to arrive at extremely compact graphs that nevertheless are perfectly representative of the various combinations of variables appearing in one function. 
     In FIG. 1, a binary decision diagram of a Boolean function is shown, in which three propositional variables x 1 , x 2 , x 3  appear. 
     In the example shown in this FIG. 1, a first variable, identified by a label x 1 , is the root of the graph. Two branches begin at this variable, a first branch at the bottom left and a second branch at the bottom right. The left-hand branch is called the low branch, while the right-hand branch is called the high branch. The set of the root, the low branch and the high branch accordingly constitutes a first node of the diagram. 
     The low branch and the high branch each end in a second variable identified by a label x 2 . A low branch and a high branch are also associated with this second variable, and this constitutes another node. 
     The set of labels (or variables), branches, and leaves associated with a low branch of another variable constitutes what will hereinafter be called the low part L of this variable. The set associated with the high branch of a variable constitutes the high part, marked H, of this variable. 
     Thus the high part of the variable x 1  begins at a node whose root is the variable x 2 , whose low part is a leaf of value 0, and whose high part is a leaf of value 1. 
     In traversing the branches of the tree beginning with the root in the direction of the leaves of value &#34;1&#34;, one determines that the function shown has the value 1 when: 
     x 2  has the value 0 and simultaneously x 1  has the value 0, or 
     x 1  has the value 0 and simultaneously x 2  has the value 1 while x 3  has the value 1. 
     The above is deduced from the traversal of the low branches associated with the root x 1 . 
     In addition, from the high part associated with the root x 1 , one deduces that the function also has the value 1 when x 1  and x 2  simultaneously have the value 1. 
     As a consequence of the above, the function shown may be written as f=x 1  *x 2  *+x 1  *x 2  x 3  +x 1  x 2 . 
     The construction of a binary decision diagram, as shown in FIG. 1, is done in accordance with predetermined known rules, which are not the subject of the present invention. They are described in the aforementioned publication by Randal E. Bryant. 
     Accordingly, the invention extremely advantageously exploits the fact that each high (positive) or low (negative) branch of the diagram in itself constitutes a subdiagram which in turn has its own high and low branches. 
     In short, the determination of the probability of each branch requires simply the memorization of the probability of each sub-branch associated directly with that branch. Hence in the course of the recursive traversals, it suffices to memorize only two values to determine the probability of each sub-branch, and hence a maximum of four values for the entire diagram. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Further characteristics and advantages of the invention will become apparent from the ensuing description in conjunction with FIGS. 1 and 2, in which: 
     FIG. 1 schematically shows the binary decision diagram of a Boolean function (f) and; 
     FIG. 2 shows how the memory of a processing apparatus may be organized so as to contain the information representing the diagram of FIG. 1. 
     FIG. 3 is a flow chart which generally shows the steps used in the method of the instant invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 1, and the way to use it, have already been described extensively above. 
     In a known manner and as indicated, the diagram of FIG. 1 is obtained from a table or event tree, not shown in the drawings. The determination of the diagram from this table, which is not the subject of the present invention, is done in such a way as to optimize the size of the diagram so that the number of labels and branches will be reduced as much as possible. 
     In short, it is stated that the function f illustrated by this diagram and whose developed formula is f=x 1  *x 2  *+x 1  *x 2  x 3  +x 1  x 2  can also be written, by previously agreed upon conventions, as f=x 1  *L+x 1  H. 
     The invention begins with this statement and advantageously exploits the fact that the mode of exact calculation of the probability associated with such a function is as follows: P(f)=(P(x 1 ))·P(L)+P(x 1  *)·P(H), in which P(a) is the probability associated with an event a, which can finally be written as P(F)=(1-P(x 1 ))·P(L))+P(x 1 )·P(H). 
     L and H are subdiagrams in which the variables x 2  and/or x 3  appear. Hence the prior knowledge of the probabilities P(x 1 ), P(x 2 ), P(x 3 ) associated with each microscopic event makes it possible, by making recursive traversals in the diagram, to obtain the global probability of the reference event. 
     FIG. 2 shows how the memory of a computer may be organized to contain the information making up the binary decision diagram of the function shown in FIG. 1. This is absolutely not limiting. 
     It is from this information in memory that the processing system is capable of calculating the probability of the function. 
     In a known fashion, the memory is organized in words, and each word is determined by its absolute or relative address and. 
     In order to represent a binary decision diagram, each word may be divided, for example, into at least five fields: a first field VAR, a second field IND L , a third field IND H , a fourth field GEST, and finally a fifth field PROBA. 
     The first field VAR of a word would contain information indicating the nature and rank of a propositional variable of the function, for example x n . 
     The second field IND L  would indicate whether the low branch of the corresponding variable ends in a node or a leaf. 
     The third field IND H  would indicate whether the high part of the corresponding variable ends in a leaf or in a node. 
     The fourth field GEST would for example contain management parameters required for using the memory, when the traversals are done between the various addresses. 
     More precisely, the second and third fields could be supplemented as follows: If the low branch associated with the propositional variable contained in the word ends in a leaf, then this second field would contain an indication &#34;Val 0&#34; or &#34;Val 1&#34; of the value of this leaf, as shown in certain cases in this FIG. 2. 
     Conversely, if the low branch associated with a propositional variable ends in a node, then this second field IND L  would contain the value of the memory address of the word in which this node is written. 
     The third field IND H  would indicate, in the same way as the second field, whether the high branch associated with a variable ends in a node or a lead, and as applicable contains either an address or a value. 
     The fourth field GEST would contain management parameters indicating the traversals that have already been made, or any other type of information required for the management and utilization of this memory. 
     Finally, the fifth field PROBA would contain the value known in advance of the probability associated with the corresponding variable x n , indicated in the first field VAR. 
     Hence by beginning with the word located at the address AD 1  and traversing the entire memory, the processing system can reconstitute the products for which the function has the value &#34;1&#34;. It is then capable of reconstituting the decision diagram and its different nodes. 
     The determination of the probabilities associated with each branch or sub-branch leads the system to break down the existing nodes in the binary decision diagram. 
     By convention, in the ensuing description, a formula of the type Nd(x, L, H)=y, breaks down the node y into its root, that is, the variable x, its left-hand or low branch L, and its right-hand or high branch H. 
     The determination of the value of the probability of an event, whose function f is represented by a binary decision diagram, can be obtained by implementing a specific algorithm that will hereinafter be called &#34;GETPROBA (f)&#34;, which employs the following steps: 
     First, a test is done to determine the nature of the function. 
     If f=0, then GETPROBA(f)=0, and if f=1, then GETPROBA(f)=1; 
     if f is other than 0 or 1, which means that f is present in the form of a node having a root x k , a low branch L and a high branch H, then a decomposition of the node is performed, and then the &#34;GETPROBA&#34; function implements the following instruction: 
     GETPROBA=(1-GETELEMENTARYPROBA(x k ))·GETPROBA(L)+GETELEMENTARYPROBA(x k )·GETPROBA(H), 
     In which &#34;GETELEMENTARYPROBA(x k )&#34; is an instruction whose execution consists of reading the value of the probability associated with the variable (x k ), in the fifth field &#34;PROBA&#34;, and incorporating it into the calculation. 
     It can also be stated that the instruction &#34;GETPROBA&#34; is recursive, since it requires the calculation of the probabilities associated with the low and high branches L and H, by having recourse to itself. As a consequence, the calculation always begins at terminal nodes of the tree, or in other words nodes whose low and high branches end in terminal leaves having the value 0 and 1, or vice versa. 
     It can also be stated that contrary to the prior art, the algorithm employed makes it possible to determine exactly the value of the probability associated with a predetermined event, since no simplification or approximation whatever is required during the calculation. 
     In addition, the memory consumption is minimal. It suffices in the memory of the processing equipment to provide a buffer memory, whose contents are modified upon each recursion, and which at the time the probability associated with the a label is calculated contains the probability, obtained by implementing the &#34;GETPROBA&#34; function, of each high and low branch associated with this label. 
     While this invention has been described in conjunction with specific embodiments thereof, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. Accordingly, the preferred embodiments of the invention as set forth herein, are intended to be illustrative, not limiting. Various changes may be made without departing from the spirit and scope of the invention as set forth herein and defined in the claims.