DE69422654T2

DE69422654T2 - Verdichter für Kodes variabeler Länger

Info

Publication number: DE69422654T2
Application number: DE69422654T
Authority: DE
Inventors: Henry Derovanessian; Vincent Liu
Original assignee: General Instrument Corp
Current assignee: Arris Technology Inc
Priority date: 1993-03-26
Filing date: 1994-03-23
Publication date: 2000-08-17
Anticipated expiration: 2014-03-24
Also published as: EP0617518B1; NO941059D0; EP0617518A3; AU674199B2; TW223720B; DE69422654D1; JPH0750591A; KR940023047A; US5446916A; ATE189088T1; EP0617518A2; CA2119971C; AU5797694A; ES2141780T3; JP3207667B2; NO941059L; CA2119971A1; KR0177001B1

Description

Die Erfindung betrifft die Übermittlung komprimierter digitaler Daten und betrifft im besonderen eine Vorrichtung zum Anordnen von Codewörtern mit variabler Länge zur Übertragung in aufeinanderfolgenden Datenbytes fester Länge.
Um das verfügbare Hochfrequenzspektrum für die Übermittlung digitaler Daten, so etwa Daten für das hochauflösende Fernsehen, wirksam zu nutzen, ist es von Vorteil, die digitalen Signale zu komprimieren, um die zu übertragende Datenmenge auf ein Minimum zu reduzieren. Eine gut bekannte Kompressionstechnik bezeichnet man als variable Längencodierung. Ein Codierschema dieser Art führt dazu, daß Bitketten fester Länge in Bitketten mit unterschiedlicher Länge codiert werden, wobei die häufiger vorkommenden Codes durch Bitketten repräsentiert sind, die kleinere Längen haben als die Codes mit fester Länge. Wenn die Zuordnung von Codes variabler Länge richtig gemacht wird, dann ist die durchschnittliche Länge solcher Codes in einem gegebenen Datenstrom viel kleiner als die der entsprechenden Codes fester Länge, wenngleich viele der Codes mit variabler Länge viel länger sind als die entsprechenden Codes mit fester Länge. Ein solches Codierschema zur Codierung mit variabler Länge ist als Huffman- Codierung bekannt.
Um mit variabler Länge codierte Nachrichten über ein System mit fester Bitrate zu übertragen, sollte ein Puffer, der die Nachrichten speichern kann, unterhalten werden. Auf diese Weise kann man die Codewörter variabler Länge ansammeln und in Bytes fester Länge mit einer festen Bitrate übertragen.
Eingabe-/Ausgabe-Puffer-Schnittstellen nach dem Stand der Technik sind in einem Byte- Format konfiguriert. Die Codes mit variabler Bitlänge werden in die richtigen Byte- Grenzen gepackt und formatiert, bevor sie in die geeigneten Puffer geschrieben werden. Bei solchen Schemata nach dem Stand der Technik muß jede Zelle in einem Puffer- Array auf jede einzelne einlaufende Datenzeile abgebildet werden, um die Codes variabler Länge in einer sequentiellen Ordnung abzunehmen und zu speichern, welche Ordnung die Ausgabe von Bytes fester Länge mit fester Rate ermöglicht. Wenn die maximale Codewortlänge z. B. 19 Bit ist, so würde ein 32- Zellen- Puffer- Array 608 elektrische Verbindungen (19 · 32) benötigen, um jede Zelle zu befähigen, jedes beliebige der 19 einlaufenden Bits zu speichern. Die Realisierung einer derartigen Struktur gestaltet sich sehr komplex und erfordert eine große nutzbare Fläche in einer auf einer integrierten Schaltung basierenden Implementierung. Solche Komplexität erhöht die Kosten der Vorrichtung beträchtlich.
Die EP-A-0 353 826 offenbart eine statistische Codieranordnung zur Erzeugung von Codewörtern mit veränderlicher Länge, dadurch, daß Daten von einem ersten und einem zweiten Register, die parallel geschaltet sind, in ein Ausgaberegister übertragen werden.
Eine Aufgabe der Erfindung liegt in der Schaffung eines Packers für Codewörter variabler Länge, der weniger komplex ist als Strukturen nach dem Stand der Technik, was zu einem geringeren Kostenaufwand führt.
Diese Aufgabe wird durch einen Packer für Codewörter variabler Länge nach Anspruch 1 erfüllt.
Weitere vorteilhafte Ausführungsformen sind Gegenstand der Unteransprüche 2 bis 7.
Die vorliegende Erfindung schafft einen mehrstufigen Packer für variable Codewörter, welcher die Organisation der Bits von Codewörtern mit variabler Länge in geeignete Byte-Grenzen erleichtert und eine verringerte Anzahl elektrischer Verbindungen aufweist.
Gemäß einer Ausführungsform der Erfindung wird ein Packer für Codewörter variabler Länge zur Verwendung bei der Übermittlung von Codewort-Daten in aufeinanderfolgenden m-bit-Bytes vorgesehen. Es sind Mittel zum Akkumulieren einer Binärsumme vorgesehen, welche eine über die Zeit empfangene Gesamtzahl von Codewort-Bits anzeigt. Ein Byte-Pointer wird von mindestens einem höchstwertigen Bit der Binärsumme abgeleitet. Ein Bit-Pointer wird von einer Mehrzahl von niederwertigsten Bits der Binärsumme abgeleitet. Ein erstes Datenspeicher-Array weist eine Mehrzahl von ersten m-bit-Speicherbytes auf und spricht auf den Byte-Pointer an, um Codewort- Daten in den ersten Speicherbytes zu speichern. Ein zweites Datenspeicher-Array weist eine Mehrzahl von zweiten m-bit- Speicherbytes auf und spricht auf den Byte- und Bit-Pointer an, um die zweiten Speicherbytes mit Codewort-Daten von dem ersten Datenspeicher-Array zu füllen. Es sind Mittel vorgesehen, um ein m-bit-Byte von Codewort-Daten von jedem gefüllten zweiten Speicherbyte auszugeben, um aufeinanderfolgende m-bit-Bytes von Codewort-Daten bereitzustellen. Einlaufende Codewörter variabler Länge werden nacheinander in dem ersten Datenspeicher-Array gespeichert, wobei jedes Codewort am Anfang eines ersten Speicherbytes beginnt, welches durch den Byte-Pointer auf Basis der Binärsumme von vorausgehenden Codewort-Bitlängen identifiziert ist. Jedes der in dem ersten Datenspeicher-Array gespeicherten Codewörter variabler Länge wird in das zweite Datenspeicher-Array transferiert, beginnend an einer Stelle innerhalb eines zweiten Speicherbytes, welche durch den Byte-Pointer und den Bit-Pointer auf Basis der Binärsumme von vorausgehenden Codewort-Bitlängen identifiziert ist.
In einer vorteilhaften Ausführungsform, welche in der Detailbeschreibung dargestellt ist, werden die hereinkommenden Codewörter in Sätze (d. h. "Superblöcke") gruppiert, welche eine Mehrzahl von Codewörtern enthalten. Der Codewort- Packer umfaßt ferner Mittel zum Rücksetzen der akkumulierenden Mittel auf Null zu Beginn jedes neuen Satzes von Codewörtern.
Weiter haben in der dargestellten Ausführungsform die Codewörter eine maximale Länge von n Bit. Jedes der beiden Datenspeicher-Array umfaßt k Speicherbytes, die jeweils m Zellen enthalten, wobei
k = [(n+m-1)/m].
Die akkumulierenden Mittel können einen q-bit-Akkumulator umfassen, wobei dessen p niederwertigsten Bits den Bit-Pointer bilden und die übrigen (q-p) höchstwertigen Bits den Byte- Pointer bilden. p ist Anzahl von Bits, die erforderlich ist, um irgendeine von m Zellen in einem Speicherbyte zu identifizieren, und (q-p) ist die Anzahl von Bits, die erforderlich ist, um irgendeines von k Speicherbytes zu identifizieren.
Codewörter werden sequentiell in den Packer für Codewörter variabler Länge eingetaktet. Es sind Zeitgeber-Mittel vorgesehen, um die Codewort-Daten codewortweise in das erste Datenspeicher-Array einzutakten. Der Byte-Pointer wird ebenfalls in das erste Datenspeicher-Array eingetaktet, wenn ein entsprechendes Codewort dorthinein eingetaktet wird. Die Codewort-Daten von dem ersten Datenspeicher-Array werden codewortweise in das zweite Datenspeicher-Array eingetaktet. Der Byte- und der Bit-Pointer werden in das zweite Datenspeicher-Array eingetaktet, wenn ein entsprechendes Codewort dorthinein eingetaktet wird.
Eine vorteilhafte Ausführungsform eines Packers für Codewörter variabler Länge umfaßt ferner Zeitgeber-Mittel zum Eintakten der Codewort-Daten in das erste Datenspeicher- Array, jeweils ein Codewort nach dem anderen, Eintakten des Byte-Pointers in das erste Datenspeicher-Array, wenn ein Codewort dorthinein eingetaktet wird, Eintakten der Codewort-Daten von dem ersten Datenspeicher- Array in das zweite Datenspeicher-Array, jeweils ein Codewort nach dem anderen, und
Eintakten des Byte- und Bit-Pointers in das zweite Datenspeicher-Array, wenn ein Codewort dorthinein eingetaktet wird.
Bei einer vorteilhaften, beispielhaft dargestellten Ausführungsform erfolgt das Eintakten der Codewort-Daten in das zweite Datenspeicher-Array einen Taktzyklus, nachdem sie in das erste Datenspeicher-Array eingetaktet wurden. Es sind Mittel vorgesehen, um das Eintakten des Byte- und Bit- Pointers in das zweite Datenspeicher-Array um einen Taktzyklus zu verzögern, so daß die richtigen Byte- und Bit- Pointer zu dem zweiten Datenspeicher-Array gelangen, wenn dieses die entsprechenden Codewort-Daten empfängt.
Die Mittel zum Ausgeben von m-bit-Bytes von Codewort-Daten von jedem gefüllten zweiten Speicherbyte können auf ein Inkrementieren des Byte-Pointers ansprechen. Auf diese Weise wird jedesmal dann, wenn Codewort-Daten, die in das zweite Datenspeicher-Array eingegeben werden, eine Byte-Grenze überschreiten, das vorhergehende volle Datenbyte aus dem Array ausgegeben.
Weitere Merkmale und Vorteile sind in der Zeichnung und der detaillierten Beschreibung offenbart.

