SUBEXPRESSION SHARING IN FILTERS USING CANONIC SIGNED-DIGIT MULTIPLIERS

A common way of implementing constant multiplication is by a series of shift and add operations, As is well known, if the multiplier is repr esented in Canonical Signed Digit (CSD) form, then the number of addit ions (or subtractions) used will be a minimum, This paper examines met hods for optimizing the design of CSD multipliers, and in particular t he gains that can be made by sharing subexpressions. In the case where several multipliers are present in a network of operators, for instan ce in an FIR filter, the savings achieved by identifying common subexp ressions can be as much as 50% of the total number of operators, The a symptotic frequency of the most common subexpression is analyzed mathe matically, and it is shown that sharing the two most common subexpress ions can be expected to lead to a 33% saving of the number of addition s.