next up previous
Next: The Entire Decomposition Strategy. Up: A New Representation of Previous: Basic Decompositions.

Goal-Oriented Reduction Decompositions.

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 tex2html_wrap_inline982 is close to the function F to be decomposed (we mean by this a high correlation of variables tex2html_wrap_inline982 and F in CDB). Function tex2html_wrap_inline982 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 tex2html_wrap_inline982 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 tex2html_wrap_inline998 .

Function tex2html_wrap_inline982 is a goal function, F is the decomposed function. tex2html_wrap_inline1004 is the correcting function.

1. If Reduct_Type_Oper = `OR' then

tex2html_wrap_inline1006 := tex2html_wrap_inline1008 ; tex2html_wrap_inline1010 .

If Reduct_Type_Oper = `AND' then

tex2html_wrap_inline1012 ; tex2html_wrap_inline1014 .

If Reduct_Type_Oper = `EXOR' then

tex2html_wrap_inline1016 ;

tex2html_wrap_inline1018 .

2. If tex2html_wrap_inline982 was a decomposable function, execute its corresponding decomposition and put the correcting function tex2html_wrap_inline1004 to OPEN stack. Otherwise, put tex2html_wrap_inline1004 to OPEN stack.

3. Put expression ( F := tex2html_wrap_inline982 Reduct_Type_Oper tex2html_wrap_inline1004 ) to DONE stack.



Marek Perkowski
Tue Nov 11 17:42:48 PST 1997