Computation of signal output probability for Boolean functions represented by OBDD
In [1] and [2], two algorithms have been proposed to calculate the output probability of Boolean functions represented by OBDDs, assuming that the input variables are equiprobable and each variable is statistically independent from others. In this paper, we point out that under these assumptions, the output probability calculation is equivalent to counting the number of min-terms of the corresponding Boolean functions. An algorithm is proposed to compute the output probability using simple integer arithmetic as opposed to floating point arithmetic involved in [1,2]. To compute output probability of Boolean functions represented by shared OBDDs and OBDDs with edge negation, we further propose a generalized algorithm. (C) 2004 Elsevier Ltd. All rights reserved.
output probability boolean obdd integer arithmetic