Skip to main content

Über dieses Buch

Representations of Discrete Functions is an edited volume containing 13 chapter contributions from leading researchers with a focus on the latest research results.
The first three chapters are introductions and contain many illustrations to clarify concepts presented in the text. It is recommended that these chapters are read first.
The book then deals with the following topics: binary decision diagrams (BDDs), multi-terminal binary decision diagrams (MTBDDs), edge-valued binary decision diagrams (EVBDDs), functional decision diagrams (FDDs), Kronecker decision diagrams (KDDs), binary moment diagrams (BMDs), spectral transform decision diagrams (STDDs), ternary decision diagrams (TDDs), spectral transformation of logic functions, other transformations oflogic functions, EXOR-based two-level expressions, FPRM minimization with TDDs and MTBDDs, complexity theories on FDDs, multi-level logic synthesis, and complexity of three-level logic networks.
Representations of Discrete Functions is designed for CAD researchers and engineers and will also be of interest to computer scientists who are interested in combinatorial problems.
Exercises prepared by the editors help make this book useful as a graduate level textbook.



1. Graph-Based Representations of Discrete Functions

BDDs are now commonly used for representing Boolean functions because of their efficiency in terms of time and space. There are many cases in which conventional algorithms can be significantly improved by using BDDs. Recently, several variants of BDDs have been developed to represent other kinds of discrete functions, such as multi-valued functions, cube sets, or arithmetic formulas. These techniques are useful not only for VLSI CAD but also for various areas in Computer Science. In this chapter, we survey the techniques of BDD and its variants. We explain the basic method of BDD manipulation, and show the relationships between the different types of BDDs.
Shin-ichi Minato

2. Representations of Logic Functions Using EXOR Operators

Logic functions are usually represented by logical expressions or decision diagrams using AND and OR operators. However, some functions have more compact representations with EXOR operators. This chapter surveys representations of logic functions using EXOR operators.
Tsutomu Sasao

3. Spectral Transform Decision Diagrams

This chapter proposes spectral decision diagrams (STDDs), that are graphical representations of spectral transforms of switching functions and integer-valued functions. Binary decision diagrams (BDDs) and functional decision diagrams (FDDs) are graphical representations for switching functions and their Reed-Muller transforms, respectively. Multi-terminal decision diagrams (MTBDDs), arithmetic transform decision diagrams (ACDDs), and Walsh transform decision diagrams (WDDs) are graphical representations for integer-valued functions, their arithmetic transforms, and their Walsh transforms, respectively. This chapter shows that an STDD represents a function and its spectral transform at the same time. As for n-bit adders, ACDDs and WDDs require O(n) nodes while MTBDDs require O(2 n ) nodes. As for n-bit multipliers, ACDDs and WDDs require O(n 2) nodes while MTBDDs require O(4 n ) nodes.
Radomir S. Stanković, Tsutomu Sasao, Claudio Moraga

4. Multi-Terminal Binary Decision Diagrams and Hybrid Decision Diagrams

Functions that map vectors with binary values into the integers are important for the design and verification of arithmetic circuits. We demonstrate how multi-terminal binary decision diagrams (MTBDDs) can be used to represent such functions concisely. The Walsh transform and Reed-Muller transform have numerous applications in computer-aided design, but the usefulness of these techniques in practice has been limited by the size of the binary valued functions that can be transformed. We show how to compute the MTBDD representations of the Walsh transform and Reed-Muller transform for functions with several hundred variables. Bryant and Chen have proposed binary moment diagrams (BMDs) for representing the class of functions that we have considered. We discuss the relationship between these methods and describe a generalization called hybrid decision diagrams which is often much more concise.
Edmund M. Clarke, Masahiro Fujita, Xudong Zhao

5. Edge Valued Binary Decision Diagrams

We describe a canonical and compact data structure, called Edge Valued Binary Decision Diagrams (EVBDD), for representing and manipulating pseudo Boolean functions (PBF). EVBDDs are particularly useful when both arithmetic and Boolean operations are required. We describe a general algorithm on EVBDDs for performing any binary operation that is closed over the integers. Next, we discuss the relation between the probability expression of a Boolean function and its representation as a pseudo Boolean function. Utilizing this, we present algorithms for computing the probability spectrum and the Reed-Muller spectrum of a Boolean function directly on the EVBDD. Finally, we describe an extension of EVBDDs which associates both an additive and a multiplicative weight with the true edges of the function graph.
Sarma B. K. Vrudhula, Massoud Pedram, Yung-Te Lai

6. Arithmetic Transform of Boolean Functions

In many applications where logic functions need to be analyzed it can be useful if we transform Boolean (or switching) functions to arithmetic functions. Such arithmetic transformations can give us new insight into solving some interesting problems. For example, the transformed functions can be easily evaluated (simulated) on integers or real numbers. Through such arithmetic simulation we can probabilistically verify a pair of functions with much more confidence than two-valued Boolean simulation. The arithmetic transform of any Boolean function can be easily computed from its BDD. To help evaluate a Boolean function on non-binary inputs, and to represent multi-variable linear polynomials with integer coefficients, a BDD like data structure snDD can be used; for many arithmetic expressions, snDDs are a very compact representation. The error in such probabilistic verification of property of a function is quantifiable and extremely low. Also, the procedures are computationally very efficient. Using a real-valued or integer-valued representation we can derive testability measures for elements of a digital circuit, or conduct the reliability analysis for various networks.
Jawahar Jain

7. OKFDDs — Algorithms, Applications and Extensions

