DE4314741C2 - Dekodierer für Einheiten von Huffman-kodierten Daten - Google Patents

Description

Die Erfindung betrifft einen Dekodierer für Einheiten von Huffman-kodierten Daten nach dem Anspruch 1.

Aus der US-PS 4,899,149 ist bereits ein Decodierer für Huffman-kodierte Daten bekannt, der eine Bit-Schiebeeinheit zur Aufnahme der kodierten Daten und eine Speichereinheit aufweist, die mit der Schiebeeinheit verbunden ist, wobei die Speichereinheit zur Dekodierung der Huffman-kodierten Daten dient. Ein gleich­ zeitiges Dekodieren mehrerer Codewörter ist jedoch mit Hilfe dieses bekannten Dekodierers nicht möglich.

Die Anwendung der Kodierung nach Huffman wird typischerweise verwendet, wenn eine große Anzahl von Daten vorhanden ist, welche verarbeitet oder über­ tragen werden müssen, wie etwa bei der digitalen Bildverarbeitung. Zum Beispiel Farb­ bilder, verarbeitet nach dem JPEG-Standard (Joint Photographic Experts and Group), und die Standard-Kodierung nach Huffmann handhaben typischerweise eine große Anzahl von Dateneinheiten. Die Kodierung nach Huffman wird in gegenwartigen und zukünftigen digitalen Videoverarbeitungsstandards zu finden sein.

Von diesen Standards wird der zuvor aufgezeigte JPEG-Standard umfaßt, welcher ein Standard auch für Bilder ist. Existierende und zukünftige Standards für Bewegungs-Videosysteme, wie etwa H.261, einem CCITT-Video-Telekonfe­ renz-Standard, und dem Motion Picture Experts Group (MPEG) I, weisen Kodie­ rungssysteme auf, welche dem JPEG-Standard sehr ähnlich sind. Folglich sind die MPEG-Standards auf die aufkommenden hochgenauen Televisionstechnologien (HDTV) bezogen. Die Gemeinsamkeit zwischen HDTV, MPEG, H.261 und JPEG ist darin zu sehen, daß sie eine Kodierung nach Huffman enthalten.

Wo die Kodierung nach Huffman verwendet wird, muß die Dekodierung der Huffman-kodierten Einheiten natürlich durchgeführt werden. Bei der Kodierung von jeder kodierten Einheit wird ein Belegungsbit (im Datennetz) bzw. ein Token von jedem Kodewort erzeugt. Jedes Token bzw. Belegungsbit enthält, weil es einheitlich ist, genug Informationen über die kodierte Einheit (und die Original­ dateneinheit), um als Steuerinformation verwendet zu werden, um die kodierte Einheit in die Originaldateneinheit umzustellen oder zu dekomprimieren.

Ein herausragendes und grundsätzliches Problem ist bei der Dekodierungstätigkeit bzw. -operation entdeckt worden, welche jedes Belegungsbit bzw. Token aus einem Kodewort erzeugt. Das Problem erscheint, wenn die Hochgeschwindig­ keitsdekodierung der kodierten Einheiten gefordert wird. Beim Dekodieren eines Stromes von Huffman-kodierten Einheiten in einem üblichen Huffman-Dekodierer enthält jede Einheit ein Kodewort und optionelle Nicht-Kodeworte mit variie­ render Länge, welche bei der Hochgeschwindigkeitsdekodierung Schwierigkeiten bereiten.

Diese Schwierigkeit beim Dekodieren Huffman-kodierter Daten bei hoher Ge­ schwindigkeit bringt eine ernsthafte Behinderung für die zukünftigen Technologien mit sich. Wie oben erläutert, ist es sehr wahrscheinlich, daß die zukünftigen digitalen HDTV-Standards die Kodierung nach Huffman enthalten werden. Eine Abschätzung der HDTV-Erfordernisse führt zu der Verarbeitung von Bildele­ ment-Komponenten bei 100 Millionen Dateneinheiten pro Sekunde.

Die der Erfindung zugrundeliegende Aufgabe besteht darin, einen Dekodierer für Einheiten von Huffman-kodierten Daten zu schaffen, der eine hohe Dekodierungs­ geschwindigkeit von Codes variabler Länge, speziell von Huffman-Codes, er­ möglicht und eine Reduzierung des erforderlichen redundanten Speicherraumes erlaubt.

Diese Aufgabe wird erfindungsgemäß durch die im Anspruch 1 aufgeführten Merkmale gelöst.

Besonders vorteilhafte Ausgestaltungen und Weiterbildungen der Erfindung ergeben sich aus den Unteransprüchen 2 bis 38.

Die Erfindung betrifft ferner auch ein Verfahren zum Dekodieren von Huffman­ kodierten Dateneinheiten in einem Bitstrom nach dem Oberbegriff des Anspruches 39.

Die erfindungsgemäßen Verfahrensschritte zur Lösung der genannten Aufgabe ergeben sich aus dem Kennzeichnungsteil des Anspruches 39.

Besonders vorteilhafte Ausgestaltungen des erfindungsgemäßen Verfahrens erge­ ben sich aus den Unteransprüchen 40 bis 47.

Im folgenden wird die Erfindung anhand von bevorzugten Ausführungsbeispielen unter Hinweis auf die Zeichnungen näher erläutert.

Fig. 1 stellt einen repräsentativen Strom von Huffman­ kodierten Dateneinheiten dar;

Fig. 2A ist eine Darstellung von JPEG-Koeffizientendaten, die zu Null-Lauflängen und Koeffizienten-Größen­ felder separiert sind;

Fig. 2B zeigt die Koeffizienten-Größendaten, die in ein Exponentenfeld und ein Mantissenfeld separiert sind; und

Fig. 2C zeigt die kodierten Daten, die durch ein Huffman- Kodewort mit variabler Länge und die Mantissen­ bits gebildet sind;

Fig. 3 stellt eine allgemeine Organisation bzw. Anord­ nung eines Dekodierers nach Huffman dar;

Fig. 4 ist ein Blockdiagramm einer Schaltung, die ver­ wendet wird, um verschiedene dekodierte Bele­ gungsbits in einen einzigen Strom zu multiplexen bzw. zu vereinigen;

Fig. 5 zeigt eine Ausführungsform gemäß der vorliegenden Erfindung, einen Dekodierer, der einen breiten Suchtabellenspeicher aufweist;

Fig. 6 ist ein Flußdiagramm aus Schritten, die den Block der Steuerlogik der in Fig. 4 gezeigten Schaltung darstellt;

Fig. 7 ist ein Flußdiagramm aus Schritten, das den Steuerlogikblock der in Fig. 4 gezeigten Schal­ tung darstellt;

Fig. 8A zeigt eine andere Ausführungsform gemäß der vor­ liegenden Erfindung, einen Dekodierer, der ver­ setzt Suchtabelleneinheiten aufweist;

Fig. 8B ist eine allgemeine Anordnung eines logischen Blocks, welcher die Länge von kodierten Datenein­ heiten von den Ausgängen von den LUT-Einheiten erzeugt;

Fig. 9A ist in Flußdiagramm aus Schritten der Operation eines versetzten bzw. gestaffelten Tabellendeko­ dierers nach Fig. 8A;

Fig. 9B ist ein Flußdiagramm von Schritten der Operation einer Abwandlung des versetzten bzw. gestaffelten Tabellendekodierers nach Fig. 8A; und

Fig. 9C ist ein Flußdiagramm aus Schritten der Operation einer zweiten Abwandlung des versetzten bzw. ge­ staffelten Tabellendekodierers nach Fig. 8A;

Fig. 10A stellt eine andere Ausführungsform gemäß der vor­ liegenden Erfindung dar, einen Steuerspeicherde­ kodierer mit mehreren Suchtabellen für eine Hauptstromdekodierung (pipelined decoding) bzw. eine Dekodierung im Hauptstrom;

Fig. 10B ist eine Konfiguration einer Speichereinheit für eine zweistufige Suchtabelle für die Hauptstrom- bzw. Hauptleitungsdekodierung in Fig. 10A;

Fig. 11 ist ein Flußdiagramm aus Schritten, die Opera­ tionen von verschiedenen Stufen des Steuerspei­ cherdekoders nach Fig. 10A darstellt;

Fig. 12A stellt eine Speicherorganisation bzw. -Anordnung dar, durch welche die Gesamtgröße des als Suchta­ belle verwendeten Speichers verringert werden kann;

Fig. 12B zeigt die Steuerlogik zum Betreiben der Speicher­ organisation nach Fig. 12A;

Fig. 13 ist ein Flußdiagramm aus Schritten, die die Ope­ ration der Speicherorganisation nach Fig. 12A darstellt.

Die vorliegende Erfindung ist auf das allgemeine Problem der Hochgeschwindigkeitsdekodierung von Huffman-Kodeworten in einem Strom von kodierten Einheiten gerichtet. Folglich, während die Beschreibung der vorliegenden Erfindung häufig im Kontext mit bestimmten Anwendungen der Kodierung nach Huffman, einem JPEG-Beispiel, gemacht wird, weist die vor­ liegende Erfindung wesentlich weitergehende Anwendungsmög­ lichkeiten auf als die für einen JPEG-Huffman-Dekodierer.

Fig. 1 ist eine beispielhafte Darstellung eines Stroms von kodierten Einheiten unter einem JPEG-Standard. Jede fortge­ setzte Einheit stellt eine kodierte Dateneinheit dar, die ein Huffman-Kodewort und manchmal nicht kodierte Worte ent­ hält. In diesem Beispiel sind die nichtkodierten Worte die Mantissenbits der DC- und AC-Koeffizienten für die Bild­ leuchtdichte bzw. Luminanz und die Farbtondichte bzw. Chro­ minanz, die gemäß JPEG definiert wird. Andere kodierte Ein­ heiten enthalten nur Kodeworte, die jene für die JPEG- Blockende- und Escape-Steuerung enthalten. Es sollte be­ merkt werden, daß die meisten der kodierten Dateneinheiten kurz sind, weniger als ein Byte lang, gelegentlichen mit einer langen Einheit. Das digitale Bild ist gemäß dem JPEG- Standard komprimiert worden.

