Method for automatically determining probabilities associated with a Boolean function

• US 5,737,242 A
• Filed: 11/01/1996
• Issued: 04/07/1998
• Est. Priority Date: 10/30/1992
• Status: Expired due to Fees

• Current Assignee: Bull Sas (Atos SE)
• Original Assignee: Bull Sas (Atos SE)
• Inventors: Madre, Jean-Christophe, Coudert, Olivier
• Primary Examiner(s): Voeltz, Emanuel T.
• Assistant Examiner(s): Wachsman, Hal D.
• Application Number:
  US08/742,872
• Time in Patent Office: 522 Days
• Field of Search: 364/554, 364/550, 364/551.01, 364/571.04, 364/488-491, 382/224, 382/141, 382/160, 371/26, 395/24, 395/27, 395/50-52, 395/61, 395/66, 395/77, 395/911, 395/912, 395/914, 395/55
• US Class Current: 702/139
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 30/3323 using formal methods, e.g. equivalence checking or property checking

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.

Claims

1. A method for fault analysis in an electronic system, said method determining a probability (P(f)) of occurrence of a reference event in the system, said reference event corresponding to a Boolean function (f) of atomic events (x₁, x₂, x₃, . . . x_k . . . ) each having a predetermined probability of occurrence (P(x₁),P(x₂),P(x₃), . . . ,P(x_k) . . . ), said method comprising:

constructing a binary decision diagram from said Boolean function, said binary decision diagram having a root event (x₁) made of one of said atomic events having the predetermined probability of occurrence P(x₁), said root event being connected to a low part (L) and a high part (H) of said binary decision diagram each including others of said atomic events;

storing, in memory means of a data processing machine, data representative of said binary decision diagram and respective predetermined probabilities of said atomic events;

recursively traversing the binary decision diagram from the stored data and predetermined probabilities of the atomic events in each of said low and high parts of said binary decision diagram to obtain a low part probability (P(L)) and a high part probability (P(H));

storing said low part probability and said high part probability in said memory means;

determining, from said stored predetermined probabilities of said root event, said low part probability and said high part probability, the probability of occurrence P(f) of the reference event by applying the formula;

P(f)=(1-P(x₁))·

P(L)+P(x₁)·

P(H), and

using said probability of occurrence P(f) to perform fault analysis on said electronic system.

2. The method of claim 1, wherein said memory means is organized in words, each word having an address (ADn), and being divided into a predetermined number of fields to be representative of said binary decision diagram.

3. The method of claim 2, wherein said binary decision diagram includes nodes, each of said nodes representing one of said atomic events, said atomic events having respective natures and ranks in the binary decision diagram, and said predetermined number of fields includes a first field (VAR) representative of said nature and rank of a corresponding one of said atomic events.

4. The method of claim 2, wherein said binary decision diagram comprises nodes and leafs, each node representing one of said atomic events and having a low branch and a high branch, while each leaf is an end of a branch and has a binary value, and said predetermined number of fields includes a second field (IND_L) indicating whether said low branch of a corresponding node ends in a node or a leaf.

5. The method of claim 4, wherein said low branch ends in a leaf having said binary value and said second field is representative of said binary value.

6. The method of claim 4, wherein said low branch ends in a node and said second field is representative of said address of said word in said memory means.

7. The method of claim 2, wherein said binary decision diagram comprises nodes and leafs, each node representing one of said atomic events and having a low branch and a high branch while each leaf is an end of a branch and has a binary value, and said predetermined number of fields includes a high branch field (IND_H) indicating whether said high branch of a corresponding node ends in a node or a leaf.

8. The method of claim 7, wherein said high branch ends in a leaf having said binary value and said second field is representative of said binary value.

9. The method of claim 7, wherein said high branch ends in a node and said high branch field is representative of said address of said word in said memory means.

10. The method of claim 2, wherein said predetermined number of fields includes a management field (GEST) containing parameters for managing said memory means when said traversals are done between said addresses.

11. The method of claim 2, wherein said predetermined number of fields includes a probability field (PROBA) representative of said predetermined probability of occurrence of a corresponding one of said atomic events.

12. The method of claim 1, wherein:

said binary decision diagram comprises nodes and leafs, each node representing one (x_k) of said atomic events and having a low branch (L) and a high branch (H) while each leaf is an end of a branch and has a binary value,

said recursive traversing step comprises implementing a first function (GETPROBA), which includes a test phase for determining whether the reference event (f) is one of said leaves or said nodes,

and said recursive traversing step is performed from the terminal nodes of said binary decision diagram.

13. The method of claim 12, wherein the reference event (f) determined during said test phase is a leaf having said binary value and said first function (GETPROBA(f)) has said binary value.

14. The method of claim 12, wherein the reference event (f) determined during said test phase is a node and said step of implementing a first function (GETPROBA) comprises determining said atomic event (x_k), said low branch and said high branch of said node, applying a second function (GETELEMENTARYPROBA(x_k)) for retrieving said predetermined probability of occurrence (P(X_k)) of said atomic event, and determining said first function from the formula:

GETPROBA=(1-GETELEMENTARYPROBA(x_k)·

GETPROBA(L)+GETELEMENTARYPROBA(x_k)GETPROBA(H).

15. The method of claim 14, wherein said second function (GETELEMENTARYPROBA(x_k)) is an instruction for reading said predetermined probability of occurrence (P(x_k) from a probability field (PROBA) of a corresponding word in said memory means.

16. The method of claim 14, wherein said memory means has buffer memory means containing said probability (GETPROBA) obtained from said formula and said buffer memory means is modified upon each of said recursion.

17. A method for synthesis and optimization of electronic circuits, said method determining a probability (P(f)) of occurrence of a reference event in the electronic circuits, said reference event corresponding to a Boolean function (f) of atomic events (x₁, x₂, x₃, . . . x_k . . . ) each having a predetermined probability of occurrence (P(x₁),P(x₂),P(x₃), . . . ,P(x_k) . . . ), said method comprising:

constructing a binary decision diagram from said Boolean function, said binary decision diagram having a root event (x₁) made of one of said atomic events having the predetermined probability of occurrence P(x₁), said root event being connected to a low part (L) and a high part (H) of said binary decision diagram each including others of said atomic events;

storing, in memory means of a data processing machine, data representative of said binary decision diagram and respective predetermined probabilities of said atomic events;

recursively traversing the binary decision diagram from the stored data and predetermined probabilities of the atomic events in each of said low and high parts of said binary decision diagram to obtain a low part probability (P(L)) and a high part probability (P(H));

storing said low part probability and said high part probability in said memory means;

determining, from said stored predetermined probabilities of said root event, said low part probability and said high part probability, the probability of occurrence P(f) of the reference event by applying the formula;

P(f)=(1-P(x₁))·

P(L)+P(x₁)·

P(H), and

using said probability of occurrence P(f) to perform synthesis and optimization of said electronic circuits.