Evaluating the output probability of Boolean functions without floating point operations

Recently, two algorithms (M.A. Thornton and V.S.S. Nair, IEEE Trans. Computer-Aided Design, Vol. 14, pp. 1328-1341, 1995 ; D.M. Miller, IEEE Trans. Computer-Aided Design, Vol. 17, pp. 1328-1341, 1998) have been proposed to calculate the output probability of a Boolean function represented by an OBDD (ordered binary decision diagram). Both algorithms assume that (1) the input variables are equi-probable, and (2) each variable is statistically independent from the others. Under these assumptions, we point out that calculating the output probability is actually identical to computing the number of min-terms of the corresponding Boolean functions. Therefore, simple integer arithmetic (as opposed to the floating point arithmetic involved in Thornton et al.´s and Miller´s algorithms) and logic shifts are sufficient to compute the output probability of a Boolean function represented by an OBDD. To compute the output probability of the Boolean functions represented by an OBDD with compacted edge negation, a generalized counting algorithm is also proposed.