DE19635251C2

DE19635251C2 - Verfahren und Apparat zur Komprimierung beliebiger Daten

Info

Publication number: DE19635251C2
Application number: DE19635251A
Authority: DE
Inventors: Michael J Gormish; Edward L Schwartz; Ahmad Zandi; James D Allen
Original assignee: Ricoh Co Ltd
Current assignee: Ricoh Co Ltd
Priority date: 1995-08-31
Filing date: 1996-08-30
Publication date: 2000-03-23
Anticipated expiration: 2016-08-31
Also published as: GB9618143D0; US5710562A; GB2305089B; JP2003133964A; JP3461822B2; JPH09121168A; DE19635251A1; JP3367832B2; GB2305089A

Description

Die vorliegende Erfindung betrifft das Gebiet der Datenkompressions- und Datendekompres sionssysteme; insbesondere betrifft die vorliegende Erfindung Kontextmodelle, die fähig sind, beliebige Daten aufzunehmen, (z. B. Daten aus mehreren Typen von Quellen oder in mehreren Typen von Formaten).

Datenkompression ist ein extrem nützliches Werkzeug, um große Mengen von Daten zu speichern und zu übertragen. Für gewisse Typen von Daten muß eine Kompression immer "verlustfrei" bzw. "lossless" oder "reversibel" sein. Mit anderen Worten müssen die Daten nach der Kompression und Dekompression exakt dieselben sein, wie die Originaldaten. Ver lustfreie Kodierverfahren beinhalten lexikalische Verfahren des Kodierens (z. B. Lempel-Ziv- Familie von Algorithmen), Lauflächen-Kodieren bzw. Run-Length-Kodieren, aufzählendes Kodieren bzw. "enumerative"-Kodieren und Entropie-Kodieren.

Manchmal wird aufgrund der großen Menge von Eingangsdaten und der beschränkten Band weite sogar noch mehr Kompression benötigt. In einem solchen Fall sind die dekomprimier ten Daten vielleicht nicht exakt gleich den Originaldaten, aber sie liegen idealerweise nahe genug bzw. genau genug daran, so daß es einen geringen oder gar keinen Unterschied macht. Wenn die Daten, die nach der Kompression und Dekompression erzeugt werden, nicht exakt dieselben sind, wie die Original-Eingangsdaten, ist das Kodieren verlustbehaftet bzw. "lossy". Verlustbehaftete Kodierverfahren können verlustfreies Kodieren als einen Unterteil bzw. Unterabschnitt beinhalten.

Entropiekodieren besteht aus irgendeinem Verfahren verlustfreien Kodierens, das versucht, Daten zu komprimieren, die nahe an der Entropiegrenze liegen, indem bekannte oder ge schätzte Symbolwahrscheinlichkeiten verwendet werden. Entropiekodieren beinhaltet zum Beispiel Huffman-Kodes, arithmetische Kodes oder binäre Entropiekodes.

Binäre Entropiekodierer sind verlustfreie (d. h. eine perfekte Rekonstruktion ist möglich) Ko dierer, die nur auf binäre (ja/nein) Entscheidungen wirken, die häufig als das höchstwahr scheinliche Symbol (MPS bzw. "most probably symbol") und als das niedrigstwahrscheinli che Symbol (LPS bzw. "least probably symbol") ausgedrückt werden. Beispiele von binären Entropiekodierern beinhalten IBM's Q-Kodierer, ein Kodierer, der hierin als ein FSM-Kodie rer bezeichnet wird, und einen Hochgeschwindigkeitsparallel-Kodierer. Der FSM-Kodierer ist ein binärer Entropiekodierer, der einen Finalautomaten bzw. "finite state machine" zur Kompression verwendet. Zur weiteren Information über FSM-Kodierer, siehe US-Patent Nr. 5,272,473, das den Titel trägt "Method and Apparatus For Entropy Coding" und am 21. De zember 1993 herausgegeben wurde. Zur weiteren Information über ein Beispiel eines Hoch geschwindigkeitsparallelkodierers, siehe US-Patent Nr. 5,381,145, das den Titel trägt "Method and Apparatus for Parallel Decoding and Encoding of Data" und am 10. Januar 1995 herausgegeben wurde.

Alle Datenkompressionssysteme können wenigstens begrifflich in zwei Teile aufgeteilt wer den, nämlich in ein Kontextmodell und einen Kodierer. Zum Kodieren werden Daten in das Kontextmodell eingegeben, das die Eingangsdaten in eine Abfolge von Entscheidungen über setzt und ein Kontext-Bin für jede Entscheidung. Sowohl die Abfolge von Entscheidungen als auch ihre zugehörigen Kontext-Bins werden zu dem Kodierer ausgegeben. Der Kodierer empfängt jedes Kontext-Bin und erzeugt eine Wahrscheinlichkeitsabschätzung für jede Ent scheidung. Der Kodierer bestimmt ebenso, ob die Entscheidung (Ergebnis bzw. Resultat oder Ereignis) in ihrem höchstwahrscheinlichen Zustand ist oder nicht ist. Basierend auf der Wahrscheinlichkeitsabschätzung, der Bestimmung des Kodierers und ob oder ob nicht die Entscheidung wahrscheinlich war, erzeugt der Kodierer einen komprimierten Datenstrom, wobei er keine oder mehrere Bits ausgibt, um die Originaleingangsdaten darzustellen. Zum Dekodieren liefert das Kontextmodell ein Kontext-Bin zu dem Kodierer. Basierend auf dem Kontext-Bin liefert der Kodierer eine Wahrscheinlichkeitsabschätzung, die zusammen mit dem komprimierten Bitstrom den Kodierer veranlaßt, ein Bit zurückzugeben, das darstellt, ob die Entscheidung (d. h. das Ereignis) in ihrem höchstwahrscheinlichen Zustand ist oder nicht. Das Kontextmodell empfängt das Rückgabe-Bit, erzeugt die Originaldaten basierend auf dem empfangenen Bit und aktualisiert das Kontext-Bin für die nächste binäre Ent scheidung.

Das Kontextmodell ist typischerweise anwendungsspezifisch. Das heißt, typischerweise wer den Kontextmodelle basierend auf den Daten gestaltet, die sie empfangen bzw. die sie em pfangen werden. Deswegen sind Kompressions- und Dekompressionssysteme, die Kontextmo delle verwenden, die besonders für einen bestimmten Datentyp gestaltet sind, in der Lage, eine bessere Kompression zu erreichen als jene, die nicht besonders für diese Typen von Da ten, die komprimiert werden, gestaltet werden. Es wäre wünschenswert, ein Kontextmodell zu haben, das mit jeglichem Typ von Daten verwendet werden kann.

Ein "Vorhersage durch den Teil-Abgleich Version-C"-Kodierer (PPMC bzw. "Prediction by Partial Match version C coder"), der von Beil, Cleary und Witten eingeführt wurde, ist eine Markov-Kompressionseinrichtung variabler Ordnung, die einen M-ary (256-ARY) Arithme tik-Kodierer verwendet. Siehe Beil, Cleary, Witten, Text Compression, Prentice Hall, 1990. Das PPMC-Kontextmodell und die M-ary-Arithmetik-Kodierer sind rechenintensiv.

Man betrachte als ein Beispiel der PPMC-Kodierung das "x" in der Zeichenkette "abcabx". Da "abcab" bereits kodiert worden ist, wurden die Kontext-Bins "a", "b" und "c" bereits zu geordnet und initialisiert. In ähnlicher Weise beinhalten Wahrscheinlichkeitsschätzungen oder Kontext-Bins erster Ordnung die Wahrscheinlichkeit von "b", und der Voraussetzung, daß das vorhergehende Zeichen "a" war (P("b" | "a")), die Wahrscheinlichkeit von "c", wenn das vorhergehende Zeichen "b" war (P("c" | "b")) und die Wahrscheinlichkeit von "a", wenn das vorhergehende Zeichen "c" war, (P("a" | "c")). Die Kontext-Bins 2-ter Ordnung, die zugeord net worden sind und initialisiert worden sind, beinhalten die P("c" | "ab") und P("a" | "bc"). Das Kontext-Bin 3-ter Ordnung P("a" | "abc") wurde zugeordnet und initialisiert. Ein PPMC- Kodierer aktualisiert eine Wahrscheinlichkeitsschätzung für jeden diesen Kontext-Bins, wenn kodiert und dekodiert wird. Ein PPMC-Kodierer bewahrt ebenso eine Wahrscheinlichkeits schätzung für andere Kontext-Bins, was ein Escape-Kode bzw. ein Umschalt-Kode ist, der anzeigt, daß ein Kontext niedrigerer Ordnung verwendet werden muß. Diese Escape-Wahr scheinlichkeiten bzw. Umschaltwahrscheinlichkeiten sind dazu da, jene Situationen handzuh aben, wo eine Wahrscheinlichkeit nicht zugewiesen wurde. Ein Kontext "-1"-ter Ordnung, wo jedes Symbol gleich wahrscheinlich ist, wird verwendet, um das erste Auftreten eines je den Symbols handzuhaben.

Tabelle 1 zeigt die Wahrscheinlichkeitsschätzungen für verschiedene Kontext-Bins, wobei γ, β, δ Wahrscheinlichkeitsschätzungen mit Werten zwischen 0 und 1 sind. Es wird angenom men, daß 8-Bit-Zeichen verwendet werden, was zu einem 256-Element-Alphabet führt. Be merkenswert ist, daß in Tabelle 1 "P("c" | "ab") = β" bedeutet, daß unter der Voraussetzung, daß die vorhergehenden zwei Zeichen "ab" waren, die Wahrscheinlichkeitsschätzung dafür, daß das nächste Zeichen "c" ist, β beträgt.

Tabelle 1 - PPMC Kontext-Bins

Um "x" in die Zeichenkette "abcabx" zu kodieren, überprüft der PPMC-Kodierer zuerst, um zu sehen, ob es eine Schätzung 4-ter Ordnung für "x" nach "bcab" gibt, und da es sie nicht gibt, wird ein Escape bzw. eine Umschaltung kodiert. Bemerkenswert ist, daß dies keinen Koderaum verbraucht, wenn die Wahrscheinlichkeit des Escapes bzw. der Umschaltung 1 be trägt. Auf der anderen Seite, bei der Abschätzung 2-ter Ordnung, beträgt die Wahrscheinlich keit des Escapes bzw. der Umschaltung 1-β und nicht 1. Da die Wahrscheinlichkeit nicht mehr 1 beträgt, wird Koderaum verbraucht. Dieser Prozeß wird für jede Ordnung wiederholt und da kein Abgleichen bzw. keine "matches" auftreten, werden die Escapes bzw. Umschal tungen, bis die Ordnung "-1" erreicht ist, kodiert, und dann wird "x" kodiert. Nach dem Ko dieren werden die Wahrscheinlichkeiten aller Ordnungen für das Auftreten von "x" aktuali siert. Die aktualisierten Kontext-Bins sind "bcab", "cab", "ab", "b" und der Kontext 0-ter Ordnung. Wenn nun die Zeicnenkette "bcabx" wieder auftritt, würde das "x" mit dem Kon text-Bin 4-ter Ordnung kodiert werden. Falls die Zeichenkette "zzabx" auftritt, würde das "x" mit einem Kontext-Bin ("ab") 2-ter Ordnung kodiert werden.

Ein Problem mit einem PPMC-Kodierer ist die Verwendung von Escape-Wahrscheinlich keiten. Escape-Wahrscheinlichkeiten werden benötigt, um Schätzungen aufzunehmen bzw. anzupassen, die nicht für ausgewählte Alphabet-Daten in der M-ary-Gesamtheit existieren. Es ist sehr schwierig, genau Wahrscheinlichkeiten den Escape-Kodes zuzuweisen.

Ein anderes Problem bei der Verwendung von PPMC ist, daß es dafür gedacht ist, auf einem großen Allzweck-Rechensystem zu laufen. Jeder Kontext wird durch eine Baum-Struktur lo kalisiert. Wenn der PPMC-Kodierer die Daten komprimiert, wird ein Baum in einer solchen Art und Weise gebaut, daß es angenommen wird, daß der Speicher nicht beschränkt ist. Je doch arbeitet ein derartiges System nicht effizient, wenn der Speicher begrenzt ist, wie zum Beispiel bei integrierten Schaltungen. Deshalb ist es wünschenswert, ein System zu haben, das mehrere Typen von Daten aufnimmt, wenn es durch den Umfang des verfügbaren Spei chers begrenzt ist.

Nahezu alle Allzweck-Datenkompressionsverfahren gründen heutzutage auf einem der zwei Verfahren der lexikalischen Kompression ("Dictionary"-Kompression), die von Ziv und Lem pel beschrieben ist. Diese werden als LZ77 und LZ78 bezeichnet. Diese Verfahren speichern die vorhergehenden Zeichen und kodieren neue Zeichen, indem sie auf Abfolgen durch iden tische vorhergehende Zeichen verweisen. Ziv/Lempel-Verfahren werden in vielen Software- und Hardware-Systemen verwendet.

Eine dynamische Markov-Kompression (DMC) wurde als ein Verfahren vorgeschlagen, bei welchem ein Kontextmodell zur Kompression von Allzweckdaten dynamisch aufgebaut wer den kann. Das Verfahren liefert typischerweise eine bessere Kompression, als die meisten lexikalischen Verfahren. Anstatt daß ein Satz vorhergehender Bits als ein Kontext verwendet wird, verwendet DMC Zustände in einem gerichteten Graphen.

Die vorliegende Erfindung liefert Kontext-Modelle zur Kompression beliebiger Daten.

Zusammengefaßt beschreibt die Erfindung ein Verfahren und ein Apparat zum Kodieren und Dekodieren von Information. Das Verfahren und der Apparat bzw. das Gerät beinhalten ein Modell, das in Hardware oder Software implementiert ist und das in der Lage ist, mit belie bigen Daten zu arbeiten (zum Beispiel Daten eines verschiedenen Typs oder einer Mannigfal tigkeit von Typen). Das Modell erzeugt einen Kontext und binäre Entscheidungen für jedes Symbol. Die vorliegende Erfindung beinhaltet ebenso einen binären Entropie-Kodierer, der Wahrscheinlichkeiten schätzt und einen komprimierten Bitstrom in Antwort auf Kontexte und die binären Entscheidungen von dem Modell erzeugt.

Bei einer Ausführungsform beinhaltet die vorliegende Erfindung ein Kontextmodell, das mit beliebigen Daten betreibbar ist und daß Kontext-Bins verschiedener Ordnungen verwendet, um einen Kontext und eine Entscheidung für jedes Symbol in einem Eingangs-Symbolstrom zu erzeugen. Ein Entropie-Kodierer schätzt Wahrscheinlichkeiten und erzeugt einen kompri mierten Datenstrom in Antwort auf Kontexte und Entscheidungen von dem Modell und ge mäß erzeugter Wahrscheinlichkeitsschätzungen.

Die vorliegende Erfindung wird nun vollständiger von der detaillierten Beschreibung, die unten gegeben wird, verstanden werden und von den begleitenden Zeichnungen verschiedener Ausführungsformen der Erfindung, die jedoch nicht als bezüglich der Erfindung beschrän kend auf die spezifischen Ausführungsformen gesehen werden sollen, sondern sie dienen nur der Erklärung und dem Verständnis. Kurze Beschreibung der Zeichnungen:

Fig. 1A ist ein Blockdiagramm eines binären Entropie-Kodiersystems.

Fig. 1B ist ein Blockdiagramm eines binären Entropie-Dekodiersystems.

Fig. 1C ist ein Blockdiagramm einer Ausführungsform des Kontextmodells der vorliegenden Erfindung.

Fig. 1D ist ein Blockdiagramm einer alternativen Ausführungsform des Kontextmodells der vorliegenden Erfindung.

Fig. 2 zeigt ein Beispiel der Kontext-Aufteilung der vorliegenden Erfindung.

Fig. 3A ist ein Flußdiagramm einer Ausführungsform des Kodier- und Dekodier- Prozesses der vorliegenden Erfindung.

Fig. 3B ist ein Flußdiagramm einer Ausführungsform des Prozesses zum Kodieren von Zeichen gemäß der vorliegenden Erfindung.

Fig. 3C ist ein Flußdiagramm einer Ausführungsform des Prozesses zum Dekodieren von Zeichen gemäß der vorliegenden Erfindung.

Fig. 3D ist ein Flußdiagramm einer Ausführungsform des Prozesses, um Kontexte bestimmter Bits in einem Zeichen gemäß der vorliegenden Erfindung zu bestimmen.

Fig. 3E ist ein Flußdiagramm eine Ausführungsform des Prozesses, um Wahr scheinlichkeits-Schätzungen gemäß der vorliegenden Erfindung zu aktualisie ren.

Fig. 4 zeigt einen Beispiel-DMC-Graphen.

Fig. 5 zeigt ein Blockdiagramm einer Ausführungsform eines DMC-Kontextmodells.

Fig. 6A zeigt einen Beispiel-DMC-Graphen, der einen aufgeteilten Zustand haben soll.

Fig. 6B zeigt einen Beispiel-DMC-Graphen, nachdem der Zustand in der Fig. 6A aufgeteilt worden ist.

Fig. 7 zeigt einen Hashing-Mechanismus der vorliegenden Erfindung.

Fig. 8 ist ein Blockdiagramm einer Ausführungsform einer Parallelkodierer- Implementation.

Fig. 9 ist ein Blockdiagramm einer alternativen Ausführungsform einer Par allelkodierer-Implementation.

Fig. 10 zeigt ein Speicher-"Banking" bzw. eine Vorgehensweise bezüglich Speicher bänke für eine Ausführungsform der vorliegenden Erfindung.

Es folgt eine detaillierte Beschreibung der vorliegenden Erfindung. Ein Kompressions- und ein Dekompressionssystem zum Handhaben beliebiger Daten wird beschrieben. Bei der folgenden detaillierten Beschreibung der vorliegenden Erfindung werden zahlreiche spezifische Details dargelegt, wie zum Beispiel spezifische Datentypen, Anzahl von Bits, etc., um ein gründliches Verständnis der vorliegenden Erfindung bereitzustellen. Jedoch wird es für einen Fachmann offensichtlich sein, daß die vorliegende Erfindung ohne diese spezifischen Details durchgeführt werden kann. In anderen Fällen werden gut bekannte Strukturen und Vorrichtungen in Blockdiagramm gestaltet eher als detailliert gezeigt, um zu vermeiden, daß die vorliegende Erfindung verschleiert wird.

