NDLI: Cube-Based Synthesis of ESOPs for Large Functions

Content Provider	IET Digital Library
Author	Zhang, Qiaowen Wang, Pengjun Hu, Jiang Zhang, Huihong
Abstract	This study focuses on low-complexity synthesis of Exclusive-or sum-of-products expansions (ESOPs). A scalable cube-based method, which only uses iterative executions of cube intersection and subcover minimization for cube set expressions, is presented to obtain quasi-optimal ESOPs for completely specified multi-output functions. For deriving canonical Reed-Muller (RM) forms, four conversion rules of cubes are proposed to achieve fast conversion between a canonical form and an Exclusiveor sum-of-products (ESOP) or between different canonical forms. Numerical examples are given to verify the correctness of cube-based minimization and conversion methods. The proposed methods have been implemented in C language and tested on a large set of MCNC benchmark functions (ranging from 5 to 201 inputs). Experimental results show that, compared with existing methods, ours can reduce the number of cubes by 27% and save the CPU time by 74% on average in the final solution of minimization, and consume less time as well during the conversion process. As a whole, our methods are efficient in terms of both memory space and CPU time and can be able to deal with very large functions.
Starting Page	527
Ending Page	534
Page Count	8
ISSN	10224653
Volume Number	27
e-ISSN	20755597
Issue Number	Issue 3, May (2018)
Alternate Webpage(s)	https://digital-library.theiet.org/content/journals/cje/27/3
Alternate Webpage(s)	https://digital-library.theiet.org/content/journals/10.1049/cje.2018.01.006
Journal	Chinese Journal of Electronics
Publisher Date	2018-05-01
Access Restriction	Open
Rights Holder	© Chinese Institute of Electronics
Subject Keyword	Algebra Boolean Function C Language Canonical Form Canonical Reed-Muller Forms Combinatorial Mathematics Computational Complexity Conversion Method Conversion Process Conversion Rules CPU Time Cube Intersection Cube Set Expressions Cube-based Synthesis Exclusive-or Sum-of-Product Expansions High Level Languages Low-complexity Synthesis MCNC Benchmark Function Minimisation Multioutput Function Optimisation Technique Quasioptimal ESOPs Subcover Minimization
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Electrical and Electronic Engineering

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

Analysis and diagnosis of stuck at and bridging faults in reed muller canonical exclusive or sum of product circuits

A Computer Algorithm for Minimizing Reed-Muller Canonical Forms

POA-FPRMs: Power Optimization Approach of Fixed Polarity Reed-Muller Expressions for Incompletely Specified Boolean Functions

Reed–Muller Canonical Forms in Multivalued Logic

Boolean Functions Simplification Algorithm of O(n) Complexity

On Generalized Reed-Muller Expansions

Fast OFDD-based minimization of fixed polarity Reed-Muller expressions

Generalized Inclusive Forms—New Canonical Reed-Muller Forms Including Minimum ESOPs

Representation of Boolean Quantum Circuits as Reed-Muller Expansions

Cube-Based Synthesis of ESOPs for Large Functions

Similar Documents

Analysis and diagnosis of stuck at and bridging faults in reed muller canonical exclusive or sum of product circuits

A Computer Algorithm for Minimizing Reed-Muller Canonical Forms

POA-FPRMs: Power Optimization Approach of Fixed Polarity Reed-Muller Expressions for Incompletely Specified Boolean Functions

Reed&#8211;Muller Canonical Forms in Multivalued Logic

Boolean Functions Simplification Algorithm of O(n) Complexity

On Generalized Reed-Muller Expansions

Fast OFDD-based minimization of fixed polarity Reed-Muller expressions

Generalized Inclusive Forms—New Canonical Reed-Muller Forms Including Minimum ESOPs

Representation of Boolean Quantum Circuits as Reed-Muller Expansions

Cube-Based Synthesis of ESOPs for Large Functions

Reed–Muller Canonical Forms in Multivalued Logic