Low multiplicative complexity logic minimisation over the basis (AND, XOR, NOT)

Logic minimisation over the basis (AND, XOR, NOT) has received much attention in recent years. Heuristic logic minimisation methods based on the notion of multiplicative complexity c ∧ (f) have reported impressive results for well-explored applications such as cryptographic S-Boxes. However, the heuristic involves randomised selections in part of its algorithm. Studying the heuristic from a consistency perspective is carried out here. Enhancements to improve different aspects of the algorithm are proposed. The benefits of the proposed enhancements are demonstrated through experimental results in comparison with the original algorithm.