
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Efficient Triadic Generators for Logic Circuits
Grant POGOSYAN Takashi NAKAMURA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E82D
No.5
pp.919924 Publication Date: 1999/05/25
Online ISSN:
DOI:
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Issue on MultipleValued Logic and Its Applications) Category: Logic and Logic Functions Keyword: multivalued logic, logic design, generating sets,
Full Text: PDF(293.5KB)>>
Summary:
In practical logic design circuits are built by composing certain types of gates. Each gate itself is a simple circuits with one, two or three inputs and one output, which implements an elementary logic function. These functions are called the generators. For the general purpose the set of generators is considered to be functionally complete, i. e. , it is able to express any logic function under chosen rules compositions. A basis is a functionally complete set of logic functions that contains no complete proper subset. Providing compactness and expressibility of the generators the notion of a basis, however, ignores the optimality of implementations. Efficiently irreducible generating set, termed εbasis, is an irreducible set of generators which guarantees an optimal implementation of every function, with respect to the number of literals in its formal expression. The notion of εbasis is significant in the composition of functions, since the classical definition of basis does not consider the efficiency of implementation. In case of Boolean functions, for twoinput (dyadic) generators it has been shown that an εbasis consists of all monadic functions, constants, and only two dyadic functions from certain classes. In this paper, expanding the domain of basic operations from dyadic to triadic, we study the efficiency of sets of 3input gates as generators. This expansion decreases the complexity of functions (hence, the complexity of functional circuits to be designed). Gaining an evident merit in the complexity, we have to pay a price by a considerable increase of the number of such generators for the multiple valued circuits. However, in the case of Boolean operations this number is still very small, and it will certainly be useful to consider this approach in the practical circuit design. This paper provides a criterion for a generating set of triadic operations of kvalued logic to be efficiently irreducible. In the case of Boolean functions it is shown that there exist exactly five types of classes of triadic operations which constitute an εbasis. A typical example of generator set which forms a triadic εbasis, is also shown.

