MINIMIZATION OF FIXED-POLARITY AND XOR CANONICAL NETWORKS/

A method for extracting the cubes of the generalised Reed-Muller (GRM) form of a Boolean function with a given polarity is presented. The me thod does not require exponential space and time complexity and it ach ieves the lower-bound time complexity. The proof of the method's corre ctness constitutes the first half of the paper. Also, a separate heuri stic algorithm to find the optimal polarity that requires the least nu mber of cubes in the GRM representation is proposed. The algorithm is fast and derives the polarity for variables and extracts all cubes sim ultaneously. It is based on the concept of a Boolean centre for vertic es, which emulates the centre of gravity concept in geometry. The expe rimental results for the heuristic algorithm agree strongly with the a uthors observations and analysis.