Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Exact Algorithm
Linear Transformation
Related Publications
(3)
Application of linearly transformed BDDs in sequential verification
Linear sifting of decision diagrams
BDD minimization by truth table permutations
Subscribe
Academic
Publications
Linear Transformations and Exact Minimization of BDDs
Linear Transformations and Exact Minimization of BDDs,10.1109/GLSV.1998.665287,Wolfgang Günther,Rolf Drechsler
Edit
Linear Transformations and Exact Minimization of BDDs
(
Citations: 14
)
BibTex

RIS

RefWorks
Download
Wolfgang Günther
,
Rolf Drechsler
We present an
exact algorithm
to find an optimallinear transformation for the variables of a Booleanfunction to minimize its corresponding ordered BinaryDecision Diagram (BDD). To prune the huge searchspace, techniques known from algorithms for findingthe optimal variable ordering are used. This BDDminimization finds direct application in FPGA design.We give experimental results for a large variety of circuitsto show the efficiency of our approach.1 IntroductionSpectral methods have ...
Conference:
ACM Great Lakes Symposium on VLSI
, pp. 325330, 1998
DOI:
10.1109/GLSV.1998.665287
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.informatik.unitrier.de
)
(
csdl.computer.org
)
(
ieeexplore.ieee.org
)
Citation Context
(11)
...But in the sense of complexity, O(3n) is a very large value. The algorithm is set out in [
19
] that...
A. Kolpakov
,
et al.
Approximate Algorithms for Minimization of Binary Decision Diagrams on...
...Linearly transformed BDDs are defined by allowing linear combinations of variables [
6
]...
...An algorithm for exact minimization of of BDDs by linear transformation of variables has been proposed in [
6
]...
Mark G. Karpovsky
,
et al.
Construction of linearly transformed planar BDD by Walsh coefficients
...Linear sifting was introduced by Meinel, Somenzi and Theobold [9] and further discussed by Günther and Drechsler [
4
][5][6]...
D. Michael Miller
,
et al.
Augmented Sifting of MultipleValued Decision Diagrams
...There remains the problem of choosing a suitable linear transformation.G¨unther and Drechsler [
63
] presented an exact algorithm to determine an optimal linear transformation such that the OBDD size is minimized, but due to its exponential runtime it is only applicable to functions depending on a small number of variables.In Sect.2.4 we showed how a swap of two adjacent variables can be performed efficiently by redirecting pointers...
Rolf Drechsler
,
et al.
Binary decision diagrams in theory and practice
...We would also like to mention recent work on linear transformations in synthesis in [9] [focussing on programmable logic arrays (PLA’s)] and [
15
] [based on earlier versions of our work and focussing on field programmable gate arrays (FPGA’s)]...
Christoph Meinel
,
et al.
Linear sifting of decision diagrams and its application insynthesis
Sort by:
Citations
(14)
FSM Encoding for BDD Representations
(
Citations: 2
)
Wilsin Gosti
,
Tiziano Villa
,
Alexander Saldanha
,
Alberto L. Sangiovannivincentelli
Journal:
Applied Mathematics and Computer Science
, vol. 17, no. 1, pp. 113124, 2007
Approximate Algorithms for Minimization of Binary Decision Diagrams on the Basis of Linear Transformations of Variables
(
Citations: 2
)
A. Kolpakov
,
R. Kh. Latypov
Journal:
Automation and Remote Control  AUTOMAT REMOTE CONTRENGL TR
, vol. 65, no. 6, pp. 938954, 2004
Construction of linearly transformed planar BDD by Walsh coefficients
(
Citations: 1
)
Mark G. Karpovsky
,
Radomir S. Stankovic
,
Jaakko Astola
Conference:
IEEE International Symposium on Circuits and Systems  ISCAS
, pp. 517520, 2004
Augmented Sifting of MultipleValued Decision Diagrams
(
Citations: 9
)
D. Michael Miller
,
Rolf Drechsler
Conference:
IEEE International Symposium on MultipleValued Logic  ISMVL
, pp. 375382, 2003
Binary decision diagrams in theory and practice
(
Citations: 49
)
Rolf Drechsler
,
Detlef Sieling
Journal:
International Journal on Software Tools for Technology Transfer  STTT
, vol. 3, no. 2, pp. 112136, 2001