DE4314741A1

DE4314741A1 - Dekodierer-Architektur nach Huffman für eine höhere Betriebsgeschwindigkeit und reduzierten Speicherbedarf

Info

Publication number: DE4314741A1
Application number: DE4314741A
Authority: DE
Inventors: James Allen; Martin Boliek; Edward L Schwartz; David Bednash
Original assignee: Ricoh Co Ltd
Current assignee: Ricoh Co Ltd
Priority date: 1992-07-07
Filing date: 1993-05-04
Publication date: 1994-02-10
Anticipated expiration: 2013-05-05
Also published as: FR2693607A1; US5325092A; JPH0685689A; DE4314741C2; FR2693607B1; GB9308583D0; GB2269070A; GB2269070B; JP3224164B2

Description

Die vorliegende Erfindung betrifft Dekodierer zum Dekompri mieren von Huffman-kodierten Daten und insbesondere die Architektur bzw. Konstruktion von Hochgeschwindigkeitsde kodierern für nach Huffman kodierte Daten. Beim Huffman- Kodieren werden Einheiten von Originaldaten zu kodierten Einheiten komprimiert, die aus Kodeworten mit variierenden Längen und optional bzw. gegebenenfalls aus nicht nach Huffman kodierten Worten bestehen bzw. diese aufweisen. Die Kodeworte sind derart ausgewählt, daß die am häufigsten auftretenden Einheiten von Originaldaten bevorzugt die kür zeste Länge aufweisen, nämlich die kürzeste Anzahl von Bits und die am wenigsten häufig auftretenden Einheiten von Ori ginaldaten weisen die größten Kodeworte auf. In dieser Wei se werden die Originaldaten zu kodierten Daten komprimiert. Dieses ist eine allgemeine Beschreibung der Kodierungstech niken nach Huffman und natürlich kann die Auswahl und Er zeugung von Kodes nach Huffman für bestimmte Anwendungen mit wesentlich größerer Präzision ausgedrückt werden.

Die Anwendung der Kodierung nach Huffman wird typischerwei se verwendet, wenn eine große Anzahl von Daten vorhanden sind, welche verarbeitet oder übertragen werden müssen, wie etwa bei der digitalen Bildverarbeitung, z. B. Farbbilder, die nach dem JPEG-Standard (Joint Photographic Experts and Group) und die Standard-Kodierung nach Huffman bewältigen typischerweise eine große Anzahl von Dateneinheiten. Die Kodierung nach Huffman wird in gegenwärtigen und zukünfti gen digitalen Videoverarbeitungsstandards zu finden sein.

Von diesen Standards wird der zuvor aufgezeigte JPEG-Stan dard umfaßt, welcher ein Standard auch für Bilder ist. Exi stierende und zukünftige Standards für Bewegungs-Videosy steme, wie etwa H.261, einem CCITT-Video-Telekonferenz- Standard, und dem Motion Picture Experts Group (MPEG) I, weisen Kodierungssysteme auf, welche dem JPEG-Standard sehr ähnlich sind. Folglich sind die MPEG-Standards auf die auf kommenden hochgenauen Televisionstechnologien (HDTV) bezo gen. 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 De kodierung der Huffman-kodierten Einheiten natürlich durch geführt werden. Bei der Kodierung von jeder kodierten Ein heit 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 Originaldateneinheit), um als Steuerinformation verwendet zu werden, um die kodierte Ein heit in die Originaldateneinheit umzustellen oder zu de komprimieren.

Ein herausragendes und grundsätzliches Problem ist bei der Dekodierungstätigkeit bzw. -operation entdeckt worden, wel che jedes Belegungsbit bzw. Token aus einem Kodewort er zeugt. Das Problem erscheint, wenn die Hochgeschwindig keitsdekodierung der kodierten Einheiten gefordert wird. Beim Dekodieren eines Stromes von Huffman-kodierten Einhei ten in einem üblichen Huffman-Dekodierer enthält jede Ein heit ein Kodewort und optionelle Nicht-Kodeworte mit vari ierender Länge, welche bei der Hochgeschwindigkeitsdekodie rung Schwierigkeiten bereiten.

Diese Schwierigkeit beim Dekodieren Huffman-kodierter Daten bei hoher Geschwindigkeit bringt eine ernsthafte Behinde rung 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 enthal ten werden. Eine Abschätzung der HDTV-Erfordernisse führt zu der Verarbeitung von Bildelement-Komponenten bei 100 Millionen Dateneinheiten pro Sekunde. Um dieses Problem zu lösen, stellt die vorliegende Erfindung neue Dekodie rungs-Architekturen bzw. -Computer-Gesamtausstattungen zur Verfügung, bei welchen kodierte Einheiten parallel deko diert werden.

