DE3689674T2

DE3689674T2 - Verfahren zur Datenkompression und -dekompression.

Info

Publication number: DE3689674T2
Application number: DE3689674T
Authority: DE
Inventors: Edward Larson Lawrence
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1985-06-11
Filing date: 1986-05-16
Publication date: 1994-09-15
Anticipated expiration: 2006-05-17
Also published as: US4626824A; BR8602558A; EP0204992B1; EP0204992A2; DE3689674D1; JPS61284119A; EP0204992A3; JPH0262058B2; CA1252896A

Description

Bereich der Erfindung

Der Gegenstand der vorliegenden Erfindung betrifft Rechnersysteme, genauer gesagt, einen Datenkompressions- und -dekompressions-Algorithmus, der im Rechnersystem angewandt wird, um Nachrichtendaten, die über ein Zwischenglied übertragen werden sollen, zu komprimieren, und um Nachrichtendaten zu dekomprimieren, sobald sie von dem Zwischenglied her eingegangen sind.

Stand der Technik

Wenn eine Nachricht über einen Nachrichtenkanal übertragen werden muß, ist es häufig erforderlich, diese Nachrichtendaten vor dem Übertragen zu komprimieren. Diese Komprimierung ist wegen der Zeit erforderlich, die zum Übertragen der Nachricht über den Nachrichtenkanal aufgewendet werden muß. Die zu berücksichtigende Zeit ist die Übertragungszeit der komprimierten Nachricht, die direkt mit der Länge der Nachricht in Beziehung steht, plus der Zeit für die Entwicklung der komprimierten Nachricht. Ein typisches Verfahren auf dem Stand der Technik zum Komprimieren von Daten ist die sogenannte "Lemple Ziv" Kompressionsmethode. Die Lemple-Ziv Nachrichtendaten-Kompressionstechnik erforderte den Einsatz eines großen Prozessors. Ferner müssen eine große Anzahl Tabellen zur Benutzung durch den Prozessor zur Durchführung der Lemple Ziv Kompressionstechnik greifbar sein. Die Lemple Ziv Methode ließ sich nicht auf den Prozessor, der in einem Personalcomputer eingesetzt ist, anpassen.
In IBM Technical Disclosure Bulletin, Bd. 14, Nr. 8, Januar 1971, S. 2438 wird ein Datenkompressions-Algorithmus beschrieben, durch den die am häufigsten auftretenden Hexadezimal-Zahlen eines Datenstroms herausgezogen und ein Bild des Datenflusses gebildet wird unter Benutzen von nur einem oder zwei Bits, um die Position der herausgezogenen Zahlen im Strom anzugeben. Zum Beispiel, wenn nur eine Zahl herausgezogen wird und dann das Bild aufgebaut ist aus den 1en, die die Positionen der ausgezogenen Zahl angeben, und den 0en, die die Positionen der restlichen Zahlen angeben. Dieser Datenfluß nach der Kompression enthält ein Halbbyte zum Identifizieren des Algorithmus, ein herausgezogenes, Zahlidentifizierendes Halbbyte, das Byte für die Länge des Flusses, einen Strombildabschnitt und den Original-Strom minus der herausgezogenen Zahl. Mehrere andere Kompressionstechniken auf dem Stand der Technik, wie z. B. die im US- Patent 4,491,934 an Heinz geoffenbarte Technik unter dem Titel "Data Compression Algorithm" sind nicht in der Lage, zu offenbaren, zu lehren oder anzudeuten, daß eine Nachricht, sobald sie einmal komprimiert ist, auch weiter komprimierbar sein könnte und so eine weiterkomprimierte Nachricht geschaffen wird, die eine Nachrichtdatenlänge aufweist, die sogar noch kleiner ist als die Länge der ursprünglich komprimierten Nachricht.

ZUSAMMENFASSUNG DER ERFINDUNG

