Logic Synthesis with AND and OR Gates in Multi-Levels:Limitation of Weak Division.

Limitation of Weak Division

Corresponding to these expressions, we have two different logic networks, as shown in Figure 32.2. The function f2 is derived by division by a divisor above but actually cannot be obtained by the weak division. Thus, the logic network for f2 is labeled as the result by strong division in Figure 32.2. Strong division is rewriting of logic expressions using any form, including the complement of a sub-expression and accordingly has far greater possibilities than the division explained so far.

The results of division are evaluated by the number of literals contained in each of the obtained expressions. This number is an approximation of the total number of fan-ins of gates in networks in the following sense: inputs to a logic gate from other gates are not counted as literals. In Figure 32.2, the number of literals of f1 is 9, and the number of literals of f2 is 6. But in the logic network for f1, an input to each of three AND gates in Figure 32.2, for example, is not counted as a literal. Counting them, the total number of fan-ins of all logic gates in the logic network for f1, which is 15 in Figure 32.2, is larger than the total number of fan-ins of all gates in the logic network for f2, 8.