DE19531049C2 - Verfahren zum Komprimieren von Daten und Codierungsvorrichtung - Google Patents

Description

Die vorliegende Erfindung betrifft ein Verfahren zum Komprimie­ ren von Daten und eine Codierungsvorrichtung.

Eine Bildinformation beinhaltet eine große Zahl von Informatio­ nen. Zum Beispiel benötigt ein Bild (1/30 Sekunden) eines Fern­ sehbildes Bildinformationen der Menge, die der von Testdaten für eine Kopie eines Buches entsprechen. Weiterhin wird in vie­ len Fällen für Bilddaten Echtzeitübertragung gebraucht, und es ist sehr schwierig eine solch große Anzahl von Informationen in Echtzeit zu übertragen.

Folglich wird eine solche Technik verwendet, bei der Bilddaten vor der aktuellen Übertragung komprimiert werden, und die kom­ primierten Daten werden übertragen und werden auf der Empfän­ gerseite expandiert. Da dies die Anzahl der übertragenen Signa­ le reduzieren kann, kann eine größere Anzahl von Informationen in demselben Zeitabschnitt über denselben Übertragungsweg über­ tragen werden. Daher ist die Signalkompressionstechnik im Feld der Bildverarbeitung sehr wichtig.

Als ein Verfahren für das Obige gibt es eine sogenannte Codie­ rungsverarbeitung variabler Länge entsprechend der kurze Codes Mustern zugeordnet werden, die in dem zu übertragenden Bildda­ ten häufig erscheinen, und relativ lange Codes weniger häufig erscheinenden Bitmustern zugeordnet werden. Fig. 1 zeigt ein Beispiel einer Bilddatenkompressionsverarbeitungsvorrichtung, die solch eine Codierungsverarbeitung variabler Länge verwen­ det. Diese Vorrichtung wurde in der nachveröffentlichten DE 44 08 522 A1 durch dieselbe Anmelderin, wie die der vor­ liegenden Anmeldung, vorgeschlagen. In diesem Beispiel ist ein Verarbeitungsdiagramm der Bildkompression, die das durch den MPEG Standard festgelegte Codierungssystem verwendet, gezeigt.

Wie in Fig. 1 gezeigt ist, werden zu komprimierende Bilddaten ID über einen Subtrahierer 200 und einen Auswähler bzw. Schal­ ter 218 einer DCT (diskrete Kosinus Transformation) Verarbei­ tungsvorrichtung 202 zur Verfügung gestellt. Die DCT Verarbei­ tungsvorrichtung 202 wandelt das Eingabesignal in Frequenzkom­ ponenten um. Das durch die DCT Verarbeitungsvorrichtung 202 verarbeitete Signal wird weiter durch einen Quantisierer 204 quantisiert. Die Quantisierung reduziert relativ die Komponen­ ten in einem Hochfrequenzbereich der durch die DCT Verarbeitung in Frequenzkomponenten umgewandelte Daten. Dies verursacht kei­ ne merkliche Verringerung der Bildqualität für das menschliche Auge, und wird deshalb zur Reduzierung der zu übertragenden Datenmenge durch Entfernen der Hochfrequenzkomponenten durch­ geführt.

Der quantisierte Wert (d. h. Lauflängenwert) wird an eine Codie­ rungseinheit variabler Länge 206 angelegt, die ein Codieren variabler Länge des Wertes durchführt. Der codierte Wert wird als komprimierter Bildwert VD über einen Puffer 208 ausgegeben.

Ein Ausgang des Quantisierers 204 wird auch an einen inversen Quantisierer 210 und eine inverse DCT Verarbeitungseinheit 212 angelegt. Der inverse Quantisierer 210 und die inverse DCT Ver­ arbeitungseinheit 212 sind zur Bewegungsvorhersage, die später beschrieben wird, vorgesehen. Ein Ausgang der inversen DCT Ver­ arbeitungseinheit 212 ist auch an einen Addierer 214 angelegt.

Der Bilddatenwert ID wird auch an eine Bildvorhersageeinheit 216 angelegt. Die Bildvorhersageeinheit 216 sagt zum Beispiel die Bewegung des Bildes zwischen (Halb-) Bildern voraus und überträgt Informationen, die nur auf das bewegende Bild bezogen sind, zum Glätten der Daten und zum Zulassen weiterer Kompres­ sion zum Reduzieren der Übertragungsmenge. Der Wert nach Ver­ arbeitung der Vorhersage wird an den Addierer 214 angelegt.

Der Ausgabewert des Addierers 214 wird über einen Selektor bzw. Schalter 220 an den Subtrahierer 200 und die Bildvorhersageein­ heit 216 angelegt. Aufgrund der Auswähloperation der Auswähler 218 und 220 wird die Bildkompression unter Berücksichtigung der Bewegungsvoraussage durchgeführt.

Fig. 2 ist ein schematisches Blockdiagramm der in Fig. 1 ge­ zeigten Codierungseinheit variabler Länge 206. Wie in Fig. 2 gezeigt ist, wird ein vom Quantisierer 204 in Fig. 1 angelegter Lauflängenwert von zum Beispiel 8 Bits in einen Laufwert und in einen Pegelwert durch einen Lauflängenkonverter 236 umgewan­ delt. Diese Werte sind gleichlange Werte. Der Pegelwert stellt das Niveau des Laufwertes dar, der nicht 0 ist. Der Laufwert stellt die Anzahl der Werte 0, die einem anderen Wert als 0 folgen, dar. Wie oben beschrieben, beinhaltet die Hochfrequenz­ komponente aufgrund der DCT Verarbeitung und Quantisierung vie­ le 0's. Daher kann die Kompression unter Verwendung der Lauf­ längenumwandlung effektiv durchgeführt werden. Der Laufwert und der Pegelwert werden an einen Daten-RAM (Speicher mit wahlfrei­ em Zugriff) 238 für Lauflängenwerte angelegt, und werden an eine Umwandlungseinheit Lauflängenwert zu Code variabler Länge 240, nachdem sie in die Form von (Lauf, Pegel) umgewandelt wur­ den, angelegt. Die Umwandlungseinheit Lauflängenwert zu Code variabler Länge 240 wandelt den (Lauf, Pegel) Wert in Codes variabler Länge um zum Anlegen derselben an einen Multiplexer 242. Die Umwandlungseinheit Lauflängenwert zu Code variabler Länge 240 wird später im Detail beschrieben werden.

Inzwischen wird eine Steuerinformation, die Kompressionsverfah­ ren und Datengröße beinhaltet, an ein Daten-RAM 232 für einen Kopf angelegt. Ein von dem Kopfdaten-RAM 232 unter Verwendung der obigen Steuerinformation als eine Adresse ausgelesener Wert wird an eine Kopferzeugungseinheit 234 angelegt. Die Kopferzeu­ gungseinheit 234 und die Umwandlungseinheit Lauflängenwert zu Code variabler Länge 240 legen Steuersignale an das Daten-RAM 232 für einen Kopf und an das Daten-RAM 238 für einen Lauflän­ genwert an und lesen damit jeweils Daten davon aus.

Die Kopferzeugungseinheit 234 gibt den Kopf des Wertes aus, und die Umwandlungseinheit Lauflängenwert zu Code variabler Länge 240 gibt einen codierten Wert variabler Länge aus. Der Multi­ plexer 242 wählt entsprechend einem von einer ganzen Steuer­ schaltung 230 gesendeten Auswahlsignal die Ausgabe der Kopfer­ zeugungseinheit 234 und die Ausgabe der Umwandlungseinheit Lauflängenwert zu Code variabler Länge 240 aus, und legt diesen an einen FIFO-Puffer 244 an.

Der FIFO-Puffer 244 puffert in Reaktion auf die von der Kopfer­ zeugungseinheit 234 und von der Umwandlungseinheit Lauflängen­ wert zu Code variabler Länge 240 die Ausgabe des Multiplexers 242 in der FIFO-Art, und gibt diese in Reaktion auf ein von einer parallelen/seriellen (P/S) Schnittstelle 246 gesendeten Ausgabeforderungssignal aus. Der FIFO-Puffer 244 ist dafür vor­ gesehen, die Abstimmung zwischen einer Verarbeitungsgeschwin­ digkeit der Codierungseinheit variabler Länge 206 und einer Geschwindigkeit der externen Ausgabe von Daten herzustellen.

Die parallele/serielle Schnittstelle 246 reagiert auf das von dem in Fig. 1 gezeigten Puffer 208 gesendeten Steuersignal, und legt die Daten an den Puffer 208 entsprechend demselben Taktsi­ gnal an.

Die ganze Steuerschaltung 230 ist zum Steuern verschiedener Be­ reiche und Einheiten in der Codierungseinheit variabler Länge 206 vorgesehen, wie die Kopfinformation und den Wert auf einer Zeitachse zu multiplexen entsprechend dem beim Codieren varia­ bler Länge verwendeten Standard.

