Computation of signal output probability for Boolean functions represented by OBDD

In [l] 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 minterms 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 OBDI)s and OBDDs with edge negation, we further propose a generalized algorithm.