In der Zeichnung zeigen:

Fig. 1 eine graphische Darstellung eines Codewort-Packers nach dem Stand der Technik;
Fig. 2 eine graphische Darstellung eines zweistufigen Codewort-Packers in Einklang mit der vorliegenden Erfindung;
Fig. 3 ein Blockdiagramm, welches eine Implementierung des zweistufigen Codewort-Packers von Fig. 2 zeigt;
Fig. 4 ein detaillierteres Blockdiagramm der Akkumulator- Stufe des Blockdiagramms von Fig. 3; und
Fig. 5a Diagramme mit Beispielen für das Laden einlaufender bis 5d Codewörter in die erste Array-Stufe und für das Laden der Codewörter von der ersten Array-Stufe in die zweite Array-Stufe.
Die variable Längencodierung von digitalen Daten ist häufig vorteilhaft, um die durchschnittliche Bitrate, die notwendig ist, um große Datenmengen zu übertragen, zu reduzieren.
Solche Schemata werden typisch in bildverarbeitenden Systemen verwendet, so etwa in hochauflösenden Fernsehsystemen, um Videodaten innerhalb einer begrenzten Bandbreite zu übertragen.
Ein Ansatz nach dem Stand der Technik, um Codewörter mit variabler Länge in feste Byte- Längen für die Übertragung zu packen, ist in Fig. 1 gezeigt. Ein einlaufendes Codewort 10, welches z. B. von 1 bis 19 Bit (D0 bis D18) umfassen kann, wird in ein Datenspeicher-Array 12 geladen, welches 32 Zellen enthält (A0 bis A31). Jedes Codewort wird zusammen mit Information übertragen, die die Länge des Codeworts identifiziert. Die identifizierende Information befähigt zum Laden eines aktuellen Codeworts in das Datenspeicher-Array 12, beginnend bei einer Zelle, die unmittelbar oberhalb der letzten Zelle liegt, die mit den vorhergehenden Codewort-Daten gefüllt ist. Wenn also z. B. ein in A0 bis A2 gespeichertes 3-bit-Codewort von einem 5-bit-Codewort gefolgt ist, wird das 5-bit-Codewort in den Zellen A3 bis A7 abgelegt, wodurch ein 8-bit-Byte (A0 bis A7) komplettiert wird, welches dann aus dem Datenspeicher-Array 12 ausgegeben werden kann.
Damit ein neues Codewort, beginnend bei einem beliebigen der in dem Array enthaltenen 32 Register, geladen werden kann, muß jede einzelne Zelle des Array Verbindung mit allen 19 möglichen Bitstellen jedes hereinkommenden Codeworts haben. Damit ist gefordert, daß jede der 32 Zellen mit 19 verschiedenen Codewort - Bitstellen Verbindung haben muß, woraus sich insgesamt 608 elektrische Verbindungen ergeben. Wenn längere Codewörter und/oder ein größeres Datenspeicher-Array für eine bestimmte Systemimplementierung gefordert sind bzw. ist, erhöht sich die Zahl der elektrischen Verbindungen entsprechend. Die Komplexität, die derartige Strukturen nach dem Stand der Technik bezüglich der Zahl der elektrischen Verbindungen zu jeder Zelle des Datenspeicher-Array fordern, wirft schwierige Realisierungsprobleme auf.
Die vorliegende Erfindung befreit von der Notwendigkeit des Standes der Technik, n Verbindungen zu jeder Zelle haben zu müssen, wobei n die maximal mögliche Codewortlänge ist. Dies wird durch die Verwendung eines Mehrstufen - Ansatzes zum Packen der Codewörter variabler Länge erzielt. Ein solcher Ansatz ist in Fig. 2 veranschaulicht.
In der Ausführungsform von Fig. 2 sind eine erste Datenspeicher-Array-Stufe 20 und ein zweites Datenspeicher-Array 22 vorgesehen. Jedes Array kann z. B. ein aus einem herkömmlichen dynamischen Speicher mit wahlfreiem Zugriff (DRAM) aufgebautes Array umfassen, welches L Zellen aufweist, die parallel geladen werden können. Die L Zellen sind übereinander gestapelt, ähnlich einem First-in/First - out - Register, wobei automatisch von der letzten Zelle auf die erste Zelle übergegangen wird. Anders ausgedrückt: sobald einmal die Zelle A31 des Array 20 geladen ist, wird als nächste Zelle die Zelle A0 geladen. Die Zellenzahl L in dem Array steht in direkter Beziehung zu der maximal möglichen Längen eines Eingangscodeworts und ist wie folgt beschrieben:
L = [(n+m-1) / m] x m.
In dem hierin veranschaulichten Beispiel ist das Codewort maximaler Länge (n) 19 bit und jedes von dem Codewort-Packer ausgegebene Byte (m) hat eine Länge von 8 bit. Demnach verlangt jede Stufe 20, 22 32 Zellen (A0 bis A31, B0 bis B31), was das Achtfache der oberen Grenze von (19+7)/8 ist, d. h.
m x [(n+(m-1)) / m].
Jedes der Arrays 20, 22 ist in k Byte aufgeteilt, wobei k = L/m. Demnach ist in der beispielhaften Ausführungsform k = 32/8 = 4. Die vier Byte der Array-Stufe 1 sind in Fig. 2 durch die Bezugsziffern 24 (Eingangsbyte 0),
26 (Eingangsbyte 1), 28 (Eingangsbyte 2) und
30 (Eingangsbyte 3) bezeichnet. Ähnlich enthält die Datenspeicher-Array der Stufe zwei Byte, welche durch die Bezugsziffern 34 (Ausgangsbyte 0), 36 (Ausgangsbyte 1), 38 (Ausgangsbyte 2) und 40 (Ausgangsbyte 3) bezeichnet sind.
Anders als beim Stand der Technik muß jede der Zellen in der Array-Stufe 1 von Fig. 2 nur bis zu drei Verbindungen zu dem hereinkommenden Codewort haben. Beispielsweise muß Zelle A8 (welches die erste Zelle in Eingangsbyte 1 ist) nur Verbindungen zum Empfang von Eingabebit D0, Eingabebit D8 oder Eingabebit D16 eines Eingangscodeworts 10 aufweisen. In dem Fall, daß ein neues Codewort mit einer Länge von mehr als 8 bit zu speichern ist, beginnend bei Zelle A0 des Eingangsbyte 0, wird A8 mit Bit D8 des einlaufenden Codewortes geladen, wie bei 70 bezeichnet. In dem Fall, daß ein neues Codewort, beginnend bei Zelle A8 von Byte 1, zu laden ist, wird Zelle A8 Bit D0 des neuen Codeworts empfangen, wie bei 72 bezeichnet. In dem Fall, daß ein neues Codewort mit einer Länge von mehr als 16 bit zu laden ist, beginnend bei Zelle A24 von Byte 3, wird A8 Bit D16 des hereinkommenden Codeworts empfangen, wie bei 74 bezeichnet. Man beachte, daß das Speichern jedes neuen Codeworts am Anfang eines Bytes der ersten Array-Stufe einsetzt. Demnach gibt es bei der beispielhaft dargestellten Ausführungsform nur vier Zellen der ersten Stufe, bei denen das Laden eines neuen Codewortes einsetzen kann. Diese sind die Zellen A0, A8, A16 und A24, welche den Beginn von Byte 0, Byte 1, Byte 2 bzw. Byte 3 repräsentieren. Das eigentliche Byte, bei dem mit dem Laden eines neuen Codeworts begonnen wird, wird von einem Byte- Pointer bestimmt, der weiter unten ausführlicher beschrieben ist.
Das Datenspeicher-Array 22 der Stufe 2 lädt Codewort-Daten von dem Array der Stufe 1 in Abhängigkeit von dem Byte- Pointer sowie einem Bit-Pointer. Jede Zelle (B0 bis B31) des Array der Stufe 2 ist mit ihrer entsprechenden Zelle in dem Array der Stufe 1 verbunden, sowie mit den sieben vorangehenden Zellen in dem Array der Stufe 1. Somit erfordert jede Zelle in dem Array der Stufe 2 acht Verbindungen. Dies ist bei 32 für Zelle B11 gezeigt.
Die jeweilige Zelle der ersten Stufe, die als Eingabe für eine Zelle der zweiten Stufe verwendet wird, wird von dem Bit-Pointer bestimmt. Innerhalb jedes Byte wird der Bit- Pointer von 0 bis 7 inkrementiert, wie bei 60 in Fig. 2 gezeigt. Wenn der Bit-Pointer Null ist und der Byte-Pointer auf Byte Null zeigt, wird jede der Zellen B0 bis B7 mit den Inhalten der Zellen A0 bis A7 geladen. Wenn das in die zweite Array-Stufe geladene Codewort in der Länge größer ist als 8 bit, setzt sich die Eins - zu - Eins - Korrespondenz zwischen den Arrays der ersten Stufe und der zweiten Stufe in das bzw. die sukzessive/n Byte/s hinein fort.
Wenn der Bit-Pointer nicht auf Null weist, blicken die Zellen der zweiten Stufe um die von dem Bit-Pointer bezeichnete Zellenzahl zurück, um Daten aus der ersten Array-Stufe zu erhalten. Wenn also beispielsweise der Bit-Pointer 3 ist und gerade Zelle B11 geladen wird, so wird Zelle B11 die Daten von Zelle A8 der ersten Array-Stufe empfangen. Ein detaillierteres Beispiel der Arbeitsweise des erfindungsgemäßen Codewort-Packers findet sich nachfolgend in Zusammenhang mit der Erörterung der Fig. 5a bis 5d.
Fig. 3 ist ein Blockdiagramm einer Implementierung eines zweistufigen Codewort-Packers gemäß der vorliegenden Erfindung. Codewörter mit variabler Länge (z. B. Huffman- Codewörter) werden von einer Code - Tabelle 80 in das Datenspeicher-Array 20 der Stufe 1 über eine Leitung 82 eingespeist. Das Speicher-Array 20 empfängt einen Systemtakt über Anschluß 21, der die Zellen des Array kontinuierlich jeden Taktzyklus auffrischt, wenn deren Inhalt über Leitung 83 in die zweite Array-Stufe 22 transferiert wird. Das Array der Stufe 2 empfängt den Systemtakt über Anschluß 23. Jedesmal, wenn ein Byte in dem Array der Stufe 2 gefüllt worden ist, wird es über eine von K Leitungen 25 auf ein herkömmliches First-in/First - out - Pufferregister (nicht gezeigt) ausgegeben, wo es zur Übertragung gehalten wird.
Gleichzeitig mit der Eingabe von Codewort-Daten in das Array 20 der Stufe 1 werden die Codelängen des Codeworts anzeigende Daten über Leitung 84 in einen Akkumulator/Stapelspeicher 86 eingespeist. Der Akkumulator/Stapelspeicher empfängt den Systemtakt über Anschluß 87. Der Akkumulator/Stapelspeicher gibt einen Byte- Pointer und einen Bit-Pointer aus, die abgeleitet sind von der akkumulierten Gesamtsumme an dem Array 20 der Stufe 1 über die Zeit zugeführten Codewort-Bits. Der Byte-Pointer wird unmittelbar von dem Array der Stufe 1 verwendet, um das Byte zu identifizieren, beidem das Speichern des aktuellen Codeworts in dem Array der Stufe 1 beginnen soll. Der Byte- Pointer und der Bit-Pointer werden um genau einen Taktzyklus verzögert, unter Verwendung einer herkömmlichen Verzögerungsschaltung 88, welche den Systemtakt über Anschluß 89 empfängt. Der verzögerte Byte-Pointer wird dem Array 22 der Stufe 2 über Leitung 90 zugeführt. Der verzögerte Bit-Pointer wird dem Array der Stufe 2 über Leitung 92 zugeführt. Der Akkumulator/Stapelspeicher 86 stellt ferner Ausgabe-Strobes W&sub1; bis Wk auf Leitungen 94 bereit, welche den Ausgabepuffer zum Empfang der Ausgangsbytes von den Leitungen 25 des Array der Stufe 2 freigeben. Ein geeigneter Ausgabe- Strobe wird jedesmal bereitgestellt, wenn eine Byte-Grenze in dem Array der Stufe 2 überschritten wird. Damit wird das soeben komplettierte volle Datenbyte aus der zweiten Array-Stufe ausgegeben.
Der Akkumulator/Stapelspeicher 86 ist detaillierter in Fig. 4 dargestellt. Die Codelängen von der Huffman- Codetabelle 80 für jedes Codewort gelangt über einen Anschluß 102 auf einen Akkumulator 104. Der Akkumulator 104 akkumuliert die Gesamtzahl an Bits in eine Binärzahl. Bei der dargestellten Ausführungsform, wo sowohl das Array der Stufe 1 wie das Array der Stufe 2 jeweils vier 8-bit- Bytes umfassen, ist der Akkumulator 104 ein 5-bit- Akkumulator. Der Akkumulator wird zu Operationsbeginn durch ein an Anschluß 100 eines Multiplexer 108 angelegtes Reset-Signal initialisiert, welches die Rückführungseingänge 110, 112 des Akkumulators mit Masse (d. h. Null) verbindet. Wenn also der Akkumulator zurückgesetzt ist, wird das nächste Codewort, beginnend bei A0, in das Array der ersten Stufe und, beginnend bei B0, in das Array der zweiten Stufe geladen. Bei einer bevorzugten Ausführungsform werden mehrere Codewörter gruppiert, so daß sie zusammen einen Block bilden, und mehrere Blöcke werden zu einem Makroblock gruppiert. Der Akkumulator wird zu Beginn jedes neuen Makroblocks rückgesetzt.
Die Ausgabe des Akkumulators 104 ist ein q-bit- Binärwort, dessen p niederwertigste Bits den Bit-Pointer bilden, während die übrigen (q-p) höchstwertigen Bits den Byte-Pointer bilden. Bei der dargestellten Ausführungsform, worin der Codewort-Packer 8-bit- Bytes ausgibt und sowohl die erste Array-Stufe wie auch die zweite Array-Stufe jeweils vier solcher Byte halten, werden die drei Bits niedrigster Wertigkeit der 5-bit- Akkumulatorausgabe als Bit-Pointer benutzt, und die zwei Bits höchster Wertigkeit werden als Byte-Pointer benutzt. Es wird erkennbar sein, daß ein Bit-Pointer von 3 Bit verwendet werden kann, um auf ein beliebiges von den 8 Bit innerhalb eines Bytes zu zeigen, und daß ein Byte- Pointer von 2 Bit verwendet werden kann, um ein beliebiges von den in einem Array enthaltenen vier Byte zu definieren. Das von dem Akkumulator 104 abgegebene 5-bit- Wort akkumuliert sich mit Hinzufügen der Längen neuer Codewörter zu den akkumulierten Längen früherer Codewörter weiter fort. Mit akkumulierender Summe von Codewortlängen werden die über 5 Bit insgesamt hinausgehenden höchstwertigen Bits verworfen. Ein Latch-Speicher 106 hält den Bit-Pointer und Byte-Pointer zur Ausgabe auf einer zyklischen Basis entsprechend dem Systemtakt, welcher über Anschluß 105 eingespeist wird.
Der von dem Latch-Speicher 106 ausgegebene Byte-Pointer und Bit-Pointer werden zu dem Multiplexer 108 zur Verwendung bei der Akkumulation der Codelängen über die Zeit zurückgeführt. Sie werden außerdem auf eine Verzögerungsschaltung 88 (Fig. 3) zur verzögerten Eingabe in das Array 22 der zweiten Stufe ausgegeben. Die Verzögerung 88 kompensiert die durch das Array der Stufe 1 verursachte Latenz und bringt so die korrekten Bit- und Byte-Pointer mit den hereinkommenden Daten zur Verwendung in dem Array der Stufe 2 in Übereinstimmung. Wie oben erwähnt, beträgt die Verzögerung genau einen Taktzyklus.
Die Fig. 5a bis 5d zeigen ein Beispiel dafür, wie der erfindungsgemäße Codewort-Packer in einer Implementierung arbeitet, wo die maximale Codewortlänge 19 bit ist und wo gefragt ist, die Codewort-Daten in 8-bit- Bytes auszugeben. In einer solchen Implementierung werden sowohl die erste Array - Stufe wie die zweite Array-Stufe jeweils 32 Zellen enthalten, aufgeteilt in vier 8-bit- Bytes. Bei dem in den Fig. 5a bis 5d dargestellten Beispiel weisen vier aufeinanderfolgende Codewörter Längen von 7 bit, 9 bit, 3 bit und 8 bit auf. In Fig. 5a ist der Codewort-Packer zurückgesetzt worden, so daß sowohl der Bit-Pointer wie auch der Byte-Pointer Null sind. Damit ist das von dem Codelängen-Akkumulator 104 abgegebene 5-bit- Wort 00000. Die drei niederwertigsten Bit "000" zeigen an, daß der Bit-Pointer Null ist. Die zwei höchstwertigen Bits "00" zeigen an, daß der Byte-Pointer Null ist. Als Folge davon wird das zum Zeitpunkt t&sub1; von dem ersten Array 20 empfangene 7-bit- Codewort in Byte Null in die Zellen A0 bis A6 geladen, wie bei 120a bezeichnet. Zum Zeitpunkt t2 (einen Taktzyklus nach t&sub1;) wird das 7-bit- Codewort von dem ersten Array 20 in die Zellen B0 bis B6 des zweiten Array 22 transferiert, wie mit 120b bezeichnet.
Ebenfalls zum Zeitpunkt t&sub2; wird das nächste Codewort, welches eine Länge von 9 bit aufweist, am ersten Array 20 empfangen, wie in Fig. 5b gezeigt. Jetzt erscheint am Ausgang des Akkumulators 104 - wegen der Addition der 7-bit- Codelänge des ersten Codeworts zu dem vom Latch 106 über Multiplexer 108 rückgeführten früheren Wert 00000 - der Wert "00111". Weil die zwei Bits mit höchster Wertigkeit des aktuellen Akkumulatorwerts 00111 "00" sind, wird das neue 9-bit- Codewort in Eingangsbyte Null des Array 20 geladen, beginnend bei Zelle A0. Weil das neue Codewort eine Länge von 9 bit hat, wird es das Byte Null (A0 bis A7) vollständig ausfüllen, wobei das letzte Bit in die Zelle A8 des Eingangsbyte 1 hineinreicht, wie bei 122a bezeichnet.
Zum Zeitpunkt t&sub3; wird das 9-bit- Codewort von dem ersten Array 20 in das zweite Array 22 übertragen. Dem ersten Array 20 zugeführte Daten überschreiben die darin enthaltenen früheren Daten, wohingegen Daten im zweiten Array 22 bis zu ihrer Ausgabe nicht überschrieben werden können. Und weil Daten von dem zweiten Array 22 nur als volle 8-bit- Bytes zur Ausgabe gelangen, muß das frühere, in den Zellen B0 bis B6 gespeicherte 7-bit- Codewort gesichert werden. Deshalb ist es notwendig, das Schreiben in das zweite Array 22 während der Zeit t&sub3; bei Zelle B7 zu beginnen. Diese Forderung wird durch die akkumulierte Codewortlänge 00111 angezeigt, die das zweite Array 22 anweist, das nächste Codewort beginnend mit Zelle B7 von Byte Null zu empfangen. Dies ist klar, weil der von den höchstwertigen Bits der akkumulierten Codelänge 00111 gebildete Byte-Pointer den Wert "00" hat und der von den niederwertigsten Bits gebildete Bit-Pointer auf Zelle B7 zeigt ("111"). Demnach wird das in das zweite Array zur Zeit t&sub3; übertragene 9-bit- Codewort die Zellen B7 bis B15 füllen. Man beachte, daß, sobald das zweite Codewort an das zweite Array transferiert wurde, insgesamt 16 bit an Codewort-Daten empfangen worden sind, welche sowohl das Ausgangsbyte 0 wie das Ausgangsbyte 1 vollständig füllen, wie bei 120b, 122b in Fig. 5b gezeigt. Weil beide dieser Bytes komplett aufgefüllt sind, werden sie aus dem zweiten Array 22 in einen Puffer zur Übertragung übernommen, gesteuert durch die Ausgabe-Strobes W&sub1; und Wk von Akkumulator/Stapelspeicher 86, der Kenntnis davon hat, daß die erste Byte- Grenze 121 und die zweite Byte-Grenze 123 erreicht worden sind.
Ebenfalls zur Zeit t&sub3; wird das erste Array 20 das nächste Codewort empfangen, dessen Länge 3 bit ist. Der Akkumulatorwert zu diesem Zeitpunkt wird 10000 sein, infolge der Summierung des früheren akkumulierten Wertes (00111) zu der Länge des vorhergehenden 9-bit- Codewortes (01001). Weil der von den zwei höchstwertigen Bits der akkumulierten Codelänge 10000 gebildete Byte-Pointer "10" bezeichnend für Eingangsbyte 2 ist, wie bei 124a in Fig. 5c gezeigt, wird das zur Zeit t&sub3; ankommende 3-bit- Codewort in Byte 2 geladen, beginnend bei Zelle A16. Wie in Fig. 5c gezeigt, wird dies dazu führen, daß die Zellen A16 bis A18 mit dem 3-bit- Codewort gefüllt werden. Zum Zeitpunkt t4 wird dieses 3-bit- Codewort zu den Zellen B16 bis B18 des zweiten Array 22 transferiert, als Antwort auf den Bit - Pointer - Anteil "000" des akkumulierten Codelängenwertes 10000. Weil zum Zeitpunkt t&sub4; keines der Bytes in dem zweiten Array 22 ganz voll ist, werden zu diesem Zeitpunkt keine Daten aus dem zweiten Array ausgelagert.
Wie in Fig. 5d gezeigt, wird das erste Array 20 das nächste Codewort, welches eine Länge von 8 bit aufweist, während t&sub4; empfangen. Die akkumulierte Codelänge beträgt nun 10011, als Resultat der Addition des früheren akkumulierten Wertes 10000 und der 3-bit- Länge (011) des früheren Codewortes. Weil die zwei höchstwertigen Bits der aktuellen akkumulierten Codelänge den Wert "10" haben, wird der Byte-Pointer weiterhin auf Eingangsbyte 2 in Array 20 zeigen, und das aktuelle 8-bit- Codewort wird in die Zellen A16 bis A23 geladen.
Zum Zeitpunkt t&sub5; wird das zweite Array 22 das 8-bit- Codewort von den Zellen A16 bis A23 des ersten Array 20 empfangen. Die Zellen B16 bis B18 des zweiten Array enthalten immer noch das zur Zeit t&sub4; geladene 3-bit- Codewort. Dementsprechend wird das aktuelle 8-bit- Codewort in die Zellen B19 bis B26 geladen, wie durch den Byte-Pointer ("10"), der auf das Ausgangsbyte 2 zeigt, und den Bit-Pointer ("11"), der auf die Zelle oberhalb der dritten Zelle in Ausgangsbyte 2 zeigt, vorgegeben. Wie in Fig. 5d gezeigt, reicht das aktuelle 8-bit- Codewort von Byte 2 in Byte 3 hinein, wie bei 126b bezeichnet. Weil Byte 2 des zweiten Array voll ist, wie durch das Überschreiten der Byte-Grenze 125 bestimmt, werden die in Byte 2 des zweiten Array 22 enthaltenden 8 Bit zu diesem Zeitpunkt ausgelesen.
Zur Zeit t&sub5; wird die akkumulierte Codelänge 11011 sein, als Resultat der Addition der 8-bit- Länge (1000) des früheren Codeworts zu der früheren akkumulierten Codelänge 10011. Der neue akkumulierte Codelängenwert 11011 wird einen Byte- Pointer "11" schaffen, der auf Eingangsbyte 3 (126a) des ersten Array für das Laden des nächsten Codewortes (nicht gezeigt) weist. Der Bit-Pointer "011" wird das zweite Array 22 anweisen, mit dem Laden des nächsten Codewortes bei Zelle B27 zu beginnen.
Der Vorgang setzt sich auf diese Weise fort, wobei Daten, die über die Zellen A31 und B31 hinausgehen, in die Zellen A0 bzw. B0 zurückgeführt und geschrieben werden. Nachdem alle Codeworte für einen Makroblock empfangen wurden, wird der Codewort-Packer neu initialisiert, indem ein Reset-Signal an den Anschluß 100 von Multiplexer 108 (Fig. 4) angelegt wird.
Dies hat zur Folge, daß das erste Codewort des nächsten Makroblocks in das erste Array 20, beginnend bei Zelle A0, und in das zweite Array 22, beginnend bei Zelle B0, geschrieben wird.
Die Berechnung der in dem Beispiel von Fig. 5a bis Fig. 5d verwendeten akkumulierten Codelängen (aufeinanderfolgende Codewortlängen von sieben, neun, drei und acht Bit) wird wie folgt zusammengefaßt:
Anfänglicher akkumulierter Wert 00000
+ 7-bit- Länge 00111
Akkumulierter Wert zur Zeit t&sub2; 00111
+ 9-bit- Länge 01001
Akkumulierter Wert zur Zeit t&sub3; 10000
+ 3-bit- Länge 00011
Akkumulierter Wert zur Zeit t&sub4; 10011
+ 8-bit- Länge 01000
Akkumulierter Wert zur Zeit t&sub5; 11011
Weil jede der Zellen in dem ersten Array 20 ein Maximum von drei Verbindungen zu dem hereinkommenden Codewort haben wird, wie bei 70, 72, 74 von Fig. 2 gezeigt, und jede der Zellen des zweiten Array nur acht Verbindungen zu Zellen in dem ersten Array 20 haben wird, wie bei 32 in Fig. 2 gezeigt, ist die Komplexität der Ausgestaltung im Vergleich zu einstufigen Codewort - Packern nach dem Stand der Technik erheblich reduziert. Bei der beispielhaft dargestellten Ausführungsform sind nur 57 Verbindungen zwischen den
Eingangscodewörtern und den Zellen des ersten Array notwendig, mit 256 notwendigen Verbindungen zwischen den Zellen des zweiten Array und Zellen des ersten Array. Dies ergibt insgesamt 313 Verbindungen, was einer Reduzierung der Komplexität um fast 50% gegenüber dem Stand der Technik gleichkommt, nach dem 608 elektrische Verbindungen zu den Zellen des Einstufen - Array notwendig waren. Bei der Zählung der Anzahl von zwischen den Eingangscodewörtern und jeder Zelle der ersten Array-Stufe erforderlichen Verbindungen ist zu beachten, daß nicht alle Zellen des ersten Array drei separate Verbindungen benötigen werden, wie bei 70, 72, 74 von Fig. 2 gezeigt. Dies ist darauf zurückzuführen, daß das Codewort maximaler Länge in der dargestellten Ausführungsform nur 19 bit ist und das Laden jedes neuen Codeworts an einer Byte-Grenze (d. h. A0, A8, A16 oder A24) einsetzt. So müssen beispielsweise die Zellen A19 bis A23 nur auf zwei mögliche Bits in den hereinkommenden Codewörtern blicken. A19 würde auf Bits D3 und D11 blicken, A20 auf Bits D4 und D12, A21 auf Bits D5 und D13, etc. Ein 19-bit- Codewort, welches entweder bei A0 oder Zelle A24 beginnt, würde nicht in die Zellen A19 bis A23 hineinreichen.
Es sollte nun erkennbar sein, daß die vorliegende Erfindung einen mehrstufigen Ansatz zum Packen von Codewörtern variabler Länge in gleich große Bytes zur Übertragung schafft. Bei der dargestellten Ausführungsform werden die Codewörter in 8-bit- Byte - Grenzen gepackt und organisiert. Codewort-Daten werden in eine erste Daten - Array - Stufe geschrieben, beginnend mit der ersten Stelle eines Byte, welches von einem Byte-Pointer bezeichnet wird. Die Codewort-Daten werden in eine zweite Datenspeicher - Array - Stufe übertragen, beginnend bei einer bestimmten Zelle, die von einem Bit-Pointer innerhalb des von dem Byte-Pointer bezeichneten Byte bezeichnet ist. Der Bit- und der Byte- Pointer werden aus der akkumulierten Länge empfangener Codewörter abgeleitet. Die Zellen der ersten Array-Stufe werden kontinuierlich jeden Taktzyklus aufgefrischt, und ihr Inhalt wird an die zweite Array-Stufe transferiert. Die Zellen der zweiten Array-Stufe werden kontinuierlich von der vorhergehenden Array-Stufe aufgefrischt, mit Ausnahme von denjenigen Zellen, die innerhalb der aktuellen Byte-Grenzen liegen, mit Daten, welche noch nicht aus dem zweiten Array ausgegeben wurden. Sobald in der zweiten Array-Stufe eine Byte-Grenze erreicht und überschritten ist, wird das entsprechende Byte in einen Puffer übernommen, unter Verwendung von Schreib- Strobes, welche von dem Codelängen-Akkumulator erzeugt werden. Ein separater Puffer ist für jedes der Bytes, die in der zweiten Array-Stufe definiert sind, vorgesehen. Die Puffer halten die übernommenen Bytes für die Übertragung.

