Efficient Triadic Generators for Logic Circuits

Grant POGOSYAN; Takashi NAKAMURA

Efficient Triadic Generators for Logic Circuits

Grant POGOSYAN, Takashi NAKAMURA

Full Text Views

0

Cite this

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 two-input (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 3-input 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 k-valued 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.

Publication: IEICE TRANSACTIONS on Information Vol.E82-D No.5 pp.919-924

Publication Date: 1999/05/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on Multiple-Valued Logic and Its Applications)

Category: Logic and Logic Functions

Cite this

Copy

Grant POGOSYAN, Takashi NAKAMURA, "Efficient Triadic Generators for Logic Circuits" in IEICE TRANSACTIONS on Information, vol. E82-D, no. 5, pp. 919-924, May 1999, doi: .
Abstract: 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 two-input (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 3-input 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 k-valued 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e82-d_5_919/_p

Copy

@ARTICLE{e82-d_5_919,
author={Grant POGOSYAN, Takashi NAKAMURA, },
journal={IEICE TRANSACTIONS on Information},
title={Efficient Triadic Generators for Logic Circuits},
year={1999},
volume={E82-D},
number={5},
pages={919-924},
abstract={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 two-input (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 3-input 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 k-valued 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.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - Efficient Triadic Generators for Logic Circuits
T2 - IEICE TRANSACTIONS on Information
SP - 919
EP - 924
AU - Grant POGOSYAN
AU - Takashi NAKAMURA
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E82-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 1999
AB - 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 two-input (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 3-input 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 k-valued 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.
ER -