Einige Teile der detaillierten Beschreibungen, die folgt, werden in Termen von Algorithmen und symbolischen Darstellungen von Operationen mit Datenbits innerhalb eines Computer speichers dargestellt. Diese algorithmischen Beschreibungen und Darstellungen sind die Mittel, die von Fachleuten auf den Gebieten der Datenverarbeitung verwendet werden, um am effektivsten das wesentliche ihrer Arbeit anderen Fachleuten zu vermitteln. Ein Algorithmus wird hier und im allgemeinen als eine selbstkonsistente Folge von Schritten verstanden, die zu einem gewünschten Ergebnis führt. Bei den Schritten handelte es sich um solche, die physikalische Manipulationen physikalischer Werte bzw. Quantitäten erfordern. Üblicherweise, obwohl dies nicht notwendig ist, nehmen diese Werte die Form elektrischer oder magnetischer Signale an, die in der Lage sind, gespeichert, übertragen, kombiniert, verglichen oder in sonstiger Weise manipuliert zu werden. Es hat sich zu Zeiten als praktisch erwiesen, grundsätzlich aus Gründen einer allgemeinen Verwendung, diese Signale als Bits, Werte, Elemente, Symbole, Zeichen, Terme, Zahlen bzw. Nummern oder dergleichen zu bezeichnen.

Es sollte jedoch im Gedächtnis behalten werden, daß alle diese und ähnliche Terme mit geeigneten physikalischen Werten bzw. Größen verbunden sind und es sich nur um herkömmliche Bezeichnungen handelt, die diesen Werten bzw. Größen beigelegt werden. Soweit es nicht besonders anders festgestellt wird, wie dies von der folgenden Diskussion klar wird, wird man begrüßen, daß bei der vorliegenden Erfindung die Diskussionen, die durchgehend Terme, wie zum Beispiel "Verarbeiten" oder "Berechnen" oder "Errechnen" oder "Bestimmen" oder "Anzeigen" oder dergleichen verwenden, auf Wirkungen bzw. Tätigkeiten und Prozesse bzw. Verarbeitungsschritte eines Computersystems oder einer ähnlichen Rechenvorrichtung bezugnehmen, die (elektronische) Größen bzw. Werte innerhalb der Register und Speicher des Computersystems in andere Daten ummanipulieren und transferieren bzw. übertragen, die als physikalische Größen bzw. physikalische Werte innerhalb der Speicher oder Register oder anderen derartigen Informationsspeicherein richtungen des Computersystems, oder in Übertragungs- oder Anzeigevorrichtungen dargestellt werden.

Die vorliegende Erfindung betrifft ebenso einen Apparat bzw. eine Vorrichtung, um die Operationen darin durchzuführen. Dieser Apparat bzw. diese Vorrichtung kann für die erforderlichen Zwecke besonders konstruiert bzw. aufgebaut werden oder er kann einen Allzweck-Computer aufweisen, der selektiv durch ein Computerprogramm, das in den Computer gespeichert ist, aktiviert oder rekonfiguriert wird. Die Algorithmen und Anzeigen, die hierin vorgestellt werden, weisen nicht inhärent einen Bezug zu irgendeinem bestimmten Computer oder einen anderen Apparat auf. Verschiedene Allzweck-Maschinen können mit Programmen verwendet werden, die mit der hierin gegebenen Lehre übereinstimmen, oder es kann sich als passend erweisen, einen spezialisierteren Apparat zu konstruieren, um die erforderlichen Verfahrensschritte durchzuführen. Die erforderliche Struktur für eine Mannigfaltigkeit dieser Maschinen wird von der folgenden Beschreibung klar werden. Zusätzlich wird die Erfindung nicht unter Bezugnahme auf eine bestimmte Programmier sprache beschrieben. Man wird es zu schätzen wissen, daß eine Mannigfaltigkeit von Programmiersprachen verwendet werden kann, um die Lehren der hierin beschriebenen Erfindung zu implementieren.

Es folgt ein Überblick über die vorliegende Erfindung

Die vorliegende Erfindung liefert ein Kompressions- und Dekompressionssystem mit einem Kontextmodell und einem binären Entropiekodierer. Fig. 1A zeigt eine Ausführungsform des Kompressionssystems der vorliegenden Erfindung, wohingegen Fig. 1B eine Ausführungsform des Dekompressionssystems der vorliegenden Erfindung zeigt. Das Kompressionssystem und das Dekompressionssystem arbeiten zusammen, um ein verlustfreies Kompressionsschema auszubilden.

Nimmt man Bezug auf die Fig. 1A, so werden Originaldaten 101 in das Kontextmodell 102 eingegeben. Bei den Originaldaten 101 kann es sich um beliebige Daten handeln. Mit anderen Worten können die Originaldaten 101 eine Mannigfaltigkeit von Typen von Daten aufweisen, wie zum Beispiel Daten von einem Text, lauffähige Files bzw. Dateien (Exe-Dateien), Quellendateien bzw. Source Files, Bilder, numerische Daten, etc. Derartige Daten können von einer Mannigfaltigkeit von Quellen, wie zum Beispiel Netzwerken, Diskettenlaufwerken, Blitz-Speichern bzw. Flash-Speichern ("flash memories"), magneto-optische Platten, optische Platten, Scanner oder andere Sensoren, etc. abgeleitet werden.

In Antwort auf die Daten 101 erzeugt ein Kontextmodell 102 einen Satz oder eine Sequenz bzw. eine Folge von Entscheidungen. Bei einer Ausführungsform weist jede Entscheidung eine binäre Entscheidung auf. Das Kontextmodell 102 liefert ebenso einen Kontext für jede Entscheidung. Das Kontextmodell 102 gibt einen Kontext 103 und ein Resultat aus, das auf das Ergebnis der Entscheidung hinweist. Für einen binären Entropie-Kodierer weist das Resultat 104 ein einziges Bit auf. Bei einer Ausführungsform kann das Kontextmodell 102 einen Kode (Wahrscheinlichkeitsklasse) ausgeben.

Ein binärer Entropie-Kodierer 105 empfängt den Kontext 103 und das Resultat 104 und erzeugt einen komprimierten Bitstrom 106. In Antwort auf diese Eingänge schätzt der binäre Entropie-Kodierer 105 die Wahrscheinlichkeit der Eingänge bzw. Eingangssignale und versucht, komprimierte Daten 106 als einen Bitstrom bzw. in Form eines Bitstroms mit einer Länge zu erzeugen, die so nahe, wie es vernünftigerweise möglich ist, an der Entropie der Wahrscheinlichkeitsschätzung liegt. Bei einer Ausführungsform kann der binäre Entropie- Kodierer 105 einen Kodierer aufweisen, wie er im US-Patent Nr. 5,381,145 beschrieben ist, das den Titel "Method and Apparatus for Parallel Decoding and Encoding of Data" trägt und am 10. Januar 1995 herausgegeben wurde oder der Entropie-Kodierer 105 kann einen Finalautomat-Binärkodierer aufweisen, wie er zum Beispiel im US-Patent Nr. 5,272,478 beschrieben ist, das den Titel trägt "Method and Apparatus for Entropy Coding" und das am 21. Dezember 1993 herausgegeben wurde.

Obwohl nur ein binärer Entropiekodierer gezeigt ist, nimmt das Kontextmodell der vorliegenden Erfindung beliebige Daten auf und kann mit mehreren binären Kompressions einrichtungen parallel arbeiten. Bei einer Ausführungsform ist das Kontextmodell mit mehreren Kodierern gekoppelt, wobei jeder Kodierer einem bestimmten Abschnitt des hereinkommenden Bitstroms zugewiesen ist. Eine derartige Ausführungsform ist im US- Patent Nr. 5,272,478 gezeigt.

Obwohl die vorliegende Erfindung ein verlustfreies Kompressionssystem bereitstellt, kann die vorliegende Erfindung als ein verlustbehaftetes Kompressionssystem konfiguriert werden und immer noch eine bessere Kompression bereitstellen, als Systeme, die gemäß dem Stand der Technik verfügbar sind und die beliebige Daten aufnehmen.

Nimmt man Bezug auf Fig. 1B, so führt eine Ausführungsform eines Dekompressions systems, das ein Kontextmodell 108 und einen binären Entropie-Kodieren 107 aufweist, den umgekehrten Prozeß durch, um die komprimierten Daten 106 zu dekomprimieren. Der binäre Entropie-Kodierer 107 empfängt einen Kontext 109 von dem Kontextmodell 108 sowie einen komprimierten Datenstrom 106. Basierend auf dem Kontext 109 erzeugt der binäre Entropie- Kodierer 107 eine Wahrscheinlichkeitsschätzung (oder eine Klasse von Schätzungen). Bei einer Ausführungsform gibt das Kontextmodell 108 einen Kode (Wahrscheinlichkeitsklasse) zu dem binären Entropie-Kodierer 107 aus.

In Antwort auf die Eingänge bzw. Eingangssignale erzeugt der binäre Entropie-Kodierer 107 ein Resultat 110, das darauf hinweist, ob eine Entscheidung in dem höchstwahrscheinlichen Zustand war oder nicht. Bei einer Ausführungsform gibt der binäre Entropie-Kodierer 107 einen Bit-Hinweis zurück, der für das Auftreten des wahrscheinlichen Ereignisses repräsentativ ist. In Antwort auf das Resultat 110 erzeugt das Kontextmodell 108 die Originaldaten 101.

Fig. 1C ist ein Blockdiagramm einer Ausführungsform des Kontextmodells der Fig. 1A und 1B. Nimmt man Bezug auf Fig. 1C, so werden die Originaldateien 131 in den Geschichte-Block bzw. Gedächtnis-Block 132 eingegeben. Der Geschichte-Block 132 puffert vorhergehende Bytes oder andere Dateneinheiten. Der Geschichte-Block 132 ist ebenso angeschlossen, um das gegenwärtige Bit 133 zu empfangen oder zu übertragen. Basierend auf den Originaldaten 131 und dem gegenwärtigen Bit 133 erzeugt der Geschichte-Block 132 Geschichte-Information 134.

Der Adressenerzeugungsblock 138 ist angeschlossen, um die Geschichte-Information 134 (oder einen Abschnitt davon) zu empfangen. In Antwort auf die Geschichte-Information 134 erzeugt der Adressenerzeugungsblock 138 mehrere Adressen, um auf mehrere Speicherbänke 135 zuzugreifen. Bei einer Ausführungsform weist der Adressenerzeugungsblock 138 einen Hashing-Mechanismus auf. Der Ausgang des Speichers 135 weist mehrere Kontexte auf. Ein Auswahl-Block 136 ist angeschlossen, um die Kontexte von dem Speicher 135 sowie auch Geschichte-Information 134 zu empfangen. Basierend auf der Geschichte-Information 134 und Information von dem Speicher 135 wählt der Auswahl-Block 136 den besten potentiellen Kontext 139 aus den Kontexten von dem Speicher 135 aus. Kontext 139 kann herausgegeben werden oder optional in einem Wahrscheinlichkeits-Schätzblock 137 eingegeben werden. Der Wahrscheinlichkeits-Schätzblock 137 empfängt ebenso das gegenwärtige Bit bzw. aktuelle Bit. In Antwort auf diese Eingänge erzeugt der Wahrscheinlichkeits-Schätzblock 137 einen Kode (z. B. Wahrscheinlichkeitsklasse) und ein Resultat. Dies wiederum wird zu einem komprimierten Bitstrom konvertiert.

Fig. 1D ist ein Blockdiagramm einer alternativen Ausführungsform des Kontextmodells der Fig. 1A und 1B. Nimmt man Bezug auf Fig. 1D, so werden Originaldaten 150 als ein Eingang empfangen und können (optional) in einer Puffereinheit 152 gepuffert werden. Ein Abschnitt bzw. Teil der Originaldaten ist das Resultat 151. Ein Zustand 141 (z. B. Register) speichert den gegenwärtigen Zustand 142, den sie als nächsten Zustand 153 von der Auswahleinrichtung 149 empfängt. Der Speicher 143 enthält mehrere Bänke und ist angeschlossen, um den gegenwärtigen Zustand 142 zu empfangen. In Antwort auf den gegenwärtigen Zustand 142 wird auf den Speicher 143 zugegriffen und dieser liefert Zählpulse bzw. eine Anzahl 146 und mögliche nächste Zustände 145. Ein Zählstand-zu-Kode- Block bzw. ein Anzahl-zu-Kode-Block 144 ist angeschlossen, um die Zählpulse 146 bzw. die Anzahl 146 zu empfangen und er erzeugt in Antwort darauf einen Kode 147. Bewerkenswert ist, daß der Kode 147 einen Kontext oder eine Wahrscheinlichkeitsklasse (optional) aufweisen kann.

Eine Auswahleinrichtung 149 ist angeschlossen, um das Resultat 151 und mögliche nächste Zustände 145 zu empfangen. Basierend auf dem gegenwärtigen Bit wählt der Selektor 149 einen nächsten Zustand 153 aus den möglichen nächsten Zuständen 145 aus, der dann zum Zustand 141 übertragen wird.

Der Aktualisierer/Aufteil-Block 148 ist angeschlossen, um Zählpulse 146, mögliche nächste Zustände 145 und das Resultat 151 zu empfangen. In Antwort auf diese Eingänge aktualisiert der Aktualisier/Aufteil-Block 148 die Zählpulse bzw. die Anzahl und sendet die neuen Zählpulse bzw. die neue Anzahl zu dem Speicher 143. Der Aktualisierer/Aufteil-Block 148 bestimmt ebenso, ob es bezüglich irgendeines Zustandes nötig ist, ihn aufzuteilen und, falls dem so ist, so sendet er die neuen Zustände zu dem Speicher 143. Das Aufteilen von Zuständen und andere Aspekte, die mit diesem Kontextmodell in Beziehung stehen, werden unten näher beschrieben.

Es wird eine Ausführungsform des Kontextmodells der vorliegenden Erfindung beschrieben

Eine Ausführungsform des Kontextmodells der vorliegenden Erfindung verwendet mehrere Ordnungen binärer Markov-Kontexte. Bei einem derartigen Kontextmodell kann es sich um das Kontextmodell handeln, das in der Fig. 1C beschrieben ist.

Bei einer Ausführungsform weist die vorliegende Erfindung ein Kontextmodell auf, das Kontexte 0-ter Ordnung, Kontexte 1-ter Ordnung, Kontexte 2-ter Ordnung etc. verwendet.

Die vorliegende Erfindung stellt Kontextmodelle höherer variabler Ordnung bereit, die die N-te Ordnung für N größer oder gleich 2 annähern. Indem eine Reihe von Kontextmodell- Ordnungen verwendet wird, ist das Kontextmodell der vorliegenden Erfindung in der Lage, Entscheidungen und Kontexte in Antwort auf beliebige Daten zu erzeugen.

Bei der vorliegenden Erfindung verwendet das Kontextmodell 0-ter Ordnung keine Geschichte früherer bzw. vorhergehender Symbole. Das Kodieren wird einfach nach der Häufigkeit des Auftretens von jedem Symbol in dem Alphabet durchgeführt. Bei einer Ausführungsform verwendet das Kontextmodell der vorliegenden Erfindung Bytes von Daten. In einem derartigen Fall beinhaltet das Alphabet 256 Symbole.

Bei der vorliegenden Erfindung werden, wenn ein Kontextmodell 0-ter Ordnung mit einem binären Entropie-Kodierer verwendet wird, acht Binärentscheidungen für jedes Symbol (zumindest) gemacht. Um M-ary-Statistiken 0-ter Ordnung zu modellieren, werden binäre Entscheidungen nicht unabhängig gemacht und werden sequentiell mit jeder binären Entscheidung durchgeführt, indem alle vorhergehenden Entscheidungen in dem selben Symbol als ein Kontext verwendet werden.

Bei einer Ausführungsform verwendet ein Kontextmodell 1-ter Ordnung ein vorhergehendes Byte einer Markov Zustandsinformation. In einem derartigen Fall werden 16 Bits einer Kontextinformation für eine Anzahl von 256 × 255 von Kontext-Bins benötigt. Die 16 Bits an Information entsprechen 8 Bits des vorhergehenden Bytes und 8 Bits (mit einen ungenutzten Wert) für die Kontexte 0-ter Ordnung.

Bei einer Ausführungsform verwendet ein Kontextmodell 2-ter Ordnung zwei vorhergehende Bytes einer Markov-Zustandsinformation. In einem derartigen Fall werden 24 Bits an Kontextinformation für 256 × 256 × 255 Kontext-Bins verwendet. Von den 24 Bits dienen 16 Bits für die zwei vorhergehenden Bytes und 8 Bits der Beschreibung der Symbolhäufigkeit.

Ein Kontextmodell N-ter Ordnung verwendet N vorhergehende Bytes einer Standard information und es benötigt 8 × (N + 1) Bits für 2^8N× 255 Kontext-Bins. Bemerkenswert ist, daß das vorhergehende Byte oder die vorhergehenden Bytes, die für den Kontext verwendet werden, nicht das unmittelbar vorausgehende Byte sein muß bzw. nicht die unmittelbar vorausgehenden Bytes sein müssen. Stattdessen kann es vorteilhaft sein, Kontexte darzulegen, die auf Bytes oder Daten basieren, die ein regelmäßig auftretendes Muster, aber ein Überspring-Muster aufweisen. Zum Beispiel können in dem Fall der RGB-Daten alle Kontexte, die zu den roten Daten in Beziehung stehen, basierend nur auf Bytes der roten Daten modelliert werden, die bereits bekannt sind, und zwar derart, daß Bytes blauer und grüner Daten übersprungen werden.

