Applications Programmed Using Decision Diagrams
Here is an incomplete list of software which I programmed using decision
diagrams. The projects range from half a page of source code written in
fifteen minutes to test an interesting idea to large stand-alone applications
developed to solve challenging tasks of minimization, decomposition, logic
optimization, and test pattern generation. The list is more or less in
a chronological order.
-
A simple constraint satisfaction system to solve the channel routing
problem
-
Synthesis of FSM state transition graphs from timing constraints
-
BDD-based dictionary
-
Exploration of the state-space of Rubik's cube (two versions)
-
Equivalence checking of two FSMs using the product machine
-
Several implementations of the compatible projection operator
-
A generator of symmetric functions
-
Implicit structural representation of boolean networks
-
Solving unate covering problem using dominance relations and formulas
with quantifiers
-
Heuristic graph coloring using the BDD representation of adjacency matrix
-
Testing boolean and multi-valued networks using the generalized sensitively
function
-
Implicit support manipulation as described by Bill Lin in this ICCD'93
paper
-
Fault localization using the sensitivity functions
-
ASTER: Visualization of boolean networks, Karnaugh maps, and BDDs with
and without complement edges
-
FSM decomposition using S.P. partitions
-
Implicit representation and manipulation of partitions and set systems
-
Efficient implementation of information measures (in collaboration with
L. Jozwiak and A. Chojnacki)
-
Checking unateness of a set of functions in a single traversal of their
shared BDDs
-
Heuristic graph coloring using the ZDD representation of adjacency lists
(unfinished)
-
Recursive disjoint decomposition using Bertacco-Damiani algorithm (ICCAD'97)
(unfinished)
-
Fast computation of Kronecker, Pseudo-Kronecker, and Free-Kronecker
Reed-Muller expansions
-
Attempts to create an implicit algorithm for "irredundant" exclusive
sum-of-product computation
-
DISDEC: Disjoint decomposition of logic functions using a new algorithm
-
A generator of random disjoint-decomposable functions
-
BI-DECOMP: Bi-decomposition of logic functions (in collaboration with
B. Steinbach) (two implementations)
-
LAT: Regular layout synthesis based on variable-pair symmetries (in
collaboration with M. Jeske)
-
RONDO: An implicit two-level sum-of-product minimizer based on the ideas
of O.Coudert
-
Heuristic solver of large cyclic cores using an implicit representation
-
Generation of all algebraic divisors using ZDDs
-
UNDEC: A system for unate decomposition based on ZDDs
-
EEMIN: A system for exact ESOP minimization using ZDDs (in collaboration
with B. Steinbach) (unfinished)
-
Several alternative implementations of the Minato-Morreale irredundant
SOP computation algorithm
-
BI-DECOMP-MV: A system for bi-decomposition of mulvi-valued functions
into MAX and MIN gates
-
XOAMIN: An experimental system for the three-level AND-OR-EXOR minimization
-
Boolean network optimization using internal don't-cares
-
BDS-2: Experiments with BDD-based logic synthesis and optimization (in
progress)
My favorite way of learning is by reading papers and source code, drawing
Karnaugh maps and formulas, figuring out things with paper and pencil.
After some time, understanding comes and the mixture of data structures
and algorithms starts working in my mind. This is the most wonderful state
and yet there is a lurking doubt that, transferred to the real world, the
performance may degrade, given the limitations due to the algorithm complexity,
the amount of available memory, etc. Experimentation becomes inevitable
in order to test the ideas and make them real, and also because (at least
in my case) the unused knowledge, especially of something as intricate
and amazing as decision diagrams, is soon forgotten. This attitude explains
why the above list is long and diverse.
Alan Mishchenko's Home Page
This page has been last modified on September 30, 2001.