Claims

1. Packer für Codewörter variabler Länge zur Verwendung bei der Übermittlung von Codewort-Daten in aufeinanderfolgenden m-bit-Bytes, umfassend:

Mittel (86, 104) zum Akkumulieren einer Binärsumme, welche eine über die Zeit empfangene Gesamtzahl von Codewort-Bits anzeigt;

Mittel (104, 106, 108) zum Ableiten einer ersten und einer zweiten Information von der Binärsumme;

ein erstes (20) und zweites (22) Datenspeicher-Array zum Speichern von Codewort-Daten;

Mittel (25) zum Ausgeben eines m-bit-Byte von Codewort - Daten von einem gefüllten zweiten Speicher-Byte, um aufeinanderfolgende m-bit-Bytes von Codewort-Daten bereitzustellen;

dadurch gekennzeichnet, daß die erste Information ein Byte-Pointer (BYTE_PTR) ist, welcher von mindestens einem höchstwertigen Bit der Binärsumme hergeleitet ist;

daß die zweite Information ein Bit-Pointer (BIT_PTR) ist, welcher von einer Mehrzahl von niederwertigsten Bits der Binärsumme hergeleitet ist;

daß das erste Datenspeicher-Array (20) eine Mehrzahl von ersten m-bit-Speicher-Bytes (A0-A7, A8-A15, A16-A23, A24-A31) aufweist und auf den Byte-Pointer anspricht, um Codewort-Daten in den ersten Speicher-Bytes zu speichern;