Dementsprechend ist es eine Hauptaufgabe der vorliegenden Erfindung, einen Kompressions- und Dekompressionsalgorithmus für ein Rechnersystem zu entwickeln, wobei der Kompressionsalgorithmus im Zusammenwirken mit der Rechnersystem-Hardware in der Lage ist, kontinuierlich und wiederholt Nachrichtendaten zu komprimieren, bis die Daten nicht mehr weiter komprimiert werden können, wobei der Algorithmus diese Funktion unter Verwendung ausschließlich der in der Nachricht vorhandenen Daten ausführt.
Diese und weitere Aufgaben der vorliegenden Erfindung werden gelöst durch Vorsehen eines Kompressionsalgorithmus, der gemäß Anspruch 1 die Nachricht selbst benutzt, um die Kompressionsfunktion auszuführen. Keine externen Tabellen sind zur Durchführung der Datenkompressionsfunktion der vorliegenden Erfindung erforderlich. Gemäß der vorliegenden Erfindung überwacht der Kompressionsalgorithmus im Zusammenwirken mit der Rechnersystem-Hardware, die zu komprimierende Nachricht, um festzustellen, ob die Länge der Nachricht, angezeigt durch einen Längenanzeiger, länger ist als eine angezogene Modulzahl. Wenn das so ist, identifiziert der Algorithmus ein Maskenzeichen, wobei dieses Maskenzeichen dasjenige Zeichen ist, das in der Nachricht am häufigsten vorkommt. Dann vergleicht der Algorithmus das Maskenzeichen mit jedem Byte der Nachricht, wobei jedes Byte jedes Zeichen der Nachricht darstellt. Wenn das Maskenzeichen genau mit dem ersten Byte der Nachricht übereinstimmt, wird eine "1" an die erste Stelle eines bestimmten Ortes gesetzt, der als Maskenbyte bezeichnet wird. Wenn das Markenzeichen nicht mit dem ersten Byte der Nachricht übereinstimmt, wird eine "0" an die erste Stelle des Maskenbytes gesetzt. Nach Durchführen aller Vergleiche zwischen dem Maskenzeichen und jedem Byte der Nachricht ist ein komplettes Maskenbyte (bestehend aus 1en und 0en) aufgebaut worden. Eine Restnachricht besteht aus den Bytes der Nachricht, die nicht genau mit dem Maskenzeichen übereinstimmen. Die neue, komprimierte Nachricht enthält den Längenindikator, die Modulzahl, das Maskenzeichen, das Maskenbyte und die Restnachricht. Die Restnachricht wird dann dem gleichen Kompressionsprozeß ausgesetzt wie oben beschrieben, wobei der Kompressionsvorgang so lange fortgesetzt wird, bis die Länge einer nachfolgenden, komprimierten Nachricht größer ist als die Länge einer vorherigen komprimierten Nachricht. Die vorherige komprimierte Nachricht wird dann über einen Datenkanal gegeben. Empfängerseitig wird, um die ursprüngliche Nachricht wiederherzustellen, das Maskenzeichen und die Restnachricht mit dem Maskenbyte verglichen. Wenn in der ersten Stellung des Maskenbyte eine "1" erscheint, wird das Maskenzeichen als erstes Zeichen der Originalnachricht benutzt, während das Auftreten einer "0" an der ersten Stellung des Maskenbyte das vom ersten Byte der Restnachricht dargestelltes Zeichnen als erstes Zeichen der Originalnachricht benutzt wird. Der Prozeß des Dekomprimierens der restlichen Stellen des Maskenbytes wird genau so fortgesetzt wie oben beschrieben.
Die erfindungsgemäße Lösung wird in Anspruch 1 charakterisiert.
In den Ansprüchen 2 bis 3 sind erfindungsgemäße Verbesserungen definiert.
Weitere Anwendungsmöglichkeiten der vorliegenden Erfindung werden aus der nachstehenden detaillierten Beschreibung deutlich.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

Ein volles Verständnis der vorliegenden Erfindung geht aus der detaillierten Beschreibung der nachstehend erläuterten, bevorzugten Ausführungsform mit den begleitenden Zeichnungen hervor, die jedoch nur hinweisenden Charakter haben und keinesfalls einschränkend zu werten sind. Diese Zeichnungen sind wie folgt:
Fig. 1 zeigt ein Blockschaltbild eines typischen Datenverarbeitungssystems unter Anwendung des erfindungsgemäßen Kompressions- und Dekompressionsalgorithmus;
Fig. 2 zeigt schematisch den Inhalt der einzelnen Speicher, die in Fig. 1 gezeigt sind;
Fig. 3A bis 3C zeigt den Kompressionsprozeß und den Dekompressionsprozeß gemäß der vorliegenden Erfindung;
Fig. 4 ist ein Flußdiagramm des erfindungsgemäßen Kompressionsalgorithmus; und
Fig. 5 ist ein Flußdiagramm des erfindungsgemäßen Dekompressionsalgorithmus.

