Efficient computation in vlsi with distributed arithmetic
Wayne P. Burleson, Louis L. Scharf · 1989
Inner-product computations form the basis of many digital signal processing algorithms. Distributed arithmetic is a method of inner product computation that uses table-lookup and addition in place of multiplication. Distributed arithmetic has previously been shown to produce novel and seemingly efficient architectures for a variety of signal processing computations; however the methods of design, analysis and comparison have been rather ad hoc. We propose a systematic method for synthesizing optimal VLSI architectures using distributed arithmetic. A partition of the inner product computation at the word and bit-level produces a computation consisting of lookups and additions. We study two classes of algorithms to implement this computation, regular iterative algorithms and tree algorithms, each of which can be expressed in the form of a dependency graph. We use linear maps to assign computations to processors in space and time. Expressions are developed for the area, latency, period and arithmetic precision for a particular partition and space/time map of the dependency graph. We use these expressions to formulate a constrained optimization problem over a large class of architectures. We extend previously published precision analyses of the distributed arithmetic algorithm, and introduce a formalism for measuring input/output complexity. We apply distributed arithmetic to conventional methods of inner-product computation and show how area, latency and period may be traded-off while maintaining constant precision. The basic ideas of distributed arithmetic are extended to other computations, other number systems and other algebras. Implementation issues such as I/O, programmability and testing are explored. We present novel applications of distributed arithmetic to polynomial evaluation, signed digit number systems, and Winograd's algorithm for matrix multiplication.