Fig. 3 zeigt schematisch den Aufbau der Umwandlungseinheit Lauflängenwert zu Code variabler Länge 240. Wie in Fig. 3 gezeigt ist, beinhaltet die Umwandlungseinheit Lauflängenwert zu Code variabler Länge 240 einen Speicher 250, der eine Tabelle von Codes variabler Länge speichert, auf die unter Verwendung des Laufwertes und des Pegelwertes als eine Adresse zum Ausgeben des entspre­ chenden Codes variabler Länge und seine Codelänge zugegriffen wird, eine Code-variabler-Länge-Erzeugungsschaltung 252 zum Erzeugen eines Codes variabler Länge basierend auf den vom Speicher 250 ausgelesenen Wert und eine Steuerschaltung 254, die das Lesen vom Speicher 250 und den Betrieb der Code varia­ bler-Länge-Erzeugungsschaltung 252 entsprechend dem von der ganzen Steuerschaltung 230 gesendeten Steuersignal (Fig. 2) steuert, während sie Kontrollsignale an benachbarte Schaltungen anlegt.

Wie in Fig. 4 gezeigt ist, beinhaltet die Tabelle von Codes va­ riabler Länge im Speicher 250 eine Mehrzahl von Werten Codes variabler Länge 266, die an entsprechenden Adressen angeordnet sind. Jede Tabelle von Codes variabler Länge 266 beinhaltet einen Bereich Codes variabler Länge 268 mit einer Breite von 17-Bit der Codes variabler Länge entsprechend der Kombination des gegebenen (Lauf, Pegel) speichert, und einen Codelängenbe­ reich 270 mit einer Breite von 5-Bit, der eine Information speichert, die eine Länge des im Bereichs Code variabler Länge 268 gespeicherten Codes variabler Länge angibt.

Die Adresse 260 zum Zugreifen auf den Wert Codes variabler Län­ ge 266 beinhaltet einen Laufbereich 262 von 6 Bits und einen Pegelbereich 264 von 7 Bits, und beinhaltet damit 13 Bits. Die Adresse wird von den von der vorherigen Stufe, wie in Fig. 3 gezeigt, angelegten Laufwert und Pegelwert erzeugt, und auf den Speicher der Tabelle Codes variabler Länge 250 wird mit der erzeugten Adresse zum Ausgeben des entsprechenden Wertes Codes variabler Länge zugegriffen.

Bei der Adresse 260 sind 6 Bits dem Lauf 262 und 7 Bits dem Pegel 264 zugewiesen, da ein Bereich des Laufs von 0 bis 63 ist und ein Bereich des Pegels zwischen ±41 ist, so daß jeweils 6 Bits und 7 Bits zum Darstellen dieser benötigt werden. Fig. 5 bis 10 zeigen die DCT Ausgabekoeffizienten der Tabellen von Codes variabler Länge von MPEG1. Diese Tabellen zeigen alle Hauptdaten.

Wie in Fig. 5 bis 10 zu sehen ist, wird der Bereich Codes va­ riabler Länge 268 aus 17 Bits gebildet und der Codelängenbe­ reich 270 aus 5 Bits gebildet, da die maximale Länge des Codes variabler Länge 17 Bits ist. Der Codelängenbereich 270 wird benötigt, da die Codelänge sogar zur Bearbeitung des Codes va­ riabler Länge benötigt wird, und die Codelänge des Codes varia­ bler Länge muß zusammen mit dem Code variabler Länge ausgegeben werden.

Kombinationen des Laufs und des Pegels, die nicht in den Tabel­ len in Fig. 5 bis 10 aufgeführt sind, werden durch eine andere Codierungseinheit (nicht gezeigt) als die obige Codierungsein­ heit variabler Länge verarbeitet.

Fig. 11 ist ein Blockdiagramm, das die Codierungsvorrichtung variabler Länge, die eine der Anmelderin bekannte Tabelle von Codes variabler Länge verwendet, zeigt, und daß auch einen Speicher für eine Tabelle von Codes variabler Länge 250 und eine Steuerschaltung 254 zeigt. Wie in Fig. 11 gezeigt ist, beinhaltet die der Anmelderin bekannte Codierungsvorrichtung variabler Länge 252 ein Register 282, ein 40-Bit Barrel Shifter (Schiebelogik) 104, ein Schieberegister 118 zum Ausgeben des Codes variabler Länge, eine Null-Erzeugungsschaltung 120, ein Register 108, einen 5-Bit Addierer 112 und ein Codelängenregi­ ster 114. Das Schieberegister 118 beinhaltet fünf 8-Bit Regi­ ster 118a-118e.

Die Steuerschaltung 254 legt jeweils Kontrollsignale a, b, d, f und g an den Speicher für eine Tabelle von Codes variabler Län­ ge 250, an das Register 108, an das Register 282, an das Regi­ ster variabler Länge 114 und an das Schieberegister 118 zum Betreiben derselben an.

Im Anfangszustand müssen beide, das Schieberegister 118 zum Ausgeben des Codes variabler Länge und das Register variabler Länge 284, zu 0 gelöscht werden. Der 40-Bit Barrel Shifter 104 ist betreibbar, den Eingabewert um einen durch das Codelängenre­ gister 114 angezeigten Wert zu schieben und denselben im Schie­ beregister 118 zu speichern.

Anfänglich sind jeweils der Code variabler Länge und die Code­ länge in der Tabelle von Codes variabler Länge in den Registern 282 und 114 gespeichert. Es wird angenommen, daß der so gespei­ cherte Code variabler Länge "001010" ist, und die so ge­ speicherte Codelänge "6" ist. Diese Werte werden jeweils von den Registern 282 und 108 an den 40-Bit Barrel Shifter 104 und an den 5-Bit Addierer 112 angelegt.

Der. Inhalt des Registers variabler Länge 284 ist 0. Daher läßt der 40-Bit Barrel Shifter 104 den Eingangswert ohne Schieben durch und legt den Eingangswert an das Schieberegister 118 zum Codeausgeben an.

Der 5-Bit Addierer 112 addiert den Eingangswert "6" und den In­ halt "0" des Codelängenregisters 114, und schreibt das Ergebnis "6" in das Codelängenregister 114. Das Codelängenregister 114 ist betriebsfähig, ein Steuersignal h an das Schieberegister 118 zum Schieben desselben anzulegen, und legt es auch als ein Da­ tenfreigabesignal an eine Schaltung der folgenden Stufe an, wenn der im Register 114 gespeicherte Wert sich auf oder über 8 erhöht. In diesem Fall ist der Inhalt jedoch "6", so daß das Schiebesignal h nicht ausgegeben wird.

Jetzt ist angenommen, daß ein codierter Code variabler Länge von "00001000" über das Register 282 an den 40-Bit Barrel Shif­ ter 104 angelegt wird, und daß eine Codelänge "8" an den Ein­ gang des 5-Bit Addierers 112 über das Register 108 angelegt wird.

Der Inhalt des Codelängenregisters 114 ist "6". Daher schiebt der 40-Bit Barrel Shifter 104 den Code variabler Länge um 6 Bits nach rechts, und speichert denselben im Schieberegister 118. Zu dieser Zeit wird der gespeicherte Inhalt des Schiebere­ gisters 118 zum Ausgeben des Codes aus dem anfänglich angeleg­ ten Code variabler Länge, gespeichert in 6 Bits beginnend von dem höchsten Bit, gebildet. Der momentan angelegte (d. h. zwei­ te) Code variabler Länge ist im siebten und den folgenden Bits gespeichert.

Der 5-Bit Addierer 112 addiert den Eingangswert "8" und den In­ halt "6" des Codelängenregisters 114, und schreibt das Ergebnis "14" in das Codelängenregister 114.

Das Codelängenregister 114 gibt das Schiebesignal h aus, und teilt seinen eigenen Inhalt gleichmäßig in acht, da der Inhalt sich zu 8 oder mehr erhöht hat. Das Schieberegister 118 zum Ausgeben des Codes reagiert auf das Schiebesignal h durch Schieben seiner Inhalte um 8 Bits nach links und Ausgeben des Inhalts des Schieberegisters 118a als codierter Wert (Bit- Strom) von seinem linken Ende. Somit wird der Inhalt des 8-Bit Registers 118a als Wert ausgegeben, und die Inhalte der Regi­ ster 118b, 118c, 118d und 118e werden jeweils zu den Registern 118a, 118b, 118c und 118d übertragen. Auch werden die 0's von 8 Bits von der Null-Erzeugungsschaltung 120 angelegt und in das Register 118e eingeschrieben.

Als ein Ergebnis der obigen Verarbeitung wird der Inhalt des Codelängenregisters 114 "6". In diesem Fall stellt der Inhalt des Codelängenregisters 114 die Bitanzahl des in dem 8-Bit-Re­ gister 118a gespeicherten Codes variabler Länge "001000" dar. Somit speichert das Codelängenregister 114 eine Datenlänge des effektiv im Codeausgabeschieberegister 118 gespeicherten Wer­ tes.