Verschiedene Ausführungsformen von Dekodierer-Architekturen nach Huffman werden vorgestellt. Diese Dekodierer-Architek turen, die sämtlich zu Hochgeschwindigkeitsbetätigungen in der Lage sind, verwenden unterschiedliche Mengen an Spei cher und Logik. Das Gleichgewicht zwischen Speicher und Lo gik weist verschiedene Platz /Geschwindigkeits-Kompromisse in bestimmten Technologien auf, die durch einen Konstruk teur von integrierten Schaltkreisen ausgeführt werden müs sen. Folglich bietet die vorliegende Erfindung Hochge schwindigkeits-Alternativen für die meisten, wenn nicht für alle der spezifischen Anwendungen, von Dekodierern nach Huffman. Die vorliegende Erfindung ermöglicht die Auswahl der optimalen Architektur für Dekodierer.

Die oben aufgezeigten Probleme bzw. Aufgaben werden gemäß der vorliegenden Erfindung durch einen Dekodierer nach einem der Patentansprüche 1 oder 6, einen Dekodierer nach Patentanspruch 19, Dekodierer-Empfangseinrichtungen nach Patentanspruch 29 und Verfahren zum Dekodieren nach einem der Ansprüche 43, 44, 45, 48 oder 51 gelöst.

Vorteilhafte Ausgestaltungen bzw. Verfahrensvarianten der Gegenstände bzw. Verfahren nach den unabhängigen Ansprüchen gehen aus den Unteransprüchen hervor.

Die vorliegende Erfindung stellt Dekodierer-Architekturen nach Huffman zur Verfügung, bei welchen im Mittel mehr als ein Kodewort in einem Strom von Huffman-kodierten Datenein heiten in mehr als ein Belegungsbit bzw. Token in einer einzelnen Dekodierungsoperation dekodiert werden können.

Eine Ausführungsform gemäß der vorliegenden Erfindung weist eine Dekodierungs-Architektur mit breiter Tabelle auf. Ein heiten aus Huffman-kodierten Daten werden über eine Bit- Verschiebungseinrichtung empfangen. Eine große Speicherein richtung, die als große Tabelle tätig wird, wird mit dem Bit-Verschieber bzw. -Umleger verbunden. Die Speicherein richtung erzeugt gleichzeitig Belegungsbits bzw. Tokens und Steuerbits, die mit der Länge der Eingaben der kompletten Kodeworte korrespondieren. Diese Steuerbits sind eine Rück kopplung für den Bit-Schieber bzw. -Umleger, welcher die Gesamtlänge der kodierten Einheiten für die nächste Deko dierungsoperation verschiebt. Folglich wird im Mittel mehr als ein Belegungsbit pro Such- oder Überprüfungs- bzw. Nachschauzyklus erhalten.

Eine andere Ausführungsform gemäß der vorliegenden Erfin dung stellt eine versetzte bzw. gestaffelte Dekodierer-Ar chitektur zur Verfügung. Wie in dem Falle der Architektur mit breiter Tabelle, hält ein Bit-Schieber die Bits der Huffman-kodierten Daten. Mehrere Tabelleneinheiten sind mit dem Bit-(Ver)Schieber verbunden, jede Einheit mit einem un terschiedlichen Versatz. Jede Tabelle sieht bzw. sucht nach einem anderen Teil der kodierten Eingabe, ob sie ein gülti ges Belegungsbit erzeugt oder nicht. Eine kombinatorische Logik, die mit den Tabelleneinheiten verbunden ist, be stimmt, welche der Einheiten gültige Belegungsbits erzeugt hat. Wiederum wird im Mittel mehr als ein Belegungsbit pro Prüfungs- bzw. Suchzyklus erhalten.

Eine Abwandlung dieser Ausführungsform stellt eine vorbe stimmte Anzahl von Bits zur Verfügung bzw. setzt diese voraus, die in dem Bit-Verschieber für jede Dekodierungs operation verschoben werden müssen. Das Dekodieren wird bei einer konstanten Rate durchgeführt. Die Gültigkeit der Be legungsbits von der Tabelleneinheit wird in einer in einer Hauptleitung vorzugsweise hintereinander angeordneten bzw. in einer verbundenen Weise bestimmt. Eine zweite Abwandlung der abgestuften Tabellendekoder-Architektur weist eine oder mehrere Tabellen nach der anfänglichen Position auf, die in der Lage ist, nur eine vorausgewählte Untermenge von Kode worten zu dekodieren. Diese Kodeworte können die am wahr scheinlichsten in der bestimmten Anwendung auftretenden sein. Dieses reduziert die benötigte Speichermenge, weil nur eine Tabelle, die erste, erforderlich ist, um zu sämt lichen Belegungsbit-Suchoperationen in der Lage zu sein.

