DE2414239C3

DE2414239C3 - Verfahren und Vorrichtung zum Komprimieren einer binären Informationsfolge

Info

Publication number: DE2414239C3
Application number: DE19742414239
Authority: DE
Inventors: Yasuyuki Tokio Komura
Original assignee: Ricoh Co Ltd
Current assignee: Ricoh Co Ltd
Priority date: 1973-03-27
Filing date: 1974-03-25
Publication date: 1979-08-16
Also published as: JPS5843943B2; DE2414239B2; JPS49122913A; DE2414239A1; GB1469433A

Description

Die Erfindung bezieht sich auf ein Verfahren zum Komprimieren einer binären Informationsfolge, die durch zeilenmäßiges Abtasten einer graphischen Vorlage erhalten wurde und aus Gruppen einer jeweils gleich großen Anzahl von Bits besteht, bei dem die einzelnen Gruppen daraufhin überprüft werden, ob sie nur Bits der ersten Art (z. B. logische NULL) oder wenigstens ein Bit der zweiten Art (z. B. logische EINS) enthalten und bei dem ein Gruppenkennzeichenbit erzeugt wird, das die beiden möglichen Fälle unterscheidet, bei dem ferner bei Auftreten des ersten Falles (nämlich: Gruppe enthält nur Bit der ersten Art) stellvertretend für die gesamte Gruppe nur das Kennzeichenbit erzeugt wird, und bei dem Auftreten des zweiten Falles (nämlich: Gruppe enthält wenigstens ein Bit der zweiten Art) eine weitere Unterteilung der Gruppe in Blöcke von Bits einer jeweils gleichen Anzahl vorgenommen wird, die einzeln daraufhin überprüft werden, ob sie nur Bits der ersten Art oder wenigstens ein Bit der zweiten Art enthalten, und bei dem ein Blockkennzeichenbit für jeden Block erzeugt wird, das die beiden möglichen Fälle unterscheidet, bei dem ferner bei Auftreten des ersten Falles (nämlich: Block enthält nur Bits der ersten Art) stellvertretend für den Block nur das Blockkennzeichenbit erzeugt wird und bei dem bei Auftreten des zweiten Falles (nämlich: Gruppe enthält wenigstens ein Bit der zweiten Art) der Block zusätzlich zu dem Blockkennzeichenbit ungeändert übernommen wird.

In der DE-OS 15 12 654 ist ein Verfahren zum Komprimieren einer digitalen Impulsfolge beschrieben, bei dem die ankommende Impulsfolge in Gruppen von jeweils 64 Bits zerlegt wird. Jede Gruppe wird daraufhin untersucht, ob sie nur Weiß-Information (beispielsweise logische EINS) oder wenigstens eine Schwarz-Information (beispielsweise logische NULL) enthält. Für die so untersuchte Gruppe wird ein Gruppenkennzeichenbit erzeugt, das die beiden angegebenen Fälle unterscheidet. Enthält die gesamte Gruppe nur Weiß-Information, so wird stellvertretend in der codierten Impulsfolge nur das Kennzeichenbit für diese Gruppe übertragen. Ist in dieser Gruppe aber auch Schwarz-Information enthalten, so wird die Gruppe weiterhin unterteilt in Untergruppen von jeweils 16 Bits, die wiederum daraufhin untersucht werden, ob sie nur Weiß-Information oder auch wenigstens eine Schwarz-Information enthalten. Für jede solche Untergruppe wird ein eigenes Kennzeichenbit erzeugt, das diese beiden möglichen Fälle unterscheidet. Diejenigen Untergruppen, die nun auch eine Schwarz-Information beinhalten, werden nochmals unterteilt in Blöcke von jeweils 4 Bits, an denen dieselbe Untersuchung wieder vorgenommen wird und ein Blockkennzeichenbit erzeugt wird, das die beiden möglichen Fälle unterscheidet. Unmittelbar nach jedem tilockkennzeichenbit, das angibt, daß der ihm zugeordnete Block auch eine Schwarz-Information

