DE4441293C2

DE4441293C2 - Verfahren und Schaltungsanordnung zum Lesen von Codewörtern variabler Länge aus einem Datenspeicher mit fester Wortlänge

Info

Publication number: DE4441293C2
Application number: DE4441293A
Authority: DE
Inventors: Thomas Dr Komarek; Christian Kroenke; Manfred Oberwestberg
Original assignee: SICAN GmbH
Current assignee: Sci Worx GmbH
Priority date: 1994-11-21
Filing date: 1994-11-21
Publication date: 1999-01-21
Anticipated expiration: 2014-11-22
Also published as: EP0714166A3; DE4441293A1; US5768428A; EP0714166A2

Description

Die Erfindung betrifft ein Verfahren und eine Schaltungsanordnung zum Lesen von Codewörtern variabler Länge aus einem Datenspeicher mit fester Wortlänge.

Codewörter variabler Länge treten vor allem bei der Anwendung von Kompressionsverfahren auf. Diese werden im zunehmenden Maße bei der Datenübertragung eingesetzt, um die zu übertragenden Nutzdaten zu reduzieren und die zur Verfügung stehende Bandbreite der Kanäle effektiv und kostengünstig zu nutzen. Kompressionsverfahren werden insbesondere bei der Übertragung von multimedialen Informationen, basierend vor allem auf die Standards H.261, JPEG und MPEG, angewandt.

Zur Datenkompression sind verschiedene Verfahren bekannt. Bei den Codierungsverfahren wird sehr häufig die Huffman-Codierung eingesetzt. Sie beruht auf der Verwendung von Codewörtern variabler Länge. Das Verfahren ordnet Symbolen mit hoher Auftrittswahrscheinlichkeit kurze Codewörter zu und entsprechend den weniger wahrscheinlichen Symbolen lange Codewörter. Dies führt zu einer Reduzierung der mittleren Codewortlänge.

Die Problematik dieses oder ähnlicher Verfahren liegt bei der Decodierung der Codewörter. Die Grenzen der Codewörter innerhalb des Datenstroms sind variabel und die Codewortlänge ist erst nach der Decodierung bekannt. Es ist daher erforderlich, daß die entsprechenden Bits variabel vom Datenstrom separiert werden, bis die Grenze des nächsten Codewortes erreicht ist.

Bisherige Verfahren benutzen in der Regel einen Eingangsdatenpuffer mit nachgeschaltetem Barrel-Shifter für die erforderlichen Shift-Operationen.

In der Patentschrift US 05253053 ("Variable Length Decoding using Lookup Tables", Okt 1993) ist ein entsprechendes Verfahren zur Variablen-Längen- Decodierung, VLD, beschrieben. Die Umwandlung des variablen in ein festes Datenformat erfolgt mittels zwei Datenpuffern, einem Barrelshifter und zweier Decodiertabellen. Durch die Verwendung eines Barrelshifters wird der Signalfluß verzögert, so daß nachteilig ein zusätzlicher Datenpuffer am Ausgang des Shifters erforderlich ist. Das Zeitverhalten des beschriebenen Verfahrens ist ungünstig und der Schaltungsaufwand relativ hoch.

In der US-PS 5245338 ist ein variabler Längendecoder beschrieben, bei dem Codewörter variabler Länge aus einem Datenspeicher mit fester Wortlänge ausgelesen werden. Die Codewörter werden durch zwei Shiftoperationen separiert, wobei zwei Shiftoperationen mit zwei Barrelshiftern getrennt voneinander durchgeführt werden. Hierbei werden die Shiftoperationen bei beiden Barrelshiftern um eine variable Bitlänge in Abhängigkeit von den Codewortlängen der bereits decodierten Codewörter durchgeführt. Nachteilig sind daher zwei aufwendige Barrelshifter erforderlich.

Der Erfindung liegt die Aufgabe zugrunde, von einem Codierverfahren bestimmte Codewörter variabler Länge aus einem Datenspeicher mit fester Wortlänge zu lesen, wobei das Verfahren unabhängig von der Länge der Codewörter ist und auch Sequenzen von Codewörtern fester Länge auftreten können. Die Leseoperation soll flexibel der Länge angepaßt sein, so daß der Implementierungsaufwand, der Rechenbedarf und die benötigte Rechenzeit gering sind.

Allgemein lassen sich drei Faktoren bestimmen, die einen Einfluß auf das Verfahren haben. Der erste Faktor ist die Wortbreite (WB) des Datenspeichers. Der zweite Faktor ist die Zahl der Takte, die zur Verfügung stehen, bis das nächste Codewort decodiert werden muß. Der dritte Faktor ist die Breite des Bitfensters (BF) für die Decodierung. Bei paralleler Decodierung entspricht sie in der Regel der maximalen Länge eines Codeworts.

Erfindung