Eine andere Ausführungsform gemäß der vorliegenden Erfin dung ist eine Architektur für einen Steuerspeicher. Ein Bit-Verschieber empfängt, wie zuvor beschrieben, die Ein heiten von Huffman-kodierten Daten. Ein Steuerspeicher ist mit dem Bit-Verschieber verbunden und enthält nur die Steuerbits, die zu den Gesamtlängen der kodierten Einheiten korrespondieren, die an den Adressenanschlüssen vollständi ge Kodeworte aufweisen. Diese Steuerbits werden zu den Bit- Verschiebern zurückgekoppelt, welche die kodierten Daten um die gesamte Länge der kodierten Daten für die nächste Deko dierungsoperation verschieben. Das Dekodieren der Kodeworte in den kodierten Einheiten wird sequentiell durch mehrere Tabelleneinheiten durchgeführt, wobei jede Einheit eine Ta belle für Belegungsbits aus Kodeworten aufweist, die an eine Hauptleitung angeschlossen ist. Ein Signalspeicher und ein Verschieber sind miteinander den Tabelleneinheiten für den Hauptleitungsanschluß (pipeline connection) zugeordnet.

Eine Abwandlung dieser Dekodierer-Architektur für einen Steuerspeicher, der an JPEG-Daten angepaßt ist, erfordert, daß die erste Tabelle nur eine Untermenge von möglichen Ko deworten dekodiert, und zwar jener für die DC-Koeffizien ten. Die zurückbleibenden Tabellen dekodieren nur eine Un termenge der möglichen Kodeworte, und zwar jene der AC-Koeffizienten. Folglich wird der Speicherplatz minimiert.

Die vorliegende Erfindung stellt auch eine effiziente Spei cherorganisation bzw. -anordnung für einen Dekodierer nach Huffman zur Verfügung. Die Organisation verwendet mehrere kleinere Speichereinheiten. Jede der Speichereinheiten wird in einer überlappenden Weise adressiert. Eine kombinatori sche Logik wählt die Speichereinheit für die dekodierten digitalen Bilddaten aus. Die Menge an Speicherplatz, die erforderlich ist, um die Huffman-kodierten Daten zu deko dieren, wird mit dieser überlappenden Verbindung von sepa raten Speichereinheiten wesentlich reduziert.

Die vorliegende Erfindung wird nunmehr unter Bezugnahme auf die Figuren näher erläutert, wobei weitere Vorteile und Merkmale gemäß der vorliegenden Erfindung offenbart werden. Dabei wird ein detailliertes Verständnis durch sorgfältiges Lesen der nachfolgenden detaillierten Beschreibung von be vorzugten Ausführungsformen unter Bezugnahme auf die im folgenden erläuterten Zeichnungen ermöglicht wurden.

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. Kro 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 gelangen, 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 Zellen 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 Lange 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 eine 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 sämtliche 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 Mulitplexer-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, die 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 Aus 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 60A-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 durch den JPEG-Standard verwendet werden, 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.

Claims

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, gekennzeichnet durch eine Bit-Schiebereinheit, die an den Eingangsanschluß angeschlossen ist, weist mehrere Zellen auf, wobei jede Zelle ein Bit der entgegengenommenen Daten hält, und eine Speichereinheit, die mehrere Eingangsadressenan schlüsse und Ausgangsanschlüsse aufweist, wobei jeder der Adressenanschlüsse an eine der Schieberegisterzellen ange schlossen ist, wobei die Speichereinheit an den Ausgangsan schlüssen simultan bzw. gleichzeitig Belegungsbits von je dem vollständigen Kodewort an den Eingangsadressenterminals erzeugt, wobei die Speichereinheit Steuersignale erzeugt, die zu der Gesamtlänge der kodierten Einheiten korrespon dieren, die vollständige Kodeworte an den Eingangsadressen anschlüssen aufweisen, so daß die kodierten Daten durch das Schieberegister geschoben werden können, wodurch die kodierten Dateneinheiten gleichzeitig de kodierbar sind und das Schieberegister für einen nächsten Dekodierungszyklus bereit ist.

2. Dekodierer nach Anspruch 1, dadurch gekennzeichnet, daß die Speichereinheit zumindest so viele Eingangsan schlü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 dazu in der Lage ist, Belegungsbits bzw. Tokens für sämtliche Kodeworte nur für eine Untermenge der Eingangsadressenterminals zu erzeu gen, wodurch die Größe der Speichereinheit reduzierbar ist.

4. Dekodierer nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, daß die Speichereinheit dazu in der Lage ist, Belegungsbits für sämtliche Kodeworte aber nur für ein zuerst in der Bit-Schiebereinheit positioniertes Kodewort zu erzeugen.

5. Dekodierer nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß die Speichereinheit dazu in der Lage ist, Belegungsbits für eine Untermenge von Kodeworten an Plätzen, die nicht mit dem zuerst positionierten Kodewort in der Bit-Schiebereinheit übereinstimmen, zu erzeugen, wo bei die Untermenge der Kodeworte die am häufigsten auftre tende ist.

