Abstract

In this paper, we review various real-life CAD-related problems that can be formulated with Boolean reasonings. The problems listed are all important ones in CAD for digital systems. Everything in logic design is relating to Boolean functions and many of them have been solved by applying Boolean reasoning techniques, such as logic expression simplification, Boolean function manipulation, etc.
However, there are still many problems in CAD for digital systems that could be solved effectively and efficiently by Boolean reasoning. Here we will list them up with examples and discuss what are the key issues in terms of practicalness when we try to solve them with Boolean reasoning. We also show some initial research activities in attacking those problems.
The topics shown here are:

• Logic synthesis/optimization issues
  • Logic circuit optimization and redesign by formulation with Boolean unification
  • Engineering change problems in logic synthesis with quantified Boolean formulae
  • AND-EOR minimization and other logic optimization with Boolean unification
• Logic verification issues
  • Problems related to Boolean comparison: Flip-flop matching and Boolean comparison with internal don't cares
  • SAT based model checking and its variants
  • High level verification with uninterpreted functions

Once some of them are solved with practical performance, they are sure to be used in practical design environment for digital systems, and influence a lot in terms of quality of such designs.
In this paper we will concentrate only on logic synthesis field. In the actual presentation, we will give details on all of the above.

Abstract

We present an implicit approach to solve problems arising in decomposition of incompletely specified multi-valued functions and relations. We introduce a new representation based on binary-encoded multi-valued decision diagrams (BEMDDs). This representation shares desirable properties of MDDs, in particular, compactness, and is applicable to weakly-specified relations with a large number of output values. This makes our decomposition approach particularly useful for data mining and machine learning.
Using BEMDDs to represent multi-valued relations we have developed two complementary input support minimization algorithms. The first algorithm is efficient when the resulting support contains almost all initial variables; the second is efficient when it contains only a few. We propose a simple heuristic measure to choose which algorithm to use. Numerical results over a set of multi-valued benchmarks provide experimental evidence for the efficiency of our approach.

Abstract

Solving large systems of Boolean equations is a hard combinatorial problems. It can be greatly facilitated by preliminary reducing the number of roots in separate equations which, in its turn, leads to decreasing the number of variables in a considered system and the number of equations. Three reduction methods are suggested in this paper for that, called spreading of constants, local reduction and technique of syllogisms. They were programmed in C++, and extensive experiments were conducted on PC Pentium 100, witnessing high efficiency of the methods and their applicability in a wide range of system parameters.

Abstract

Traditional approaches to solving satisfiability problems have been centered on assigning values to one variable at a time and simplifying the expression. This paper shows an effective algorithm which takes advantage of the parallel nature of bit processing at the register level of computers, in order to process all of the boolean variables in a satisfiability formula simultaneously. This inherent parallelism is used to intersect known solution sets from different clauses of the formula. If there exists a non-empty intersection of solution sets from each clause, then the formula is shown to be satisfiable.

Abstract

A pure algebraic approach to linear automata theory is presented exhibiting the formal analogy to time discrete system theory. With respect to the homogeneous equations especially the eigenvalues of the systemmatrix and the stability of the states are investigated.

Abstract

In this paper, we extend various Boolean representations for switching functions, as SOPs, Reed-Muller expressions, Kronecker, and Pseudo Kronecker AND-EXOR expressions, to functions used in Fibonacci interconnection topologies. Then, we extend the world-level expressions, as arithmetic expressions, and Walsh expressions, to these functions. We introduced the corresponding decision diagrams as graphic representations of these bit-level and word-level expressions. In this way, we provide a base to extend the application of powerful CAD design tools for switching functions to functions in Fibonacci interconnection topologies.

Abstract

Many problems which belong to the classes NP and NP-Complete are permutation-dependent. Their solution depends on finding some appropriate permutation of a set of objects. Since no known polynomial-time algorithms are available for such problems, a deterministic approach to solving them requires the enumeration of all possible permutations of the objects. This leads to unacceptable algorithmic performance. This paper demonstrates a technique derived from the field of Evolutionary Algorithms, which uses the transpositional nature of permutations, both for solving such permutation-dependent problems as well as for dealing with the more complicated subset problems that can occur.

Abstract

We introduce new representations for Boolean functions which look like polynomials whose summands are operator images of odd functions. The obtained classes of canonical forms extend many of known classes, for example GRM and KRO. For classes of operator canonical forms which are called here heterogeneous, effective algorithms for finding coefficients are found. The new representations can be used for synthesis of quasi-minimum ESOP circuits.

Abstract

Calculation of a function's autocorrelation coefficients is usually done either by brute force application of the defining equation, or by using a fast method to calculate the interim spectral coefficients and applying a transform to these coefficients. Both of these methods require time exponential in the number of inputs to calculate each coefficient. We present in this paper various methods for more efficient calculation of a function's first order autocorrelation coefficients. The first method is based on a disjoint cube list, and requires on the order of p² time for each coefficient, where p is the number of cubes in the disjoint list. The other methods are based on ROBDD representations of the function(s). Advantages and disadvantages of each method is discussed, and possibilities for other techniques are introduced.

Abstract

To decrease the circuit depth the assorted means of multiplexing are suggested to use. The multiplexing-based approach consists in realizing the given Boolean function through appropriate switching some circuits corresponding to functions which are less in complexity than the initial one. Instead of conventional multiplexers it is proposed to use tri-state gates located among other gates of a circuit. This technique is said to be «multiplexing without multiplexers». Thanks to flexible multiplexing provided by the suggested technique the excessive area consumption inherent in the multiplexing-based approach in general can be reduced.

Abstract

