An approach to approximate computing: Logic transformations for one-minterm changes in specification

摘要

Here we consider one special situation for approximate computing. Given a specification, S, in a truth table and its corresponding multi-level logic circuit implementation, I, S is changed to S' by only changing the truth table value for exactly one minterm from 0 to 1 or 1 to 0. We would like to transform I into I' in such a way that I' is equivalent to S' This is a sort of basic operations for approximate logic synthesis, as the functional changes are minimal (only for one minterm). We experimentally show that even if we change functions for all of the gates in the circuit, I, without changing their input signals (their immediate fanins), i.e., no topological changes, the circuit can never become equivalent to S' for all the cases we tried. However, if we allow to change the function of only one gate in the last level of the circuit, I, and allow to change its input signals as well, the circuit becomes equivalent to S' around 13% of the cases in average with in average additional 1.1 inputs to the gate in the last level. We also experimentally show that one minterm changes in truth tables are, comparing with one and two products changes where all minterms inside the products are changed, the most difficult problems to accommodate from the viewpoint of Engineering Change Order (ECO) or logic debugging, when the circuits are implemented as multi-level logic.