Abstract

The paper is an overview of basic quantum circuits for researchers specializing in logic design. After brief intuitive review of quantum circuits, we discuss the issues in synthesis and test problems, pointing to the similarities with classical digital circuits. Finally, Quantum Computational Intelligence is mentioned as a new area that uses quantum ideas in the framework of Computational Intelligence, especially machine learning. The goal of the paper is to demonstrate that with very limited introduction to quantum fundamentals, the logic design specialists can use their knowledge and skills to become productive researchers in the new quantum-related area of computer engineering that we propose to call Quantum Design Automation (QDA).

Abstract

It is well known that quantum mechanics is explained in quantum logic and orthomodular lattices. However, these logic and algebraic structure have not always been succeeded in explaining behavior of quantum information systems. A qubit |ψñ = α|0ñ + β|1ñ in quantum information systems is extension of classical concept ”bit”, where |0ñ and |1ñ are basis of a two dimensional quantum system with two orthogonal states, α and β are probabilistic amplitudes in C. Then, one qubit can have infinite number of values in contrast with classical one bit. In this paper, to analyze various infinite number of quantum states, we establish a discrete algebraic structure as a model of qubit space, which is isomorphic to Kleene algebra 3 = < {0,1/2,1},~,/\,\/ >. Furthermore, we propose weak Kleenean non-additive measures and weak Kleene-Choquet integrals. Then, we show that we can analyze quantum communication channels effectively by the proposed framework using a quantum cryptosystem as an example.

Abstract

Reversible logic plays a fundamental role both in low-power electronics and in quan- tum computing. Thus it is important to know which reversible logic gates can be used as building block for the implementation of an arbitrary boolean function and which cannot.

Abstract

Reversible logic has applications in many fields, including quantum computing. Recently, physical realizations of quantum MVL gates in ion trap technology have been reported [26] and various ternary quantum gates have been experimentally built [2]. This paper proposes an approach to synthesis of reversible MVL circuits using a complexity measure based on shared multiple-valued decision diagrams with cyclic edge negations. It is a generalization of a method we have recently developed for the binary reversible logic synthesis that showed promising results in comparison with the known approaches. The approach can be used with arbitrary libraries of reversible MVL gates and arbitrary cost functions.

Abstract

Reversible logic maps each input pattern to a unique output pattern. In order to realize these funcToffoli Templates with 8 Gatestions reversible gates, such as Toffoli, are brought together in a cascade to form a reversible circuit. One effective method for simplifying reversible circuits is accomplished via template matching. The basis for a template is a series of gates that realizes the identity function. Template matching deals with matching a set of gates in the circuit with those of a template and replacing the matching gates with the remaining gates of the template in reverse order if more than half the template has been matched. There currently exist templates of up to size 7. In order for template matching to be more effective, larger templates needed. However, discovering such templates is not a simple task; the search requires an enormous amount of processing power. This paper deals with the design and implementation of a template finding program on a parallel computer which makes the template finding process be a feasible task. It also discusses the templates found after running the program.

Abstract

The automated synthesis of application specific co-processors has been a complex and demanding problem. To handle the inherent informational and architectural complexity of this problem novel development approaches supported by powerful tools are taken. In this paper we present an approach that is based on UML and hardware/software co-design. We will show how Boolean problem solvers can be modeled with this language and discuss the synthesis of hardware from such models. Also we show important problems we recognized with the current approaches that should be investigated in the future.

Abstract

The results presented in this paper are intermediate of work on the problem of encoding (or state assignment) of network of Finite State Machines (FSMs). Partitioning or decomposition requires to realization of synthesis of FSM in two stages. Initial stage is solving of problem of choosing of partition’s system. This stage corresponds to primary rough phase of FSM decomposition. Next stage is coding of given network of FSMs. Following transformations of given network of FSMs is more delicate optimization.
In current report we devote our investigation to development of an algorithm of FSMs network coding with minimal code length. We present new encoding strategy based on the measure of information relationship. An illustrative example allows monitoring all steps of the algorithm. Experiments on the circuits of MCNC benchmarks present efficiency of the proposed approach in comparison with standard methods of FSM encoding.

Abstract

Timed alternating finite automata (TAFA), a natural generalization of timed finite automata (TFA), are synchronous and powerful models for real-time constraint computations and embedded systems We introduce deterministic timed alternating finite automata (DTAFA), a class of timed alternating finite automata, extended with a finite set of re stricted and mutually exclusive real-valued clocks on events which trigger the state transi tions of the automaton. We show how to transform deterministic n-state TFA into log n- state DTAFA and state some language properties between TFA, DTAFA, and deterministic TFA. We then show that, unlike TFA and TAFA, DTAFA are closed under all Boolean operations, including the complementation. In addition, we present an equational language representation for DTAFA which parallels that of timed languages for TAFA.
keywords: Timed automata, timed alternating finite automata, timed language equations.

