Voyager Inside: Der Rice Algorithmus und die Datenraten bei Kompression

Zwischen Saturn und Uranus wurde Voyager „reeinginert“, d.H. sie erhielt zahlreiche Verbesserungen. Die meisten davon waren nur möglich weil die Sonden programmierbare Computer hatten, anders als die Mariners in deren Serie sie zuerst einsortiert wurde (Mariner-Jupiter-Saturn 77).

Eine der umfangreichsten Veränderungen war die Einführung eines Kompressionsverfahrens. An der Stelle gleich eine Bemerkung, das ist in der Website falsch beschrieben, da ich bis zum Buch populärwissenschaftliche Darstellungen als Quelle genutzt habe und die beschrieben die Vorgehensweise wie folgt: Man übertrug das erste Pixel einer Zeile unkomprimiert (8 Bit) und die folgenden Pixel als 3 Bit Differenzwert zur vorherigen Helligkeit. Das ist falsch.

Aber zuerst mal eine Einführung zu Kompressionsalgorithmen an sich. Man unterscheidet verlustbehaftete und verlustlose Kompressionen. Verlustbehaftete hatte Voyager schon an Bord, so wurden die Daten von PPS, UVS und LECP logarithmiert und in der Form Mantisse und Exponent übertragen, wobei diese weniger Bits aus die Ausgangsdaten hatten. Ein verlustbehafteter Algorithmus erlaubt es nicht die Originaldaten zu restaurieren, ein verlustloser schon.

Der wohl bekannteste verlustbehaftete Algorithmus ist die Huffmann-Codierung. Sie untersucht zuerst einen Datenblock und macht sich eine Tabelle, wie oft jeder Wert vorkommt. Bei einem Bild (das Beispiel bliebt in der Folge gleich) ist es so, dass nicht alle Farben gleichgestellt sind, bei einem Bild mit viel Hintergrund sind die meisten Pixel schwarz. Die Huffmann-Codierung ordnet nun der häufigsten Farbe wenige Bits zu und den selten benutzten Farben mehr Bits. Das können für seltene Farben dann durchaus auch mehr Bits sein als das Pixel im Original hatte. Man kann für jedes Bild seine Entropie berechnen, das ist die Mittlere Anzahl von Bits die nötig sind um den Informationsgehalt vollständig zu beschrieben. Ein Bild das z.B. nur aus einer Farbe besteht benötigt nur 1 Bit/Pixel auch wenn jedes Pixel dann in 8 oder 12 Bit kodiert ist. Dabei geht in die Bewertung sowohl die Anzahl der unterschiedlichen Werte wie auch die Bits pro Helligkeitswert ein. Dich höchste Entropie haben demnach Bilder in denen der gesamte Wertbereich ausgeschöpft ist (bei 8 Bit es also 256 Helligkeitsstufen gibt) und bei denen alle Helligkeitswerte gleich oft vorkommen, das ist seltsamerweise nur bei einem gleichförmigen Rauschen so, den ganz älteren Bloglesern vielleicht noch von dem Bild eines Fernsehers nach Sendeschluss bekannt.

Die Huffmann-Codierung wurde beim JPL intern eingesetzt um die Voyager-Rohbilder zu komprimieren. Voyagers Rechner für die Datenverarbeitung, das FDS, hatte ihn aber nicht an Bord, auch nicht bei de Nachrüstung, obwohl der Algorithmus alt ist, schon 1952 entwickelt. Der Grund ist relativ einfach. Huffmann ist langsam und benötigt viel Speicher. Man sollte ihn auf eine größere Anzahl von Daten anwenden, weil auch der Baum der beim Algorithmus entsteht – welcher Helligkeitswert welcher Bitfolge entspricht, übertragen wird, und bei kleinen Datenmengen frisst das natürlich jede Ersparnis auf. Es gibt bei dem ersten Voyager CD-ROM mit den Bildern die mit Huffmann komprimiert sind, ein Entpackprogramm, auch als Quelltext und dabei wird verwiesen das eine VAX 11/750, das ist ein 32 Bit Minicomputer der Ende der siebziger Jahre auf den Markt kam, eine Minute für das Komprimieren des Bildes mit 640.000 Pixel braucht. Eine VAX 11/750 ist in etwa so schnell wie eine Motorola MC 68000 oder ein Intel I80286, also um ein vielfaches schneller als Voyagers Bordrechner. So war der Algorithmus nicht für das FDS praktikabel.

