Analysis of direct cover algorithms for minimization of MVL functions

M. Abd-El-Barr; L. Al-Awami

doi:10.1109/ICM.2003.237881

Analysis of direct cover algorithms for minimization of MVL functions

M. Abd-El-Barr
, L. Al-Awami

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

9 Scopus citations

Abstract

There exist a number of algorithms for minimization of MVL functions. The main objective is to produce near minimal expressions for MVL functions at an affordable cost (measured in terms of CPU time). Among the proposed heuristic-based techniques, direct cover-based techniques have received the most attention. In this paper, we analyze two of the existing direct cover techniques in terms of the number of implicants needed to synthesize a given function. We introduce five modified techniques and analyze them as well. An overall comparison is conducted among the existing and the proposed techniques. The analysis is based on performance measures of these techniques for 50,000 2-variable 4-valued and 21,000 2-variable 5-valued randomly selected functions. The analysis shows that algorithm DM-MIN-2 outperforms all other considered algorithms. The algorithm introduced by Besslich is outperformed by all considered algorithms.

Original language	English
Title of host publication	Proceedings of the 15th International Conference on Microelectronics, ICM 2003
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	308-312
Number of pages	5
ISBN (Electronic)	9770520101
DOIs	https://doi.org/10.1109/ICM.2003.237881
State	Published - 2003

Publication series

Name	Proceedings of the International Conference on Microelectronics, ICM
Volume	2003-January

Bibliographical note

Publisher Copyright:
© 2003 ICM.

Keywords

Algorithm design and analysis
Cost function
Heuristic algorithms
Iterative algorithms
Iterative methods
Minerals
Minimization methods
Performance analysis
Petroleum
Programmable logic arrays

ASJC Scopus subject areas

Electrical and Electronic Engineering

Access to Document

10.1109/ICM.2003.237881

Cite this

Abd-El-Barr, M., & Al-Awami, L. (2003). Analysis of direct cover algorithms for minimization of MVL functions. In Proceedings of the 15th International Conference on Microelectronics, ICM 2003 (pp. 308-312). Article 1287819 (Proceedings of the International Conference on Microelectronics, ICM; Vol. 2003-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICM.2003.237881

@inproceedings{46545c7174604422991f2bbd88a1ae0e,

title = "Analysis of direct cover algorithms for minimization of MVL functions",

abstract = "There exist a number of algorithms for minimization of MVL functions. The main objective is to produce near minimal expressions for MVL functions at an affordable cost (measured in terms of CPU time). Among the proposed heuristic-based techniques, direct cover-based techniques have received the most attention. In this paper, we analyze two of the existing direct cover techniques in terms of the number of implicants needed to synthesize a given function. We introduce five modified techniques and analyze them as well. An overall comparison is conducted among the existing and the proposed techniques. The analysis is based on performance measures of these techniques for 50,000 2-variable 4-valued and 21,000 2-variable 5-valued randomly selected functions. The analysis shows that algorithm DM-MIN-2 outperforms all other considered algorithms. The algorithm introduced by Besslich is outperformed by all considered algorithms.",

keywords = "Algorithm design and analysis, Cost function, Heuristic algorithms, Iterative algorithms, Iterative methods, Minerals, Minimization methods, Performance analysis, Petroleum, Programmable logic arrays",

author = "M. Abd-El-Barr and L. Al-Awami",

note = "Publisher Copyright: {\textcopyright} 2003 ICM.",

year = "2003",

doi = "10.1109/ICM.2003.237881",

language = "English",

series = "Proceedings of the International Conference on Microelectronics, ICM",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "308--312",

booktitle = "Proceedings of the 15th International Conference on Microelectronics, ICM 2003",

address = "United States",

}

Abd-El-Barr, M & Al-Awami, L 2003, Analysis of direct cover algorithms for minimization of MVL functions. in Proceedings of the 15th International Conference on Microelectronics, ICM 2003., 1287819, Proceedings of the International Conference on Microelectronics, ICM, vol. 2003-January, Institute of Electrical and Electronics Engineers Inc., pp. 308-312. https://doi.org/10.1109/ICM.2003.237881

Analysis of direct cover algorithms for minimization of MVL functions. / Abd-El-Barr, M.; Al-Awami, L.
Proceedings of the 15th International Conference on Microelectronics, ICM 2003. Institute of Electrical and Electronics Engineers Inc., 2003. p. 308-312 1287819 (Proceedings of the International Conference on Microelectronics, ICM; Vol. 2003-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Analysis of direct cover algorithms for minimization of MVL functions

AU - Abd-El-Barr, M.

AU - Al-Awami, L.

PY - 2003

Y1 - 2003

N2 - There exist a number of algorithms for minimization of MVL functions. The main objective is to produce near minimal expressions for MVL functions at an affordable cost (measured in terms of CPU time). Among the proposed heuristic-based techniques, direct cover-based techniques have received the most attention. In this paper, we analyze two of the existing direct cover techniques in terms of the number of implicants needed to synthesize a given function. We introduce five modified techniques and analyze them as well. An overall comparison is conducted among the existing and the proposed techniques. The analysis is based on performance measures of these techniques for 50,000 2-variable 4-valued and 21,000 2-variable 5-valued randomly selected functions. The analysis shows that algorithm DM-MIN-2 outperforms all other considered algorithms. The algorithm introduced by Besslich is outperformed by all considered algorithms.

AB - There exist a number of algorithms for minimization of MVL functions. The main objective is to produce near minimal expressions for MVL functions at an affordable cost (measured in terms of CPU time). Among the proposed heuristic-based techniques, direct cover-based techniques have received the most attention. In this paper, we analyze two of the existing direct cover techniques in terms of the number of implicants needed to synthesize a given function. We introduce five modified techniques and analyze them as well. An overall comparison is conducted among the existing and the proposed techniques. The analysis is based on performance measures of these techniques for 50,000 2-variable 4-valued and 21,000 2-variable 5-valued randomly selected functions. The analysis shows that algorithm DM-MIN-2 outperforms all other considered algorithms. The algorithm introduced by Besslich is outperformed by all considered algorithms.

KW - Algorithm design and analysis

KW - Cost function

KW - Heuristic algorithms

KW - Iterative algorithms

KW - Iterative methods

KW - Minerals

KW - Minimization methods

KW - Performance analysis

KW - Petroleum

KW - Programmable logic arrays

UR - https://www.scopus.com/pages/publications/38349140400

U2 - 10.1109/ICM.2003.237881

DO - 10.1109/ICM.2003.237881

M3 - Conference contribution

AN - SCOPUS:38349140400

T3 - Proceedings of the International Conference on Microelectronics, ICM

SP - 308

EP - 312

BT - Proceedings of the 15th International Conference on Microelectronics, ICM 2003

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Analysis of direct cover algorithms for minimization of MVL functions

Abstract

Publication series

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this