NDLI: Three-level logic minimization based on function regularities

Content Provider	IEEE Xplore Digital Library
Author	Bernasconi, A. Ciriani, V. Luccio, F. Pagli, L.
Copyright Year	1982
Abstract	We exploit the "regularity" of Boolean functions with the purpose of decreasing the time for constructing minimal three-level expressions, in the sum of pseudoproducts (SPP) form recently developed. The regularity of a Boolean function f of n variables can be expressed by an autosymmetry degree k (with 0 /spl les/ k /spl les/ n). k = 0 means no regularity, that is we are not able to provide any advantage over standard synthesis. For k /spl ges/ 1 the function f is said to be autosymmetric, and a new function f/sub k/ depending on n - k variables only, called the restriction of f, is identified in time polynomial in the number of points of f. The relation between f and f/sub k/ is discussed in depth to show how a minimal SPP form for f can be build in linear time from a minimal SPP form for f/sub k/. The concept of autosymmetry is then extended to functions with don't care conditions, and the SPP minimization technique is duly extended to such functions. A large set of experimental results is presented, showing that 61% of the outputs for the functions in the classical ESPRESSO benchmark suite are autosymmetric. The minimization time for such functions is critically reduced, and cases otherwise intractable are solved. The quality of the corresponding circuits, measured with some well established cost functions, is also improved. Finally, we discuss the role and meaning of autosymmetric functions, and why a great amount of functions of practical interest fall in this class.
Sponsorship	IEEE Council on Electronic Design Automation IEEE Circuits and Systems Society
Starting Page	1005
Ending Page	1016
Page Count	12
File Size	767084
File Format	PDF
ISSN	02780070
Volume Number	22
Issue Number	8
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2003-08-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Minimization methods Boolean functions Circuit synthesis Logic circuits Polynomials Cost function Design optimization Logic design Arithmetic
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Electrical and Electronic Engineering Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Synthesis of SPP three-level logic networks using affine spaces

Efficient Boolean division and substitution using redundancy addition and removing

Permissible functions for multioutput components in combinational logic optimization

Optimization of Imprecise Circuits Represented by Taylor Series and Real-Valued Polynomials

Multi-level logic minimization using implicit don't cares

Computer-Aided Minimization Procedure for Boolean Functions

Fast three-level logic minimization based on autosymmetry

Fast factorization method for implicit cube set representation

Exact two-level minimization of hazard-free logic with multiple-input changes

Three-level logic minimization based on function regularities

Similar Documents

Synthesis of SPP three-level logic networks using affine spaces

Efficient Boolean division and substitution using redundancy addition and removing

Permissible functions for multioutput components in combinational logic optimization

Optimization of Imprecise Circuits Represented by Taylor Series and Real-Valued Polynomials

Multi-level logic minimization using implicit don't cares

Computer-Aided Minimization Procedure for Boolean Functions

Fast three-level logic minimization based on autosymmetry

Fast factorization method for implicit cube set representation

Exact two-level minimization of hazard-free logic with multiple-input changes

Three-level logic minimization based on function regularities