6. Dekodierer, der Einheiten von Huffman-kodierten Daten empfängt, insbesondere nach einem der Ansprüche 1 bis 5, wobei jede Einheit ein Kodewort in der Form von Bits auf weist, wobei der Dekodierer gekennzeichnet ist durch:
eine Bit-Schiebereinheit, die die Bits der empfangenen bzw. entgegengenommenen Daten in der Ordnung des Eingangs hält;
mehrere Such- bzw. Nachprüftabelleneinheiten, die an die Bit-Schiebereinheit so angeschlossen sind, daß jede der Such- bzw. Nachprüftabelleneinheiten gleichzeitig Bele gungsbits erzeugt, die einer Mehrzahl von in der Ordnung des Eingangs versetzten Bits entspricht, und
eine Logikeinrichtung, die an die Such- bzw. Nachprüf tabelleneinheiten angeschlossen ist, um zu bestimmen, wel che der Such- bzw. Nachprüftabelleneinheiten gültige Bele gungsbits erzeugt hat bzw. erzeugt,
wodurch der Dekodierer in einem Zyklus eine oder meh rere Einheiten der empfangenen bzw. entgegengenommenen Da ten dekodiert, die Bits von kompletten Kodeworten aufwei sen, die eine Such- bzw. Nachprüftabelleneinheit dazu ver anlassen, ein Belegungsbit zu erzeugen.

7. Dekodierer nach Anspruch 6, dadurch gekennzeichnet, daß die Logikeinrichtung zusätzlich die gesamte Anzahl von Bits bestimmt, die durch die Bit-Schiebereinheit 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 Such- bzw. Nach prüftabelleneinheit zu der Bit-Schiebereinheit um ein Bit versetzt ist.

9. Dekodierer nach einem der Ansprüche 6 bis 8, dadurch gekennzeichnet, daß ein Anschluß von jeder Such- bzw. Nach prüftabelleneinheit zu der Bit-Schiebereinheit 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 bzw. dazu kor respondieren und die Such- bzw. Nachprüftabelleneinheiten eine Mehrzahl von Belegungsbits parallel erzeugen, ein Be legungsbit für jeden Huffman-Kode.

11. Dekodierer nach einem der Ansprüche 6 bis 10, dadurch gekennzeichnet, daß die Mehrzahl von Such- bzw. Nachprüfta belleneinheiten vier Belegungsbits parallel erzeugt, je weils 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ß die mehreren der Such- bzw. Nachprüf tabelleneinheiten einer erste Einheit, die an eine Anfangs position der Bit-Schiebereinheit angeschlossen ist, und zu mindest eine zweite Einheit aufweisen, die an die Bit- Schiebereinheit zu der Anfangsposition versetzt angeschlos sen ist, wobei die erste Einheit Belegungsbits für alle möglichen Kodeworte erzeugt, und die zweite Einheit Bele gungsbits für eine Untermenge von allen möglichen Kodewor ten erzeugt.

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

14. Dekodierer nach einem der Ansprüche 6 bis 13, dadurch gekennzeichnet, daß Einheiten von Huffman-kodierten Daten einer Mehrzahl von Huffman-Kodes entsprechen bzw. dazu kor respondieren und die Such- bzw. Nachprüftabelleneinheiten eine Mehrzahl von Belegungsbits parallel erzeugen, ein Be legungsbit für jeden Huffman-Kode.

15. Dekodierer nach Anspruch 14, dadurch gekennzeichnet, daß die Mehrzahl von Such- bzw. Nachprüftabelleneinheiten vier Belegungsbits parallel erzeugt, ein Belegungsbit je weils für AC-Bildleuchtdichte-, DC-Bildleuchtdichte-, AC-Farbton- und DC-Farbton-Huffman-Kodes.

16. Dekodierer nach einem der Ansprüche 6 bis 15, dadurch gekennzeichnet, daß eine Verbindung von jeder Such- bzw. Nachprüftabelleneinheit zu der Bit-Schiebereinheit um ein Bit versetzbar ist.

17. Dekodierer nach Anspruch 13, dadurch gekennzeichnet, daß die mehreren der Such- bzw. Nachprüftabelleneinheiten eine erste Einheit, die an eine Anfangsposition der Bit- Schiebereinheit angeschlossen ist, und zumindest eine zweite Einheit aufweisen, die zu der Anfangsposition an die Bit-Schiebereinheit versetzt angeschlossen ist, wobei die erste Einheit Belegungsbits für alle möglichen Kodeworte erzeugt, und die zweite Einheit Belegungsbits für eine Un termenge von allen möglichen Kodeworten erzeugt.

18. Dekodierer nach Anspruch 17, dadurch gekennzeichnet, daß dieser auf einen durch die zweite Einheit in Abhängig keit zu einem Satz von Bits in dem Bit-Schieber erzeugten Belegungsbit anspricht, wobei die Bit-Schiebereinheit den Satz von Bits verschiebt, so daß die erste Einheit ein Be legungsbit in Abhängigkeit dazu erzeugt.

