A new pairwise NPN Boolean matching algorithm based on structural difference signature

DOI10.3390/SYM11010027MaRDI QIDQ2333963zbMATH OpenOpenAlexFDO

Authors Juling Zhang, William N. N. Hung, Jinzhao Wu, Yixin Zhu, Guowu Yang

Publication date 13 November 2019

Published in Symmetry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/sym11010027

zbMATH Keywords

independent variableNPN Boolean matchingstructural difference signature vectorvariable symmetry

Mathematics Subject Classification ID

Review text

Summary: In this paper, we address an NPN Boolean matching algorithm. The proposed structural difference signature (SDS) of a Boolean function significantly reduces the search space in the Boolean matching process. The paper analyses the size of the search space from three perspectives: the total number of possible transformations, the number of candidate transformations and the number of decompositions. We test the search space and run time on a large number of randomly generated circuits and Microelectronics Center of North Carolina (MCNC) benchmark circuits with 7--22 inputs. The experimental results show that the search space of Boolean matching is greatly reduced and the matching speed is obviously accelerated.

Recommendations

• scientific article; zbMATH DE number 4061303
• Efficient Bit-Parallel Algorithms for (δ,α)-Matching
• An improved Boolean circuit for maximum matching in a convex bipartite graph
• Limits of using signatures for permutation independent Boolean comparison
• On finding the closest bitwise matches in a fixed set
• A structure matching method based on functional dependencies
• Fast Exact NPN Classification by Co-Designing Canonical Form and Its Computation Algorithm

Cites work

• A group algebraic approach to NPN classification of Boolean functions
• Computing Affine Equivalence Classes of Boolean Functions by Group Isomorphism
• Heuristic NPN classification for large functions using AIGs and LEXSAT
• On The Number of Symmetry Types of Boolean Functions of n Variables
• Symmetry groups for the decomposition of reversible computers, quantum computers, and computers in between

Cited in

(2)

• Heuristic NPN classification for large functions using AIGs and LEXSAT
• Fast Exact NPN Classification by Co-Designing Canonical Form and Its Computation Algorithm

This page was built for publication: A new pairwise NPN Boolean matching algorithm based on structural difference signature

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2333963)