daß das zweite Datenspeicher-Array (22) eine Mehrzahl von zweiten m-bit-Speicher-Bytes (B0-B7, B8-815, B16-B23, B24-B31) aufweist und auf den Byte- und den Bit-Pointer anspricht, um die zweiten Speicher-Bytes mit Codewort-Daten von dem ersten Datenspeicher-Array (20) zu füllen;

daß die Ausgabe-Mittel (25) ein m-bit-Byte von Codewort - Daten (OUTPUT BYTE 0, OUTPUT BYTE 1, OUTPUT BYTE 2) von jedem gefüllten zweiten Speicher-Byte (B0-B7, B8-B15, B16-B23, B24-B31) ausgeben, um die aufeinanderfolgenden m-bit-Bytes von Codewort-Daten bereitzustellen;

daß hereinkommende Codewörter variabler Länge (CODE WORD) aufeinanderfolgend in dem ersten Datenspeicher - Array (20) gespeichert werden, wobei jedes Codewort am

- Anfang eines ersten Speicher-Byte beginnt, welches durch den Byte-Pointer auf Basis der Binärsumme von vorausgehenden Codewort-Bitlängen identifiziert ist; und

daß jedes der in dem ersten Datenspeicher-Array (20) gespeicherten Codewörter variabler Länge zu dem zweiten Datenspeicher-Array (22) übertragen wird, beginnend an einer Stelle innerhalb eines zweiten Speicher-Byte, die durch den Byte-Pointer und den Bit-Pointer auf Basis der Binärsumme von vorausgehenden Codewort-Bitlängen identifiziert ist.

