It has been considered difficult to obtain the minimum AND-EXOR expression of a given function with six variables in a practical computing time. In this paper, a faster algorithm of minimizing AND-EXOR expressions is proposed. We believe that our algorithm can compute the minimum AND-EXOR expressions of any six-variable and some seven-variable functions practically. In this paper, we first present a naive algorithm that searches the space of expansions of a given n-variable function f for a minimum expression of f. The space of expansions are generated by using all combinations of (n-1)-variable product terms. Then, how to prune the branches in the search process and how to restrict the search space to obtain the minimum solutions are discussed as the key point of reduction of the computing time. Finally a faster algorithm is constructed by using the methods discussed. Experimental results to demonstrate the effectiveness of these methods are also presented.

This paper presents a new method that efficiently generates all of the kernels of a sum-of-products expression. Its main feature is the memorization of the kernel generation process by using a graph structure and implicit cube set representations. We also show its applications for common logic extraction. Our extraction method produces smaller circuits through several extensions than the extraction method based on two-cube divisors known as best ever.

This paper shows the best operators for sum-of-products expressions. We first describe conditions of functions for product and sum operations. We examine all two-variable functions and select those that meet the conditions and then evaluate the number of product terms needed in the minimum sum-of-products expressions when each combination of selected product and sum functions is used. As a result of this, we obtain three product functions and nine sum functions on three-valued logic. We show that each of three product functions can express the same functions and MODSUM function is the most suitable for reduction of product terms. Moreover, we show that similar results are obtained on four-valued logic.

This paper describes Kleenean coefficients that are a subset of Kleenean functions for use in representing multiple-valued logic functions. A conventional multiple-valued sum-of-products expression uses product terms that are the MIN of literals and constants. In this paper, a new sum-of-products expression is allowed to sum product terms that also include variables and complements of variables. Since the conventional sum-of-products expression is complete, so also is the augmented one. A minimization method of the new expression is described besed on the binary Quine-McCluskey algorithm. The result of computer simulation shows that a saving of the number of implicants used in minimal expressions by approximately 9% on the average can be obtained for some random functions. A result for some arithmetic functions shows that the minimal solutions of MOD radix SUM, MAX and MIN functions require much fewer implicants than those of the standard sum-of-products expressions. Thus, this paper clarifies that the new expression has an advantage to reduce the number of implicants in minimal sum-of-products expressions.