Wenn ein nächster Code variabler Länge eingegeben wird, wird der eingegebene Code variabler Länge um eine Bitzahl des im 8- Bit Register 118a gespeicherten Codes variabler Länge nach rechts geschoben, und dann im Schieberegister 118 gespeichert, so daß das Schieberegister 118 zum Ausgeben des Codes den näch­ sten Code variabler Länge an Stellen direkt folgend auf die des schon im Schieberegister 118 gespeicherten Codes variabler Län­ ge speichert.

Die obige Verarbeitung wird sich wiederholend auf den Code va­ riabler Länge und seiner vom Speicher 250 gesendeten Länge durchgeführt, und ein Zug Codes variabler Länge wird in der Form eines Bit-Stroms erzeugt.

Die Bildkompressionsvorrichtung in einer ähnlichen Technik glättet die Werte selbst durch Bewegungsvohersage, und führt weiter die DCT Verarbeitung und Quantisierung zum Entfernen der Hochfreqeunzkomponenten durch. Daher beinhalten die zu kompri­ mierenden Bildsignale eine große Zahl von Nullen, und können unter Verwendung Tabellen von Codes variabler Länge, zum Bei­ spiel in Fig. 5 bis 10 gezeigt, effizient komprimiert werden. Da ein Nachschlagetabellensystem verwendet wird, ist eine kom­ plizierte Verarbeitung nicht notwendig, und eine schnelle Co­ dierungsverarbeitung kann durchgeführt werden..

Jedoch weist die Codierungsvorrichtung variabler Länge, die das oben beschriebene Nachschlagetabellensystem verwendet, den Nachteil auf, daß eine großer Speicher benötigt wird. Wie aus Fig. 5 bis 10 ersichtlich ist, weisen die Codes variabler Länge Codelängen in einem Bereich von 2 bis 7 Bits auf. Beim Vorbe­ reiten der Tabellen von Codes variabler hänge in dem Speicher ist es jedoch schwierig, die Länge von Bereichen Codes varia­ bler Länge selbst als eine frei wählbare Bitlänge zu setzen, so daß ein Feld mit einer festgelegten Länge, das an die maximale Codelänge angepaßt ist, jedem Wert Codes variabler Länge zuge­ ordnet werden muß. Um daher einen Code variabler Länge darzu­ stellen, wird ein Wert von 22 Bits benötigt (Code variabler Länge von 17 Bits und Codelänge von 5-Bits). Um diese Tabelle von Codes variabler Länge in dem Speicher zu entwickeln, ist es notwendig, einen Speicher von mindestens 8 k Wörtern (achttau­ send Wörtern) (Adressenraum von 13-Bit Adressen) × 22 Bits vor­ zusehen.

Genauer, weisen die in Fig. 5 bis 10 gezeigten Tabellen von Codes variabler Länge nur zweihundert verschiedene Arten von Kombinationen des zu verarbeitenden Laufs und Pegels auf, aber der Platz von achttausend Wörtern wird benötigt, um die Tabel­ len im Speicher zu entwickeln. Daher wurde eine Codierungsver­ arbeitung variabler Länge verlangt, die den verwendeten Spei­ cherplatz effizienter nützen kann, und die den benötigten Spei­ cher reduzieren kann.

Ein Vorschlag zum Erreichen des obigen Verlangens ist in der japanischen Patentoffenlegungsschrift Nr. 4-142163 (1992) of­ fenbart. Entsprechend der Offenbarung dieser Veröffentlichung wird der Tatsache Aufmerksamkeit geschenkt, daß ein spezielles Wiederholungsmuster (z. B. von "0") oft in einem führenden Be­ reich des Codes variabler Länge gefunden wird, und daß der Code variabler Länge in eine Anzahl von Wiederholungen des Wiederho­ lungsmusters ausgehend von dem führenden Ende, dem verbleiben­ den Wert und der Länge des verbleibenden Wertes zum Speichern derselben umgewandelt wird. Beim Zugreifen auf den Speicher wird der Code variabler Länge durch Addition bestimmter Zeichen (z. B. 0) in der Anzahl, die der Wiederholungsanzahl des Wieder­ holungsmusters zu dem führenden Ende des verbleibenden Wertes entspricht, erzeugt.

Entsprechend dieser Art können die wiederholten 0's beginnend von dem führenden Ende durch eine kleine Zahl von Bits darge­ stellt werden. Zum Beispiel können zwei Bits die Wiederholungs­ anzahl von 0 bis 3 darstellen, können 3 Bits die Wiederholungs­ anzahl von 0 bis 7 darstellen, und können 4 Bits die Wiederho­ lungsanzahl von 0 bis 7 darstellen, und können 4 Bits die Wie­ derholungsanzahl von 0 bis 15 darstellen. Dies reduziert die gesamte benötigte Bitlänge zum Darstellen des Codes variabler Länge. Da die benötigte Bitlänge pro Adresse des Speichers ver­ ringert ist, kann die ganze Kapazität des Speichers verringert werden.

Auch wenn diese Technik verwendet wird, verbleibt jedoch immer noch ein großer ungenützter Bereich in dem Speicher. Es ist ge­ wünscht, einen solchen Bereich effizient zu verwenden. Ferner muß der nicht verwendete Bereich ohne einen Verlust des Vorteils des Nachschlagetabellensystems verwendet werden.

Aufgabe der Erfindung ist es, ein Verfahren zum Komprimieren von Daten und eine Codierungsvorrichtung bereitzustellen, bei denen die Kapazität eines für Codes variabler Länge benötigten Spei­ chers reduziert ist.

Die Aufgabe wird durch das Verfahren des Anspruches 1 oder die Codierungsvorrichtung des Anspruches 6 gelöst.

Weiterbildungen der Erfindung sind in den Unteransprüchen ange­ geben.

Es kann ein Vergleich zwischen der ersten Kombination, die die zweite gleichlange Bestimmungskomponente einer gegebenen Klasse beinhaltet, und der zweiten Kombination, die die zweite gleich­ lange Bestimmungskomponente aus einer Klasse, die im absoluten Wert größer als die oben gegebene Klasse ist, beinhaltet, in Verbindung mit der Größe des dritten Bereiches für die zweite gleichlange Bestimmungskomponente an jede Adresse durchgeführt werden, der die Tatsache zeigt, daß die Größe in der zweiten Kombination größer als die in der ersten Kombination ist. Jedoch kann die Größe des zweiten Bereichs für die erste gleichlange Bestimmungskomponente in der zweiten Kombination klein sein. Daher kann die ganze Bereichslänge festgelegt werden. Wenn eine solche Einteilung nicht gemacht wird, würde jeder der zweiten und dritten Bereiche genötigt sein, eine Größe aufzuweisen, die groß genug ist, um den maximalen Wert des absoluten Wertes der ersten gleichlangen Bestimmungskomponente und den maximalen Wert des absoluten Wertes der zweiten gleichlangen Bestimmungskompo­ nente zu speichern, so daß sich die Adressenlängen als Ganze erhöhen würde. Daher wird entsprechend der Erfindung die benö­ tigte Adressenlänge zum Zugriff reduziert. Dies ermöglicht die Reduzierung der Kapazität des Speichers für die Codes variabler Länge.

Bevorzugt wird der Code variabler Länge aus einer Anzahl von gegebenen, sich vom führenden Ende fortsetzenden ersten Zeichen und einem verbleibenden Code gebildet, und die Codelänge ist die Codelänge des verbleibenden Codes. Obwohl der die Zahl des füh­ renden und der fortsetzenden ersten Zeichen darstellende Bereich eine festgelegte Länge aufweist, kann die Anzahl der Zeichen, die der N-ten Potenz von zwei entsprechen, dargestellt werden, wobei N die Bitanzahl ist. Daher kann in dem Codierungssystem variabler Länge, in dem viele der Codes variabler Länge führende und fortsetzende erste gegebene Zeichen in eine Anzahl, die grö­ ßer als die N-te Potenz von 2 ist, beinhalten, die Datenlänge, die dem an jeder Adresse in der Tabelle gespeicherten Code va­ ialer Länge entspricht, reduziert werden im Vergleich mit dem Fall, bei dem der obige Aufbau nicht verwendet wird. Dieser Ef­ ekt wird größer entsprechend der Erhöhung der Anzahl von Codes variabler Länge mit denselben führenden und fortsetzenden Zei­ hen, die in der Anzahl größer als die N-te Potenz von 2 sind. Dies erlaubt eine weitere Reduzierung der Kapazität des Spei­ hers, der für Tabellen von Codes variabler Länge benötigt wird.

Wenn das Verfahren bei dem Bildkompressionscodierungsstandard MPEG verwendet wird, ist die erste gleichlange Bestimmungskompo­ nente der Laufwert, und die zweite gleichlange Bestimmungskompo­ nente ist der Pegelwert. Wenn das Verfahren bei dem Bildkompres­ sionscodierungsstandard H261 verwendet wird, ist die erste gleichlange Bestimmungskomponente der Laufwert und ist die zweie gleichlange Bestimmungskomponente der Pegelwert.

Entsprechend der Vorrichtung kann die zum Zugriff benötigte Adresse durch das Adressenerzeugungsmittel erzeugt werden. Da die Vorrichtung die Codes variabler Länge verwendet, die ent­ sprechend dem vorliegenden Verfahren gespeichert sind, kann die benötigte Adressenlänge kurz sein. Daher kann die Kapazität eines benötigten Speichers klein sein.

