Function Extraction from Arithmetic Bit-Level Circuits

Abstract

The paper describes a method to derive a polynomial function computed by an arithmetic bit-level circuit. The circuit is modeled as a bit-level network composed of adders and logic gates and computation performed by the circuit is viewed as a flow of binary data through the network. The problem is cast as a Network Flow problem and solved using standard algebraic techniques. Extraction of the arithmetic function from the circuit is accomplished by transforming the expression at the primary outputs into an expression at the primary inputs. Experimental results show application of the method to certain classes of large arithmetic circuits.