The "regularity" of a Boolean function can be exploited for decreasing its minimization time. It has already been shown that the notion of autosymmetry is a valid measure of regularity, however such a notion has been studied thus far either in the theoretical framework of self-dual Boolean functions, or for the synthesis of a particular family of three-level logic networks. In this paper we show that the degree of autosymmetry of an arbitrary function can be computed implicitly in a very efficient way, and autosymmetry can then be exploited in any logic minimization context. Our algorithms make crucial use of Binary Decision Diagrams. A set of experimental results on the synthesis of standard benchmark functions substantiates the practical relevance of our theoretical results.
Exploiting regularities for boolean function synthesis / A. Bernasconi, V. Ciriani, F. Luccio, L. Pagli. - In: THEORY OF COMPUTING SYSTEMS. - ISSN 1432-4350. - 39:4(2006 Jul), pp. 485-501.
Exploiting regularities for boolean function synthesis
V. CirianiSecondo
;
2006
Abstract
The "regularity" of a Boolean function can be exploited for decreasing its minimization time. It has already been shown that the notion of autosymmetry is a valid measure of regularity, however such a notion has been studied thus far either in the theoretical framework of self-dual Boolean functions, or for the synthesis of a particular family of three-level logic networks. In this paper we show that the degree of autosymmetry of an arbitrary function can be computed implicitly in a very efficient way, and autosymmetry can then be exploited in any logic minimization context. Our algorithms make crucial use of Binary Decision Diagrams. A set of experimental results on the synthesis of standard benchmark functions substantiates the practical relevance of our theoretical results.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.