Entsprechend der Vorrichtung nach Anspruch 6 kann das Adressen­ erzeugungsmittel die zum Zugreifen benötigte Adresse erzeugen, und kann den Code variabler Länge, basierend auf der Anzahl der führenden und fortsetzenden gegebenen ersten Zeichen, auf dem verbleibenden Code und auf der Codelänge des verbleibenden Codes, die als ein Ergebnis des Zugriffs erhalten wurden, aus­ geben. Daher kann die benötigte Adressenlänge kürzer sein als im Stand der Technik, und die in jeder Adresse gespeicherte Daten­ länge kann reduziert sein. Daher kann die benötigte Kapazität eines Speichers klein sein. Länge führende und fortsetzende erste gegebene Zeichen in eine Anzahl, die größer als die N-te Potenz von 2 ist, beinhalten, die Datenlänge, die dem an jeder Adresse in der Tabelle gespei­ cherten Codes variabler Länge entspricht, reduziert werden im Vergleich mit dem Fall, bei dem der obige Aufbau nicht verwen­ det wird. Dieser Effekt wird größer entsprechend der Erhöhung der Anzahl von Codes variabler Länge mit denselben führenden und fortsetzenden Zeichen, die in der Anzahl größer als die N- te Potenz von 2 sind. Dies erlaubt eine weitere Reduzierung der Kapazität des Speichers, der für Tabelle von Codes variabler Länge benötigt wird.

Wenn das Verfahren bei dem Bildkompres­ sionscodierungsstandard MPEG verwendet wird, ist die erste gleichlange Bestimmungskomponente der Laufwert, und die zweite gleichlange Bestimmungskomponente ist der Pegelwert. Wenn das Verfahren bei dem Bildkompressionscodierungsstandard H261 ver­ wendet wird, ist die erste gleichlange Bestimmungskomponente der Laufwert und ist die zweite gleichlange Bestimmungskomponente Pegelwert.

Entsprechend der Vorrichtung kann die zum Zugriff benötigte Adresse durch das Adressenerzeugungsmittel er­ zeugt werden. Da die Vorrichtung die Codes varia­ bler Länge verwendet, die entsprechend dem vorliegenden Verfahren gespeichert sind, kann die benötigte Adressenlänge kurz sein. Daher kann die Kapa­ zität eines benötigten Speichers klein sein.

Entsprechend der Vorrichtung nach Anspruch 6 kann das Adressenerzeugungsmittel die zum Zugreifen benötigte Adresse erzeugen, und kann den Code variabler Länge, basierend auf der Anzahl der führenden und fortsetzenden gegebenen ersten Zei­ chen, auf dem verbleibenden Code und auf der Codelänge des ver­ bleibenden Codes, die als ein Ergebnis des Zugriffs erhalten wurden, ausgeben. Daher kann die benötigte Adressenlänge kürzer sein als im Stand der Technik, und die in jeder Adresse gespeicherten Datenlänge kann reduziert sein. Daher kann die benötigte Kapazität eines Speichers klein sein.

Es folgt die Beschreibung von Ausführungsbeispielen anhand der Figuren.

Von den Figuren zeigen:

Fig. 1 ein Verarbeitungsdiagramm einer Bildkom­ pressionsverarbeitung;

Fig. 2 ein Blockdiagramm einer Codierungsvorrich­ tung variabler Länge;

Fig. 3 ein Blockdiagramm einer Codierungsvorrich­ tung von Lauflängendaten variabler Länge in einer ähnlichen Technik;

Fig. 4 schematisch einen Aufbau einer Tabelle von Codes variabler Länger in der ähnlichen Technik;

Fig. 5 bis 10 Tabellen von Codes variabler Länge von ei­ nem DCT-Ausgabekoeffizienten des MPEG1;

Fig. 11 ein Blockdiagramm einer der Anmelderin be­ kannten Erzeugungseinheit von Codes varia­ bler Länge;

Fig. 12 ein Diagramm, das die Verteilung der Kom­ binationen von Lauf- und Pegeldaten der DCT-Ausgabekoeffizienten des MPEG1 zeigt;

Fig. 13 Kombinationen von Lauf- und Pegeldaten der DCT-Ausgabekoeffizienten des MPEG1 in Form einer Tabelle, in der die Kombinationen ba­ sierend auf dem Bereich des Pegels in Klas­ sen eingeteilt sind;

Fig. 14 schematisch einen Adressenaufbau zum Erzeu­ gen von Adressen für jeweilige Pegelberei­ che;

Fig. 15 und 16 Tabellen von Codes variabler Länge von ei­ nem DCT-Ausgabekoeffizienten des H261;

Fig. 17 die Verteilung der Kombination von in Fig. 6 gezeigten Lauf und Pegel;

Fig. 18 die Inhalte der in Fig. 17 gezeigten Ver­ teilung, aufgeteilt in Klassen basierend auf dem Pegelbereich in einer Tabellenform;

Fig. 19 schematisch ein Verfahren zum Erzeugen ei­ ner Adresse;

Fig. 20 ein Blockdiagramm, das eine Codierungsein­ heit für Lauflängendaten variabler Länge einer Ausführungsform der Erfindung zeigt;

Fig. 21 bis 27 Tabellen von Codes variabler Länge von ei­ nem DCT-Ausgabekoeffizienten des MPEG1;

Fig. 28 ein Blockdiagramm einer Adressenumwand­ lungsschaltung in eine Ausführungsform der Erfindung;

Fig. 29 den Betrieb einer Logikschaltung;

Fig. 30 schematisch ein Verfahren zur Erzeugung einer Adresse in einer Ausführungsform der Erfindung;

Fig. 31 ein Blockdiagramm einer Erzeugungsschaltung von Code variabler Länge in eine Ausfüh­ rungsform der Erfindung;

Fig. 32 bis 34 Ablaufdiagramme, die den Betrieb der Erzeu­ gungsschaltung für einen Code variabler Länge in einer Ausführungsform der Erfin­ dung zeigt;

Fig. 35 ein Beispiel einer Serie von Daten, die va­ riable Länge codiert werden sollen; und

Fig. 36 bis 38 eine Änderung von Inhalten von einem Schie­ beregister zum Ausgeben eines Codes.

Die vorliegende Erfindung verwendet die Tatsache, daß eine spe­ zielle Verbindung bei Kombinationen von Laufdaten und Pegelda­ ten existiert, die vorherbestimmt ist, zum Beispiel in Verbin­ dung mit einem DCT-Ausgabekoeffizienten des MPEG1. Fig. 12 zeigt die Verteilung der (Lauf, Pegel) Kombinationen des DCT- Ausgabekoeffizienten des MPEG1. Die Abszisse zeigt den Pegel an, und die Ordinate zeigt den Lauf an. In einem Bereich von einem kleinen absoluten Wert des Pegels, wie aus Fig. 12 er­ sichtlich ist, sind die Läufe, die mit solchen Pegeln kombi­ niert sind, in einem Bereich von 0 bis 31 verteilt. Sowie der absolute Wert des Pegels sich erhöht, erniedrigt sich die An­ zahl der mit den Pegeln kombinierten Läufen, und die absoluten Werte davon erniedrigen sich auch. In einem Bereich von einem großen absoluten Wert des Pegels, existieren Läufe nur mit ei­ nem Wert, d. h. "0".

Die in Fig. 12 gezeigten Kombinationen von Pegel und Lauf kön­ nen basierend auf den Bereich des Pegels, wie in der in Fig. 13 gezeigten Tabelle, eingeteilt werden. Entsprechend der in Fig. 13 gezeigten Einteilung gibt es vier eingeteilte Bereiche, d. h. Bereiche von -1 bis +1, -2 und 2 und von -6 bis -3 und von +3 bis +6, und einen anderen Bereich als diese. Jeder von die­ sen festgelegten Bereichen basierend auf dem Pegel wird in der vorliegenden Beschreibung als "Klasse" bezeichnet.

Wie in Fig. 13 gezeigt ist, ist der maximale Wert in einem Be­ reich des Pegels von -1 bis +1 des mit dem Pegel kombinierten Laufes 31. Die absoluten Werte der Pegel, die zu dieser Klasse gehören, sind 0 und 1. Daher kann der mit diesen zu dieser Klasse gehörenden Pegel kombinierte Lauf mit 6 Bits dargestellt werden, und der Pegelwert kann mit 2 Bits dargestellt werden.

In einem Bereich des Pegels von -2 und +2 sind mit diesen Pegel kombinierte Läufe im Bereich zwischen 0 und 16. Der absolute Wert des Pegels ist 2. Daher kann der mit dem zu dieser Klasse gehörenden Pegel kombinierte Wert mit 5 Bits dargestellt wer­ den, und der Pegel kann mit 3 Bits dargestellt werden. Entspre­ chend kann in dem Pegelbereich von -6 bis -3 und von +3 bis +6 der Lauf mit 3 Bits dargestellt werden und der Pegel kann mit 4 Bits dargestellt werden. In dem anderen Fall als in den obigen kann der Lauf mit 2 Bits dargestellt werden und der Pegel kann mit 7 Bits dargestellt werden.

