We will use two stacks. The OPEN stack stores the sub-functions to be realized, from which the one evaluated as the easiest to realize is selected for the realization first. The DONE stack stores the completely realized subfunctions. These functions can be re-used during reduction decompositions. Also, DONE is used to reconstruct the entire circuit when the OPEN stack becomes empty.
The Goal-Oriented Reduction Decompositions are used in two cases:
1. When some already realized function is close to the function F to be decomposed
(we mean by this a high correlation of variables
and F in CDB).
Function
becomes then a goal function.
2. When one of the previously attempted (Immediate or Basic) decompositions of F was "nearly possible".
We mean by this that
many cofactors in this decomposition had patterns corresponding to a given type of decomposition.
In such case, the method from [16] is used to create the
goal function and select the Reduct_Type_Oper, which defines the type
of the decomposition.
In both above cases, the procedure Reduction is next called, to execute the reduction, possibly also to execute the decomposition, and put new subfunctions to OPEN.
Procedure .
Function is a goal function, F is the decomposed function.
is the correcting function.
1. If Reduct_Type_Oper = `OR' then
:=
;
.
If Reduct_Type_Oper = `AND' then
;
.
If Reduct_Type_Oper = `EXOR' then
;
.
2. If was a decomposable function, execute its
corresponding decomposition and put the correcting function
to OPEN stack. Otherwise, put
to OPEN stack.
3. Put expression ( F := Reduct_Type_Oper
) to DONE stack.