Ternary decision diagrams. Survey
---
paper_title: Shared binary decision diagram with attributed edges for efficient Boolean function manipulation

paper_content:

The efficiency of Boolean function manipulation depends on the form of representation of Boolean functions. Binary decision diagrams (BDDs) are graph representations proposed by S.B. Akers (1978) and R.E. Bryant (1985). BDDs have some properties which can be used to enable efficient Boolean function manipulation. The authors describe a technique of more efficient Boolean function manipulation that uses shared binary decision diagrams (SBDDs) with attributed edges. The implements include an ordering algorithm of input variables and a method of handling 'don't care'. A Boolean function manipulator using the above methods is developed and it is shown that the manipulator is very efficient in terms of speed and storage.<<ETX>>
---
paper_title: Multiple-valued logic design tools

paper_content:

A brief overview of past progress in multiple-valued logic design is presented. The methods are considered with respect to the likely development of multiple-valued field programmable gate arrays. Look-up table based arrays are considered in some detail and an algorithm for mapping multiple-valued functions to such an array is presented. This algorithm uses reduced order multiple-valued decision diagrams, an extension of R.E. Bryant's (1986) well-studied structure for binary functions. The algorithm works in the functional domain and does not require the synthesis and optimization of a conventional network prior to technology mapping. >
---
paper_title: Implicit and incremental computation of primes and essential primes of Boolean functions

paper_content:

Recently introduced implicit set manipulation techniques have made it possible to formally verify finite state machines with state graphs too large to be built. The authors show that these techniques can also be used with success to compute and manipulate implicitly large sets of prime and of essential prime implicants of incompletely specified Boolean functions. These sets are denoted by meta-products that are represented with binary decision diagrams (BDDs). Two procedures are described. The first is based on the standard BDD operators, and the second, more efficient, takes advantage of the structural properties of BDDs and of meta-products to handle a larger class of functions than the first procedure. >
---
paper_title: Exact Minimization of FPRMs Using Multi-Terminal Exor TDDs

paper_content:

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.
---
paper_title: A synthesis algorithm for two-level XOR based circuits

paper_content:

A fast algorithm for minimizing the two-level AND/XOR representation of combinational functions, based on a graphical data structure similar to the OBDD, is described. This GMX (Graphical Minimizer for XORs) algorithm works by 'reading-off' and minimizing the solution from an augmented OBDD, called an SFG. The advantage of the SFG structure is that it is often of polynomial size. The algorithm generates solutions significantly better, or no worse, than all previously published solutions on a set of example circuits. >
---
paper_title: Generalization of Consensus Theory and Application to the Minimization of Boolean Functions

paper_content:

Given two implicants of a Boolean function, we can, by performing their consensus, find a third implicant. This operation has been used for finding the prime implicants of a Boolean function. In this paper, the consensus is extended from two to any number of terms. A property of these generalized consensus relations leads to a systematic way of finding them. It is shown that any prime implicant of a Boolean function is a generalized consensus; therefore the algorithm for the determination of the consensus relations can be used for finding the prime implicants. This new method is simpler than the usual process of iterative consensus. It is also shown in this paper that consensus theory can be used for finding the minimal sums of a Boolean function. The methods are applicable for any Boolean function, with or without don't care conditions, with a single or a multiple output.
---

Title: Ternary Decision Diagrams. Survey

Section 1: Introduction
Description 1: Provide an overview of logic function representation methods and introduce the concept and need for ternary decision diagrams (TDDs), highlighting their differences from binary decision diagrams (BDDs).

Section 2: BDDs
Description 2: Discuss the binary decision diagrams (BDDs) methodology, including their structure, reduction rules, and canonical forms.

Section 3: General-TDDs
Description 3: Explain general-TDDs as an extension to BDDs for three-valued logic functions and their properties, such as canonicity and reduction.

Section 4: SOP-TDDs
Description 4: Describe SOP-TDDs, focusing on their representation of sum-of-products expressions and how they are constructed and reduced.

Section 5: ESOP-TDDs
Description 5: Cover ESOP-TDDs, detailing their construction process and their advantages in terms of the number of products over SOP-TDDs.

Section 6: AND-TDDs
Description 6: Discuss AND-TDDs and their role in representing the set of implicants of a logic function, along with applications in generating other forms of TDDs.

Section 7: EXOR-TDDs
Description 7: Explain EXOR-TDDs, their construction, and their application in optimizing AND-EXOR expressions.

Section 8: Relations among TDDs
Description 8: Analyze the relationships among different types of TDDs and their respective properties.

Section 9: Complexity of TDDs
Description 9: Present a complexity analysis of TDDs, highlighting the practical limits of their construction and comparing sizes of various TDDs for different functions.

Section 10: Various Works on TDDs
Description 10: Review significant contributions to the study and application of TDDs, including methodologies and optimization techniques.

Section 11: Theoretical analysis
Description 11: Provide a deeper theoretical analysis of the sizes of different types of TDDs and BDDs, supported by experimental data and theorems.

Section 12: SOP-TDD
Description 12: Further discuss properties of SOP-TDDs and present a comparison with BDDs in terms of size reduction benefits.

Section 13: Kleene-TDD
Description 13: Detail the Kleene-TDD package, its complexities, and potential methods for optimization through decomposition.