19. Dekodierer für Einheiten von Huffman-kodierten Daten, insbesondere nach einem der Ansprüche 1 bis 18, wobei jede Einheit Kodeworte aufweist und der Dekodierer einen Ein gangsanschluß bzw. Eingangsanschlüsse zum Empfangen bzw. zum Entgegennehmen der Daten aufweist, gekennzeichnet durch
eine Bit-Schiebereinheit, die die entgegengenommenen bzw. empfangenen Daten in der Eingangsordnung hält;
eine erste Such- bzw. Nachprüftabelleneinheit, die an zumindest einen ersten Abschnitt der Bit-Schiebereinheit angeschlossen ist, um Steuersignale zum Schieben des Regi sters in Abhängigkeit zu der gesamten Länge der kodierten Einheiten zu erzeugen, die vollständige Kodeworte in dem ersten Abschnitt der Bit-Schiebereinheit aufweisen; und
eine Mehrzahl bzw. mehrere von zweiten Such- bzw. Nachprüftabelleneinheiten, die an den ersten Abschnitt der Bit-Schiebereinheit in einer Hauptleitung bzw. einer Lei tung angeordnet bzw. angeschlossen sind; die zweiten Such- bzw. Nachprüftabelleneinheiten erzeugen sequentiell Bele gungsbits bzw. Tokens abhängig zu den vollständigen Kode worten in dem ersten Abschnitt;
wodurch die Bit-Schiebereinheit für eine nachfolgende Dekodieroperation ohne das Erfordernis einer Dekodierung eines Kodeworts der empfangenen bzw. entgegengenommenen Da ten verschiebbar ist bzw. verschieben kann.

20. Dekodierer für Einheiten von Huffman-kodierten Daten nach Anspruch 19, dadurch gekennzeichnet, daß die Mehrzahl von zweiten Such- bzw. Nachprüftabelleneinheiten eine erste Einheit zum Dekodieren eines ersten Kodeworts in dem Bit- Schieber und zumindest eine zweite Einheit aufweist, um ein Kodewort, das dem ersten Kodewort in dem Bit-Schieber nach folgt, zu dekodieren, wobei die zweite Einheit dazu in der Lage ist, nur eine Untermenge von Kodeworten, die durch die erste Einheit dekodiert werden können, zu dekodieren.

21. Dekodierer für Einheiten von Huffman-kodierten Daten nach einem der Ansprüche 19 oder 20, dadurch gekennzeich net, daß die Huffman-kodierten Daten JPEG-Daten aufweisen und die erste Einheit dazu in der Lage ist, Belegungsbits für DC-Koeffizienten zu erzeugen.

22. Dekodierer für Einheiten von Huffman-kodierten Daten nach einem der Ansprüche 19 bis 21, dadurch gekennzeichnet, daß die verbleibenden zweiten Such- bzw. Nachprüftabellen einheiten dazu in der Lage sind, Belegungsbits für AC-Koef fizienten zu erzeugen.

23. Dekodierer für Einheiten von Huffman-kodierten Daten nach einem der Ansprüche 19 bis 22, dadurch gekennzeichnet, daß die erste Einheit dazu in der Lage ist, alle Kodeworte in die bzw. in den Huffman-kodierten Daten zu dekodieren.

24. Dekodierer für Einheiten von Huffman-kodierten Daten nach einem der Ansprüche 19 bis 23, dadurch gekennzeichnet, daß die Mehrzahl von zweiten Such- bzw. Nachprüftabellen einheiten über eine Mehrzahl von Signalspeichern und Schiebern angeschlossen sind, wobei ein Signalspeicher und ein Schieber jedem der zweiten Speichereinheiten mit Aus nahme von einem zuzuordnen sind, wobei die eine zweite Such- bzw. Nachprüftabelleneinheit an den ersten Abschnitt der Bit-Schiebereinheit parallel zu dem ersten Speicher an geschlossen ist, wobei die eine zweite Such- bzw. Nachprüf tabelleneinheit ein Belegungsbit erzeugt, das zu einem er sten vollständigen Kodewort in dem ersten Abschnitt der Bit-Schiebereinheit korrespondiert.

25. Dekodierer für Einheiten von Huffman-kodierten Daten nach Anspruch 24, dadurch gekennzeichnet, daß ein zweiter der zweiten Such- bzw. Nachprüftabelleneinheiten an den zu geordneten Schieber anschließbar ist, wobei der zugeordnete Schieber, der an den zugeordneten Signalspeicher und die eine zweite Such- bzw. Nachprüftabelleneinheit angeschlos sen ist, wobei eine zweite Such- bzw. Nachprüftabellenein heit ferner Steuerbits erzeugt, die zu der Länge der ko dierten Einheit des ersten vollständigen Kodeworts korre spondiert, wobei der zugeordnete Signalspeicher an den er sten Abschnitt der Bit-Schiebereinheit parallel zu der er sten Such- bzw. Nachprüftabelle angeschlossen ist, der zu geordnete Schieber die Daten in dem Signalspeicher in Ab hängigkeit zu den Steuerbits von der einen zweiten Such- bzw. Nachprüftabelleneinheit verschiebt, so daß die zweite Such- bzw. Nachprüftabelleneinheit ein Belegungsbit korre spondierend zu einem zweiten vollständigen Kodewort in dem ersten Abschnitt der Bit-Schiebereinheit erzeugt.

