Astronomy and Space Flight, Astronomie und Raumfahrt und dies und das... :: Thema anzeigen

Achtung: Dies ist eine historische Web-Site. Aktuell ist https://rainer.gerhards.net/ (engl) bzw https://www.rainer-gerhards.de/ (deutsch). Alle dynamischen Funktionen, Formulare etc auf dieser Seite sind abgeschaltet.
Datenschutzerklärung Impressum

Astronomy and Space Flight, Astronomie und Raumfahrt und dies und das...

Rechenanlagen - Was ist Saturationsarithmetik?

rgerhards - 27.11.2008, 12:04 Uhr
Titel: Was ist Saturationsarithmetik?

Der Einfachheit halber sei hier einfach einmal von positiven Ganzzahlen ausgegangen, also sei $n \in \mathbb{N}$ .

In der Theorie ist $\mathbb{N}$ natürlich unendlich (Satz des Archimedes). In der Praxis haben wir es jedoch im Regelfall immer mit endlichen n zu tun.

Ein Beispiel sei der Kilometerzähler im Auto. Der verfügt oft über 5 Stellen. Er kann also Werte im Interval (0, 99999) darstellen. Was passiert nun, wenn wir bereits 99.999 km gefahren sind und noch einen weiteren km fahren? Der km-Zähler "läuft über" und zeigt wieder den Wert 0 an. Wenn man noch die guten alten mechanischen Zähler mit ihren Zahnrädern und den Ziffern darauf vor Augen hat, dann ist das auch sehr natürlich.

Mathematisch handelt es sich um eine Modulo-Rechung und zwar wird der km-Stand modulo 100.000 gerechnet. D.h. es wird nur der Rest der Division der eigentlichen Zahl durch 100.000 beachtet. Alle diese Reste bilden eine sogenannte Äquivalenzklasse (so, genauer kann ich das im Moment aber noch nicht ausführen). Um im Beispiel zu bleiben. Der km-Stand sei 112.314km. Dann zeigt der km-Zähler das Modulo 100.000 an, also den Rest. Die Anzeige ist damit 12.314.

Zurück zu Rechenanlagen: auch dort gibt es Beschränkungen bzgl. des darstellbaren Intervalls. Bei Ganzzahlen ist das meist eine Wortbreite, also heute 32 oder 64 Bit. Bei einem 32-Bit Rechner ist das Ganzzahl-Interval also $(0,2^{32}-1)$ . Alle Rechnungen werden also Modulo $2^{32}$ gerechnet.

Um die Beispiele jetzt nachvollziehbarer zu machen, gehe ich einfach einmal von einer Wortbreite von 2 Bit aus, dann wird modulo 4 (bin: 100) gerechnet.

Demnach gilt:

00 + 00 = 00
00 + 01 = 01
00 + 10 = 10
...
10 + 01 = 11
10 + 10 = 00 (100 modulo 100 = 1 Rest 0)
10 + 11 = 01 (101 module 100 = 1 Rest 1)
...

Das Ergebnis der Addition von 2 Ganzzahlen kann also eine Zahl sein, die kleiner ist, als die beiden Operanden (eben 11 + 01 = 00). Dabei entsteht natürlich ein Überlauf. Diese Vorgehensweise ist nützlich, wenn ich den Überlauf beispielsweise in einer "höheren" Stufe wieder verarbeiten kann.

Nicht für alle Anwendungen ist die Modulo-Rechnung aber sinnvoll. Sie ist auch keineswegs die einzige Möglichkeit, Berechnungen zu betreiben.

Ein Beispiel: In der Computergrafik sollen 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 (begründet durch das trichromatische Sehen des Menschen). Die entsprechenden Komponenten können 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.

Im weiteren Beispiel betrachte ich nun nur noch die R-Komponente, analoges gilt auch für die 3 anderen. Wenn ich nun zwei Bilder übereinander lege (z.B. in einer grafischen Oberfläche), so addiere ich die R-Komponenten der jeweiligen Pixel. 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. Ups... die Kombination der beiden rot ist weniger rot als die beiden ursprünglichen Pixel. Das wollten wir eigentlich nicht haben...

In der Praxis kann rot nicht röter als "total rot" werden. Und "total rot" ist der Wert 255. Man kann sagen, bei diesem Wert ist der Rot-Kanal saturiert. Dies gibt einen Hinweis darauf, dass uns die Saturationsarithmetik helfen kann.

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.

Die Saturationsarithmetik wird offensichtlich in aktuellen Prozessoren gerade von Multimediabefehlen verwendet. Und das meiner Vermutung nach wegen der oben geschilderten Vorgehensweise bei der Berechnung der Pixelfarbe. Wobei es nun wohl an der Zeit ist zu gestehen, dass ich eigentlich von Multimedia-Entwicklung keine Ahnung habe, und mir noch nicht einmal sicher bin, ob das Beispiel oben stimmt Wink

. Es könnte aber korrekt sein, und würde dann einen gültigen Anwendungsfall darstellen. Das soll uns erst einmal genügen.

Dennoch steht zu vermuten, dass die Grafikprogrammierung hier erheblichen Einfluss hat. Denn es fällt auf, dass ein solches (R,G,B,A)-Tupel genau in einen 32 Bit-Multimedia Datentyp hineinpasst und die entsprechenden Maschineninstruktionen Saturationsarithmetik verwenden. Ich würde also fast was drauf verwetten, dass das genau der Anwendungszweck ist.