beinhaltet, schließt sich der aus 4 Bits bestehende Block in der ursprünglichen Datenfolge ungeändert an. Die so codierte Datenfolge enthält also für jede Datengruppe eine Verschachtelung von Kennzeichenbits und ungeändert zu übertragenden Bits.

Eine ähnliche Codierung ist der DE-AS 12 96 182 zu entnehmen, bei der eine digitale Informationsfolge in aufeinanderfolgende Gruppen von jeweils 8 Bits eingeteilt wird. Aufeinanderfolgende Gruppen werden daraufhin überprüft, ob sie nur Weiß-Information oder wenigstens auch eine Schwarz-Information enthalten. Folgen mehrere Gruppen mit nur Weiß-Information aufeinander, so werden diese in einem Datenwort zusammengefaßt, dessen erstes Bit ein Kennzeichenbit darsteilt, das angibt, daß mehrere Gruppen zusammengefaßt wurden. Das folgende aus 8 Bit bestehende Teilwort gibt die Zahl der nur Weiß-Information enthaltenden Gruppen wieder. Jede Gruppe, die auch Schwarz-Information enthält, wird ungeänJert zusammen mit einem Kennzeichenbit wiedergegeben, das angibt, daß es sich um eine solche ungeänderte Datenfolge handelt.

Der vorliegenden Erfindung liegt die Aufgabe zugrunde, ein Verfahren und eine Vorrichtung zum Komprimieren einer digitalen Informationsfolge anzugeben, bei dem die komprimierten Daten übersichtlich geordnet und dementsprechend leicht verarbeitbar sind.

Diese Aufgabe wird ausgehend von dem obigen Verfahren durch das Kennzeichen des Hauptanspruchs gelöst.

Vorteilhafte Weiterbildungen dieses Verfahrens sowie eine Vorrichtung zum Durchführen des Verfahrens sind in den Unteransprüchen angegeben. Im folgenden wird die Erfindung anhand der Figuren näher erläutert. Es zeigt

F i g. I eine schematische Ansicht eines graphischen Dokuments;

Fig.2 eine scnematische Darstellung binärer Information, die durch Abtasten des Dokuments von F i g. 1 erzeugt wurde;

Fig.3 eine der Fig.2 entsprechende Darstellung binärer Information nach Umcodierung in die Delta-Form;

F i g. 4 eine ähnliche Darstellung wie F i g. 3, die verdeutlicht, wie extrem kurze Impulse ohne übermäßigen Verlust an Auflösung unterdrückt werden können;

F i g. 5 eine tabellenförmige Ansicht eines Teiles einer erfindungsgemäßen komprimierten Informationsfolge;

Fig.6 ein Blockschaltbild eines Komprimierungssystems gemäß der Erfindung; und

Fig. 7 ein Blockschaltbild eines Expansionssystems, das dazu dient, die komprimierte Information wieder zu expandieren.

In Fig. 1 ist ein zweidimensionales graphisches Dokument gezeigt, das graphische Information in Form einer unregelmäßig dunklen Fläche enthält. Obwohl das vorliegende Verfahren speziell für die Verwendung bei einem Faksimilesystem geeignet ist, bei dem ein zweidimensionales graphisches Dokument abgetastet wird, umfaßt es auch andere Anwendungen. Ganz allgemein kann gesagt werden, daß dieses Verfahren überall dort einset/.bar ist, wo eine binäre Bild-Informationsfolge vorliegt, die sich unterteilen läßt.

