Browse Prior Art Database

Method of Factoring Boolean Functions

IP.com Disclosure Number: IPCOM000039616D
Original Publication Date: 1987-Jul-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Brayton, RK: AUTHOR

Abstract

A technique of factoring Boolean functions is described. Employed is the concept of finding the factorization of an incompletely specified Boolean function which is nearly minimal in terms of the number of literals needed to represent the function. The method is based on a technique called "Strong Factorization" (SF) which uses "strong division" which enables factorization to be accomplished by means of recursive factoring, so that "don't care" conditions are considered in the factoring of an algorithm. The concept is considered to be particularly useful in transistorized gate architecture, whereby factorization can save logic area space, delay and power in the implementation of a function. Since factorization can be utilized to decompose a Boolean function into subparts, each of the subparts can then be implemented separately.

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

Page 1 of 2

Method of Factoring Boolean Functions

A technique of factoring Boolean functions is described.

Employed is the concept of finding the factorization of an incompletely specified Boolean function which is nearly minimal in terms of the number of literals needed to represent the function.

The method is based on a technique called "Strong Factorization" (SF) which uses "strong division" which enables factorization to be accomplished by means of recursive factoring, so that "don't care" conditions are considered in the factoring of an algorithm. The concept is considered to be particularly useful in transistorized gate architecture, whereby factorization can save logic area space, delay and power in the implementation of a function. Since factorization can be utilized to decompose a Boolean function into subparts, each of the subparts can then be implemented separately.

If the factorization is nearly minimal, then the implementations is nearly minimal in terms of transistors or gates required to build the function. Some of the ways to factor a function, include dividing by a literal and repeating this until progress ceases, as in the term AB+AC = A(B+C), called quick factor (QF). Another method is to find a kernal and divide by the kernal, repeating the process until no kernals remain, then QF the remainder, as in the following example: AE+BCE+AF+BCF+BDE+BDF+AB = (E+F)(A+B)(C+D)+AB This is called exact factoring (XF). Both the QF and the XF methods treat the Boolean functions as an algebraic monomial so that any Boolean simplifications to be done must be done before factorization on the disjunctive form representing the function. If any "don't care" conditions are to be taken into account, they must be implemented during the Boolean minimization of the disjunctive form. In the QF and the XF methods, the quality of the factorization depends on which literal or kernal is chosen first. Usually this choice is done by heuristics, which try to use the most "valuable" factor. Once chosen, the multiplier of this factor is obtained using "weak" division, corresponding to normal algebraic factorization. The function is then recursively factored as f=km+r, where k is the factor chosen, m is the multiplier and r is the remainder. Each is a Boolean function, but in both QF and XF they are treated as algebraic monomials for recursive factorization of f. The factorization is obtained by recursively applying the chosen factorization method to each of k, m, and r to obtain: XF(f) = XF(k) XF(m) + XF(r). The technique described herein, called "Strong Factorization" (SF) employs "strong division", as opposed to "weak division", to accomplish the factorization. Although the first step in the algorithm is the same as in QF or XF, that of...