DETAILLIERTE BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSFORM

Unter Bezugnahme auf Fig. 1 werden typische Datenverarbeitungssysteme gezeigt. In Fig. 1 beinhaltet ein erstes, datenübertragendes System 10 einen Speicher 10a, der an einen Systembus 10b angeschlossen ist, und ein Input/Output (1/0) [Eingabe/Ausgabe (E/A)] Peripheriegerät 10d, das an den Systembus 10b angeschlossen ist. Der Prozessor 10c führt Anweisungen aus, die im Speicher 10a abgespeichert sind, und überträgt die Ergebnisse auf die E/A-Vorrichtung 10d. Ein Telefon 15 ist an die E/A-Vorrichtung 10d angeschlossen und nimmt die übertragenen Ergebnisse von der E/A-Vorrichtung 10d her auf. Das Telefon 15 ist ferner an ein zweites, aufgenommene Daten verarbeitendes System 20 angeschlossen, wobei das Telefon 15 die Ergebnisse, die es von der E/A-Vorrichtung 10d erhält, an das zweite Datenverarbeitungssystem 20 weitergibt. Das zweite Datenverarbeitungssystem 20 beinhaltet eine Input/Output (I/O) [Eingabe/Ausgabe (E/A)] Peripherievorrichtung 20d, die an einen Systembus 20b angeschlossen ist, einen Prozessor 20c, der an den Systembus 20b angeschlossen ist, und einen Speicher 20a, der an den Systembus 20b angeschlossen ist. Der Prozessor 20c führt die im Speicher 20a gespeicherten Anweisungen aus. Wenn die Ergebnisse vom ersten Datenverarbeitungssystem 10 her über das Telefon 15 eingehen, führt der Prozessor 20 die im Speicher 20a gespeicherten Befehle aus mit der Absicht, die vom ersten Datenverarbeitungssystem 10 eingehenden Daten zu interpretieren oder im Hinblick auf diese Ergebnisse andere Funktionen auszuführen.
Unter Bezugnahme auf Fig. 2 wird eine schematische Darstellung des Inhalts der Speicher 10a und 20a gezeigt. Speicher 10a und Speicher 20a enthalten jeweils einen Kompressionsalgorithmus bzw. einen Dekompressionsalgorithmus, die dort gespeichert sind. Der Kompressionsalgorithmus komprimiert im Zusammenwirken mit der Rechnersystem-Hardware die Nachrichtenblockdaten unter Verwendung ausschließlich der in der Nachricht selbst enthaltenen Daten. Der Dekompressionsalgorithmus extrahiert die ursprünglichen Nachrichtenblockdaten aus den komprimierten Nachrichtenblockdaten.
Nehmen wir jetzt Bezug auf Fig. 1 zusammen mit Fig. 2; der Prozessor 10c des ersten Datenverarbeitungssystems 10 enthält Nachrichtenblockdaten, die zum Prozessor 20c des zweiten Datenverarbeitungssystems 20 übertragen werden sollen. Prozessor 10c führt die Anweisungen im Zusammenwirken mit dem in Speicher 10a gespeicherten Kompressionsalgorithmus durch Komprimieren der im Cache (Pufferspeicher) des Prozessors 10c gespeicherten Nachrichtenblockdaten aus. Die komprimierten Nachrichtenblockdaten werden über die E/A-Vorrichtung 10d und das Telefon 15 an das zweite Datenverarbeitungssystem 20 übermittelt und gehen bei der E/A-Vorrichtung 20d ein. Der Prozessor 20c führt die mit dem in Speicher 20a gespeicherten Dekompressionsalgorithmus verbundenen Anweisungen durch und dekomprimiert die komprimierten Nachrichtenblockdaten, die vom ersten Datenverarbeitungssystem 10 her eingehen. Als Ergebnis werden die ursprünglichen Nachrichtenblockdaten, die ursprünglich im Cache des Prozessors 10c abgespeichert waren, extrahiert und im Cache des Prozessors 20c gespeichert. Da der Speicher 20a den gleichen Kompressionsalgorithmus enthält wie er auch im Speicher 10a vorhanden ist, lassen sich die Nachrichtenblockdaten, die im Cache des Prozessors 20c vorhanden sind, auf gleiche Weise komprimieren, wie sie auch durch die Anwendung des Prozessors 10c komprimiert wurden. Auf ähnliche Weise kann der Prozessor 10c durch Benutzen des Dekompressionsalgorithmus, der im Speicher 10a gespeichert ist, eine Dekompressionsfunktion durchführen. Bei dem in Fig. 1 gezeigten Datenverarbeitungssystem kann es sich um jedes typische Datenverarbeitungssystem handeln.
Nehmen wir jetzt Bezug auf Fig. 3a bis 3c; dort wird der erfindungsgemäße Kompressions- und der Dekompressionsprozeß dargestellt. In Fig. 3b ist ein typisches Beispiel für einen Datenblock gezeigt. Dieses Datenblockbeispiel wird nur zum Zweck der Darstellung benutzt und gilt nicht als illustratives Beispiel für einen Teil einer wirklichen Nachricht. Der Nachrichtenblock der Fig. 3b enthält ein Datenbyte, das repräsentativ für ein erstes Zeichen, Char1, ist, gefolgt von einem anderen Datenbyte, Byte1, gefolgt von einem weiteren Datenbyte, Byte 2, gefolgt von dem Datenbyte, das für das erste Zeichen, Char1, repräsentativ ist, gefolgt von dem Datenbyte, das für das erste Zeichen, Char1, repräsentativ ist.
In Fig. 3b sieht man, daß fünf Datenbytes gezeigt werden: Char1, Byte1, Byte2, Char1, Char1. Bei Untersuchung der ersten fünf Datenbytes sieht man, daß das Byte Char1 am häufigsten vorkommt. Das am häufigsten vorkommende Byte, im vorliegenden Fall "Char1", wird als "Maskenzeichen" bezeichnet.
Nehmen wir Bezug auf Fig. 3a; dort wird eine komprimierte Nachricht auf der Grundlage der Nachricht in Fig. 3b gezeigt. Im allgemeinen enthält eine komprimierte Nachricht das Maskenzeichen, gefolgt von einem Maskenbyte, gefolgt von der Restnachricht. In unserem Beispiel in Fig. 3a enthält die komprimierte Nachricht 30 das Maskenzeichen "Char1", 30a, gefolgt von dem Maskenbyte 30b, gefolgt von der Restnachricht 30c.
Die komprimierte Nachricht in Fig. 3a wird auf folgende Weise aus der ursprünglichen Nachricht in Fig. 3b synthetisiert: Das Maskenzeichen 30a wird durch Bestimmen des in allen Bytes der Nachrichtenblockdaten am häufigsten auftretenden Zeichens identifiziert. In unserem Beispiel ist das am häufigsten auftretende Zeichen "Char1". Deshalb ist "Char1" das Maskenzeichen 30a. Das Maskenbyte 30b wird aufgebaut durch Vergleichen des Maskenzeichens 30a mit jedem Byte der Originalnachricht, wie in Fig. 3b gezeigt wird. Wenn das Maskenzeichen 30a das gleiche ist wie das, das durch das erste Nachrichtenbyte dargestellt wird, wird der ersten Stelle des Maskenbytes 30b eine "1" zugeordnet; wenn jedoch das Maskenzeichen nicht das gleiche Zeichen ist, wie es vom ersten Byte der Nachricht dargestellt wird, wird der ersten Stelle des Maskenbytes 30b eine "0" zugewiesen. Der gleiche Vergleich wird zwischen dem Maskenzeichen 30a und jedem anderen Byte der Originalnachricht gemäß Fig. 3b zugewiesen. Unter Benutzung unseres Beispiels wird das Maskenzeichen "Char1" mit dem ersten Byte der Nachricht gemäß Fig. 3b verglichen, das "Char1" ist. Da das das gleiche Zeichen ist, wird der ersten Stelle des Maskenbyte eine "1" zugeordnet. Das Maskenzeichen "Char1" wird mit dem zweiten Byte und mit dem dritten Byte der ursprünglichen Nachricht, "Byte1" und "Byte2" verglichen. Da das Maskenzeichen nicht das gleiche Zeichen ist wie sie von "Byte1" oder "Byte2" dargestellt werden, wird dem Maskenbyte jeweils eine "0" als die nächsten zwei Stellen zugeordnet. Das Maskenzeichen "Char1" wird mit dem vierten und dem fünften Byte der Originalnachricht "Char1" und "Char1" verglichen. Da das Maskenzeichen gleich dem Zeichen ist, das durch das vierte und fünfte Byte dargestellt wird, wird jeweils eine "1" an die letzten zwei Stellen des Maskenbytes gesetzt, wodurch sich "10011" ergibt. Daher ist "10011" das Maskenbyte 30b. Die Restnachricht 30c enthält die ursprüngliche Nachricht, wie in Fig. 3b gezeigt wird, bei der jedoch das Maskenzeichen "Char1" aus der Nachricht entfernt wurde. In unserem Beispiel sind "(Byte1) (Byte2)" die Restnachricht 30c. Daraus ergibt sich, daß die Nachricht in Fig. 3a die komprimierte Form der Nachricht in 3b ist.
Die Originalnachricht der Fig. 3b wird aus der komprimierten Nachricht der Fig. 3a auf folgende Weise herausgezogen: Wenn beginnend mit der ersten Stelle des Maskenbytes 30b hier eine "1" steht, stellt das Maskenzeichen "Char1" das erste Byte der ursprünglichen Nachricht dar, wenn hier eine "0" steht ist das erste Byte der Restnachricht, "Byte1", das erste Byte der ursprünglichen Nachricht. Wenn auf ähnliche Weise, beginnend mit der zweiten Stelle des Maskenbytes 30b, hier eine "1" steht, ist das Maskenzeichen "Char1" das zweite Byte der ursprünglichen Nachricht, wenn andererseits hier eine "0" steht, wenn das erste Byte der Restnachricht nicht benutzt wird, stellt das erste Byte der Restnachricht das zweite Byte der ursprünglichen Nachricht dar. Wenn das erste Byte der Restnachricht benutzt wurde, stellt das zweite Byte der Restnachricht das zweite Byte der ursprünglichen Nachricht dar.
Benutzten wir nun unser Beispiel in Fig. 3a; da das Maskenbyte "10011" ist, ist das erste, vierte und fünfte Byte der ursprünglichen Nachricht das Maskenzeichen 30a, d.i. "Char1", aber das zweite und das dritte Byte der ursprünglichen Nachricht sind die restlichen Teile der Restnachricht, d.i. (Byte1) bzw. (Byte2)
In Fig. 3c wird der Prozeß des kontinuierlichen und wiederholten Komprimierens von Nachrichtenblockdaten dargestellt. Wie bereits bemerkt, ist der Kompressionsalgorithmus der vorliegenden Erfindung in der Lage, Daten kontinuierlich und wiederholt zu komprimieren, bis die Daten nicht mehr weiter komprimiert werden können. Das heißt, wenn die Nachrichtenblöcke beim Komprimieren nicht mehr kleiner werden, sondern an Größe wieder zunehmen, wird zur Übertragung von einem Datenverarbeitungssystem zu einem anderen der kleinstmögliche Nachrichtenblock benutzt.
Nehmen wir jetzt Bezug auf Fig. 3c (1); eine Nachricht "(Nachricht)" wird zunächst komprimiert auf die Form "(ch1) (mb1) (rm1)" wobei (ch1) das Maskenzeichen, (mb1) das Maskenbyte und (rm1) die Restnachricht ist, wie in Fig. 3c (2) gezeigt wird. Die Restnachricht (rm1) der Fig. 3c (2) wird weiter komprimiert auf die Form "(ch2) (mb2) (rm2)" wobei (ch2) das Maskenzeichen für die Restnachricht (rm1), (mb2) das Maskenbyte für die Restnachricht (rm1), und (rm2) die Restnachricht für die erste Restnachricht (rm1) ist, wie in Fig. 3c (3) gezeigt wird. Die Restnachricht (rm2) der Fig. 3c (3) wird weiter komprimiert zur Form "(ch3) (mb3) (rm3)" wobei (ch3) das Maskenzeichen für die Restnachricht (rm2), (mb3) das Maskenbyte für die Restnachricht (rm2), und (rm3) die Restnachricht für die Restnachricht (rm2) ist, wie in Fig. 3c (4) dargestellt wird. Wenn eine weitere Kompression der Nachricht aus Fig. 3 (4) eine größere anstatt eine kleinere Nachricht ergibt, wird die in Fig. 3c (4) enthaltene Nachricht von einem ersten Datenverarbeitungssystem 10 an ein zweites Datenverarbeitungssystem 20 übertragen, wie in Fig. 1 gezeigt wird.
Vor der Nachricht "(Nachricht)" in Fig. 3c (1) steht häufig ein Längenindikator "(LL)" und eine Modulnummer "(abcde)". Der Indikator "LL" ist eine Zahl, die die wahre Länge der Nachricht "(Nachricht)" angibt, und die Modulzahl "(abcde)" ist eine Zahl, die eine Bezugslänge angibt. Wenn der Längenindikator "(LL)" größer ist als die Modulzahl "(abcde)", komprimiert der erfindungsgemäße Kompressionsalgorithmus die Nachrichtenblockdaten. Wenn aber der Längenindikator "(LL)" nicht größer ist als die Modulzahl "(abcde)", komprimiert der Kompressionsalgorithmus der vorliegenden Erfindung die Originalnachrichtenblockdaten nicht, sondern die Originalnachrichtenblockdaten werden ohne Komprimieren durch den Datenkanal vom Datenverarbeitungssystem 10 zum Datenverarbeitungssystem 20 übertragen.
Nehmen wir Bezug auf Fig. 4; hier wird ein Flußdiagramm des Kompressionsalgorithmus gezeigt, der in Speicher 10a und in Speicher 20a gespeichert ist. In Fig. 4 beginnt der Algorithmus in Block 40a mit Nullstellen eines Zählers und Aufzeichnen der Länge der zu komprimierenden Nachricht. Die Zähler werden in Block 40b gelöscht. Ein Zeiger wird auf das erste Zeichen der Nachricht gestellt. Wenn nicht alle Nachrichtenzeichen gezählt sind, wird in Block 40d der Zeichenzähler inkrementiert. Sobald das häufigste Zeichen identifiziert ist, wird in Block 40e das Zeichen gespeichert und in Block 40f zum nächsten Zeichen übergegangen. Wenn das häufigste Zeichen nicht identifiziert wird, wird in Block 40f zum nächsten Zeichen übergegangen. Sobald alle Zeichen gezählt sind, wird in Block 40g die Länge der komprimierten Nachricht berechnet. Wenn die neue Größe nicht kleiner ist, wird in Block 40h die Nachricht übertragen und das Ende erreicht. Wenn die neue Größe kleiner ist, werden in Block 40i Bits = 0 und Maske = 0 gesetzt und die Maske wird zur Ausgangsnachricht addiert. In Block 40j wird der Zeiger auf das erste Zeichen der Nachricht gesetzt. Wenn alle Zeichen geprüft sind, aber die verarbeiteten Zeichen keine Mehrfachen von 8 sind, wird in Block 40k die Maske ausgerichtet und die neue Nachricht in Block 40L als zu komprimierende Nachricht behandelt. Jetzt wird zu Block 40b übergegangen und alle Schritte werden wiederholt. Wenn die verarbeiteten Zeichen ein Mehrfaches von 8 sind, wird die neue Nachricht in Block 40L als zu komprimierende Nachricht betrachtet und zu Block 40b übergegangen. Wenn nicht alle Zeichen untersucht sind und das häufigste Zeichen nicht identifiziert ist, wird in Block 40M das augenblickliche Zeichen zur ausgehenden Nachricht addiert. In Block 40N wird zum nächsten Bit übergegangen. Wenn die verarbeiteten Zeichen Mehrfache von 8 sind, wird in Block 40P ein neues Maskenbyte geklärt und die Frage "sind alle Zeichen untersucht?" wird wiederholt. Wenn nicht alle Zeichen untersucht sind und das häufigste Zeichen identifiziert ist, wird in Block 40Q auf das Bit in der Maske übergegangen und die Frage "sind die verarbeiteten Zeichen Mehrfache von 8?" wird wiederholt.
Jetzt ein Hinweis auf Fig. 5; diese ist ein Flußdiagramm des Dekompressionsalgorithmus 50, gespeichert in den Speichern 10a und 20a.
In Fig. 5 entscheidet der Dekompressionsalgorithmus, ob die eingegangene Nachricht komprimiert ist. Wenn sie komprimiert ist, wird in Block 50a die Länge der Nachricht festgestellt. In Block 50b wird das Kompressionszeichen herausgezogen. In Block 50c wird die Anzahl der Bits gleich Null gesetzt. In Block 50d wird die Maske geholt. Wenn das höherwertigste Bit (M.S.) nicht gesetzt ist, wird in Block 50e das Eingangszeichen auf den Ausgang kopiert. Wenn das M.S. Bit gesetzt ist, wird in Block 50f das Kompressionszeichen ausgegeben. Wenn nicht alle Eingangszeichen verarbeitet sind und die Anzahl der zu untersuchenden Bits nicht gleich 8 ist, wird die Frage "ist höherwertigstes Bit gesetzt?" wiederholt und die Schritte 50e bzw. 50f werden wiederholt, in Abhängigkeit davon, ob das M.S. Bit gesetzt ist. Wenn nicht alle Eingangszeichen verarbeitet sind, aber die Anzahl der zu untersuchenden Bits gleich 8 ist, wird zu Block 50c übergegangen und die obige Schrittfolge wird wiederholt. Wenn alle Eingangszeichen verarbeitet sind, werden in Block 50g die Eingangs- und die Ausgangsnachricht vertauscht und zum es wird wieder zum Anfang des Dekompressionsalgorithmus übergegangen unter Wiederholung der Frage "ist die Nachricht komprimiert?".