Bei der vorliegenden Erfindung sind nicht alle Kontexte die gesamte Zeit während des Kodierprozesses verfügbar oder aktiv. Anfänglich sind nur Kontexte niedrigerer Ordnung aktiv, während Kontexte höherer Ordnung beim Fortschreiten des Kodierens aktiv werden. Im allgemeinen leiden Kontextmodelle höherer Ordnung an dem Problem, daß eine enormale Anzahl von Wahrscheinlichkeitsschätzungen benötigt werden und nur eine geringe Datenmenge in vielen der Kontext-Bits auftreten kann. Dies führt zu vielen schlechten Wahrscheinlichkeitsschätzungen. Die vorliegende Erfindung beschleunigt die Wahrscheinlich keitsschätzung, indem adaptiv Modelle unterschiedlicher Ordnung verwendet werden. Die vorliegende Erfindung verwendet einen Kontext niedrigerer Ordnung, bis ein bestimmter Kontext höherer Ordnung häufig genug auftritt, so daß es vernünftig genug ist, zu erwarten, daß eine gute Wahrscheinlichkeitsschätzung gemacht werden kann und daß die Verwendung eines Modells höherer Ordnung eine bessere Kompression ermöglichen wird. Zu diesem Zeitpunkt wird der Kontext "aufgeteilt", wodurch ermöglicht wird, daß der bestimmte Kontext hoher Ordnung verwendet wird. Das Aufteilen der Kontext-Bins niedrigerer Ordnung, um die Verwendung der Kontext-Bins höherer Ordnung zu ermöglichen, wird unten beschrieben. Bemerkenswert ist, daß der Aufteil-Mechanismus, der oben diskutiert wurde, anders ist als das Aufteilen, das in der Alternativen DMC-Ausführungsform unterhalb des Kontextmodells beschrieben ist.

Bei einer Ausführungsform der vorliegenden Erfindung untersucht das Kontextmodell alle verschiedenen möglichen Ordnungen, um das aktive Kontext-Bin höchster Ordnung zu bestimmen, das auf das Bit zutrifft bzw. auf dieses anzuwenden ist, und kodiert mit dieser Ordnung. Bemerkenswert ist, daß der Kontext aktiv ist, falls eine Wahrscheinlichkeitsschät zung für ihn existiert. Das Kontextmodell der vorliegenden Erfindung sucht von der höchsten Ordnung zu der niedrigsten Ordnung, um ein aktives Kontext-Bin zu finden, um jedes Bit zu kodieren. Somit versucht das Kontextmodell Bits mit der höchsten Anzahl an vorher gehenden Zeichen, die man nutzen kann, zu kodieren und arbeitet sich nach unten, wobei mit der höchstmöglichen Ordnung kodiert wird. Der untenstehende Pseudokode stellt die Betriebsweise des Kontextmodells dar:

Bemerkenswert ist, daß bei einer Ausführungsform das Kontextmodell zu einer Stelle im Speicher hasht bzw. gemäß des Hashing-Verfahrens übergeht, die für den Kontext verwendet wird, um zu bestimmen, ob er aktiv ist. Das Hashing wird genauer unten beschrieben.

Die höchste verfügbare Ordnung muß nicht immer verwendet werden, um die Daten zu modellieren. Zum Beispiel kann die Wahrscheinlichkeitsschätzung für einen Kontext niedrigerer Ordnung besser sein (d. h. repräsentativer sein) als die höhere Ordnung und somit einen besseren Kandidaten darstellen. Die Bestimmung, wann eine höhere verfügbare Ordnung eines Kontextes verwendet wird, liegt in der Hand des Gestalters bzw. ist eine Sache der Ausgestaltung.

Bei einer Ausführungsform sind nur die Kontext-Bins 0-ter Ordnung anfänglich aktiv. Deshalb verwendet die gesamte Kodierung Kontext-Bins 0-ter Ordnung. Wenn jeder Kontext 0-ter Ordnung verwendet ist, wird die Statistik bzw. die statistischen Daten, die den Kontexten 1-ter Ordnung entsprechen, aktualisiert. Während jeder Aktualisierung bestimmt die Kontext-Aufteillogik der vorliegenden Erfindung, ob ein bestimmtes Kontext-Bin 1-ter Ordnung zur weiteren Verwendung aktiviert werden sollte. Nur nachdem ein Kontext-Bin 0- ter Ordnung verwendet wurde, kann ein Kontext-Bin 1-ter Ordnung aktiviert werden. In ähnlicher Weise wird, wenn einmal ein Kontext-Bin 1-ter Ordnung verwendet wurde, ein Kontext-Bin 2-ter Ordnung aktualisiert. Dies schreitet fort, bis alle Kontext-Bins, die von den Daten verwendet werden und von der bestimmten Implementation der vorliegenden Erfindung unterstützt werden, aktiv sind.

Die Anzahl an Ordnungen, die durch die bestimmte Implementation unterstützt werden, ist auf die maximale Anzahl erlaubter Ordnungen beschränkt. Die maximal erlaubte Anzahl an Ordnungen kann von dem verfügbaren Speicher abhängen, um Kontexte und Wahrscheinlich keitsschätzungen in dem System zu speichern. Die maximale Ordnung kann drei, vier, fünf, sechs oder von höherer Ordnung sein, insbesondere falls die Zeichen weniger als 8 Bits sind.

Obwohl die oben beschriebene Ausführungsform ein Kontextmodell erläutert, das mit Kontexten 0-ter Ordnung beginnt, ist dies kein Erfordernis. Die Kontextmodelle können mit Kontexten N-ter Ordnung beginnen, wo N gleich 1 oder größer ist. Die vorliegende Erfindung kann verwendet werden, wo eine anfängliche Anzahl von Kontexten verschiedener Ordnungen verwendet und später angepaßt werden.

Bei einer Ausführungsform wird, unter der Voraussetzung, daß eine Wahl zwischen der Verwendung mehrerer Kontext-Bins verschiedener Ordnungen gegeben ist, der Kodierer mit den am meisten versetzten bzw. assymetrischen Kontext-Bins, der dasselbe MPS (höchst wahrscheinliche Symbol bzw. "most probable symbol") wie das Kontext-Bin höchster Ordnung, das zuvor aufgetreten ist, aufweist, ausgewählt. In einem derartigen Fall werden die PEM-Zustände der Kontext-Bins, die nicht zum Kodieren verwendet werden, die aber hätten verwendet werden können, aktualisiert, falls die MPS sich nicht von der beim Kodieren verwendeten MPS unterscheidet und die Anzahl von Malen, die der Kontext getroffen worden ist, geringer ist als eine Schwelle, die genauer unten beschrieben wird. Es ist zu bemerken, daß das Treffen eines Kontextes bedeutet, ihn zum Kodieren zu verwenden oder eine Ordnung tiefer zum Kodieren zu verwenden.

Fig. 2 zeigt ein Beispiel der adaptiven bzw. angepaßten Kontextmodell-Verarbeitung der vorliegenden Erfindung, die Kontexte höherer Ordnung während des Kodierens von Daten verwendet. Nimmt man Bezug auf Fig. 2, so ist ein Strom von Datenbits gezeigt, der XY- Paare von Datenbits darstellt und der von rechts nach links kodiert wird. Die "XY"-Paare sind zwei Bits, die zu einer Zeit kodiert werden (2-Bit-Symbole), wobei die Ordnungs- Auswahl auf Symbolen und nicht auf Bits basiert. Anfänglich ist die Wahrscheinlichkeit eines X(p(x)) gleich 50%. Die Wahrscheinlichkeit von Y gleich 1 zu sein, wenn x gleich 0 ist, (p(y = 1 | x = 0)) beträgt 50%. In ähnlicher Weise ist die Wahrscheinlichkeit von Y gleich 1 zu sein, wenn X gleich 1 ist (p(y | x = 1)) ebenso 50%. Nach der Kodierung des ersten X, d. h. des ersten Bits, wird die Wahrscheinlichkeit, daß X eine 1 ist, erhöht (++).

Wenn das zweite Bit kodiert wird, wird es basierend auf der Tatsache, daß das × 1 ist und die Wahrscheinlichkeit von Y gleich 1 zu sein, wenn X gleich 1 ist, wird erniedrigt (--). In ähnlicher Weise nimmt die Wahrscheinlichkeit von X gleich 1 zu sein ab, wenn ein drittes Bit kodiert wird. Jedoch wird bei diesem Punkt der erste Kontext "1-ter Ordnung" erzeugt (d. h. p(x | b)) und seine Wahrscheinlichkeit wird verringert. Das heißt, die Wahrscheinlichkeit von X gleich 1 zu sein, wenn es "b" folgt, nimmt ab.

Wenn das vierte Bit gezählt wird, wird es in seiner Wahrscheinlichkeit kodiert und die Wahrscheinlichkeit von Y gleich 1 zu sein, wenn X gleich 0 ist, nimmt ab. Jedoch wird bei diesem Punkt ein neuer Kontext erzeugt. Der erzeugte Kontext ist die Wahrscheinlichkeit von Y gleich 1 zu sein, wenn ein X gleich 0 und ein "b" vorausgeht. Diese Wahrscheinlichkeit von Y gleich 1 zu sein wird verringert. Der Prozeß bzw. das Verfahren schreitet fort, wobei verschiedene Wahrscheinlichkeiten erzeugt werden.

Zu bemerken ist, daß, wenn bei der siebten Bitposition, wo die Wahrscheinlichkeit von X gleich 1 zu sein, wenn ein "b" vorhergeht, verringert wird, die Wahrscheinlichkeit von X von sich selbst (p(x)) nicht mehr aktualisiert wird noch als ein Kontext verwendet wird. Darüberhinaus wird ein neuer Kontext erzeugt, die p(x | b, a). Das heißt, der Kontext von der Wahrscheinlichkeit von X gleich 1 zu sein, wenn ein "b" und "a" vorhergeht, wird erzeugt und seine Wahrscheinlichkeit 1 zu sein, wird verringert. Dies ist der erste Kontext "2-ter Ordnung". Wenn das nächste Y-Bit kodiert wird, ist die Wahrscheinlichkeit von Y gleich 1 zu sein, wenn es von einem X gleich 0 und einem "b" gefolgt wird, der Kontext und wird dekrementiert bzw. verringert. Zu bemerken ist, daß der erste Kontext nicht mehr aktualisiert wird oder in diesem Fall verwendet wird.

Es wird die Kontextaufteilung und schnelle Adaption bzw. schnelle Anpassung beschrieben

Die Kontext-Aufteilungslogik der vorliegenden Erfindung bestimmt, wann ein neues Kontext- Bin aktiviert werden soll. Um zu bestimmen, wann ein neues Kontext-Bin zu aktivieren ist, gleicht das Kontextmodell der vorliegenden Erfindung zwei im Konflikt stehende Ziele aus. Zum einen wünscht die Kontext-Aufteillogik soviel vergangene Geschichte wie möglich zu verwenden. Mit anderen Worten, das Kontextmodell wünscht soviele Kontext-Bins hoher Ordnung wie möglich zu verwenden, was es ermöglicht, zukünftige Daten vorherzusagen und gut zu kodieren. Jedoch erlaubt die Verwendung weniger Kontext-Bins Implementationen in der Praxis, insbesondere dann, wenn weniger Speicher verfügbar ist, und erlaubt, daß gute Wahrscheinlichkeitsschätzungen für jeden Kontext durchgeführt werden. Weniger Kontext- Bins und gute Wahrscheinlichkeitsschätzungen bedeuten mehr Daten pro Kontext, was für eine gute Kompression erforderlich ist.

Bei einer Ausführungsform wird ein Kontext-Bin besonders hoher Ordnung aktiviert, wenn ein Zähl-Wert eine Schwelle erreicht. Jedesmal wenn ein Kontext-Bin N-ter Ordnung verwendet wird, wird ein Zähl-Wert für einen zugeordneten Kontext N-1-ter Ordnung inkrementiert. Falls der Zählwert um eine Konstante jedesmal erhöht wird, wenn ein Kontext verwendet wird, gewährleistet dann das Warten, bis der Schwellwert erreicht ist, daß der Kontext häufig genug verwendet wird, so daß es vernünftig ist, zu erwarten, daß eine gute Wahrscheinlichkeitsschätzung für ihn bestimmt werden kann. Der Schwellwert wird basierend darauf gewählt, wie lange es braucht, um eine gute Wahrscheinlichkeitsschätzung zu erhalten. Bei einer Ausführungsform ist der Schwellwert 7.

Bei einer alternativen Ausführungsform wird der Umfang, um den der Wert imkrementiert bzw. erhöht wird, dazu in Beziehung gesetzt, wie nahe die Wahrscheinlichkeitsschätzung des Kontextes N-ter Ordnung an 50% liegt. Für ein System auf R-Kodierer-Basis, das eine Zustandstabelle verwendet, wie zum Beispiel eine Tabelle, die im US-Patent Nr. 5,272,478 offenbart ist, wo ein Wahrscheinlichkeits-Schätz- (PEM- bzw. "probability estimation"-) Zustand 0 für die 50%-Wahrscheinlichkeitsklasse ist und der maximale PEM-Zustand für die assymetrischste bzw. am meisten versetzte Wahrscheinlichkeitsklasse ist, ist der Umfang zum Erhöhen der maximale PEM-Zustand minus dem gegenwärtigen PEM-Zustand.

Bei einer Ausführungsform wird sich ein Kontext-Bin, das an einem maximalen Assymetrie- Kode bzw. Versetz-Kode angepaßt ist, nicht aufteilen, um Kontexte höherer Ordnung zu verwenden. Dies ist vorteilhaft, da es bereits mit dem maximalen Umfang kodiert wurde und nichts dadurch gewonnen werden kann, in dem zu einem höheren Kontext übergegangen wird. Das Kodieren des höchstwertigen Bits von ASCII-Files bzw. einer ASCII-Dateien, das immer 0 ist, ist ein Beispiel dafür, wo das Modell 0-ter Ordnung die gesamte mögliche Kompression erzielt, und das Aufteilen des Kontextes, um Modelle höherer Ordnung zu verwenden, nicht wünschenswert ist. Bei einer Ausführungsform wird das Aufteilen von Kontexten, die schlecht komprimiert worden sind, bevorzugt. Mit anderen Worten, es werden jene bevorzugt, die einen geringen Versatz bzw. eine geringe Assymetrie aufweisen.

Es wird die Wahrscheinlichkeitsschätzungs-Beschleunigung für aktivierten Kontext beschrieben

Die vorliegende Erfindung stellt eine verbesserte Kompression durch die Verwendung einer Adaptionsrate bzw. -geschwindigkeit der Wahrscheinlichkeitsschätzung bereit. Bei einer Ausführungsform, wo R-Kodes in einer PEM-Zustandstabelle verwendet werden, kann ein Satz von Zuständen anfänglich verwendet werden, um eine schnelle Adaption zu gewähr leisten. Ein Beispiel einer derartigen Tabelle ist in der US-Patentanmeldung mit der Seriennummer 08/172,646 gezeigt, die den Titel. "Method and Apparatus for Parallel Encoding and Decoding of Data" trägt und die am 23. Dezember 1993 eingereicht wurde.

Wenn ein Kontext-Bin einen Schwellwert erreicht und aktiviert wird, existieren verschiedene Wahlmöglichkeiten für die Wahrscheinlichkeitsschätzung für das Kontext-Bin. Ein Default- bzw. voreingestellter 0 PEM-Zustand kann verwendet werden. Alternativ kann der PEM- Zustand von dem Kontext niedrigerer Ordnung verwendet werden. Eine andere Alternative ist es, die Bits zu verfolgen, die in dem inaktiven Kontext von N + 1-ter Ordnung kodiert worden wären, wenn Daten in dem Kontext N-ter Ordnung kodiert werden, so daß eine gute anfängliche Wahrscheinlichkeitsschätzung gemacht werden kann. Bei einer Ausführungsform wird eine Aufzeichnung vorhergehender Bits zur Verwendung bei der Bestimmung des korrekten höchstwahrscheinlichen Symbols (MPS) für ein neu aktiviertes Kontext-Bin bewahrt, das dann mit dem PEM-Zustand von dem Kontext-Bin niedriger Ordnung verwendet wird.

Andere Beschleunigungen für die Wahrscheinlichkeitsschätzung beinhalten das folgende. Falls das MPS ("most probable symbol") des Kontextes höherer Ordnung sich von dem Kontext niedrigerer Ordnung unterscheidet, kann der PEM-Zustand von einem Kontext oder beiden Kontexten erhöht werden. Falls kein niedrigstwahrscheinliches Symbol (LPS bzw. "least probable symbol") in dem Kontext höherer Ordnung vor der Aktivierung auftritt, kann der PEM-Zustand des Kontextes höherer Ordnung erhöht werden. Diese Typen von Be schleunigung sind leicht in Hardware oder Software von Fachleuten implementierbar.

Es wird die Zuweisung und der Zugriff von Speicher für Kontexte beschrieben

Bei der vorliegenden Erfindung wird Speicher Kontexten zugeordnet, da sie verwendet werden, um den Bedarf große Speicher zu haben, zu vermeiden. Deshalb ist das Kon textmodell der vorliegenden Erfindung zur Verwendung in Systemen mit beschränktem Speicher vorgesehen. Die Entscheidung, ob Speicher einem Kontext-Bin höherer Ordnung zugeordnet wird, wird basierend auf der Tatsache, daß der Speicher begrenzt ist, getroffen. Die vorliegende Erfindung verwendet ebenso Hashing, um zu versuchen, so viele Kontexte hoher Ordnung wie möglich bei einem festen Speicherumfang zu verwenden. Zum Beispiel wird Hashing verwendet, um 24-Bit-Kontexte auf 2⁸ oder 2¹⁶ Speicherstellen zu verringern, die verwendet werden können, falls verfügbar. Die vorliegende Erfindung löst Hash- Kollisionen, indem Kontexte niedrigerer Ordnung verwendet werden, so daß Kontext-Bins niemals beliebig kombiniert werden. Die Verwendung von Hashing in der vorliegenden Erfindung vermeidet die Verwendung zeitaufwendiger Suchoperationen und wird später beschrieben.

Bei einer Ausführungsform liefert die vorliegende. Erfindung keinen Speicher für jeden möglichen Kontext, insbesondere für alle Kontexte 2-ter Ordnung und höherer Ordnung. Bei der vorliegenden Erfindung wird Speicher Kontexten höherer Ordnung zugewiesen, indem eine Hashing-Funktion verwendet wird. Bei einer Ausführungsform werden alle Kontexte 2- ter und 3-ter Ordnung Speicher über Hashing zugewiesen. Zum Beispiel kann eine 64K- Speicherbank den 24M möglichen Kontexten 2-ter Ordnung zugewiesen werden.