Die Fig. 2A bis 2C stellen Kodieren nach Huffman in dem JPEG-Kontext dar. Unter JPEG sind die Komponenten von Bild­ elementen von einem digitalen Bild in die Koeffizienten ei­ ner diskreten Kosinustransformation eines 8×8-Bildelement- Blocks reduziert. Wie in Fig. 2A gezeigt, wird ein Lauflängenbitfeld an jeden Koeffizienten angefügt, der nicht Null ist, wobei die Anzahl der als Null bewerteten Koeffizienten in einem Lauf (in einer Zick-Zack-Ordnung) aufgezeichnet wird. Das Koeffizientenfeld stellt die Größe der Koeffizienten dar. Jeder in Fig. 2B gezeigte Koeffi­ zient wird dann in ein Mantissenfeld und ein Exponentenfeld separiert. Das Kodieren der Originaldateneinheiten wird durch die Substitution eines vorbestimmten Huffman-Kode­ worts für die Lauflänge, und in diesem Fall Exponentenfel­ der durch das Belegungsbit, wie in Fig. 2C dargestellt, durchgeführt. Das Huffman-Kodewort und das Mantissenbitfeld ist die kodierte Einheit. Für Koeffizienten, welche keine Mantisse aufweisen, ist das Kodewort alleine die kodierte Einheit.

Viele der Einzelheiten des JPEG-Kodierungsverfahrens sind hier weggelassen. Es ist für die Zwecke der vorliegenden Erfindung ausreichend zu bemerken, daß die kodierten Ein­ heiten von variierender Länge sind. Wie oben erläutert, führt dieses beim Dekodieren der kodierten Einheiten zu der Schwierigkeit, ein Belegungsbit bzw. Token zu erzeugen, das zum Dekomprimieren der kodierten Einheiten in die Ori­ ginaldateneinheiten verwendet wird.

Dieses allgemeine Problem mit Huffman-Dekodierern wird durch eine allgemeine Organisation bzw. Anordnung eines in Fig. 3 gezeigten Huffman-Dekodierers demonstriert. Der De­ kodierer weist eine Bit-Verschiebereinheit 10 auf, grund­ sätzlich vorzugsweise einen Trommelschieber (barrel shifter), welcher einen parallelen Strom von kodierten Ein­ heiten akzeptiert. Die Einheit 10 wird mit einer Tabelle 11 zum Erzeugen der Belegungsbits aus den Kodeworten in dem Strom der kodierten Einheiten verbunden. Parallel adressie­ ren die Bits Bereiche in der Tabelle 11, wenn die Tabelle 11 eine Speichereinheit ist, oder bilden die Eingabesignale für die logische Kombination, wenn die Tabelle 11 ein kom­ binatorischer logischer Block ist. In jedem Falle wird ein Belegungsbit am Ausgang der Tabelle 11 erzeugt. Von dieser Nachprüfungs- bzw. Suchoperation für ein Kodewort wird die Länge der Daten-Einheit, zu welcher das Kodewort gelangt, bestimmt. Diese Längeninformation wird als Steuersignal zu der Bit-Verschiebereinheit 10 zurückgespeist, so daß das Kodewort der nächsten Dateneinheit in die Position für eine Nachprüfung bzw. ein Suchen gerückt bzw. verschoben wird. Folglich wird die Prüfung oder Dekodierung von jedem Kode­ wort sequentiell vorgenommen, veranlaßt durch die Unter­ schiedlichkeit in der Länge der Huffman-Kodeworte und der kodierten Dateneinheiten.

Die vorliegende Erfindung vermeidet dieses sequentielle De­ kodieren. In jeder der Dekodierer-Architekturen gemäß der vorliegenden Erfindung gibt es eine Bit-Verschiebungsein­ heit 24, wie sie in den Fig. 5, 8 und 10A gezeigt ist.

Jede der Zellen des Bit-Verschiebers 24 ist an die Adres­ sen-Anschlüsse von einer oder mehreren Speichereinheiten in verschiedenen Anordnungen angeschlossen, wie sie unten er­ klärt werden. Die Speichereinheiten arbeiten als Suchta­ bellen für Kodeworte, welche in die Zellen des Registers 24 verschoben bzw. gerückt worden sind. Die Suchtabellen er­ zeugen für jedes Kodewort ein Belegungsbit. In dem JPEG- Beispiel werden als Ausgangssignale von den Speichereinhei­ ten insgesamt 13 Bits erzeugt; vier Bits für die Lauflänge, vier Bits für den Exponenten und fünf Bits für das Steuer­ wort, das als Länge für die Verschiebung des Bitstromes be­ zeichnet wird. Fünf Steuerbits werden benötigt, weil die maximale Länge einer kodierten JPEG-Einheit 27 Bits be­ trägt. Um ein ungültiges Belegungsbit darzustellen, kann z. B. ein Steuerwort Null verwendet werden. Es können andere Mittel verwendet werden, um ein ungültiges Belegungsbit darzustellen.

Die Speichereinheiten sind in der Form von Zufallszugriffs- Speichern (RAM-Speicher), welche flexibel mit den Bele­ gungsbits von bestimmten Huffman-Kodes geladen werden kön­ nen, sobald der Huffman-Kode definiert worden ist oder aus Lesespeichern (ROM-Speicher), wenn der Huffman-Kode zuvor bekannt ist. Natürlich können auch Einheiten aus kombinato­ rischer Logik als eine Alternative zu den ROM-Einheiten verwendet werden.

Sämtliche der verschiedenen Ausführungsformen nach der vor­ liegenden Erfindung erzeugen gleichzeitig Vielfach- bzw. parallele Belegungsbits. Diese Belegungsbits müssen in ei­ nem geordneten Datenstrom angeordnet werden. Fig. 4 zeigt eine Schaltung zum Handhaben multiplexer Operationen bzw. Vielfachoperationen für diese Funktion. Die Register 21 werden jedesmal geladen, wenn der Huffman-Dekodierer einen Zyklus vollendet. Jedes der Register 21 wird mit einem de­ kodierten Belegungsbit, einem optionell nicht-kodierten Wort (den Mantissenbits in dem JPEG-Beispiel), falls eines vorhanden ist, und den Bits, die die gesamte Länge der de­ kodierten Dateneinheit anzeigen, geladen. Die Belegungsbits und Bits, die die Länge anzeigen, werden von jedem der ver­ schiedenen Huffman-Dekodierer erzeugt, die unten beschrie­ ben sind, und die optionellen nicht-kodierten Worte werden aus den kodierten Daten erzeugt.

Ein Startsignal aus der Systemsteuerlogik (nicht gezeigt), deutet an, daß Multiplexen durchgeführt worden ist. Ein Steuerlogikblock 23 nimmt das Startsignal und Signale von den Registern 21 entgegen, die die Länge der Dateneinheiten anzeigen. Der Block 23 wählt sequentiell (über einen Dekodierer 22) die bestimmten Register 21 aus, welche gül­ tige Belegungsbits enthalten. Der Block 23 stellt auch ein Signal für ein FIFO (First-In-First-Out)-Register zur Ver­ fügung, welches nicht gezeigt wird, um anzuzeigen, daß eine gültige Eingabe in das FIFO verfügbar ist. Die Belegungs- und Mantissenbits von jedem ausgewählten Register 21 werden in die FIFO geladen und die Originaldaten sind nach dem Austreten aus dem FIFO umgeformt. Das Umformen der Daten ist eine wohlbekannte Operation. Die bestimmte Konfigura­ tion des Logikblocks 23 hängt von der bestimmten Architek­ tur des Dekodierers ab und wird unten erörtert.

Die Zeit, die zum Multiplexen eines Belegungsbits in dem FIFO erforderlich ist, ist wesentlich geringer als die, die zum Durchführen eines Dekodierungszyklus erforderlich ist. Die Gesamtsteuerlogik verwendet einen Taktgeber, welcher m­ mal schneller ist als der Taktgeber, der für den Dekodierer verwendet wird, wobei m die maximale Anzahl von Dekodierun­ gen pro Zyklus ist.

Breite Tabellenarchitektur

Eine Ausführungsform eines Hochgeschwindigkeitsdekodierers gemäß der vorliegenden Erfindung ist eine in Fig. 5 darge­ stellte breite Tabellenarchitektur bzw. Architektur mit breiter Tabelle. Die Eingabeanschlüsse einer Einzelspei­ chereinheit 30, einer Suchtabelle für die Kodeworte sind an die individuellen Zeilen der Bit-Verschiebereinheit 24 an­ geschlossen, so daß der Inhalt der Verschieber 24 Bereiche in der Speichereinheit 30 adressiert, wie oben beschrieben. Jedoch ist die Speichereinheit 30 bereit, um verschiedene mögliche Belegungsbits sofort zu erzeugen. In jedem JPEG- Beispiel nach den Fig. 1 und 2A bis 2C beträgt die maximale Länge eines Kodeworts 16 Bits und die typische Größe jeder kodierten Einheit ist geringer als ein Byte, 8 Bits. Folg­ lich sollte die Speichereinheit 30 für JPEG zumindest 16 Eingabeanschlüsse aufweisen. Für andere Anwendungen ist die typische Anzahl von Eingangsanschlüssen zu einem Speicher z. B. 12 bis 20. Mit anderen Worten erzeugt die Speicherein­ heit 30 die korrekten Belegungsbits parallel in einer Deko­ dierungsoperation. Für jedes Kodewort in dem Schieber 24 an den Adressenanschlüssen der Speichereinheit 30 wird ein Be­ legungsbit erzeugt.

Die Speichereinheit 30 speichert auch die Steuerinformatio­ nen für den Bitschieber 24, um die gesamte Anzahl Bits in die nächste Dekodieroperation zu schieben. Wenn z. B. Belegungsbits für zwei Kodeworte, die zu Dateneinheiten mit Längen von 4 bzw. 5 Bits korrespondieren, dekodiert werden, dann wird die Steuerinformation für eine Verschiebung über 9 Bits über die Steuerleitungen 15 zurück zu dem Schieber 24 gesendet. Wenn die Gesamtlänge von dekodierten Datenein­ heiten 27 Bits beträgt, dann wird ein 27-Bit-Verschiebungs­ signal zu der Bit-Schiebereinheit 24 gesendet.

Die Sequenz aus Operationsschritten für die Dekodiererar­ chitektur mit breiter Tabelle ist in Fig. 6 gezeigt. Dort gibt es zwei grundlegende Schritte. Der erste ist, daß eine Nachprüf- bzw. Suchoperation an den Eingangsanschlüssen der Speichereinheit 30 durchgeführt wird, um zu bestimmen, ob ein oder mehrere Belegungsbits adressiert werden und an den Ausgangsanschlüssen des Speichers 30 erzeugt werden. Der Ausgang von der Speichereinheit 30 enthält auch die gesamte Länge sämtlicher in dem Bit-Schieber 24 dekodierter Daten­ einheiten. Diese Information wird in den Schieber 24 zu­ rückgespeist, um durch diese die Anzahl von Bits zu ver­ schieben und die Dekodierungsoperation wird wiederholt.

