Approximate Logic Synthesis by Symmetrization
Anna Bernasconi1, Valentina Ciriani2 and Tiziano Villa3
1Dipartimento di Informatica Università di Pisa, Italy
anna.bernasconi@unipi.it
2Dipartimento di Informatica Università degli Studi di Milano, Italy
valentina.ciriani@unimi.it
3Università degli Studi di Verona, Italy
tiziano.villa@univr.it
ABSTRACT
Approximate synthesis is a recent trend in logic synthesis that changes some outputs of a logic specification to take advantage of error tolerance of some applications and reduce complexity and consumption of the final implementation. We propose a new approach to approximate synthesis of combinational logic where we derive its closest symmetric approximation, i.e., the symmetric function obtained by injecting the minimum number of errors in the original function. Since BDDs of totally symmetric functions are quite compact, this approach is particularly convenient for BDD-based implementations, such as networks of MUXes directly mapped from BDDs. Our contribution is twofold: first we propose a polynomial algorithm for computing the closest symmetric approximation of an incompletely specified Boolean function with an unbounded number of errors; then we discuss strategies to achieve partial symmetrization of the original specification while satisfying given error bounds. Experimental results on classical and new benchmarks confirm the efficacy of the proposed approach.