Die Speicherstelle für jeden gehashten Kontext beinhaltet zusätzlich zu der Wahrscheinlich keitsschätzungs-Kontextaufteilungs-Information, die volle Beschreibung des Kontextes, der dem Hash-Wert zugewiesen ist. Wenn eine Hash-Kollision auftritt, ist es nur dem Kontext, der mit der vollen Beschreibung des Kontextes übereinstimmt, erlaubt, die bestimmte gehashte Speicherstelle zu verwenden. Eine gehashte Kontext-Speicherstelle ist einem einzigen Kontext zugewiesen und Hashing veranlaßt nicht irgendeinen Kontext kombiniert zu werden.

Es gibt zahlreiche mögliche Hashing-Funktionen. Bei einer Ausführungsform kann die vorliegende Erfindung Hashing-Funktionen, wie zum Beispiel modulare Arithmetic Exklusiv- Oder-Bäume, Nachschlagtabellen (LUTS bzw "look-up tables ") mit Zufallswerten, etc. verwenden. Eine einzige Hashing-Funktion kann auf mehrere Speicherstellen zeigen oder mehrere Hashing-Funktionen können verwendet werden. Bei einer Ausführungsform wird [A + 137B] Modulo (MOD) 256 als eine Hashing-Funktion für zwei 8-Bit-Werte A und B verwendet und verwendet vier Speicherstellen pro Hash-Wert. Kontext-Bins 0-ter und 1-ter Ordnung verwenden nicht Hashing. Ein Kontext zweiter Ordnung verwendet eine 64K- Speicherbank, die durch 8 Bits vom Hashing der zwei vorhergehenden Zeichen und 8 Bits vom Hashing des vorhergehenden Zeichens und der Information 0-ter Ordnung adressiert werden. Kontexte 3-ter Ordnung verwenden 64K-Speicherbänke, die von 8 Bits vom Hashing des vorhergehenden Zeichens und der Information 0-ter Ordnung und 8 Bit vom Hashing des zweiten und dritten nächstvorhergehenden Zeichens adressiert werden.

Fig. 7 zeigt das Hashing der vorliegenden Erfindung. Nimmt man Bezug auf Fig. 7, so wird ein Hash durchgeführt, indem ein Hashing-Mechanismus 701 durchgeführt wird, der vergangene Geschichte und eine Bitposition empfängt, um eine Adresse 702 zu erzeugen. Bei einer Ausführungsform werden separate bzw. getrennte Bänke für jede Bitposition verwendet. In diesem Fall erzeugt der Hashing-Mechanismus 701 die Adresse 702 in Antwort auf die vergangene-Geschichte- bzw. Vergangenheits-Information. Die Adresse 702 ist dazu bestimmt, den Kontextspeicher 704 zu veranlassen, Zugriff zu haben. Bei einer Ausführungs form weist jeder Eintrag des Kontextspeichers 704 eine Wahrscheinlichkeitsschätzung und einen vollen Kontext auf. Bemerkenswert ist, daß die Wahrscheinlichkeitsschätzung Zählpulse anstatt nur Zustände sein kann. Eine vorbestimmte Anzahl von Einträgen wird jedem Hash- Wert (Adresse) zugewiesen. Bei einer Ausführungsform werden vier Kontext-Bins jedem Hash-Wert zugewiesen. Wenn der Hash-Wert 702 erzeugt wird, werden die mehreren Kontexte bzw. Vielfach-Kontexte (z. B. 4), die dem Hash-Wert 702 entsprechen, aus dem Kontext-Speicher 704 gelesen. Zu diesem Punkt bzw. Zeitpunkt wird der volle Kontext verglichen, um zu bestimmen, welcher der mehreren Kontexte bzw. Vielfach-Kontexte der aktuelle Kontext ist. Indem ein derartiges Hashing-Schema verwendet wird, wird die Anzahl der Suchoperationen, die ansonsten benötigt werden, um den Kontext zu erhalten, verringert.

Es werden adaptive Kontexte 1-ter Ordnung beschrieben

Ein grundsätzlicher Unterschied zwischen der vorliegenden Erfindung und PPMC beim Stand der Technik ist, daß die vorliegende Erfindung wählt, wann Kontexte aufgeteilt werden. Eine der Folgen dieses Merkmals ist es, daß adaptiv unter sich gegenseitig ausschließenden Kontextmodell-Bins gewählt werden kann bzw. eine Auswahl getroffen werden kann. Dies ermöglicht es, verschiedene Kontextmodelle 1-ter Ordnung für Daten zu verwenden, die nicht in Bytes vorliegen. Zum Beispiel kann für 16-Bit-Daten der beste Vorhersager 1-ter Ordnung das zweite nächstvorhergehende Byte und nicht das vorhergehende Byte sein. Eine Ausführungsform der vorliegenden Erfindung, die Hashing verwendet, ermöglicht es, den Kontext 1-ter Ordnung das vorhergehende, zweitnächstvorhergehende, drittnächstvorher gehende bzw. viertnächstvorhergehende Byte zu verwenden, um gute Vorhersagen für 8-Bit-, 16-Bit-, 24-Bit- bzw. 32-Bit-Daten zu liefern. Bemerkenswerterweise muß die Größe der Daten nicht spezifiziert werden, sie wird adaptiv bzw. angepaßt bestimmt. Ein anderes sich gegenseitig ausschließendes Kontextmodell, das nützlich sein könnte, wäre eins, daß die adaptive Auswahl der Verwendung von 8-Bit-, 16-Bit-, 24-Bit- oder 32-Bit-Differenzen für numerische Daten erlaubt.

Es wird die Kodier/Dekodier-Verarbeitung der vorliegenden Erfindung beschrieben

Bei einer Ausführungsform arbeitet die vorliegende Erfindung auf Bit-Ebenen, um vom Parallelismus einen Vorteil zu ziehen. Dies ermöglicht es, daß ein Eingangsdatenstrom fortschreitend um Bit-Ebenen kodiert wird und vielleicht zukünftige Daten auf vorhergehende Bit-Ebenen als Kontext für nachfolgende Bit-Ebenen anzuwenden. Bei einer alternativen Ausführungsform können große Abschnitte fester Größe parallel kodiert werden. Bei wieder einer anderen alternativen Ausführungsform können große Abschnitte von Daten variabler Größe parallel beginnend mit Kontext-Bins 0-ter Ordnung verarbeitet werden.

Es sollte bemerkt werden, daß ein Ablauf bzw. ein Betrieb bei hohen Geschwindigkeiten einen großen Umfang von Speicher-Bandbreite erfordert. Bei einer Ausführungsform kann auf den Speicher, der einem Kontextmodell jeder Ordnung zugeordnet ist, gleichzeitig zugegriffen werden.

Fig. 3A-3E zeigen das Kodier- und Dekodierverfahren der vorliegenden Erfindung. Es sollte bemerkt werden, daß das Verarbeiten durch eine auschließlich für diesen Zweck bestimmte Hardware oder Software oder eine Kombination von beiden durchgeführt werden kann. Zum Beispiel kann der Prozeß durch ein Computersystem, indem Software abläuft, durchgeführt werden.

Nimmt man Bezug auf Fig. 3A, so ist ein Flußdiagramm des Kodier- und Dekodier prozesses der vorliegenden Erfindung gezeigt. Der Prozeß der vorliegenden Erfindung beginnt damit, daß die Verarbeitungslogik den "Treffer-" bzw. "Hit-" und "Abgleich-" bzw. "Match-"Speicher für Kontexte von Ordnungen größer als 0 initialisiert (Verarbeitungsblock 301). Der "Treffer" bezieht sich auf einen Verwendungs-Zähler, der anzeigt, wie häufig ein bestimmter Kontext zur Kompression verwendet worden ist. Ein Schwellwert kann in dem Speicher mit beinhaltet werden, um ihn bei der Bestimmung des Zählstandes, bei dem ein Kontext aufgeteilt werden kann, zu verwenden. Der "Abgleich-" bzw. "Match"-Speicher nimmt auf den Speicher bezug, der die vollen Kontexte speichert. Als nächstes wird der Wahrscheinlichkeits-Schätz-Speicher für jeden Kontext initialisiert (Verarbeitungsblock 302). Bei einer Ausführungsform wird eine Gruppe von Kontexten als immer aktiv initialisiert, wie zum Beispiel die Kontexte 0-ter Ordnung, und die übrigen Kontexte werden als inaktiv initialisiert, aber es wird ihnen erlaubt, später aktiv zu sein. Zuletzt initialisiert als Teil des Initialisierungsprozesses die Verarbeitungslogik den Entropie-Kodierer (Verarbeitungsblock 303). Bemerkenswert ist, daß die Initialisierung des Entropie-Kodierers ein optionaler Schritt ist, der gestaltet ist, um den Entropie-Kodierer in einen voreingestellten bzw. Default- Initialisierungszustand einzustellen, und zwar derartig, daß, wenn der Entropie-Kodierer ein Satz von Zuständen, die zu Beginn der Verarbeitung verwendet werden, aufweist, eine schnelle Adaption bzw. Anpassung bereitgestellt wird.

Ein Test bestimmt dann, ob der Prozeß im Durchführen von Kodieren oder Dekodieren besteht (Verarbeitungsblock 304). Falls der Prozeß in der Durchführung von Kodieren besteht, schreitet der Prozeß beim Verarbeitungsblock 305 fort, wo die Verarbeitungslogik Zeichen kodiert. Nach entweder dem Kodieren oder Dekodieren der Zeichen endet die Verarbeitung.

Fig. 3B zeigt eine Ausführungsform des Prozesses zur Kodierung von Zeichen gemäß der vorliegenden Erfindung. Nimmt man Bezug auf die Fig. 3B, so beginnt der Prozeß damit, daß die Verarbeitungslogik testet, ob alle Zeichen kodiert worden sind (Verarbeitungsblock 310). Falls alle Zeichen kodiert worden sind, schreitet die Verarbeitungslogik bei dem Verarbeitungsblock 311 fort, wo die Verarbeitungslogik den Entropie-Kodierer räumt, nach dieser Zeit endet der Prozeß bzw. die Verarbeitung. Das Räumen des Entropie-Kodierers kann durchgeführt werden, um den Entropie-Kodierer zurückzusetzen. Bemerkenswert ist, daß dies ein optionaler Schritt ist und nicht bei allen Implementationen benötigt wird.

Falls nicht alle Zeichen kodiert worden sind, schreitet der Prozeß bei dem Verarbeitungs block 312 fort, wo die vorliegende Erfindung das nächste Zeichen "c" erhält. Danach setzt die Verarbeitungslogik den Wert einer Variablen i auf die höchstwertige Bitposition des Zeichens c (Verarbeitungsblock 313) und den Wert einer Variablen b auf Bit i des Zeichens c (Verarbeitungsblock 314).

Dann bestimmt die Verarbeitungslogik den Kontext für Bit i des nächsten Zeichens (Ver arbeitungsblock 315). Danach kodiert der Verarbeitungsblock den Wert der Variablen b mit dem Kontext (Verarbeitungsblock 316), aktualisiert die Wahrscheinlichkeit (Verarbeitungs block 317) und dekrementiert dann den Wert der Variablen i (Verarbeitungsblock 318).

Ein Test bestimmt dann, ob der Wert der Variablen i größer als oder gleich 0 ist (Ver arbeitungsblock 319). Falls der Wert der Variablen i größer als oder gleich 0 ist, kehrt der Prozeß mit einer Schleife zu dem Verarbeitungsblock 314 zurück. Falls der Wert der Variablen i nicht größer als oder gleich 0 ist, schreitet der Prozeß beim Verarbeitungsblock 320 fort, wo die vergangene Zeichen-Geschichte bzw. Zeichen-Vergangenheit durch die Verarbeitungslogik aktualisiert wird. Nachdem die vergangene Zeichengeschichte bzw. Zeichen-Vergangenheit aktualisiert worden ist, schreitet die Verarbeitung beim Verarbei tungsblock 310 fort.

Fig. 3C zeigt eine Ausführungsform des Prozesses der Dekodierung von Zeichen gemäß der vorliegenden Erfindung. Nimmt man Bezug auf Fig. 3C, so beginnt der Prozeß zum Dekodieren von Zeichen, indem die Verarbeitungslogik testet, ob alle Zeichen dekodiert worden sind (Verarbeitungsblock 320). Falls nicht alle Zeichen dekodiert worden sind, endet die Verarbeitung. Falls alle Zeichen dekodiert worden sind, schreitet der Prozeß beim Verarbeitungsblock 321 fort, wo die Verarbeitungslogik den Wert einer Variablen i auf die höchstwertige Bitposition des Zeichens initialisiert und dann den Kontext für Bit i des nächsten Zeichens bestimmt (Verarbeitungsblock 322). Nach der Bestimmung des Kontextes für Bit i dekodiert die Verarbeitungslogik das Bit i des nächsten Zeichens (Verarbeitungs block 323), aktualisiert seine Wahrscheinlichkeit (Verarbeitungsblock 324) und dekremen tiert den Wert der Variablen i um 1 (Verarbeitungsblock 325).

Ein Test bestimmt dann, ob der Wert der Variablen i größer als oder gleich 0 ist (Verarbeitungsblock 326). Falls der Wert der Variablen i größer als oder gleich 0 ist, schreitet die Verarbeitung zum Verarbeitungsblock 322 fort. Auf der anderen Seite, falls der Wert der Variablen i nicht größer als oder gleich 0 ist, schreitet der Prozeß beim Verarbeitungsblock 327 fort, wo die Verarbeitungslogik die vergangene Zeichen-Geschichte bzw. Zeichen-Vergangenheit aktualisiert. Nach dem Aktualisieren der vergangenen Zeichengeschichte bzw. Zeichen-Vergangenheit gibt die Verarbeitungslogik das Zeichen aus (Verarbeitungsblock 328) und die Verarbeitung schreitet zum Verarbeitungsblock 320 fort.

Fig. 3D zeigt den Prozeß zur Bestimmung des Kontextes des Bits i des nächsten Zeichens. Nimmt man Bezug auf Fig. 3D, so beginnt der Prozeß damit, daß die Verarbeitungslogik die Speicheradresse des "Treffers", des "Abgleichs" und der Wahrscheinlichkeitsschätzung für den Kontext der Ordnung 2 oder größer bestimmt, indem vergangene Geschichte bzw. Vergangenheit und Hashing verwendet wird (Verarbeitungsblock 330). Als nächstes bestimmt die Verarbeitungslogik die Speicheradresse des "Treffers" und die Wahrscheinlichkeitsschät zung für Kontexte der Ordnung 0 und 1, indem vergangene Geschichte bzw. Vergangenheit verwendet wird (Verarbeitungsblock 331). Nachdem die notwendigen Speicheradressen bestimmt worden sind, setzt die Verarbeitungslogik eine Variable j, die die gegenwärtige Ordnung darstellt, auf 0 (Verarbeitungsblock 332).

Die Verarbeitungslogik bestimmt dann, ob die Ordnung j weniger als 2 ist. Falls der Wert der Ordnungsvariablen geringer als 2 ist, schreitet der Prozeß beim Verarbeitungsblock 339 fort, wo eine Variable flag[j] gesetzt wird. Bemerkenswert ist, daß die Varible flag[j] anzeigt, daß Kontextspeicher zu der Ordnung j für die gegenwärtige Geschichte zugewiesen ist. Falls die Ordnung j weniger als 2 ist, schreitet der Prozeß bei dem Verarbeitungsblock 335 fort, wo ein Test bestimmt, ob der match[j] ("match" steht für Abgleich bzw. Übereinstimmung) auf einen Anfangswert gesetzt ist, der auf eine Speicherstelle hinweist, die gegenwärtig nicht Kontextinformation speichert (jedoch später verwendet werden kann). Falls match[j] einem Anfangswert gleicht, schreitet der Prozeß zum Verarbeitungsblock 336 fort, wo die Verarbeitungslogik match[j] auf den vollen Kontext setzt. Danach schreitet der Prozeß beim Verarbeitungsblock 339 fort. Falls match[j] nicht gleich dem Anfangswert ist, schreitet der Prozeß beim Verarbeitungsblock 337 fort, wo die Verarbeitungslogik bestimmt, ob match[j] gleich einem vollen Kontext gesetzt ist. Falls match[j] gleich einem vollen Kontext gesetzt ist, schreitet der Prozeß beim Verarbeitungsblock 339 fort. Falls match[j] nicht gleich dem vollen Kontext gesetzt ist, schreitet die Verarbeitung beim Verarbeitungs block 338 fort, wo flag[j] gelöscht wird.

Nach dem Löschen oder Setzen des flags erhöht bzw. inkrementiert die Verarbeitungslogik den Wert der Variablen j um 1 (Verarbeitungsblock 340) und testet, ob der Wert der Variablen j geringer als oder gleich ist der maximalen Ordnung (Verarbeitungsblock 341). Falls der Wert der Variablen j geringer ist oder gleich ist der maximalen Ordnung, schreitet der Prozeß beim Verarbeitungsblock 334 fort. Falls der Wert der Variablen j nicht geringer oder gleich der maximalen Ordnung ist, schreitet der Prozeß beim Verarbeitungsblock 342 fort, wo der Wert der Variablen j gleich der maximalen Ordnung gesetzt wird.

Nachdem der Wert der Variablen j auf die maximale Ordnung gesetzt wurde, setzt die Verarbeitungslogik eine temporäre Variable, die "bestskew" ("beste Assymetrie" bzw. "bester Versatz") genannt wird, die verwendet wird, um die Assymetrie bzw. den Versatz zu vergleichen (Verarbeitungsblock 343). Die bestskew-Variable wird anfänglich auf -1,0 oder einen ungültigen Wert gesetzt. Nachdem die bestskew-Variable initialisiert worden ist, bestimmt der Verarbeitungsblock, ob flag[j] gesetzt ist, (Verarbeitungsblock 344). Falls flag[j] nicht gesetzt ist, schreitet die Verarbeitung beim Verarbeitungsblock 351 fort. Falls die Verarbeitungslogik bestimmt, daß flag[j] gesetzt ist, schreitet die Verarbeitungslogik zum Verarbeitungsblock 345 fort, wo sie bestimmt, ob der Wert der bestskew-Variable gleich einem Anfangswert ist. Falls der Wert der bestskew-Variablen auf einen Anfangswert gesetzt ist, schreitet der Prozeß beim Verarbeitungsblock 346 fort, wo die Verarbeitungslogik eine Variable bestMPS gleich MPS[j] (das MPS der Ordnung j, MPS ist das höchswahrscheinliche Symbol bzw. "most probable symbol") setzt.

