TU Bergakademie Freiberg | Fakultät für Mathematik und Informatik

Logo IFI 6th International Workshop Boolean Problems
Home Lehre Email

From Quantum Gates to Quantum Learning: recent research and open problems in quantum circuits

Marek A. Perkowski,
Portland Quantum Logic Group,
Department of Electrical Engineering and Computer Science,
Korea Advanced Institute of Science and Technology, and
Department of Electrical and Computer Engineering, Portland State University,


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).

"; if (eregi("Netscape",$browser)) $s=1; ?>

A Simple Model for Estimating Quantum Communication Channels

Tomoyuki ARAKI
Department of Electronics and Phtonic Systems Engineering,
Hiroshima Institute of Technology
E-mail: araki@ieee.org


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 ñ 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.

All non-linear reversible logic gates are r-universal

A. De Vos
Imec v.z.w., Vakgroep elektronika and informatiesystemen,
Universiteit Gent
L. Storme
Vakgroep zuivere wiskunde and computeralgebra,
Universiteit Gent


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.

An Approach to Synthesis of Multiple-Valued Reversible Logic Circuits

Pawel Kerntopf
Institute of Computer Science, Department of Electronics and Information
Technology, Warsaw University of Technology, Warsaw, Poland
email: P.Kerntopf@ii.pw.edu.pl


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.

Toffoli Templates with 8 Gates

Joshua R. Dick, Gerhard W. Dueck
Faculty of Computer Science
University of New Brunswick
Fredericton, New Brunswick
y0h7s@unb.ca, gdueck@unb.ca

Dmitri Maslov
Dept. of Computer Science
University of Victoria
Victoria, British Columbia


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.

Hardware Synthesis of UML-Models

Thomas Beierlein
Hochschule Mittweida
Labor Embedded Control

Dominik Fröhlich
TU Bergakademie Freiberg
Inst. of Computer Science

Bernd Steinbach
TU Bergakademie Freiberg
Inst. of Computer Science


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.


Elena Fomina, Alexander Sudnitson, and Roman Vasilyev
Department of Computer Engineering
Tallinn University of Technology
Raja Street, 12618 Tallinn, Estonia
Tel.: +372 620 2251, Fax: +372 620 2246, alsu@cc.ttu.ee


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.

On Deterministic Timed Alternating Finite Automata

Abdelaziz Fellah *
Dept. of Computer Science
University of Sharjah
Sharjah, UAE
e-mail: abd@sharjah.ac.ae


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.

*on leave, Dept. of Math. & Computer Science, University of Lethbridge, Lethbridge, Alberta, Canada. e-mail: fellah@cs.uleth.ca

Experimental Studies on Test Pattern Generation for BDD Circuits

Junhao Shi, Görschwin Fey, Rolf Drechsler
Institute of Computer Science
University of Bremen
28359 Bremen, Germany


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.

Efficient Reprogrammable Architecture for Boolean Functions and Cellular Automata

Harald Richter and Christian Siemers
Clausthal University of Technology, Institute for Computer Science
Julius-Albert-Str. 4, D-38678 Clausthal-Zellerfeld


An architecture was developed that under certain preconditions allows to efficiently implement any Boolean function f: Bm -> Bn, 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.

Remarks on Symmetric Binary and Multiple-Valued Logic Functions

Radomir S. Stankovic, Jaakko Astola1, Karen Egiazarian1
Dept. of Computer Science, Faculty of Electronics, 18000 Ni·s, Serbia
1Tampere International Center for Signal Processing
Tampere University of Technology, Tampere, Finland


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.

Minimization of Multi-Valued Functions in Decomposition of a System of Completely Specified Boolean Functions

Yuri Pottosin*, Eugeny Shestakov, Dmitry Sadnikov
United Institute of Informatics Problems of the NAS of Belarus
Surganov str., 220012 Minsk, Belarus; e-mail: pott@newman.bas-net.by


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.

* The author is supported by ISTC project B-986.

Relation between Boolean functions and spreading sequences for MC-CDMA transmission

Ekaterina Pogossova, Karen Egiazarian, Jaakko Astola
Tampere University of Technology,
Dept. of Information Technology, P.O. BOX 553, Tampere, Finland


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.

Foundations of Hierarchical SAT-Solving

Yakov Novikov
Konrad-Zuse-Zentrum für
Informationstechnik Berlin (ZIB)

