Functional composition: A new paradigm for performing logic synthesis

This paper presents the functional composition (FC), a new paradigm for combinational logic synthesis. FC is based on the following principles: (1) representation of logic functions as a bonded pair of functional/structural representations; (2) it starts from a set of initial functions; (3) simpler functions are associated to create more complex ones; (4) a partial order that enables dynamic programming is respected; (5) a set of allowed functions is maintained to reduce execution time/memory consumption. We present functional composition algorithms variants for Boolean factoring, AIG rewriting, minimum decision chain computation and SOP generation.