Danach schreitet der Prozeß beim Verarbeitungsblock 349 fort, wo die Verarbeitungslogik den Wert der bestskew-Variablen gleich skew[j] (die Wahrscheinlichkeitsschätzung der Variablen j; skew steht für Versatz bzw. Assymetrie) setzt und eine bestorder-Variable gleich j setzt (Verarbeitungsblock 350). Auf der anderen Seite, falls der Wert der bestskew- Variablen nicht gleich einem Anfangswert ist, schreitet der Prozeß beim Verarbeitungsblock 347 fort, wo die Verarbeitungslogik testet, ob der Wert der bestMPS-Variablen gleich MPS[j] ist. Falls der Wert der Variablen bestMPS nicht auf MPS[j] gesetzt wird, schreitet dann der Prozeß beim Verarbeitungsblock 351 fort. Falls der Wert der bestMPS-Variablen MPS[j] gleicht, dann testet die Verarbeitungslogik, ob skew[j] größer ist als der beste "skew" bzw. die beste Assymetrie, wie sie durch den Wert der bestskew-Variablen dargelegt ist (Verarbeitungsblock 348). Falls skew[j] größer als der Wert der bestskew-Variablen ist, schreitet der Prozeß beim Verarbeitungsblock 349 fort. Falls skew[j] nicht größer ist als der Wert der bestskew-Variablen, schreitet der Prozeß beim Verarbeitungsblock 351 fort.

Nachdem die Verarbeitungslogik bestimmt, daß skew[j] nicht größer ist, als der Wert der bestskew-Variable oder nachdem die bestorder-Variable gleich der maximalen Ordnung gesetzt worden ist, dekrementiert die Verarbeitungslogik die Variable j um 1 (Verarbeitungs block 351). Dann testet die Verarbeitungslogik, ob der Wert der Variablen j größer als oder gleich 0 ist (Verarbeitungsblock 352). Falls der Wert der Variablen j größer oder gleich 0 ist, schreitet der Prozeß beim Verarbeitungsblock 344 fort. Falls der Wert der Variablen j nicht größer als oder gleich 0 ist, schreitet der Prozeß beim Verarbeitungsblock 353 fort, wo der Wert der "Treffer-"Variablen bzw. "hits-"Variablen für "bestorder" ("beste Ordnung") um 1 inkromentiert wird. Nach dem Inkrementieren der Treffer-Variablen bzw. hits- Variablen, bestimmt ein Test, ob der Wert der bestorder-Variablen geringer ist als die maximale Ordnung (Verarbeitungsblock 354). Falls der Wert der bestorder-Variablen geringer ist als die maximale Ordnung, inkrementiert die Verarbeitungslogik den Wert der hits-Variablen bzw. Treffer-Variablen für bestorder + 1 um 1 (Verarbeitungsblock 355). Nachdem der Wert der hits-Variablen inkrementiert wurde oder nachdem bestimmt wurde, daß der Wert der bestorder-Variablen nicht geringer ist als die maximale Ordnung, endet die Verarbeitung.

Fig. 3E zeigt den Prozeß zur Aktualisierung der Wahrscheinlichkeit eines bestimmten Kontextes. Nimmt man Bezug auf Fig. 3E, so beginnt der Prozeß damit, daß die Verarbeitungslogik die Wahrscheinlichkeitsschätzung der besten Ordnung aktualisiert (Verarbeitungsblock 360). Dann initialisiert die Verarbeitungslogik den Wert einer Variablen j auf 0 (Verarbeitungsblock 361). Die Verarbeitungslogik bestimmt dann, ob flag[j] gesetzt ist (Verarbeitungsblock 362). Falls flag[j] nicht gesetzt ist, schreitet der Prozeß beim Verarbeitungsblock 368 fort. Jedoch schreitet der Prozeß, falls flag[j] gesetzt ist, beim Verarbeitungsblock 363 fort, wo die Verarbeitungslogik bestimmt, ob der Wert der Variablen j gleich der bestorder-Variablen gesetzt ist. Falls der Wert der Variablen j gleich dem Wert der bestorder-Variablen gesetzt ist, schreitet der Prozeß beim Verarbeitungsblock 368 fort. Ansonsten schreitet der Prozeß beim Verarbeitungsblock 364 fort, wo die Verarbeitungslogik bestimmt, ob skew[j] gleich einem Anfangswert gesetzt ist. Falls skew[j] gleich einem Anfangswert gesetzt ist, schreitet der Prozeß beim Verarbeitungsblock 366 fort. Ansonsten schreitet der Prozeß beim Verarbeitungsblock 365 fort.

Beim Verarbeitungsblock 365 bestimmt die Verarbeitungslogik, ob MPS[j] gleich dem Wert der Variablen bestMPS gesetzt ist. Falls MPS[j] nicht gleich dem Wert der bestMPS- Variablen gesetzt ist, schreitet der Prozeß beim Verarbeitungsblock 368 fort. Ansonsten schreitet der Prozeß beim Verarbeitungsblock 366 fort, wo die Verarbeitungslogik bestimmt, ob der Wert von hits[j] geringer ist als ein vorbestimmter Schwellenwert. Falls hits[j] nicht geringer ist als ein vorbestimmter Schwellenwert, schreitet der Prozeß beim Verarbeitungs block 368 fort; ansonsten schreitet der Prozeß beim Verarbeitungsblock 367 fort, wo die Verarbeitungslogik die Wahrscheinlichkeitsschätzung von Ordnung j aktualisiert. Dann schreitet der Prozeß beim Verarbeitungsblock 368 fort, wo der Wert der Variablen j um 1 inkrementiert wird. Dann bestimmt die Verarbeitungslogik, ob der Wert der Variablen j geringer als oder gleich der maximalen Ordnung ist. Falls der Wert der Variablen j geringer als oder gleich der maximalen Ordnung ist, schreitet der Prozeß beim Verarbeitungsblock 362 fort; ansonsten endet der Prozeß.

Es wird die dynamische Markov-Kompression (DMC bzw. "Dynamic Markov Compression.") als ein alternatives Kontextmodell beschrieben

Eine alternative Ausführungsform des Kontextmodells der vorliegenden Erfindung (gezeigt in Fig. 1D) weist ein dynamisches Markov-Kompressions-(DMC)Kontextmodell auf, das dynamisch zur Kompression beliebiger Daten aufgebaut ist. Das DMC-Kontextmodell liefert eine bessere Kompression als die meisten (Hardware-) lexikalischen Verfahren. Bemerkens wert ist, daß dieses Kontextmodell als ein Kontextmodell implementiert werden kann, das in Fig. 1D gezeigt ist.

Anstatt daß ein Satz vorhergehender Bits als ein Kontext verwendet wird, verwendet DMC einen Zustand in einem gerichteten Graphen. Ein Beispiel eines derartigen Graphen ist in Fig. 4 gezeigt. "Geschichte" wird in jedem Zustand gespeichert, da ein gegebener Zustand nur mit einer bestimmten Abfolge von Bits erreicht werden kann. Ein Graph kann mit 8 Zuständen begonnen werden, die eine Bitposition darstellen, oder mit einem Satz von Zuständen, die eine gewisse Anzahl von in Beziehung stehenden vorhergehenden Bits und die Bitposition erfassen. Während des Kodierprozesses wird es manchen Zuständen erlaubt, aufgeteilt zu werden. Jedoch weisen nach dem Aufteilen von Zuständen manche Zustände zusätzlich "Geschichte" oder "Erinnerung bzw. Speicher" auf, da eine spezifischere Abfolge benötigt wird, um sie zu erreichen. Zum Beispiel weisen manche Zustände nur ein Bit an Geschichte auf, während andere Zustände viele Bits an Geschichte aufweisen können. Idealerweise wächst der Graph, um genau den gegenwärtigen Datenstrom vorherzusagen. Das Wachsen des Graphens hängt von den kodierten Daten ab.

Bei jeder Position in dem Graphen wird ein Zählstand der Anzahl von Eins-Bits und Null- Bits gehalten, die in dem Zustand aufgetreten sind. Diese werden sowohl dazu verwendet, die Wahrscheinlichkeit eines Eins-Bits für das nächste Mal, wenn in den Zustand eingetreten wird, abzuschätzen, als auch dazu, um zu bestimmen, ob ein Zustand in zwei verschiedene Zustände aufgeteilt werden soll. Jeder Zustand beinhaltet zwei Zeiger auf die Zustände, die nach einem Eins-Bit und nach einem Null-Bit verwendet werden.

Nimmt man Bezug auf Fig. 4, so sind die Bögen mit dem unkomprimierten Bit (0 oder 1) und mit dem Zählstand der vorhergehenden Bits, die in den Zustand aufgetreten sind, beschriftet. Falls das Kodieren in dem am weitesten links befindlichen Zustand, dem Zustand 0 begonnen wird, zeigt der Zustand in dem Graphen die Bitposition Modulo 4 an. Wie gezeigt ist, gibt es keine Unterscheidung für den Wert von vorhergehenden Bits (sowohl Null- als auch Eins-Bits führen zu demselben nächsten Zustand). Eine Schätzung der Zählpulse offenbart, daß in dem Zustand 0 ein Null-Bit nahezu immer auftritt, so daß eine gute Kompression erhalten werden kann. Im Zustand 3 sind Null-Bits und Eins-Bits gleichwahrscheinlich.

Ein Beispiel-Zustandsspeicher, der dem Zustandsdiagramm in Fig. 4 zugeordnet ist, ist in der Tabelle 2 unten gezeigt:

Tabelle 2

Das Kodierverfahren ist wie folgt:

1. Bestimme das nächste Bit (Eins oder Null) in dem unkomprimierten File bzw. in der unkomprimierten Datei.
2. Um eine "eins"-binäre Entscheidung bzw. eine binäre Entscheidung betreffend Eins zu kodieren, verwende eine Wahrscheinlichkeit, die durch die number_of_ones/(number_of_ones + number_of_zeros) bestimmt ist bzw. durch die Anzahl der Einsen geteilt durch die Summe aus der Anzahl der Einsen und der Anzahl der Nullen bestimmt ist. Um eine Null zu kodieren, kodiere Eins minus dieser Wahrscheinlichkeit.
3. Aktualisiere den Zählstand für das Bit, das auftrat.
4. Ändere den nächsten Zustand für das Bit, das auftrat.

Ein Blockdiagramm, das dieses Verfahren implementiert, ist in Fig. 5 gezeigt. Nimmt man Bezug auf Fig. 5, so erhält ein Zustandsregister 501 den gegenwärtigen Zustand aufrecht. Der Zustand in dem Zustandsregister 501 wird durch einen Multiplexor (MUX) 502 bereitgestellt, der die nächsten Zustände aus dem Speicher 504 für den Fall empfängt, daß das gegenwärtige Bit eine Eins oder eine Null ist. Verwendet man das gegenwärtige Bit als ein Auswahlsignal für MUX 502, so liefert MUX 502 einen der zwei Zustände zu dem Zustandregister 501.

Die gegenwärtigen 0 und 1 Zählpulse für den Zustand, der durch das Zustandsregister 501 spezifiziert ist, werden von dem Speicher 504 zu der Zähllogik 503 gesendet, die entweder den 0- oder 1-Zählstand inkrementiert, und zwar basierend auf dem Wert des gegenwärtigen Bits. Nachdem einer der Zählstände inkrementiert worden ist, werden sie zurück in den Speicher 504 gespeichert.

Die 0- und 1-Zählstände vom Speicher 504 werden ebenso zu der Logik 505 (vor dem Aktualisieren) gesendet, die die Zählstände in einen Kode konvertiert. Bei einer Ausführungs form weist die Logik 505 eine Nachschlagtabelle (LUT bzw. "look-up table") auf. Die Ausganslogik 505 weist einen Kode und ein MPS auf, die von einem Parallel-Kodierer 506 empfangen werden, der den komprimierten Bitstrom liefert.

Da der Dekoder die Zählstände kennt, bevor sie aktualisiert werden, kann er das kodierte Bit von dem komprimierten Bitstrom bestimmen. Dann kann der Dekoder die Zählstände bzw. Zählpulse aktualisieren und denselben nächsten Zustand wie der Kodierer auswählen.

Es wird die Adaption bzw. das Anpassen des Kontextmodells beschrieben

Um die bestmögliche Kompression bereitzustellen, wird der Graph ausgeweitet, indem selektiv ein Zustand in zwei Zustände aufgeteilt wird. Dies wird unten als Adaption bzw. Anpassung bezeichnet. Bei einer Ausführungsform werden die Wahrscheinlichkeitsschätzungs-Zählpulse -Zählstände verwendet, um zu entscheiden, wann der Graph vergrößert werden soll. Aus diesem Grund ist es wichtig, wahre Zählpulse bzw. Zählstände zu haben, anstatt nur pseudo-zufällige Schätzungen.

Nachdem ein Bit kodiert worden ist (Schritt 2 oben) und bevor der Zähler aktualisiert wurde (Schritt 3 oben), wird eine Entscheidung darüber getroffen, ob der Zustand, in den gerade eingetreten wird, aufgeteilt wird. Bei einer Ausführungsform gibt es zwei Bedingungen, die bestehen müssen, bevor ein Zustand aufgeteilt wird: Der Zählstand des Zweiges, der gerade genommen wird, liegt oberhalb einer ersten Schwelle und in den Zustand, in den gerade eingetreten wird, wurde begonnen einzutreten, indem Zweige, die sich von dem gegenwärti gen Zweig unterscheiden, häufiger als eine zweite Schwelle verwendet wurden. Wenn beide Bedingungen erfüllt sind, wird der Zustand, in den gerade eingetreten wird, aufgeteilt. Der Zweig, der dabei war zu dem alten Zustand überzugehen, wird geändert und ein neuer Zustand wird erzeugt und in ihn eingetreten. Alle Zweige von anderen Zuständen zeigen weiterhin auf den alten Zustand.

Die Schwellen, die in den beiden Aufteil-Bedingungen verwendet werden, werden hierin als MINcnt1 und MINcnt2 bezeichnet. Die Zählpulse bzw. der Zählstand für die Zweige werden zwischen dem neuen Zustand und dem alten Zustand proportional zu dem Zählstand auf dem gegenwärtigen Zweig und den gesamten Verwendungen des alten Zustandes aufgeteilt. Der neue Zustand verwendet dieselben nächsten Zustände (für Null- und Eins-Bits), wie es der alte Zustand tat.

Dieses Zustands-Aufteilen ist in Fig. 6A und 6B erläutert. In Fig. 6A sind mehrere Zustände zusammen mit den Zweigen gezeigt. Die Zweige sind mit dem Eingangsbit und der Anzahl von Malen, die der Zweig verwendet wurde, beschriftet. Der Zweig von Zustand 4 und Zustand 5, der mit "1,6" beschriftet wurde, bedeutet, daß der Zustand 5 der nächste Zustand sein wird, wenn ein Eins-Bit das Eingangssigna 30102 00070 552 001000280000000200012000285912999100040 0002019635251 00004 29983l ist, und dies geschah sechsmal. Jeder Zustand weist zwei Zweige auf, aber Zweige, die nicht für dieses Beispiel wichtig sind, wurden in der Figur weggelassen (zum Beispiel der Zweig für ein Null-Bit im Zustand 1).

Tabelle 3 zeigt ein Zustands-Speicher, der der Fig. 6A zugeordnet ist. Bemerkenswert ist, daß die Stellen mit Strichen Werte beinhalten, die weggelassen wurde, um zu vermeiden, daß das folgende Beispiel verschleiert wird. Der Zustand 120 ist der ungenutzte Zustand, der zum Aufteilen verfügbar ist.

Tabelle 3

Man nehme für diese Darstellung an, daß MINcnt1 gleich 5 ist und MINcnt2 gleich 3 ist. Falls das Kodieren gegenwärtig im Zustand 1 durchgeführt wird und ein Eins-Bit auftritt, würde der nächste Zustand normalerweise Zustand 4 sein. Als erstes wird eine Überprüfung durchgeführt, um zu sehen, ob der Zustand 4 aufgeteilt werden sollte. Eine Bedingung ist es, daß der Zweig, der gerade genommen wird, mehr als MINcnt1-mal genommen wurde. Da MINcnt1 weniger als 8 ist, ist dies in dem Beispiel wahr bzw. trifft zu. Die zweite Bedingung ist, daß in dem Zustand 4 mehr als MINcnt2-mal von anderen Zuständen eingetreten worden ist. Dies wird bestimmt, indem die Anzahl von Malen, die der Zustand 4 verlassen wurde, addiert wird (6 + 6) und die Anzahl von Malen, die der aktive Zweig verwendet wurde, 8, substrahiert wird. Da MINcnt2 drei ist, wird diese Bedingung ebenso erfüllt.

Wegen der Aufteil-Bedingung wird der Zustand 1 mit einem Eins-Bit nun zum Zustand 120 eher als Zustand 4 übergehen. Bei dem Beispiel wurde der Zweig achtmal verwendet und der nächste Zustand zwölfmal, so daß 2/3 der Zählpulse zu dem neuen Zustand gehen. Die aktualisierte Zustandsmaschine ist in Fig. 6B gezeigt. Nach dem Aufteilen des Zustands wird der Zählstand für Zustand 1 aktualisiert und der gegenwärtige Zustand wird Zustand 120.

Tabelle 4 zeigt den Zustandsspeicher, der Fig. 6B zugeordnet ist. Bemerkenswert ist, daß der Stern auf Einträge in der Tabelle hinweist, die ausgehend von Tabelle 3 aufgrund der Zustands-Aufteilung geändert wurden. Wie in Tabelle 3 zeigen die Striche an, daß eine Anzahl in dem Tabelleneintrag gespeichert ist, aber weggelassen wurde, um eine Verschleierung des Beispieles zu vermeiden. Der neue Zustand ist Zustand 120, da das der nächste verfügbare Zustand ist.

Tabelle 4

Bemerkenswert ist, daß bei der vorliegenden Erfindung die Zustände in bestimmten Speicherbänken gespeichert werden, wie dies genauer unten beschrieben wird. Dies ist ein Unterschied zum Stand der Technik, wo ein einziger Speicher alle Zustände speichert. Da Zustände in bestimmten Speicherbänken gespeichert werden, ist der Umfang des Speichers, der für einen bestimmten Zustand verfügbar ist, beschränkt. Bei der vorliegenden Erfindung basiert die Bestimmung, ob ein Zustand aufgeteilt wird, auf dem verfügbaren Raum bzw. Speicher in der Speicherbank des Zustandes. Dies wird genauer unten beschrieben.

