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

Yutaka HATA  Kazuharu YAMATO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E76-D   No.5   pp.555-561
Publication Date: 1993/05/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Multiple-Valued Logic)
Category: Logic Design
Keyword: 
computer hardware and design,  multiple-valued some-of-products expressions,  optimal output permutation,  logic complexity,  upper bounds,  

Full Text: PDF(563.9KB)>>
Buy this Article




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.