We define and study a new class of regular Boolean functions called D-reducible. A D-reducible function, depending on all its n input variables, can be studied and synthesized in a space of dimension strictly smaller than n. We show that the D-reducibility property can be efficiently tested, in time polynomial in the representation of f, that is, an initial SOP form of f. A D-reducible function can be efficiently decomposed, giving rise to a new logic form, that we have called DredSOP. This form is shown here to be generally smaller than the corresponding minimum SOP form. Our experiments have also shown that a great number of functions of practical importance are indeed D-reducible, thus validating the overall interest of our approach.
Dimension-reducible Boolean functions based on affine spaces / A. Bernasconi, V. Ciriani. - In: ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS. - ISSN 1084-4309. - 16:2(2011), pp. 13.1-13.21. [10.1145/1929943.1929945]
Dimension-reducible Boolean functions based on affine spaces
V. CirianiUltimo
2011
Abstract
We define and study a new class of regular Boolean functions called D-reducible. A D-reducible function, depending on all its n input variables, can be studied and synthesized in a space of dimension strictly smaller than n. We show that the D-reducibility property can be efficiently tested, in time polynomial in the representation of f, that is, an initial SOP form of f. A D-reducible function can be efficiently decomposed, giving rise to a new logic form, that we have called DredSOP. This form is shown here to be generally smaller than the corresponding minimum SOP form. Our experiments have also shown that a great number of functions of practical importance are indeed D-reducible, thus validating the overall interest of our approach.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.