P Tummeltshammer, M. Pueschel, A. Steininger, C. Überhuber:
"Constant Multiplication Methods";
Report for Research Report 107/2004, Technische Universität Wien, Institut für Technische Informatik, Treitlstraße 3, A-1040 Vienna, Austria;
An important primitive in the hardware implementations of linear DSP transforms like the discrete Fourier transform or discrete cosine transforms is a circuit that multiplies an input value by one out of a set of several different constants. Up to now standard multiplication units were mainly used for that purpose. In this report a novel hardware implementation based on combining the addition chains of the constituent constants is proposed. They form a composite addition chain, consisting of addition units and multiplexers that carry out the multiplication by the constants sequentially. An algorithm is being presented that automatically generates such a circuit for a given set of constants. The algorithm exploits similarities in the addition chains' structure to create a circuit of minimum size. Up to now these similarities were specifically restricted to so called fundamentals, mainly used for designing FIR filters. The new approach introduces a way to exploit the addition chains' structure to a much higher degree, applying the technique of time-multiplexing. This way the number of addition units in the composite addition chain is kept constant, resulting in an overall area reduction. The resulting circuit can be output to synthesizable Verilog code. The quality of the designs is evaluated after synthesis for a commercial 0.18Ám standard cell ASIC library. Therefore the area efficiency of this addition-chain based approach is compared against a straightforward approach based on a constant table and a full multiplier. It can be shown that for an interesting and relevant class of problems, the addition chain based method leads to substantial savings in circuit area.
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.