26. Dekodierer für Einheiten von Huffman-kodierten Daten nach einem der Ansprüche 19 bis 25, worin jeder der zweiten Such- bzw. Nachprüftabelleneinheiten ein Paar von dritten Such- bzw. Nachprüftabelleneinheiten aufweist, wobei eine erste dieses Paars Belegungsbits erzeugt und eine zweite dieses Paars Steuersignale für sequentielle Such- bzw. Nachprüfoperationen durch die zweite Such- bzw. Nachprüf tabelleneinheit erzeugt.

27. Dekodierer für Einheiten von Huffman-kodierten Daten nach Anspruch 26, dadurch gekennzeichnet, daß die Mehrzahl von zweiten Such- bzw. Nachprüftabelleneinheiten 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 Such- bzw. Nachprüftabelleneinheit folgendes aufweist:
eine erste eines Paares von dritten Such- bzw. Nach prüftabelleneinheiten, die an den ersten Abschnitt der Bit- Schiebereinheit parallel zu dem ersten Speicher angeschlos sen ist, wobei die erste des Paars ein Belegungsbit korre spondierend zu einem ersten vollständigen Kodewort in dem ersten Abschnitt der Bit-Schiebereinheit erzeugt; und
eine zweite des Paares von dritten Such- bzw. Nach prüftabelleneinheiten, die auf das erzeugte Belegungsbit anspricht, um ein Steuersignal zu erzeugen, das eine Länge eines ersten vollständigen Kodeworts anzeigt.

28. Dekodierer für Einheiten von Huffman-kodierten Daten nach Anspruch 27, dadurch gekennzeichnet, daß eine zweite der zweiten Such- bzw. Nachprüftabelleneinheiten an den zu geordneten Schieber angeschlossen ist, wobei der zugeordne te Schieber an den zugeordneten Signalspeicher und die eine zweite Such- bzw. Nachprüftabelleneinheit angeschlossen ist, der zugeordnete Signalspeicher an den ersten Abschnitt der Bit-Schiebereinheit parallel zu der ersten Such- bzw. Nachprüftabelle angeschlossen ist, der zugeordnete Schieber die Daten in dem Signalspeicher in Abhängigkeit zu den Steuerbits von dem zweiten des Paares von dritten Such- bzw. Nachprüftabelleneinheiten verschiebt, so daß die zwei te Such- bzw. Nachprüftabelleneinheit ein Belegungsbit er zeugt, das zu einem zweiten vollständigen Kodewort in dem ersten Abschnitt der Bit-Schiebereinheit korrespondiert.

29. Huffman-Dekodierer, der Einheiten von Huffman-kodier ten Datenbits empfängt bzw. entgegennimmt, insbesondere nach einem der Ansprüche 1 bis 28, wobei jede Einheit ein Kodewort aufweist und die Bits in einer Mehrzahl von Zellen in einer Eingangsordnung hält, wobei jede der Zellen ein Bit hält, wobei der Dekodierer gekennzeichnet ist durch:
eine Mehrzahl von Speichereinheiten, wobei die Spei chereinheiten an eine Untermenge von den Zellen angeschlos sen sind, um ein Belegungsbit, das zu einem Kodewort in der Untermenge von Zellen korrespondiert, und Steuerbits zu er zeugen, die zu einer Gesamtzahl von den Bits korrespondie ren, die einer kodierten Dateneinheit des Kodeworts zuzu ordnen sind, wobei jede der Speichereinheiten an die Zellen angeschlossen ist, um überlappende Anschlüsse zu den Zellen zu bilden; und
Mitteln, die an die Zellen angeschlossen sind, um eine der Speichereinheiten für die Belegungsbits in Abhängigkeit zu den Bits in den Zellen auszuwählen;
wodurch die Menge an Speicherplatz, die erforderlich ist, um die Huffman-kodierten Daten zu dekodieren, wesent lich reduziert ist.

30. Dekodierer nach Anspruch 29, worin der Eingang zumin dest so breit ist, wie das breiteste Huffman-Kodewort, das an die Adresseneingangsanschlüsse der Mehrzahl von Spei chereinheiten anschließbar ist.

31. Dekodierer nach einem der Ansprüche 29 oder 30, da durch gekennzeichnet, daß eine der Speichereinheiten dazu in der Lage ist, eine Mehrzahl von Belegungsbits gleichzei tig korrespondierend zu der Mehrzahl von Kodeworten in der Untermenge von angeschlossenen Zellen zu erzeugen.

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