Um die Aufgabe unter Berücksichtigung der drei Faktoren mit minimalem Schaltungsaufwand bei gleichzeitig günstigem Timing-Verhalten durchzuführen werden die Shift-Operationen erfindungsgemäß in zwei Stufen getrennt. Nach der Erfindung wird in der ersten Stufe ein Shift mit fester Bitbreite (BR) durchgeführt. Dabei sollte wenn möglich BR ein gemeinsamer Teiler von WB und BF sein. Es gilt dann: BF = N × BR. Erfindungsgemäß wird dann in der zweiten Stufe ein variabler Shift durchgeführt. Die maximalen Größe des Shifts beträgt BR - 1. Mit diesen zwei Operationen fassen sich alle Codewörter der Länge 1..BF separieren.

Die Vorgehensweise ist im nachfolgenden Beispiel veranschaulicht:
zu erfolgender Shift: 14 bit
Bitbreite: 4 bit
1. Stufe: 3 × Shift4
2. Stufe: Shift2

Die zwei Stufen der Shift-Operation werden erfindungsgemäß, wie in Fig. 1 gezeigt, räumlich und zeitlich getrennt ausgeführt. Die erste Stufe (101) liegt vor dem Datenpuffer (102). Der Datenpuffer ist entsprechend der Bitbreite BR in Unterpuffer (103) aufgeteilt. Die zweite Stufe (104) liegt am Ausgang des Datenpuffers.

Beim Start eines Decodiervorgangs liegt am Ausgang zum Decodermodul ein Datenwort der Länge BF an. Nach der Decodierung steht fest, welche Länge das Codewort hatte. Im ersten Schritt des Verfahrens wird nun geprüft, ob im Datenpuffer nach dem Shift-Vorgang noch eine ausreichende Anzahl von Datenbits zur Verfügung stehen würden, um ein Datenwort der Größe BF zu decodieren. Ist dies nicht der Fall, muß ein neues Datenwort aus dem Datenspeicher gelesen werden. Gleichzeitig wird in der ersten Shift-Stufe ein Shift um N mal BR Bits durchgeführt. Die Zahl N hängt dabei von der Länge des decodierten Codewortes und vom vorherigen Zustand der zweiten Shift-Stufe ab.

Muß auch ein Datenwort neu gelesen werden, so werden die Bits gleich über den Shift-Vorgang an die richtige Position im Puffer gebracht. Der Shift-Vorgang kann parallel oder auch seriell ausgeführt werden. Dies ist abhängig von der Zahl der Takte, die zur Verfügung stehen (Faktor 2). Ein serieller Shift benötigt weniger Hardwareaufwand.

Nachdem die Teilpuffer neu geladen sind, wird über die zweite Shift-Stufe der noch fehlende variable Shift von 0 bis BR - 1 eingestellt. Daher liegen am Eingang zur Stufe 2 immer mindestens BF + BR Bits an, um diesen Shift-Vorgang zu ermöglichen (105). Danach liegen die aktuellen Bits aus dem Datenspeicher für einen neuen Decodiervorgang am Ausgang an.

Durch die Erfindung wird der Hardwareaufwand verringert, da die Architektur flexibel ist und die Bitbreite optimal an die Wortbreite und das Bitfenster angepaßt werden kann. Außerdem kann die Hardware durch Ausnutzung von Prozeßpausen während des Decodierungsvorgangs reduziert werden. Durch die erfindungsgemäße Aufteilung des Shift-Vorgangs und Verlagerung vor und hinter eine Registerstufe wird die Verzögerungszeit der Shift-Operationen minimiert.

Zeichnungen

Die Erfindung ist anhand der nachfolgenden Figuren erläutert. Es zeigen:

Fig. 1: schematische Darstellung der Erfindung

Fig. 2: Ausführungsbeispiel für Erfindung: BR = 8,2 Takt nach Decodierung

Fig. 3: Ausführungsbeispiel für Erfindung: BR = 4,4 Takt nach Decodierung

Fig. 4: Ausführungsbeispiel für Erfindung: BR = 8,1 Takt nach Decodierung

Ausführungsbeispiele

In Fig. 2 bis Fig. 4 sind Ausführungsbeispiele der Erfindung angegeben. Dabei wurde für WB und BF jeweils der Wert 16 gewählt.

In Fig. 2 ist eine Ausführungsform für BR = 8 und 2 Takte Zeit nach der Decodierung (Faktor 2) gezeigt. Entsprechend BR = 8 sind 2 Teilpuffer vorhanden, wobei N = 2 gilt. Die erste Shift-Stufe ist mit Multiplexern realisiert. Die zweite Shift-Stufe (207) ist als programmierbarer Shifter dargestellt und besteht aus 16 8-zu-1-Multiplexern.

