Abstract

Both non-determinism and multi-level networks compactly characterize the flexibility allowed in implementing a circuit. A theory for representing and manipulating non-deterministic (ND) networks is introduced. The theory supports the usual network manipulations, done on deterministic binary networks, such as node minimization, elimination, decomposition etc. Three ways to interpret the behavior of an ND network are given. Operations performed on ND networks are analyzed for how they can change behavior under each interpretation. Some common network operations can increase different behaviors and thus might cause the network to violate its external specification. Several methods to correct this problem are proposed.

Abstract

The goal of the PQLG group is to develop complete methodologies, software tools and circuits for quantum logic. Our interests are mainly in logic synthesis for quantum circuits and quantum system design [10]. This paper proposes emulation of quantum circuits using standard reconfigurable FPGA technology and FPGA-based Evolvable Quantum Hardware. These are research areas not yet dealt with by other research groups.

Abstract

This paper introduces the concept of binary quantum decision trees and decision diagrams. While binary decision diagrams (BDDs) are efficient representation of large sparse matrices, in computer aided design (CAD) algorithms, their quantum counterparts are useful for quantum logic synthesis and analysis. Two new types of binary quantum decision trees and diagrams are introduced in this paper which allow for further possible optimizations in the design of quantum circuits, analogous to the classical case where various types of decision diagrams lead to various levels of optimizations in the synthesis of classical logic circuits. The new types of Decision Diagrams use the quantum computational basis states and the two-valued Einstein-Podolsky-Rosen (EPR) basis states. New Shannon and Margolus quantum evolution processes are also presented which are necessary for automated analysis and verification of netlists of quantum gates and for try-and-check methods such as evolutionary algorithms.

Abstract

We propose an automated synthesis of Reversible logic (RL) circuits using Darwinian and Lamarckian Genetic Algorithms (GA). Our designs are in a form of cascades of generalized gates which generalize factorized Exclusive-Or-Sum-of-Products (ESOP) circuits. GA can be used to explore the problem space of combinational functions and here it is used to evolve reversible logic circuits. We emphasize the role of problem encoding - a well-designed encoding leads to improved results. Our method with well-encoded circuits is compared to standard method on classical benchmarks in GA, and shows good results for synthesis of both random functions and benchmark functions with practical meaning, such as adders.

Abstract

In this paper the number of universal binary reversible logic gates with three inputs and three outputs is derived on the basis of conditions for weak completeness of Boolean functions. We extend this result to the case of reversible gates with four inputs and four outputs and show that almost all such gates are universal.

Abstract

This paper presents a tutorial review of relationships between the Boolean difference and the dyadic Gibbs derivative, considered as bit-level and word-level logic deriva-tives, and Ternary decision diagrams (TDDs). We point out that for a given function f, calculation of these logic derivatives equals to building up of the corresponding TDDs for f. Due to that, determination of particular values of logic derivatives reduces to the descending of the corresponding paths in the related bit-level and word-level TDDs.

Abstract

The problem of resolving restrictive logic equations occurs in the analysis and synthesis of digital systems. The implicit representation of logic functions is useful to describe the behavior of the systems, and the explicit unique representation is needed to describe the structure. The main aim of this paper is to show an easy way to find candidates of functions, resolving the given equation in a unique way, and to check that these functions are valid. In order to do this, the basic definitions of derivative operations are introduced, and, by using an inductive approach, suitable algorithms are suggested and evaluated. Quantitative results about the uniquely resolvable equations show finally some surprising results.

Abstract

The problem of solving large systems of logical equations with restricted number of variables in every of them has many applications. In this paper, two methods for its solution are regarded: the equation scanning method and the argument scanning method. The first method is implementing consecutive multiplication of orthogonal DNFs of the equations from a considered system and uses the search tree Te which levels are put in one to one correspondence with equations. The second method realizes a scanning procedure over arguments corresponding to levels of the search tree Ta . In both cases the run-time is roughly proportional to the size of the tree, i.e. to the number of its vertices. Two original algorithms were worked out that considerably reduce that number in trees Te and Ta . The program implementation and computer experiments confirm their high efficiency. They show also that the argument scanning method greatly surpasses in efficiency the other one.

Abstract

Modular decomposition is a thoroughly nvestigated topic in many areas such as switch- ing theory,reliability theory,game theory and graph theory.We propose an O (mn )- algorithm for the recognition of a modular set of a monotone Boolean function f with m prime mplicants and n variables.Using this result we show that the the computation of the modular closure of a set can be done n time O (mn 2 ).On the other hand,we prove that the recognition problem for general Boolean functions s coNP-complete.Moreover, we introduce the so called generalized Shannon decomposition of a Boolean functions as an e .cient tool for proving theorems on Boolean function decompositions.

Abstract

