Skip to Content

MULTICON: Multiplierless Design of Low-Complexity and High-Speed DSP Systems

0
Your rating: None
Tool Name (abbreviation): 
MULTICON
Author(s): 
Levent Aksoy, -, PT
(unregistered) Author(s): 
Paulo Flores (INESC-ID/IST TU Lisbon)
José Monteiro (INESC-ID/IST TU Lisbon)
Eduardo Costa (UCPEL)

The multiplication of data samples with constant coefficients is a ubiquitous operation and performance bottleneck in many Digital Signal Processing (DSP) systems, such as, digital Finite Impulse Response (FIR) filters, Discrete Cosine Transforms (DCTs), filter banks, and error correcting codes. Since the realization of a multiplication operation in hardware is expensive in terms of area, delay, and power dissipation and the constants to be multiplied by variable(s) are determined by the DSP algorithms beforehand, the constant multiplications are generally realized in a shift-adds architecture where each constant multiplication is realized using addition, subtraction, and shift operations. Hence, the fundamental optimization problem is defined as finding the minimum number of addition and subtraction operations that realize the constant multiplications. Over the years, many efficient high-level algorithms have been introduced for the multiplierless design of constant multiplications. However, the optimization of the number of operations does not always yield a design with the minimum area at gate-level. Thus, the high-level algorithms should take into account the gate-level implementation cost of each addition and subtraction operation considering the design platform, i.e., ASIC or FPGA. Moreover, performance is also a crucial parameter in many DSP systems and circuit area is generally expandable in order to achieve a given performance target. Although the delay parameter is dependent on several implementation issues, such as placement and routing, the delay of a shift-adds design of constant multiplications is generally considered in terms of the number of adder-steps, which denotes the maximal number of adders and subtracters in series. Hence, to find the optimal tradeoff between area and delay, the high-level algorithms should take into account both the gate-level implementation costs of operations and the adder-step of the design. Furthermore, power consumption has become a matter of concern with the increasing popularity of portable electronic devices that include many DSP systems. As indicated in the switching activity and power dissipation estimation models, power consumption in the multiplierless design of constant multiplications is highly related with the depth of each operation and its gate-level area at gate-level. Hence, the high-level algorithms should consider these metrics in order to reduce the power dissipation. In the University Booth of DATE12, we would like to present our high-level algorithms designed for the multiplierless realization of constant multiplications considering the area, delay, and power dissipation parameters. We will demonstrate the efficiency of high-level algorithms at both high-level and gate-level on DSP systems, such as FIR filters and DCTs, compared with the previously proposed algorithms. This work is partially supported by the Portuguese Foundation for Science and Technology (FCT) research project PTDC/EIA-EIA/103532/2008 Multicon - Architectural Optimization of DSP Systems with Multiple Constants Multiplications. Our expertise on this research area can be found in the Multicon project website.

Project Information
Project Acronym: 
MULTICON
Project Start: 
Thu, 01/01/2009
Project End: 
Sat, 06/30/2012
Project Funding ID: 
PTDC/EIA-EIA/103532/2008
Project Description: 
The main goal of this research project is the development of new models and algorithms for the optimization of Multiple Constant Multiplications (MCM) architectures. Most of existing algorithms simply minimize the number of adders and subtracters used in MCM blocks. However, the complexity of an MCM operation can be reduced significantly when the high-level algorithms consider the gate-level implementation of addition and subtraction operations. Moreover, the total delay of MCM blocks is also an important requirement that has been ignored in most optimization models. The developed algorithms should incorporate area and delay in a common optimization model for MCM blocks and be tuned for each MCM instance in order to reduce the total problem search space. Furthermore, the proposed architectures should have the capability to activate only the hardware elements of the MCM that are required for computation of a given constant multiplication. Hence, major saving in power consumption are expected by reducing the global switching activity in the MCM.
Tag your tool
Keywords: 
Multiplierless design of constant multiplications
high-level synthesis algorithms
gate-level area optimization
optimization of area under a delay constraint
design of DSP systems