Für die breite Nachprüf- bzw. Suchtabellen-Architektur weist der Multiplexer-Steuerlogikblock 23 in Fig. 4 einen Zähler und eine kleine Menge kombinatorischer Logik auf. Die Operation mit dem Block 23 folgt dem Flußdiagramm nach Fig. 7. Der Zähler, welcher die Position eines Kodeworts an den Eingangsanschlüssen bzw. -terminals der Speichereinheit 30 anzeigt, ist anfangs Null. Wenn ein Startsignal auf­ tritt, ermächtigt bzw. gibt der Zähler, der den Wert Null aufweist, den Ausgang des Registers 21 an der Position Null frei. Die Gültigkeit des Belegungsbits in diesem Register wird geprüft, indem bestimmt wird, ob die Länge der unko­ dierten Dateneinheit, die zu dem Belegungsbit in dem Regi­ ster 21 korrespondiert, Null ist oder nicht. Wenn das Bele­ gungsbit gültig ist (die Länge ist nicht Null), macht der Block 23 das FIFO-Eingangsermächtigungssignal geltend, so daß die Inhalte des Registers 21 in das FIFO geladen wer­ den. Wenn das Belegungsbit ungültig ist (die Länge ist Null), kehrt der Block 23 in den Zustand zurück, in dem der nächste Dekodierungszyklus und ein Startsignal, nachdem der Zähler gelöscht ist, erwartet werden. Angenommen, das Bele­ gungsbit ist gültig, so wird der Zähler inkrementiert, so daß er nun die Position des nächsten Registers aufweist. Eine Überprüfung wird durchgeführt, ob die Position gültig ist, indem überprüft wird, ob eine maximale Zahl erreicht worden ist. Wenn nicht, ermächtigt bzw. gibt der logische Block 23 das nächste Register 21 an der durch den Zähler angezeigten Position frei. Eine Gültigkeitsüberprüfung des Belegungsbits in dem nächsten Register wird durchgeführt und die Schritte werden wiederholt, bis die maximale Zahl erreicht worden ist oder ein ungültiges Belegungsbit gefun­ den worden ist. Der Zähler wird dann für den nächsten Deko­ dierungszyklus und ein Startsignal gelöscht.

Es ist ersichtlich, daß die Speichereinheit 30 mit vielen Eingabe- und Ausgabeanschlüssen sehr groß werden kann. Der Nachteil dieser Architektur mit breitem Speicher ist, daß für eine anwachsende Zahl von n Eingangsanschlüssen die Speichergröße mit 2ⁿ anwächst. Unter bestimmten Umständen kann die Größe der Speichereinheit 30 reduziert werden und dennoch eine effektive parallele Dekodierungsoperation er­ zielen. In diesem Fall ist der erste Belegungsbit-Ausgang oder der Ausgang für das zuerst positionierte Kodewort in dem Bit-Schieber 24 wie oben beschrieben. Der Ausgang für dieses Kodewort muß ausreichend Bits zum Beschreiben sämt­ licher möglicher Belegungsbits (13 Bits für das JPEG-Bei­ spiel) aufweisen. Jedoch können die anderen parallelen Aus­ gänge für die folgenden Belegungsbits weniger Bits verwen­ den. Die stochastischen Eigenschaften der kodierten Daten bestimmen die Untermenge der Belegungsbits, welche in den nachfolgenden Kodewortpositionen dekodiert werden können. Diese Belegungsbit-Ausgänge werden als die am häufigsten auftretenden Belegungsbits ausgelegt. In dem JPEG-Beispiel kann z. B. ein zusätzliches Ausgangsbit von dem Ausgang der Speichereinheit 30 verwendet werden, um anzuzeigen, daß eines der nachfolgenden Kodeworte ein Blockende-Kodewort ist. Ein anderes Beispiel ist, daß 9 Ausgangsbits für Bele­ gungsbits für die JPEG-AC-Koeffizienten ohne Null-Lauflänge verwendet werden können.

Der beschriebene Speicher kann in verschiedenen Organisa­ tionen angeordnet werden, um die vier Kodes nach Huffman für JPEG zu handhaben. Vier getrennte und parallele Spei­ chereinheiten 30 können verwendet werden, um die AC- und DC-, die Bildleuchtdichte- und die Bildfarbton-Huffman-Ko­ des zu handhaben. Die Steuerlogik, die auf das Blockende und die Anzahl der dekodierten Koeffizienten anspricht, hält die Spur und gibt die zutreffenden Speichereinheiten mit Steuersignalen frei. Eine andere Anordnung erhöht den Platz der einzelnen Speichereinheit 30, um den Prüf- bzw. Suchtabelleninhalt für alle vier Kodes beizubehalten. Die Steuerlogik bestimmt ähnlich, welcher Kode mit zwei zusätz­ lichen Adressenleitungen zu dem Speicher dekodiert werden soll.

Diese zwei Speicherorganisationen sind ebenfalls für die Speichereinheiten, die als Prüf- bzw. Nachschautabellen in den anderen unten beschriebenen Dekodierer-Architekturen verwendet werden, anwendbar.

Versetzte bzw. gestaffelte Tabellenarchitektur

Eine andere Architektur für einen Dekodierer gemäß der vor­ liegenden Erfindung hat mehrere bzw. verschiedene LUT (Look Up Table: Prüf- bzw. Suchtabelle)-Einheiten 40, die mit den Zellen des Bit-Schiebers 24 in einer versetzten bzw. ge­ staffelten Weise verbunden sind, wie in Fig. 8A gezeigt. Jede der LUT-Einheiten 40 ist eine Prüf- bzw. Suchtabelle für Kodeworte des kodierten Daten-Bitstrom in dem Schieber 24 und für die Längen der Kodeworte und für irgendwelche optionell nicht kodierten Worte (für das JPEG-Beispiel Mantissenbits). Die erste LUT-Einheit 40-0 ist an die Zel­ len in der anfänglichen Position des Schieberegisters 24 angeschlossen. Mit anderen Worten ist die erste LUT-Einheit 40-0 an die von einer anfänglichen Zelle 0 beginnende Bit- Schieberzelle angeschlossen. Wie in Fig. 8A gezeigt, ist die LUT-Einheit 40-0 16 Bits breit (wie auch die anderen LUT-Einheiten 40), um das unter dem JPEG-Standard größtmög­ liche Kodewort unterzubringen (es ist zu bemerken, daß die LUT-Einheiten in ihrem Speicher reduziert werden können, wie im Hinblick auf die Fig. 12A und 12B erläutert). Folg­ lich wird die erste LUT-Einheit 40-0 an Zellen 0-15 (0 bis 15) des Bit-Schiebers 24 angeschlossen. Der Anschluß der nächsten LUT-Einheit 40-1 wird um eine Zelle gestaffelt bzw. versetzt, so daß sie durch Zellen 1-16 (1 bis 16) des Bit-Schiebers 24 adressiert wird. Die folgende LUT-Einheit 40-2 wird an Zellen 2-17 (2 bis 17) angeschlossen, usw.

Der Betrag des Versatzes an dem Ort jeder LUT-Einheit 40 wird durch die bestimmte Anwendung und den verwendeten Huffman-Kode bestimmt. Der Betrag der Versetzung für die versetzten bzw. gestaffelten LUT-Einheiten 40 kann in einer wahrscheinlichsten Weise für die beste Nutzung des Spei­ cherplatzes ausgeführt werden. Wenn z. B. die wahrschein­ lichste Länge einer unkodierten Dateneinheit 4 Bits be­ trägt, wird die zweite LUT-Einheit 40-1 an den Bit-Schieber 24 angeschlossen, der bei Bit 4 anfängt, der wahrschein­ lichsten Position der nächsten unkodierten Dateneinheit. Typischerweise wird der Betrag des Versatz es für den ersten Versatz auf die kürzestmögliche kodierte Einheit begründet. In dem in Fig. 8A gezeigten Beispiel ist die nächste LUT- Einheit 40-1 mit einem 1-Bit-Versatz von der anfänglichen Position angeordnet, wenn z. B. die kürzest mögliche kodier­ te Einheit 1 Bit ist. Jede LUT 40 weist die Möglichkeit auf, durch ein gültiges Kodewort adressiert zu werden. Na­ türlich braucht kein LUT 40 an der Position 1 vorhanden zu sein, wenn der Huffman-Kode keine Kodeworte der Länge 1 enthält.

Typischerweise wird die erste versetzte Position in Abhän­ gigkeit des Minimums gewählt, da die kodierten Einheiten jede Länge zwischen irgendeinem Minimum und irgendeinem Maximum aufweisen können. Die folgenden Positionen sind nacheinander ausgewählt worden. Wenn z. B. eine bestimmte Anwendung kodierte Einheiten aufweist, die mit einer we­ sentlich höheren Wahrscheinlichkeit geradzahlige Längen aufweisen als ungeradzahlige Längen, kann es optimal sein, versetzte LUT′s nur geraden Positionen zuzuordnen.

Geht man zu dem Beispiel gemäß Fig. 8 zurück, so erzeugt die erste Einheit 40-0 immer ein gültiges Ausgangssignal. Die anderen LUT-Einheiten 40 können ein gültiges Resultat erzeugen, wenn die Eingangsanschlüsse jener LUT-Einheiten an dem Beginn eines Kodeworts angeordnet sind. Der Ausgang einer ersten Speichereinheit 40-0 zeigt der LUT-Einheit 40 an, welche das nächste gültige Resultat aufweist, und die Einheit 40 zeigt nachfolgend die folgende Einheit 40 mit einem gültigen Resultat an, bis sämtliche gültigen Resulta­ te gefunden worden sind.

Die Fig. 9A stellt die Schritte zur Durchführung des Deko­ dierungszyklus mit der versetzten Tabellenarchitektur dar. Zuerst wird eine Suchoperation parallel für sämtliche Such­ tabelleneinheiten 40 durchgeführt. Die Gesamtlänge der Da­ ten-Einheiten, die Kodeworte in gültige Belegungsbits deko­ diert haben, wird anschließend berechnet, und der Bit- Schieber 24 wird anschließend um den berechneten Betrag verschoben. Die Operation geht für den nächsten Dekodie­ rungszyklus zu dem ersten Schritt zurück.