Daher kann man, wie in Fig. 14 gezeigt ist, den Aufbau der Adresse zum Zugreifen auf die Tabelle von Codes variabler Länge entsprechend dem Bereich des Pegels ändern.

Genauer, werden jeweils 6 Bits und 2 Bits dem Laufwert und dem Pegelwert in dem Pegelbereich von -1 bis +1 zugeordnet. In dem Bereich des Pegel von -2 und +5, werden jeweils 5 Bits und 3 Bits dem Laufwert und dem Pegelwert zugeordnet. In dem Bereich von -6 bis -3 und von +3 bis +6 werden jeweils 3 Bits und 4 Bits dem Laufwert und dem Pegelwert zugeordnet. In dem anderen Bereich als in den obigen werden jeweils 2 Bits und 7 Bits dem Laufwert und dem Pegelwert zugeordnet.

Wenn die Adresse wie oben beschrieben geändert wird, treten Schwierigkeiten auf, wenn durch die Adressen dargestellten Speicherbereiche miteinander überlappen. Daher wird der führen­ de 2-Bit Bereich der Adresse als ein Flag bzw. Kennzeichen 50 verwendet, und 00, 01, 10 und 11 werden den jeweiligen Klassen (Pegelbereichen) zugeordnet. Bei der Erzeugung der Adres­ sen in dieser Art kann die gesamte Adreßlänge höchstens 11 Bits sein. Wenn die Einteilung in dieser Art nicht durchgeführt ist, werden für die Adresse wie schon beschrieben 13 Bits benötigt (siehe Fig. 4). Daher ist es verständlich, daß der Adreßraum auf etwa 1/4 unter Verwendung des in Fig. 14 gezeigten Adreß­ aufbaus verringert werden kann.

Das Vorhergehende kann entsprechend auf andere Bildcodierungs­ standards angewendet werden. Fig. 15 und 16 zeigen Tabellen von Codes variabler Länge von einem DCT-Ausgabekoeffizienten des H261. In Fig. 15 und 16 stellt "s" ein Zeichen dar. Genauer, s ist "0", wenn der Pegelwert positiv ist, und ist "1", wenn er negativ ist. Die Verteilung der Kombination von Lauf und Pegel ist in einem Diagramm von Fig. 17 gezeigt. In Fig. 17 zeigt die Abszisse den Pegel an, und die Ordinate zeigt den Lauf an. Auch bei der Kombination der DCT-Ausgabekoeffizienten von H261 ist, wie aus Fig. 17 ersichtlich ist, der maximale Wert des Lauf­ werts groß, wenn der absolute Wert des Pegelwerts klein ist, und der absolute Wert des Laufwerts erniedrigt sich wie der absolute Wert des damit kombinierten Pegels sich erhöht.

Fig. 18 zeigt eine Tabelle, in der die DCT-Ausgabekoeffizienten des H261 eingeteilt sind. Wie aus Fig. 18 ersichtlich ist, gibt es Klassen entsprechend den Pegelbereichen von 0 und 1, zwi­ schen 2 und 7, und von 8 und mehr. In diesen Fällen werden die Bitanzahl von 7, 7 und 8 benötigt, um die Kombination von Lauf und Pegel darzustellen.

Fig. 19 zeigt eine Art der Erzeugung einer Adresse zum Zugrei­ fen auf die DCT-Ausgabekoeffiziententabelle von H261, basierend auf dem Ergebnis von Fig. 18. In diesem Fall sind Flagbereiche bzw. Kennzeichenbereiche 52 in ähnlicher Weise vorgesehen, um das Überlappen von Bereichen von Codes variabler Länge, die zu den jeweiligen Klassen gehören, zu verhindern. "00" ist der Klasse der Pegel von 0 und 1 zugeordnet, "01" ist der Klasse der Pegel von 2 bis 7 zugeordnet, und "1" ist der anderen Klas­ se als die obigen zugeordnet. Damit können der Lauf und der Pe­ gel in den Klassen der Pegel von 0 und 1 und der Pegel von 2 bis 7 mit 7 Bits dargestellt werden. In der anderen Klasse als die obigen kann der Lauf und der Pegel mit 8 Bits dargestellt werden. Daher ist es verständlich, daß Codes variabler Länge in allen Pegelbereichen mit insgesamt nur 9 Bits adressiert werden können, in Bereichen die sich nicht miteinander überlappen.

Dasselbe Konzept kann auch bei einer Verarbeitung zum Umwandeln von Makroblockadressenerhöhungsdaten und Bewegungscode in Codes variabler Länge in Bildkompressionscodierungsstandards MPEG und H261, sowie bei einer Verarbeitung zum Umwandeln von Kombina­ tionsdaten von (Lauf, Pegel) in Codes variabler Länge in JPEG angewendet werden. Obwohl die folgende Beschreibung mit einer Vorrichtung und einem Tabellenaufbau zum Umwandeln der Kombina­ tionsdaten von (Lauf, Pegel) in Codes variabler Länge MPEG1 erfolgt, ist es für den Durchschnittsfachmann anhand der Be­ schreibungen der vorliegenden Anmeldung einfach zu verstehen, daß Tabellen für die jeweiligen oben beschriebenen Arten von Umwandlungen entsprechend zu dem ähnlichen Konzept gebildet werden können, und daß Codierungsvorrichtungen, die solche Ta­ bellen verwenden, gebildet werden können.

Eine in Fig. 20 gezeigte Umwandlungseinheit Codes variabler Länge für Lauflängendaten 60 kann in der Codierungseinheit va­ riabler Länge 206 anstatt der Umwandlungseinheit Codes varia­ bler Länge für Lauflängendaten 240 in der ähnlichen Art, die schon mit Bezug zu Fig. 2 beschrieben wurde, verwendet werden. Wie in Fig. 20 gezeigt ist, beinhaltet die Umwandlungseinheit Codes variabler Länge für Lauflängendaten 60 eine Adressenum­ wandlungsschaltung 62, einen Speicher 64 zum Speichern einer Tabelle von Codes variabler Länge entsprechend der Erfindung, eine Erzeugungsschaltung Codes variabler Länge 66, die basie­ rend auf einem Wert, der die Anzahl der führenden und fortset­ zenden 0's des von dem Speicher 64 angelegten Codes variabler Länge anzeigt, der verbleibende Code davon und die Codelänge des verbleibenden Codes betreibbar ist, zum Anfügen der fest­ gelegten Anzahl von 0's an das führende Ende des verbleibenden Codes zum Ausgeben des Codes variabler Länge, und einer Steuer­ schaltung 68 zum Steuern des Betriebs der Adressenumwandlungs­ schaltung 62, des Speichers 64 und der Code variabler Länge Steuerschaltung 66.

Die Adreßumwandlungsschaltung 62, dessen genauer Aufbau später beschrieben werden wird, empfängt einen Laufwert und einen Pe­ gelwert zum Erzeugen und Anlegen der Adresse an den Speicher 64 in der in Fig. 14 gezeigten Art. Die Adressenumwandlungsschal­ tung 62 gibt ein Codeumwandlungssignal aus, wenn sie eine ande­ re Kombination von (Lauf, Pegel), als die durch MPEG1 festge­ legten, entdeckt. Wenn dieses Codeumwandlungssignal ausgegeben wird, wird die Codierung der (Lauf, Pegel) Daten entsprechend einer anderen Art durchgeführt. Eine Einheit für diesen Zweck ist in der Figur nicht gezeigt.

Die im Speicher 64 gespeicherten Inhalte der Tabelle von Codes variabler Länge sind in Fig. 21 bis 27 gezeigt. Fig. 21 und 22 zeigen Kombinationen von (Lauf, Pegel), die der Klasse des Pe­ gelbereiches von -1 bis +1 angehören, Fig. 23 zeigt Kombinatio­ nen von (Lauf, Pegel), die der Klasse des Pegelbereiches von -2 und +2 angehören, und Fig. 24 zeigt Kombinationen von (Lauf, Pegel), die den Klassen des Pegelbereiches von -6 bis -3 und von +3 bis +6 angehören. Fig. 25 bis 27 zeigen Kombinationen von (Lauf, Pegel) in anderen Bereichen als die obigen.

Zum Beispiel ist, wie in Fig. 21 gezeigt ist, die gesamte Bit­ breite der Adressenbits in dem Pegelbereich, der der Klasse von -1 bis +1 angehört, 7 Bits, von denen die Bits vom siebten bis zum zweiten Platz den Laufwert darstellen, und das erste und nullte Bit den Pegelwert darstellen. Entsprechend stellen, wie in Fig. 23 gezeigt ist, in dem Pegelbereich von -2 und +2 die Bits vom siebten bis zum dritten Platz die Adressenbits des Laufwertes dar, und die Bits vom zweiten bis zum nullten Platz stellen den Pegelwert dar. In den Pegelbereichen von -6 bis -3 und von +3 bis +6 stellen die Bits vom siebten bis zum vierten Platz der Adressenbits den Laufwert dar, und die Bits vom drit­ ten bis zum nullten Platz stellen den Pegelwert dar. In dem anderen Bereich als die obigen stellen die Bits am achten und siebten Platz der Adressenbits den Laufwert dar, und die Bits vom sechsten bis zum nullten Platz stellen den Pegelwert dar.

