Logic Synthesis with AND and OR Gates in Multi-Levels:Selection of Divisors.

Selection of Divisors

Among the divisions, those with a certain type of divisor to be described in the following are called weak divisions. The objective of the weak division is the derivation of a logic network with a logic expression having a minimal total number of literals, repeatedly applying the weak division to the given logic expression until the division cannot apply to the logic expression any further. In this case, the total number of literals is intended to be an approximation of the total number of inputs to all the logic gates, although not exactly, as explained later. Thus, we should start with a logic expression in a minimal sum of products by using two-level logic minimization [1,2] before weak division in order to obtain a good result.

In the weak division, the divisor selection is the most important problem to produce a compact network because there are many divisor candidates to be found in the given logic expression and the result of the weak division depends on divisor selection. For example, the expression f = ab ∨ acd ∨ ace ∨ bce ∨ bcd in Eq. 32.1 with 14 literals has many divisor candidates, a, b, c, a ∨ b, b ∨ cd, and others. When a ∨ b is first selected as the divisor, the resultant network illustrated in Figure 32.1(b) for f = c(a ∨ b)(d ∨ e) ∨ ab with 7 literals is obtained. On the other hand, if b ∨ cd is first selected as the divisor, the resultant network for f = c(e(a ∨ b) ∨ bd) ∨ a(b ∨ cd) with 10 literals illustrated in Figure 32.1(c) is obtained, which is larger than the network illustrated in Figure 32.1(b).

Divisors can be derived by finding sub-expressions called kernels. All the kernels for the given logic expression can be found as follows.

First, all the subsets of products in the given logic expression are enumerated. Next, for each subset of products, the product of the largest number of literals that is common with all the products in this subset is found. This product of the largest number of literals is called a co-kernel. Then the sum of products, from each of which this co-kernel (i.e., the product of the largest number of literals) is eliminated is obtained as a kernel. For example, the sum of products abc ∨ abd has the co-kernel ab as the product of the largest number of literals that is common to all the products, abc and abd. The kernel of abc ∨ abd is c ∨ d. However, ab ∨ ac ∨ d has no kernels, because it has no common literals for all products. The kernel b ∨ c with co-kernel a is found when the subset of products, ab ∨ ac, is considered.

Certainly, by trying all divisor candidates and selecting the best one, we can derive a network as small as possible by the weak division. However, such an exhaustive search is too time-consuming, requiring a huge memory space. The branch-and-bound method is generally more efficient than the exhaustive search [3].

Thus, the heuristic method that the type of divisor candidates is restricted to sum of products with specific feature is proposed [2]. This method is called kernel decomposition, reducing the number of divisor candidates.

A kernel of an expression for f is the sum with at least two products such that all the products in the sum contain no common literals (e.g., ab ∨ c is a kernel, but ab ∨ ac and abc are not kernels, because all products, ab and ac, in ab ∨ ac contain a, and abc is a single product), especially, a kernel whose subsets contain no other kernels is called a level-0 kernel (e.g., a ∨ b is a level-0 kernel, but ab ∨ ac ∨ d is not a level-0 kernel because sub-expression ab ∨ ac contains kernel b ∨ c). The level of kernels is defined recursively as a level-K kernel contains at the next lower level-(K – 1) kernel (e.g., ab ∨ ac ∨ d is a level-1 kernel because it contains level-0 kernel b ∨ c).

Usually, a level-K kernel with K ≥ 1 is not used as a divisor to save processing time, because the results obtained by all level kernels as divisors are the almost same as those obtained by using only the level-0 kernels. Thus, all the kernels that are not level-0 kernels are excluded from divisor candidates.

For example, the logic expression illustrated in Figure 32.1, f = ab ∨ acd ∨ ace ∨ bce ∨ bcd, has 16 kernels as shown in Table 32.1. By eliminating all the level-1 kernels, ad ∨ ae ∨ bd ∨ be, ea ∨ eb ∨ bd and others from Table 32.1, we have the divisor candidates in Table 32.2.

The next step is the selection of one divisor from all candidates. A candidate that decreases the largest number of literals in the expression by the weak division is selected as a divisor. If there is a tie, choose one of them. The difference in the number of literals before and after the weak division by the kernel is called the weight of the kernel. In the above example, the result of the weak division by the kernel b ∨ cd is f = a(b ∨ cd) ∨ ace ∨ bce ∨ bcd. The weight of the kernel b ∨ cd is 1, because the number of literals is reduced from 14 to 13 by this division. The weight of the kernels can be easily calculated by the number of literals in kernels and co-kernels without execution of weak division, because the quotient of the division by a kernel is a product of a co-kernel and other sub-expressions. The weight of the kernels for this example is shown in Table 32.2.

Then the kernel a ∨ b is selected as a divisor with the largest weight. The expression f = ab ∨ acd ∨ ace ∨ bce ∨ bcd is divided by a ∨ b. In the next division, d ∨ e is selected and divides the expression after division by a ∨ b. Finally, the network f = c(a ∨ b)(d ∨ e) ∨ ab illustrated in Figure 32.1(b) is obtained.

These operations, enumeration of all the kernels, calculation of the weights of all kernels, selection of the largest one, and division are applied repeatedly until no kernel can be found. In this case, we can choose a different sequence of divisors, deriving a different result. But often we do not have a different result, so it may not be worthwhile to try many different sequences of divisors.

Instead of the kernel decomposition method, a faster method is proposed [4]. In this method, the divisor candidates are restricted to only 0-level kernels with two products, along with introduction of complement- sharing that when both ab ∨ab and ab ∨ab are among divisor candidates, one is realized with a logic gate while realizing the other by complementing it by an inverter (ab ∨ ab = (a ∨ b )(a ∨ b) = a b ∨ ab for this example). Although the restriction is stronger than the kernel decomposition method, the method produces smaller networks and can run faster than the kernel decomposition in many cases.