A Research on the Representation and Manipulation of Logical Expressions using Ternary Decision Diagrams

我们将使用Ternary Decision Diagrams （TDDs）来表示函数的方法。（1） Termary Decision Diagrams and Their Applications. AND Ternary Decision Diagrams （ATDD） ： Suppose that a logic function f is expanded as f=xf0Vxfl。在二进制决策图（BDD）中，f有两棵树表示f0和f1的节点。In ATDD，the node for f has three sub tree representing f0， f1， and f2， where f2=f0 · f1。ATDD隐含地代表了一组prime implicamts （PIs）。我们开发了一个程序来生成一套使用ATDDs的PIs。这种方法比普通的方法更有效，而且我们成功地生成了数百万个PIs。We also obtained the upper bound on the size of memory required to represent ATDDs. EXOR Termary Decision Diagrams （ETDD） ： In ETDD，the node for f has three sub tree representing f0， f1， and f2， where f2=f0 <symmetry>f1。ETDDs是有用的，可以简化各种AND-EXOR表达式。（2） Optimization of Various AND-EXOR Expressions.Various cl ... More 在AND-EXOR表达式中出现的类别： FPRM （固定极性里德-穆勒表达式）、KRO （Kronecker表达式）、PSDKRO （模拟Kronecker表达式）、GRM （通用里德-穆勒表达式）和ESOP （EXOR总产品表达式）。ETDD是用来优化这些表达式的，ESOP需要在这些表达式中使用少数产品，但优化是，在一般情况下使用的。我们为ESOP开发了EXMIN 2，这是一个人道主义最小化方案。EXMIN 2使用十条规则。我们也对一套规则进行了模拟，以获得最佳ESOP。对于ESOP，加上少量的输入，我们可以通过使用廉价的方法来获得一种真正的最低限度的ESOP。我们已经获得了所有最低限度的ESOP，多达5个变体。我们还使用最低ESOP的结果开发了一个简化程序。我们还为ESOP开发了一种有效的最小化方法，并使用BDD。这个程序适用于具有n=6个变量的系数，GRM是ESOP的一个子类。我们为GRMs开发了一个简单的可测试的现实。我们开发了1）使用BDD来实现GRMs的精确最小化方法，2）使用迭代改进方法来实现一种人道主义简化方法。FPRM是GRMs的一个子类。FPRM的优化方法已经研究了好几年了。我们开发了一种方法，可以通过使用多终端EXOP临时决策图表来获得实际最低FPRM。如果使用这个方法，我们成功地将FPRM减少到90多个输入和更多输出。传统方法可将FPRM最小化，最多可达16个输入，PSDKRO是ESOP的一个子类。我们开发了一个使用ETDDs的最小化程序的PSDKROS。这一方法比EXMIN 2快得多，可以用作ESOP的前极简化算法。我们正在使用ETDDs开发ESOP的最小化方法。Less（低）

We considered methods to represent logic functions by using Ternary Decision Diagrams (TDDs).(1) Termary Decision Diagrams and Their Applications.AND Ternary Decision Diagrams (ATDD) : Suppose that a logic function f is expanded as f=xf0Vxfl. In a binary decision diagram (BDD), the node for f has two sub trees representing f0 and f1. In ATDD,the node for f has three sub tree representing f0, f1, and f2, where f2=f0 ・ f1. An ATDD implicitly represents a set of prime implicamts (PIs). We developed a program to generate a set of PIs using ATDDs. This method is mucg more efficient than ordinary methods, and we successfully generated sets of millions of PIs. We also obtained the upper bound on the size of memory required to represent ATDDs.EXOR Termary Decision Diagrams (ETDD) : In ETDD,the node for f has three sub tree representing f0, f1, and f2, where f2=f0 <symmetry> f1. ETDDs are useful to simplify various AND-EXOR expressions.(2) Optimization of Various AND-EXOR Expressions.Various cl … More asses exist in AND-EXOR expressions : FPRM (Fixed Polarity Reed-Muller expression), KRO (Kronecker expression), PSDKRO (pseudo-Kronecker expression), GRM (Generalized Reed-Muller expression), and ESOP (EXOR sum-of-products expression).ETDDs are useful to optimize these expressions.ESOPs require the fewest products among these expressions, but the optimization is, in general, difficult. We developed EXMIN2, a heuristic minimization program for ESOPs. EXMIN2 uses ten rules. We also analized the set of rules to obtain optimum ESOPs. For the ESOPs with small number of inputs, we can obtain an exact minimum ESOPs by using exhaustive methods. We obtained all the minimum ESOPs up to 5 variables. We also developed a simplification program using the results of exact minimum ESOPs. We also developed an exact minimization method for ESOPs, using BDDs. This program is useful for the fumctions with up to n=6 variables.GRM is a sub-class of ESOPs. We developed an easily testable realization for GRMs. We developed 1)an exact minimization method for GRMs by using BDDs, and 2)a heuristic simplification method using iterative improvement method.FPRM is a sub-class of GRMs. Optimization methods for FPRMs have beenstudied for many years. We developed a method to obtain exact minimum FPRMs by using multi-terminal EXOP ternary decision diagrams. By using this method, we successfully minimized the FPRMs with more than 90 inputs and many outputs. The conventional methods can minimize FPRMs with up to 16 inputs.PSDKRO is a sub-class of ESOPs. We developed a minimization program for PSDKROs by using ETDDs. This method is much faster than EXMIN2, and can beused as pre-minimization algorithm for ESOPs. We are developing a minimization method for ESOP using ETDDs. Less