Diese sequentielle Operation zum Bestimmen der Gesamtzahl der Bits zum Schieben in dem Register 24 scheint die Deko­ diereroperation zu verlangsamen. Jedoch ist die Rückkopp­ lungsinformation zum Betätigen des Schiebers 24 für die nächste Dekodierungsoperation nur eine 5-Bit-Ausgangsfunk­ tion einer großen Anzahl von Eingangssignalen. Anstatt die Berechnungen sequentiell durchzuführen, kann die Bestimmung des Betrages der Bit-Verschiebung mit einer verdrahteten Logik umgesetzt werden, so wie sie beispielhaft in Fig. 8B gezeigt ist, da die Funktion unabhängig von dem bestimmten verwendeten Huffman-Kode ist. Exemplarische Anhänge A und B, welche am Ende dieser Beschreibung angefügt sind, sind zutreffende Tabellen, welche verwendet werden können, um den verdrahteten Logikblock 20 für die versetzte Suchtabel­ len-Dekodiererarchitektur nach Fig. 8A herzustellen. 8 LUT- Einheiten 40 mit einem 1-Bit-Versatz zwischen jeder der Einheiten 40 werden angenommen. Mit einem JPEG-Huffman-Kode wird es ebenfalls angenommen, daß die längste Kode-Daten- Einheit 27 Bits beträgt.

Im Anhang A stellen die aufgelisteten Eingangszahlen die Länge der kodierten Dateneinheit an jedem versetzten Ort dar. Die Ausgangszahlen sind die Gesamtzahlen, um den Bit- Shifter bzw. -Schieber zu verschieben bzw. zu shiften. Der Anhang B enthält die unterschiedlich gezeigten äquivalenten Informationen. Die aufgelisteten Eingangszahlen stellen die Länge der kodierten Dateneinheit an jedem versetzten Ort und die Position des versetzten Ortes dar. Die Ausgangszah­ len sind die gleichen wie für Anhang A. Verschiedene kombi­ natorische logische Implementationen ergeben sich aus den zwei Tabellen.

Alternativ können die Signale willkürlich sein, da die Aus­ gangssignale für den kombinatorischen Logikblock 20 von den LUT-Einheiten 40 sind. Deshalb kann eine Verschlüsselung der Größeninformation einfach als der Logikblock 20 gewählt werden.

Für die versetzte Tabellenarchitektur weist der Multi­ plexer-Steuerlogikblock 23 in Fig. 4 einen Zwischenspeicher und eine kleine Menge an logischer Schaltung auf. Die Ope­ ration, die der der Dekodierer-Architektur mit breiten Ta­ bellen sehr ähnlich ist, wird ebenfalls durch das Flußdia­ gramm in Fig. 7 gezeigt. Der Zwischenspeicher, welcher die versetzte Position eines Kodeworts anzeigt, ist anfangs Null. Wenn ein Startsignal auftritt, wird der Zwischenspei­ cher, der den Wert Null aufweist, den Ausgang des Registers 21 freigeben, der das anfängliche Belegungsbit an der Posi­ tion Null aufweist. Die Gültigkeit des Belegungsbits in diesem Register wird geprüft, indem bestimmt wird, ob die Länge der unkodierten Dateneinheit, die zu dem Belegungsbit in dem Register 21 korrespondiert, Null ist oder nicht. Wenn das Belegungsbit gültig ist (die Länge ist nicht Null), macht der Block 23 das FIFO-Eingangsfreigabesignal geltend, so daß die Inhalte des Registers 21 in das FIFO geladen werden. Wenn das Belegungsbit ungültig ist (die Länge ist Null), kehrt der Block 23 zu dem Zustand zurück, in dem er den nächsten Dekodierungszyklus und ein Start­ signal erwartet, nachdem der Zwischenspeicher gelöscht wor­ den ist. Angenommen, das Belegungsbit ist gültig, so weist nun der Speicher bzw. Zwischenspeicher die versetzte Posi­ tion des nächsten Kodewortes auf. Eine Prüfung wird durch­ geführt, ob die Position zutrifft, indem überprüft wird, ob eine maximale Zahl erreicht worden ist. Wenn nicht, gibt der Logikblock 23 das nächste Register 21 an der Position frei, die durch den Zwischenspeicher angezeigt wird. Eine Gültigkeitsprüfung des Belegungsbits im nächsten Register wird durchgeführt und die Schritte werden fortgesetzt, bis die maximale Zahl erreicht wird oder ein ungültiges Bele­ gungsbit aufgefunden wird. Der Zwischenspeicher bzw. Spei­ cher wird dann für den nächsten Dekodierungszyklus und ein Start- bzw. Anfangssignal gelöscht. Alternativ kann der Zwischenspeicher durch einen Signalspeicher ersetzt werden, wenn die Datenlänge in jedem Register 21 durch eine Eingabe der Länge plus der versetzten Position ersetzt wird, wie in dem Fall gemäß Anhang B. Die Operation bleibt dieselbe.

Eine Abwandlung der versetzten Dekodiererarchitektur mit Suchtabelle vermeidet den Zeitnachteil zum Bestimmen der Gesamtbits, um den Bit-Schieber 24 zu schieben bzw. zu shiften. Bei dieser Dekodierer-Architektur schiebt bzw. shiftet der Bit-Schieber 24 mittels eines konstanten Glei­ chen bzw. Pendants zu der Anzahl der versetzten LUT-Einhei­ ten 40 bei einer konstanten Rate. Die Bestimmung, welche der versetzten Suchtabellen-Speichereinheiten 40 mit gülti­ gen Kodeworten adressiert worden sind, ist bei den Rück­ kopplungssignalen zum Schieben der Schieber 24 nicht er­ forderlich. Diese Bestimmung kann erübrigt werden.

Die Operationsschritte für einen Dekodierungszyklus für diese Abwandlung sind in Fig. 9B gezeigt. In diesem Fall wird eine parallele Suche für samtliche der LUT-Einheiten 40 durchgeführt. Dann wird der Bit-Schieber 24 betätigt, um die Zahl der Bits zu verschieben, die gleich der Zahl der LUT-Einheiten 40 vor dem nächsten Dekodierungszyklus ist.

Diese Architektur weist an jeder versetzten Position eine Suchtabellen-Speichereinheit auf, wie oben im Hinblick auf Fig. 8A beschrieben worden ist. Jedoch erzeugt jede, abwei­ chend von der obigen Beschreibung, mehrere Ausgangsbeleg- Bits bei einer Anwendung parallel, die mehrere Huffman-Ko­ des aufweist. Eine derartige Anwendung ist das obige JPEG- Beispiel. Vier Ausgangsbelegungs-Bits werden parallel er­ zeugt, ein Belegungsbit bzw. Token jeweils für den AC- Bildleuchtdichte-, den DC-Bildleuchtdichte-, den AC-Farb­ ton- und den DC-Farbton-Huffman-Kode. Nach jedem Dekodie­ rungszyklus wird der Schieber 24 um die Anzahl der versetz­ ten Anschlüsse zu den Speichereinheiten verschoben, so daß jede Bitposition in dem Eingabestrom für jeden Huffman-Kode dekodiert wird. Da sämtliche möglichen Ergebnisse verfügbar sind, ist keine zusätzliche Dekodierung notwendig. Die zu­ treffenden Resultate werden nach jedem Dekodierungszyklus aus sämtlichen möglichen Resultaten ausgewählt. Die Steuer­ logik zieht das dekodierte Belegungsbit von jeder Bitposi­ tion in dem Strom in Betracht. Nur wenn diese Bitposition ein gültiges Kodewort enthält, wählt die Steuerlogik das korrespondierende Belegungsbit für das gegenwärtige Huffman-Kodewort aus und erhöht die Zahl, um die zu igno­ rierende Anzahl von Bitpositionen bis zum nächsten gültigen Kodewort. Zu dieser Zeit bestimmt die Steuerlogik auch den Huffman-Kode, die AC-Bildleuchtdichte, die DC-Bildleucht­ dichte, den AC-Farbton und den DC-Farbton, zu welchen das nächste Kodewort gehört. Da der Betrag des Verschiebens in dem Bit-Schieber 24 vor jedem Dekodierungszyklus immer kon­ stant ist, ist ein Trommelschieber in der Einheit 24 nicht erforderlich, was eine signifikante Hardware-Einsparung er­ gibt.

Diese bestimmte Dekodiererarchitektur kann eine besondere Anwendbarkeit für HDTV aufweisen. Anstelle auf die Menge der Belegungsbits pro Bildbereich beschränkt zu sein, die sie verarbeiten kann, ist die Dekodiererarchitektur auf die Zahl von Eingabebits pro Bildbereich beschränkt. Da HDTV- Übertragungsdaten wahrscheinlicher zum Spezifizieren einer maximalen Bitrate als einer Belegungsbitrate sind, kann das Bestimmen der Zahl der versetzten Speichereinheiten, die für einen gegebenen Kodierungsstandard erforderlich sind, leichter sein. Ein Nachteil dieser Abwandlung ist, daß jede Bitposition in allen vier Kodes dekodiert werden muß. Die­ ses erfordert große Speichereinheiten als Suchtabellen 40 an jeder versetzten Position.

Eine andere Abwandlung dieser Dekodierer-Architektur be­ treibt auch den Bit-Schieber 24, um diesen um die Anzahl der konstanten Anzahl von Bits, zu verschieben, die der Zahl von versetzten LUT-Einheiten 40 gleich ist. Die Platz­ menge, die für die Suchtabelleneinheiten 40 erforderlich ist, ist ebenfalls reduziert. Da Huffman-Kodeworte nicht mit gleichmäßiger Frequenz auftreten, muß nur die LUT- Einheit 40-0 für die anfängliche Bitposition jedes mögliche Kodewort handhaben können. Die LUT-Einheiten 40-i (i < 0) an anderen Positionen brauchen nur allgemeine oder kurze Kodeworte handhaben zu können. Solange allgemeine Kodeworte an anderen versetzten Positionen in dem Bitstrom auftreten, operiert diese Abwandlung wie die frühere Abwandlung. Wenn ein langes oder ungleichmäßiges Kodewort an einer Position auftritt, die es nicht handhaben kann, wird ein Fehler­ signal erzeugt. Das Fehlersignal verwendet den Trommel­ schieber in der Bit-Schiebereinheit 24, um den Dekodierer mit der unzutreffenden Bitposition an der anfänglichen Po­ sition des Schiebers 24 neu zu starten. Folglich werden un­ gleichmäßig auftretende Kodeworte wie ein Fehlerzustand be­ handelt. Diese nachfolgende "Fehlerhandhabungsoperation" bewirkt eine Zeitverzögerung, da einige Bitpositionen mehr als einmal dekodiert werden.

