Method for automatically determining probabilities associated with a Boolean function
First Claim
Patent Images
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 (x1, x2, x3, . . . xk . . . ) each having a predetermined probability of occurrence (P(x1),P(x2),P(x3), . . . ,P(xk) . . . ), said method comprising:
- constructing a binary decision diagram from said Boolean function, said binary decision diagram having a root event (x1) made of one of said atomic events having the predetermined probability of occurrence P(x1), 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(x1))·
P(L)+P(x1)·
P(H), andusing said probability of occurrence P(f) to perform fault analysis on said electronic system.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
17 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 (x1, x2, x3, . . . xk . . . ) each having a predetermined probability of occurrence (P(x1),P(x2),P(x3), . . . ,P(xk) . . . ), said method comprising:
-
constructing a binary decision diagram from said Boolean function, said binary decision diagram having a root event (x1) made of one of said atomic events having the predetermined probability of occurrence P(x1), 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(x1))·
P(L)+P(x1)·
P(H), andusing said probability of occurrence P(f) to perform fault analysis on said electronic system. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
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 (x1, x2, x3, . . . xk . . . ) each having a predetermined probability of occurrence (P(x1),P(x2),P(x3), . . . ,P(xk) . . . ), said method comprising:
-
constructing a binary decision diagram from said Boolean function, said binary decision diagram having a root event (x1) made of one of said atomic events having the predetermined probability of occurrence P(x1), 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(x1))·
P(L)+P(x1)·
P(H), andusing said probability of occurrence P(f) to perform synthesis and optimization of said electronic circuits.
-
Specification