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

点击翻译按钮获取中文摘要

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