Output Permutation and the Maximum Number of Implicants Needed to Cover the Multiple-Valued Logic Functions

Yutaka HATA, Kazuharu YAMATO

Summary :

An idea of optimal output permutation of multiple-valued sum-of-products expressions is presented. The sum-of-products involve the TSUM operator on the MIN of window literal functions. Some bounds on the maximum number of implicants needed to cover an output permuted function are clarified. One-variable output permuted functions require at most p1 implicants in their minimal sum-of-products expressions, where p is the radix. Two-variable functions with radix between three and six are analyzed. Some speculations of maximum number of the implicants could be established for functions with higher radix and more than 2-variables. The result of computer simulation shows that we can have a saving of approximately 15% on the average using permuting output values. Moreover, we demonstrate the output permutation based on the output density as a simpler method. For the permutation, some speculation is shown and the computer simulation shows a saving of approximately 10% on the average.

• Publication: IEICE TRANSACTIONS on Information Vol.E76-D No.5 pp.555-561
• Publication Date: 1993/05/25
• Type of Manuscript: Special Section PAPER (Special Issue on Multiple-Valued Logic)
• Category: Logic Design

Authors

Yutaka HATA
Kazuharu YAMATO

Keyword

computer hardware and design,  multiple-valued some-of-products expressions,  optimal output permutation,  logic complexity,  upper bounds