NDLI: BOOM-a heuristic Boolean minimizer

Content Provider	IEEE Xplore Digital Library
Author	Hlavicka, J. Fiser, P.
Copyright Year	2001
Description	Author affiliation: Dept. of Comput. Sci. & Eng., Czech Tech. Univ., Prague, Czech Republic (Hlavicka, J.)
Abstract	We present a two-level Boolean minimization tool (BOOM) based on a new implicant generation paradigm. In contrast to all previous minimization methods, where the implicants are generated bottom-up, the proposed method uses a top-down approach. Thus instead of increasing the dimensionality of implicants by omitting literals from their terms, the dimension of a term is gradually decreased by adding new literals. Unlike most other minimization tools like ESPRESSO, BOOM does not use the definition of the function to be minimized as a basis for the solution, and thus the original coverage influences the solution only indirectly through the number of literals used. Most minimization methods use two basic phases introduced by Quine-McCluskey, known as prime implicant (PI) generation and the covering problem solution. Some more modern methods, like ESPRESSO, combine these two phases, reducing the number of PIs to be processed. This approach is also used in BOOM, where the search for new literals to be included into a term aims at maximum coverage of the output function. The function to be minimized is defined by its on-set and off-set, listed in a truth table. Thus the don't care set, often representing the dominant part of the truth table, need not be specified explicitly. The proposed minimization method is efficient above all for functions with a large number of input variables while only few care terms are defined. The minimization procedure is very fast, hence if the first solution does not meet the requirements, it can be improved in an iterative manner. The method has been tested on several different kinds of problems, like the MCNC standard benchmarks or larger problems generated randomly.
Starting Page	439
Ending Page	442
File Size	507369
Page Count	4
File Format	PDF
ISBN	0780372476
ISSN	10923152
DOI	10.1109/ICCAD.2001.968667
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2001-11-04
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Minimization methods Computer science Electronic mail Input variables Circuit testing Benchmark testing Switching circuits Digital circuits Field programmable gate arrays Programmable logic arrays
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Computer Science Applications 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

Circuit clustering for delay minimization under area and pin constraints

Functionally Linear Decomposition and Synthesis of Logic Circuits for FPGAs

ITEM: an if-then-else minimizer for logic synthesis

Canonical restricted mixed-polarity exclusive sums of products

Complexity of the lookup-table minimization problem for FPGA technology mapping

Area minimization of MPRM circuits

Boolean matching for LUT-based logic blocks with applications to architecture evaluation and technology mapping

Robust FPGA resynthesis based on fault-tolerant Boolean matching

Heuristic minimization of multiple-valued relations

BOOM-a heuristic Boolean minimizer

Similar Documents

Circuit clustering for delay minimization under area and pin constraints

Functionally Linear Decomposition and Synthesis of Logic Circuits for FPGAs

ITEM: an if-then-else minimizer for logic synthesis

Canonical restricted mixed-polarity exclusive sums of products

Complexity of the lookup-table minimization problem for FPGA technology mapping

Area minimization of MPRM circuits

Boolean matching for LUT-based logic blocks with applications to architecture evaluation and technology mapping

Robust FPGA resynthesis based on fault-tolerant Boolean matching

Heuristic minimization of multiple-valued relations

BOOM-a heuristic Boolean minimizer