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...

Full description

Saved in:
Bibliographic Details
Main Authors: Yingtao Jiang, Yihui Tang, Yuke Wang, Savaria, Y.
Format: Conference Proceeding
Language:English
Subjects:
Arithmetic
Boolean functions
Computational complexity
Data structures
Input variables
Integrated circuit interconnections
Logic circuits
Power generation
Probability
Testing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0840-7789
2576-7046
DOI:10.1109/CCECE.1999.807237