Wie in Fig. 21 gezeigt ist, stellen Datenbits vom dreizehnten bis zum zehnten Platz die Anzahl der führenden und fortsetzen­ den 0's im Code variabler Länge entsprechend dem (Lauf, Pegel) dar. Die Bits vom neunten bis zum dritten Platz stellen den verbleibenden Code dar, d. h. einen Code von dem die führenden und fortsetzenden 0's entfernt sind. Die Bits vom zweiten bis zum nullten Platz stellen eine Codelänge des verbleibenden Co­ des dar. Zum Beispiel ist, wie in Fig. 5 gezeigt ist, wenn der Lauf 3 ist und der Pegel 1 ist, der entsprechende Code varia­ bler Länge "001110". Dies kann in der Form entsprechend der Erfindung ausgedrückt werden, in diesem Fall, wie in der Zeile des Laufes von 3 und des Pegels von 1 in Fig. 21 gezeigt ist, stellen die Datenbits vom dreizehnten bis zum zehnten Platz binär "0010" und damit in dezimal "2" dar, und die Bits vom neunten bis zum dritten Platz stellen den verbleibenden Code von "1110" dar. Die Codelänge des verbleibenden Codes ist 4 und kann binär, wie in Fig. 21 gezeigt ist, als "100" dargestellt werden. Kombinationen von anderen Läufen und Pegeln können in einer ähnlichen Art dargestellt werden.

Fig. 28 zeigt genau die Adressenumwandlungsschaltung 62 aus Fig. 20. Wie in Fig. 28 gezeigt ist, beinhaltet die Adressen­ umwandlungsschaltung 62 eine Inverterschaltung 72 zum Erstellen eines absoluten Werts des Pegelwertes, einen 1-Bit Addierer 74, einen Multiplexer 76, Vergleicher 78, 80 und 82 zum Vergleichen einer Größe des absoluten Wertes des von dem Multiplexer 76 angelegten Pegelwertes mit jeweils 2, 3 und 7, einer Logik­ schaltung 84, die ein Signal zum Bestimmen der Art der Kombina­ tion der Adressenerzeugung ausgibt, durch Durchführen einer logischen Operation der Komparatoren 78, 80 und 82, und einer Adressenerzeugungsschaltung 86, die eine Adresse basierend auf der Ausgabe der Logikschaltung 84 und des empfangenen Pegelwer­ tes und Laufwertes erzeugt. Wenn ein Pegelwert außerhalb der vorbestimmten Bereiche festgestellt wird, gibt die Logikschal­ tung 84 einen Fehler aus, der als ein Codeumwandlungssignal gesendet wird (siehe Fig. 20).

Die Inverterschaltung 72 und der 1-Bit Addierer 74 sind für den Fall vorgesehen, bei dem der empfangene Pegelwert eine negative Zahl ist, und arbeiten um eine Zahl durch Invertieren des Vor­ zeichens der negativen Zahl zu erzeugen. Der Multiplexer 76 gibt die Ausgabe des Addierers 74 aus, wenn das Vorzeichenbit des Pegelwertes 1 ist (negativ) und gibt den empfangenen Pegel­ wert aus, wenn es 0 (positiv) ist.

Fig. 29 zeigt den Betrieb der in Fig. 28 gezeigten Logikschal­ tung 84 in Form einer Tabelle, die die Ausgabe entsprechend der Kombination der Eingaben darstellt. In Fig. 29 stellen die Vor­ zeichenbits 1, 2 und 3 jeweils die Ausgaben der Komparatoren 78, 80 und 82 dar, und genauer, stellen die Vorzeichenbits ge­ bildet durch Subtrahieren von 2, 3 und 7 von dem Absolutwert des Pegelwertes dar.

Der Fall, bei dem alle Vorzeichenbits 1 bis 3 l sind, bedeutet, daß der absolute Wert des Pegelwertes kleiner als 2 ist. Dies entspricht dem Fall, bei dem der Pegelbereich, wie in Fig. 14 gezeigt, von -1 bis +1 ist. In diesem Fall wird der Steueraus­ gang auf 0 gesetzt. Der Fall, bei dem die Vorzeichenbits 1 bis 3 jeweils 0,1 und 1 sind, entspricht dem Fall, bei dem der Ab­ solutwert des Pegels 2 ist, und der Steuerausgang wird zu 1 gesetzt. Der Fall, bei dem die Vorzeichenbits 1 bis 3 jeweils 0,0 und 1 sind, entspricht dem Pegelbereich von -6 bis -3 und von +3 bis +6, in diesem Fall wird der Steuerausgang auf 2 ge­ setzt. Der Fall, bei dem alle Vorzeichenbits 0 sind, entspricht dem Fall, bei dem der Absolutwert des Pegels größer als 6 ist. In diesem Fall wird der Steuerausgang auf 3 gesetzt. Diese Steuerausgaben können binär als "00", "01", "10" und "11" dar­ gestellt werden. Dies entspricht den in Fig. 14 gezeigten Flags 50, so daß die Flags 50 so wie sie zum Erzeugen der Adressen sind, wie in Fig. 30 gezeigt ist, verwendet werden können. Die Logikschaltung 84 ist so aufgebaut, daß sie die Fehlerausgabe auf 0 setzt, wenn die Kombination der Vorzeichenbits in Fig. 29 zu irgendeinem der obigen Fälle gehört, und daß sie in dem an­ deren Fall als in den obigen die Fehlerausgabe auf 1 setzt.

Fig. 30 zeigt genau ein Verfahren zum Erzeugen einer Adresse durch die Adressenerzeugungsschaltung 86. Wie in Fig. 30 ge­ zeigt ist, wird jeder führende Bereich 90 von 3 Bits so verwen­ det, daß der Flagwert im Flagbereich 50 von den führenden zwei Bits so wie er ist gespeichert wird, und daß "0" im dritten Bit gespeichert wird, wenn der Flagwert zwischen 0 und 2 ist. Der Laufwert und der Pegelwert werden in den folgenden Bits ent­ sprechend den in Fig. 30 gezeigten Klassen zugeordnet. Damit können alle möglichen Kombinationen von (Lauf, Pegel) mit 11 Bits dargestellt werden. Der Adressenraum von 11 Bits ent­ spricht zweitausend Wörtern. Der Wert bei jeder Adresse hat eine Breite von 13 Bits. Daher benötigt der Speicher 64 nur zweitausend Wörter × 13 Bits. Im Stand der Technik wird ein Speicher von achtausend Wörtern × 22 Bits benötigt, so daß die Erfindung den benötigten Speicher auf einen Bruchteil kleiner als 1/6 reduzieren kann. Der Aufbau, der nur die in der japani­ schen Patentoffenlegungsschrift Nr. 4-14263 offenbarte Technik verwendet, benötigt 13 Bits für die Adresse, und benötigt den Speicherplatz von achttausend Wörtern. Sogar bei einem Ver­ gleich mit dieser kann die Codierung variabler Länge mit einem in 1/4 reduzierten Speicher durchgeführt werden.

Fig. 31 zeigt eine Code variable Länge Erzeugungsschaltung 66 zusammen mit einem Speicher für eine Tabelle von Code variabler Länge 64 und einer Steuerschaltung 68.

Wie in Fig. 31 gezeigt, beinhaltet die Code variable Länge Er­ zeugungsschaltung 66 Register 102, 106 und 108, einen Multiple­ xer 110, einen 5-Bit Addierer 112, ein Code variabler Länge Register 114, ein 40-Bit Barrel Shifter 104, ein Schieberegi­ ster 118, gebildet aus 8-Bit Registern 118a-118e, und eine Null-Erzeugungsschaltung 120. In Fig. 31 tragen die gleichen Teile und Bereiche, wie die in Fig. 11, die gleichen Bezugszei­ chen. Namen und Funktionen von denen, die die gleichen Bezugs­ zeichen tragen, sind dieselben.

Die in Fig. 31 gezeigte Erzeugungsschaltung Codes variabler Länge 66 unterscheidet sich von der der Anmelderin bekannten in Fig. 11 gezeigten Schaltung 252 in dem, daß sie zusätzlich ein Register 106 und einen Multiplexer 110 aufweist. Das Register 102 entspricht dem in Fig. 11 gezeigten Register 282, aber die darin benötigte Bitanzahl kann reduziert sein, da die Codelänge des von dem Speicher für eine Tabelle von Codes variabler Länge 64 gesendeten Codes kürzer ist als die im Stand der Technik.