33. Dekodierer nach einem der Ansprüche 29 bis 32, dadurch gekennzeichnet, daß die Zellen (0-15) numeriert sind und die Mehrzahl von Speichereinheiten drei Speichereinheiten auf weisen, eine erste Speichereinheit, die an Zellen (0-7) ange schlossen ist, eine zweite Speichereinheit, die an Zellen (4-11) angeschlossen ist und eine dritte, insbesondere zwei te, Speichereinheit, die an Zellen (8-15) angeschlossen ist.

34. Dekodierer nach Anspruch 33, dadurch gekennzeichnet, daß das Belegungsbit mittels eines kanonischen Huffman-Ko des kodierbar ist.

35. Dekodierer nach Anspruch 34, dadurch gekennzeichnet, daß die Auswähleinrichtung auf den Platz bzw. die Anordnung einheitlicher Präfix-Bits in den Zellen anspricht.

36. Dekodierer nach Anspruch 35, dadurch gekennzeichnet, daß die Auswähleinrichtung auf den Platz bzw. die Anordnung von aufeinanderfolgenden Bits der logischen "Einsen" in den Zellen anspricht.

37. Dekodierer nach Anspruch 36, dadurch gekennzeichnet, daß die Auswähleinrichtung die dritte Speichereinheit über die Bestimmung auswählt, daß Zellen (0-7) logische "Einsen" enthalten; falls nicht, wählt sie die zweite Speicherein heit über die Bestimmung, daß Zellen (0-3) logische "Einsen" enthalten; ansonsten wählt sie die erste Speichereinheit.

38. Dekodierer nach Anspruch 35, worin die Auswähleinrich tung auf den Platz bzw. die Anordnung von nacheinander fol genden Bits der logischen "Nullen" in den Zellen anspricht.

39. Dekodierer nach Anspruch 38, 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 aus wählt.

40. Dekodierer nach einem der Ansprüche 29 bis 39, dadurch gekennzeichnet, daß die Daten digitale Transformationskoef fizienten und Lauflängen zwischen Transformationskoeffi zienten, 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.

41. Dekodierer nach Anspruch 40, dadurch gekennzeichnet, daß jede der Speichereinheiten 13 Ausgangsanschlüsse auf weist.

42. Dekodierer nach Anspruch 41, dadurch gekennzeichnet, daß fünf der Ausgangsanschlüsse die Länge der kodierten Da tenbits tragen, vier Anschlüsse Null-Lauf-Länge tragen, die den digitalen Transformationskoeffizienten zugeordnet sind, und vier Anschlüsse die Länge der Mantissen-Bits tragen.

43. Verfahren zum Dekodieren von Huffman-kodierten Daten einheiten in einem Bitstrom, insbesondere zur Anwendung bei einer der Vorrichtungen nach den Ansprüchen 1 bis 42, wobei jede der kodierten Dateneinheiten Kodeworte aufweist, wobei das Verfahren gekennzeichnet ist durch:
ein Satz von Bits von den kodierten Dateneinheiten wird an den Eingangsanschlüssen einer Speichereinheit 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 Belegungsbits von den Kodeworten erzeugt werden; und
die Bits in dem Bitstrom werden über die Gesamtzahl von Bits verschoben, um einen nächsten Satz von Bits an den Eingangsanschlüssen der Speichereinheit für einen nachfol genden Dekodierungszyklus zur Verfügung zu stellen.

44. Verfahren zum Dekodieren von Huffman-kodierten Daten einheiten in einem Bitstrom, insbesondere zur Ausführung auf einem der Dekodierer nach einem der Ansprüche 1 bis 42, wobei jede der kodierten Dateneinheiten Kodeworte aufweist, dadurch gekennzeichnet, daß das Verfahren die folgenden Schritte enthält:
eine Mehrzahl von Sätzen von Bits der kodierten Daten einheiten an Eingangsanschlüssen einer Mehrzahl von Such- bzw. Nachprüftabelleneinheiten werden jeweils gleichzeitig zur Verfügung gestellt;
ein Belegungsbit wird von jeder Such- bzw. Nachprüfta belleneinheit in Abhängigkeit zu einem jeweiligen Satz von Bits an den Eingangsanschlüssen von den Such- bzw. Nach prüftabelleneinheiten gleichzeitig erzeugt;
eine Gesamtzahl der Bits der Dateneinheiten, die Bele gungsbits aus Kodeworten in dem Satz von Bits erzeugt ha ben, wird bestimmt; und
die Bits in dem Bitstrom werden um die Gesamtzahl von Bits verschoben, um eine Mehrzahl von nächsten Sätzen von Bits an den Eingangsanschlüssen der Such- bzw. Nachprüfta belleneinheiten für einen nachfolgenden Dekodierungszyklus zur Verfügung zu stellen.