The article describes a new Boolean minimization and single-level partitioning method based on the BOOM minimizer. The minimization is performed with respect to various restrictions stated for the use of input variables. This enables us to effectively decompose the circuit into several components for which the numbers of inputs and outputs are explicitly specified. The method can thus be used to produce circuits with minimized load of the external inputs, circuits with balanced input load, or easily testable circuits. It can handle extremely large functions (up to thousands of input variables) in a very short time and its use is advantageous above all for highly unspecified functions, where the number of don't cares is large.

Abstract

In this paper we investigate the possibility of efficient minimization of number of vectors in lists representing Boolean functions. We use the representation of a function as an ordered list of ternary or Boolean vectors and propose a faster algorithm that is based on ordering of vectors. We sort the vectors in lists using the number of ones and dashes to create classes and subclasses. This model is used to speed up the optimization of orthogonal vector lists, an algorithm known as block change & block building. Unlike the algorithm used in XBOOLE system this algorithm uses additional knowledge from the ordered model and changes only blocks, that lead to new possibilities of block building. Our new algorithm is compared with algorithm, used in XBOOLE system, and finally it is shown by means of experimental results that our algorithm with ordering of vectors requires fewer comparisons to find a new block building possibility.

Abstract

A technique for decomposition of a Boolean function is suggested. The technique is similar to Shannon expansion and can be used for implementing Boolean functions by multiplexing. The suggested forms of decomposition are based on the concept of a cover of a ternary matrix. The same covers are applied in decomposition of systems of Boolean functions. The problems related to optimization of the suggested decomposition are considered.

Abstract

This paper deals with the methods of FSM internal states coding the with respect to the space and time characteristics of the final design.The aim is to obtain good placement of a designed FSM to the selected FPGA.It looks for such qualitative and quantitative properties of FSM benchmarks to choose good method for coding before performing all FOUNDATION algorithms because this process is time consuming.Our method of coding of the internal FSM states FEL-code based on partial,sequential and general decomposition of internal states is presented. time analysis of the designed circuit.

Abstract

The problem of design of logic control devices for distributed discrete-event systems is considered. A method for minimization of sequent automata realizing parallel control algorithms is suggested. Optimization of a sequent automaton is achieved by minimization of the code length, when transforming a parallel automaton into a sequent one, and simplifying sequents: removing redundant sequents and letters from them. The additional possibilities for optimization arise when providing the proper control for a specific object of the control, within the restricted domain.

Abstract

This paper surveys methods to represent logic functions by cascades. First, a design method for multi-rail cascades with redundant inputs is shown. It uses logic minimization of SOPs (sum-of- products expressions) or ESOPs (EXOR sum-of-products expressions) of multiple-valued inputs. Then, a design method for multi-rail cascades with irredundant inputs is shown. It uses functional decompositions using BDDs. In both cases, extensions to multiple-output functions are shown.

Abstract

Abstract

This paper considers he most complex functions for exclusive-or sum-of-products ex- pressions (ESOPs).Speci .cally,i derives the number of products required for represent- ing such functions by minimum ESOPs (MESOPs).First,an e .cien algorithm to derive a minimum ESOP for an arbitrary function of 6 variables is presen ed.Then,by using this algorithm an algorithm to derive class of all he most complex functions of 6 variables is shown.By using a knowledge about all he most complex 6-variable functions an upper bound on the number of products in minimum ESOPs and more e .cien algorithm to derive a minimal ESOP for an arbitrary function of 6 variables are presented.The main result is the following:7-variable functions with more han 29 products in MESOPs do not exist.

Abstract

BDDs are used in several fields as e.g. formal verification or synthesis. Minimizing the number of nodes in a BDD is a common technique, to reduce the memory needed to express a function. But recently applications like SAT-solving or synthesis have been shown to benefit from a small number of paths in a BDD. Here we present an algorithm and its implementation to carry out the minimization of a BDD with respect to the number of paths. After showing the existence of functions that can not be represented by a BDD that is minimal in the number of nodes and the number of paths at once, statistical experiments on the ISCAS89 benchmark set show the efficiency of the technique. In another set of experiments the minimization of numbers of paths is compared to that of the number of nodes.

Abstract

In this paper we sum up the research that was done during the last decade on the topic of Structurally Synthesized Binary Decision Diagrams (SSBDDs). We describe general properties of SSBDDs that make this model very efficient for circuit structure dependent methods and algorithms. In addition, we describe a deterministic test generation algorithm based on SSBDDs and four efficient simulation methods of different classes: logic simulation, multi-valued simulation, timing simulation, and fault simulation. We investigate and show the origins of their common advantages and draw conclusions, which hold for all the described algorithms. The analysis is made on the basis of experimental data acquired when applying these algorithms to ISCAS’85 benchmark circuits. The experiments unveil some new properties of these benchmarks, which we also present in our paper.

Abstract

