Asia Pacific Conference on Circuits and Systems · 2003 · 13 citations · 6 references
ComputingComputer ScienceAlgorithmsOptimizationTheory Of ComputationCombinatorial OptimizationComputational ComplexityOptimization TheorySelective PruningBoolean Function MinimizationBoolean MinimizationMinimization Of Boolean FunctionsPartial ProductsSearch Space Pruning
We propose a faster algorithm of minimizing AND-EXOR expressions. While it has been considered difficult to obtain the minimum AND-EXOR expression of a given function with six variables in a practical computing time, 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.
6
Easily Testable Realizations ror Logic Functions
S.M. Reddy · IEEE Transactions on Computers · 1972 · 278 citations
On the complexity of mod-2l sum PLA's
T. Sasao, Philipp W. Besslich · IEEE Transactions on Computers · 1990 · 180 citations