Search

Affine equivalent classes of Boolean functions have many applications in modern cryptography and circuit design. Previous publications have shown that affine equivalence on the entire space of Boolean functions can be computed up to 10 variables, but not on the quotient Boolean function space modulo functions of different degrees. Computing the number of equivalent classes of cosets of Reed-Muller code R (1 , n) is equivalent to classifying Boolean functions modulo linear functions, which can be computed only when n ≤ 7. Based on the linear representation of the affine group A G L (n , 2) on the quotient space R (s , n) / R (k , n) , we obtain a useful counting formula to compute the number of equivalent classes. Instead of computing the conjugacy classes and representatives directly in A G L (n , 2) , we reduce the computation complexity by introducing an isomorphic permutation group Pn and performing the computation in Pn. With the proposed algorithm, the number of equivalent classes of cosets of R(1,n) can be computed up to 10 variables. Furthermore, the number of equivalent classes on R (s , n) / R (k , n) can also be computed when − 1 ≤ k < s ≤ n ≤ 10, which is a major improvement and advancement comparing to previous methods. [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]

In biological systems, the dynamic analysis method has gained increasing attention in the past decade. The Boolean network is the most common model of a genetic regulatory network. The interactions of activation and inhibition in the genetic regulatory network are modeled as a set of functions of the Boolean network, while the state transitions in the Boolean network reflect the dynamic property of a genetic regulatory network. A difficult problem for state transition analysis is the finding of attractors. In this paper, we modeled the genetic regulatory network as a Boolean network and proposed a solving algorithm to tackle the attractor finding problem. In the proposed algorithm, we partitioned the Boolean network into several blocks consisting of the strongly connected components according to their gradients, and defined the connection between blocks as decision node. Based on the solutions calculated on the decision nodes and using a satisfiability solving algorithm, we identified the attractors in the state transition graph of each block. The proposed algorithm is benchmarked on a variety of genetic regulatory networks. Compared with existing algorithms, it achieved similar performance on small test cases, and outperformed it on larger and more complex ones, which happens to be the trend of the modern genetic regulatory network. Furthermore, while the existing satisfiability-based algorithms cannot be parallelized due to their inherent algorithm design, the proposed algorithm exhibits a good scalability on parallel computing architectures. [ABSTRACT FROM AUTHOR]

Interconnect planning is an important issue in VLSI designs. Routing congestion is an important problem during placement. This paper presents a novel approach to estimating the routing congestion on the hexagonal model with bounded-length detours. It is the first probabilistic estimation work on hexagonal topologies. A combinatorial estimation algorithm is presented. The experimental results demonstrate the effectiveness of the method. [ABSTRACT FROM AUTHOR]