Der Algorithmus den Voyager einsetzte ist der Rice-Algorithmus. Robert F. Rice entwickelte ihn am JPL. Ich gebe im folgenden wieder, wie er bei Voyager implementiert ist, der Algorithmus selbst ist der Sprache der Informationswissenschaft formuliert, also abstrakte Mathematik. Ich habe zwar Softwaretechnik studiert, aber an einer FH (auch wenn es inzwischen eine Hochschule ist) und damit praxisorientiert. Wer es detaillierter mag: hier ist die Beschreibung und hier die Orginaldokumente von Robert Rice. Der Rice Algorithmus basiert auf der Annahme, das sich nebeneinander liegende Pixel kaum in ihrer Helligkeit unterscheiden. Anders als Huffman arbeitet er nur mit wenigen Pixeln.

Der Algorithmus wurde so implementiert: Eine Zeile des Bildes wurde in den sekundären FDC Speicher kopiert und die Differenzen zwischen den Pixeln als eine Gruppe von Ganzzahlen ermittelt. Dabei wurden auch negative Abweichungen als eine positive Ganzzahl implementiert, das heißt der Wertebereich musste über 256 hinausgehen.

Anschließend nahm sich der FDC jeweils fünf dieser Abweichungen und übertrug für diese einen Indexwert, der für folgende Abweichungen stand:

Bitfolge	Länge des komprimierten Wortes	Differenzbereich
000	1	0, +1
001	2	-1, +2
010	3	-3, +4
011	4	-7, +8
100	5	-15, +16
101	6	-31, +32
110	Nicht benutzt
111	Unkomprimierten Wert senden

Jeder Indexwert stand für einen Kodierer, der jeweils in seinem Bereich die niedrigste Bitzahl für den Wert erzeugte. Der aus dieser Funktion erzeugte Wert wurde dann für jedes der fünf Pixel angehängt. Bei Voyager wurden aufgrund der Geschwindigkeit des FDS keine Funktionen, sondern Entscheidungstabellen genutzt, deren Meist-Signifikante Bits immer 0 waren. Die angegebene Kompression von 3 Bit bezieht sich auf das Gesamtergebnis, nicht das nun jedes Byte in 3 Bit komprimiert wird. Es konnten bei vielen gleichen Pixels auch nur 1 Bit sein. Die Abbildung zeigt ein Beispiel einer Codierung. In diesem Beispiel werden 9 Pixel mit je 8 Bit (72 Bit) in 19 Bit komprimiert. Der Rice-Algorithmus gilt als eine verlustlose Komprimierung. Da bei Voyager aber das niederwertige Bit nicht berücksichtigt wurde, ist er bei Voyager nicht verlustlos. Er produzierte Daten, die 0,5 Bit über dem mittleren Informationsgehalt der Bilddaten lagen.

Abbildung 1: Kompression

Da es auch abrupte Helligkeitssprünge gibt, z.B. am Rande einer Planetenscheibe zum Weltraum, gab es auch die Option den unkomprimierten Wert zu senden.

Aufgrund dessen, dass man den Speicher für maximal eine Zeile benötigt und bei Voyager nur maximal 5 Pixel auf einmal verarbeitet werden, benötigt der Rice-Algorithmus wenige Ressourcen, sowohl was den Speicher wie Rechengeschwindigkeit angeht.

Der Rice-Algorithmus wurde sowohl in Form von Software wie Hardware bei Galileo, Cassini, Mars Obervers, Mars Global Surveyor, Huygens und sogar Mars 96 eingesetzt.

Das erste Pixel einer Zeile wurde als Referenz immer unkomprimiert gesendet. Der Algorithmus hatte eine Begrenzung. Es ist im Datenblock eine feste Größe für eine Zeile, nämlich 2.480 Bit vorgesehen. Ist dieser Bereich erschöpft. so bricht der Kompressor ab, die restlichen Pixels werden verworfen. So konnte, wenn es zu viele Variationen des Kontrasts in einem Bild gab, eine Zeile abgeschnitten werden. Um diesen Fehler zu minimieren, verarbeitet der FDS nicht die Bilddaten direkt, sondern setzte das niedrigwertige Bit immer auf 0, das reduzierte die Graustufen von 256 auf 128. Als Zweites, um nicht einen ganzen Block rechts im Bild zu verlieren, wechselte man die Codierung der Zeilen ab. Nach einer Zeile die ausgehend von Pixel 1 „nach hinten“ komprimiert wurde, kam eine Zeile dran, die vom letzten Pixel (800) „nach vorne“ komprimiert wurde. Die fehlenden Pixeln kann man so aus den Nachbarzeilen restaurieren. Bei Tests von Saturnbilddaten kam es bei 85 Prozent der Bilder zu weniger als 3 Prozent Datenverlust. Das war hinnehmbar. Ein Beispiel für die Auswirkung ist dieses Rohbild von Neptun. Als besondere Probleme erweisen sich die Rousseau-Markierungen im Bild, die für hohe Kontraste sorgten.