Claims

1. Verfahren zum Komprimieren eines Datensatzes, in dem ein Kompressionsalgorithmus benutzt wird, der diesen Datensatz komprimiert durch:

Identifizieren eines Maskenzeichens im Datensatz, das das am meisten vorkommende Zeichen im Datensatz repräsentiert;

Entwickeln eines Maskenbytes im Zusammenwirken mit dem Maskenzeichen, wobei das Maskenbyte die Stellen des Maskenzeichens im Datensatz identifiziert, und Identifizierung der Stellen jedes Teils einer Restnachricht, die dem Datensatz zugeordnet wird;

Entwickeln der Restnachricht, wobei die Restnachricht der Datensatz ist, aus dem das Maskenzeichen herausgezogen ist; und

Verketten des Maskenzeichens, des Maskenbytes und der Restnachricht und damit Bilden eines weiteren Datensatzes, dadurch gekennzeichnet, daß

der Kompressionsalgorithmus den weiteren Datensatz erneut komprimiert durch:

Entwickeln neuer Maskenzeichen, neuer Maskenbytes und neuer Restnachrichten aus der Restnachricht und Verkettung der Maskenzeichen, Maskenbytes und der neuen Restnachrichten, und

für den Fall, daß der vorher komprimierte Datensatz und der anschließend komprimierte Datensatz nicht gebildet wurden, Entwickeln weiterer neuer Maskenzeichen, weiterer neuer Maskenbytes und weiterer neuer Restnachrichten aus der neuen Restnachricht und Verkettung der Maskenzeichen, Maskenbytes und der weiteren neuen Restnachrichten, bis der vorher komprimierte Datensatz und der anschließend komprimierte Datensatz gebildet sind.

