Approaches to the specification, synthesis and simulations of reversible and quantum circuits are significantly different from those used in conventional logic design. Many techniques require the construction and manipulation of very large matrices. The first part of this paper is tutorial in nature. It reviews a selection of decision diagram techniques and how they have been applied to matrix representation for reversible and quantum circuits. The second part of the paper shows how decision diagrams can be used to check the equivalence of two circuits regardless of the number of ancillary inputs and garbage outputs using a new technique employing simple matrix operations. The presentation here addresses reversible circuits with binary inputs and outputs, but it is readily extended to the multiple-valued case, and to general quantum circuits. While this method has been developed using one particular type of decision diagram, QMDD, it should be straightforward to implement it using other decision diagram structures developed for quantum gates and circuits. This paper is intended primarily as an introduction to the area. It is not intended to cover all decision diagram techniques that have been developed for reversible and quantum circuits. Also, it does not address the issue of how decision diagrams may be used in the synthesis of circuits.
Synthesis of reversible logic has become a very important research area. In recent years several algorithms – heuristic as well as exact ones – have been introduced in this area. Typically, they use the specification of a reversible function in terms of a truth table as input. Here, the position of the outputs are fixed. However, in general it is irrelevant, how the respective outputs are ordered. Thus, a synthesis methodology is proposed that determines for a given reversible function an equivalent circuit realization modulo output permutation. More precisely, the result of the synthesis process is a circuit realization whose output functions have been permuted in comparison to the original specification and the respective permutation vector. We show that this synthesis methodology may lead to significant smaller realizations. We apply Synthesis with Output Permutation (SWOP) to both, an exact and a heuristic synthesis algorithm. As our experiments show using the new synthesis paradigm leads to multiple control Toffoli networks that are smaller than the currently best known realizations.
We investigate the structure of reversible circuits. Our experimental data reveal some interesting characteristics of circuits built from NOT, CNOT and Toffoli gates, namely new decomposition types of reversible Boolean functions and existence of many NOT gates in some optimal reversible three-input three-output circuits.
If we like to make an arbitrary permutation of a large number (say n) objects, where n is a non-prime number (n = pq, with both p and q integer), it is advantageous to arrange the objects in a rectangular p×q matrix. Then the permutation can be performed in three steps: first one applies a permutation where all objects remain in the same row, then one applies a permutation where all objects remain in the same column, and finally one applies a second permutation where all objects remain in the same row. In telecommunication, this remarkable theorem is the basis of so-called Clos networks, where w communication wires have to be permuted, according to one of the w! possible permutations. In binary digital communication, w wires transport one of the 2w possible messages. Reversible computing consists of applying a permutation, not to the w wires but to the 2w possible messages. The Clos approach allows us to build reversible binary computers very efficiently. The approach is somewhat less efficient for multiple-valued reversible logic and, unfortunately, is not applicable at all for arbitrary quantum circuits.
In several previous papers and particularly in [3] we presented the use of logic equations and their solution using ternary vectors and set-theoretic considerations as well as binary codings and bit-parallel vector operations. In this paper we introduce a new and elegant model for the game of Sudoku that uses the same approach and solves this problem without any search always finding all solutions (including no solutions or several solutions). It can also be extended to larger Sudokus and to a whole class of similar discrete problems, such as Queens’ problems on the chessboard, graph-coloring problems etc. Disadvantages of known SAT approaches for such problems were overcome by our new method.
The problem under discussion is to check whether the given combinational circuit implements a system of incompletely specified Boolean functions. We present a novel approach to verification for such a case. SAT-based procedure is discussed that allows testing whether the given circuit implements a multiple-output cube contained in the specification of a system of incompletely specified Boolean functions given. The procedure has been expanded to test several (or all) multiple-output cubes simultaneously within the only SAT session. Dealing with several multiple output cubes within the only model-checking session allows speedup of verification process.
A novel universal QCA gate is introduced and called a boundary comparator. This gate implements a Boolean function in its boundary form, as a superposition of elementary boundary functions or as threshold functions having weights equal to integer powers of 2. An array of the boundary comparators is called Comparator based Programmable Array (CPA) and forms a homogeneous regular structure programmable for implementing any logic function. The paper describes a) presenting a Boolean function in its boundary form; b) structure of the boundary comparator, and c) structure of the CPA. The proposed CPA is testable, reparable and debuggable.
The purpose of the paper is to explore the possibility of applying the language PRALU, proposed for description of parallel logical control algorithms and rooted in the Petri net formalism for design and modelling of real-time multi-agent systems. The methodology of programming agents in PRALU is offered that is based on two-block architecture: the block of synchronization and the functional block.
Complex numbers in finite fields are reinvestigated under the generalizing viewpoints of algebraic field extensions as well as the number theoretical theory of rests. Distinction is made between even and odd fields.
Conic sections and spheres are investigated in finite fields. Emphasis is put on the defi- nition of non-degenerate conics and their dual behaviour with respect to all primes and prime powers. Graphs are presented in particular for circles, ellipses and hyperbolas and and simple spheres. The results are compared to those in characteristic 0.
A new tool for manipulation of logic functions is presented in this paper. The source functions
are described by an algebraic expression (or a set of expressions), in a VHDL-like style, by a truth
table (PLA) or as a CNF form. In particular, any multilevel network of logic gates can be used as a
source for the tool. The tool is capable of performing basic Boolean operations on the source
functions, like negating the function, performing AND, OR, XOR operations, etc., between two or
more functions. Then, the tool is able to mutually transform the CNF and DNF function
representations, which also enables to solve a satisfiability (SAT) problem as a byproduct. Last, but
not least, the tool performs a function collapsing, i.e., it transforms a multi-level Boolean network
into its two-level description (truth table).
Some Boolean operations, like computing a negation of a function in DNF, are rather time and
memory consuming. For this reason a special structure called a “ternary tree” is introduced. The
ternary tree is used to store the function’s terms and to perform a basic minimization of the function
representation. Basic principles of the ternary tree representation of a function and its minimization
principles are described in this paper too.
The proposed tool was tested on several different problems (minimization of a function, SAT
solving, collapsing) and compared with state-of-the-art tools.
This paper is a tutorial review of some former and recent work in classification of switching functions. Considered are different approaches to the classification and discussed features of resulting classification methods.
The Specialized Normal Form (SNF) is a unique (canonical) representation of Exclusive Sum-Of-Products (ESOP) expressions of a Boolean function. Hence this expansion of a Boolean function abstracts the form of the given ESOP expression and directs the focus to the properties of the function itself. This paper shows, how information about the given function can be detected from the shape of the SNF. In detail we explore the complexity of a Boolean function and try to detect the cubes appearing in the exact minimal ESOPs.
The use of decision diagrams (DD) for the computation and representation of binary function
spectra has been well studied [2,3,5]. Computations and representation of spectra for multiplevalued
logic (MVL) functions have also been considered [6]. For binary functions, this approach
can be implemented using one of a number of the highly efficient publicly available binary
decision diagram (BDD) packages, e.g. CUDD [13]. Work with MVL functions requires a package
suited to the MVL case, e.g. [7,8].
Quantum multiple-valued decision diagrams (QMDD) were introduced in [9-12] as a means to
represent and manipulate the matrices required for binary or multiple-valued reversible and
quantum gates and circuits. In this paper, we show how QMDD can also be applied to the
computation of spectral transformations of binary and multiple-valued functions. A major
motivation for this work is that it introduces an approach to the spectral analysis of reversible and
quantum circuits in a representation that is applicable to simulation and synthesis of such circuits.
It is also of interest in that it is a consistent approach for a variety of transformations of binary and
multiple-valued functions.
Former work developed zero-suppressed Multi-terminal BDDs (ZMTBDDs) for the effi- cient generation and representation of stochastic transition rate matrices underlying high- level (Markov model) descriptions of systems [5, 4]. For manipulating ZMTBDDs, possibly defined over different sets of function variables, but allocated in a shared environment as provided by BDD-packages such as CUDD [15] the authors of [4] and [7] developed the concept of partially shared ZMTBDDs. This paper recapitulates important aspects of this concept and presents run-time data as obtained from the analysis of benchmarking models in the context of symbolic, performance analysis of systems.
We present a BDD-based Computer Algebra system for relation algebra, called Rel- View. After a short introduction to relation algebra and the system, we describe how both can be applied in formal algorithm development. We also exhibit the applications by presenting some typical examples.
A new data structure called Split Multi-terminal Binary Decision Diagrams (Split MTBDD) is introduced for representing Multi–Output logic Functions (MOF). Split MTBDDs are efficient for some functions where conventional BDDs are not. A Split MTBDD comprises interconnected MTBDD components, each associated with a “dichotomic fragment”. The “dichotomy” reflects cognitive patterns introduced by the designer of a MOF specification. The paper describes a method of transforming an arbitrary MOF into a corresponding Split MTBDD. Experimental results indicate that Split MTBDDs are more compact than conventional MTBDDs for many benchmarks. Criteria for prediction of the Split MTBDD compactness are formulated and justified.
We give a heuristic for Disjoint Sum-of-Products (DSOP) minimization of a Boolean function f, based on a new criterion for product selection. Starting from a Sum-of-Products (SOP) S of f, i.e., a set of cubes covering the 1’s of f, we assign a weight w(p) to each product (cube) p in S, where w(p) depends on the intersection of p with the other cubes of S. We assign higher weight to the cubes that, if selected in DSOP, would generate a higher fragmentation of the other cubes. Disjoint cubes are then selected for increasing value of w and for decreasing size, recomputing the SOP on the residual function at different possible stages as a trade-off between quality of result and computational time. A set of experiments conducted on major benchmark functions show that our method, with all its variants, always generates better results than the ones of previous heuristics including one based on a BDD representation of f.
A new method of minimization of Boolean functions of many variables is offered, based on preliminary building up a Boolean matrix of neighborhood in the characteristic set M 1. It includes iterative procedure of finding prime implicants of higher ranks with consequent rank reduction. Its program implementation allows finding good DNF for random Boolean functions of up to 24 variables. A vast computer experiment was fulfilled for estimation of the program efficiency and the area of its application.
A method to find hard logic synthesis examples with known upper bound is presented. The circuits can be small and yet difficult to synthesize. Any area-related metric can be used in finding the circuits and testing synthesis tools. The hardness of the examples is robust with respect to the metric used and to minor alterations in the circuit.
Basic definitions and theorems of differential and integral calculus in finite fields for realvalued functions of one indeterminate are presented and compared to those in characteristic 0. The derivatives of elementary functions are derived and discussed. An outlook to functions of n indeterminates is given.
A Boolean description of linear block coding techniques may be merged into actually implementable hardware, operating fully in parallel, i.e. within one clock cycle, without iterative or recursive components. The scheme is suitable for any generator matrix complexity, and is adaptable also to the special case of cyclic redundancy check (CRC) polynomial coding. For the much larger class of linear block coding, a novel scheme of error sorting is used to establish suitable generator matrices with specific error detecting patterns to reduce or suitably tailor the number (or classes) of detectable errors, yielding error detectability at the theoretical Hamming limit.
The genetic algorithms of test generation and fault simulation for digital circuits are considered. The main modes of genetic algorithm parallelization for test generation and simulation are represented - “worker-farmer”, “island model”. The program implementation and computer experiments of proposed methods are discussed.
Elementary algebraic and transcendental functions as well as their corresponding inverse functions are defined in finite fields for all primes and prime powers. These functions are investigated with respect to their geometrical and analytical behaviour.
Four valued bit code (4VBC) maps multi-valued logic into the bit pairs of 00, 10, 01, and 11 to mean respectively Contradiction, False, True, and Tautology. The two dimensional form of bit pairs is found to obey the law of the excluded middle. The four valued logic of Belnap-Dunn is shown to be inconsistent with 4VBC. Tables of connectives and truth conditions are assembled to reveal the first elementary segment of 4VBC to be able to express propositional, modal, and deontic logics and the second segment temporal logic. A new table method for proving theorems and demonstrating axioms is introduced.