Computation of Signal Output Probability for Boolean Functions Represented By OBDD

Document Type

Article

Publication Date

6-2004

Publication Title

Computers & Mathematics with Applications

Volume

47

Issue

12

First page number:

1865

Last page number:

1874

Abstract

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.

Keywords

Algebra; Boolean--Data processing; Algorithms; Machine theory; Programming (Mathematics)

Disciplines

Computer and Systems Architecture | Computer Engineering | Computer Sciences | Electrical and Computer Engineering | Theory and Algorithms

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library

Share

COinS