Saturation arithmetic

Saturation arithmetic is an arithmetic in which ( such as addition or multiplication) to run all operations at a fixed interval between a minimum and maximum. When the result of an operation is larger than the maximum interval, it is set to this value. A result, the interval limit therefore never exceed, but dwells also with her. So you can say, the value is saturated at the interval boundary. The same applies to the minimum, this may not be exceeded.

Examples

As an example, the interval from -100 to 100 is given. Then the following operations produce the results indicated:

  • 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 = 70

As you can see from these examples, associative and distributive laws do not apply in the Saturationsarithmetik. Therefore, it is in the abstract mathematics of secondary importance. However, it has an important function in digital computer systems and algorithms.

Application in the multimedia sector

A special importance has the Saturationsarithmetik in multimedia applications, for example in the processing of images.

For example, to be superimposed in the computer graphics two images. Each pixel is represented as a 4- tuple (R, G, B, A ), where R, G, B, the respective red, green and blue components of the color. The corresponding components can assume integer values ​​in the interval [ 0,255 ], where a higher value means higher color saturation. The A component is the alpha channel, the " opaque " a pixel is determined as. Also, A is in the interval [ 0,255 ] with 0 completely transparent and 255 completely solid and opaque.

In the following example, only the R component should be considered, the same considerations also apply to the other three.

Two images are superposed on each other (for example in a graphical user interface ), the R component of the respective pixels are added. Suppose that the red portion of the first pixel is 100 and that of the second 50 then increases the amount of red " superimposed " pixel on 150th

But what now if the first pixel has an R - value of 150 and the second 200? In the intermediate result we then R = 350, the results calculated modulo 256 94 The problem is obvious: the combination of the two is red less red than the two original pixels. This is not a meaningful result in this application.

In practice, can be " totally red " red redder than not. And " total red " is the value 255 One can say that at this value of the red channel saturated ( saturated ) is.

The solution of the problem can be reached by Saturationsarithmetik: Unlike the modulo arithmetic here the lower or upper interval limit is not over - or - below, when an (sub ) run exists. In Saturationsarithmetik therefore applies to our example: 150 200 = 255 And 255 x = 255 for all x. Likewise are 255-300 not 211 (as in modulo arithmetic), but 0 Here again 0 - x = 0 for all x.

Implementation options

Software

Following a short pseudo -Pascal code shows how Saturationsarithmetik can be displayed in the software. However, the algorithm shown is not practicable, since it presupposes that in principle is arithmetic with sufficient accuracy is available and the corresponding result is then limited only to the actual interval.

WertIn: = a b; { Actual calculation,            this is now on the interval (min, max)            mapped. WertAus contains the financial statements            the result of the calculation. }   if ( WertIn > max ) then     WertAus: = max else if ( WertIn

As an example, let us consider only the addition. There are numbers with n bits are added. For this purpose, an "ordinary " n -bit adder and a 2 -way n- bit multiplexer is used. The carry bit of the adder is supplied to the selection input of the multiplexer. To a multiplexer, the result of the adder is passed to the other, the constant 1 in the n-bit width. If the carry bit (ie an overflow has occurred ) is set, then the multiplexer switches the constant 1, that remains on the upper interval limit. If the carry bit is not set, the result of the adder is connected through.

710401
de