Fig. 9C stellt die Operationsschritte für den Dekodierungs­ zyklus für diese architektonische Abwandlung dar. Durch den ersten Schritt wird eine parallele Such- bzw. Nachsuchope­ ration in sämtlichen Suchtabellen 40 durchgeführt. Dann wird der Bit-Schieber 24 betätigt, um die Anzahl von Bits zu schieben, die gleich der Anzahl der LUT-Einheiten 40 ist. Eine Bestimmung wird dann vorgenommen, wenn ein Feh­ lersignal durch den Multiplexer-Steuerlogikblock 23 erzeugt wird, der dieser Dekodierer-Architektur zuzuordnen ist. Die Operation der Schaltung nach Fig. 4 und der Steuerlogik­ block 23 sind, wie oben im Hinblick auf Fig. 7, zu be­ schreiben. Wenn sämtliche LUT′s 40 ihre zugeordneten Kode­ worte handhaben bzw. suchen können, wird kein Fehlersignal (Länge ungleich 0, Belegungsbit gültig) erzeugt, so kehrt die Dekodierungsoperation für den nächsten Dekodierungs­ zyklus an den Start zurück, wie in Fig. 9C gezeigt. Wenn eines der reduzierten LUT′s 40-i (i < 0) sein Kodewort nicht suchen kann und ein Fehlersignal (Länge 0, Belegungs­ bit ungültig) erzeugt, wird der Trommelschieber in der Bit- Schiebereinheit 24 umgekehrt betätigt, um die Bits zu dem Ort zu schieben, wo der Fehler lokalisiert worden ist. Das unzutreffende Kodewort wird an der anfänglichen Bitposition zur Dekodierung durch die LUT 40-0 plaziert, welche dazu in der Lage ist, sämtliche möglichen Kodeworte zu handhaben. Die Operation wird an den anfänglichen Schritte zur aberma­ ligen Dekodierung zurückgeführt.

Die Steuerspeicher-Architektur

Fig. 10A stellt eine Steuerspeicher-Architektur dar. In dieser Architektur wird eine Steuerspeichereinheit 50 mit den Zellen der Bit-Schiebereinheit 24 verbunden. Der Spei­ cher 50 weist viele Adreßorte auf, jedoch ist die Anzahl der Ausgangsbits für jeden Ort klein. Diese kleine Zahl von Ausgangsbits spezifiziert die Information, die zu dem Bit- Schieber 24 zurückzuleiten ist, z. B. die Gesamtzahl von Bits, die für den nächsten Dekodierungszyklus zu schieben sind und Blockendesignale.

Die aktuelle Dekodierung wird durch mehrere verbundene De­ kodierungsstufen durchgeführt. Die Dekodierungsstufen sind mit jeder Stufe verbunden, die ein Eingangs-Schieberegister 52 aufweist, das durch die vorherige Stufe angetrieben wird. Folglich adressieren die Bits in dem Schieber 24 eine erste LUT-Einheit 51-0, die einen Teil der ersten Stufe bildet, um das Ausgangsbelegbit des Kodeworts in der ersten Position in dem Schieberegister 24 zu erzeugen. In dem Auf­ gang sind die Bits enthalten, die die Länge der kodierten Koeffizienten in der ersten Position spezifizieren.

Zu der gleichen Zeit werden die Bits in dem Schieber 24 ebenfalls in einem Signalspeicher 52-0 der ersten verbunde­ nen Stufe geladen. Die Bits in dem Signalspeicher 52-0 pas­ sieren zu einem Schieberegister 53-0 in der ersten Stufe. Unter Steuerung der Ausgangsbits von der LUT-Einheit 51-0 der ersten Stufe verschiebt das Schieberegister 53-1 über die Länge der kodierten Dateneinheit. Der verschobene In­ halt in den Zellen des Registers 53-0 adressiert eine LUT- Einheit 51-1 für die zweite Verbindungs- bzw. Hauptlei­ tungsstufe. Die LUT-Einheit 51-1 erzeugt das Belegungsbit, das die Länge spezifizierende Bits enthält, für die nächste kodierte Dateneinheit in dem Bitstrom, der durch den Bit- Schieber 24 passiert. Bei der nächsten Stufe werden die In­ halte des Schieberegisters 53-0 der ersten Stufe in einen Signalspeicher 52-1 der zweiten Stufe geladen, welcher die Bits in ein Schieberegister 53-1 der zweiten Stufe passie­ ren läßt. In Abhängigkeit zu den die Länge spezifizierenden Ausgangsbits von der LUT-Einheit 51-1 der zweiten Stufe verschiebt das Schieberegister 53-1 der zweiten Stufe seine Inhalte, welche anschließend eine LUT-Einheit 51-2 für die dritte Stufe adressieren. Die LUT-Einheit 51-2 erzeugt dann das Belegungsbit für die nächste Dateneinheit in den ko­ dierten Daten. Diese verbundene Dekodierung setzt sich fort, bis sämtliche gültigen Kodeworte von dem Bit-Schieber 24 dekodiert worden sind. In der Zwischenzeit wird der nächste Satz von geschobenen Daten von dem Bit-Schieber 24 in einer verbundenen Dekodierungsoperation dekodiert.

Die operationsmäßigen Schritte für die Steuerspeicher-Ar­ chitektur sind in Fig. 11 dargestellt. Viele Schritte wer­ den parallel durchgeführt. Eine anfängliche Such- bzw. Nachprüfoperation wird mit der Speichereinheit 50 durchge­ führt, um die Gesamtlänge der dekodierten Daten in dem Bit- Schieber 24 zu erhalten (und irgendwelche Belegungsbits für ein Blockende für das JPEG-Beispiel). Der Bit-Schieber 24 wird anschließend über diesen Betrag verschoben und die Operationen kehren an den anfänglichen Schritt zurück. Diese zwei Schritte werden durch die zwei operationsmäßigen Blocks auf der linken Seite der Darstellung gezeigt. In der Zwischenzeit wird eine Operation bzw. werden Operationen der verbundenen Dekodiererstufen durchgeführt, wie dieses durch sämtliche Operationsblocks zur Rechten der linken Blocks dargestellt wird. Ein Such- bzw. Nachprüfschritt wird anfänglich durch eine Such- bzw. Nachprüftabellenein­ heit 51-i durchgeführt. Ein Belegungsbit bzw. Token wird zusammen mit der Länge der dekodierten Dateneinheit, die dem Belegungsbit zuzuordnen ist, erzeugt. Das Schieberegi­ ster 53-i dieser Stufe verschiebt die Daten über die Länge der dekodierten Dateneinheit und die Operation kehrt zu dem Such- bzw. Nachprüfschritt für die Tabelleneinheit 51-i+1 der nächsten Stufe zurück. Diese verbundene Operation setzt sich fort, bis die letzte Stufe erreicht worden ist, an welchem Punkt eine Such- bzw. Nachprüfoperation mit der letzten Such- bzw. Nachprüftabelleneinheit 53-m durchge­ führt wird, wobei m die Anzahl der Such- bzw. Nachprüfta­ belleneinheiten 53 ist.

Für die Steuerspeicher-Architektur kann der Multiplexer- Steuerlogikblock 23 nach Fig. 4 identisch mit dem für die Dekodierer-Architektur mit breiter Tabelle sein, die zuvor mit der gleichen Operation beschrieben wurde, die im Hin­ blick auf Fig. 7 beschrieben wurde. In dieser Steuerspei­ cher-Architektur sind unnötige spekulative Suchen bzw. Nachprüfungen vermieden. Einsparungen an Speicherplatz kön­ nen durch Ersetzen jeder der LUT′s 51-i durch zwei Spei­ chereinheiten erzielt werden. Die LUT′s 51-i erzeugen ein Belegungsbit, das im Falle von JPEG durch Exponenten-Bits und Lauflängen-Bits und die Länge der gesamten kodierten Dateneinheit gebildet wird. Wie in Fig. 10B dargestellt, ist jedes LUT in einen ersten Teil 51A, welcher das Bele­ gungsbit erzeugt, und einen zweiten Teil 51B aufgeteilt, welcher die Länge der kodierten Einheit erzeugt. Eine zwei­ stufige Such- bzw. Nachprüfoperation wird durchgeführt, je­ doch werden wesentliche Einsparungen an Speicherplatz über eine einzelne LUT erhalten, welche sowohl die Belegungsbits als auch die Längen erzeugt.

Eine andere Beobachtung ist, daß in vorherigen Beschreibun­ gen angenommen wurde, daß die LUT′s sowohl das Belegungsbit als auch die Länge der kodierten Dateneinheit erzeugen müs­ sen, um schnell zu sein. In diesen Beispielen ist es be­ quem, eine Länge Null zu verwenden, um ein ungültiges Bele­ gungsbit anzuzeigen. Wenn diese Längeninformation nicht gültig ist, können ungültige Belegungsbits als bzw. von den Belegungsbits selbst oder andere Steuerbits angesehen wer­ den.

Eine Abwandlung dieser Architektur führt die erste LUT-Ein­ heit 51-0 als eine Such- bzw. Nachprüftabelle nur für DC- Kodes aus. Wenn die LUT 51-0 nicht durch einen Koeffizien­ ten am Anfang eines Koeffizientenblocks adressiert wird, wird der Ausgang von der LUT 51-0 übersprungen. Der Rest der an der Hauptleitung angeschlossenen bzw. damit verbun­ denen Stufen handhabt AC-Kodes, so daß sämtliche der LUT- Einheiten kleiner sind, als die angenommene minimale Größe.

Minimale Größe der Speichereinheit

Bei der obigen Diskussion der verschiedenen Dekodierer- Architekturen ist es offensichtlich, daß ein großer Teil des Platzes der integrierten Schaltung, um die ausgewählte Architektur umzusetzen, durch Speicher für Such- bzw. Nach­ prüftabellen besetzt wird. Die vorliegende Erfindung bietet auch eine Organisation bzw. Anordnung für eine Speicherein­ heit, so daß die Speichermenge, die durch jede Speicherein­ heit besetzt wird, entweder RAM oder ROM, minimiert wird.

