[ main page ] [ back ]

2004 : Multiple Constant Multiplication by Time-Multiplexed Mapping of Addition Chains

Author(s)
Peter Tummeltshammer
Abstract
An important primitive in the hardware implementations of linear DSP transforms like discrete cosine transform or discrete Fourier transform is a circuit, that can multiply an input value by one of several different constants. Up to now standard multiplication units were mainly used for that purpose. In this thesis a novel implementation of the circuit 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 can process the multiplication by these constants sequentially. An algorithm is being presented that can automatically generate 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 larger 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 written out to synthesizable Verilog code. The quality of the designs is evaluated after synthesis for a commercial 0.18Ám standard cell ASIC library. Therefor 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 space of problems, the addition-chain based method offers savings in circuit area. Finally, the benefit of the new approach is shown by a practical example. A face recognition system, using the discrete Fourier transform, was implemented in Verilog, showing the value of the new approach for a complex application.
Bibtex
@mastersthesis{ tummeltshammer:2004,
  author =      "Peter Tummeltshammer",
  title =       "Multiple Constant Multiplication by Time-Multiplexed Mapping of Addition Chains",
  address =     "Treitlstr. 3/3/182-1, 1040 Vienna, Austria",
  school =      "Technische Universit{\"a}t Wien, Institut f{\"u}r Technische Informatik",
  year =        "2004"
}
Download
Get dipl_deu.pdf - Adobe PDF-format, (1052.1387 KB; posted at July 09 2013)


[ main page ] [ back ]