Eine Zusammenfassung von Schritten, um eine Entscheidung, ob oder ob nicht aufgeteilt und eine Aufteilung durchgeführt werden soll zu implementieren, lautet wie folgt:

1. Falls kein Raum bzw. Speicher in der gegenwärtigen Speicherbank vorliegt oder der Zählstand für den gegenwärtigen Zweig zu gering ist oder die Summe der Zweige, die einen nächsten Zustand verlassen minus dem Zählstand des gegenwärtigen Zweiges zu gering ist, wird dann eine Aufteilung des nächsten Zustandes nicht erlaubt.
2. Falls das Aufteilen nicht erlaubt ist, kopiere man die Bestimmung bzw. das Ziel des nächsten Zustands zu einem neuen Zustand.
3. Ändere die Bestimmung bzw das Ziel des gegenwärtigen Zweiges zu einem neuen Zustand.
4. Weise die Zählstände für den neuen Zustand proportional zu dem Zählstand des Zweiges zu, d. h. new_count_0 = branch_cnt . next. cnt0/(next_cnt0 + next_cnt1), wobei "new_count" für neuer Zählstand, "branch_cnt" für Zweig-Zählstand und "next_cnt" für nächsten Zustand steht.
5. Verändere die Zählstande für den nächsten Zustand auf den Unterschied zwischen dem was sie waren und den Zählpulsen, die dem neuen Zustand zugewiesen sind.

Es ist vorteilhaft, einen Zustand aufzuteilen, falls eine derartige Vorgehensweise die Kompression verbessert. Jedoch ist es schwierig, eine derartige Entscheidung zu treffen, und es kann Speicher erfordern und die Untersuchung einer Menge von Daten. Wie hierin beschrieben wurde, wird ein Zustand aufgeteilt, falls zwei oder mehr Pfade durch denselben Zustand hindurchgehen und beide häufig verwendet werden. Die Kompressions-Kosten zum Aufteilen von Zuständen beinhalten die Verlangsamung der Wahrscheinlichkeitsschätzung und das Aufbrauchen aller verfügbaren Zustände, bevor andere Zustände aufgeteilt werden können. Die Schwellen werden ausgewählt, um ein Gleichgewicht zwischen Verlangsamung der Wahrscheinlichkeitsschätzung, dem Aufbrauchen aller verfügbaren Zustände und der Verbesserung der Kompression zu erzeugen, obwohl viele Werte nahezu dieselben Ergebnisse ergeben.

Es werden die Speicher-Erfordernisse und die Vorgehensweise bezüglich der Bänke bzw. das "Banking" beschrieben

Bei der vorliegenden Erfindung weist jeder Zustand vier Datenelemente auf: Einen Zählstand sowohl für Null-Bits als auch für Eins-Bits aus bzw. von dem Zustand und einem Zeiger zu dem nächsten Zustand sowohl für ein Null-Eingangsbit als auch für Eins-Eingangsbit. Eine verbesserte Kompression tritt auf, wenn eine Festpunkt-Arithmetik mit wenigstens zwei binären dezimalen Stellen verwendet wird (Zählpulse werden nach dem Aufteilen bis zu einer Genauigkeit von 1/4 beibehalten). Die Verwendung weniger genauer Zählpulse führt zu einer schlechten Wahrscheinlichkeitsschätzung, wenn die Zustände aufgeteilt werden. Bei einer Ausführungsform werden 16 Bits sowohl zum Zählen von Null als auch als Eins verwendet (5-Bit-Ganzzahlzähler und 2-Bit-Bruchzähler). Ebenso kann jeder Kontext zwei Zeiger aufweisen die in der Lage sind, die gesamte Anzahl von erlauben Zuständen zu indizieren bzw. zu erfassen.

Bei einer Ausführungsform kann der Graph anfänglich mit 8 Zuständen beginnen, einer für jede Bitposition in einem Byte (MSB bis LSB). In diesem Fall kann der gesamte Zustands speicher in 8 Bänke aufgeteilt werden, die zyklisch verwendet werden. Ein Zustand wird nur aufgespaltet, falls mehr Speicher in derselben Bank existiert. Jeder Zustand verwendet 3 Bits (entsprechend den 8 Bänken) weniger für die Zeiger als DMC nach dem Stand der Technik, und zwar wegen der impliziten Adresse, die durch die Bitposition gegeben ist.

Die Verwendung einer impliziten Adressierung kann ausgedehnt werden, indem der Speicher weiter in Bänke gemäß den vorhergehenden Bits unterteilt wird. Zum Beispiel könnte eine von 64 Bänken basierend auf 3 vorhergehenden Bits und der Bitposition ausgewählt werden. Solange der anfängliche Graph die korrekten Zustände enthält (zum Beispiel Zustände, die in einer Bank sind, wenn sie dieselben vorhergehenden Bits aufweisen und auf die Bank für entsprechender Eingangssignale zeigen), wird die Teilung bzw. Einteilung aufrechterhalten, wenn die Zustände aufgeteilt werden. Die neue Bank wird nun gewählt, indem der Bit- Positionszähler, die vorhergehenden Bits aus einem Schieberegister und der. Wert, der in dem gegenwärtigen Zustand gespeichert ist, kombiniert werden.

Da mehr Zustände sich anfänglich in einer Bank als in einer zweiten aufteilen können, behält ein Zähler (oder ein Speicher) für jede Bank eine Aufzeichnung des nächsten Zustandes, der in jener Bank verwendet werden soll. Das "Banking" bzw. die Vorgehensweise bezüglich einer Bank kann zu einer verringerten Kompression führen, weil eine Bank nicht den gesamten zugewiesenen Speicher brauchen kann, während eine andere Bank sich nicht soweit aufteilen kann, wie sie es in einem System machen würde, das keinen Bedingungen bzw. Randbedingungen unterworfen ist.

Fig. 10 zeigt Unterschiede zwischen dem DMC-Kontextmodell nach dem Stand der Technik und der vorliegenden Erfindung. Nimmt man Bezug auf Fig. 10, so verwendet das DMC- Kontextmodell nach dem Stand der Technik einen einzigen "unendlichen" Speichervorrat, der nur den anfänglichen Graphen zu Beginn speichert. Später, wenn die Zustände aufgeteilt sind, werden zusätzliche Zustände, die erzeugt werden, in dem Speicher gespeichert. Jeder Zustand in dem Speicher beinhaltet Speicheradressen auf Stellen in dem Speicher für den nächsten Zustand (abhängig davon, ob der nächste Zustand eine Eins oder eine Null ist).

Die vorliegende Erfindung kann andererseits nur einen logisch "gebankten" Speicher. Bei der vorliegenden Erfindung muß nur eine Teiladresse bzw. müssen nur Teiladressen mit jedem Zustand gespeichert werden. Dies liegt daran, daß die vorhergehenden Bits und eine Zähler- Bitposition, die bei den DMC-Implementationen nach dem Stand der Technik gespeichert werden müssen, automatisch wegen der Verwendung getrennter Bänke bestimmt werden. Somit speichert die vorliegende Erfindung, während der DMC-Algorithmus nach dem Stand der Technik das Äquivalente einer ganzen Bankadresse und die Adresse innerhalb der Bank, die in dem Speicher gespeichert werden soll, benötigt, nur die Adressen innerhalb der Bank (für die zwei Zustände und die Zählpulse bzw. Zählstände).

Bemerkenswert ist, daß physikalisch getrennte Bänke einen parallelen Betrieb ermöglichen. Bei einer Hardware-Ausführung ist die Zähler-Bitposition ein Teil der Bankadresse, um zu gewährleisten, daß auf unterschiedliche physikalische Bänke zugegriffen werden kann. Bemerkenswert ist, daß jede physikalische Bank eine oder mehrere logische Bänke beinhalten kann.

Für eine Hardware-Implementation sind die Erfordernisse beim "Banking" bzw. bei der Vorgehensweise bezüglich der Bänke 2Mlog(M/B) + Blog(M/B) + 2MW, wobei B die Anzahl der Bänke in Verwendung ist, M die gesamte Anzahl von Zuständen in allen Bänken ist, W die Breite in Bits des Speichers ist, der für Zähler verwendet wird, und alle Logarithmen zur Basis 2 sind. Bemerkenswert ist, daß dies voraussetzt bzw. annimmt, daß eine gleiche Anzahl von Zuständen in jeder Bank verfügbar ist. Falls das Kompressions system auf Daten mit bekannten Eigenschaften verwendet wird, ist es möglich, eine unterschiedliche Anzahl von Zuständen in jeder Bank zu verwenden. Zusätzlich werden mehrere Zustände bzw. Mehrfachzustände, selbst wenn es bekannt ist, daß Bit-Position 7 immer null ist (so, wie wenn ASCII kodiert wird), immer noch in Bank 7 benötigt, um. Geschichte-Information von Bank 6 zu Bank 0 zu tragen.

Während es in Anzahl von Kontexten ausgedrückt immer ein Vorteil ist, ein adaptives Modell zu verwenden, gibt es zusätzliche Kosten bzw. Aufwendungen bezüglich der Speicherung der Struktur des Modells. Bei einer Ausführungsform gibt es zwei Ganzzahl-Zählpulse bei jedem Kontext und zwei Zeiger zu dem nächsten Kontext. Jeder Kontext verwendet 26 + 2 log (Anzahl der Kontexte) Bits, und zwar ohne "Banking". Bei einer Ausführungsform liegt die Verwendung von Speicher zwischen 64 kbits und 1 Mbit (z. B. 768 kbits eines Speichers auf einem Chip).

Es wird die Neuskalierung von Zählern beschrieben

Bei einer Ausführungsform werden alle Zählpulse bzw. Zählstände als Festpunkt-Zahlen mit 2 Bits rechts von dem Binärpunkt beibehalten, um die Kompression zu verbessern und zu verhindern, daß die Wahrscheinlichkeitsschätzung leidet.

Selbst mit dem zugefügten Zusatz von 2 Extrabits pro Zähler ist es möglich, eine kleinere Anzahl von Bits zu verwenden, um die Zählpulse für jeden Zustand zu speichern als beim DMC gemäß dem Stand der Technik. Bei einer Ausführungsform können Zählpulse bei einem gewissen maximalen Wert, wie zum Beispiel 64 oder 32 neu skaliert werden. Das Neuskalieren von Zählpulsen zerstört die Aufteilungsregeln für den ursprünglichen DMC- Algorithmus, aber es werden höhere Zählpulse nicht erreicht, bis der größte Teil des Aufteilens durchgeführt wurde. Somit ist es möglich, anstelle der 32 Bits, die für "unbegrenzte" Zählpulse verwendet werden, nur 14 ( = 2 . log(32) + 2 . 2) zu verwenden. Bei einer Ausführungsform kann eine Neuskalierung durch eine Verschiebung sowohl der Eins- als auch Null-Zählpulse durchgeführt werden, wenn eins der beiden einen maximalen Wert erreicht.

Die Verringerung der Genauigkeit eines Zählers kann die Bitrate erhöhen und die Speicheraufwendungen bzw. Speicherkosten verringern.

Es wird die Wahrscheinlichkeits-Schätz-Tabelle beschrieben

Jeder Kontext verwendet Speicher, um den nächsten Zustand zu wählen und die Anzahl von Verwendungen eines jeden Zweiges nachzuverfolgen. Das Banking verringert die Speicherkosten bezüglich des nächsten Zustandes.

Um den Speicher zu verringern, der für Wahrscheinlichkeitsschätzungen benötigt wird, kann eine Tabelle mit Zählpulsen in ihr verwendet werden und jeder Kontext würde nur einen Zeiger in die Tabelle aufweisen. Es ist nicht notwendig, alle möglichen Zählpulse in der Tabelle zu behalten. Zum Beispiel könnten nur Zählpulse, die auf weniger als 32 aufaddiert sind, behalten werden. Bei einer Ausführungsform beinhaltet die Tabelle nicht den Bruchteil des Zählstandes, insbesondere dann, wenn die Zählpulse größer sind. Eine Tabelle zur Schätzung weist ebenso einen Vorteil auf, weil es nicht nötig sein wird, einen Zählstand durch die Summe zu dividieren, um die Wahrscheinlichkeitsschätzung zu bestimmen bzw. festzulegen. Somit kann eine Division im voraus bestimmt werden und die Tabelle kann den für die Verwendung passenden Kode enthalten.

Bei einer Ausführungsform können 16 oder 32 verschiedene Kodes durch den binären Entropie-Kodierer verwendet werden. Da nicht alle möglichen Zählpulse in der Tabelle existieren, wird der nächste Zustand in der Tabelle eher bereitgestellt, als das der Zähler verwendet wird, um den nächsten Zustand zu bestimmen. Ein Abschnitt bzw. Teil einer möglichen Tabelle erscheint in der Tabelle 5.

Diese Ausführungsform erfordert Speicher zum Speichern der Tabelleneinträge oder festverdrahtete Logik. Jedoch ist der Umfang, der für derartige Tabellen zugefügt wird, viel geringer als der Speicher, der eingespart wird, indem eher nur ein Index in jedem Zustand des Kontextmodells als zwei große Zähler in jedem Zustand verwendet wird. Die Zähler sind noch notwendig, um zu bestimmen, ob ein Knoten aufgeteilt werden sollte, und um die Zählpulse nach dem Aufteilen zu wählen.

Tabelle 5-Schätz-Tabelle

In Tabelle 5C beinhalten die Kode-Einträge R-Kodes, die adaptive Kodes sind, die Golomb- Lauflängenkodes (Golomb-"run length codes") beinhalten (d. h. R2(k)-Kodes). Zur weiteren Information betreffend diese R-Kodes, siehe US-Patent Nr. 5,381,145, das den Titel "Method and Apparatus for Parallel Decoding and Encoding of Data" trägt und am 10. Januar 1995 herausgegeben wurde.

Es wird die vereinfachte Entscheidung bezüglich Zustandsaufteilung beschrieben

Falls eine einzige Tabelle verwendet wird, um sowohl Aufteil-Regeln als auch Wahr scheinlichkeitsschätzungen bereitzustellen, wäre es denkbar, daß sie nur 512 Einträge aufweist. In diesem Fall würde ein Zustand nur 9 Bits anstelle der gegenwärtigen 14, die für Zählpulse verwendet werden, benötigen. Jedoch liegt, da jeder Kontext ebenso zwei Zeiger zu den nächstmöglichen Zuständen aufweist, die wahre Speicherverringerung nahe bei 10% und der Verlust der Kompression rechtfertigt nicht die Speichereinsparungen. Der einzige Grund, eine einzige Tabelle zur Wahrscheinlichkeitsschätzung und für das Aufteilen zu verwenden, ist gegeben, falls die erforderliche Berechnung verringert werden kann.

Wie oben diskutiert, wird der neue Zählstand, wenn ein Zustand aufgeteilt ist, durch ein proportionales Skalieren new0 = branch . cnt0/(cnt0 + cnt1) bestimmt (es steht "new" für neu, "branch" für Zweig. "cnt" für Zählstand). Die verbliebenen neuen Werte können durch Substrahieren berechnet werden. Eine Wahrscheinlichkeits-Schätztabelle kann gestaltet werden, die Aufteilregeln und Schätzungen enthält. Eine Wahrscheinlichkeits-Schätztabelle wird erzeugt, indem MPS- und LPS-Zählpulse verwendet werden. Die Zustände werden aufgeteilt, falls der gegenwärtige Zweig häufiger als eine Schwellen-Anzahl verwendet wird. Der neue Schätzzustand für den neuen Kontext und der aufgeteilte Kontext ergibt sich durch ein Reskalieren bzw. Neuskalieren der Zählpulse um 1/2.

Die Schätztabelle weist verschiedene Teile von Information für jeden Eintrag auf: Der Ablauf-Kode zur Verwendung für den Kontext (3-6 Bits), der nächste Zustand auf einem LPS, der nächste Zustand auf einem MPS, ein Wechsel bzw. ein Swap auf LPS-Bit, ein Aufteil-OK auf LPS-Bit, ein Aufteil-OK auf MPS-Bit, und nächste Zustände für Aufteilungen auf LPS und MPS. Die zwei nächsten Zustände zur Verwendung auf Aufteilungen können auf einen Zustand verringert werden, der entweder auf MPS oder LPS verwendet werden soll. Es gibt einen Vorteil bei der Verwendung vorhergehender Information über eine Bitposition, aber dieser Vorteil verschwindet langsam, sowie die Anzahl der verwendeten Bits erhöht wird. Bei einer Ausführungsform werden einzelne Zählpulse von Einsen und Nullen nicht behalten und eine Nachschlagtabelle zum Aufteilen von Zuständen wird verwendet.

Das adaptive Kontextmodell der vorliegenden Erfindung erreicht eine Leistungsfähigkeit, die nicht mit einem Markov-Kontextmodell fester Ordnung erreicht werden kann. Damit ein Hardware-Kompressionssystem nützlich ist, muß es wenigstens eine 2 : 1-Kompression auf manchen großen Sätzen von Dateien erzielen. Ohne ein adaptives Kontextmodell wird eine 2 : 1-Kompression häufig nicht erreicht. Mit mehr Kontexten kann ein Kontextmodell fester Ordnung schließlich Wahrscheinlichkeiten nicht genau mit dem endlichen Umfang von verfügbaren Daten schätzen. Somit bietet die vorliegende Erfindung, weil sie nicht so beschränkt ist, Vorteile gegenüber dem Stand der Technik.

Es wird ein wahlfreier bzw. zufälliger Zugriff und ein paralleler Betrieb beschrieben

