Saturation arithmetic

Saturation arithmetic

Saturation arithmetic is a version of arithmetic in which all operations such as addition and multiplication are limited to a fixed range between a minimum and maximum value. If the result of an operation is greater than the maximum it is set ("clamped") to the maximum, while if it is below the minimum it is clamped to the minimum. The name comes from how the value becomes "saturated" once it reaches the extreme values; further additions to a maximum or subtractions from a minimum will not change the result.

For example, if the valid range of values is from -100 to 100, the following operations produce the following values:
* 60 + 43 = 100
* (60 + 43) − 150 = −50
* 43 − 150 = −100
* 60 + (43 − 150) = −40
* 10 × 11 = 100
* 99 × 99 = 100
* 30 × (5 − 1) = 100
* 30×5 − 30×1 = 70As can be seen from these examples, familiar properties like associativity and distributivity fail in saturation arithmetic. This makes it unpleasant to deal with in abstract mathematics, but it has an important role to play in digital hardware and algorithms.

Typically, early computer microprocessors did not implement integer arithmetic operations using saturation arithmetic; instead, they used the easier-to-implement modular arithmetic, in which values exceeding the maximum value "wrap around" to the minimum value, like the hours on a clock passing from 12 to 1. In hardware, modular arithmetic with a minimum of zero and a maximum of 2"n" can be implemented by simply discarding all but the lowest "n" bits.

However, although more difficult to implement, saturation arithmetic has numerous practical advantages. The result is as numerically close to the true answer as possible; it's considerably less surprising to get an answer of 127 instead of 130 than to get an answer of −126 instead of 130. It also enables overflow of additions and multiplications to be detected consistently without an overflow bit or excessive computation by simple comparison with the maximum or minimum value (provided the datum is not permitted to take on these values).

Additionally, saturation arithmetic enables efficient algorithms for many problems, particularly in digital signal processing. For example, adjusting the volume level of a sound signal can result in overflow, and saturation causes significantly less distortion to the sound than wrap-around. In the words of researchers G. A. Constantinides et al.:

Saturation arithmetic operations are available on many modern platforms, and in particular was one of the extensions made by the Intel MMX platform, specifically for such signal processing applications.

Saturation arithmetic for integers has also implemented in software for a number of programming languages including C, C++, Eiffel, and most notably Ada, which has built-in support for saturation arithmetic. This helps programmers anticipate and understand the effects of overflow better. On the other hand, saturation is challenging to implement efficiently in software on a machine with only modular arithmetic operations, since simple implementations require branches that create huge pipeline delays.

Although saturation arithmetic is less popular for integer arithmetic in hardware, the IEEE floating-point standard, the most popular abstraction for dealing with approximate real numbers, uses a form of saturation in which overflow is converted into "infinity" or "negative infinity", and any other operation on this result continues to produce the same value. This has the advantage over simple saturation that later operations which decrease the value will not end up producing a "reasonable" result, such as in the computation sqrt{x^2-y^2}.


External links

* [ SARITH: Safe ARITHmetic – A Progress Report] : Report on a saturation arithmetic component for Eiffel.

Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Saturation — or saturated generally means thoroughly full , while unsaturated means less than full. These terms may be related to: * Dew point, which is a temperature that occurs when atmospheric humidity reaches 100% and the air can hold no more moisture *… …   Wikipedia

  • Arbitrary-precision arithmetic — In computer science, arbitrary precision arithmetic indicates that calculations are performed on numbers whose digits of precision are limited only by the available memory of the host system. This contrasts with the faster fixed precision… …   Wikipedia

  • Fixed-point arithmetic — In computing, a fixed point number representation is a real data type for a number that has a fixed number of digits after (and sometimes also before) the radix point ( e.g. , after the decimal point . in English decimal notation). Fixed point… …   Wikipedia

  • Arithmétique saturée — Cette arithmétique opère dans un domaine de valeurs limité par deux bornes, disons m et M. Une opération en arithmétique saturée fournit des résultats tels que : Si le calcul donne un nombre inférieur au plus petit nombre représentable m,… …   Wikipédia en Français

  • Digital signal processor — A Digital Signal Processor chip found in a guitar effects unit. A digital signal processor (DSP) is a specialized microprocessor with an architecture optimized for the fast operational needs of digital signal processing.[1] …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • MMX (instruction set) — Pentium with MMX MMX is a single instruction, multiple data (SIMD) instruction set designed by Intel, introduced in 1996 with their P5 based Pentium line of microprocessors, designated as Pentium with MMX Technology .[1] …   Wikipedia

  • Shadow volume — Example of Carmack s stencil shadowing in Doom 3. Shadow volume is a technique used in 3D computer graphics to add shadows to a rendered scene. They were first proposed by Frank Crow in 1977[1] as the geometry describing the 3D shape of the… …   Wikipedia

  • Clipping (audio) — For shortening of voice snippets due to failures in voice activity detection, see squelch and voice activity detection. The altered peaks and troughs of the sinusoidal waveform displayed on this oscilloscope indicate the signal has been clipped.… …   Wikipedia

  • Clipping (signal processing) — An oscilloscope screen of an amplifier clipping. The amplifier should be outputting a clean sine wave with rounded tops and bottoms, but instead they are cut off flat, or clipped . Clipping is a form of distortion that limits a signal once it… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”