Probabilistic Aspects of Boolean Switching Functions via a New Transform

Publisher Website
Google Scholar
Abstract
A new algorithm Js mtroduced for computing the probability expression, F = Pr(fl 1), that a Boolean functionfequals 1 as a function of the probabihUes that its inputs equal 1. It is shown that this expression ts umquely characterized by a spectrum vector S. A new matrix P which has the property that S I AP, where A is the mmterm vector of the function f, is then introduced. Next, S is related to the Reed-Muller canomc (RMC) form of the function f, and it is shown that the RMC coefficient vector a can be obtained trivially from the vector S. The reverse transformation is computationally harder. It is also shown how S and P can be used to compute the Walsh ccoefficlents off ~x WORDS AND PmtAsEs: Boolean switching functions, probability expression, random testing, Reed- Muller canonic form, transform techniques, Walsh transform