Wenn eine adaptive verlustfreie Kompression auf einer Datei durchgeführt wird, ist es im allgemeinen notwendig, die gesamte Datei zu dekomprimieren, um das letzte Byte in dem File bzw. in der Datei zu dekomprimieren (es gibt keinen wahlfreien Zugriff). Jedoch gehen in einem Computersystem die Aufrufe des Betriebssystems, um auf Disketten zuzugreifen oder Speicher zu räumen, typischerweise davon aus, daß eine gewisse Form von wahlfreiem Zugriff verfügbar ist. Ein Anwendungs-Programmierer kann ein bestimmtes Byte suchen, aber das Betriebssystem (oder die Vorrichtungs-Treibereinrichtung) wird den korrekten Block suchen und den gesamten Block lesen. Ein wahlfreier Zugriff kann bereitgestellt werden, indem Abschnitte einer Datei unabhängig komprimiert werden. Falls die Größe des Stückes der Datei zu gering ist, gibt es unzureichend Daten, um genaue Wahrscheinlichkeitsschät zungen bereitzustellen. Diese ungenügende Anpassung bzw. Adaption verursacht eine wesentliche Kompressionsabnahme. Größere unabhängig komprimierte Blöcke erfordern, daß mehr Daten zusammen komprimiert und dekomprimiert werden, was eine größere Latenz bzw. Zugriffswartezeit für einen Zugriff verursacht.

Die Größe eines unabhängigen Stückes kann basierend auf der physikalischen Vorrichtung, die Kompression verwendet, gewählt werden.

Unabhängige Blöcke können komprimiert oder dekomprimiert werden, und zwar unabhängig durch parallele Hardware. Falls große Puffer vorgesehen sind oder die unabhängigen Blöcke klein genug sind, könnte dies eine Verringerung des Zeitaufwandes bedeuten, der zur Dekomprimierung langer Dateien benötigt wird. Jedoch müssen die getrennten Blöcke immer noch korrekt organisiert werden und zu der Speichervorrichtung gesendet bzw. übertragen werden. Ebenso wird dieser Typus von paralleler Operation bzw. Betriebsweise nicht die Latenz bzw. Wartezeit ausreichend verringern, falls die Blockgrößen zu groß sind.

Wegen eines Wunsch nach wahlfreiem Zugriff auf komprimierte Daten können die Kodierer periodisch zurückgesetzt werden. Jeder Block wird in diesem Fall im wesentlichen eine getrennte Datei und mit der kleineren Datengröße ist eine Wahrscheinlichkeitsschätzung nicht so effektiv und eine Kompression ist nicht so gut. Die verwendete Blockgröße kann von der Speichervorrichtung oder Anwendung abhängen. Deshalb können bei einer Ausführungsform Blockgrößen von 1 KB bis 64 KB verwendet werden. Unterhalt 1 KB wird eine Kompression wesentlich verringert.

Bei einer Ausführungsform werden 7-Bit-Zähler und 8 logische Bänke mit 8 KB-Blöcken verwendet.

Die binären Kompressionseinrichtungen, wie zum Beispiel jene, die hierin beschrieben sind, können schneller komprimieren und weisen eine geringere Latenz bzw. Wartezeit mit paralleler Arbeit auf. Verschiedene binäre Kompressionseinrichtungen können verwendet werden und die Statistik bzw. statistische Daten teilen. Jede Kompressionseinrichtung kann auf einer unterschiedlichen Bitposition eines kleinen Blockes arbeiten. In einem derartigen Fall wird das erste Zeichen in jedem kleinen Block ohne irgendwelche Geschichte-Bits ("memory bits") kodiert. Die verschiedenen Bitpositionen greifen auf verschiedene Bänke des physikalischen Speichers zu. Diese können teilweise der logischen Speicherbankaufteilung entsprechen, die oben diskutiert wurde. Das Aufteilen statistischer Daten bzw. der Statistik erlaubt es, daß gute Wahrscheinlichkeitsschätzungen mit diesen kleineren Blöcken erzielt werden. Der einzige Kompressionsverlust ist die Vorhersage des ersten Zeichens in jedem kleinen Block.

Mit paralleler Hardware wird jeder Kodierer auf einem unterschiedlichen Stück der Daten arbeiten. Die statistischen Daten können über einen großen Block akkumuliert werden. Falls jeder Kodierer 8 Bytes auseinander ist, dann muß alle 8 Bytes ein Bit kodiert werden, ohne das vorhergehende Bit zu kennen und das zweite Bit kann nur ein Bit von Geschichte verwenden, etc. Mit sehr kleinen Puffern (z. B. 4 Bytes) gibt es einen Verlust bei der Kompression, wenn mehr Kontexte verwendet werden. Vermutlich liegt dies daran, daß das Kontextmodell versucht, sich längeren Zeichenketten anzupassen und daran, daß das Rücksetzen dieser Kontexte selten verwendet wird. Das Rücksetzen der Geschichte-Puffer hat deutlich einen Einfluß auf die Kompression.

Es wird eine parallele Implementation einer Kompression beliebiger Daten beschrieben

Die vorliegende Erfindung stellt eine Kompression beliebiger Daten bereit, indem ein Parallel-Entropie-Kodierer verwendet wird. Die folgende Diskussion beschreibt zwei Verfahren der Sequentialisierung der Eingangsdaten durch Parallel-Kontextmodelle.

Eine Ausführungsform verwendet vier parallele Kontextmodelle (805-808) auf einen Eingangsstrom an, wie es in Fig. 8 gezeigt ist. Jeder Kodierer weist seinen eigenen Puffer auf (Puffer 801-804), der in einer Reihenfolge vom Anfang zum Ende abgearbeitet wird. Bei einer Ausführungsform weist jeder Puffer 801-804 einen 8 Byte-Puffer auf. Die Kodierer sind gestaffelt, so daß sie immer auf unterschiedliche Speicherbänke zugreifen. Wenn die Verarbeitung vollständig ist, können die vier Puffer geschaltet werden. Das Zugriffsmuster ist unten in der Tabelle 6 gezeigt. Das Kontextmodell 805 arbeitet immer auf den ersten 8 von 32 Bytes; Kontextmodell 806 arbeitet an den nächsten 8 Bytes usw. Tabelle 6 zeigt das Bit, das bei jedem Kontextmodell ("Conext model", CM) über die Zeit kodiert wird. Jeder Eintrag in Tabelle 6 beinhaltet drei Zahlen: Das Byte, das Bit und die Bank.

Tabelle 6

Um zu überprüfen, ob der Bedarf besteht, Zustände aufzuteilen, untersucht jedes Kon textmodell ebenso Daten in der Speicherbank, die dem gegenwärtigen Bit folgen. Dies geschieht im Riegel-Schritt bzw. "lock-step". Das Kontextmodell 805 greift auf Bank 0 zu, um Information über den gegenwärtigen Zustand zu bekommen, während Kontextmodell 806 auf Bank 1 zugreift usw. Dann greift das Kontextmodell 805 auf Information in Bank 1 zu, um eine Aufteil-Information bzw. eine aufgeteilte Information über den nächsten Zustand zu bekommen. Bei einer Ausführungsform wird das Schalten, um den Kontextmodellen zu erlauben, auf andere Speicherbänke zuzugreifen, mittels eines Crossbars durchgeführt, indem Adressen und Daten verwendet werden.

Bei einer alternativen Ausführungsform, wie jene, die in Fig. 9 gezeigt ist, gibt es nur ein 32 Byte-Puffer 901. Das Puffer 901 kann ein Schieberegister aufweisen. Das Kontextmodell 906 greift entweder auf Byte 0 Bit 0 oder auf Byte 8 Bit 0 oder auf Byte 16 Bit 0 oder auf Byte 24 Bit 0 zu. Das Kontextmodell 907 greift auf eines der Einser-Bits derselben vier Bytes zu usw. Nachdem jedes Kontextmodell das geeignete bzw. passende Bit gelesen hat, kann das Schieberegister 901 um vier Bits verschoben werden. Das Zugriffsmuster ist in Tabelle 7 gezeigt. In diesem Fall ist die primäre Speicherbank immer die Bank 0 für ein Kon textmodell 906 und Bank 1 für ein Kontextmodell 907. Natürlich greifen die Kontextmodelle auf die folgende Bank für die Aufteil-Information zu. Tabelle 7 ist ebenso anders, weil die Kontextmodelle um zwei Positionen beim Beginn gestaffelt wurden. Dies ist wahrscheinlich realistischer, weil es Pipeline-Delays beim Empfangen von Information von dem Speicher oder von dem parallelen Entropie-Kodierer (z. B. einem Hochgeschwindigkeitspar allelkodierer) geben kann. Sogar längere Verzögerungen könnten zugefügt werden. Der gegenwärtige Zustand wird unter den Kontextmodellen weitergegeben bzw. durchgeleitet. (Bemerkenswert für diese Ausführungsform eines Kontextmodells ist es, daß anstelle der Durchleitung eines gegenwärtigen Zustandes in einem Zyklus (0, 1, 2, 3, 0, . . .) Geschichte- Information durchgeleitet wird bzw. hindurchgelangt).

Tabelle 7

Wohingegen viele Änderungen und Modifikationen der vorliegenden Erfindung ohne Zweifel einen Durchschnittsfachmann offenbar werden, nachdem er die vorhergehende Beschreibung gelesen hat, ist es selbstverständlich, daß verschiedene gezeigte und beispielhaft beschriebene Ausführungsformen in keinster Weise als beschränkend anzusehen sind. Deshalb ist es nicht beabsichtigt, daß die Details der verschiedenen Ausführungsformen den Umfang der Ansprüche beschränken sollen, die wiederum nur jene Merkmale wiedergeben, die als für die Erfindung wesentlich angesehen werden.

Somit wurde ein System und ein Verfahren zur Kompression und Dekompression von beliebigen Daten beschrieben.

Sie läßt sich wie folgt grob zusammenfassen:

Die Erfindung betrifft ein Kodier- und Dekodiersystem, das ein Modell beinhaltet, das in Hardware oder Software implementiert ist und das in der Lage ist, auf beliebigen Daten zu arbeiten (zum Beispiel Daten verschiedener Typen oder einer Mannigfaltigkeit von Typen). Das Modell erzeugt einen Kontext und binäre Entscheidungen für jedes Symbol. Das verwendet ein binärer Entropie-Kodierer, um einen komprimierten Bitstrom zu erzeugen. Ein Kontextmodell ist mit beliebigen Daten betreibbar und verwendet Kontext-Bins verschiedener Ordnungen, um einen Kontext und eine Entscheidung für jedes Symbol in einem Eingangs- Symbolstrom zu erzeugen. Ein Entropie-Kodierer schätzt eine Wahrscheinlichkeit und erzeugt einen komprimierten Datenstrom in Antwort auf die Kontexte und Entscheidungen aus dem Modell und gemäß der erzeugten Wahrscheinlichkeitsschätzungen.

Der erfindungsgemäße Apparat, das erfindungsgemäße System und Verfahren zur Kompressions und Dekompression beliebiger Daten, lassen sich insbesondere mit folgendem kombinieren:

- Einer Einrichtung zur Umwandlung physikalischer Signale und Meßwerte (z. B. Tonsignale, Bildsignale etc.) in digitale Signale, die dann mittels der erfindungsgemäßen Einrichtungen komprimiert bzw. kodiert werden. Bei derartigen Umwandlungseinrichtung kann es sich z. B. um Scanner zur Bildabtastung (z. B. bei Faxgeräten), Einrichtungen zur digitalen Tonaufzeichnung, Meßwerterfassungssysteme zur Erfassung physikalischer Werte (z. B. Druck, Temperatur etc.) kombiniert mit einem Analog-digitalwandler oder Ton- bzw. Sprachanalysegeräte handeln.
- Eine Ausgabeeinrichtung zur Umwandlung der dekomprimierten bzw. dekodierten digitalen Werte in physikalische Signale (z. B. Tonausgabe mit D/A-Wandler, Ausgabe auf einem Bildschirm oder Drucker etc., Ausgabe auf Faxgeräten oder Fernsehgeräten etc.).

Zwischen Kompression und Dekompression kann ein langer Übertragungsweg (z. B. über Sattelit, Internet etc.) liegen.

Claims

1. Vorrichtung zum Komprimieren eines Eingangs-Datenstromes mit:
einem Kontextmodell, das betreibbar ist, um individuelle Bits beliebiger Datentypen zu modellieren, wobei das Modell verschiedene Ordnungen verwendet, um einen Kontext und eine binäre Entscheidung für jedes Bit in dem Eingangs-Datenstrom zu erzeugen, und das weiter adaptiv Kontexte höherer Ordnung als jene, die aktiv ist, während die Eingangsdaten kodiert werden, aktiviert,
wobei ein Kontext höherer Ordnung einer größeren Anzahl vorhergehender Daten entspricht als ein Kontext niedriger Ordnung;
einem binären Entropie-Kodierer, der an das Modell angeschlossen ist, um einen komprimierten Bitstrom in Antwort auf Kontexte und binäre Entscheidungen von dem Kontextmodell zu erzeugen und zwar basierend auf Wahrscheinlichkeitsschätzungen, die dadurch erzeugt werden.

2. Vorrichtung nach Anspruch 1, dadurch gekennzeichnet, daß das Modell und der binäre Entropie-Kodierer arbeitet, um den Eingangs-Datenstrom verlustfrei zu komprimieren.

3. Vorrichtung nach einem der vorhergehenden Ansprüche, insbesondere nach Anspruch 1, dadurch gekennzeichnet, daß das Modell ein adaptives Modell mit einer veränderlichen Anzahl von Kontexten aufweist, während der Eingangs-Datenstrom komprimiert wird.

4. Vorrichtung nach einem der vorhergehenden Ansprüche, insbesondere nach Anspruch 1, dadurch gekennzeichnet, daß der Eingangs-Datenstrom in Echtzeit komprimiert wird.

5. Vorrichtung nach einem der vorhergehenden Ansprüche, insbesondere nach Anspruch 1, dadurch gekennzeichnet, daß er weiter einen Speicher fester Größe aufweist, der an das Modell angeschlossen ist, um Kontexte zu speichern.

6. Vorrichtung nach einem der vorhergehenden Ansprüche, insbesondere nach Anspruch 1, dadurch gekennzeichnet, daß das Modell ein Markov-Kontextmodell aufweist.

7. Vorrichtung nach einem der vorhergehenden Ansprüche, insbesondere nach Anspruch 1, dadurch gekennzeichnet, daß das Modell ein dynamisches Markov-Kompressionsmodell aufweist.

8. Vorrichtung zur Komprimierung eines Eingangs-Symbolstroms mit:
einem Kontextmodell, das mit beliebigen Daten betreibbar ist, um individuelle Bits von Symbolen in dem Eingangs-Symbolstrom zu modellieren, wobei das Modell Kontext- Bins verschiedener Ordnungen verwendet, um einen Kontext und eine Entscheidung für jedes Bit eines jeden Symbols zu erzeugen und das weiter adaptiv Kontexte höherer Ordnung als jene, die aktiv ist, während die eingehenden Symbole kodiert werden, aktiviert, wobei ein Kontext höherer Ordnung einer größeren Anzahl vorhergehenden Daten entspricht als ein Kontext niedrigerer Ordnung; und
einem Entropie-Kodierer, der an das Kontextmodell angeschlossen ist, um Wahrscheinlichkeiten zu schätzen und um einen komprimierten Datenstrom in Antwort auf Kontexte und Entscheidungen von dem Modell zu erzeugen, das auf erzeugten Wahr scheinlichkeitsschätzungen basiert.

9. Vorrichtung nach Anspruch 8, dadurch gekennzeichnet, daß der Entropie-Kodierer einen binären Entropie-Kodierer aufweist und jede Entscheidung eine binäre Entscheidung aufweist.

10. Vorrichtung nach Anspruch 8 oder 9, insbesondere nach Anspruch 8, dadurch gekennzeichnet, daß das Kontextmodell anfänglich nur Kontext-Bins N-ter Ordnung verwendet.

11. Vorrichtung nach Anspruch 10, bei welchem die N-te Ordnung die 0-te Ordnung aufweist.

12. Vorrichtung nach Anspruch 8 bis 11, insbesondere nach Anspruch 8, dadurch gekennzeichnet, daß das Kontextmodell eine Entscheidung basierend auf dem Kontext höchster Ordnung, der aktiv ist, erzeugt.

13. Vorrichtung nach Anspruch 8 bis 12, insbesondere nach Anspruch 8, dadurch gekennzeichnet, daß anfänglich nur eine vorbestimmte Anzahl von Kontexten zur Verwendung verfügbar ist und zusätzliche Kontexte danach aktiviert werden.

14. Vorrichtung zum Komprimieren eines Eingangs-Symbolstroms mit:
einem Kontextmodell, das mit beliebigen Daten betreibbar ist, wobei das Modell Modelle unterschiedlicher Ordnung verwendet, um einen Kontext und eine Entscheidung für jedes Symbol zu erzeugen, wobei ein Kontext höherer Ordnung einer größeren Anzahl vorhergehender Daten entspricht als ein Kontext niedrigerer Ordnung; und
einem Entropie-Kodierer, der an das Kontextmodell angeschlossen ist, um Wahrscheinlichkeiten zu schätzen und um Entscheidungen in einen komprimierten Datenstrom in Antwort auf Kontexte und Entscheidungen von dem Modell zu kodieren, der auf erzeugten Wahrscheinlichkeitsschätzungen basiert;
wobei das Kontextmodell insoweit adaptiv ist, daß das Kontextmodell Kontext-Bins höherer Ordnung aus einer Vielzahl von inaktiven Kontext-Bins adaptiv aktiviert und Speicher für derartige Kontext-Bins zuordnet, während Symbole in dem Eingangs- Symbolstrom kodiert werden.

15. Vorrichtung nach Anspruch 14, bei welchem das Kontextmodell verschiedene Modelle N-ter Ordnung verwendet, wo N größer als oder gleich 2 ist.

16. Vorrichtung nach Anspruch 14 oder 15, insbesondere nach Anspruch 14, dadurch gekennzeichnet, daß das Kontextmodell, wenn das Kontextmodell ein Kontext-Bin n-ter Ordnung verwendet, statistische Daten aktualisiert, die einem Kontext-Bin einer Ordnung höher als die n-te Ordnung entspricht.

17. Vorrichtung nach Anspruch 14 bis 16, insbesondere nach Anspruch 14, dadurch gekennzeichnet, daß das Kontextmodell statistische Daten, die wenigstens einen Kontext-Bin (n + 1)-ter Ordnung entsprechen, aktualisiert, wenn ein Kontext n-ter Ordnung verwendet wird.

