Article

On the minimization of SOPs for bi-decomposition functions

Authors:

Tsutomu Sasao,

Jon T. ButlerAuthors Info & Claims

ASP-DAC '01: Proceedings of the 2001 Asia and South Pacific Design Automation Conference

Pages 219 - 224

https://doi.org/10.1145/370155.370327

Published: 30 January 2001 Publication History

Get Access

Abstract

A function f is AND bi-decomposable if it can be written as f (X1,X2) = h1(X1)h2(X2). In this case, a sum-of-products expression (SOP) for f is obtained from minimum SOPs (MSOP) for h1 and h2 by applying the law of distributivity. If the result is an MSOP, then the complexity of minimization is reduced. However, the application of the law of distributivity to MSOPs for h1 and h2 does not always produce an MSOP for f. We show an incompletely specified function of n(n-1) variables that requires at most n products in an MSOP, while 2(n-1) products are required by minimizing the component functions separately. We introduce a new class of logic functions, called orthodox functions, where the application of the law of distributivity to MSOPs for component functions of f always produces an MSOP for f . We show that orthodox functions include all functions with three or fewer variables, all symmetric functions, all unate functions, many benchmark functions, and few random functions with many variables.

References

[1]

R. K. Brayton, G. D. Hactel, C. T. Mc-Mullen, and A. Sangiovanni-Vincentelli, Logic Minimization Algorithms for VLSI Synthesis, Norwall, MA, Kluwer Academic Publishers, April 1984.

Digital Library

Google Scholar

[2]

R. S. Michalski and Z. Kulpa, "A system of programs for the synthesis of switching circuits using the method of disjoint stars," Proceedings of IFIP Congress, pp. 61-65, April 1971.

Google Scholar

[3]

A. Odlyzko, "On covering a product of sets with products of subsets," Discrete Mathematics, pp. 373-380, 1973.

Digital Library

Google Scholar

[4]

W. J. Paul, "Realizing Boolean functions on disjoint set of variables," Theoretical Computer Science 2, pp. 383-396, 1976.

Crossref

Google Scholar

[5]

R. L. Rudell and A. Sangiovanni-Vincentelli, "Multiple-valued minimization for PLA optimization," IEEE Trans. Computer- Aided Design, vol. CAD-6, No. 5 pp. 727-749, September 1987.

Google Scholar

[6]

T. Sasao and M. Matsuura, "DECOMPOS: An integrated system for functional decomposition," 1998 International Workshop on Logic Synthesis, Lake Tahoe, pp. 471-477, June 1998.

Google Scholar

[7]

B. Voight and I. Wegener, "A remark on minimal polynomials of Boolean functions," CSL'88, 2nd Workshop on Computer Science Logic Proceedings, pp. 372-383, 1989.

Digital Library

Google Scholar

Cited By

View all

Emelyanov PPonomaryov D(2015)Algorithmic issues of AND-decomposition of boolean formulasProgramming and Computing Software10.1134/S036176881503003241:3(162-169)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1134/S0361768815030032
Sasao TButler JImai M(2004)A fast method to derive minimum SOPs for decomposable functionsProceedings of the 2004 Asia and South Pacific Design Automation Conference10.5555/1015090.1015250(585-590)Online publication date: 27-Jan-2004
https://dl.acm.org/doi/10.5555/1015090.1015250
Mishchenko ASasao TGetreu IFix LLavagno L(2003)Large-scale SOP minimization using decomposition and functional propertiesProceedings of the 40th annual Design Automation Conference10.1145/775832.775872(149-154)Online publication date: 2-Jun-2003
https://dl.acm.org/doi/10.1145/775832.775872
Show More Cited By

Index Terms

On the minimization of SOPs for bi-decomposition functions

Recommendations

Derivatives of bent functions in connection with the bent sum decomposition problem
Abstract
In this paper, we investigate when a balanced function can be a derivative of a bent function. We prove that every nonconstant affine function in an even number of variables n is a derivative of $(2^{n - 1} - 1)$ $∣ B_{n - 2} ∣^{2}$ bent functions, where $B_{n}$ is the set ...
Cubical CAMP for minimization of Boolean functions
VLSID '96: Proceedings of the 9th International Conference on VLSI Design: VLSI in Mobile Communication

The paper presents QCAMP, a cube-based algorithm for minimization of single Boolean functions. The algorithm does not generate all the prime cubes, nor does it require the Off-set of the function. Two significant contributions of QCAMP are the UNATE ...
Exploiting functional properties of boolean functions for optimal multi-level design by bi-decomposition
Artificial intelligence in logic design

This paper introduces the theory of bi-decomposition of Boolean functions. This approach optimally exploits functional properties of a Boolean function in order to find an associated multilevel circuit representation having a very short delay by using ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ASP-DAC '01: Proceedings of the 2001 Asia and South Pacific Design Automation Conference

January 2001

662 pages

ISBN:0780366344

DOI:10.1145/370155

Chairman:
Satoshi Goto
NEC Corp., Kawasaki, Japan

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 January 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ASP-DAC01

Sponsor:

IEICE
IPSJ
SIGDA
IEEE HK CAS

ASP-DAC01: Asia and South Pacific Design Automation Conference 2001

Yokohama, Japan

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
128
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Emelyanov PPonomaryov D(2015)Algorithmic issues of AND-decomposition of boolean formulasProgramming and Computing Software10.1134/S036176881503003241:3(162-169)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1134/S0361768815030032
Sasao TButler JImai M(2004)A fast method to derive minimum SOPs for decomposable functionsProceedings of the 2004 Asia and South Pacific Design Automation Conference10.5555/1015090.1015250(585-590)Online publication date: 27-Jan-2004
https://dl.acm.org/doi/10.5555/1015090.1015250
Mishchenko ASasao TGetreu IFix LLavagno L(2003)Large-scale SOP minimization using decomposition and functional propertiesProceedings of the 40th annual Design Automation Conference10.1145/775832.775872(149-154)Online publication date: 2-Jun-2003
https://dl.acm.org/doi/10.1145/775832.775872
Coudert OSasao T(2002)Two-Level Logic MinimizationLogic Synthesis and Verification10.1007/978-1-4615-0817-5_1(1-27)Online publication date: 2002
https://doi.org/10.1007/978-1-4615-0817-5_1

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Derivatives of bent functions in connection with the bent sum decomposition problem

Cubical CAMP for minimization of Boolean functions

Exploiting functional properties of boolean functions for optimal multi-level design by bi-decomposition