F i g. 1 illustriert ein allgemein verwendetes regelmäßiges orthogonales Abtastsystem, bei dem jede Zeile 1 bis 20 in hundert diskrete Bits unterteilt ist. Es wird in bekannter Weise von links nach rechts und von oben nach unten abgetastet. Eine Impulskette, die durch Abtasten des gesamten Dokuments entsteht, enthält daher 2000 diskrete Informationsbits. Wenn angenommen wird, daß ein positiver Impuls für jeden Bereich erzeugt wird, der eine Dichte obe-halb eines gewissen Wertes besitzt, und daß kein Impuls erzeugt wird, falls die Dichte eines Bereiches unterhalb dieses Wertes liegt, dann ruft die Abtastung des Dokuments von F i g. 1 eine elektrische Impulskette gemäß Fig. 2 hervor, bei der aufeinanderfolgende Zeilen zur leichteren Darstellung

lü vertikal angeordnet sind. Jede Zeile wird in eine vorbestimmte Anzahl von Blöcken unterteilt. Im vorliegenden Fall sind es zehn Blöcke, die von 0 bis 9 numeriert sind.

Das Grundkonzept des vorliegenden Verfahrens liegt darin, daß eine größere Wirksamkeit für die Komprimierung graphischer Information dadurch erzielt wird, daß nur die graphische Information der Blöcke übertragen wird, die Impulse enthalten, was in F i g. 2 den dunklen Bereichen des graphischen Dokuments entspricht. Zusätzlich kann dieses Verfahren auch mit bekannten Komprimierungsmethoden kombiniert werden, um einen noch höheren Wirkungsgrad zu erreichen. Fig. 3 zeigt die Impulskette von Fig. 2 nach Umwandlung in die Delta-Form. Bei dieser Operation

wird die erste Zeile ohne Änderung wiedergegeben. Die zweite Zeile wird dann mit der ersten Zeile Bit für Bit verglichen. Ein logisch negatives oder »delta weiß«-Signal, das in Fig. 3 als kein Impuls dargestellt ist, wird erzeugt, wenn die entsprechenden Bits zweier Zeilen

jo gleich sind, während ein logisch positives oder »delta schwarz«-Signal, das in F i g. 3 als ein positiver Impuls gezeigt ist, erzeugt wird, wenn die entsprechenden Bits zweier Zeilen unterschiedlich sind. Die Delta-Modulation definiert daher statt des Bereiches des Dokuments selbst, dessen Umriß. Der Prozeß wird für nachfolgende Zeilen in der Weise wiederholt, daß eine bestimmte Zeile mit der vorangegangenen Zeile verglichen wird (nicht mit der Delta-Form der vorangegangenen Zeile), bis alle Zeilen umgewandelt wurden. Die Wirksamkeit der Komprimierung nach dieser Methode ergibt sich aus der starken Korrelation zwischen benachbarten Zeilen der meisten graphischen Dokumente, so daß das Verhältnis der »delta schwarz«-Information zur »delta weiß«-lnformation im allgemeinen ziemlich niedrig ist.

Bei vielen Anwendungen kann der Wirkungsgrad der Komprimierung dadurch noch weiter angehoben werden, daß Impulse mit einer Länge unterhalb eines gewissen Wertes, etwa »delta schwarz«-Impulse, die nur aus einem Bit bestehen, wie in F i g. 4 gestrichelt gezeigt,

mi unterdrückt werden. Obwohl diese Methode, die im folgenden als modifizierte Delta-Modulation bezeichnet wird, einen leichten Auflösungsverlust zur ^Polge hat, ist sie in vielen praktischen Fällen akzeptabel. Ein »delta schwarz«-lmpuls, dessen voreilende oder nacheilende Flanke nur ein Bit von einem benachbarten Block entfernt ist, könnte ebenfalls unterdrückt werden.

Fig. 5 zeigt einen Teil der Impulskette von Fig. 3, wobei nur jene Blöcke, die eine »delta schwarz«-lnformation enthalten, aufrechterhalten und mit Zeilen- und

