5

Saturation Arithmetic

This chapter explains how saturation arithmetic can be used to optimize multiple word-length designs. Section 5.1 first motivates our approach and covers some background material. Section 5.2 contains a discussion of the overheads in terms of system area and speed associated with saturation arithmetic implementations. After introducing some necessary definitions in Section 5.3, a technique for analytic estimation of saturation arithmetic noise is presented in detail in Section 5.4. This noise estimation procedure forms the basis of an extension, presented in Section 5.5, to the optimization heuristic discussed in the previous chapter, to jointly optimize signal word-lengths and scalings. This algorithm has been implemented as part of the Synoptix system, and the results obtained are presented and discussed in Section 5.6. The chapter ends with conclusions in Section 5.7.

5.1 Overview

In a standard implementation of a DSP system, when adding two numbers using two’s complement representation, there is a possibility of overflow. In the two’s complement representation, overflow results in a ‘wrap-around’ phenomenon, where attempts to represent positive numbers just outside the representable range result in their interpretation as large negative numbers, and vice versa. The result can be a catastrophic loss in signal-to-noise ratio. Signals in digital signal processing designs are therefore usually either scaled appropriately to avoid overflow for all but the most extreme input vectors, or saturation arithmetic is used. Saturation arithmetic introduces extra hardware to avoid the wrap-around, replacing it with saturation to either the largest positive number or the largest negative number representable at the adder output.

In microprocessor based DSP, hardware support for saturation modes is usually available, and the decision on whether saturation arithmetic should be used is typically left to the programmer, for example in the TMS320C6200

80 5 Saturation Arithmetic

DSP [TI] or the MMX extensions to the Pentium [PW96]. For direct implementation in hardware, the choice of whether or not to use saturation arithmetic is particularly important due to the associated cost of the extra saturation logic in area and delay.

For LTI systems, if 1 scaling is used, as in Chapter 4, overflow is not an issue and therefore standard arithmetic is to be preferred. In some cases 1 scaling can be overly pessimistic, catering for situations that are extremely rarely encountered with practical input signals. Overly pessimistic signal scaling can lead to a number of most significant bits (MSBs) in a datapath being left unused. This is true particularly in the case of filters with long impulse responses. Under these circumstances an alternative scaling scheme could be used to reduce the datapath width and therefore save implementation area and power consumption, however overflow becomes a distinct possibility. It is in these situations that saturation arithmetic becomes a useful implementation scheme, to limit the impact of these overflows on the overall system signal-to-noise ratio.

A reasonable design approach, when creating a saturation arithmetic implementation of a DSP system, is to determine signal scaling through simulation. Input vectors are supplied to the system, and the peak value reached by each internal signal is recorded. Signals are then scaled to ensure that the full dynamic range a orded by the signal representation would be used under excitation with the given input vectors. In contrast, this chapter presents an optimization technique suitable for LTI systems, based on analytic noise models.

5.2 Saturation Arithmetic Overheads

Saturation arithmetic is not a cost-free design methodology. The implementation of a saturation arithmetic component has some area and delay overheads associated with it, when compared to the equivalent non-saturation component.

Traditionally, saturation arithmetic has been associated with the addition operator [Mit98]. However there are also circumstances where saturation may be appropriate following a multiplication. Consider for example a (7, 0) signal which uses its full dynamic range, and therefore has a peak of ±(1 − 2−7). We may multiply this signal by a (7, 1) coe cient with value 1 + 2−6. The resulting signal will therefore have a peak of ±(1+2−6 −2−7 −2−13), although the (14, 1) format for this signal could represent peaks of up to ±(21 − 2−13), approximately double the range. It is intuitive, therefore, that a saturation by one bit after the multiplication would rarely saturate to its peak values, and choosing a (13, 0) representation for the result rather than (14, 1) may result in a more e cient implementation at only a small cost in saturation error. The technique described in this chapter generalizes the approach, to

5.2 Saturation Arithmetic Overheads

81

allow saturators to be inserted after any operator: primary input, addition, delay or constant coe cient multiplication.

Another standard approach to saturation arithmetic is to saturate only a single most significant bit (MSB). A standard saturation would therefore convert an (n, p) representation into an (n − 1, p − 1) representation. This design approach derives from having a single n-bit accumulator. The approach taken in this chapter does not constrain the design space in this way, and indeed can saturate di erent signals to di erent degrees, in order to trade o implementation area with implementation error.

The key component introduced and studied in this chapter is therefore a saturator, as defined in Definition 5.1 and illustrated in Fig. 5.1 for a k-bit saturator applied to an (n + 1)-bit two’s complement signal. The symbols used follow IEEE standard [IEE86]: specifically ‘>=1’ refers to an ‘or’ gate, ‘G1’ to the common select line of the two-input multiplexers, and inversion is indicated by a triangle. From this architecture, a simple area cost model can be deduced for the saturator: A(n, k) = c1k+c2n, where c1 and c2 are empirically derived constants which may vary with target architecture. The cost function used in Section 4.2 must therefore be modified to incorporate this additional cost. Of course, the output of every operator need not be saturated: following the notation of Section 4.1.1, saturation is never needed if pj = pj for a signal j, because the full output range is required. In addition for an LTI system, if there is no signal j such that pj is less than the value suggested by 1 scaling, then the system is free from overflow and the saturation area model need not be used, even if there is a signal j with pj < pj .

Definition 5.1. A saturator is a circuit component, as illustrated in Fig. 5.1, for converting from format (n, p) to format (n − k, p − k). The parameter k is referred to as the degree of the k-bit saturator.

Another di erence to the area model used in Chapter 4, is that the previously cost-free computation nodes inport and fork may now have a cost associated with them due to any saturation nonlinearities at their outputs. fork is of particular interest, since for a minimal area implementation, a fork node should be implemented as a cascade of saturators as shown in Fig. 5.2.

In addition to the area overhead of saturation arithmetic, there will also be some delay penalty associated with the saturator. Fig. 5.3 illustrates how the placed and routed propagation delay across a saturation arithmetic constant coe cient multiplier varies with input word-length for a fixed coe cient value and for 1-bit saturation. This figure shows a very significant timing overhead for saturation arithmetic, up to 73%.

To summarize, saturation arithmetic provides advantages in terms of allowing controlled overflows that may not dramatically a ect the output signal- to-noise ratio. However these advantages are provided at the cost of a somewhat larger and slower circuit compared to standard two’s complement arithmetic for the same binary point locations and word-lengths. In a given imple-

82 5 Saturation Arithmetic

	xn						x0
Input:	S		...
			yn-k				y0
Output:				S		...

&

xn

xn-1 .

.

xn-k

>=1

xn

xn-1 .

.

xn-k

>=1

G1

_		_
xn		1			y0
x0		1
_		_
xn		1			y1
x1		1
			.
			.
			.
_
		_
xn
		1			yn-k-1
xn-k-1		1
xn					yn-k

Fig. 5.1. A two’s complement saturator from (n, p) to (n − k, p − k)

(8,1)		(7,0)
		(6,-1)	(8,1)		(7,0)		(6,-1)
		(6,-1)
(a) a fork with saturated				(b) its minimal area
outputs					implementation

Fig. 5.2. Cascaded minimal area implementation of a fork saturation