2. Packer für Codewörter variabler Länge nach Anspruch 1, wobei die hereinkommenden Codewörter in Sätze gruppiert werden, welche eine Mehrzahl von Codewörtern enthalten, wobei der Codewort-Packer ferner umfaßt:

Mittel (100) zum Rücksetzen der akkumulierenden

Mittel (86, 104) auf Null zu Beginn jedes neuen Satzes von Codewörtern.

3. Packer für Codewörter variabler Länge nach Anspruch 1 oder 2, wobei die Codewörter eine maximale Länge von n bit haben, wobei das erste und das zweite Datenspeicher-Array jeweils k Speicher-Bytes umfassen und jedes Speicher-Byte m Bit-Speicherzellen (A0-A31, B0-B31) enthält, wobei

k = [n+m-1) / m].

4. Packer für Codewörter variabler Länge nach einem der vorangehenden Ansprüche, wobei die akkumulierenden Mittel (86, 104) einen q-bit-Akkumulator umfassen, wobei dessen p niederwertigsten Bits den Bit-Pointer bilden und die übrigen (q-p) höchstwertigen Bits den Byte- Pointer bilden, wobei p die Anzahl von Bits ist, die · erforderlich ist, um eine der m Bit-Speicherzellen (B0-B31) in einem Speicherbyte zu identifizieren, und wobei (q-p) die Anzahl von Bits ist, die erforderlich ist, um eines der k Speicherbytes (B0-B7, B8-B15, B16- B23, B24-B31) zu identifizieren.