Im folgenden wird zur Erläuterung der Fall angenommen, daß ein Codewort der Länge 14 bit decodiert wurde. Die zweite Shift-Stufe (207) stand dabei auf Shift4. Im Teilpuffer 206 stand das untere Byte vom Datenwort dw. Im Teilpuffer 205 steht das obere Byte vom Datenwort dw und der Multiplexer 202 selektierte das untere Byte vom Datenwort dw + 1.

Ein Shift von 4 in 207 bedeutet, das beim letzten Decodiervorgang die unteren 4 bit im Teilpuffer 206 schon decodiert waren und nicht mehr für die Decodierung zur Verfügung standen. Beim Decodiervorgang wurden dann weitere 14 bit des Puffers decodiert. Daraus folgt, das insgesamt 18 bit der zur Verfügung stehenden 24 Bit bereits decodiert sind. Deshalb muß für die nächste Decodierung ein Datenwort nachgeladen werden.

Im ersten Takt wird das durch Multiplexer 202 selektiert untere Byte von dw + 1 über den Multiplexer 204 in den Teilpuffer 206 geladen. Im zweiten Takt wird von 202 das obere Byte von dw + 1 selektiert und über 203 in den Teilpuffer 205 geladen. Gleichzeitig wird ein Request für ein neues Datenwort gesendet. Mit dem nächsten Takt, in dem der neue Decodierungsvorgang beginnt, steht das neue Datenwort dw + 2 dann im Puffer 201 zur Verfügung. Gleichzeitig selektiert im Decodierungstakt der Multiplexer 202 das untere Byte von dw + 2. Der programmierbare Shifter 207 wird auf Shift2 eingestellt. Dieser Wert ergibt sich aus folgender Rechnung:
decodiert: 4 + 14 Bit = 18 Bit < 16 Bit
→ neues Datenwort
1. Shift-Stufe: 2 × Shift8
2. Shift-Stufe: Shift2

Nachdem das Codewort decodiert ist beginnt der Vorgang von neuem.

In Fig. 3 ist das Beispiel für 4 Takte Zeit nach der Decodierung (Faktor 2) angegeben. Hier werden die Teilpuffer 307 bis 310 über die Multiplexer 302 bis 306 Takt für Takt nachgeladen. Der weitere Ablauf entspricht dem Ausführungsbeispiel aus Fig. 2.

In Fig. 4 ist die Schaltung für nur einen Takt Zeit nach der Decodierung dargestellt. Dieser Fall muß immer speziell behandelt werden, da ein Nachladen der Teilpuffer mit jedem Takt nicht möglich ist. Deshalb kann ein Teil der Shift- Operationen von Stufe 1 erst hinter den Puffern ausgeführt werden.

Es gibt Fälle, wo das untere Byte vom neuen Datenwort dw + 2 in den Teilpuffer 406 geladen werden muß. Da aber zunächst das durch 402 selektierte obere Byte von dw + 1 über 404 in den Puffer 407 geladen werden muß, ist bei nur einem Takt ein Nachladen von 406 nicht möglich. Dieser Fall wird daher über den hinter 406 geschalteten Multiplexer 405 abgefangen.

Claims

1. Verfahren zum Lesen von Codewörtern variabler Länge aus einem Datenspeicher mit fester Wortlänge, wobei die Codewörter durch zwei Shiftoperationen separiert werden, die zwei Shiftoperationen getrennt voneinander durchgeführt werden und die Codewörter nach der ersten Shiftoperation zwischengespeichert werden, dadurch gekennzeichnet, daß die erste Shiftoperation um eine feste Bitlänge und die zweite Shiftoperation um eine variable Bitlänge durchgeführt wird.

2. Schaltungsanordnung zum Lesen von Codewörtern variabler Länge aus einem Datenspeicher mit fester Wortlänge mit zwei Rechenwerken zur Durchführung von Shiftoperationen, dadurch gekennzeichnet, daß das erste Rechenwerk für das Shiften um eine feste Bitlänge und das zweite Rechenwerk für das Shiften um eine variable Bitlänge ausgeprägt ist.

3. Schaltungsanordnung nach Anspruch 2, dadurch gekennzeichnet, daß Zwischenspeicher mit fester Bitbreite zwischen dem ersten und dem zweiten Rechenwerk angeordnet sind.

4. Schaltungsanordnung nach Anspruch 2 oder 3, dadurch gekennzeichnet, daß das erste Rechenwerk aus Multiplexern aufgebaut ist.

5. Schaltungsanordnung nach Anspruch 4, dadurch gekennzeichnet, daß die Eingangsdaten in einen ersten Multiplexer geführt werden, dessen Ausgang mit einem programmierbaren Shifter und mit je einem Eingang mindestens eines Multiplexers, dessen Ausgang an je einen Zwischenspeicher, die mit dem programmierbaren Shifter und je einem Eingang des vorgeschalteten und des nachfolgenden Multiplexers verbunden sind, geschaltet ist, verbunden ist.