In this paper, we present a general approach which specifically targets reduction of redundant computation in common d'igital signal processing (DSP) tasks such as filtering and matrix multiplication. The main idea presented in this work is to show that such tasks can be expressed as multiplication of vectors by scalars and fast multiplication can be achieved by sharing computation in such operations. The multiplication schemes considerably reduce redundant computation by decomposing the vectors in a manner which results in maximal computation sharing, thereby, resulting in a faster and potentially low-power implementation. Two decomposition approaches are presented, one based on a greedy decomposition and the other based on fixed-size lookup rule which lead to two multiplication architectures for scaling of vectors. Analysis of the proposed implementations shows a speed-up by a factor of up to 3 over a carry save array multiplier. Analog simulation of an example 8-bit multiplier shows a speed advantage by a factor of 1.85 and a power disadvantage of 1.9 over a conventional carry save array multiplier. Using voltage scaling, the power consumption of the example multiplier can be reduced to 56% of the carry save array multiplier.

Date of this Version

March 1999