Abstract

Synthesis for Testability has become a major issue as the size and complexity of circuits and systems is rapidly increasing. Due to their good testability design styles based on multiplexors have become very popular. In particular a Binary Decision Diagram (BDD) can directly be mapped to a BDD circuit using multiplexors. BDD circuits can be modified to retrieve 100% testable circuits under the stuck-at fault model at a low cost. In this paper Automatic Test Pattern Generation (ATPG) for BDD circuits is studied. BDD circuits are compared to conventionally optimized circuits. The number of test patterns are compared for the different methods. For the benchmark circuits the number of test patterns needed is comparable to the relative sizes of the circuits. Even a gain up to a factor of four occurred.

Abstract

An architecture was developed that under certain preconditions allows to efficiently implement any Boolean function f: B^m -> Bⁿ, B={0,1} by means of a reprogrammable CAM/RAM array. It proved to be a balanced combination of two known approaches for implementing Boolean functions, i.e. look-table in RAM, and fixed array of AND and OR gates according to the disjunctive normal form of f.

Abstract

This papers extends definitions of elementary symmetric functions for binary valued switching functions to multiple-valued (MV) functions. It is shown that under a suitable selection of the underlined algebraic structure, the basic results in reduced polynomial rep- resentations for symmetric binary-valued functions can be extended to MV functions. The method of defining elementary symmetric functions can be used to create many symmetric MV benchmark functions as combinations of elementary symmetric MV functions. Since the same method can be applied in different algebraic structures, various benchmark functions can be defined.

Abstract

A method for decomposition of a system of completely specified Boolean functions using minimization of multi-valued functions is considered. To minimize a multi-valued function the Espresso-MV program is used. Experimental results on benchmarks are given.

Abstract

In this paper, we address the problem of spreading sequence design for multicarrier CDMA transmission. With the help of Boolean and multiple-valued logic theory, we derive a number of orthogonal matrices, with the rows well suitable for multicarrier CDMA spreading n terms of peak-to-average power ratio of the resulting transmitted signal.

Abstract

The theory of hierarchical Boolean satisfiability (SAT) solving proposed in this paper is based on a strict axiomatic system and introduces a new important notion of implicativity. The theory makes evident that increasing implicativity is the core of SAT-solving. We provide a theoretical basis for increasing the implicativity of a given SAT instance and for organizing SAT-solving in a hierarchical way. The theory opens a new domain of research: SAT-model construction. Now quite different mathematical models can be used within practical SAT-solvers. The theory covers many advanced techniques such as circuit-oriented SAT-solving, mixed BDD/CNF SAT-solving, merging gates, using pseudo-Boolean constraints, using state machines for representation of Boolean functions, arithmetic reasoning, and managing don’t cares. We believe that hierarchical SAT-solving is a cardinal direction of research in practical SAT-solving.

Abstract

The Jordan normal form of an arbitrary Boolean square matrix is derived and applied to the analysis of the behavior of the solution of the linear state space equations. The theory is generalized to all finite fields of prime characteristic.

Abstract

A finite field formulation of the Maxwellian equations is presented. The derivation of wave equations as well as solutions are discussed. By means of a Lorentz-like binary transformation a covariant formulation of these equations is given. The transformational behavior of the electromagnetic field tensor and the energy-momentum tensor are discussed.

Abstract

Inconsistent systems of linear logical equations are considered, the number of equations in which exceeds the number of variables. The task of finding of a solution satisfying the maximum number of the equations is put. A combinatorial randomized algorithm to solve this task is offered, the results of its computer implementation are adduced.

Abstract

This paper presents a new type of neuron, called Boolean neuron. We suggest algorithms for decomposition of Boolean functions sets based on Boolean neural networks that include only Boolean neurons. The advantages of these neural networks consist in the reduction of memory space and computation time in comparison to the representation of Boolean functions by usual neural networks. The Boolean neural network can be mapped to a FPGA so that our new approach substitutes classical design methods of these circuits. We show as example the AND-decomposition of a Boolean function set into unique basic functions and their mapping to the general Boolean neural network.

Abstract

Exclusive Sum of Products or ESOP expressions for Boolean functions have been studied for more than a decade. The interest towards such formulae is triggered by the fact that the choice of AND, EXOR, NOT as generators for formal expressions is proven to be more effcient in terms of formula complexity compared to the classical AND-OR-NOT expressions. We present an algorithm which nds an exact minimum ESOP for a given Boolean function, with number of literals as the measure of optimality. This algorithm is based on a technique of redundant term elimination in the process of selecting a candidate combination of minterms to match with the given function. Since the problem of exact minimization has an over-polynomial complexity, such algo- rithms are bound to fail halting within a feasible time for suffciently large functions. Our gaol was to achieve a faster performance than that of known algorithms, and to be able to construct minimum ESOPs for more functions in practically workable computation time.

