Combinatorial Methods of Solving Boolean Problems
Arkadij Zakrevskij
United
of the
email:zakr@newman.bas-net.by
Abstract:
A big variety of Boolean problems which arise under logical design of discrete devices can be reduced to different combinatorial tasks, usually hard ones. Practically efficient means for solving them have been suggested, including procedures of search tree reduction, randomized parallelization of computations, recognizing good solutions between numerous elements of the search space. Application of these means to some known problems is demonstrated in the paper. There are regarded original methods of pattern recognition, solving large systems of Boolean equations, linear ones in their number, decomposition of Boolean functions. Experimental investigations prove their high efficiency.
Fourier Representations of Switching Functions for Circuit Design
Radomir
S. Stanković
Dept. of Computer Science
Faculty of Electronics
18000 Niš
Jaakko Astola
FIN-33101
Abstract:
The paper discusses circuit design from Fourier representations of switching functions. Optimization with respect to the complexity of the network, the calculation time and the memory requirements, is performed by varying the domain group structure of the switching functions.
Adjacency Graph of the SNF as Source of Information
Bernd Steinbach
D-09596 Freiberg, Germany
email:steinb@informatik.tu-freiberg.de
Abstract:
The Specialized Normal Form (SNF) is a unique (canonical) representation of Exclusive Sum-Of-Products (ESOP) expressions of a Boolean function. The adjacency graph of the SNF takes the cubes of the SNF as labels of the vertices and connects such vertices by an edge which differ exactly in one variable of the associated cubes. It is known that each adjacency graph of the SNF of a Boolean function f : Bk -> B is a k-regular graph. This paper shows, how differences between the vertices of this graph can be detected in order to find cubes from exact minimal ESOPs.
Boolean Representation of Relationships Between Elements of
a Software Model
Christina Dorotska, Bernd Steinbach
D-09596
Freiberg, Germany
e-mail: {dorotska,
steinb}@informatik.tu-freiberg.de
Abstract:
In this paper we show an approach to represent a software
model and its relationships with Boolean functions. The software model is
described with UML (Unified Modeling Language). The information about
relationships inside of this model is expressed both by the class diagram and by
OCL (Object Constraint Language) expressions. A BVL (Binary Vector List) is
used to represent a Boolean function. The Boolean model of the software is used
to generate test templates of the software. We will show that applying of a BVL
for compact storage of all relationships information saves time to create the
Boolean model and to generate test templates.
Abstract complex Numbers and 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
Abstract:
Abstract complex numbers are constructed on finite fields of prime characteristic p. Their existence and properties are investigated. It is shown, that these numbers correspond to a rearrangement of the power and polynomial representation. In this line complex vectors and matrices are introduced and discussed, where emphasis is put on their relevance with respect to quantum mechanics in finite fields.
A Multi-Processor Approach to SAT-Problems
Christian Posthoff
The University of The
Trinidad & Tobago
email:cposthoff@fsa.uwi.tt
Bernd Steinbach
D-09596 Freiberg, Germany
email:steinb@informatik.tu-freiberg.de
Abstract:
The 3-SAT problem is one of the most important and interesting NP-complete problems with many applications in different areas. In several previous papers and in [5] we showed the use of ternary vectors and set-theoretic considerations as well as binary codings and bit-parallel vector operations in order to solve this problem. After the parallelism of the solution process has been established on the register level, i.e. related to the existing hardware, this article shows the extension to the use of several processors working in parallel. On the basis of the previous considerations this extension is easy to understand. Simultaneously it should be used as an inspiration to implement such a multi-processor solution and to apply it to many different problems.
Reusing Learned Information in SAT-based ATPG
Görschwin Fey, Tim Warode, Rolf Drechsler
{fey,drechsle}@informatik.uni-bremen.de
Abstract:
The robustness of engines for ATPG has to be improved to cope with the growing size of circuits. Recently, SAT-based ATPG approaches have been shown to be very robust even on large industrial circuits. Here, we propose techniques to further improve the efficiency by embedding learning techniques in a SAT-based ATPG engine. We provide a heuristic to apply incremental SAT when enumerating faults and a technique to apply circuit-based learning where incremental SAT is not applicable. A proof of correctness is given for circuit-based learning. Experimental results on large benchmarks show the efficiency of the approach.
XSLT based method for automatic generation of a graphical
representation of a decision diagram represented using XML
Stanislav Stanković, Jaakko Astola
email: stanislav.stankovic@tut.fi,
jaakko.astola@tut.fi
Abstract:
In our previous work we have introduced the concept of an XML:DD framework. As a .exible and robust platform for representation of various classes of Decision Diagrams for switching functions. It is meant to provide an easy exchange of data between these applications by means of one standardized meta-format that can be easily converted to different application speci.c formats. In this paper, we go one step further and introduce an extension to the basic system capable of automatic production of graphic representation of a decision diagram. The purpose of this paper is to demonstrate the .exibility of the proposed framework on an example of conversion of a decision diagram represented in XML form to 2D vector graphic format.
Reduction of the Number of Paths in Binary Decision
Diagrams by Linear Transformation of Variables
Osnat Keren
Bar Ilan University,
Israel
kereno@macs.biu.ac.il
Ilya Levin,
ilia1@post.tau.ac.il
Radomir S. Stankovic
rstankovic@bankerinter.net
Abstract:
The paper deals with the problem of counting and minimizing the number of paths in Binary Decision Diagrams. The suggested approach uses the linear transform of initial variables and is based on a newly introduced weighted autocorrelation function. It is shown that the total number of paths in BDD is the sum of values of a weighted autocorrelation function. The efficiency of the proposed technique is illustrated on a number of benchmarks.
Group theory for reversible logic
Alexis De Vos and Yvan Van Rentergem
Imec v.z.w., Vakgroep
elektronika en informatiesystemen
Universiteit Gent
Abstract:
Reversible logic circuits of logic width w form a group R. Synthesis of an arbitrary reversible circuits benifits from so-called double cosets X \ R / Y, where X and Y are appropriate subgroups of R. We choose X equal either to the subgroup Y, or to the trivial subgroup 1 consisting of merely the identity gate, or to an intermediate choice. For small width w, the last choice turns out to be the best. For large width w, however, the second choice is the cheapest one. It leads to a hardware cost proportional to merely w22w.
Elements of Quantum Mechanics in Finite Fields
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
Abstract:
Elementary quantum mechanics is formulated on all finite fields of prime characteristic p. Departing from an axiomatic approach we derive the classical Poisson-brackets, the commutator relations and the uncertainty relations. The invariance properties of the Schrödinger equation are discussed as well as the Heisenberg picture. The important example of the harmonic oscillator is investigated.
Output Grouping Method Based on a Similarity of Boolean Functions
Petr Fišer, Pavel Kubalík, Hana Kubátová
Department of Computer Science and Engineering
Karlovo nám. 13, 121 35
e-mail: fiserp@fel.cvut.cz, xkubalik@fel.cvut.cz,
kubatova@fel.cvut.cz
Abstract:
A method allowing us to efficiently group the multi-output Boolean function outputs is presented in this paper. Some kind of decomposition is usually involved in the logic synthesis process. Here the circuit has to be repeatedly divided into subcircuits, until these subcircuits become technological library elements or technology-dependent components, in general. Our output-grouping method can be used to compute which functions of a set of Boolean functions could share most of logic. This idea can be exploited in single-level decomposition, where a two-level multi-output circuit is divided into several stand-alone blocks, while retaining their two-level nature. The total size of these circuits should be kept minimal. After such single-level decomposition the circuits are further processed by a common synthesis process.
Obtained results are shown in this paper, for a set of standard MCNC and ISCAS benchmarks. Two general problems to be solved were considered for tests: an output-grouping based decomposition and a parity predictor synthesis, which is used in an on-line diagnostic design.
Interconnect Analysis of Spatial Decomposition of
Boolean Functions for Predictable Nanotechnologies
Svetlana N. Yanushkevich,
Bernd Steinbach,
TU Bergakademie Freiberg,
Germany, steinb@informatik.tu-freiberg.de,
Vlad P. Shmerko
Abstract:
This paper addresses the interconnect problem of representation of logic networks in spatial dimensions. Interest to spatial interconnect is motivated by the advent in nanotechnologies and attempts to evaluate and explore the appropriate nanoscale architectures. It have been shown in our previous study that 3D logic network with target topology can be designed by replacing each elementary logic block in a network by its 3D equivalent. In this paper, we solve the problem of partitioning of these 3D blocks over constraints of logic function interconnect and hypercube-like topology. This problem is motivated by the fact that nanotechnologies are sometime critical to the type of this interconnect. We found that decomposition techniques are useful to this solution because provide possibilities to chose a logic functions for assembling decomposed sub-networks.
FPGA Implementation of Boolean Neural Networks using UML
Roman Kohut, Bernd Steinbach,
Dominik Fröhlich
D-09596
email:{kohut, steinb}@informatik.tu-freiberg.de
dfroehli@htwm.de
Abstract:
This paper suggests a new approach for modeling of Boolean
neural networks on fieldprogrammable gate arrays (FPGAs) using UML. The
presented Boolean neural networks (BNN) allow a decreasing of the required
number of configurable logic blocks (CLB) for the realizing of Boolean neuron.
The element of BNN, called Boolean neuron, may be mapped directly to lookup
table (LUT) and configurable logic block (CLB) of FPGAs. Our approach solves
digital design problems especially with respect of the performance and gate
count. In the examples through paper we describe the UML model of the BNN, its
transformation, and the mapping to FPGAs.
Concurrent Decomposition of Multiterminal BDDs
Ilya
Levin1, Osnat Keren2,
1Tel
2Bar
Abstract:
The paper deals with the problem of decomposition of logic functions and their implementation in a form of Multi Terminal Binary Decision Diagrams (MTBDD). The new logic decomposition method and the implementation style, called concurrent decomposition, introduced in the paper leads to a compact VLSI layout of locally interconnected logic elements. It is easily amenable to VLSI implementations of custom design in deep submicron technology, where control over interconnect wiring and its delay becomes of primary importance.
The proposed decomposition method is based on the algebra of D -polynomials reviewed in the paper. The resulting decomposition is directly mapable onto special type of binary graph called Concurrent Multi Terminal BDD. The paper describes both the theoretical fundamentals of the decomposition algorithm and its certain implementation. Benchmark results are presented and analyzed. Guidelines for effective using of the proposed technique are provided.
Linearization of Functions Represented as a Set of
Disjoint Cubes at the Autocorrelation Domain
Osnat Keren
Bar Ilan University, Israel
kereno@macs.biu.ac.il
Ilya Levin,
ilia1@post.tau.ac.il
Radomir S. Stankovic
rstankovic@bankerinter.net
Abstract:
The implementation cost of a multi-output Boolean function, in terms of the number of two-input AND-OR gates, can be reduced by using a linear decomposition. The linearly decomposed Boolean function consists of a linear function followed by the corresponding linearly transformed function. A complexity of the linearized function and therefore, its implementation cost, depends on the linear transform chosen. In this paper we suggest a spectral technique of the linear transformation of functions defined by disjoint cubes.
The proposed linearization procedure is defined over the autocorrelation domain where the autocorrelation function is represented as an arithmetic sum of products. The computation complexity of the suggested method is polynomial in both the number of input variables and the number of cubes of the original function. Hence the suggested method is applicable to functions of a large number of input variables.
Experimental results over standard benchmarks show reduction in the implementation complexity in comparison with the implementation of the initially given non linearized functions. The efficiency in terms of the computation time is demonstrated on randomly generated functions of large number of inputs.
Decomposition of a Boolean Function Using the
Generalized Compact Table
Yuri Pottosin, Eugeny Shestakov
United
Surganov str., 220012
Minsk, Belarus;
e-mail:
{pott,she}@newman.bas-net.by
Abstract:
The concept of generalized compact table is introduced that increase efficiency of the method of decomposition of a Boolean function based on ternary matrix cover. A method for decomposition of a Boolean function using its representation in the form of generalized compact table is given.
The Attractor Structure of Rule 60 Cellular Automata
Jan Schmidt
schmidt@fel.cvut.cz
Abstract:
The analysis of Rule 90 CA by Martin, Odlyzko and Wolfram using diploynomials over finite fields is extended to Rule 60 CA with odd cylinder size. Two classes of such CA are recognized. Their maximum attractor lengths and transients characteristics are given. The basic building block, from which the entire state space can be produced, is identified for each type. An application of the results for diagnostic purpose is outlined.
Generalized Timed Alternating Finite Automata
Abdelaziz Fellah
Dept. of Computer Science
Sharjah,
e-mail: fellah@sharjah.ac.ae
Abstract:
In this paper, we introduce a general framework of timed automata, called generalized timed alternating finite automata (GTAFA), and study their power and properties. The class of languages accepted by GTAFA is equal to the class of regular languages. We present an equational language representation for GTAFA which parallels that of languages equations for timed alternating finite automata. In addition, we show that GTAFA are closed under Boolean operations.