Diese Speicherorganisation bzw. -anordnung ist in Fig. 12A dargestellt. Anstelle einer einzelnen Speichereinheit, wie etwa zuvor beschrieben, ist jede Speichereinheit in drei getrennte Speichereinheiten 60A, 60B und 60C aufgeteilt. Wie zuvor beschrieben, ist der gesamte Speicher an die ein­ zelnen Zellen in der Schieber-Einheit 24 angeschlossen. In Fig. 12A sind die ersten 16 Zellen des Schiebers 24 an den Speicher angeschlossen, so daß der Inhalt von 8 Zellen je­ den der Speicher 60A-60C in einer überlappenden Weise adressiert. Zellen 0-7 adressieren den Speicher 60A, Zellen 4-11 adressieren den Speicher 60B und Zellen 8-15 adressie­ ren den Speicher 60C.

Die Speichereinheiten 60A, 60B und 60C sind Such- bzw. Nachprüftabellen, welche jeweils kurze, mittellange und lange Kodeworte dekodieren. Eine kombinatorische Logik, die durch einen Block 61 dargestellt ist, gibt einen der Speicher 60A-60C frei. Wenn die ersten acht Zellen alle lo­ gische "Einsen" enthalten, wird der Speicher 60C für lange Kodeworte freigegeben. Andererseits wird, wenn die ersten vier Zellen alle logische "Einsen" enthalten, der Speicher 60B für mittellange Kodeworte freigegeben. Ansonsten wird der Speicher 60A für kurze Kodeworte freigegeben.

Die kombinatorische Logik, die diese Freigabefunktion durchführt, ist in Fig. 12B dargestellt. Fünf Gates, die eine Logik mit zwei Niveaus mit einer Zusammenführung von vier Eingängen aufweisen, werden verwendet. Die kombinato­ rische Logik nimmt eine sehr kleine Menge an Platz ein. Zu­ sätzlich wird die Freigabefunktion zum Auswählen einer der Speichereinheiten 66A-60C sehr schnell durchgeführt. Da diese Freigabefunktion anhand von Daten von dem Bitstrom in dem Schieber 24 erzeugt wird, gibt es kein Erfordernis für eine Dekodierungsfunktion, die vor der Auswahl durchgeführt wird.

Die Operationen werden in dem Flußdiagramm nach Fig. 13 dargestellt. Vier operationsschritte werden anfänglich pa­ rallel durchgeführt. Such- bzw. Nachprüfoperationen werden für den Speicher 60A für kurze Kodeworte, den Speicher 60B für mittlere Kodeworte und den Speicher 60C für lange Kode­ worte durchgeführt. Auch Steuersignale, um den zutreffenden Speicher auszuwählen, werden erzeugt. Dann wird der Ausgang des ausgewählten Speichers freigegeben.

Diese Speicheranordnung bzw. -organisation minimiert den Speicherplatz. Nur drei Speicher mit acht Eingängen werden anstelle eines einzelnen großen Speichers verwendet. Zum Vergleich, ein Speicher mit 16 Eingängen zum Handhaben von AC-Huffman-Kodes erfordert einen Speicher von 852.000 Bits. In dem vorliegenden Fall werden nur 9.984 Bits verwendet.

Ein möglicher Nachteil ist, daß diese Speicheranordnung bzw. -organisation nicht sämtliche möglichen Huffman-Kodes bewältigen kann. Kodeworte aus 9 bis 12 Bits müssen mit zu­ mindest vier "Einsen" beginnen und längere Kodeworte müssen mit zumindest acht "Einsen" beginnen. Jedoch können die meisten Kodes, welche durch die kanonische Form spezifi­ ziert werden, die vom JPEG-Standard verwendet wird, verarbeitet werden. Jegliche einheitlichen Sätze von Prä­ fixen bzw. Vorsatzkodes können verwendet werden, wie etwa z. B. acht oder vier "Nullen".

Diese reduzierte Speicherorganisation ist für sämtliche, zuvor oben beschriebenen Dekodierer-Architekturen anwend­ bar, ausgenommen der Architektur mit breiter Tabelle. Not­ wendigerweise kann die Speichereinheit bei dieser Architek­ tur nicht aufgebrochen bzw. unterbrochen werden; der Spei­ cher muß vollständig spezifiziert bleiben. Jedoch kann das Such- bzw. Nachprüfkonzept mit breiter Tabelle verwendet werden, um diese Erfindung zusätzlich zu verbessern. Zum Beispiel kann der Speicher 60A für kurze Kodeworte selbst eine "breite" Tabelle sein, die dazu in der Lage ist, mehr als ein Belegungsbit gleichzeitig für verschiedene kurze Kodeworte in Zellen 0-7 zu erzeugen. Da der Speicher 60A nun als mehrere Belegungsbits zugleich erzeugend angenommen werden kann, können mehrere Zellen 8-11 an den Speicher 60A angeschlossen werden.

Schließlich sind in der obigen Beschreibung von bestimmten Dekodierer-Architekturen die Merkmale der verschiedenen Dekodierer-Architekturen aus Zwecken der Darstellbarkeit getrennt worden. Viele dieser Merkmale können miteinander für einen Huffman-Dekodierer kombiniert werden, welcher be­ sonders auf eine Anwendung oder ein Erfordernis ausgerich­ tet ist. Zum Beispiel sollten viele der Verwirklichungen von Huffman-Dekodierern für JPEG für viele der aufkommenden bzw. zukünftigen Standards für digitale Bildverarbeitung anwendbar sein, wie etwa MPEG und HDTV. Folglich sollte der Ausdruck "JPEG", der zuvor in der Beschreibung von ver­ schiedenen Umsetzungen der vorliegenden Erfindung benutzt wurde, nicht streng betrachtet werden, sondern viel eher breit, als "JPEG"-artig.

Folglich können verschiedene Alternativen, Modifikationen und Äquivalente der vorliegenden Erfindung verwendet wer­ den, während die obige Beschreibung eine vollständige Be­ schreibung der bevorzugten Ausführungsformen nach der Er­ findung ist. Es sollte klar sein, daß die vorliegende Er­ findung gleichermaßen anwendbar ist, indem zweckmäßige Mo­ difikationen der oben beschriebenen Ausführungsformen vor­ genommen werden. Deshalb sollte die obige Beschreibung nicht als Beschränkung des Schutzbereichs der Erfindung an­ gesehen werden, welcher durch die Grenzen der nachfolgenden Ansprüche definiert wird.

Anhang A

Anhang B

Claims (47)

1. Dekodierer für Einheiten von Huffman-kodierten Daten, wobei jede Einheit Kodeworte aufweist und der Dekodierer einen Eingangsanschluß aufweist, der die Daten empfängt bzw. entgegennimmt,
mit einer Bit-Schiebereinheit (24), die an den Eingangsanschluß ange­ schlossen ist und mehrere Zellen aufweist, wobei jeweils eine Zeile ein Bit der entgegengenommenen Daten hält, und
mit einer Speichereinheit (30), die mehrere Eingangsadressenanschlüsse und Ausgangsanschlüsse aufweist, wobei jeder der Adressenanschlüsse an eine der Schieberegisterzellen angeschlossen ist, wobei die Speichereinheit (30) an den Ausgangsanschlüssen simultan bzw. gleichzeitig Belegungsbits von jedem voll­ ständigen Kodewort an den Eingangsadressenanschlüssen erzeugt, wobei die Speichereinheit (30) Steuersignale erzeugt, die zu der Gesamtlänge der kodierten Einheiten korrespondieren, die vollständige Kodeworte an den Eingangsadres­ senanschlüssen aufweisen, so daß die kodierten Daten durch die Bit-Schieberein­ heit (24) geschoben werden können,
wobei wenigstens zwei Belegungsbits an Adressen der Speichereinheit (30) gespeichert werden und wobei wenigstens eine Adresse der Speichereinheit (30) mehr als ein Belegungsbit an einer Adresse speichert, die eine Konzentration von mehr als einem Kodewort bildet, wodurch die kodierten Dateneinheiten gleichzei­ tig dekodierbar sind und die Bit-Schiebereinheit (24) für einen nächsten Dekodie­ rungszyklus bereit ist.

2. Dekodierer nach Anspruch 1, dadurch gekennzeichnet, daß die Speicher­ einheit (30) zumindest so viele Eingangsanschlüsse aufweist, wie das größte Kodewort in den Huffman-kodierten Daten.

3. Dekodierer nach einem der Ansprüche 1 oder 2, dadurch gekennzeichnet, daß die Speichereinheit (30) dafür ausgebildet ist, Belegungsbits für sämtliche Kodeworte nur für eine Untermenge der Eingangsadressenterminals zu erzeugen.

4. Dekodierer nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, daß die Speichereinheit (30) dafür ausgebildet ist, Belegungsbits für sämtliche Kodeworte nur für ein zuerst in der Bit-Schiebereinheit (24) positioniertes Ko­ dewort zu erzeugen.

5. Dekodierer nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß die Speichereinheit (30) dafür ausgebildet ist, Belegungsbits für eine Unter­ menge von Kodeworten an Plätzen, die nicht mit dem zuerst positionierten Kode­ wort in der Bit-Schiebereinheit (24) übereinstimmen, zu erzeugen, wobei die Untermenge der Kodeworte die am häufigsten auftretende ist.

6. Dekodierer nach Anspruch 1, dadurch gekennzeichnet,
daß die Bit-Schiebereinheit (24) dafür ausgebildet ist, die Bits der empfan­ genen Daten in der Ordnung des Eingangs zu halten,
daß mehrere Suchtabelleneinheiten (40-0, 40-1, 40-2) vorgesehen sind, die an die Bit-Schiebereinheit (24) so angeschlossen sind, daß jede der Such- bzw. Nachprüftabelleneinheiten gleichzeitig Belegungsbits erzeugt, die einer Mehrzahl von in der Ordnung des Eingangs versetzten Bits entspricht, und
eine Logikeinrichtung (20) vorgesehen ist, die an die Suchtabelleneinheiten (40-0, 40-1, 40-2) angeschlossen ist, um zu bestimmen, welche der Suchtabellen­ einheiten gültige Belegungsbits erzeugt,
wodurch der Dekodierer in einem Zyklus eine oder mehrere Einheiten der empfangenen bzw. entgegengenommenen Daten dekodiert, die Bits von kom­ pletten Kodeworten aufweisen, die eine Suchtabelleneinheit dazu veranlassen, ein Belegungsbit zu erzeugen.

7. Dekodierer nach Anspruch 6, dadurch gekennzeichnet, daß die Logik­ einrichtung (20) zusätzlich die gesamte Anzahl von Bits bestimmt, die durch die Bit-Schiebereinheit (24) für einen nächsten Dekodierungszyklus zu verschieben sind.

