Browse Prior Art Database

Fast Method for Finding Largest Prime Implicant Containing a Given Implicant of a Boolean Function

IP.com Disclosure Number: IPCOM000046558D
Original Publication Date: 1983-Aug-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Brayton, RK: AUTHOR

Abstract

In finding a minimum cover of a Boolean function, a cube of a given cover is typically lifted or raised to be a prime implicant. This requires many steps, and typically the largest prime is not obtained. A method which almost always finds the largest prime in a single step is shown. Let c => f (f is a Boolean function, and c is a cube). Assume that f is given and consists of cubes d1, d2, ..., dm A cube c is represented by a vector (c1, c2, ..., cn), where ci = 1 if the ith variable appears in the cube, ci = 0 if the negation of the ith variable appears, and ci = 2 otherwise. Construct the matrix A = (aij), where (Image Omitted) Theorem Let columns k1, k2, ..., ke be a minimum set such that A restricted to these columns has at least one 1 in each row. Then p = (p1,...

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 100% of the total text.

Page 1 of 1

Fast Method for Finding Largest Prime Implicant Containing a Given Implicant of a Boolean Function

In finding a minimum cover of a Boolean function, a cube of a given cover is typically lifted or raised to be a prime implicant.

This requires many steps, and typically the largest prime is not obtained. A method which almost always finds the largest prime in a single step is shown. Let c => f (f is a Boolean function, and c is a cube). Assume that f is given and consists of cubes d1, d2, ..., dm A cube c is represented by a vector (c1, c2, ..., cn), where ci = 1 if the ith variable appears in the cube, ci = 0 if the negation of the ith variable appears, and ci = 2 otherwise. Construct the matrix A = (aij), where

(Image Omitted)

Theorem Let columns k1, k2, ..., ke be a minimum set such that A restricted to these columns has at least one 1 in each row. Then p = (p1,...,pn is a maximum prime containing c, where

(Image Omitted)

The following algorithm is an extremely fast way of finding a minimum column cover of A almost all the time. a Set K = 0

b If A is empty, quit.

c Choose the set of rows of A with minimum row count

(X min).

d If min = 1, set K=K [jm], where the set [jm] is

the set of column indices appearing in the minimum

row-count rows. Delete rows of A covered by K.

Go to b.

e If min >1, set K=K [jmax], where jmax is a column

of [jm], i.e., jmax e [jm], with a maximum column

count. Delete rows of A covered by K. Go to b.

1