Symmetric Minimal Covering Problem and Minimal PLA's with Symmetric Variables

Abstract

This paper first discusses the symmetric property of the minimal covering problem in terms of group theory and then the use of this property in the branch-and-bound method for solving the problem. Computational results on solving sample problems are shown to demonstrate the improvement of computational efficiency of the branch-and-bound method by the utilization of the symmetric property. The sample problems contain the minimal sum derivation of symmetric switching functions, as an application to the design of minimal programmable logic arrays (PLA's). It is shown that when the minimal covering problem derived for the given switching function has symmetric permutations, the given switching function may not be symmetric; although when the given switching function is symmetric, the minimum covering problem obtained from the function is symmetric. The branch-and-bound method based on the symmetric property can be applied not only to symmetric switching functions but also to switching functions which are not symmetric, if the corresponding minimal covering problems have symmetric permutations. The method can be also applied to minimal covering problems which arise outside the minimal sum derivation problems for switching functions.