Sättigungsarithmetik

Bildaddition mit und ohne Saturationsarithmetik

Sättigunsarithmetik ist eine Arithmetik, in der alle Operationen (wie Addition oder Multiplikation) in einem festen Intervall zwischen einem Minimum und Maximum ablaufen. Wenn das Resultat einer Operation größer ist als das Intervall-Maximum, so wird es auf diesen Wert gesetzt. Ein Resultat kann die Intervallgrenze also niemals überschreiten, verweilt aber auch bei ihr. Man kann also sagen, der Wert ist bei der Intervallgrenze gesättigt. Analoges gilt für das Minimum, dieses kann nicht unterschritten werden.

Beispiele

Als Beispiel sei das Intervall von -100 bis 100 gegeben. Dann erzeugen die folgenden Operationen die angegebenen Resultate:

• 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

Wie man an diesen Beispielen sehen kann, gelten Assoziativ- und Distributivgesetz in der Saturationsarithmetik nicht. Daher ist sie in der abstrakten Mathematik von untergeordneter Bedeutung. Sie besitzt jedoch eine wichtige Funktion in digitalen Rechenanlagen und Algorithmen.

Anwendung im Multimedia-Bereich

Eine besondere Bedeutung besitzt die Saturationsarithmetik im Multimedia-Bereich, beispielsweise bei der Bearbeitung von Bildern.

Sollen beispielsweise in der Computergrafik zwei Bilder übereinander gelegt werden. Jedes Pixel ist als ein 4-Tupel (R,G,B,A) dargestellt, wobei R,G,B die entsprechenden rot, grün und blau Anteile der Farbe sind. Die entsprechenden Komponenten können ganzzahlige Werte im Interval (0,255) annehmen, wobei ein höherer Wert höhere Farbsättigung bedeutet. Die A-Komponente ist der Alpha-Kanal, der bestimmt wie "durchsichtig" ein Pixel ist. Auch A liegt im Interval (0,255) mit 0 vollständig transparent und 255 vollständig solide und undurchsichtig.

In dem folgenden Beispiel soll nur die R-Komponente betrachtet werden, analoge Überlegungen gelten auch für die 3 anderen.

Werden zwei Bilder übereinander gelegt (z.B. in einer grafischen Oberfläche), so werden die R-Komponenten der jeweiligen Pixel addiert. Nehmen wir an, der Rot-Anteil des ersten Pixels sei 100 und der des zweiten 50. Dann steigt der Rotanteil des "übereinandergelegten" Pixels auf 150.

Was aber nun, wenn das erste Pixel einen R-Wert von 150 und das zweite von 200 hat? Im Zwischenergebnis haben wir dann R = 350, das modulo 256 gerechnet ergibt 94. Das Problem ist offensichtlich: die Kombination der beiden rot ist weniger rot als die beiden ursprünglichen Pixel. Das ist in diesem Anwendungsfall kein sinnvolles Ergebnis.

In der Praxis kann rot nicht röter als "total rot" werden. Und "total rot" ist der Wert 255. Man kann sagen, dass bei diesem Wert der Rot-Kanal gesättigt (saturiert) ist.

Die Lösung des Problems ist mit Saturationsarithmetik zu erreichen: Anders als bei der Modulo-Arithmetik wird hier die untere bzw. obere Interval-Grenze nicht über- bzw- unterschritten, wenn ein Über(Unter)lauf vorliegt. In Saturationsarithmetik gilt also mit unserem Beispiel: 150 + 200 = 255. Und 255 + x = 255 für alle x! Gleichfalls gibt 255 - 300 nicht 45 (wie bei Modulo Arithmetik) sondern 0. Auch hier gilt wieder 0 - x = 0 für alle x.

Implementierungsmöglichkeiten

Software

Nachfolgenden ein kurzer-Pseudo-Pascal Code, der zeigt, wie Saturationsarithmetik in Software abgebildet werden kann. Der gezeigte Algorithmus ist allerdings nicht praxistauglich, da er voraussetzt, dass prinzipiell Arithmetik mit hinreichender Genauigkeit zur Verfügung steht und das entsprechende Ergebnis dann erst auf das eigentliche Intervall eingegrenzt wird.

WertIn := a + b; { eigentliche Berechnung,
          dieses wird nun auf das Intervall (min,max)
          abgebildet. WertAus enthält im Abschluss
          das Ergebnis der Berechnung.}
 
if (WertIn > max) then
   WertAus := max
else
if (WertIn < min) then
   WertAus := min
else
   WertAus := WertIn

Hardware

Als Beispiel sei hier nur die Addition betrachtet. Es sollen Zahlen mit n-Bit addiert werden. Dazu wird benutzt ein "gewöhnlicher" n-Bit Addierer sowie ein 2-Wege n-Bit Multiplexer. Das Carry-Bit des Addierers wird an den Selektionseingang des Multiplexers geführt. An den einen Multiplexereingang wird das Ergebnis des Addierers geführt, an den anderen die Konstante 1 in n-Bit Breite. Wenn das Carry-Bit gesetzt ist (also ein Überlauf aufgetreten), dann schaltet der Multiplexer die Konstanten 1 durch, bleibt also immer an der oberen Intervallgrenze. Ist das Carry-Bit nicht gesetzt, so wird das Ergebnis des Addierers durchgeschaltet.

Literatur

• Uwe Brinkschulte, Theo Ungerer: Mikrocontroller und Mikroprozessoren. Springer 2007, ISBN 3540468013, S.24,344ff