DPALS: A dynamic programming-based algorithm for two-level approximate logic synthesis

Approximate circuit design is an emerging paradigm in which a designer deliberately changes the specified Boolean function to reduce area, delay, and/or power consumption of a circuit. This paper focuses on the synthesis of approximate logic circuits (or ALS) under a given error constraint. In particular, we consider ALS for a two-level design under an error rate constraint. A dynamic programming-based algorithm is proposed to find a nearly optimal approximate function by identifying the most promising set of cubes to be added to the on-set of the original function. Then, an off-the-shelf two-level logic synthesis tool is applied to further optimize the sum-of-product (SOP) expression. The experimental results show that the literal reduction is close to the optimal solution when the error rate constraint is tight and that more than 50% literal reduction is achieved for error rate below 0.8% for an 8-bit adder and a square root circuit.