Cited By
View all- Sampson MKalathas MVoudouris DPapakonstantinou G(2012)Exact ESOP expressions for incompletely specified functionsIntegration10.1016/j.vlsi.2011.10.00145:2(197-204)Online publication date: Mar-2012
A heuristic algorithm to minimize ESOPs for multiple-output incompletely specified functions
Pages 357 - 361
Abstract
In this work, a novel heuristic algorithm for the minimization of Exclusive-Or Sum Of Products (ESOP) expressions for multiple output incompletely specified functions is presented. An initial algorithm, DCMIN, uses functional decomposition and multiple-valued logic in order to produce almost minimal expressions for these functions. Based on DCMIN, an improved algorithm, QuickDCMIN, is proposed, which outperforms existing algorithms.
References
[1]
A. Gaidukov. Algorithm to derive minimum esop for 6-variable function. In 5th IWBP September 2002.
[2]
M. Helliwell and M. Perkowski. A fast algorithm to minimize multi-output mixed-polarity generalized reed-muller forms. In 25th ACM/IEEE Conf. on Design automation pages 427--432, 1988.
[3]
T. Hirayama and Y. Nishitani. A simplification algorithm of and-exor expressions for multiple-output functions. In 2nd Workshop on Applications of Reed-Muller Expansion in Circuit Design pages 88--93, Chiba City, Japan, 1995.
[4]
T. Kozlowski, E. L. Dagless, andJ. M. Saul. An enhanced algorithm for the minimization of exclusive-or sum-of-products for incompletely specified functions. In 1995 IEEE Intrn. Conf. on Computer Design (ICDD'95) page 244, 1995.
[5]
M. Matsuura and T. Sasao. Representation of incompletely specified switching functions using pseudo-kronecker decision diagrams. In Reed-Muller 2001 pages 27--33, Starkville, Mississippi, USA, August 2001.
[6]
G. Papakonstantinou. Minimization of modulo-2 sum of products. IEEE Trans. on Computers 28(2): 163--167, 1979.
[7]
G. Papakonstantinou. Minimal modulo-2 expressions of switching functions withfive variables. Intrn. Journal of Electr. 50(3): 211--214, 1981.
[8]
T. Sasao. Exmin2: A simplification algorithm for exclusive-or sum-of-products expressions for multiple-valued input two-valued output functions. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems 12(5): 621--632, May 1993.
[9]
T. Sasao and M. Matsuura. Bdd representation for incompletely specified multiple-output logic functions and its applications to functional decomposition. In DAC2005 June 2005.
[10]
N. Song and M. A. Perkowski. Minimization of exclusive sum-of-products expressions for multiple-valued input, incompletely specified functions. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems 15(4), April 1996.
[11]
S. Stergiou and G. Papakonstantinou. An efficient algorithm for exact esop minimization. In The 2002 Int. Conf. on VLSI June 2002.
[12]
S. Stergiou and G. Papakonstantinou. Towards a general novel exact esop minimization methodology. In 6th Intrn. Workshop on Appl. of the Reed Muller Expansion in Circuit Design March 2003.
[13]
S. Stergiou and G. Papakonstantinou. Exact minimization of esop expressions with less than eight product terms. Journal of Circuits, Systems, and Computers 13(1): 1--15, 2004.
[14]
S. Stergiou, D. Voudouris, and G. Papakonstantinou. Exact and heuristic mvesop minimization algorithms. IEICE Trans. on Fund. E87-A(1), January 2004.
[15]
D. Voudouris, M. Kalathas, and G. Papakonstantinou. Decomposition of multi-output boolean functions. In HERCMA2005 Athens, September 2005.
Index Terms
- A heuristic algorithm to minimize ESOPs for multiple-output incompletely specified functions
Recommendations
A Multiple-Valued Reed-Muller Transform for Incompletely Specified Functions
This paper considers the Reed-Muller transform for incompletely specified multiple-valued logic functions, which is obtained as the finite field polynomial representation. A new algorithm for dealing with single-variable functions is presented. It is ...
Multiple-Valued Logic Charge-Coupled Devices
A new method to implement multiple-valued logic in large scale integrated circuits is introduced. The data are represented by discrete amounts of charge in a charge-coupled device. In this paper the design principles and realizations in four-valued ...
An enhanced algorithm for the minimization of exclusive-OR sum-of-products for incompletely specified functions
ICCD '95: Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and ProcessorsMost of the current exclusive-OR sum-of-products minimization algorithms use rule-based heuristics to transform an initial circuit description into a possibly compact form. This paper presents an enhanced minimization algorithm, MINT, introducing new ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2006
450 pages
ISBN:1595933476
DOI:10.1145/1127908
- General Chairs:
- Gang Qu,
- Yehea Ismail,
- Program Chairs:
- Vijaykrishnan Narayanan,
- Hai Zhou
Copyright © 2006 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 30 April 2006
Check for updates
Author Tags
Qualifiers
- Article
Conference
Acceptance Rates
Overall Acceptance Rate 312 of 1,156 submissions, 27%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 144Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Oct 2024
Other Metrics
Citations
Cited By
View all- Sampson MKalathas MVoudouris DPapakonstantinou G(2012)Exact ESOP expressions for incompletely specified functionsIntegration10.1016/j.vlsi.2011.10.00145:2(197-204)Online publication date: Mar-2012
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in