Das Register 106 ist so verbunden, um den Wert zu empfangen, der die Anzahl der führenden und folgenden 0's in dem Code va­ riabler Länge von dem Speicher für eine Tabelle von Code varia­ bler Länge 64 anzeigt. Die Ausgänge der Register 108 und 106 sind mit zwei Eingängen des Multiplexers 110 verbunden. Der Ausgang des Multiplexers 110 ist mit einem der Eingänge des 5- Bit Addierers 112 verbunden. Der andere Eingang des 5-Bit Ad­ dierers 110 ist mit dem Ausgang des Registers variabler Länge 114 verbunden.

Die Steuerschaltung 68 sendet die Steuersignale a-g zum Betrei­ ben des Speichers für eine Tabelle von Codes variabler Länge 64 und der Erzeugungsschaltung Codes variabler Länge 66 wie folgt.

Wie in Fig. 32 gezeigt ist, wird ein Signal a in Schritt 130 angelegt. Damit werden die Anzahl der führenden und folgenden 0's gespeichert in der umgewandelten Adresse, der verbleibende Code und die Codelänge des verbleibenden Codes von dem Speicher der Tabelle von Code variabler Länge 64 ausgegeben.

Im Schritt 132 werden die Signale b, c und d angelegt und der verbleibende Code, die Codelänge des verbleibenden Codes und die Anzahl der führenden und folgenden 0's werden jeweils in den Registern 102, 106 und 108 gespeichert.

Im Schritt 134 werden die Signale e und f angelegt. In Reaktion auf das Anlegen des Signals e wählt der Multiplexer 110 und legt den Inhalt des Registers 106 an den 5-Bit Addierer 112 an. Daher addiert der 5-Bit Addierer 112 die Anzahl der führenden und folgenden 0's und den Inhalt des Codelängenregisters 114, und legt das Ergebnis an das Codelängenregister 114 an. In Re­ aktion auf das Anlegen des Signals f speichert das Codelängen­ register 114 die Ausgabe des 5-Bit Addierers 112.

Im Schritt 136 wird festgestellt, ob der Inhalt des Codelängen­ registers 114 kleiner als 8 ist oder nicht. Wenn er kleiner als 8 ist, führt die Steuerung zum Schritt 142. Wenn der Inhalt des Codelängenregisters 114 8 oder mehr ist, wird im Schritt 138 das Steuersignal h angelegt. Dieses Steuersignal h wird extern als Datenfreigabesignal zum externen Aufrufen Daten hereinzu­ nehmen ausgegeben. Das 8-Bit Register 118a als der führende Platz im Schieberegister 118 gibt den 8-Bit Wert als ein Code variabler Länge in Reaktion auf das Steuersignal h aus.

Wie in Fig. 33 gezeigt ist, werden die Inhalte der Register 118b-118e im Schritt 140 in die Register 118a-118d geschoben. Der Inhalt des Codelängenregisters 114 wird um 8 reduziert. Das Register 18e wird mit 0 aufgefüllt, die von der Null-Erzeu­ gungsschaltung 120 da hinein geschoben werden.

Im Schritt 142 wird das Steuersignal g angelegt. Das Schiebere­ gister 118 speichert den Code, der verbleibt, nachdem der 40- Bit Barrel Shifter 104 ihn um den Wert des Codelängenregisters 114 nach rechts schiebt. Es sollte bemerkt werden, daß zu die­ ser Zeit der Inhalt vom ersten Platz zum Platz des Wertes des Codelängenregisters gespeichert wird, und daß danach der ver­ bleibende Code addiert wird.

Im Schritt 144 wird das Steuersignal e nicht mehr angelegt, und das Steuersignal f wird angelegt. Damit legt der Multiplexer 110 die Codelänge des verbleibenden Codes, der im Register 108 gespeichert ist, an den 5-Bit Addierer 112 an. Der 5-Bit Addie­ rer 112 addiert den Wert des Codelängenregisters 114 und die Länge des verbleibenden Codes und legt das Ergebnis an das Co­ delängenregister 114 an. Das Codelängenregister 114 speichert die Ausgabe des 5-Bit Addierers 112 in Reaktion auf das Anlegen des Steuersignals f.

In Schritt 146 wird festgestellt, ob der Inhalt des Codelängen­ registers 114 kleiner als 8 ist oder nicht. Wenn er kleiner als 8 ist, ist die Codierungsverarbeitung variabler Länge eines Wertes beendet. Wenn er 8 oder mehr ist, führt die Steuerung zum Schritt 148 in Fig. 34. Im Schritt 148 wird das Steuersi­ gnal h angelegt, und das Hereinnehmen von einem codierten Wert wird extern angefordert. Das Schieberegister 118 gibt den Wert des führenden 8-Bit Registers 118a als codierten Wert in Reak­ tion auf das Anlegen des Steuersignals h aus.

Weiter werden in Schritt 150 die Inhalte der Register 118b-118e zu den Registern 118a-118d geschoben, und von der Null-Erzeu­ gungsschaltung 120 gesendete 0's werden in das Register 118e geschoben. Der Inhalt des Codelängenregisters 114 wird um 8 erniedrigt, und die Steuerung führt den Ablauf zum Schritt 146 in Fig. 33 zurück.

Die oben beschriebene Verarbeitung wird wiederholt an jeweili­ gen Werten durchgeführt, womit die Codierung variabler Länge durchgeführt wird.

Der Betrieb der in Fig. 31 gezeigten Schaltungen wird im fol­ genden genauer beschrieben werden. Alle Inhalte der Codeausga­ beregister 118 und des Codelängenregisters 114 sind im Anfangs­ zustand 0. Als erstes wird angenommen, daß der codierte Code variabler Länge "001010" ist. Die Anzahl der führenden und fol­ genden 0's ist "2", der verbleibende Code ist "1010" und die Codelänge des verbleibenden Codes ist "4".

Die Anzahl der führenden und folgenden 0's, d. h. "2" wird über das Register 106 und den Multiplexer 110 an den 5-Bit Addierer 112 angelegt. Der 5-Bit Addierer 112 addiert den Eingabewert "2" und den Inhalt "0" des Codelängenregisters 114. Das Ergeb­ nis, d. h. "2" wird im Codelängenregister 114 gespeichert.

Der verbleibende Code "1010" wird an den 40-Bit Barrel Shifter 104 angelegt. Da der Inhalt des Codelängenregisters 114 "2" ist, wird der Code variabler Länge um 2 Bits durch den 40-Bit Barrel Shifter 104 nach rechts geschoben, und wird an das Schieberegister 118, vorgesehen zum Ausgeben des Codes, ange­ legt. Damit wird "001010" im ersten bis zum sechsten Bit im Schieberegister 118, vorgesehen zum Ausgeben des Codes, gespei­ chert.

Die Länge "4" des verbleibenden Codes wird über das Register 108 und den Multiplexer 110 an den 5-Bit Addierer 112 angelegt. Der 5-Bit Addierer 112 addiert den Inhalt des Codelängenregi­ sters 114, d. h. "2" und die Ausgabe des Multiplexers 110, d. h. "4" und legt das Ergebnis an das Codelängenregister 114 an. Das Codelängenregister 114 speichert das angelegte Ergebnis "6".

Im folgenden wird nun der Betrieb der Schaltung 66 beschrieben, der durchgeführt wird, wenn der codierte Code variabler Länge von "00001000" angelegt wird. In diesem Fall ist die Anzahl der führenden 0's "4", ist der verbleibende Code "1000", und ist die Länge des verbleibenden Codes "4".

Die Anzahl der führenden und folgenden 0's, d. h. "4" wird über das Register 106 und die Multiplexer 110 an den 5-Bit Addierer 112 angelegt. Der 5-Bit Addierer 112 addiert den Eingangswert "4" und den Inhalt "6" des Codelängenregisters 114. Das Ergeb­ nis von "10" wird an das Codelängenregister 114 angelegt und wird darin gespeichert.

Der verbleibende Code "1000" wird über das Register 102 an den 40-Bit Barrel Shifter 104 angelegt. Der Inhalt des Codelängen­ registers 114 ist "10". Daher wird der verbleibende Code durch den 40-Bit Barrel Shifter 104 um 10 Bits nach rechts geschoben, und wird an das Schieberegister 118 zum Ausgeben des Codes an­ gelegt. Das Schieberegister 118 speichert die Ausgabe des 40- Bit Barrel Shifters 104 im elften und den folgenden Bits. In diesem Zustand hat das Schieberegister 116 im ersten bis sech­ sten Bit den anfänglich angelegten Code variabler Länge gespei­ chert. Der zweite Code variabler Länge "00001000" wird im sieb­ ten bis vierzehnten Bit gespeichert.

Die Länge "4" des verbleibenden Codes wird über das Register 108 und dem Multiplexer 110 an den 5-Bit Addierer 112 angelegt. Der 5-Bit Addierer 112 addiert den Eingangswert "4" und den Inhalt des Codelängenregisters 114, d. h. "10", und legt das Ergebnis von "14" an das Codelängenregister 114 zum Speichern desselben an. Daher wird das Steuersignal h angelegt und der Code variabler Länge wird ausgegeben.

