Computation of signal output probability for Boolean functions represented by OBDD

✍ Scribed by Yingtao Jiang; Yuke Wang; Xiaoyu Song; Y. Savaria

• Book ID: 104007431
• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 556 KB
• Volume: 47
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/j.camwa.2003.08.004

✦ Synopsis

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