8. Dekodierer nach einem der Ansprüche 6 oder 7, dadurch gekennzeichnet, daß ein Anschluß von jeder Suchtabelleneinheit (40-0, 40-1, 40-2) zu der Bit- Schiebereinheit (24) um ein Bit versetzt ist.

9. Dekodierer nach einem der Ansprüche 6 bis 8, dadurch gekennzeichnet, daß ein Anschluß von jeder Suchtabelleneinheit (40-0, 40-1, 40-2) zu der Bit- Schiebereinheit (24) um Beträge versetzt ist, die den am wahrscheinlichsten auftretenden Kombinationen von kodierten Dateneinheiten entsprechen.

10. Dekodierer nach einem der Ansprüche 6 bis 9, dadurch gekennzeichnet, daß Einheiten von Huffman-kodierten Daten einer Mehrzahl von Huffman-Kodes entsprechen und die Suchtabelleneinheiten (40-0, 40-1, 40-2) eine Mehrzahl von Belegungsbits parallel erzeugen, ein Belegungsbit für jeden Huffman-Kode.

11. Dekodierer nach einen der Ansprüche 6 bis 10, dadurch gekennzeichnet, daß die Mehrzahl von Suchtabelleneinheiten (40-0, 40-1, 40-2) vier Belegungsbits parallel erzeugt, jeweils ein Belegungsbit für AC-Bildleuchtdichte-, DC-Bild­ leuchtdichte-, AC-Farbton- und DC-Farbton-Huffman-Kodes.

12. Dekodierer nach einem der Ansprüche 6 bis 11, dadurch gekennzeichnet, daß mehreren der Suchtabelleneinheiten (40-0, 40-1, 40-2) einer ersten Einheit, die an eine Anfangsposition der Bit-Schiebereinheit (24) angeschlossen ist, und zumindest eine zweite Einheit aufweisen, die an die Bit-Schiebereinheit (24) zu der Anfangsposition versetzt angeschlossen ist, wobei die erste Einheit Bele­ gungsbits für alle möglichen Kodeworte erzeugt, und die zweite Einheit Bele­ gungsbits für eine Untermenge von allen möglichen Kodeworten erzeugt.

13. Dekodierer nach einem der Ansprüche 6 bis 12, dadurch gekennzeichnet, daß die Gesamtmenge von Bits, die durch die Bit-Schiebereinheit (24) für einen nächsten Dekodierungszyklus zu verschieben sind, festlegbar ist.

14. Dekodierer nach einem der Ansprüche 6 bis 13, dadurch gekennzeichnet, daß eine Verbindung von jeder Suchtabelleneinheit (40-0, 40-1, 40-2) zu der Bit- Schiebereinheit (24) um ein Bit versetzbar ist.

15. Dekodierer nach Anspruch 12, dadurch gekennzeichnet, daß dieser auf einen durch die zweite Einheit in Abhängigkeit zu einem Satz von Bits in der Bit-Schiebereinheit (24) erzeugten Belegungsbit anspricht, wobei die Bit-Schieber­ einheit (24) den Satz von Bits verschiebt, so daß die erste Einheit ein Belegungsbit in Abhängigkeit dazu erzeugt.

16. Dekodierer nach Anspruch 1, gekennzeichnet durch
eine erste Suchtabelleneinheit (40-0), die an zumindest einen ersten Ab­ schnitt der Bit-Schiebereinheit (24) angeschlossen ist, um Steuersignale zum Schieben des Registers in Abhängigkeit zu der gesamten Länge der kodierten Einheiten zu erzeugen, die vollständige Kodeworte in dem ersten Abschnitt der Bit-Schiebereinheit (24) aufweisen, und
eine Mehrzahl von zweiten Suchtabelleneinheiten (40-1, 40-2), die an den ersten Abschnitt der Bit-Schiebereinheit (24) in einer Hauptleitung angeschlossen sind, wobei die zweiten Suchtabelleneinheiten sequentiell Belegungsbits abhängig zu den vollständigen Kodeworten in dem ersten Abschnitt erzeugen,
wodurch die Bit-Schiebereinheit (24) für eine nachfolgende Dekodier­ operation ohne das Erfordernis einer Dekodierung eines Kodeworts der empfan­ genen Daten verschieben kann.

17. Dekodierer für Einheiten von Huffman-kodierten Daten nach Anspruch 16, dadurch gekennzeichnet, daß die Mehrzahl von zweiten Suchtabelleneinheiten (40-1, 40-2) eine erste Einheit zum Dekodieren eines ersten Kodeworts in der Bit-Schiebereinheit (24) und zumindest eine zweite Einheit aufweist, um ein Kodewort, das dem ersten Kodewort in der Bit-Schiebereinheit nachfolgt, zu dekodieren, wobei die zweite Einheit dafür ausgebildet ist, nur eine Untermenge von Kodeworten, die durch die erste Einheit dekodiert werden können, zu deko­ dieren.

18. Dekodierer für Einheiten von Huffman-kodierten Daten nach einem der Ansprüche 16 oder 17, dadurch gekennzeichnet, daß die Huffman-kodierten Daten JPEG-Daten aufweisen und die erste Einheit dafür ausgebildet ist, Bele­ gungsbits für DC-Koeffizienten zu erzeugen.

19. Dekodierer für Einheiten von Huffman-kodierten Daten nach einem der Ansprüche 16 bis 18, dadurch gekennzeichnet, daß die verbleibenden zweiten Suchtabelleneinheiten (40-1, 40-2) dafür ausgebildet sind, Belegungsbits für AC-Koeffizienten zu erzeugen.

20. Dekodierer für Einheiten von Huffman-kodierten Daten nach einem der Ansprüche 16 bis 19, dadurch gekennzeichnet, daß die erste Einheit (40-0) dafür ausgebildet ist, alle Kodeworte in den Huffman-kodierten Daten zu dekodieren.

21. Dekodierer für Einheiten von Huffman-kodierten Daten nach einem der Ansprüche 16 bis 20, dadurch gekennzeichnet, daß die Mehrzahl von zweiten Suchtabelleneinheiten (51-1, . . ., Fig. 10A) über eine Mehrzahl von Signalspei­ chern (52-0) und Schiebern (53-0, . . .) angeschlossen sind, wobei ein Signal­ speicher und ein Schieber jeder der zweiten Suchtabelleneinheiten (51-1, . . ., Fig. 10A) zuzuordnen sind, wobei eine zweite Suchtabelleneinheit an den ersten Abschnitt des Schiebers parallel zu der ersten Suchtabelleneinheit angeschlossen ist, wobei die eine zweite Suchtabelleneinheit ein Belegungsbit erzeugt, das zu einem ersten vollständigen Kodewort in dem ersten Abschnitt des Schiebers korrespondiert.

22. Dekodierer für Einheiten von Huffman-kodierten Daten nach Anspruch 21, dadurch gekennzeichnet, daß eine zweite (51-2) der zweiten Suchtabelleneinheiten (51-1, 51-2, . . .) an den zugeordneten Schieber (53-1) anschließbar ist, wobei der zugeordnete Schieber an den zugeordneten Signalspeicher (52-1) und die eine zweite Suchtabelleneinheit (51-2) angeschlossen ist, wobei eine zweite Such­ tabelleneinheit ferner Steuerbits erzeugt, die zu der Länge der kodierten Einheit des ersten vollständigen Kodeworts korrespondieren, wobei der zugeordnete Signalspeicher an den ersten Abschnitt des Schiebers parallel zu der ersten Such­ tabelleneinheit angeschlossen ist, der zugeordnete Schieber die Daten in dem Signalspeicher in Abhängigkeit zu den Steuerbits von der einen zweiten Such­ tabelleneinheit verschiebt, so daß die zweite Suchtabelleneinheit ein Belegungsbit korrespondierend zu einem zweiten vollständigen Kodewort in dem ersten Ab­ schnitt des Schiebers erzeugt.

23. Dekodierer für Einheiten von Huffman-kodierten Daten nach einem der Ansprüche 16 bis 22, worin jede der zweiten Suchtabelleneinheiten (51-1, 51-2, . . .) ein Paar von dritten Suchtabelleneinheiten (51A, 51B) aufweist, wobei eine erste (51A) dieses Paares Belegungsbits erzeugt und eine zweite (51B) dieses Paares Steuersignale für sequentielle Suchoperationen durch die zweiten Suchta­ belleneinheiten erzeugt.

24. Dekodierer für Einheiten von Huffman-kodierten Daten nach Anspruch 23, dadurch gekennzeichnet, daß die Mehrzahl von zweiten Suchtabelleneinheiten durch eine Mehrzahl von Signalspeichern und Schiebern angeschlossen sind, wobei ein Signalspeicher und ein Schieber jedem der zweiten Speichereinheiten bis auf einen zugeordnet sind, wobei die eine zweite Suchtabelleneinheit folgendes aufweist:
eine erste (51A) eines Paares von dritten Suchtabelleneinheiten (51A, 51B), die an den ersten Abschnitt des Schiebers parallel zu dem ersten Speicher ange­ schlossen ist, wobei die erste (51A) des Paares ein Belegungsbit korrespondierend zu einem ersten vollständigen Kodewort in dem ersten Abschnitt des Schiebers erzeugt; und
eine zweite (51B) des Paares von dritten Suchtabelleneinheiten, die auf das erzeugte Belegungsbit anspricht, um ein Steuersignal zu erzeugen, das eine Länge eines ersten vollständigen Kodeworts anzeigt.

25. Dekodierer nach Anspruch 1, gekennzeichnet durch:
eine Mehrzahl von Speichereinheiten (60A, 60B, 60C), wobei die Speicher­ einheiten an eine Untermenge von den Zellen des Schiebers (Fig. 12A) ange­ schlossen sind, um ein Belegungsbit, das zu einem Kodewort in der Untermenge von Zellen korrespondiert, und Steuerbits zu erzeugen, die zu einer Gesamtzahl von den Bits korrespondieren, die einer kodierten Dateneinheit des Kodeworts zuzuordnen sind, wobei jede der Speichereinheiten an die Zellen angeschlossen ist, um überlappende Anschlüsse zu den Zellen zu bilden; und
Mitteln (61), die an die Zellen angeschlossen sind, um eine der Speicher­ einheiten (60A, 60B, 60C) für die Belegungsbits in Abhängigkeit zu den Bits in den Zellen auszuwählen.

26. Dekodierer nach Anspruch 25, worin der Eingang zumindest so breit ist, wie das breiteste Huffman-Kodewort, das an die Adresseneingangsanschlüsse der Mehrzahl von Speichereinheiten anschließbar ist.