'■■ Blocksignalen kombiniert sind. Ein logisch positives Signal »1« kennzeichnet eine Zeile oder einen Block, der eine »delta schwarz«-lnformation enthält, die wenigstens aus einem Bit besieht, währenH , i;· logisch negatives Signal »0« eine Zeile oder einen Block kennzeichnet, der keine ,.-uJ.la schwarzw-information besitzt. Wenn eine bestimmte Zeile (wie z. B die Zeile 1 im Beispiel) keine »delta schwarzw-lniorniaiion enthält, wird nur ein negatives /eiiciisignal »0« geliefert. Wenn

wenigstens ein Block einer bestimmten Zeile wenigstens ein Bit einer »delta schvarzx-inlormation enthält, winJ ein positives Zeiknsignal />!3 erzeugt. Dem Zeilensignal folgt ein Blocksignal, das an/.eigt, welcher der Blöcke dieser 7: :;■ ir aufeinanderfolgender Reüu nngci>^r<lnp!. wob«.! die Blöcke, die keine »delta schwar/u-lnlormation enthalten, forlgelassen werden,

Im Beispiel von F i g. 3 und 5 enthält die Zeile I keinerlei »delta schwarzH-lnfonnation, so daß nur ein negatives Zeilcnsignal »0« erzeugt wird. In Zeile ί sind jedoch die Bits 58 bis 60 des Blocks 5 und die Bits 61 bis 68 des Blocks 6 »delta schwarz«. Daher wird ein positives Zeilensignal »1« erzeugt, dem ein Blocksignal folgt. Die Bits 0 bis 9 des Blocksignals entsprechen den Blöcken 0 bis 9 der entsprechenden Zeile; die Bits 5 und

6 des Blocksignals für Zeile 2 sind daher positiv »1«, womit angezeigt wird, daß die Blöcke 5 und 6 eine »delta schwarze-Information enthalten. Dem Blocksignal folgen die Blöcke 5 und 6 in dieser Reihenfolge.

In ähnlicher Weise enthalten in Zeile 3 die Blöcke 4 bis 7 »delta schwarzw-Information. weshalb die Bits 4 bis

7 des Blocksignals positiv »1« sind, während der Rest negativ »0« ist.

Das vorliegende Verfahren ist auch auf einen Fall anwendbar, bei dem die Impulskette ohne vorherige Umwandlung in die Delte-Form. so wie sie vom Abtaster erzeugt wurde, komprimiert wird. Ebenso ist das Verfahren auch auf einen Fall anwendbar, bei dem die Impulskette kontinuierlich ist, anstatt in Zeilen unterteilt zu sein. In diesem Fall wird die Information in bestimmter Anordnung komprimiert, bei der einem Blocksignal die Blöcke, die Impulse enthalten, folgen. Wenn die Impulskette in Zeilen unterteilt ist, haben die komprimierten Daten die allgemeine Form »Zeilensignal + Blocksignal + Blöcke«, die Impulse enthalten.

F i g. 6 zeigt eine Vorrichtung bzw. ein System zum Komprimieren graphischer Information gemäß dem oben beschriebenen Verfahren, bei dem nur Blöcke aufrechterhalten werden, die positive Impulse enthalten. Es wird angenommen, daß die Eingangsinformation in Form einer elektrischen Impulskette codiert ist, die in eine bestimmte Anzahl von Blöcken gleicher Länge und eine bestimmte Anzahl von Zeilen unterteilt ist, wobei jede Zeile die gleiche Anzahl von Blöcken aufweist. Die Eingangsinformation soll die Form von F i g. 2 besitzen.

