## Reducing Multi-Valued Algebraic Operations to Binary

Jie-Hong R. Jiang and Alan Mishchenko^{1}

(Professor Robert K. Brayton)

California State Micro program and (SRC) 682-004

Algebraic operations were developed for binary logic synthesis and
extended later to apply to multi-valued (MV) logic. Operations in
the MV domain were considered more complex and slower. We show that
MV algebraic operations are essentially as easy as binary ones,
with only a slight overhead (linear in the expressions) in
transformation into and out of the binary domain.

By introducing co-singleton sets as a new basis, any MV
sum-of-products expression can be rewritten and parsed to a binary
logic synthesizer for fast execution. The optimized results can be
directly interpreted in the MV domain. This process, called EBD,
reduces MV algebraic operations to binary.

A pure MV operation differs mainly from its corresponding EBD one
in that the former possesses "semi-algebraic" generality, which
has not been implemented for binary logic. Preliminary experimental results show that the proposed methods are significantly faster,
with little or no loss in quality when run in comparable scripts of sequences of logic synthesis operations.

We also show that in principle through the co-singleton transform,
all MV semi-algebraic operations could be reproduced in the binary domain if the binary operations had semi-algebraic extensions. This result suggests that semi-algebraic operations in the binary domain should be investigated in the future.

^{1}Postdoctoral Researcher, Portland State University

Send mail to the author : (jiejiang@eecs.berkeley.edu)

Edit this abstract