27. Dekodierer nach einem der Ansprüche 25 oder 26, dadurch gekennzeich­ net, daß eine der Speichereinheiten dazu in der Lage ist, eine Mehrzahl von Belegungsbits gleichzeitig korrespondierend zu der Mehrzahl von Kodeworten in der Untermenge von angeschlossenen Zellen zu erzeugen.

28. Dekodierer nach Anspruch 27, dadurch gekennzeichnet, daß die eine Speichereinheit an eine Untermenge von Zellen angeschlossen ist, die die am frühesten empfangenen bzw. entgegengenommenen Bits hält.

29. Dekodierer nach einem der Ansprüche 25 bis 28, dadurch gekennzeichnet, daß die Zellen 0-15 numeriert, sind und die Mehrzahl von Speichereinheiten drei Speichereinheiten aufweisen, eine erste Speichereinheit, die an Zellen 0-7 ange­ schlossen ist, eine zweite Speichereinheit, die an Zellen 4-11 angeschlossen ist und eine dritte Speichereinheit, die an Zellen 8-15 angeschlossen ist.

30. Dekodierer nach Anspruch 29, dadurch gekennzeichnet, daß das Bele­ gungsbit mittels eines kanonischen Huffman-Kodes kodierbar ist.

31. Dekodierer nach Anspruch 30, dadurch gekennzeichnet, daß die Auswähl­ einrichtung auf die Lage einmaliger Präfix-Bits in den Zellen anspricht.

32. Dekodierer nach Anspruch 31, dadurch gekennzeichnet, daß die Auswähl­ einrichtung auf die Lage von aufeinanderfolgenden Bits der logischen "Einsen" in den Zellen anspricht.

33. Dekodierer nach Anspruch 32, dadurch gekennzeichnet, daß die Auswähl­ einrichtung die dritte Speichereinheit über die Bestimmung auswählt, daß Zellen 0-7 logische "Einsen" enthalten; falls nicht, wählt die Auswahleinheit die zweite Speichereinheit über die Bestimmung, daß Zellen 0-3 logische "Einsen" enthalten; ansonsten wählt sie die erste Speichereinheit.

34. Dekodierer nach Anspruch 31, worin die Auswähleinrichtung auf den Platz bzw. die Anordnung von nacheinander folgenden Bits der logischen "Nullen" in den Zellen anspricht.

35. Dekodierer nach Anspruch 32 oder 34, dadurch gekennzeichnet, daß die Auswähleinrichtung die dritte Speichereinheit über die Bestimmung auswählt, daß Zellen 0-7 logische "Nullen" enthalten; falls nicht, sie die zweite Speichereinheit über die Bestimmung auswählt, daß Zellen 0-3 logische "Nullen" enthalten; ansonsten sie die erste Speichereinheit auswählt.

36. Dekodierer nach einem der Ansprüche 25 bis 35, dadurch gekennzeichnet, daß die Daten digitale Transformationskoeffizienten und Lauflängen zwischen Transformationskoeffizienten, die nicht Null sind, aufweist, wobei die Speicher­ einheiten digitale Bilddaten erzeugen, die die Länge einer Einheit von kodierten Datenbits aufweisen, wobei die Länge den digitalen Transformationskoeffizienten zuzuordnen ist, und die Länge der Mantissen-Bits aufweist.

37. Dekodierer nach Anspruch 36, dadurch gekennzeichnet, daß jede der Speichereinheiten 13 Ausgangsanschlüsse aufweist.

38. Dekodierer nach Anspruch 37, dadurch gekennzeichnet, daß fünf der Ausgangsanschlüsse die Länge der kodierten Datenbits tragen, vier Anschlüsse Null-Lauf-Länge tragen, die den digitalen Transformationskoeffizienten zugeord­ net sind, und vier Anschlüsse die Länge der Mantissen-Bits tragen.

39. Verfahren zum Dekodieren von Huffman-kodierten Dateneinheiten in einem Bitstrom bei einem Dekodierer nach Anspruch 1, gekennzeichnet durch die folgenden Schritte:
ein Satz von Bits von den kodierten Dateneinheiten wird an den Eingangs­ anschlüssen einer Speichereinheit (30) zur Verfügung gestellt, die dazu in der Lage ist, simultan eine Mehrzahl von Belegungsbits aus den Kodeworten der Bits und eine Gesamtzahl von Bits der Dateneinheiten zu erzeugen, wobei die Bele­ gungsbits von den Kodeworten erzeugt werden; und
die Bits in dem Bitstrom werden über die Gesamtzahl der gespeicherten Bits verschoben, um einen nächsten Satz von Bits an den Eingangsanschlüssen der Speichereinheit für einen nachfolgenden Dekodierungszyklus zur Verfügung zu stellen.

40. Verfahren nach Anspruch 39, dadurch gekennzeichnet, daß das Verfahren die folgenden Schritte enthält:
eine Mehrzahl von Sätzen von Bits der kodierten Dateneinheiten an Ein­ gangsanschlüssen einer Mehrzahl von Suchtabelleneinheiten (40) werden jeweils gleichzeitig zur Verfügung gestellt;
ein Belegungsbit wird von jeder Suchtabelleneinheit in Abhängigkeit zu einem jeweiligen Satz von Bits an den Eingangsanschlüssen von den Suchtabellen­ einheiten gleichzeitig erzeugt;
eine Gesamtzahl der Bits der Dateneinheiten, die Belegungsbits aus Kode­ worten in dem Satz von Bits erzeugt haben, wird bestimmt; und
die Bits in dem Bitstrom werden um die Gesamtzahl von gespeicherten Bits verschoben, um eine Mehrzahl von nächsten Sätzen von Bits an den Eingangs­ anschlüssen der Suchtabelleneinheiten für einen nachfolgenden Dekodierungs­ zyklus zur Verfügung zu stellen.

41. Verfahren nach Anspruch 39, dadurch gekennzeichnet, daß das Verfahren folgendes enthält:
eine Mehrzahl von Sätzen von Bits der kodierten Dateneinheiten werden an Eingangsanschlüssen einer Mehrzahl von jeweiligen Suchtabelleneinheiten (40) gleichzeitig zur Verfügung gestellt, wobei jeder Satz von Bits in dem Bitstrom zu anderen Sätzen versetzt bzw. gestaffelt ist;
von jeder Suchtabelleneinheit wird gleichzeitig ein Belegungsbit erzeugt, in Abhängigkeit zu einem jeweiligen Satz von Bits an den Eingangsanschlüssen der Suchtabelleneinheit; und
die Bits in dem Bitstrom werden über eine vorbestimmte Zahl von gespei­ cherten Bits verschoben, um eine Mehrzahl von nächsten Sätzen von Bits an den Eingangsanschlüssen der Suchtabelleneinheiten für einen nachfolgenden Deko­ dierungszyklus zur Verfügung zu stellen.

42. Verfahren nach Anspruch 41, dadurch gekennzeichnet, daß die vorbe­ stimmte Zahl von Bits zu dem größten Versatzbetrag zwischen den Sätzen von Bits korrespondiert.

43. Verfahren nach Anspruch 41, ferner dadurch gekennzeichnet, daß die Gültigkeit jedes Belegungsbits von jeder Suchtabelle bestimmt wird;
daß ein Fehlersignal in Abhängigkeit zu der Bestimmung eines ungültigen Belegungsbits von einer Suchtabelle in Abhängigkeit zu dem Satz erzeugt wird; und
die Bits in dem Bitstrom werden zurückgeschoben, so daß der Satz von Bits an der Suchtabelle an Eingangsanschlüssen einer anderen Suchtabelle zur Verfügung gestellt wird, die dazu in der Lage ist, von dem Satz von Bits ein gültiges Belegungsbit zu erzeugen.

44. Verfahren nach Anspruch 39, gekennzeichnet durch die folgenden Schritte:
ein Satz von Bits von den kodierten Dateneinheiten an Eingangsanschlüssen einer ersten Suchtabelleneinheit zum Erzeugen einer Gesamtzahl von Bits der Dateneinheiten, die Kodeworte in dem Satz von Bits aufweisen, zur Verfügung gestellt;
Belegungsbits werden aus Kodeworten in dem Satz von Bits in einer Hauptleitung bzw. Verbindungsleitung erzeugt; und
die Bits in dem Bitstrom werden über die Gesamtzahl von gespeicherten Bits verschoben, um einen neuen Satz von Bits an den Eingangsanschlüssen der Speichereinheit für einen nachfolgenden Dekodierungszyklus zur Verfügung zu stellen.

45. Verfahren nach Anspruch 44, dadurch gekennzeichnet, daß der erzeugende Schritt aufweist:
der Satz von Bits wird an Eingangsanschlüssen einer zweiten Suchtabellen­ einheit zur Verfügung gestellt, um ein Belegungsbit bzw. Token von einem Kodewort in dem Satz von Bits und eine Gesamtzahl von Bits der Dateneinheit, die das Kodewort aufweist, zu erzeugen;
der Satz von Bits wird über die Gesamtzahl von gespeicherten Bits ver­ schoben;
der verschobene Satz von Bits wird an Eingangsanschlüssen einer dritten Suchtabelleneinheit zur Verfügung gestellt, um ein Belegungsbit von einem Kodewort in dem verschobenen Satz von Bits und eine Gesamtzahl von Bits der Dateneinheit, die das Kodewort aufweist, zu erzeugen; und
die obigen Schritte werden eine vorbestimmte Anzahl von Malen wie­ derholt, wobei die vorbestimmte Anzahl zu einer Anzahl von Suchtabellenein­ heiten korrespondiert.

46. Verfahren nach Anspruch 45, dadurch gekennzeichnet, daß die Huffman- kodierten Dateneinheiten JPEG-Daten aufweisen und die zweite Suchtabellen­ einheit nur auf DC-Kodeworte anspricht und die dritte Such- bzw. Nachprüftabel­ le nur auf AC-Kodeworte anspricht.

47. Verfahren nach Anspruch 39, gekennzeichnet durch die folgenden Schritte:
eine Mehrzahl von Suchtabellen wird zur Verfügung gestellt;
jede der Suchtabellen wird an eine Untermenge der Bit-Schieberzellen angeschlossen, wobei jede Untermenge mit einer anderen überlappt;
Belegungsbits werden gleichzeitig durch jede der Suchtabellen in Abhängig­ keit zu Bits in den Untermengen der angeschlossenen Zellen erzeugt; und
gültige Belegungsbits werden von den gleichzeitig erzeugten Belegungsbits ausgewählt.