Symbolic method for simplifying AND-EXOR representations of Boolean functions using a binary-decision technique and a genetic algorithm

Abstract

An algorithm called XORGA is presented which minimises Boolean multi-output logic functions as multilevel AND-EXOR networks of two-input logic gates. It carries out symbolic simplification, and works from the bottom of a binary variable decision tree to the top, with variable choice determined using a genetic algorithm. Since the algorithm is multilevel in nature, it delivers more compact circuits than two-level ESOP minimisation algorithms, such as EXMIN2. It also finds more economical representations than the fixed polarity Reed-Muller method.