Ein wahlweise zu verwendender Delta-Konverter A besitzt ein Schieberegister 10 und einen Komparator 12. Der Konverter A ist nicht erforderlich, wenn die Information bereits in Delta-Form geliefert wird oder wenn sie direkt aus der Form von F i g. 2 komprimiert werden soll. Die Eingangsinformation wird dem Eingang des Schieberegisters 10 und gleichzeitig einem Eingang des Komparators 12 zugeführt Der Ausgang des Schieberegisters 10 ist mit einem anderen Eingang des Komparators 12 verbunden. Der Ausgang des Komparators 12 ist mit einem Eingang eines Logikregisters 14 einer ersten Einrichtung B und ebenfalls mit dem Eingang eines Pufferregisters 16 einer zweiten Einrichtung C verbunden. Ein Ausgang des Logikregisters 14 ist mit dem Eingang eines Blockregisters 18 verbunden, das eine Bit-Kapazität besitzt, die gleich der Anzahl der Blöcke pro Zeile (im beschriebenen Fall 10) ist, wobei jedes Bit einer bestimmten Blockposition in der Zeile entspricht. Ausgänge des Blockregisters 18 und des Pufferregisters 16 sind mit Eingängen eines Logikgatters 20 verbunden, dessen Ausgang mit einem Eingang eines Mischers 22 verbunden ist Eine dritte Einrichtung D weist eine Logikeinheit 24 auf, die einen Em«<mf 26 hc-it/1 und deren Ausgang mn einem anderen bindung des Mische"··, 22 verbunden \'Λ. LVr Hingang 26 der I.ogikeinheit 24 kann entweder mit einem oder mit beiden Ausgängen 28 und 30 des ι l.ogikregisltrs 14 bzw. des Pufferregislers 16 verbunden sein, hin dritter lungang des Mischers 22 ist mit einem anderen Ausgang ies Blockregisters 18 verbunden.

Im Bcii !<-■!") wird d'e erste Zeile in das Schieberegister IC und den Komparator 12 eingeleitet, wobei sowohl

ip uas Schieberegister 10 als auc'.i das Pufferregister 16 die kapazität haben, die gesamte Zeile zu speichern. Die zweite /eilt, wird dann eingeführt; die erste Zeile wird ohne Änderung in das Pufferregister 16 und das Logikregister 14 überführt. Wenn die zweite Zeile

'■> einiäuii, wird sit- Bit für Bit mit der ersten Zeile verglichen; eine logisch positive »1« bzw. ein »delta schwarz«-Signal wird in das Pufferregister 16 und das Logikregister 14 geleitet, wenn die verglichenen Bits unterschiedlich sind. Eine logisch negative »0« bzw. ein »delta weiß«-Signal wird in das Pufferregister 16 und das Logikregister 14 gegeben, wenn die verglichenen Bits gleich sind. Während des Vergleichsprozesses wird der Inhalt des Schieberegisters 10, der zuvor die erste Zeile enthielt, nacheinander Bit für Bit durch die zweite Zeile ersetzt. Wenn die Operation vollendet ist, enthält das Schieberegister 10 die zweite Zeile und ist bereit für die Einführung der dritten Zeile. Während des Prozesses wurde die zweite Zeile in die Delta-Form überführt und in das Pufferregister 16 und das Logikregister 14 eingeleitet. Das Pufferregister 16 enthält daher die gesamten 100 Bits der Delta-Information, die vom Konverter A umgewandelt wurden. Dieser Prozeß wird für jede Zeile wiederholt.

Das Logikregister 14 ist in beliebiger bekannter Weise angeordnet, um den Ausgang des Konverters A Bit für Bit zu untersuchen und zu entscheiden, welcher der Blöcke eine »delta schwarzw-Information enthält. Ein logisch positives Signal »1« wird entsprechend einem Block, der eine »delta schwarz«-Information

