Minimization of AND-OR-EXOR Three-Level Networks with AND Gate Sharing

Debatosh DEBNATH; Tsutomu SASAO

Minimization of AND-OR-EXOR Three-Level Networks with AND Gate Sharing

Debatosh DEBNATH, Tsutomu SASAO

Full Text Views

0

Cite this

Summary :

This paper presents an exact minimization algorithm for AND-OR-EXOR three-level networks, where a single two-input exclusive-OR (EXOR) gate is used. The network realizes an EXOR of two sum-of-products expressions (EX-SOP), where the two sum-of-products expressions (SOP) can share products. The objective is to minimize the total number of different products in the two SOPs. An algorithm for the exact minimization of EX-SOPs with up to five variables are shown. Up to five variables, EX-SOPs for all the representative functions of NP-equivalence classes were minimized. For five-variable functions, we confirmed that minimum EX-SOPs require up to 9 products. For n-variable functions, minimum EX-SOPs require at most 92^n-5 (n6) products.

Publication: IEICE TRANSACTIONS on Information Vol.E80-D No.10 pp.1001-1008

Publication Date: 1997/10/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on Synthesis and Verification of Hardware Design)

Category: Logic Design

Cite this

Copy

Debatosh DEBNATH, Tsutomu SASAO, "Minimization of AND-OR-EXOR Three-Level Networks with AND Gate Sharing" in IEICE TRANSACTIONS on Information, vol. E80-D, no. 10, pp. 1001-1008, October 1997, doi: .
Abstract: This paper presents an exact minimization algorithm for AND-OR-EXOR three-level networks, where a single two-input exclusive-OR (EXOR) gate is used. The network realizes an EXOR of two sum-of-products expressions (EX-SOP), where the two sum-of-products expressions (SOP) can share products. The objective is to minimize the total number of different products in the two SOPs. An algorithm for the exact minimization of EX-SOPs with up to five variables are shown. Up to five variables, EX-SOPs for all the representative functions of NP-equivalence classes were minimized. For five-variable functions, we confirmed that minimum EX-SOPs require up to 9 products. For n-variable functions, minimum EX-SOPs require at most 92^n-5 (n6) products.
URL: https://global.ieice.org/en_transactions/information/10.1587/e80-d_10_1001/_p

Copy

@ARTICLE{e80-d_10_1001,
author={Debatosh DEBNATH, Tsutomu SASAO, },
journal={IEICE TRANSACTIONS on Information},
title={Minimization of AND-OR-EXOR Three-Level Networks with AND Gate Sharing},
year={1997},
volume={E80-D},
number={10},
pages={1001-1008},
abstract={This paper presents an exact minimization algorithm for AND-OR-EXOR three-level networks, where a single two-input exclusive-OR (EXOR) gate is used. The network realizes an EXOR of two sum-of-products expressions (EX-SOP), where the two sum-of-products expressions (SOP) can share products. The objective is to minimize the total number of different products in the two SOPs. An algorithm for the exact minimization of EX-SOPs with up to five variables are shown. Up to five variables, EX-SOPs for all the representative functions of NP-equivalence classes were minimized. For five-variable functions, we confirmed that minimum EX-SOPs require up to 9 products. For n-variable functions, minimum EX-SOPs require at most 92^n-5 (n6) products.},
keywords={},
doi={},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - Minimization of AND-OR-EXOR Three-Level Networks with AND Gate Sharing
T2 - IEICE TRANSACTIONS on Information
SP - 1001
EP - 1008
AU - Debatosh DEBNATH
AU - Tsutomu SASAO
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E80-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 1997
AB - This paper presents an exact minimization algorithm for AND-OR-EXOR three-level networks, where a single two-input exclusive-OR (EXOR) gate is used. The network realizes an EXOR of two sum-of-products expressions (EX-SOP), where the two sum-of-products expressions (SOP) can share products. The objective is to minimize the total number of different products in the two SOPs. An algorithm for the exact minimization of EX-SOPs with up to five variables are shown. Up to five variables, EX-SOPs for all the representative functions of NP-equivalence classes were minimized. For five-variable functions, we confirmed that minimum EX-SOPs require up to 9 products. For n-variable functions, minimum EX-SOPs require at most 92^n-5 (n6) products.
ER -