Abstract

In this paper an effcient algorithm for the synthesis and minimization of CA (cellular array architectures) is proposed. Our algorithm starts from a completely-specified switching function and produces reversible wave cascades with an effort to minimize the number of the produced chains (cascades). This kind of topology can easily be mapped to reversible cir- cuits (generalized Toffoli gates) as it is presented in the related bibliography. The proposed algorithm uses function decomposition and ETDDs (EXOR ternary decision diagrams). The experimental results that are obtained (they are presented at the end of this work) prove the effciency of the proposed method.

Abstract

We propose a novel two-level Boolean minimizer coming in succession to our previously developed minimizer BOOM, so we have named it BOOM-II. It is a combination of two minimizers, namely BOOM and FC-Min. Each of these two methods has its own area where it is most efficiently applicable. We have combined these two methods together to be able to solve all kinds of problems efficiently, independently on their size or nature. The tool is very scalable in terms of the required runtime and/or the quality of the solution. It is applicable to functions with an extremely large number of both input and output variables.

Abstract

The present paper proposes a new method for two level minimization of Boolean functions, which is not only a versatile and elegant paper-and-pencil method but also the one for which a parallel minimization algorithm can be readily developed. A novel minterm numbering scheme based on Gray code is proposed exploiting the Gray code’s unit distance and reflection properties for obtaining adjacency among the given minterms in paper-and-pencil method as well as to develop a parallel algorithm for generating prime implicants and subsequent minimization of the given Boolean function. The proposed paper-and-pencil method and the parallel algorithm are implemented on a few examples having don’t care terms.

Abstract

It is found out that a set of test patterns for all multiple stick-at faults at the gates poles of a combinational circuit designed coincides with a set of test patterns for all single stuck-at faults of irredundant sums of prime implicants describing the combinational circuit behavior. The combinational circuits is designed with a multi level synthesis method based on division of sums of products and a factorized two level synthesis method applied to kernels and co-kernels. The method of finding such setoff test patterns is discussed.

Abstract

The problem under consideration is to reduce the area of the layout of regular VLSI structures by means of their folding. Some results of cutting down exhaustive computational efforts on the search for the optimal regular structure folding have been described. An efficient method for onedimensional unconstrained simple folding is presented. It is formulated on a Boolean matrix depicting the compatibility relation among all pairs of columns of the array-based structure.

Abstract

This paper is devoted to the problem of testing of object oriented software based on the using of test cases. The software is described with a Unified Modeling Language (UML) and will be transferred by the XML to the test tool. For the internal representation of the software the Boolean model is used, which maps all correct values by a one and all wrong values by a zero. Value that influences the test result and can be both correct and wrong, is mapped by a dash (don’t-care). The test cases will be generated by replacing of don’t-cares by ones and zeros.

Abstract

The semantic-tree approach is the most robust method for deciding QBFs. This method is very similar to the DPLL algorithm for evaluating SAT instances. In this paper we show how memorization can be embedded to this method to get better results. In other words we present an algorithm for evaluating QBFs, which is based on an adopted version of semantic-tree method and ZDDs (which are variants of BDDs). The capability of ZDDs in storing sets of subsets efficiently, enabled us to store the formula very compact and led us to implement the search algorithm in such a way that we could store and reuse the results of all already solved subformulas. We call this idea: ’strengthening semantic-tree method by memorization’. This idea along some other techniques, enabled our algorithm to solve a bunch of the standard QBF benchmark problems faster than the best existing QBF solvers. Keywords: DPLL, Zero-Suppressed Binary Decision Diagram (ZDD), Quantified Boolean Formulae (QBF), Satisfiability, QSAT, Memorization, Dynamic Programming.

Abstract

Determination of a suitable order of variables is an important task in representation of switching functions by Binary Decision Diagrams (BDDs). This paper presents a deterministic procedure for determination of order of variables which produces Shared Binary Decision Diagrams (SBDDs) of the reduced complexity expressed in the number of non-terminal nodes count. Experimental results show that SBDDs produced by this procedure have equal or comparable number of nodes as SBDDs for the optimal order of variables.

Abstract

Current paper presents a special case of BDDs called Structurally Synthesized BDDs. Different from BDDs, which are generated by Shannon’s expansion, SSBDDs are generated by a superposition procedure. The paper investigates the mathematical properties of such kind of BDDs, in order to separate the properties of the underlying ”skeleton” graphs from the properties of SSBDDs. SSBDD representations for both, Boolean formulae and digital logic circuits are explained. Finally, usefulness of the model is shown in the application of fault modeling in digital test.