cants, and combining them to create subsequent sets,
until either no more implicants are generated, or the
full depth of implicants have been generated. In this
algorithm, the MakeInitialImplicants procedure generates
the implicants from every row of r using the
row t which is picked. The t row can be picked at random,
although the actual implementation simply uses
the first row in the relation. The MakeNextImplicants
procedure is a simple loop which uses two iterators
to go through a set, and for every pair of implicants
found with the same set of classifiers and minterms
differing only in one place, a new implicant is generated,
with the particular bit of the minterm (where
the difference was obtained) as ‘*’ and marking the
original two implicants as used. The MakePrimeImplicants
procedure goes through this collection of sets
I, and collects all the unused implicants.
The MakeEssentialImplicants algorithm selects a
minimal set of essential implicants from the Prime implicants
generated. A greedy algorithm is then used
to generate the essential prime implicants. For each
of the essential prime implicants created, a full rule
can be created for every implicant for which the set
of classifiers is 1. For all the implicants with a set of
classifiers more than 1, CoreCircle is recursively called
with the tuples covered by such implicants.
Circle is implemented in Java, configurable to
use any JDBC-compliant database in the backend
(or ODBC compliant databases using Sun’s JDBCODBC
bridge). The system was tested with Microsoft
Access, Microsoft SQL server, and Oracle. The current
implementation is configurable through a config