45. Verfahren zum Dekodieren von Huffman-kodierten Daten einheiten in einem Bitstrom, insbesondere zur Ausführung auf einem Dekodierer nach einem der Ansprüche 1 bis 42, wo bei jede der kodierten Dateneinheiten Kodeworte aufweist, dadurch gekennzeichnet, daß das Verfahren folgendes ent hält:
eine Mehrzahl von Sätzen von Bits der kodierten Daten einheiten werden an Eingangsanschlüssen einer Mehrzahl von jeweiligen Such- bzw. Nachprüftabelleneinheiten gleichzei tig zur Verfügung gestellt, wobei jeder Satz von Bits in dem Bitstrom zu anderen Sätzen versetzt bzw. gestaffelt ist;
von jeder Such- bzw. Nachprüftabelleneinheit wird gleichzeitig ein Belegungsbit erzeugt, in Abhängigkeit zu einem jeweiligen Satz von Bits an den Eingangsanschlüssen der Such- bzw. Nachprüftabelleneinheit; und
die Bits in dem Bitstrom werden über eine vorbestimmte Zahl von Bits verschoben, um eine Mehrzahl von nächsten Sätzen von Bits an den Eingangsanschlüssen der Such- bzw. Nachprüftabelleneinheiten für einen nachfolgenden Dekodie rungszyklus zur Verfügung zu stellen.

46. Verfahren nach Anspruch 45, dadurch gekennzeichnet, daß die vorbestimmte Zahl von Bits zu dem größten Versatz betrag zwischen den Sätzen von Bits korrespondiert.

47. Verfahren nach Anspruch 45, ferner dadurch gekenn zeichnet, daß
daß die Gültigkeit jedes Belegungsbits von jeder Such- bzw. Nachprüftabelle bestimmt wird;
daß ein Fehlersignal in Abhängigkeit zu der Bestimmung eines ungültigen Belegungsbits von einer Such- bzw. Nach prüftabelle 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 Such- bzw. Nachprüftabelle an Eingangsanschlüssen einer anderen Such- bzw. Nachprüftabel le zur Verfügung gestellt wird, die dazu in der Lage ist, von dem Satz von Bits ein gültiges Belegungsbit zu erzeu gen.

48. Verfahren zum Dekodieren von Huffman-kodierten Daten einheiten in einem Bitstrom, insbesondere zur Verwendung auf einem Dekodierer nach einem der Ansprüche 1 bis 42, wo bei jede der kodierten Dateneinheiten Kodeworte aufweist, wobei das Verfahren durch folgende Schritte gekennzeichnet ist:
ein Satz von Bits von den kodierten Dateneinheiten an Eingangsanschlüssen einer ersten Such- bzw. Nachprüftabel leneinheit zum Erzeugen einer Gesamtzahl von Bits der Da teneinheiten, 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 Bits verschoben, um einen neuen Satz von Bits an den Eingangsanschlüssen der Speichereinheit für einen nachfol genden Dekodierungszyklus zur Verfügung zu stellen.

49. Verfahren nach Anspruch 48, dadurch gekennzeichnet, daß der erzeugende Schritt aufweist:
der Satz von Bits wird an Eingangsanschlüssen einer zweiten Such- bzw. Nachprüftabelleneinheit zur Verfügung gestellt, um ein Belegungsbit bzw. Token von einem Kodewort in dem Satz von Bits und eine Gesamtzahl von Bits der Da teneinheit, die das Kodewort aufweist, zu erzeugen;
der Satz von Bits wird über die Gesamtzahl von Bits verschoben;
der verschobene Satz von Bits wird an Eingangsan schlüssen einer dritten Such- bzw. Nachprüftabelleneinheit zur Verfügung gestellt, um ein Belegungsbit von einem Kode wort 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 wiederholt, wobei die vorbestimmte Anzahl zu einer Anzahl von Such- bzw. Nachprüftabelleneinheiten kor respondiert.

50. Verfahren nach Anspruch 49, dadurch gekennzeichnet, daß die Huffman-kodierten Dateneinheiten JPEG-Daten aufwei sen und die zweite Such- bzw. Nachprüftabelleneinheit nur auf DC-Kodeworte anspricht und die dritte Such- bzw. Nach prüftabelle nur auf AC-Kodeworte anspricht.

51. Verfahren zum Reduzieren der Größe einer Such- bzw. Nachprüftabelle, die an Zellen eines Bit-Schiebers in einem Huffman-Dekodierer angeschlossen ist, insbesondere zur Ver wendung bei einem Dekodierer nach einem der Ansprüche 1 bis 42, wobei das Verfahren durch folgende Schritte gekenn zeichnet ist:
eine Mehrzahl von Such- bzw. Nachprüftabellen wird zur Verfügung gestellt;
jede der Such- bzw. Nachprüftabellen wird an eine Un termenge der Bit-Schieberzellen angeschlossen, wobei jede Untermenge mit einer anderen überlappt;
Belegungsbits werden gleichzeitig durch jede der Such- bzw. Nachprüftabellen in Abhängigkeit zu Bits in den Unter mengen der angeschlossenen Zellen erzeugt; und
gültige Belegungsbits werden von den gleichzeitig er zeugten Belegungsbits ausgewählt.