Sättigungsarithmetik
Sättigungsarithmetik oder Saturationsarithmetik 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.
Es 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 Intervall [0,255] annehmen, wobei ein höherer Wert höhere Farbsättigung bedeutet. Die A-Komponente ist der Alpha-Kanal, der bestimmt, wie „undurchsichtig“ ein Pixel ist. Auch A liegt im Intervall [0,255], wobei 0 vollständig transparent und 255 vollständig solide und undurchsichtig bedeutet.
In dem folgenden Beispiel soll nur die R-Komponente betrachtet werden, analoge Überlegungen gelten auch für die drei anderen.
Werden zwei Bilder übereinander gelegt (z. B. in einer grafischen Oberfläche), so werden die R-Komponenten der jeweiligen Pixel addiert. Der Rot-Anteil des ersten Pixels sei beispielsweise 100 und der des zweiten 50. Dann steigt der Rotanteil des „übereinandergelegten“ Pixels auf 150.
Wenn aber nun das erste Pixel einen R-Wert von 150 und das zweite einen von 200 hat, ist das Zwischenergebnis R = 350; das modulo 256 gerechnet ergibt 94. Das Problem ist offensichtlich: Die Kombination der beiden Rottöne 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 Intervall-Grenze nicht über- bzw- unterschritten, wenn ein Über(Unter)lauf vorliegt. In Saturationsarithmetik gilt also mit obigem Beispiel: 150 + 200 = 255. Und 255 + x = 255 für alle nicht-negativen x. Gleichfalls ergibt 255 − 300 nicht 211 (wie in der Modulo-Arithmetik), sondern 0. Auch hier gilt wieder 0 − x = 0 für alle nicht-negativen x.
Implementierungsmöglichkeiten
Software
Nachfolgenden ein kurzer Pseudo-Code, der zeigt, wie Sättigungsarithmetik 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 n-Bit-Zahlen addiert werden. Dazu wird ein „gewöhnlicher“ n-Bit-Addierer sowie ein 2-Wege-n-Bit-Multiplexer benutzt. 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 der Breite n Bit. 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 3-540-46801-3, S. 24,344ff