Fig. 35 zeigt eine Serie von an die in Fig. 31 gezeigte Erzeu­ gungsschaltung Codes variabler Länge 66 angelegten Werte. Fig. 36 bis 38 zeigen die Änderung der Inhalte des Schieberegisters 118 in Fig. 31, bedingt durch diese Daten.

Wie in Fig. 35 gezeigt ist, wird angenommen, daß die Codes va­ riabler Länge "110", "01000", "001010", "00001100", 001001100", "001000010" und "00000010100" der Reihe nach angelegt werden. In diesen Codes variabler Länge sind die Anzahl der führenden und folgenden 0's 0, 1, 2, 4, 2, 2 und 6, und die verbleibenden Codes sind "110", "1000", "1010", "1100", "1001100", "1000010" und "10100". Die Längen der verbleibenden Codes sind 3, 4, 4, 4, 7, 7, und 5.

Fig. 36 zeigt bei (a) den Anfangszustand. Im Anfangszustand sind alle Inhalte der Register 118a-118e und des Registers Co­ des variabler Länge 114 0.

Bei (b) in Fig. 36 ist ein Zustand gezeigt, daß ein Wert 1 ein­ gegeben wird. "110" wird im ersten bis dritten Bit im Register 118a gespeichert, und 3 wird im Codelängenregister gespeichert.

Wie bei (c) in Fig. 36 gezeigt ist, wird, da die Anzahl der führenden (und folgenden) 0 im zweiten Wert 1 ist, die "0" im vierten Bit im Register 118a gültig als das führende Ende des nächsten Codes, und der Inhalt des Codelängenregisters wird 4. Danach wird, wie bei (d) in Fig. 36 gezeigt ist, der Wert 2 eingegeben, und der verbleibende Code "1000" des Wertes 2 wird in den vier Bits, beginnend von dem fünften Platz im Register 118a, gespeichert. Das Codelängenregister nimmt den Wert 8 an.

Danach werden die jeweiligen Werte, wie in Fig. 36 bis 38 ge­ zeigt ist, eingegeben, und Codes variabler Länge werden ausge­ geben, wie bei (e) in Fig. 36, (c) und (f) in Fig. 37 und (b), (e) und (f) in Fig. 38 gezeigt ist. Die Ausgabe des so gebilde­ ten Codes variabler Länge ist: "110010000010100000110000100110000100001000000010". Es kann verstanden werden, daß der Bitstrom von Codes variabler Länge, wie in Fig. 35 gezeigt ist, ausgegeben wird.

Entsprechend der Erfindung, wie oben beschrieben, kann die Ta­ belle des Codes variabler Länge mit einem Speicher mit einer kleineren Kapazität als der im Stand der Technik gebildet wer­ den, und die Erfindung kann nicht nur auf den Bildkompressions­ codierungsstandard MPEG1 aber auch auf H261 und JPEG angewendet werden. Da die gewünschten Codes variabler Länge durch einen einfachen Aufbau, gebildet aus dem Schieberegister, dem 5-Bit Addierer und den Registern gebildet werden können, können Codes variabler Länge schnell durch einen einfachen Schaltungsaufbau erzeugt werden. Obwohl die Ausführungsformen in Verbindung mit dem Fall beschrieben worden sind, bei dem die Anzahl der füh­ renden und folgenden 0's (oder 0) verwendet wird, ist die Er­ findung darauf nicht beschränkt, sondern kann in ähnlicher Wei­ se auf den Fall angewendet werden, bei dem die Anzahl der füh­ renden und folgenden 1's verwendet wird.

Claims (8)

1. Verfahren zum Komprimieren von Daten unter Verwendung von Codes variabler Länge und von Codelängen des Codes variabler Länge,
wobei die Codes variabler Länge, die jeweils durch eine Kombina­ tion eines Wertes einer ersten Bestimmungskomponente (Lauf) mit einem Wert einer zweiten Bestimmungskomponente (Pegel) darge­ stellt sind, und die Codelängen an einer Adresse (Fig. 14, 19, 30) in einem Speicher (64) gespeichert sind und wobei
die Adressen (Fig. 14, 19, 30), die jeweils einen ersten Bereich (50, 52, 90) zum Bestimmen einer Klasse, einen zweiten Bereich für den Wert der ersten Bestimmungskomponente (Lauf) und einen dritten Bereich für den Wert der zweiten Bestimmungskomponente (Pegel) aufweisen,
durch folgende Schritte bestimmt werden:
Einteilen der Kombinationen der Werte der ersten und zweiten Be­ stimmungskomponenten (Lauf, Pegel) in Abhängigkeit des Absolut­ wertes der zweiten Bestimmungskomponente (Pegel) in die Klassen (Fig. 13, 18)
und Festlegen der Länge des zweiten Bereiches und der Länge des dritten Bereiches für jede Klasse derart, daß die Länge des zweiten Bereiches und die Länge des dritten Bereiches für die maximalen Absolutwerte der ersten und zweiten Bestimmungskompo­ nenten (Lauf, Pegel) minimal werden.

2. Verfahren nach Anspruch 1, bei dem der Code variabler Länge aus der Anzahl der gegebenen ersten Zeichen, die sich von dem führenden Ende fortsetzen, und einem verbleibenden Ende (Fig. 21-27) gebildet ist und bei dem die Codelänge die Codelänge des verbleibenden Codes ist.

3. Verfahren nach Anspruch 1 oder 2, bei dem das erste Zeichen 0 oder 1 ist.

4. Verfahren nach einem der Ansprüche 1 bis 3, bei dem die Codes variabler Länge im Bildkompressionscodierungsstandard MPEG ver­ wendet werden, die erste gleichlange Bestimmungskomponente ein Laufwert ist und die zweite gleichlange Bestimmungskomponente ein Pegelwert ist.

5. Verfahren nach einem der Ansprüche 1 bis 3, bei dem die Codes variabler Länge in einem Bildkompressionscodierungsstandard H261 verwendet werden, die erste gleichlange Bestimmungskomponente ein Laufwert ist und die zweite gleichlange Bestimmungskomponente ein Pegelwert ist.

6. Codierungsvorrichtung (60) zum Erzeugen eines zweiten Codes variabler Länge unter Verwendung von durch eines der Verfahren der Ansprüche 1 bis 5 gespeicherten ersten Codes variabler Länge mit:
einem Adressenerzeugungsmittel (62) zum Empfangen der ersten und der zweiten Bestimmungskomponente (Lauf, Pegel) zum Erzeugen der Adresse basierend auf der empfangenen ersten und zweiten Bestimmungskomponente (Lauf, Pegel) und auf der Klasse, in der die zweite Bestimmungskomponente (Pegel) enthalten ist, und zum Anlegen der erzeugten Adresse an den Speicher (64), und
einer Steuerschaltung (66, 68) zum Auslesen der ersten Codes variabler Länge und zum Erzeugen der zweiten Codes variabler Länge daraus.

7. Codierungsvorrichtung (60) nach Anspruch 6, bei der die Steuerschaltung (66, 68) ein Zeichenadditionsmittel (66) aufweist, das basierend auf der Anzahl von führenden und folgenden ersten Zeichen des ersten Codes variabler Länge, auf dem verbleibenden Code desselben und auf der Codelänge des verbleibenden Codes derart betreibbar ist, daß der zweite Code variabler Länge, der die ersten Zeichen in gleicher Anzahl zu der Anzahl an dem führenden Ende des verbleibenden Codes auf­ weist, ausgegeben wird.

8. Codierungsvorrichtung nach Anspruch 7, bei dem das Zeichen­ additionsmittel (66) ein Schieberegister (118), das auf ein vorbestimmtes Schiebesignal derart reagiert, daß ein Schieben von Daten um eine vorbestimmte Länge in einer vorbestimmten Richtung, daß ein nacheinander Herausschieben der Daten von einem vorderen Ende entsprechend der vorbestimmten Richtung zum Ausgeben des zweiten Codes variabler Länge und daß ein nacheinander Hineinschieben der ersten Zeichen in ein Ende, das gegenüber dem vorderen Ende relativ zu der vorbestimmten Richtung liegt, durchgeführt wird;
ein Datenlängenspeichermittel (114) zum Speichern einer in dem Schieberegistermittel (118) gespeicherten effektiven Datenlänge, das auf die Tatsache, daß die gespeicherte effektive Datenlänge eine vorbestimmte Länge überschreitet, derart reagiert, daß das Schiebesignal an das Schieberegistermittel (118) angelegt wird und daß die gespeicherte effektive Datenlänge um die vorbestimmte Länge erniedrigt wird; und
ein Schiebeübertragungsmittel (104) zum Schieben des verbleibenden Codes um die Anzahl der ersten Zeichen von einer Position, die durch das Datenlängenspeichermittel (114) festgelegt ist, und zum Speichern desselben in dem Schieberegistermittel (118) enthält,
wobei das Datenlängenspeichermittel (1 14) die gespeicherte effektive Datenlänge um eine Summe der Anzahl der ersten Zeichen und der Codelänge des verbleibenden Codes als Reaktion auf die Tatsache, daß der verbleibende Code durch das Schiebeübertragungsmittel (104) in dem Schieberegistermittel (118) gespeichert wird, erhöht.