In data with very many don't cares, EXORCISM is unable to find the best pattern. As an example, let us consider function defined as follows: ON = {0X10, 1X01}, OFF = {0X01, 1111, 1010}. When cube 0X10 is extended to 0X1X, and cube 1X01 is extended to 1X0X, these two extended cubes can be correctly exorlinked. However, when there are many don't cares surrounding an ON-cube, the program does not know which of them to select. (Extension cube of cube is cube with any subset of literals removed - including none and all ). For instance, if cube 1X01 is extended to 1X0X and cube 0X10 is extended to 0XX0, the minimization is more difficult. If DC-cubes 0011 and 0111 were merged to DC-cube 0X11, then this DC-cube can be exorlinked with 0XX0 to cubes 0XXX and 0X01. Next 0X01 and 1X0X can be reshaped to 0X00 and XX0X. Finally it can be found using disjoint sharp operation that 0X00 is included in DC set, so the final result is XX0X and 0XXX.
We separate cubes used in synthesis into ON cubes, ON/DC cubes and OFF/DC-cubes. ON cube includes only true minterms. It is then a cube such that # ON = . ON/DC cube includes true minterms and don't cares. It is then a cube such that OFF = . OFF/DC cube includes false minterms, and possibly don't cares. # denotes sharp operation.
In this section we propose a new method of combining Espresso and EXORCISM into a single program, called EXORCISM_DC.
The algorithm given below, using Espresso, creates larger ON, DC and ON/DC cubes to be used by EXORCISM. It iterates for several starting points and finally, when no improvement is possible, it returns the best of all ESOP and SOP solutions. Thus, its result is never worse than that of either Espresso or EXORCISM.
EXORCISM_DC
Given: ON, OFF.
1. DC := Espresso[ 1 # (ON OFF ].
2. SOP := Espresso(ON, OFF).
3. ON := Random_Disjoint(Espresso(ON)).
4. ESOP := Random_Disjoint(SOP).
ON/DC := ON Random_Choice(DC,ON,ESOP).
ESOP_new := Exorcism(ON/DC,DC).
Remove from ESOP_new all OFF/DC cubes.
if cost(ESOP_new) < cost(ESOP)
then ESOP := ESOP_new.
5. [ON/DC, DC] := Random_Reshape[ON, DC, ESOP].
6. Iterate times steps 4 - 5.
7. If improvement in steps 4 - 6 then go to 4.
8. Iterate times steps 3 - 7.
9. If improvement in steps 3 - 8 then go to 3.
10. If cost(SOP) < cost(ESOP)
then return [ "SOP", SOP, cost(SOP) ].
else return [ "ESOP", ESOP, cost(ESOP) ].
Above, Espresso is the well-known U.C. Berkeley minimizer that can be called with several data formats, including completely specified format with set ON, and incompletely specified format with sets ON and OFF. Exorcism is our minimizer that can be called with any ESOP (including disjoint ON) as the first argument and any set DC as the second argument. Random_Disjoint is a program that takes a set of cubes and transforms it to random set of disjoint cubes. Every time this program is called it produces different set of disjoint cubes which is functionally equivalent to its argument. Random_Choice takes a random subset of cubes from DC that are expected to be exorlinked with cubes from ESOP. Random_Reshape reshapes each set ON and DC separately.