The Entire Decomposition Strategy.

The comprehensive Decomposition strategy, Algorithm 3, includes all above partial decomposition schemes among its special cases. It is based on the following principles:

1. Using various fast and greedy decompositions is better for a very strongly unspecified function than a single method of high complexity. Try simple decompositions first. If various previous attempts failed then try more complex circuit structures and decomposition types.

2. Use DFC (see [14] for definition) to measure the costs of partial solutions and be thus able to compare them.

3. The user can control the algorithm using several parameters.

Besides OPEN and DONE, Algorithm 3 uses the EVAL stack, which stores the decomposition attempts, in order to compare them one with another and select the best decomposition. In making choice decisions, the following parameters of are taken into account: number of true minterms, number of false minterms, number of true cubes, number of false cubes, sets A, B, C together with best patterns for them. number of input variables, % of ON Pattern columns, % of OFF Pattern columns, % of DC Pattern columns, % of Pattern columns, % of Approximate ON Pattern columns, % of Approximate OFF Pattern columns, % of Approximate DC Pattern columns, % of Approximate Pattern columns, cost parameters, distance, number_of_bound_sets, and other.

Algorithm 3. Total Decomposition Strategy.

1. Put F to OPEN.

2. Take the easiest to realize function from OPEN.

Call it FT.

3. Using PAR1 number of different sets A, B, C

try Immediate Decompositions to FT in this order:

OR, AND, EXOR, Complex_Gates, Ashenhurst.

a) If the decomposition exists, execute it for FT,

using stacks OPEN and DONE.

b) If there exist some close function

(of distance smaller than DIST1) to FT in DONE,

then call Reduction(FT, , Reduct_Type_Oper),

to reduce function FT to .

c) If there exist a decomposition of function ,

of distance DIS2 from FT

then call Reduction(FT, , Reduct_Type_Oper)

to reduce function FT to ,

and execute decomposition of .

4. Using PAR2 number of different sets A, B, C,

try Basic Decompositions in this order:

Curtis ( = PAR3), PUB ( = PAR4).

5. If none of the above worked, and good weak patterns

have been found in the previous stages,

execute respective Weak Decompositions.

6. If OPEN = then return the SOLUTION

else go to 2.