Limits of using signatures for permutation independent Boolean comparison

Janett Mohnke, Paul Molitor, Sharad Malik

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


This paper addresses problems that arise while checking the equivalence of two Boolean functions under arbitrary input permutations. The permutation problem has several applications in the synthesis and verification of combinational logic: it arises in the technology mapping stage of logic synthesis and in logic verification. A popular method to solve it is to compute a signature for each variable that helps to establish a correspondence between the variables. Several researchers have suggested a wide range of signatures that have been used for this purpose. However, for each choice of signature, three remain variable that cannot be uniquely identified. Our research has shown that, for a given example, this set of problematic variables tends to be the same - regardless of the choice of signatures. The paper investigates this problem.

Original languageEnglish (US)
Pages (from-to)167-191
Number of pages25
JournalFormal Methods in System Design
Issue number2
StatePublished - Sep 2002

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


  • High level design tools
  • Permutation independent Boolean comparison
  • Reduced ordered binary decision diagram
  • Synthesis and verification


Dive into the research topics of 'Limits of using signatures for permutation independent Boolean comparison'. Together they form a unique fingerprint.

Cite this