2. Verfahren gemäß Anspruch 1, dadurch gekennzeichnet, daß der komprimierte Datensatz wiederholt neu komprimiert wird, bis ein vorher komprimierter Datensatz und ein anschließend komprimierter Datensatz gebildet sind, die Länge des anschließend komprimierten Datensatzes größer ist als die Länge des vorher komprimierten Datensatzes, wobei dann der vorher komprimierte Datensatz der gewünschte Datensatz ist.

3. Verfahren gemäß Anspruch 2, dadurch gekennzeichnet, daß das wiederholte Neukomprimieren des komprimierten Datensatzes die folgenden Schritte umfaßt:

a) Entwickeln eines neuen Maskenzeichens, eines neuen Maskenbytes und einer neuen Restnachricht aus dieser Restnachricht und damit Ausbilden einer neuen Restnachricht;

b) Verketten der Maskenzeichen, der Maskenbytes und der komprimierten Restnachrichten;

c) für den Fall, daß Schritt b) nicht zu der Bildung des vorher komprimierten Datensatzes führt, Wiederholung der Schritte a) und b) unter Verwendung zuerst der neuen Restnachricht, bis der vorher komprimierte Datensatz gebildet ist;

d) Entwickeln eines weiteren neuen Maskenzeichens, eines weiteren neuen Maskenbytes und einer weiteren neuen Restnachricht aufgrund der Restnachricht des vorherigen komprimierten Datensatzes unter Bildung einer weiteren komprimierten Restnachricht; und

e) Wiederholen von Schritt b) unter Verwendung der weiteren komprimierten Restnachricht, um den nachfolgenden komprimierten Datensatz zu bilden.