In the paper, we consider the problem of checking whether cubes from a set S are implicants of a DNF formula D, at the same time minimizing the overall time taken by the checks. An obvious but inefficient way of solving the problem is to perform all the checks independently. In the paper, we consider a different approach. The key idea is that when checking whether a cube C from S is an implicant of D we can deduce (learn) implicants of D that are not implicants of C. These cubes can be used in the following checks for search pruning. Experiments on random DNF formulas, DIMACS benchmarks and DNF formulas describing circuits show that the proposed learning procedure reduces the overall time taken by checks by up to two orders of magnitude.

Abstract

The paper presents a minimization algorithm for Boolean functions whose values are defined only for a small part of their range. In contrast to other known minimization algorithms, it uses the "start big" strategy gradually reducing the dimensionality of a term until an implicant is generated. This approach leads to a very fast solution even for problems with several hundreds of input variables and several hundreds of minterms with defined output values. Its programmed version gave in these cases better results (in terms of runtime and minimality of the solution) than the state-of-the-art ESPRESSO.

Abstract

In this paper, we briefly discuss the Haar spectral diagrams (HSDs). Then, we define the Haar transform decision diagrams (HSTDDs). We show that the exact algorithm by Karpovsky for minimization of the number of non-zero coeĆcients in the Haar spectrum can be used for minimization of the number of paths and the number of nodes in HSTDs. This research was motivated by the following issues.

1. Decision diagrams (DDs) are a data structure permitting representation of large discrete functions efficiently in terms of space and time. The optimization of DD representation for a given function is an important issue in applications of DDs. The optimization of DDs aims at the reduction of some basic characteristics of a DD, for example, the number of nodes (size of the DD), the number of levels (depth of the DD), the number of paths. However, most of the minimization algorithms are heuristic. The exact algorithms perform checking of all possible combinations of parameters permitting reduction of a characteristic of the DD.
2. There is apparent a renewed considerable interest in application of discrete Haar transform in logic design and related areas.

Abstract

Boolean derivatives and differentials are used as models for changes in discrete, binary coded systems. Derivatives describe dynamic properties of Boolean functions, e.g. dependence and independence, linearity and monotonicity. They are operators generating other Boolean functions. Equations with derivatives define classes of Boolean functions. Boolean Differentials are models for any kinds of changes, e.g. signal edges, errors, deviations. Equations with differentials define graphs of dynamic systems. A unified theory of derivatives and differentials called Boolean Differential Calculus will be presented.

Abstract

Logic differential and integral calculus is a counterpart of classical differential and integral calculus adapted to applications in switching theory and logic design. In this paper, we analyze the most important achievements in this area in the last fifty years and briefly discuss future trends of development of this theory and related applications. We show examples of practical applications of logic differential operators.

Abstract

In this paper we investigate the possibility of faster calculation of operations on Boolean functions. We use the representation of function as an ordered list of ternary or Boolean vectors and propose a faster algorithm to reduce their number, profit by ordering. We sort the vectors in lists using the number of ones and strokes and create a model of classes and subclasses. This model is used in faster blockbuilding algorithm.
Our algorithm is compared with three other algorithms, and finally it is shown by means of experimental results that our algorithm with ordering of vectors need fewer comparisons and can find more pairs of vectors, which can build a block.

Abstract

A technique for representation of a system of completely specified Boolean functions in the form of a table similar to the Karnaugh map but more compact is described. Two methods for decomposition based on this form are suggested. Experimental results on benchmarks are given.

ABSTRACT

The characterization of faulty functions in combinational circuits under stuck-at faults is a relatively unexplored area of research in testing and diagnosis of digital circuits and systems. Existing results reported in this area are mostly concerned with restricted types of functions and circuits. This paper considers two-level combinational circuits realizing arbitrary functions and present many general results which dictate how a fault-free function can be transformed to a feasible faulty function under the stuck-at fault model. A new concept of fault-mapping graph (FMG) is introduced which captures the transitions from a fault-free to its faulty functions. Important properties of FMG are then explored which shed light on general fault behavior in irredundant combinational networks.

Abstract

The problem of handling really large systems is closely connected with decomposition methods widely used during the synthesis process. In this paper the model of parallel automaton is proposed. This model can be used on each level from the high level of the control algorithm to the low level of circuit structure for solving design and test tasks. The model of parallel automaton is very general. The restriction to special parallel automaton which fulfills certain introduced properties is helpful for practical application and calculation of test sequences.

Abstract

In this paper a procedure is shown to modify a finite state machine in such a way that an One- Shot-Coding of their states is possible. The characteristic of One-Shot-Codes for finite state machines result in some properties of the realized sequential networks. The main advantage is less power dissipation, better electromagnetic compatibility and very fast circuits because only one bit changes between all successive states.

Abstract

In [1] we showed that any Boolean function can be associated to a Cayley graph whose spectrum coincides with the Walsh spectrum of the function, and used this idea to inves- tigate the spectrum of certain special functions. In this paper we further exploit this idea by studying the class of functions whose associated Cayley graph is bipartite. We derive an algebraic characterization for these functions, analyze their circuit complexity and argue that some of them might be of interest for cryptographic applications.

Abstract

In this paper we present a hardware environment, i.e. a scalable multiprocessor system, that has been especially designed for application of Evolutionary Algorithms (EAs). In contrast to other approaches the hardware is adapted and optimized to this problem domain. We describe our multiprocessor system with respect to technical aspects and discuss the resulting options for EAs. We also give some ideas on the software framework, which is an essential part of the project. Finally as a case study the Travelling Salesman Problem is implemented to demonstrate the feasibility and performance of our approach.

Abstract

This paper describes the architecture of a heterogeneous, concurrent, and distributed system, which can be used for solving large computational problems. At first we introduce the system architecture and the techniques used to implement it. To estimate the performance of the distributed system we compute a boolean task parallely.