We present Ordered Kronecker Functional Decision Diagrams (OKFDDs), a graph-based data structure for the representation and manipulation of Boolean functions. OKFDDs are a generalization of Ordered Binary Decision Diagrams and Ordered Functional Decision Diagrams and as such provide a more compact representation of the functions than either of the two decision diagrams. We review basic properties of OKFDDs and study methods for their efficient representation and manipulation. These algorithms are integrated in our OKFDD package PUMA whose implementation is briefly discussed. Finally we point out some applications of OKFDDs, demonstrate the efficiency of our approach by some experiments and discuss a promising extension of the concept to also allow representation and manipulation of word-level functions.
Rolf Drechsler, Bernd Becker

8. Exact Minimization of FPRMs Using Multi-Terminal Exor TDDs

This chapter presents methods to derive a fixed polarity Reed-Muller expression (FPRM) and a Kronecker expression (KRO) having the minimum number of products for a given logic function. The minimization methods use EXOR ternary decision diagrams (ETDDs) and multi-terminal binary decision diagrams (MTBDDs) to represent extended truth vectors and weight vectors, respectively. Various techniques to reduce computation time and memory storage are developed. Experimental results up to 94 inputs are shown. The presented method outperforms existing methods.
Tsutomu Sasao, Fumitaka Izuhara

9. Multiple Domain Logic Synthesis

Field programmable gate arrays (FPGA) and other complex programmable devices (CPLD) require new logic minimization techniques since the cost functions used for conventional target implementations are no longer valid. Until now, existing tools are only adapted to the new requirements. However, the underlying approaches for logic minimization and technology mapping remained the same. We present logic minimization techniques that extend classical approaches. Basic function properties as e.g. linearity, monotony, and symmetry of its variables are detected. They are used in decomposition and partial collapsing steps to group variables with common properties within a multi-level Boolean network. The Boolean functions are stored as decision diagrams. Three different Boolean normal forms are used: disjunctive normal form, Reed-Muller expansion, and equivalence polynomial. Therefore, three types of decision diagrams are needed: binary decision diagrams (BDD), functional decision diagrams (FDD), and equivalence decision diagrams (EDD). A multiple domain minimization approach based on decomposition, domain selection, variable ordering, and variable polarity optimization is introduced.
Jörg Bullmann, Udo Kebschull

10. Satisfiability Problems for OFDDs

We investigate the complexity of problems on Ordered Functional Decision Diagrams (OFDDs) related to satisfiability, i.e. SAT-ONE, SAT-ALL, and SAT-COUNT. We prove that SAT-ALL has a running time linear in the product of the number of satisfying assignments and the size of the given OFDD. Counting the satisfying assignments in an OFDD is proved to be #P-complete, and thus not possible in polynomial time unless P=NP.
Ralph Werchner, Thilo Harich, Rolf Drechsler, Bernd Becker

11. Complexity Theoretical Aspects of OFDDs

Experimental results have shown that OFDDs (ordered functional decision diagrams) are a representation of Boolean functions which are sometimes superior to OBDDs (ordered binary decision diagrams). Most of the complexity theoretical problems have been solved for OBDDs. Here some results for OFDDs are proved. It is NP-complete to decide whether a function represented by some OFDD can be represented by an OFDD of size s using another variable ordering. Given an OFDD representation for an incompletely specified function, it is NP-hard to compute an optimal OFDD cover for this function respecting the same variable ordering. The replacement of variables by constants may cause an exponential blow-up of the OFDD size. Finally, it is investigated how a local change of the variable ordering may change the OFDD size. This leads to simulated annealing algorithms to improve variable orderings.
Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener

12. Ternary Decision Diagrams and their Applications

This chapter presents various ternary decision diagrams (TDDs) to represent logic functions. A path from the root node to the terminal node representing a constant 1 is called a 1-path. The 1-paths for a Reduced Ordered AND TDD (ROATDD) and prime TDD (PTDD) represent the sets of the implicants and the prime implicants (PIs) of the functions, respectively. The 1-paths for a Reduced Ordered TDD (RO-TDD) represent a sum-of-products expression (SOP). For any function, there is a unique ROATDD and a unique PTDD. For any SOP, there is a unique ROTDD. An arbitrary function of n variables can be represented by a TDD with O(3 n /n) nodes. A symmetric function can be represented by a TDD with O(n 3 ) nodes. A program to generate all the PIs by using PTDDs is developed and shown to be much faster than conventional methods.
Tsutomu Sasao

13. Or-and-Or Three-Level Networks

This chapter considers the number of gates to realize logic functions by OR-AND-OR three-level networks under the condition that both true and complemented variables are available, and each gate has no fan-in and fan-out constraints. We show that an arbitrary n-variable function can be realized by an OR-AND-OR three-level network with at most 2 r+1 + 1 gates, where n = 2r and r is an integer. We also prove that for sufficiently large r, regardless of the number of levels, we need at least 2 r+1 (1 - ξ) gates to realize almost all functions of n variables by an AND-OR multi-level network, where ξ is an arbitrarily small positive real number (0 < ξ < 1). We developed a heuristic algorithm to design OR-AND-OR three-level networks, realized various functions, and compared the number of gates for OR-AND-OR three-level networks with AND-OR two-level ones. For arithmetic functions of 8 variables, three-level networks require, on the average, 40% fewer gates than AND-OR two-level ones. For other benchmark functions of 9 to 128 variables, three-level networks required up to 91% fewer gates. For randomly generated functions of 10 variables, three-level networks required 50% fewer gates.
Tsutomu Sasao


Weitere Informationen