Raik Brinkmann
Infineon Technologies AG


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.

Jordan Normal Form of Boolean Matrices

Wolf-Michael Wendler
Fachhochschule Braunschweig/Wolfenbüttel
University of Applied Sciences
Fachbereich Fahrzeug-, Produktions- und Verfahrenstechnik
Robert-Koch-Platz 10-14
38440 Wolfsburg
email: W-M.Wendler@FH-Wolfenbuettel.DE


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.

Binary Maxwellian Equations

Wolf-Michael Wendler
Fachhochschule Braunschweig/Wolfenbüttel
University of Applied Sciences
Fachbereich Fahrzeug-, Produktions- und Verfahrenstechnik
Robert-Koch-Platz 10-14
38440 Wolfsburg
email: W-M.Wendler@FH-Wolfenbuettel.DE


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.

Solving Inconsistent Systems of Linear Logical Equations

Arkadij Zakrevskij
United Institute of Informatics Problems of the National Academy of Sciences,
220012 Minsk, Belarus
e-mail: zakr@newman.bas-net.by


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.

Decomposition of Boolean Function Sets for Boolean Neural Networks

Roman Kohut, Bernd Steinbach
Freiberg University of Mining and Technology
Institute of Computer Science
D-09596 Freiberg, Germany
email:{kohut, steinb}@informatik.tu-freiberg.de


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.

Building Minimum ESOPs Through Redundancy Elimination

Grant R. Pogosyan
Mathematics and Information Science
International Christian University
Osawa 3-10-2, Mitaka, Tokyo, 181-8585 Japan

Ivo G. Rosenberg
Mathematics and Statistics
University of Montreal
C.P. 6128, Succ. Centreville, Montreal, Que, Canada H3C 3J7

Seiya Takada
School of Frontier Sciences
University of Tokyo
Kashiwanoha 5-1-5, Kashiwa, Chiba 277-8561, JAPAN


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.

Maitra Cascade Minimization*

Dimitrios Voudouris and George Papakonstantinou
National Technical University of Athens
email: dvoudour@cslab.ece.ntua.gr, papakon@cslab.ece.ntua.gr


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.

*This paper has been partially funded by the project Protagoras/NTUA

Two-Level Boolean Minimizer BOOM-II

Petr Fišer, Hana Kubátová
Department of Computer Science and Engineering
Czech Technical University
Karlovo nam. 13, 121 35 Prague 2
e-mail: fiserp@fel.cvut.cz, kubatova@fel.cvut.cz


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.

A Novel Method for Minimization of Boolean Functions using Gray Code and development of a Parallel Algorithm

S.Verma and K. Permar
Government Engineering College, Raipur 492 010 CG, India
email: vshrish9@yahoo.com and kdpermar@yahoo.com


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.

Easy testable combinational circuit design

A. Matrosova, S. Ostanin, V. Andreeva
Tomsk State University, Russia
{mau, ostanin, avv}@fpmk.tsu.ru


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.

Simple folding of array-based VLSI structures

Liudmila Cheremisinova
The United Institute of Informatics Problems of
National Academy of Sciences of Belarus
email: cld@newman.bas-net.by


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.

Generation of test case templates using the Boolean representation of software model

Christina Dorotska
Freiberg University of Mining and Technology, Institute of Computer Science,
D-09596 Freiberg, Germany,
e-mail: dorotska@informatik.tu-freiberg.de


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.

Strengthening Semantic-tree Method in evaluating QBFs

Mohammad GhasemZadeh, Volker Klotz and Christoph Meinel
FB-IV Informatik, University of Trier, Germany
{GhasemZadeh, klotz, meinel}@TI.Uni-Trier.DE


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.

Variable Ordering in SBDD Considering Function in Spectral Domain

Milena Stankovic
Faculty of Electronic,
University of Nis,
Beogradska 14, 18000 Nis, Serbia

Jaakko Astola, Karen Egiazarian
TICSP, Tampere
University of Technology,
P.O. Box 553, Tampere, Finland
jaakko.astola@tut.fi, karen@cs.tut.fi


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.

Structurally synthesized binary decision diagrams

A. Jutman, A. Peder, J. Raik, M. Tombak, R. Ubar
Tallinn University of Technology, University of Tartu


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.

Inhalt:/ Content: Institut für Informatik, TU Bergakademie Freiberg
Gestaltung/ Layout: Webmaster, 28. September 2004