Search

Affine equivalence of Boolean functions has various applications in computer science and modern cryptography, such as circuit design and S-boxes. Existing methods for detecting affine equivalence of Boolean functions work in some cases but not when the truth table of a Boolean function is sparse. To improve previous methods and overcome this limitation, we propose a method by transforming the Boolean function to a function with the property that its function values at the orthonormal basis are all equal to 1 or 0, which narrows down the search space of affine transformations. Our first algorithm has the advantage of getting a smaller search space than previous methods and is especially useful for sparse functions. Specifically, when the Boolean functions are sparse, the search space can be reduced exponentially in average and experiments show the efficiency of our first algorithm. We then present another algorithm to transform one circuit into its equivalent affine circuit by synthesizing a reversible circuit and inserting it in front of the original circuit. To our knowledge, this is the first work to automatically synthesize an affine equivalent circuit for any given circuit and the first to do this by combining reversible circuit and non-reversible circuit. [ABSTRACT FROM AUTHOR]

The classification of Boolean functions plays an underpinning role in logic design and synthesis of VLSI circuits. This paper considers a underpinning question in Boolean function classification: how many distinct classes are there for k-input Boolean functions. We exploit various group algebraic properties to efficiently compute the number of unique equivalent classes. We have reduced the computation complexity from 2mm! to (m + 1)!. We present our analysis for NPN classification of Boolean functions with up to ten variables and compute the number of NP and NPN equivalence classes for 3-10 variables. This is the first time to report the number of NP and NPN classifications for Boolean functions with 9-10 variables. We demonstrate the effectiveness of our method by both theoretical proofs and numeric experiments. [ABSTRACT FROM AUTHOR]

An efficient pairwise Boolean matching algorithm for solving the problem of matching single-output specified Boolean functions under input negation and/or input permutation and/or output negation (NPN) is proposed in this paper. We present the structural signature (SS) vector, which comprises a first-order signature value, two symmetry marks, and a group mark. As a necessary condition for NPN Boolean matching, the SS is more effective than the traditional signature. A symmetry mark can distinguish symmetric variables and asymmetric variables and be used to search for multiple variable mappings in a single variable-mapping search operation, which reduces the search space significantly. Updating the SS vector via Shannon decomposition provides benefits in distinguishing unidentified variables, and the group mark and phase collision check can be used to discover incorrect variable mappings quickly, which also speeds up the NPN Boolean matching process. Using the algorithm proposed in this paper, we test both equivalent and non-equivalent matching speeds on the MCNC benchmark circuit sets and random circuit sets. In the experiment, our algorithm is shown to be 4.2 times faster than competitors when testing equivalent circuits and 172 times faster, on average, when testing non-equivalent circuits. [ABSTRACT FROM AUTHOR]

Affine equivalence classification of Boolean functions has significant applications in logic synthesis and cryptography. Previous studies for classification have been limited by the large set of Boolean functions and the complex operations on the affine group. Although there are many research on affine equivalence classification for parts of Boolean functions in recent years, there are very few results for the entire set of Boolean functions. The best existing result has been achieved by Harrison with 15768919 affine equivalence classes for 6-variable Boolean functions. This paper presents a concise formula for affine equivalence classification of the entire set of Boolean functions as well as a formula for affine classification of Boolean functions with distinct ON-set size respectively. The method outlined in this paper greatly simplifies the affine group's action by constructing an isomorphism mapping from the affine group to a permutation group. By this method, we can compute the affine equivalence classes for up to 10 variables. Experiment results indicate that our scheme for calculating the affine equivalence classes for more than 6 variables is a significant advancement over previous published methods. [ABSTRACT FROM PUBLISHER]

Reversible logic plays an important role in quantum computing. This article presents some novel results on synthesis of 3 × 3 reversible Boolean gates. We derive the relationship between reversible 3 × 3 gates and corresponding symmetric groups. By introducing a set of universal libraries, we show how to use group theory to synthesize any 3 × 3 reversible gate. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]