Concepedia

Subexpression sharing in filters using canonic signed digit multipliers

IEEE Transactions on Circuits and Systems II Analog and Digital Signal Processing · 1996 · 587 citations · 15 references

DOI

TL;DR

Constant multiplication is typically implemented with shift‑and‑add operations, and using Canonical Signed Digit (CSD) representation minimizes the number of additions; in operator networks such as FIR filters, sharing common subexpressions can reduce the total operator count by up to 50%. This paper investigates how optimizing CSD multiplier design by sharing subexpressions can lower addition counts. The study explores optimization techniques for CSD multipliers, focusing on subexpression sharing within networks of operators. Mathematical analysis shows that sharing the two most common subexpressions can yield a 33 % reduction in the number of additions.

Abstract

A common way of implementing constant multiplication is by a series of shift and add operations. As is well known, if the multiplier is represented in Canonical Signed Digit (CSD) form, then the number of additions (or subtractions) used will be a minimum. This paper examines methods for optimizing the design of CSD multipliers, and in particular the gains that can be made by sharing subexpressions. In the case where several multipliers are present in a network of operators, for instance in an FIR filter, the savings achieved by identifying common subexpressions can be as much as 50% of the total number of operators. The asymptotic frequency of the most common subexpression is analyzed mathematically, and it is shown that sharing the two most common subexpressions can be expected to lead to a 33% saving of the number of additions.