18. Vorrichtung nach Anspruch 14 bis 17, insbesondere nach Anspruch 14, dadurch gekennzeichnet, daß das Kontextmodell Kontexte niedrigerer Ordnung verwendet, bis ein bestimmter Kontext höherer Ordnung häufig genug auftritt, so daß eine vernünftige Erwartung existiert, daß eine gute Wahrscheinlichkeitsschätzung mit dem Kontext höherer Ordnung verbunden ist, und so daß die Verwendung des Kontextes höherer Ordnung eine bessere Kompression erlaubt.

19. Vorrichtung nach Anspruch 14 bis 18, insbesondere nach Anspruch 14, dadurch gekennzeichnet, daß die vorliegende Erfindung eine Kontext-Aufteil-Logik aufweist, um zu bestimmen, wann Kontexte zu aktivieren sind.

20. Vorrichtung nach Anspruch 19, dadurch gekennzeichnet, daß die Kontext-Aufteil- Logik ein Kontext-Bin höherer Ordnung aktiviert, wenn ein Zählwert eine vorbestimmte Schwelle erreicht.

21. Vorrichtung nach Anspruch 20, dadurch gekennzeichnet, daß der Zählwert für einen Kontext (n+ 1)-ter Ordnung inkrementiert wird, wenn ein Kontext-Bin n-ter Ordnung verwendet wird.

22. Vorrichtung nach Anspruch 20, dadurch gekennzeichnet, daß der Zählwert um eine Konstante jedesmal erhöht wird, wenn der Kontext n-ter Ordnung verwendet wird.

23. Vorrichtung nach Anspruch 20, dadurch gekennzeichnet, daß der Zählwert um einen variablen Umfang jedesmal erhöht wird, wenn der Kontext n-ter Ordnung verwendet wird.

24. Vorrichtung nach Anspruch 23, dadurch gekennzeichnet, daß der variable Umfang, dazu in Beziehung steht, wie nahe die Wahrscheinlichkeitsschätzung n-ter Ordnung an 50% liegt.

25. Vorrichtung nach Anspruch 20 bis 24, insbesondere nach Anspruch 20, dadurch gekennzeichnet, daß eine anfängliche Wahrscheinlichkeitsschätzung für ein neu aktiviertes Kontext-Bin einen Default- bzw. Vorgabe-Wahrscheinlichkeitsschätzzustand aufweist.

26. Vorrichtung nach Anspruch 20-25, insbesondere nach Anspruch 20, dadurch gekennzeichnet, daß eine anfängliche Wahrscheinlichkeitsschätzung für das neu aktivierte Kontext-Bin (n + 1)-ter Ordnung einen Wahrscheinlichkeitsschätzzustand des Kontextes n-ter Ordnung aufweist.

27. Vorrichtung nach Anspruch 20-26, insbesondere nach Anspruch 20, dadurch gekennzeichnet, daß eine anfängliche Wahrscheinlichkeitsschätzung für das neu aktivierte Kontext-Bin einen Wahrscheinlichkeitsschätzzustand basierend auf Bits aufweist, die unter Verwendung des Kontext-Bins, falls es immer aktiviert gewesen wäre, kodiert worden wären.

28. Vorrichtung nach Anspruch 20-27, insbesondere nach Anspruch 20, dadurch gekennzeichnet, daß eine Wahrscheinlichkeitsschätzung für ein aktiviertes Kontext-Bin (n + 1)-ter Ordnung einen Wahrscheinlichkeitsschätzzustand aufweist, der erhöht wird, falls das Kontext-Bin (n + 1)-ter Ordnung ein Symbol höchster Wahrscheinlichkeit (MPS) aufweist, das sich von einem MPS des Kontextes n-ter Ordnung unterscheidet.

29. Vorrichtung nach Anspruch 20, dadurch gekennzeichnet, daß eine Wahrscheinlichkeitsschätzung für einen aktivierten Kontext (n + 1)-ter Ordnung einen Wahrscheinlichkeitsschätzzustand aufweist, der erhöht wird, falls kein Symbol niedrigster Wahrscheinlichkeit in dem Kontext (n + 1)-ter Ordnung vor der Aktivierung auftritt.

30. Vorrichtung nach einem der vorhergehenden Ansprüche, insbesondere nach Anspruch 14, der weiter einen Hashing-Mechanismus aufweist, um wenigstens einen Kontext höherer Ordnung einer Speicherstelle zum Zugriff davon zuzuweisen, wo n größer als oder gleich 2 ist.

31. Vorrichtung nach Anspruch 30, dadurch gekennzeichnet, daß Kontext-Bins unterhalb des Kontextes n-ter Ordnung nicht Hashing verwenden.

32. Vorrichtung zum Komprimieren eines Eingangs-Symbolstroms nach Anspruch 14, dadurch gekennzeichnet, daß das Kontextmodell mit einer Mannigfaltigkeit von Datentypen betreibbar ist, um Kontexte und binäre Entscheidungen für Symbole in dem Eingangs- Symbolstrom zu erzeugen, wobei das Kontextmodell wenigstens einen Speicher mit einer Vielzahl bzw. Anzahl von Bänken aufweist, in dem jede Bank einen oder mehreren verschiedenen Zuständen zugeordnet ist; und der Entropie-Kodierer ein binärer Entropie-Kodierer ist, der an dem Kontextmodell angeschlossen ist, um Wahrscheinlichkeiten zu schätzen, die auf Kontexten von dem Kontextmodell basieren, und um binäre Entscheidungen von dem Kontextmodell in einen komprimierten Datenstrom basierend auf erzeugten Wahrscheinlichkeitsschätzungen zu kodieren.

33. Vorrichtung nach Anspruch 32, dadurch gekennzeichnet, daß ein Zustand des Kontextmodells sich aufteilt, falls mehr Speicher in der Bank existiert, die den Zustand speichert.

34. Vorrichtung nach Anspruch 32, dadurch gekennzeichnet, daß die Zeiger zu jedem Zustand impliziert durch die Bitposition adressiert werden.

35. Vorrichtung nach Anspruch 34, dadurch gekennzeichnet, daß die Bänke in dem Speicher basierend auf einer vorbestimmten Anzahl von vorhergehenden Bits und der Bitposition ausgewählt werden.

36. Vorrichtung nach Anspruch 35, dadurch gekennzeichnet, daß eine neue Bank ausgewählt wird, indem ein Bitpositionszähler, die vorhergehenden Bits und der Wert, der in dem gegenwärtigen Zustand gespeichert ist, kombiniert wird.

37. Vorrichtung nach Anspruch 32, dadurch gekennzeichnet, daß er weiterhin eine Tabelle aufweist, die Zählpulse enthält, wobei jeder Kontext einen Zeiger in die Tabelle aufweist.

38. Vorrichtung nach Anspruch 37, dadurch gekennzeichnet, daß die Tabelle sowohl Aufteil-Regeln als auch Wahrscheinlichkeitsschätzungen bereitstellt.

39. Vorrichtung nach Anspruch 38, dadurch gekennzeichnet, daß Zustände aufgeteilt werden, falls der gegenwärtige Zweig häufiger als eine Schwellen-Anzahl verwendet wird.

40. Vorrichtung zur Dekomprimierung eines komprimierten Datenstroms mit:
einem Modell, das mit beliebigen Daten betreibbar ist, um einzelne Bits zu modellieren, wobei das Modell verschiedene Ordnungen verwendet, um einen Kontext für jedes Bit in dem komprimierten Datenstrom zu erzeugen, wobei ein Kontext höherer Ordnung einer größeren Anzahl vorhergehender Daten entspricht als ein Kontext niedrigerer Ordnung;
einem binären Entropie-Dekoder, der an das Modell angeschlossen ist, der eine Wahrscheinlichkeitsschätzung in Antwort auf den Kontext und auf ein Ergebnis, das darauf hinweist, ob eine Entscheidung in ihren höchstwahrscheinlichen Zustand war oder nicht, erzeugt, wobei das Kontextmodell rekonstruierte Daten in Antwort auf das Ergebnis erzeugt, wobei
das Modell ein adaptives Modell aufweist, das die Anzahl von Kontexten variiert, während der komprimierte Datenstrom dekomprimiert wird.

41. Vorrichtung nach Anspruch 40 mit:
einem Pufferspeicher, der komprimierte Daten speichert;
einer Anzahl von Kontextmodellen, die an dem Pufferspeicher angeschlossen sind, um eine Anzahl von Kontexten in Antwort auf Zustands- und Geschichte-Information und den dekomprimierten Daten zu erzeugen;
eine Anzahl von Speicherbänken, wobei jede der Anzahl von Bänken an ein einzelnes Kontextmodell angeschlossen ist, um eine Kontextinformation bereitzustellen, um einzelne Kontexte in Antwort auf Signale von der Anzahl von Kontextmodellen zu senden; und wobei der Entropie-Dekoder ein paralleler Entropie-Dekoder ist, der an der Anzahl von Kontextmodellen angeschlossen ist, um einen Bitstrom in Antwort auf die dekomprimierten Daten und Kontexten von der Anzahl von Kontexten zu rekonstruieren.

42. Vorrichtung nach Anspruch 40, dadurch gekennzeichnet, daß das Kontextmodell anfänglich nur Kontext-Bins N-ter Ordnung verwendet.

43. Vorrichtung nach Anspruch 42, bei welcher die N-te Ordnung eine 0-te Ordnung aufweist.

44. Vorrichtung nach Anspruch 40, bei welcher das Kontextmodell dahingehend adaptiv ist, daß das Kontextmodell Kontext-Bins von einer Anzahl von inaktiven Kontext-Bins aktiviert und Speicher für derartige Kontext-Bins zuordnet, während Bits in dem komprimierten Bitstrom dekomprimiert werden.

45. Vorrichtung nach Anspruch 40, bei welcher das Kontextmodell wenigstens einen Speicher mit einer Anzahl von Bänken aufweist, in dem jede Bank einem oder mehreren verschiedenen Zuständen zugeordnet ist.

46. Vorrichtung nach Anspruch 45, bei welcher der Zustand des Kontextmodells sich aufteilt, falls mehr Speicher in derselben Bank existiert, die den Zustand enthält.

47. Vorrichtung nach Anspruch 1 oder 14, die folgendes zur Bereitstellung von Kontexten aufweist:
eine Anzahl von Puffern zum Speichern unkomprimierter Daten;
eine Anzahl von Kontextmodellen, wobei jede der Anzahl von Kontextmodellen an einzelne Puffer angeschlossen ist, wobei die Kontextmodelle parallel arbeiten, um Kontexte bereitzustellen;
eine Anzahl von Speicherbänken, die Zustandsinformation speichern, die Kontexten entsprechen; und
einen Schaltmechanismus, der mit der Anzahl von Kontextmodellen verbunden ist, um Adressen- und Dateninformationen zwischen der Anzahl von Kontextmodellen und der Anzahl von Speicherbänken zu leiten, wobei jedes Kontextmodell auf einen verschiedenen bzw. unterschiedlichen Satz von Bänken, um Zustandsinformationen zu erhalten, und auf einen anderen unterschiedlichen bzw. verschiedenen Satz von Bänken, um Aufteil- Information bzw. aufgeteilte Information zu erhalten, zugreift.

48. Vorrichtung nach Anspruch 47, dadurch gekennzeichnet, daß die Anzahl von Bänken logische. Bänke aufweisen.

49. Vorrichtung nach Anspruch 47 oder 48, dadurch gekennzeichnet, daß der Schaltmechanismus einen Crossbar-Schalter aufweist.

50. Vorrichtung nach Anspruch 1 oder 14 mit:
einem Pufferspeicher, der unkomprimierte Daten speichert;
einer Anzahl von Kontextmodellen, die an dem Pufferspeicher angeschlossen sind, um eine Anzahl von Kontexten in Antwort auf Zustands- und Geschichte-Informationen und die unkomprimierten Daten zu erzeugen;
einer Anzahl von Speicherbänken, bei welchen jeder der Anzahl von Bänken an einzelne der Anzahl von Kontextmodellen angeschlossen ist, um Kontextinformation bereitzustellen, um bzw. einzelne Kontexte in Antwort auf Signale von den Kontextmodellen zu senden; wobei der Entropie-Kodierer
ein paralleler Entropie-Kodierer ist, der an die Anzahl von Kontextmodellen angeschlossen ist, um einen komprimierten Bitstrom in Antwort auf die unkomprimierten Daten zu erzeugen.

51. Vorrichtung nach Anspruch 50, dadurch gekennzeichnet, daß die Anzahl von Speicherbänken logische Bänke aufweisen.

52. Vorrichtung nach Anspruch 50, dadurch gekennzeichnet, daß der Pufferspeicher ein Schieberegister aufweist.

53. Vorrichtung nach Anspruch 50, dadurch gekennzeichnet, daß die Geschichte- Information Information über das Auftreten von Symbolen aufweist.

54. Vorrichtung nach Anspruch 50, dadurch gekennzeichnet, daß eine Anzahl von Kontextmodellen folgendes aufweist:
ein Zustandsregister, das einen gegenwärtigen Zustand speichert, wobei das eine Kontextmodell auf die Anzahl von Speicherbänken zugreift, um Zählstand-Information bzw. Zähl-Information zu erhalten;
eine Zählstand-zu-Kode-Einheit, die angeschlossen ist, um die Zählstand-Information bzw. Zähl-Information aus der Vielzahl bzw. Anzahl von Speicherbänken zu empfangen und um die Zählstand-Information in einen Kode umzuwandeln, der von dem parallelen Entropie-Kodierer verwendet wird, um den komprimierten Bitstrom zu erzeugen.

55. Vorrichtung nach Anspruch 54, dadurch gekennzeichnet, daß der Speicher ebenso einen Satz möglicher nächster Zustände erzeugt und daß das eine Kontextmodell weiter einen Auswahlmechanismus aufweist, der den nächsten Zustand für das eine Kontextmodell basierend auf dem Satz möglicher nächster Zustände und wenigstens einem Teil bzw. Abschnitt unkomprimierter Daten erzeugt.

56. Vorrichtung nach Anspruch 54 oder 55, dadurch gekennzeichnet, daß das eine Kontextmodell weiterhin eine Aktualisier-Logik aufweist, die an die Vielzahl bzw. Anzahl von Speicherbänken angeschlossen ist, um Zählpulse bzw. Zählerstände in der Vielzahl bzw. Anzahl von Speicherbänken in Antwort auf die Zähl-Information bzw. Zählstand- Information zu aktualisieren.

57. Vorrichtung nach Anspruch 54 bis 56, dadurch gekennzeichnet, daß das eine Kontextmodell weiter eine Aufteil-Logik aufweist, die Zustände aufteilt und zwar basierend auf der Kontextinformation, die verwendet wird, um Kontexte zu erzeugen.

58. Vorrichtung nach Anspruch 50, dadurch gekennzeichnet, daß die Vielzahl bzw. Anzahl von Speicherbänken logische Bänke aufweisen.

59. Vorrichtung nach Anspruch 50, dadurch gekennzeichnet, daß die Pufferspeicher Schieberegister aufweisen.

60. Verfahren der Kompression eines Eingangsstromes, der eine Vielzahl von Symbolen enthält, wobei das Verfahren die folgenden Schritte aufweist:
ein Kontext und eine Entscheidung für jedes Bit eines jedes Symbols in dem Eingangsstrom wird mit einem Kontextmodell, das mit verschiedenen Ordnungsmodellen betreibbar ist, erzeugt; wobei ein Kontext höherer Ordnung einer größeren Anzahl von vorhergehenden Daten entspricht als ein Kontext niedrigerer Ordnung, ein Kontext-Bin höherer Ordnung, das nicht zuvor aktiviert wurde, wird adaptiv aktiviert, einschließlich des Schrittes, wonach Speicher dynamisch zugewiesen wird, wenn er benötigt wird, Information entsprechend des Kontext-Bins höherer Ordnung zu speichern; und
Entscheidungen werden in einen komprimierten Datenstrom kodiert.

61. Verfahren nach Anspruch 60, dadurch gekennzeichnet, daß es weiter den Schritt aufweist, wonach statistische Daten entsprechend wenigstens einem Kontext-Bin (n + 1)-ter Ordnung aktualisiert werden, wenn ein Kontext n-ter Ordnung verwendet wird.

62. Verfahren nach Anspruch 60 oder 61, insbesondere nach Anspruch 60, dadurch gekennzeichnet, daß es weiter den Schritt aufweist, wonach ein Kontext niedrigerer Ordnung verwendet wird, um Entscheidungen zu erzeugen, bis ein bestimmter Kontext höherer Ordnung häufig genug verwendet wird, so daß eine vernünftige Erwartung existiert, daß eine gute Wahrscheinlichkeitsschätzung erzielbar ist und daß die Verwendung des Kontextes höherer Ordnung eine bessere Kompression erlaubt.

63. Verfahren nach Anspruch 60 bis 62, insbesondere nach Anspruch 60, dadurch gekennzeichnet, daß es weiter den Schritt aufweist, wonach das Kontext-Bin höherer Ordnung aktiviert wird, wenn ein Zählwert eine vorbestimmte Schwelle erreicht.

64. Verfahren nach Anspruch 63, dadurch gekennzeichnet, daß es weiter den Schritt aufweist, wonach der Zählwert eines Kontextes (n + 1)-ter Ordnung inkrementiert wird, wenn ein Kontext-Bin n-ter Ordnung verwendet wird.

65. Verfahren der Kompression eines Eingangsstromes mit einer Vielzahl von Symbolen, wobei das Verfahren die folgenden Schritte aufweist:
ein Kontext und eine Entscheidung für jedes Bit eines jeden Symbols in dem Eingangsstrom wird basierend auf einem gegenwärtigen Zustand eines Kontextmodells, das mit Modellen verschiedener Ordnung betreibbar ist, erzeugt, wobei ein Kontext höherer Ordnung einer größeren Anzahl vorhergehender Daten entspricht als ein Kontext niedrigerer Ordnung,
der gegenwärtige Zustand wird aufgeteilt, falls mehr Speicher in derselben Bank wie der gegenwärtige Zustand existiert, so daß Speicher dynamisch für ein Kontext-Bin höherer Ordnung adaptiv zugeordnet wird; und
Entscheidungen werden in einen komprimierten Datenstrom kodiert.

66. Verfahren nach Anspruch 65, dadurch gekennzeichnet, daß es weiter die Schritte aufweist, wonach eine Bank basierend auf einer vorbestimmten Anzahl von vorhergehenden Bits und der Bitposition ausgewählt wird, und zwar wie von einem Zeiger angezeigt.