A fast method to derive minimum SOPs for decomposable functions
Pages 585 - 590
Abstract
This paper shows that divide-and-conquer derives a minimum sum-of-products expression (MSOP) of functions that have an AND bi-decomposition when at least one of the sub-functions is orthodox. This extends a previous result showing that divide-and-conquer derives the MSOP of the AND bi-decomposition of two orthodox functions. We show that divide-and-conquer does not always produce an MSOP when neither function is orthodox. However, our experimental results show that, in this case, it derives a near minimal SOP. At the same time, our approach significantly reduces the time needed to find an MSOP or near minimal SOP. Also, we extend our results to functions that have a tri-decomposition.
References
[1]
R. K. Brayton, G. D. Hachtel, C. T. McMullen, and A. Sangiovanni-Vincentelli, Logic Minimization Algorithms for VLSI Synthesis, Norwall, MA, Kluwer Academic Publishers, April 1984.
[2]
J. T. Butler, "Analysis and design of fanout-free networks of positive symmetric gates," Jour. of the ACM, pp. 481--498, July 1978.
[3]
J. P. Hayes, "The fanout structure of switching functions," Jour. of the ACM, pp. 551--571, October 1975.
[4]
C. L. Liu, Elements of discrete mathematics, McGraw-Hill, 1977.
[5]
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.
[6]
A. Mischenko and T. Sasao, "Large-scale SOP minimization using decomposition and functional properties," 40th Design Automation Conference, Anaheim, CA, pp. 471--477, June 2-6, 2003.
[7]
A. Odlyzko, "On covering a product of sets with products of subsets," Discrete Mathematics, pp. 373--380, 1973.
[8]
W. J. Paul, "Realizing Boolean functions on disjoint set of variables," Theoretical Computer Science 2, pp. 383--396, 1976.
[9]
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.
[10]
T. Sasao, Switching Theory for Logic Synthesis, Kluwer Academic Pub., p. 95, Boston, London and Dordrecht, 1999.
[11]
T. Sasao and J. T. Butler, "On the minimization of SOPs for bi-decomposable functions," Asia and South Pacific Design Automation Conference, (ASP-DAC'2001), Yokohoma, Japan, pp. 219--224, Jan. 30-Feb. 2, 2000.
[12]
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.
[13]
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.
Recommendations
On the minimization of SOPs for bi-decomposition functions
ASP-DAC '01: Proceedings of the 2001 Asia and South Pacific Design Automation ConferenceA 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 ...
Minimum Distance between Bent and Resilient Boolean Functions
IWCC '09: Proceedings of the 2nd International Workshop on Coding and CryptologyThe minimum distance between bent and resilient functions is studied. This problem is converted into two problems. One is to construct a special matrix, which leads to a combinatorial problem; the other is the existence of bent functions with specified ...
A new method for secondary constructions of vectorial bent functions
AbstractIn 2017, Tang et al. have introduced a generic construction for bent functions of the form , where g is a bent function satisfying some conditions and h is a Boolean function. Recently, Zheng et al. (Discret Math 344:112473, 2021) ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- IPSJ: Information Processing Society of Japan
- IEEE Circuits and Systems Society
- SIGDA: ACM Special Interest Group on Design Automation
- IEICE: Institute of Electronics, Information and Communication Engineers
Publisher
IEEE Press
Publication History
Published: 27 January 2004
Check for updates
Qualifiers
- Article
Conference
ASPDAC04
Sponsor:
- IPSJ
- SIGDA
- IEICE
ASPDAC04: Asia and South Pacific Design Automation Conference 2004
January 27 - 30, 2004
Yokohama, Japan
Acceptance Rates
Overall Acceptance Rate 466 of 1,454 submissions, 32%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 155Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 17 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in