4(i enthält, in jedem Bit des Blockregisters 18 gespeichert, während ein logisch negatives Signal »0« entsprechend den Blöcken, die keine »delta schwarzw-Information enthalten, in den Bits des Blockregisters 18 gespeichert werden. Auf diese Weise wird das in F i g. 5 dargestellte

Jj Blocksignal zusammengestellt. Das Logikgatter 20 hat Zugriff zu den Inhalten des Pufferregisters 16 und empfängt das Blocksignal als einen Steuereingang vom Blockregister 18; das Logikregister 20 ist in beliebiger bekannter Art ausgerüstet, um die Blöcke, die in dem

■"·« Pufferregister 16 gespeichert sind und eine »delta schwarz«-Information enthalten, unter der Steuerung des Blocksignals aus dem Blockregister 18 in aufeinanderfolgender Weise durchzulassen. Sowohl das Biocksignal als auch die Blöcke, die eine »delta schwarz«-Information enthalten, werden zum Mischer 22 geführt.

Die Logikeinheit 24 ist mit dem Pufferregister 16 oder dem Logikregister 14 oder mit beiden verbunden und in beliebiger bekannter Weise ausgestattet um feststellen zu können, ob die verarbeitete Zeile »delta schwarz«-In-

<■>" formation enthält; wenn dies der Fall ist, liefert die Logikeinheit 24 ein logisch positives Signal »1« zum Mischer 22 und ein logisch negatives Signal »0«, wenn dies nicht der Fall ist Dieses Signal ist das Zeilensignal.

Der Mischer 22 kombiniert das Zeilensignal, das

'■ Blocksignal und die Blöcke, die »delta schwarz«-Information enthalten, in der zweiten vorbestimmten Anordnung wie folgt: Zeilensignal + Blocksignal (wenn das Zeilensignal positiv ist) + Blöcke, die »delti

Schwärze-Information enthalten (wenn das Zeuensignai positiv ist).

Der Ausgang des Mischers 22 ist zu einem Übertragungsglied L geführt, das vorgesehen sein kann, um die komprimierte Inform.ι··· ^i im wesentlichen unverändert üher einen Übertragungskanal an eine Empfangseinheit zu übertragen, um mit i^r eine RadiotnigerweMe zur Radioübertragung zu modulieren oder um mit ihr einen Lichtstrahl für die Übertragung mittels Laser oder Faseroptiken zu modulieren. Das Übertragungsglied L soll die Verbindung zwischen einer Übertragungseinheit und einer Empfangseinheit schaffen, was im einzelnen nicht Gegenstand der Erfindung ist.

F i g. 7 zeigt eine Expansionscinheit, uie dazu dient, die Delta-Information aus der Komprimierungseinheit von F i g. 6 auseinanderzuziehen, und die ursprüngliche graphische Information zusammenzusetzen. Die Einheiten von Fig.6 und 7 bilden zusammen mit dem Übertragungsglied L ein System zur Übertragung und zum Empfang graphischer Information, die in Form einer elektrischen Impulskette codiert ist. Eine Wiedergabeeinrichtung, die dazu dient, den expandierten Ausgang der Einheit von F i g. 7 in eine visuelle Form zu übertragen, ist nicht Teil der Erfindung.

Eine erste Speichereinrichtung besitzt ein Pufferregister 32, während eine zweite Speichereinrichtung ein Blockregister 34 aufweist; das Pufferregister 32 und das Blockregister 34 sind dem Pufferregister 16 bzw. dem Blockregister 18 von F i g. 6 ähnlich. Das Pufferregister 32, das Blorkregister 34 und ein Flip-Flop 40 besitzen Eingänge, die mit dem Ausgang des Übertragungsgliedes L verbunden sind; sie speichern die Blöcke, die »delta schwarz«-Information enthalten, das Blocksignal bzw. das Zeilensignal. Ein Logikgatter 36 ähnlich dem Logikgatter 20 von F i g. 6 besitzt Eingänge, die mit den Ausgängen des Pufferregisters 32 und des Blockregisters 34 verbunden sind, und einen Ausgang, der mit einem Eingang eines !Comparators 38 verbunden ist. Der Komparator 38 besitzt einen weiteren Eingang, der mit dem Ausgang des Flip-Flops 40 verbunden ist, und liefert an seinem Ausgang die ausgedehnte bzw. auseinandergezogene Graphik-Information, die in ihre Ursprungsform zusammengesetzt bzw. umgewandelt wurde. Ein Delta-Graphik-Inverter besitzt ein Schieberegister 42, dessen Eingang mit dem Ausgang des Komparator 38 und dessen Ausgang mit einem anderen Eingang des Komparators 38 verbunden ist. Der Eingang eines Inverters 44 ist mit dem Ausgang des Schieberegisters 42 verbunden, während sein Ausgang mit noch einem anderen Eingang des Komparators 38 verbunden ist Die Wirkungsweise der Empfangseinheit von F i g. 7 ist im wesentlichen komplementär zu der der Obertragungseinheit von Fig.6. Wie oben erwähnt, werden das Zrüensignal, das Blocksignal und die Blöcke, die eine »delta schwarz«-Information enthalten, in dem Flip-Flop 40, dem Blockregister 34 bzw. dem Puffen egister 32 gespeichert. Wenn das Zeilensignal im Flip-Flop 40 logisch negativ »0« ist und damit andeutet, daß die verarbeitete Zeile keine »delta schwarz«-Information besitzt, läßt der Komparator 38 den Inhalt des Schieberegisters 42 unverändert durch. Wenn das Zeilensignal logisch positiv »1« ist und damit angibt, daß

ίο die Zeile »delta schwarzw-Information enthält, findet der folgende Ablauf statt:

Während der Verarbeitung der vorangegangenen Zeile war die Delta-Darstellung dieser Zeile mittels des Komparators 38 in die Ursprungsform expandiert und

is ausgegeben. Außerdem war die expandierte Form der vorangegangenen Zeile in dem Schieberregister 42 gespeichert, was aus der folgenden Beschreibung verständlich wird. Das Logikgatter 36 läßt in beliebiger bekannter Weise, unter der Steuerung des Blocksignals im Biockregister 34 die Blöcke nacheinander durch. Wenn ein Bit eines Blocksignals, das einem bestimmten Block entspricht, logisch positiv ist, läßt das Logikgatter 36 den entsprechenden Block zum Komparator 38 durch. Ist das Bit logisch negativ, erzeugt das Logikgatter 36 einen Block ohne Impulse. In dieser Weise wird die komprimierte Delta-Information zur Standard-Delta-Form expandiert.

Aus den oben erläuterten Gründen ist der Delta-Inverter wahlweise zu verwenden; wenn er vorgesehen wird, arbeitet er folgendermaßen.

Die vorangegangene Zeit wird in expandierter und invertierter Form vom Schieberegister 42 und dem Ausgang des Logikgatters 36 gleichzeitig zum Komparator 38 geführt und Bit für Bit verglichen. Wenn das Delta-Eingangsbit der vom Logikgatter 36 verarbeiteten Zeile logisch negativ ist, was anzeigt, daß die entsprechenden Bits der beiden Zeilen gleich sind, wählt der Komparator 38 seinen direkten Eingang vom Schieberegister 42 aus und läßt das Bit vom Schieberegister 42 zum Ausgang des Komparators 38 ohne Änderung passieren. Wenn jedoch das Bit vom Logikgatter 36 logisch positiv ist, was bedeutet, daß die Bits der beiden Zeilen unterschiedlich sind, wählt der Komparator 38 seinen Eingang vom Inverter 44, so daß das Bit vom Schieberegister 42 an dem Ausgang des Komparators 38 in logisch invertierter Form erscheint Da jedes Bit einer Zeile aus der Delta- in seine Ursprungsform invertiert wird, wird die invertierte Form im Schieberegister 42 gespeichert, um das entsprechende Bit der vorangegangenen Zeile zu ersetzen; nachdem eine Zeile verarbeitet und ausgegeben wurde, wird eine Kopie der endgültigen Form für den Vergleich mit der nächsten Zeile im Schieberegister 42 gespeichert

Hierzu 5 Blatt Zeichnungen

Claims

Patentansprüche:

1. Verfahren zum Komprimieren einer binären Informationsfolge, die durch zeilenmäßiges Abtasten einer graphischen Vorlage erhalten wurde und aus Gruppen einer jeweils gleich großen Anzahl von Bits besteht, bei dem die einzelnen Gruppen daraufhin überprüft werden, ob sie nur Bits der ersten Art (z. B. logische NULL) oder wenigstens ein Bit der zweiten Art (z. B. logische EINS) enthalten und bei dem ein Gruppenkennzeichenbit erzeugt wird, das die beiden möglichen Fälle unterscheidet, bei dem ferner bei Auftreten des ersten Falles (nämlich: Gruppe enthält nur Bit der ersten Art) stellvertretend für die gesamte Gruppe nur das Kennzeichenbit erzeugt wird, und bei dem bei Auftreten des zweiten Falles (nämlich: Gruppe enthält wenigstens ein Bit der zweiten Art) eine weitere Unterteilung der Gruppe in Blöcke von Bits einer jeweils gleichen Anzahl vorgenommen wird, die einzeln daraufhin überprüft werden, ob sie nur Bits der ersten Art oder wenigstens ein Bit der zweiten Art enthalten, und bei dem ein Blockkennzeichenbit für jeden Block erzeugt wird, das die beiden möglichen Fälle unterscheidet, bei dem ferner bei Auftreten des ersten Falles (nämlich: Block enthält nur Bits der ersten Art) stellvertretend für den Block nur das Blockkennzeichenbit erzeugt wird und bei dem bei Auftreten des zweiten Falles (närnlich: Gruppe enthält wenigstens ein Bit der zweiten Art) der Block zusätzlich zu dem Blockkennzeichenbit ungeändert übernommen wird, d a durch gekennzeichnet, daß die Gruppe von Bits die Informationsfolge einer Abtastzeile darstellt und die jeweils einer Zeile zugeordneten Blockkenn-Zeichenbits als fortlaufende Folge von Bits gebildet werden, und daß an diese Folge von Bits diejenigen Blöcke ungeändert in der Reihenfolge ihres Auftretens in der ursprünglichen Informationsfolge angeschlossen werden, die wenigstens ein Bii der zweiten Art enthalten.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die binäre Information aufeinanderfolgender Zeilen vor dem Komprimieren nach dem Delta-Modulationsverfahren umcodiert wird.

3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß die Blöcke, die wenigstens ein Bit der zweiten Art enthalten, daraufhin untersucht werden, wie viele unmittelbar aufeinanderfolgende Bits der zweiten Art in jedem Block enthalten sind, und daß diese aufeinanderfolgenden Bits unterdrückt werden, wenn sie unter einer bestimmten Anzahl liegen.

4. Vorrichtung zum Durchführen des Verfahrens nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, daß ein Zeilenspeicher (16) vorgesehen ist, in dem die binäre Information einer Zeile speicherbar ist, daß ferner an den Eingang des Zeilenspeichers ein Logikregister (14) angeschlossen ist, dem die information einer Zeile ebenfalls <^i(| zuführbar ist und das die Kennzeichenbits erzeugt, daß an dieses Logikregister ein Blockrcgistcr (18) angeschlossen ist, das die Kennzeichenbits speichert, daß an den Zeilenspeicher (16) und das Blockregister (18) eine logische Einheit (20, 22) angeschlossen ist, ■ > die für jede Zeile eine binäre Information in der folgenden Reihenfolge erzeugt:
Zeilenkennzeichenbit, Blockkennzeichenbits, Ulockinformation.

5. Vorrichtung nach Anspruch 4 zum Durchführen des Verfahrens nach Anspruch 2, dadurch gekennzeichnet, daß ein ein Schieberegister (10) und einen daran angeschlossenen Komparator (12) aufweisender Delta-Konverter ^/vorgesehen ist, und daß der Delta-Konverter ausgangsseitig an den Zeilenspeichcr (16) und das Logikregister (14) angeschlossen ist.