5. Packer für Codewörter variabler Länge nach einem der vorangehenden Ansprüche, ferner umfassend Zeitgeber - Mittel (21, 23, 87, 89) zum:

Eintakten der Codewort-Daten in das erste Datenspeicher - Array (20), jeweils ein Codewort nach dem anderen,

Eintakten des Byte-Pointers in das erste Datenspeicher - Array (20), wenn ein Codewort dorthinein eingetaktet wird,

Takten der Codewort-Daten aus dem ersten Datenspeicher - Array (20) in das zweite Datenspeicher-Array, jeweils ein Codewort nach dem anderen, und

Eintakten des Byte-Pointers und Bit-Pointers in das zweite Datenspeicher-Array (22), wenn ein Codewort dorthinein eingetaktet wird.

6. Packer für Codewörter variabler Länge nach Anspruch 5, wobei die Codewort-Daten in das zweite Datenspeicher - Array (22) einen Taktzyklus nach ihrem Eintakten in das erste Datenspeicher-Array (20) eingetaktet werden, wobei der Codewort-Packer ferner umfaßt:

Mittel (88) zum Verzögern des Taktens des Byte-Pointers und des Bit-Pointers in das zweite Datenspeicher - Array (22) um einen Taktzyklus.

7. Packer für Codewörter variabler Länge nach einem der vorhergehenden Ansprüche, wobei die Ausgabe-Mittel (25) auf ein Inkrementieren des Byte-Pointers (BYTE_PTR) ansprechen, um Daten von einem zweiten Speicherbyte auszugeben, welches gefüllt worden ist.