next up previous
Next: Round-Robin Parallelism Up: Bit-Serial Multiplication Previous: Bit-Serial Multiplication

Fixed Coefficients

When the C values are fixed by the application (an important special case) it becomes possible to eliminate any explicit representation of them from the circuit. One way to take advantage of this is to specify the constants bit vectors representing the coefficients and allow standard logic simplification software to eliminate all the AND gates together with many of the intermediate stages of the adder tree. This is less effective than one might hope, however, because the dedicated carry propagation logic has a rigid structure and because the carry bits propagating through intermediate stages will tend to ``fill in'' eliminated bit positions. To take full advantage of fixed bits in the C values requires a specialized approach.

One such approach leads to a class of designs which were shown by Mintzer to be well suited to cell-based programmable logic implementation. These distributed arithmetic designs are a specialization of the serial-k architecture. The n coefficients are partitioned into sufficiently small subsets tex2html_wrap_inline653 so that the pre-computed sums tex2html_wrap_inline655 may be efficiently retrieved from a lookup table structure. Carry propagation is eliminated in the first rank of the computing structure and, more importantly, zero bits in the coefficients lead to ``don't care'' conditions in the lookup table logic that can be efficiently exploited by the logic compiler.

More recently Aoki, Sawada, and Higuchi demonstrated a construction of a generalized signed-weight representation for an arbitrary fixed vector of coefficients that results in carry propagation-free adders. In the present paper we do not assume the coefficients are fixed and so we will not delve further into these techniques. We note, however, that our technique can be applied to summing the partitioned sums obtained by exploiting constant coefficients. The ideas are orthogonal.

In [?], Liu, Wu, Raghupathy and Chen examine the problem of DSP circuit performance from the algorithmic level, where they are free to choose to do something better than computing the sum of products. Their examples provide a motivating sense of the scale of interesting DSP problems.


next up previous
Next: Round-Robin Parallelism Up: Bit-Serial Multiplication Previous: Bit-Serial Multiplication

Stephen W. Nuchia
Mon Dec 11 17:02:42 CST 2000