Integrated circuits with a highly regular, repeated structure outperform IC's with complex logic interconnects, in transistor density, gate delay time, and testability. These advantages drive the search for highly regular structures. In [4] a triangular Davio lattice array has been introduced and its testability. A new structure, rectangular Davio lattice array is introduced here that has even more advantages for testability and nano-technology design.

Abstract

Integrated circuits with a highly regular, repeated structure outperform IC's with complex logic interconnects, in transistor density, gate delay time, and testability. They will be even more important for future technologies such as single electron transistors. These advantages drive the search for highly regular structures that can be used to replace complex logic. This paper studies synthesis and test of regular lattice structures built of Davio gates. Tools useful for analysis and synthesis of the triangular logic lattice structures are given. Finally, universal tests for the structures are developed.

Abstract

A new cellular array is introduced for synthesizing totally symmetric Boolean functions. The cellular structure is simple and universal – it uses only 3-input, 3-output AND-OR cells, and admits complete path-delay fault testability. The design is an improved version of the classical DSTL array reported earlier by Hurst [1], that eliminates path-delay untestability of the earlier design. The new design also admits a universal test set of length 2n that detects all single stuck-at faults, where n is the number of input variables. The proposed design is useful in view of the fact that two-level realizations of most of the symmetric functions are known to be path-delay untestable.

Abstract

This paper outlines formal verification in general and then introduces CVE’s equivalence checking tool gatecomp, an equivalence checker developed in the formal verification group at Infineon, Germany.The basic verification tasks are described and the advanced features of the tool are discussed. The application of gatecomp to large industrial examples is reported. This demonstrates the power of the tool for various verification tasks, like netlist vs netlist comparison, RTL vs. netlist comparison or RTL vs. RTL comparison.

Abstract

In this paper we present an approach to the development ofdynamically reconfigurable computer systems. The approach supports the application of object-oriented methodologies. This is facilitated by a supporting development environment. An important part of this environment is a compiler. This tool can bind system-level specifications automatically to eligible components of a target hardware to minimize the overall execution time. In the main part of this paper an algorithm is presented, that computes good quality mappings automatically in reasonable times. This is done by the utilization of information captured in use-cases and collaborations.

Abstract

We propose a method for local search of Boolean relations relating variables of a CNF formula. The method is to branch on small subsets of the set of CNF variables and in analyzing results of unit propagation. By taking into account variable value assignments deduced during the unit propagation procedure the method is able to justify any relation represented by a Boolean expression. The proposed technique is based on bitwise logical operations with ternary vectors. We implement a restricted version of the method used for unit clause derivation and equivalent-literal identification as a preprocessor engine for a SAT-solver. The experiments show that the proposed technique is useful for solving real-world instances of the formal verification domain.

Abstract

The paper presents a classi .cation of the classes of operator canonical forms of Boolean functions.These representations extend well-known exclusive-or sum-of-products expres- sions (ESOPs).We consider constructing methods and complexities of operator represen- tations.

Abstract

In this paper, we propose a regular layout geometry called 3 ×3 lattice * . The main difference of this geometry compared to the known 2 ×2 regular layout geometry is that it allows the cofactors on a level to propagate to three rather than two nodes on the lower level. This gives additional freedom to synthesize compact functional representations. We propose a SAT-based algorithm, which exploits this freedom to synthesize 3 ×3 lattice representations of completely specified Boolean functions. The experimental results show that the algorithm generates compact layouts in reasonable time.

Abstract

This paper deals with the representation of Boolean functions using artificial neural networks and points out three important results. First, using a polynomial as transfer function, a single neuron is able to represent a non-monotonous Boolean function. Second, the number of inputs in the neural network can be decreased if the binary values of the Boolean variables are encoded. This approach simplifies significantly the necessary number of neurons in the artificial neural network. Finally, an algorithm to compute the minimal number of neurons was developed. The lower bound, calculated by this algorithm, corresponds to a suggested structure of artificial neural networks. An example shows, how such a simple artificial neural network may represent a Boolean function.

Abstract

A pure algebraic approach to linear automata theory is presented. Emphasis is put on the investigation of periodic inputs and different formulations of the theory.

Abstract

Based on a pure algebraic approach linear autonomous systems are investigated. Especially the transformational behavior of the structure and the states of the corres- ponding state graphs is treated.

Abstract

Relation decomposition has been used for FPGA mapping, layout optimization, and data mining. Decision trees are very popular in data mining and robotics. We present relation decomposition as a new general-purpose machine learning method which generalizes the methods of inducing decision trees, decision diagrams and other structures. Relation decomposition can be used in robotics also in place of classical learning methods such as Reinforcement Learning or Artificial Neural Networks. This paper presents an approach to imitation learning based on decomposition. A Head/Hand robot learns simple behaviors using features extracted from computer vision, speech recognition and sensors.