Implicit Prime Cover Computation: An Overview

Abstract

A set of products is a prime cover of a Boolean function f if it is made of prime implicants of f , and if the sum of its products covers f . Finding a prime cover, an irredundant prime cover, or a minimal prime cover of a function f is a problem that arises in several fields of computer science, for instance in logic synthesis, automated reasoning, realiability analysis, and some optimization problems. This paper shows how the three prime cover computation problems mentioned above can be efficiently solved using implicit manipulations of sets of products. 1 Introduction Computing a prime cover, an irredundant prime cover, or a minimal prime cover of a Boolean function has several applications in computer science. In logic synthesis, an irredundant prime cover, or better, a minimal prime cover, provides the user with an efficient 2-level logic implementation of a single or multi output Boolean function [2, 24, 14]. In reliability analysis, prime covers are a way for either exhaustive...