Arithmetic transform ternary decision diagrams for exact minimization of fixed-polarity arithmetic expressions

Abstract

In this paper, we define Arithmetic Transform TDDs (AC-TDDs) as a word-level counterpart of EXOR-TDDs. We discuss relationships and differences with the Arithmetic TDDs (Arith-TDDs). Then, we pointed out that from AC-TDDs we can read all the arithmetic polynomial expressions for switching functions. We show that, unlike other TDDs, single root AC-TDDs can be used to represent multi-output functions. We also show that AC-TDDs can be used for exact minimization of Fixed-polarity Arithmetic expressions in the same way as EXOR-TDDs can be used for minimization of Fixed-polarity Reed-Muller expressions.