Browse Prior Art Database

Techniques for Avoiding Multiplier Overflow in Signal Processors

IP.com Disclosure Number: IPCOM000121360D
Original Publication Date: 1991-Aug-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 6 page(s) / 218K

Publishing Venue

IBM

Related People

Carmon, DE: AUTHOR [+4]

Abstract

This article provides a solution to a problem that occurs in processors, such as digital signal processors, that use two's complement arithmetic with fractional scaling. With fractional scaling, bits in the operand have the following weighting:

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 31% of the total text.

Techniques for Avoiding Multiplier Overflow in Signal Processors

      This article provides a solution to a problem that occurs
in processors, such as digital signal processors, that use two's
complement arithmetic with fractional scaling.  With fractional
scaling, bits in the operand have the following weighting:

      With this representation, the value of the operand is in the
range,
      -2(N-1) to 2(N-1) - 1.

      Additions and subtractions of operands with fractional scaling
can produce overflows and underflows.  These are detected and
registered as status conditions using conventional techniques.  An
error condition can occur with multiplication, however, that is not
covered today by these techniques.  This error occurs when the
product of (-1) and (-1) is taken.  With fractional notation (-1)(-1)
= +1 and this number cannot be represented as a valid value.  As a
result, the multiplier output overflows, producing the erroneous
value, -1, shown below.

      The +1 value overflows to -1, the most negative value in the
N-bit code.  The +1 output value can be represented only in a scaling
system having a sign bit with significance of -2 (or more) negative.
Having a difference in significance between output and input operands
violates the principal advantage of fractional scaling; namely, that
the product has the same numeric significance as do the input
operands and their decimal points are in the same places.

      Several approaches have been used to contend with the +1
overflow anomaly.  One approach is to test the binary product for the
condition (010...0) that will cause a fractional format overflow.
This condition can then be flagged as a multiplier overflow error and
proper action taken.  Its disadvantage is that the +1 overflow must
be interpreted as an error condition and processor performance
(cycles) must be expended to cope with it.  Another solution is to
extend the significance of the output product as it is accumulated in
an accumulator register.  This approach does not provide a solution
when an N-bit representation of the accumulated products is required
that has the same significance as the operands.  The following
paragraphs describe two improved approaches for addressing multiplier
overflow that are superior to current techniques.  The selection of
which method to be used in a design will depend on characteristics of
the particular data flow used in the processor.

      The first solution to the overflow problem is to define a
procedure for representation of the overflow within the N bit data
flow.  It is based on representing the +1 as a sum of the most
positive and least positive values in the arithmetic range.  When
these values are included as part of an addition or subtraction, the
correct weighting of the overflow value will be achieved.  Fig. 1
illustrates the technique.  The operand precision is 16 bits and the
multiplier produces a 32-bit product.  The pro...