A Formal Framework for Maximum Error Estimation in Approximate Logic Synthesis

Approximate logic synthesis techniques have become popular in error-resilient systems, where accuracy requirements can be traded for improved energy efficiency. Many of these techniques operate on a circuit by substituting or removing some of its portions under a predefined error constraint; however, the research on systematic methods to determine the error induced by such transformations is still at an early stage. We propose herein a generic framework for modeling maximum error in a circuit, called partition and propagate, which is a fundamental preliminary step for ALS. This framework is based on circuit partitioning and error propagation among the subcircuits. We provide a sound, complete formal description of such framework, and we illustrate how two state-of-the-art algorithms can be subsumed by it. Moreover, we propose a novel gate-level error-modeling algorithm, which is able to identify the whole range of possible errors induced by a given approximate transformation. We compare the three strategies and illustrate the efficiency of the new error-propagation methodology, which is able to identify accurate error bounds and, hence, guide ALS techniques to more valuable solutions.