Optimum functional decomposition using encoding
Rajeev Murgai, Robert K. Brayton, Alberto L. Sangiovanni-Vincentelli · 1994
In this paper, we revisit the classical problem of functional decomposition [1, 2] that arises so often in logic synthesis.One basic problem that has remained largely unaddressed to the best of our knowledge is that of decomposing a function such that the resulting sub-functions are simple, i.e., have small numberof cubes or literals.In this paper, we show h o w to solve this problem optimally.W e show that the problem is intimately related to the encoding problem, which is also of fundamental importance in sequential synthesis, especially state-machine synthesis.We formulate the optimum decomposition problem using encoding.In general, an input-output encoding formulation has to be employed.However, for eld-programmable gate array architectures that use look-up tables, the input encoding formulation suces, provided we use minimum-length codes.The last condition is really not a constraint, since each extra code bit means that an extra table has to be used (and that could be expensive).The unused codes are used as don't cares for simplifying the sub-functions.We compare the original implementation of functional decomposition, which ignores the encoding problem, with the new version that uses encoding while doing decomposition.We obtain an average improvement o f o v er 20% on a set of standard benchmarks for look-up table architectures.