Dieses Problem haben aufgrund desselben Algorithmus übrigens auch Galileo- und Cassini Aufnahmen. Es ist in allen drei Missionen die gleiche Einschränkung die Größe eines Datenblocks zum Sendesystem der eben konstant ist ist und nicht verlängert werden kann. Als Beispiele habe ich hier eine Neptun-Aufnahme von Voyager 2 und eine Cassini-Aufnahme von Dione beigelegt.

Das leitet mich zum zweiten Punkt über den Sendeformaten für die Daten. Ein Datenblock bei Uranus und Neptun betrug bei einer Datenrate von 14,4 kbit:

Feld	Header	GS & E	Füller	Pixel	Komprimierte Zeile	Pixel	Komprimierte Zeile	Fehlerkorrektur	Füller
Länge:	48 Bit	2.160 Bit	16 Bit	8 Bit	2.472 Bit	8 Bit	2.472 Bit	1.024 Bit	432 Bit
Aufbau:	32 Bit Framesync Code. 8 Bit Nullen 8 Bit ID	Daten die in 0,6 Sekunden anfallen (3600 Baud)	Als FDS Notbehelf nötig	Pixel 1 unkomprimiert	Pixel 2-800 komprimiert	Pixel 800 unkomprimiert	Pixel 799- 1 komprimiert	Reed.Solomon Code	Füller
7.136 Bit								1.024 Bit	432 Bit
8.640 Bit in 0,6, Sekunden (bei 14,4 KBaud)

Der Codeblock bestand aus 7.136 Bits Nutzdaten, 1.024 Bits Reed-Solomon Code und 432 Füllbits, zusammen 8.640 Bits, die in 0,6 Sekunden bei 14.400 Baud übertragen wurden. Netto entsprach dieser Codeblock einer Datenrate von 28,533 KBaud mit Golay Code, ohne Komprimierung. Die Nettodatenrate wurde also fast verdoppelt.

Die abschließenden Füllbits waren nötig, weil es feste Senderaten gab, der Block musste aufgefüllt werden um die Datenrate von 13,68 auf 14,4 KBaud zu steigern.

Der Reed-Solomon Code wurde auch auf die Bildadaten angewandt (der Golay Code den Voyager bei Jupiter und Saturn nur auf die GS & E Daten). Er arbeitet mit festen Codeblöcken von 223 Bit zu denen er 32 Bit addiert, also im optimalen Fall 14,4 % Overhead, sind es weniger als 223 Bit so muss mit Nullen auf ein Vielfaches von 223 Bit aufgefüllt werden.

Was mich persönlich verwundert ist das für Uranus und Neptun neue FDS-Modi eingeführt werden um die Datenrate an die des Sendesystens anzupassen. Das waren aber alle „edited“ Modi, das hießt es gab neue Modi um Teile eines Bildes nicht zu übertragen. An den prinzipiellen Modi ein komplettes Bild zu übertragen änderte sich wenig, das war ein Bild mit maximaler Ausleserate (48 Sekunden, 115.200 Bit/s mit GS&E Daten). Das konnte verlängert werden auf 3 x 48, 5 x 48 und 10 x 48 Sekunden. Ohne Komprimierung entspricht dies Datenraten von 44,8, 29,9 und 19,2 kbit/s.

Mit Komprimierung wurden bei Uranus 14,4 kbit/s (Modus 5:1) und 21,6 kbit/s (Modus 3:1) eingesetzt, bei Neptun noch 9,6 kbit/s (10:1). Datenraten dazwischen wurden nicht genutzt. Bei Uranus wäre die Datenrate von 29,9 kbit/s über Australien nutzbar gewesen. Sie war als Fallback definiert, wenn der neue Algorithmus scheitern würde – man konnte ihn anders als andere Verbesserungen nicht vorher bei Voyager 1 testen, weil diese schon nach Saturn den Speicher einen ihrer FDS verloren hatte und damit konnte nicht ein FDS komprimieren und der andere die Daten formatieren. Bei 29,9 kbit/s wäre auch der Modus 2:1 mit den komprimierten Daten möglich gewesen. Zwischen 3 und 5 läge die Ausleserate um den Faktor 4 (192 s pro Bild), die mit 19,2 kbit/s, einer definierten Datenrate möglich gewesen wäre. Ebenso wäre mit 12,8 kbit/s ein 6:1 Modus möglich und mit 10,8 kbit/s ein 8:1. Beides Verbesserungen gegenüber 9,6 kbit (10:1) (ich gehe davon aus das die niedrigen Datenraten um 1,2 kbit/s gestaffelt sind, da definierte Datenraten von 4,8 – 7,2 – 8,4 – 9,6 – 14,4 kbit/s existieren).

Meine Vermutung: Die Anpassung an reduzierte Datenraten geschieht bei Voyager durch das Verlängern der Pause nach dem Stahlrücklauf. Dies scheint nicht vom FDS durchgeführt werden, sondern der Elektronik an den Kameras und die ist eben nicht programmierbar.