Affordable Access

Access to the full text

Numerical computation of characteristic polynomials of Boolean functions and its applications

Authors
  • Agrawal, Vishwani D.1
  • Lee, David1
  • Woźniakowski, Henryk2
  • 1 Bell Laboratories, Murray Hill, NJ, 07974, USA , Murray Hill
  • 2 Columbia University, New York, USA and Institute of Applied Mathematics, University of Warsaw, Warsaw, Poland , Warsaw
Type
Published Article
Journal
Numerical Algorithms
Publisher
Springer US
Publication Date
Jul 01, 1998
Volume
17
Issue
3-4
Pages
261–278
Identifiers
DOI: 10.1023/A:1016632423579
Source
Springer Nature
Keywords
License
Yellow

Abstract

We study the problem of evaluation of characteristic polynomials of Boolean functions with applications to combinational circuit verification. Two Boolean functions are equivalent if and only if their corresponding characteristic polynomials are identical. However, to verify the equivalence of two Boolean functions it is often impractical to construct the corresponding characteristic polynomials due to a possible exponential blow-up of the terms of the polynomials. Instead, we compare their values at a sample point without explicitly constructing the characteristic polynomials. Specifically, we sample uniformly at random in a unit cube and determine whether two characteristic polynomials are identical by their evaluations at the sample point; the error probability is zero when there are no round-off errors. In the presence of round-off errors, we sample on regular grids and analyze the error probability. We discuss in detail the Shannon expansion for characteristic polynomial evaluation.

Report this publication

Statistics

Seen <100 times