DE19742417A1

DE19742417A1 - Vorrichtung und Verfahren zur Durchführung von M-fachem Maschinenendzustands-Entropiekodieren bzw. Entropiekodieren mit einer Maschine mit finitem Zustand

Info

Publication number: DE19742417A1
Application number: DE19742417A
Authority: DE
Inventors: Michael J Gormish; Edward L Schwartz
Original assignee: Ricoh Co Ltd
Current assignee: Ricoh Co Ltd
Priority date: 1996-09-26
Filing date: 1997-09-25
Publication date: 1998-04-16
Anticipated expiration: 2017-09-26
Also published as: GB2317794B; JP3459030B2; GB9720231D0; DE19742417B4; US5912636A; JPH10107645A; GB2317794A

Description

Die vorliegende Erfindung bezieht sich auf den Bereich der Datenkompressions- und -dekompressionssysteme; die vorliegende Erfindung bezieht sich insbesondere auf das Maschinenendzustands-Entropiekodieren von n Bits zu einer Zeit bzw. zur gleichen Zeit, gemäß den Ansprüchen 1, 8 und 18.

Die Datenkompression ist ein äußerst nützliches Werkzeug zum Speichern und Übertragen großer Datenmengen. Zum Beispiel wird die zum Übertragen eines Bildes erforderliche Zeit, wie etwa eine Faksimileübertragung eines Dokuments, äußerst stark verringert, wenn eine Kompression verwendet wird, um die Anzahl von Bits zu verringern, die erforderlich ist, um das Bild zu rekonstruieren.

Bei einigen Kompressionssystemen wird ein Eingabefeld oder Datensatz in eine Abfolge von Entscheidungen unter der Vorgabe eines Entscheidungsmodells übersetzt.

Jede Entscheidung hat eine damit verknüpfte Wahrscheinlichkeit und basiert auf dieser Wahrscheinlichkeit, wobei ein Ausgabekode erzeugt wird und dem komprimierten Feld angehängt wird. Um dieses kodierte System zu realisieren, haben Kompressions systeme drei Teile: ein Entscheidungsmodell, ein Wahrscheinlichkeitsabschätzungs modell und einen Bitstromgenerator. Das Entscheidungsmodell empfängt die Ein gangsdaten und übersetzt die Daten in einen Entscheidungssatz, den das Kompres sionssystem verwendet, um die Daten zu kodieren. Auf das Entscheidungsmodell wird üblicherweise als einem Kontektmodell Bezug genommen. Das Wahrscheinlichkeits abschätzungsverfahren ist eine Prozedur zum Entwickeln der Wahrscheinlichkeits abschätzung für die Wahrscheinlichkeit jeder Entscheidung. Der Bitstromgenerator führt das letztendliche Bitstromkodieren durch, um den Ausgangskode zu erzeugen, der der komprimierte Datensatz oder das komprimierte Feld ist. Die Kompression kann wirksam in einem oder beiden der Entscheidungsmodelle und dem Bitgenerator auftreten.

Eine Kompressionstechnik, die weithin eingesetzt wird, ist das arithmetische Kodie ren. Arithmetisches Kodieren bildet einen Datenstring (d. h. eine "Nachricht") auf einen Kodestring in einer derartigen Weise ab, daß die Originalnachricht aus dem Kodestring bzw. der Kodefolge zurückgewonnen werden kann. Für eine Erörterung des arithmetische Kodierens siehe Glenn (G. Langdon, Jr., "An Introduction to Arithmetic Coding", IBM Journal of Research and Development, Band 28, Nr. 2 (März 1984). Ein wünschenswertes Merkmal von einigen älteren arithmetischen Kodiersystemen ist, daß die Kompression in einer einzigen Durchlaufabfolge über die Daten ohne einen festen Satz von Statistiken durchgeführt wird, um die Daten zu kodieren. Auf diese Weise ist das arithmetische Kodieren angepaßt.

Ein binärer Arithmetikkodierer ist eine Art von arithmetischem Kodiersystem. In einem binären arithmetischen Kodiersystem kann die Auswahl eines Symbols aus einer Liste bzw. einem Satz von Symbolen als eine Abfolge von binären Entscheidungen kodiert werden. Ein Beispiel eines binären Arithmetikkodierers ist der Q-Kodierer, der von IBM von Armonk, New York, entwickelt worden ist.

Die Maschinenendzustands(FSM)-Kodierer sind im Stand der Technik verwendet worden, um ein wirksames Entropiekodieren für einzelne Bits mit einer verknüpften Wahrscheinlichkeitsabschätzung bereitzustellen. Einige dieser FSM-Kodierer sind als Nachschlagetabellen bzw. Tabellen (LUTs) realisiert worden. Siehe hierzu beispiels weise die US-Patente Nrn. 5,272,478 und 5,363,099. Als ein Beispiel einer End zustandsmaschine, die eine Kanalmodulation und eine Fehlerkorrektur mit Entropieko dieren durchführt, sei auf das US-Patent Nr. 5,475,388 verwiesen.

Im allgemeinen sind Endzustandsmaschinen, die LUTs verwenden, für Mehr-Bit symbole nicht schnell. Falls z. B. eine Zahl zwischen einschließlich 0 und 7 zu kodieren ist, muß die Zahl in ein Minimum von drei Bits getrennt werden, wodurch drei separate Tabellennachschläge erforderlich werden. Der aufsummierte Aufwand von drei getrennten Nachschlägen verlangsamt den Kodierungsprozeß. Was erforder lich ist, ist, daß mehrere Tabellennachschläge vermieden werden, während Mehr-Bit symbole kodiert werden.

Das Kodieren nach Huffman stellt ein m-faches Kodieren zur Verfügung, bei dem ein Mehrfachsymbol kodiert und/oder dekodiert wird. Das Huffman-Kodieren erzeugt Kodes mit variabler Länge, die integrale (nicht bruchstückhafte) Bitzahlen sind. Mit anderen Worten gibt es keine Zeit, wenn der Kodierer Informationen enthält, die einige der Bits beeinflussen, die gerade auszugeben sind. Symbole mit höheren Wahrscheinlichkeiten erhalten kürzere Kodes.

Das Datenkodieren und -dekodieren sind äußerst zeitintensive Betätigungen. In vielen Systemen wird die Wahrscheinlichkeitsabschätzung unter Verwendung einer Tabelle durchgeführt. Wenn sowohl die Wahrscheinlichkeitsabschätzung als auch das Entro piekodieren als LUTs idealisiert werden, werden separate Nachschläge in Tabellen ohne Parallelität erforderlich. Es ist wünschenswert, getrennte Nachschläge in Ta bellen, falls möglich, zu vermeiden, um die Zeitmenge zu verringern, um die Wahr scheinlichkeitsabschätzung und das Entropiekodieren nach dem Stand der Technik durchzuführen.

Im Stand der Technik ist das Entropiekodieren üblicherweise schnell durchgeführt worden, jedoch ohne die bestmögliche Kompression, über beispielsweise das Kodieren nach Huffman, oder ist vollkommen adaptiv bzw. angepaßt gewesen, z. B. noch langsamer über arithmetisches Kodieren. Es ist wünschenswert, derartige Operationen bzw. Betätigungen zu beschleunigen, während sie angepaßt bzw. adaptiv bleiben.

Die vorliegende Erfindung stellt eine erhöhte Geschwindigkeit für das Entropiekodie ren unter Verwendung eines Endzustandsmaschinenkodierers bzw. eines Maschinenko dierers mit finitem Zustand zur Verfügung, der dazu in der Lage ist, Eingänge mit n Bits unterzubringen. Die vorliegende Erfindung stellt ferner das Kodieren von m fachen Symbolen, wie das Kodieren nach Huffman, bereit, mit der Ausnahme einer nicht-integralen Anzahl von Bits (bruchstückhaften bzw. fraktionierten). Die vorlie gende Erfindung stellt auch eher einen einzigen Tabellennachschlag sowohl für die Wahrscheinlichkeitsabschätzung als auch die Biterzeugung als zwei getrennte Be tätigungen bzw. Operationen zur Verfügung.

Die vorliegende Erfindung löst die eingangs genannten Aufgaben bzw. Nachteile im Stand der Technik durch die Gegenstände der unabhängigen Ansprüche 1, 8 bzw. 18. Vorteilhafte Ausführungsformen dieser unabhängigen Ansprüche werden durch die in den Unteransprüchen aufgeführten Merkmale vorgeschlagen.

Ein m-facher Endzustandsmaschinenkodierer bzw. Maschinenkodierer mit finitem Zustand wird beschrieben. Bei einer Ausführungsform weist der Kodierer nach der vorliegenden Erfindung eine Kanalzustands-Speichereinrichtung und eine Entropieko dierungs-Nachschlagtabelle auf, die Zustandsinformationen von der Kanalzustands- Speichereinrichtung empfängt. Die Entropiekodierungstabelle kodiert n Bits von Eingangsdaten zu einer Zeit bzw. zur gleichen Zeit in Reaktion auf die Zustands information von der Kanalzustands-Speichereinrichtung, wo bei n ≧ 2 ist.

Die vorliegende Erfindung wird vollständiger aus der im einzelnen dargelegten Beschreibung zu verstehen sein, die unten angeführt ist, und aus den begleitenden Darstellungen von verschiedenen Ausführungsformen der Erfindung, die jedoch nicht dazu benutzt werden sollten, um die Erfindung auf die spezifischen Ausführungs formen einzuschränken, sondern nur zur Erläuterung und zum Verständnis sind.

Fig. 1A stellt einen Endzustands-Maschinenabschätzer/-Kodierer bzw. einen finiten Zustandsmaschinenabschätzer/-Kodierer dar.

Fig. 1B stellt eine Ausführungsform des FSM-Kodierers dar.

Fig. 1C stellt einen Maschinenabschätzer/-Dekodierer mit finitem Zustand bzw. Endzustand dar.

Fig. 2 stellt eine Ausführungsform eines FSM-Kodierers für Zwei Bit zu einer Zeit dar, der dazu in der Lage ist, beliebige Wahrscheinlichkeiten zu verarbeiten bzw. handzuhaben.

Fig. 3 stellt einen FSM-Kodierer für Vier-Bit zu einer Zeit bzw. zur gleichen Zeit dar, der für Bits der gleichen Wahrscheinlichkeitsklasse kon struiert ist.

Fig. 4 stellt eine Ausführungsform eines FSM-Kodierers für Mehrfachsymbole (M-ary bzw. M-fach) dar.

Fig. 5 stellt einen Kodierer dar, der dazu in der Lage ist, die gleiche Operation wie nach Fig. 1A, Fig. 3 und Fig. 4 durchzuführen, indem zwei zusätzliche Bits als einem Tabellenselektor verwendet werden.

Fig. 6 stellt eine Ausführungsform einer Abschätzung mit einer Tabelle und eines Kodiersystems dar.

Fig. 7 stellt eine Ausführungsform eines Maschinenabschätzers/-Kodierers mit Endzustand bzw. mit finitem Zustand dar, indem der Wahrscheinlich keitsabschätzungszustand das wahrscheinlichste Symbol (MPS) enthält.

Fig. 8 zeigt einen Kodierungsbaum, der durch den Huffman-Algorithmus für einen bestimmten Satz von Symbolen erzeugt worden ist.

Ein Verfahren und eine Vorrichtung zum Komprimieren und Dekomprimieren wird beschrieben. In der nachfolgenden, im einzelnen dargelegten Beschreibung der vorliegenden Erfindung werden zahlreiche spezifische Einzelheiten in den Vorder grund gerückt, wie etwa Arten von Kodierern, Anzahlen von Bits, Signalnamen usw., um ein sorgfältiges Verständnis der vorliegenden Erfindung zu ermöglichen. Jedoch wird es dem Fachmann im Stand der Technik vor Augen geführt, daß die vorliegende Erfindung ohne diese spezifischen Einzelheiten praktiziert werden kann. In anderen Beispielen sind wohlbekannte Strukturen und Einrichtungen in der Gestalt von Block diagrammen eher als im einzelnen gezeigt, um es zu vermeiden, daß die vorliegende Erfindung unklar gemacht wird.

Einige Teile der im einzelnen dargelegten Beschreibungen, die folgen, werden in Algorithmen und symbolischen Darstellungen von Operationen, die auf Daten in nerhalb eines Computerspeichers angewendet werden, dargestellt. Diese algorith mischen Beschreibungen und Darstellungen sind die Mittel, die durch die Datenver arbeitungsfachleute im Stand der Technik verwendet werden, um das wesentliche bzw. die Substanz ihrer Arbeit anderen Fachleuten im Stand der Technik am wirksamsten zu übermitteln. Ein Algorithmus wird hier und allgemein als eine selbstkonsistente Abfolge von Schritten aufgefaßt, die zu einem gewünschten Ergebnis führen. Die Schritte sind von der Art, die physikalische Manipulationen von physikalischen Größen bzw. Mengen erfordern. Obwohl dies üblicherweise nicht erforderlich ist, haben die Größen die Gestalt von elektrischen oder magnetischen Signalen, die gespeichert, übertragen, kombiniert, verglichen und anders manipuliert bzw. verändert werden können. Es hat sich vor einiger Zeit als angenehm erwiesen, prinzipiell aus Gründen der allgemeinen Verwendung, auf diese Signale als Bits, Werte, Elemente, Symbole, Charakter, Ausdrücke, Zahlen bzw. Ziffern oder dergleichen Bezug zu nehmen.

Es sollte jedoch zur Kenntnis genommen werden, daß all diese und ähnliche Aus drücke in Verbindung mit passenden physikalischen Größen zu bringen sind und lediglich bequeme Bezeichnungen sind, die diesen Größen zugeordnet sind. Falls es nicht gesondert anders zum Ausdruck gebracht wird, wie es aus der nachfolgenden Erörterung hervorgeht, wird es bevorzugt, daß sich über die vorliegende Erfindung hinweg Erörterungen, die Ausdrücke, wie etwa "Verarbeiten" oder "Berechnen" oder "Rechnen" oder "Bestimmen" oder "Anzeigen" oder dergleichen, verwenden, auf Tätigkeiten und Verfahren eines Computersystems oder einer ähnlichen elektronischen Recheneinrichtung beziehen, die Daten, die als physikalische (elektronische) Größen innerhalb eines Registers oder Speichers des Computersystems oder anderen der artigen Informationsspeicher-, -übertragungs- oder -wiedergabeeinrichtungen darstellt, manipuliert oder überträgt. Derartige Computersysteme setzen üblicherweise einen oder mehrere Prozessoren ein, um Daten zu verarbeiten, die an einen oder mehrere Speicher über einen oder mehrere Busse bzw. Datenbusse angekoppelt sind.

Die vorliegende Erfindung bezieht sich auch auf eine Vorrichtung, um die hier erläuterten Operationen bzw. Betätigungen durchzuführen. Diese Vorrichtung kann speziell für die erforderlichen Zwecke konstruiert sein oder sie kann einen Computer für generelle Zwecke aufweisen, der wahlweise aktiviert oder durch ein Computer programm, das im Computer gespeichert ist, neu konfiguriert wird. Ein derartiges Computerprogramm kann in einem mit dem Computer lesbaren Speichermedium ge speichert sein, wie etwa eine Art von Scheibe, die Disketten, optische Scheiben, CD-ROMs und magneto-optische Scheiben, statische Speicher (ROMs), Speicher (RAMs) mit wahlfreiem Zugriff, EPROMs, EEPROMs, magnetische oder optische Karten oder irgendeine Art von Medium enthalten, die zur Speicherung elektronischer Befehle geeignet sind, die jeweils an einen Bus des Computersystems angekoppelt sind, wobei die lesbaren Speichermedien nicht auf die vorgenannten beschränkt sind. Die hier dargestellten Algorithmen und Wiedergaben sind nicht inhärent auf irgendeinen bestimmten Computer oder andere Vorrichtungen bezogen. Verschiedene Maschinen für allgemeine Zwecke können mit Programmen gemäß den hier wiedergegebenen Lehren verwendet werden oder es kann sich als passend bzw. bequem erweisen, spezialisiertere Vorrichtungen zu konstruieren, um die erforderlichen Verfahrens schritte durchzuführen. Der erforderliche Aufbau für eine Anzahl dieser Vorrichtun gen bzw. Maschinen wird aus der folgenden Beschreibung ersichtlich. Ferner wird die vorliegende Erfindung nicht unter Bezugnahme auf irgendeine bestimmte Program miersprache beschrieben. Es ist vorzuziehen, daß verschiedene Programmiersprachen verwendet werden können, um die Lehren der hier beschriebenen Erfindung in die Tat umzusetzen.

Die vorliegende Erfindung stellt eine Beschleunigung für einen Endzustands-Maschi nenkodierer bzw. einen Maschinenkodierer mit finitem Zustand durch Kodieren von n Bits zu einer Zeit zur Verfügung. Mit anderen Worten stellt die vorliegende Erfin dung das Kodieren eines Alphabets von M-Symbolen (wobei M <= 2) unter Verwen dung eines Maschinenkodierers mit finitem Zustand bzw. mit Endzustand zur Verfü gung. Das Kodieren von M-Symbolalphabeten führt zu einer erhöhten Geschwindig keit und einer erhöhten Kompressionsfunktion. Die vorliegende Erfindung führt auch ein Laufkodieren, ein Kodieren nach Huffman und andere Kodierungen mit mehreren Symbolen mit einem FSM-Kodierer durch. Die Kombination des FSM-Kodierers mit dem Mehr-Symbolkodierer bzw. Mehrfach-Symbolkodierer stellt sowohl die Ge schwindigkeit der Mehr-Symbolkodes als auch die Kompressionsfunktion zur Verfü gung, die typischerweise nur mit arithmetischen Kodes möglich ist.

Der FSM-Kodierer nach der vorliegenden Erfindung kann mehrere Nachschlagtabellen (LUTs) verwenden. Jede LUT ist für die Verwendung in einer bestimmten Situation erzeugt worden. Wie z. B. in weiteren Einzelheiten unten beschrieben, kann eine der Tabellen zur Verwendung mit den letzten signifikanten Bits von Wavelet-Koeffizienten verwendet werden, die typischerweise 50% aus 1 und 50% aus 0 bestehen. Jede der Tabellen wird verwendet, um unterschiedliche Arten von Kodierern in bezug auf den gleichen Bitstrom durchzuführen. Die vorliegende Erfindung verwendet den Kodierer, in dem zwischen diesen Tabellen während des Kodierens zurück- und vorwärts geschaltet wird, während die fraktionalen Bits bzw. die buchstückhaften bzw. gebro chenen Bits in dem Bitstrom aufrechterhalten werden.

Im Stand der Technik kann das auf FSM basierende Kodiersystem drei Tabellen verwenden. Die erste der Tabellen enthält die gegenwärtige Wahrscheinlichkeits abschätzung und den Wert des wahrscheinlichsten Symbols (MPS) für jeden Kontext, für den eine Abschätzung durchgeführt wird. Die Eingänge in diese Tabelle werden mit jedem Symbol geändert, das in einem Kontext kodiert wird. Eine zweite Tabelle stellt die Aktualisierungen der Wahrscheinlichkeitsabschätzungen bereit. Diese Tabelle ändert sich nicht und aktualisiert Eingänge in die Kontexttabelle. Die dritte Tabelle ist der Satz bzw. die Liste von Zuständen, die legale Ausgänge zu dem Bitstrom be schreibt. Diese Tabelle ändert sich nicht und aktualisiert den gegenwärtigen Zustand für den Kodierer variabel. Die Tabelle zeigt auch an, was für Bits ausgegeben werden sollten.

Der Dekodierer verwendet die gleichen Tabellen zum Speichern von Wahrscheinlich keitsabschätzungen und zum Aktualisieren von Wahrscheinlichkeitsabschätzungen, verwendet aber eine andere Tabelle zum Kodieren. Die dritte Tabelle in dem Dekoder schaut nach Eingangsbits und Wahrscheinlichkeitsabschätzungen nach und bestimmt, ob die MPS auftritt, bestimmt den nächsten Zustand und bestimmt die Anzahl von Bits, durch die der Eingangsstrom zu verschieben ist, um die nächste Dekodier operation vorzubereiten. Eine Ausführungsform der Größen und Strukturen dieser Tabellen wird in der Tabelle 1 unten angegeben.

Tabelle 1

Die Fig. 1A ist eine Blockdarstellung einer Ausführungsform eines Maschinenabschät zers/-Kodierers mit endlichem Zustand bzw. finitem Zustand mit zwei Tabellen, die Anschlüsse zwischen den Tabellen darin darstellen. Bezugnehmend auf Fig. 1A wird ein Kontextspeicher 101, der die gegenwärtige Wahrscheinlichkeitsabschätzung den MPS-Wert für jeden Kontext, für den eine Abschätzung durchgeführt ist, speichert, gekoppelt, um einen Kontext 110, eine Nächst_mps-Anzeige 111 vom Exklusiv-Oder (XOR) 102 und eine Nächst_p-Zustandsanzeige 112 zu empfangen. Die Nächst_mps- Anzeige 111 stellt eine Anzeige für den Kontextspeicher 101 zur Verfügung, was das nächste MPS ist. Das heißt, die Nächst_mps-Anzeige 111 zeigt an, ob sich das MPS geändert hat. Die Nächst_p-Zustandsanzeige 112 stellt einen Hinweis für den Kontext speicher 101 im Hinblick darauf, was die nächste Wahrscheinlichkeitsabschätzung ist, zur Verfügung. Auf der Grundlage dieser Eingänge wird auf den Kontextspeicher 101 zugegriffen und der gegenwärtige Wahrscheinlichkeitszustand (p-Zustand) 113 und das gegenwärtige MPS werden ausgegeben.

Das gegenwärtige MPS 114 wird zu einem Eingang des XOR-Gatters 102 gekoppelt. Der andere Eingang des XOR-Gatters 102 wird zu einem Ausgang, dem Kipp_mps bzw. dem Toggle_mps 115, der Wahrscheinlichkeitsabschätzungstabelle 102 gekop pelt. In einer Ausführungsform wird dann, wenn das Kipp_mps-Signal 115 gleich "1" ist und der Wert des p-Zustands 113 kleiner als 215 ist, oder ein Ausgang (Ausgangs größe 122<0) dort ist, der Wert des MPS, der in dem Kontextspeicher 101 gespei chert ist von "0" auf "1" oder von "1" auf "0" geändert.

Ein Komparatorblock 104 ist angekoppelt bzw. angeschlossen, um das momentane bzw. gegenwärtige MPS 114 zu empfangen und vergleicht das gegenwärtige MPS 114 mit dem Eingangsbit 116. Falls das Ergebnis des Vergleichs anzeigt, daß das MPS 114 dem Eingangsbit 116 gleicht, wird die "Gleichheits"-Anzeige 117 angegeben. Falls das Ergebnis des Vergleichs anzeigt, daß das MPS 114 nicht gleich dem Ein gangsbit 116 ist, wird die "Gleichheits"- bzw. "Wahrscheinlichkeits"-Anzeige 117 nicht angezeigt.

Die Währscheinlichkeitsabschätzungstabelle 103 wird angeschlossen, um den p-Zu stand 113 und die Gleichheits- bzw. Wahrscheinlichkeitsanzeige 117 zu empfangen und gibt auf der Grundlage dieser Eingänge eine Wahrscheinlichkeitsklasse (p-Klasse) 118, das Kipp_ bzw. Toggle_mps 115 und die Nächst_p-Zustandsanzeige 112 aus. Das Kipp_mps 115 zeigt an, ob das MPS von 1 auf 0 oder umgekehrt geändert werden sollte. Die tatsächliche Wahrscheinlichkeitsabschätzung wird durch eine Klasse dargestellt, auf die hier als P-Klasse Bezug genommen wird. Jede P-Klasse wird für einen Bereich von Wahrscheinlichkeiten verwendet. In einer Ausführungsform wird jede P-Klasse für einen Wahrscheinlichkeitsbereich verwendet, anstatt verschiedene Bits zu verwenden, um eine genaue Wahrscheinlichkeit zu spezifizieren. In dieser Weise werden nur ein paar Bits benötigt, um zu spezifizieren, in welchem Klassen bereich die Wahrscheinlichkeit liegt. Bei einer Ausführungsform werden vier Bits verwendet, um die P-Klasse zu spezifizieren.

Eine Ausführungsform der Wahrscheinlichkeitsabschätzungstabelle 103 wird in der Tabelle 2 unten gezeigt:

Eintritt PEM

Die Entropiekodiertabelle 105, die eine Maschine mit finitem Zustand bzw. End zustand darstellt, ist angekoppelt, um die P-Klasse 118, die Wahrscheinlichkeits anzeige 117 und einen Ausgang vom Kanalzustand 106 zu empfangen und erzeugt 0 oder mehr Ausgangsbits wie der als dem komprimierten Bitstrom. Der Kanalzustand 106 speichert gebrochene Bits bzw. Bitbrüche, die den gegenwärtigen Zustand dar stellen, in dem der Ausgangskanal ist. In einer Ausführungsform weist der Kanal zustand 106 ein Register oder ein anderes Speicherelement auf, das Zustands informationen speichert. In einer Ausführungsform speichert der Kanalzustand 106 sechs Bits der Kanalinformationen. Der Ausgang des Kanalzustands 106 tritt in Reaktion auf eine nächste Zustandsanzeige, dem Nächst_Zustand 119, auf, der von der Entropiekodierungstabelle 105 ausgegeben wird.

Basierend auf ihren Eingängen gibt die Entropiekodierungstabelle 105 ein oder mehr Bits als dem komprimierten Datenstrom, auf den hier als Ausgangsbit 121 Bezug genommen wird, und eine Anzeige der Anzahl von Bits in dem Ausgang, auf die hier als Ausgangsgröße 122 Bezug genommen wird, aus. Man bemerke, daß die Ausgangs größe 122 nur eine Anzeige sein kann, im Hinblick auf welche Bits im Ausgangsstrom eine Signifikanz vorhanden ist. Die Entropiekodiertabelle 105 erzeugt auch ein oder mehrere Bits, um den nächsten Zustand anzuzeigen, auf den als Nächst_Zustand 119 Bezug genommen wird. Der Nächst_Zustand 119 wird in den Kanalzustand 106 als dem Zustand, der für das nächste Bit(s) eingegeben wird, eingespeist.

Bei einer Ausführungsform weist die Entropiekodiertabelle 105 eine Nachschlagtabelle (LUT) auf, die mehrere Zustände hat, wobei jeder der Zustände ein oder mehrere Paare von legalen Übergängen hat. Jeder Übergang wird definiert, um das Speichern von null oder mehr Bits, die wegzulassen sind, zu verursachen, wenn der Übergang auftritt, und ein Zielzustand auftritt, auf den der Übergang während des Übergangs transferiert. Es ist wegen dieses Zielzustands, daß die LUTs es fortsetzen, das nächste Symbol zu verarbeiten.

Die Fig. 1B stellt eine Ausführungsform des FSM-Kodierers dar. Bezugnehmend auf Fig. 1B wird die Entropiekodier-Nachschlagtabelle 105 angeschlossen, um sechs Bits der Zustandsinformation von dem Zustandsregister 106 zu empfangen, wobei vier Bits die P-Klasse darstellen und ein Bit die Wahrscheinlichkeitsanzeige bereitstellt. In Folge stellt die Entropiekodier-Nachschlagtabelle 105 8 Ausgangsbits (AUSBITS) bereit, vier Bits, um die Ausgangsgröße (AUSGRÖSSE) anzuzeigen und 6 Bits, um den nächsten Zustand anzuzeigen.

Eine Reihe von Puffern kann verwendet werden, um die Ausgangsbits 121 zwischen zuspeichern bzw. zu puffern. Diese Puffer werden nicht gezeigt, um zu vermeiden, daß die vorliegende Erfindung unklar wird.

Eine Ausführungsform der Wahrscheinlichkeitsabschätzungs- und der FSM-Kodierta belle, die verwendet werden, um die Entropiekodierung durchzuführen, werden in den Tabellen 3 und 4 unten gezeigt. Die Tabelle 3 zeigt einen Auszug der Wahrscheinlich keitsabschätzungstabelle, während die Tabelle 4 Auszüge aus der FSM-Kodiertabelle gibt.

Auszüge der Wahrscheinlichkeitsabschätzungstabelle

Die Tabelle 4 zeigt nur die ersten und letzten paar Reihen bzw. Zeilen und wird durch den Zustand, die Wahrscheinlichkeitsklasse und LPS/MPF befehligt bzw. bestellt. Jeder Eintritt in die Tabelle ist dreifach (nächster Zustand, Ausgang, Ausgangsbits). Das dritte Element läßt die Anzahl der Ausgangsbits erkennen, die zu dem kom primierten Ausgangsstrom addiert werden sollten, was es ermöglicht, 0 und 00 zu unterscheiden.

Auszüge aus der Kodiertabelle

Die Fig. 1C stelle eine Blockdarstellung eines Maschinendekoders mit finitem Zustand dar. Der Kontextspeicher ist genau derselbe wie es für den Dekoder die Wahrscheinlichkeitsabschätzungstabelle ist. Die Entropiedekodiertabelle weist einen anderen Satz von Eingängen und Ausgängen auf, wie es unten beschrieben ist. Bezugnehmend auf Fig. 1C werden komprimierte Bits 130 durch ein Schieberegister 131 empfangen, welches komprimierte Bits für die Entropiekodiertabelle 115 bereit stellt. Die Entropiekodiertabelle 115 empfängt auch den Kanalzustand von dem Kanalzustandsspeicherbereich 106 und eine p-Klasse 118 von der Wahrscheinlichkeits abschätzungstabelle 103. In Reaktion auf diese Eingänge erzeugt die Entropiekodierta belle 115 einen LPS 132, den Nächst_Zustand 119 (wie in dem Dekoder) und die Ausgangsgröße 121.

Das LPS 132 wird an einen Eingang des Exklusiv-Oder(XOR)-Gatters 137 ange schlossen, das auch das gegenwärtige MPS 114 empfängt. Auf der Grundlage dieser zwei Eingänge wird ein Bit 140 von dem Decoder ausgegeben.

Das LPS 132 wird auch mit dem Kipp_MPS 115, das von der Wahrscheinlichkeits abschätzungstabelle 103 ausgegeben wird, durch das AND-Gatter 136 summiert. Der Ausgang des AND-Gatters 136 wird mit dem LPS 132 durch das XOR-Gatter 138 einer Exklusiv-Oder-Operation unterzogen, um die Nächst_p-Zustandsanzeige 112 zu erzeugen, die einen Eingang zu dem Kontextspeicher 101 darstellt.

Das LPS 132 wird auch als ein Auswählsignal für einen Multiplexer (Mux) 135 verwendet, um entweder das Nächst_LPS-Signal 133, das das nächste LPS anzeigt, oder das Nächst_MPS-Signal 132, das das nächste MPS anzeigt, auszugeben, die von der Wahrscheinlichkeitsabschätzungstabelle 103 ausgegeben werden. Der Ausgang von der Mux 135 ist das Nächst_MPS 111, das ein Eingang zu dem Kontextspeicher 101 ist.

Die Ausgangsgröße bzw. Ausgröße 121 wird von der Entropiekodiertabelle 115 ausgegeben, um die Anzahl der Bits zu steuern, um den komprimierten Bitstrom zu schieben, um den nächsten Eingang zu der Entropiekodiertabelle 115 bereitzustellen.

Der Dekoder kann aus dem Kodierer unter Verwendung des unten gezeigten Kodes hergeleitet werden. Gegeben sei die Kodiertabelle von der Form der Tabelle 4, wobei die Funktion maketable (table, 62, 16) zu einer Dekodiertabelle zurückkehren wird, die durch den Zustand, die Wahrscheinlichkeitsklasse und die komprimierten Bits (8 Bit für den komprimierten Datenstrom) in der Gestalt der Tabelle 5 indexiert ist.

Dekodererzeugungskode

Ein Auszug für die Dekodiertabelle ist in der Tabelle 5 unten gezeigt.

Teil der FSM Dekodiertabelle

Mehrere Bits bei mehreren Wahrscheinlichkeiten

Eine Entropiekodiertabelle kann aufgebaut werden, die mehrere Bits (gleiche Indika tionen) und mehrere Wahrscheinlichkeiten (Wahrscheinlichkeitsklasse) zu einer Zeit akzeptiert. Ein Beispiel einer derartigen Tabelle wird in Fig. 2 gezeigt. Bezugneh mend auf Fig. 2 wird eine Entropiekodierungs-Nachschlagtabelle 205 angeschlossen, um 16 Eingangsbits zu empfangen, die die 6 Bits der Zustandsinformation vom Zustandsregister 106 aufweisen, 4 Bits, die eine erste Wahrscheinlichkeitsklasse P-Klasse-1 darstellen, ein Bit, das eine erste Wahrscheinlichkeitsanzeige Likely1 bereit stellt, vier Bits, die eine zweite Wahrscheinlichkeitsklasse P-Klasse-2 darstellen, und ein Bit, das eine zweite Wahrscheinlichkeitsanzeige Likely2 bereitstellt. Die En tropiekodierungstabelle 205 gibt 27 Bits aus, die 6 Bits aufweisen, die den nächsten Zustand darstellen, der zu dem Zustandsregister 106 zurückgeführt wird, 16 Aus gangsbits (AUSBITS) und fünf Bits, die die Größe des Ausgangs anzeigen (AUSGRÖSSE). Folglich kodiert die Entropiekodierungstabelle 205 zwei Bits für irgend welche Wahrscheinlichkeiten zu einer Zeit.

Ein Problem bei der Verwendung einer einzigen Tabelle, die mehrere Bits für mehre re Wahrscheinlichkeitsklassen zu einer Zeit unterbringen kann, ist, daß eine solche Tabelle mit der Anzahl der größer werdenden Eingänge sehr groß wird. Auch er fordert eine sehr große Tabelle mehr Bits, um die Tabelle zu adressieren, was ihre Geschwindigkeit verringert.

Mehrere Bits bei fester Wahrscheinlichkeit

Die vorliegende Erfindung stellt eine gesteigerte Geschwindigkeit für einen Kodierer zur Verfügung, indem mehrere Bits bei einer fixen Wahrscheinlichkeit zu einer einzigen Entropiekodiertabelle gesandt werden. Die fixe Wahrscheinlichkeit kann eine Wahrscheinlichkeitsklasse aufweisen. Jedoch bringt jede Tabelle, die n Biteingänge (n ≧ 2) unterbringt, nur eine derartige Klasse oder Wahrscheinlichkeit unter. Es sollte bemerkt werden, daß eine Tabelle aufgebaut werden kann, um verschiedene P-Klassen unterzubringen, jedoch die Unterbringung einer gesteigerten Eingangsgröße erfordert.

Ein Beispiel einer Tabelle, die mehrere Bits bei der gleichen Zeit unterbringt, ist eine Tabelle, die Bits handhabt, die bei einer Wahrscheinlichkeit von 0,5 (oder 50%) liegen. Die Fig. 3 stellt eine Ausführungsform einer derartigen Entropiekodiertabelle dar. Bezugnehmend auf Fig. 3 ist die Entropiekodiertabelle 305 angeschlossen, um 10 Eingangsbits zu empfangen, die 6 Bits der Zustandsinformation von dem Zustands register 306 zusammen mit vier Eingangsbits, Likely1-4, aufweisen und gibt 21 Bits aus, die sechs Bits der Nächst-Zustandsinformation, die dem Zustandsregister 306 zurück eingespeist werden, 11 Ausgangsbits (AUSBITS) und vier Bits, um die größe des Ausgangs (AUSGRÖSSE) anzuzeigen, aufweisen. Folglich werden unter Verwen dung der fixen Wahrscheinlichkeit die Größe des Eingangs und des Ausgangs im Vergleich zu der Tabelle nach Fig. 2 verringert.

Bei einer anderen Ausführungsform empfängt die Kodiertabelle mehrere Eingänge, die eine fixe Wahrscheinlichkeit haben, die stark abgeschrägt ist, wie etwa z. B. in dem oberen Bereich von 90% (beispielsweise näherungsweise 98, näherungsweise 99%, usw.).

Der FSM-Kodierer der vorliegenden Erfindung kann in ein Kodiersystem einbezogen werden, wie es etwa in Fig. 1A gezeigt ist. Bei einer Ausführungsform wird der Abschätzungszustand bei Pseudo-Zufallsintervallen aktualisiert. Indem nur bei Pseudo- Zustandsintervallen aktualisiert wird, müssen vollständige Zahlungen bzw. Zählwerte sämtlicher LPSs und MPSs nicht gespeichert werden. Bei einer Ausführungsform wird der Abschätzungszustand aktualisiert, wenn die Entropiekodierungstabelle 105 Aus gangsbits erzeugt. Bei einer Ausführungsform kann die Ausgangsgröße 122 mit Null verglichen werden, um zu bestimmen, wenn ein Ausgang aufgetreten ist. Dies er fordert es, daß die Tabelle Extrazustände enthält, um Änderungen der Wahrscheinlich keit auszugleichen, die zwischen den Aktualisierungen auftreten. Gleichermaßen kann der FSM-Dekoder auch in den Dekoder einbezogen werden, der in Verbindung mit Fig. 1A erörtert worden ist.

Tabellenerzeugung

Tabellen zum Handhaben mehrerer Bits zu einer Zeit im Gegensatz zu einzelnen Bits jeweils eines zu einer Zeit, können durch Anlegen einzelner Bits und Überwachen der Ausgangsbits und der nächsten Zustände, die auftreten, wenn eine Tabelle mit einem Bit zu einer Zeit verwendet wird, erzeugt werden. Dann können neue Ausgänge erzeugt werden, indem die Ausgangsbits von einer Reihe von Zuständen verknüpft bzw. verkettet werden. Der nächste Zustand für die Reihe ist der nächste Zustand, der von den letzten Ausgangsbits erzeugt wird. Dieses Verfahren wird durch die unten erörterten Beispiele deutlich gemacht. Die Tabelle ist häufig größer und enthält Eingänge, die durch Senden von Bits jeweils eines zu einer Zeit durch den gegenwär tigen Entropiekodierer bestimmt werden können. Das heißt, daß spezifische Tabellen konstruiert werden können, indem der Maschinenabschätzer/-Kodierer mit finitem Zustand bzw. Endzustand nach Fig. 1A verwendet wird. In den Entropiekodierta bellen, die mit mehreren Bits bzw. Mehrfachbits in dieser Weise aufgebaut werden, hält die vorliegende Erfindung die Kompatibilität mit binären Kodiertabellen aufrecht und ermöglicht es den Tabellen, an irgendeinem Punkt geschaltet zu werden, selbst mit Bruchteilen von Bits.

Zum Beispiel wird ein beispielhafter FSM-Kodierer in der Tabelle 6 unten dargestellt.

FSM-Kodierer

Ein FSM-Kodierer mit Zwei-Bit zu einer Zeit erzeugt einen nächsten Zustand und einen Ausgang in Antwort auf Eingänge, die den gegenwärtigen Zustand, zwei Wahrscheinlichkeitsklassen und zwei Ergebnisse aufweisen. Um zu bestimmen, was der nächste Zustand und der Ausgang sein sollte, werden der Ausgang von einem Kodierer mit einem Bit zu einer Zeit und der letzte Zustand nach dem Kodieren von zwei Bits verwendet. In dem Fall der Tabelle 1 z. B. ist anzunehmen, daß der Kodie rer mit einem Bit zu einer Zeit in dem Zustand 0 ist und ein MPS in Klasse 1 zu kodieren ist, gefolgt durch ein MPS in Klasse 0. Das erste Bit veranlaßt den Kodierer mit einem zu einer Zeit, keine Bits auszugeben und sich zum Zustand 1 zu bewegen. Das zweite Bit ist im Zustand 1 kodiert und veranlaßt ein 0-Bit, ausgegeben zu werden und kehrt in den Zustand 0 zurück. Der Ausgang der neuen Tabelle für diesen Eingang mit zwei Bit würde 0 sein, was sich aus der Verkettung des Nicht-Bits verknüpft mit dem ersten Bit und dem 0-Bitausgang ergibt, der mit dem zweiten Bit verknüpft wird. Der neue nächste Zustand in dem Kodierer mit zwei zu einer Zeit würde für den Eingang mit zwei Bits der Zustand 0 sein. Eine neue Tabelle, die mehrere (2) Bits zu einer Zeit handhabt, die von dem FSM-Kodierer mit einem Zustand nach Tabelle 6 erzeugt wird, wird in Tabelle 7 unten gezeigt.

Tabelle 7

Ein Beispiel eines Kodierers der Klasse 0 mit 3 Bit wird unten in Tabelle 8 gezeigt.

Klasse-0-Kodierer mit 3 Bit

Es sollte bemerkt werden, daß das Tabellenerzeugungsverfahren der vorliegenden Erfindung verwendet werden kann, um Tabellen von verschieden großen Eingängen zu erzeugen. Jedoch wird ein Zustand für jede mögliche Eingangsbitkombination benötigt.

Es ist häufig wünschenswert, Tabellen, wie etwa Tabelle 7, schneller zu machen. Jedoch würde, um eine Tabelle mit 64 Zuständen, die 16 Wahrscheinlichkeitsklassen hat, auf viermal so schnell zu beschleunigen, die Tabelle anstelle von 2¹¹ Eingängen 2²⁶ Eingänge haben müssen, die durch die einfach schnelle Tabelle verwendet werden, und ist in vielen Situationen nicht praktikabel.

M-fach-Kodieren Laufkodes

Bei einer Ausführungsform werden für ein schnelles Kodieren für 50% Bits (oder 60% Bits) und ein Golumb oder andere Startschritt-Stopp-Kodes bereitgestellt, die einzelne Bits und 50% Bits verwenden. Ein solcher Kode wird in dem Buch bzw. Aufsatz von Bell, Cleary, Witten, Text Compression, beschrieben. Die Tabelle 9 stellt ein Beispiel eines Start-Schritt-Stopp-Kodes dar:

Tabelle 9

Ein typischer Lauflängenkode wird in der Tabelle 10 gezeigt. Bezugnehmend auf Tabelle 10 ist dieser Kode gut, um einen Ablauf von Nullen mit einer Wahrscheinlich keit von näherungsweise 0,917 zu kodieren.

Tabelle 10

Bei einem derartigen System gibt es zumeist zwei Tabellennachschläge für bis zu acht kodierten Bits. Bei der vorliegenden Erfindung kann der Laufkode in Tabelle 10 unter Verwendung der FSM-Kodiertabelle für 1 und 4 50% Bits realisiert werden.

Eine Ausführungsform des Kodes zu Realisierung des Laufkodierers lautet:

Falls die maximale Lauflänge (8 in diesem Fall) auftritt, dann ist nur ein Bit auszu geben. Dies wird durch Kodieren einer 0 bei einer fixen Wahrscheinlichkeit von 50% getan (durchgeführt durch die Funktion FSMCode_bei_50). Dieses Kodieren wird naherungsweise ein Bit verwenden, wird jedoch beliebige Bruchbits von vorherigen Operationen aufrechterhalten. Falls ein Laufauftritt, der geringer als das Maximum ist, dann muß ein Wert von 4 Bit kodiert werden, der mit einer 1 beginnt. Dies wird unter Verwendung einer Nachschlagtabelle mit vier Bit zu einer Zeit durchgeführt, was der Zugriff über die Funktion FSMCode_4_Bits_bei_50 ist. Die 50 in dem Funktionsnamen bezieht sich auf die Tatsache, daß diese Funktion annimmt, daß die Wahrscheinlichkeit fix bei ein halb oder 50% liegt.

Eine Ausführungsform des Codes, der verwendet wird, um das Dekodieren zu realisieren, lautet wie folgt:

Der Dekodierer weiß im voraus nicht, wenn ein Wert mit 4 Bit oder ein Wert mit einem Bit dekodiert werden muß. So dekodiert er zuerst ein Bit bei 50% mit dem Aufruf FSMDekodieren_bei_500. Falls dieses Bit eine Zahl 1 ist, dann kodiert der Kodierer tatsächlich vier Bits, um einen Lauf zu beschreiben. Die verbleibenden drei Bits werden mit dem Aufruf FSMDekodieren_bei_500 dekodiert und ihr Wert ist die kodierte Lauflänge. Falls das erste dekodierte Bit eine 0 war, dann trat der maximale Lauf auf und es ist nicht nötig, irgendwelche zusätzlichen Bits zu dekodieren.

Huffman-Kodes und Huffman-ähnliche Kodes

Die vorliegende Erfindung stellt einen FSM-Kodierer zur Verfügung, der eine Kodier tabelle nach Huffman aufweist. Die Kodiertabelle nach Huffman kann die einzige Tabelle des FSM's sein oder kann eine von mehreren Entropiekodiertabellen in dem FSM sein. Bei einer Ausführungsform haben die Huffman-Bits eine Wahrscheinlich keit von 50% und sie werden mit einer fixen Wahrscheinlichkeit von 50% kodiert. Dies kann einen Kompressionsvorteil gegenüber Huffman-ähnlichen Kodes zur Verfügung stellen. Bei einer Ausführungsform werden die Bits anstelle von 50% schief bzw. abgeschrägt. Man bemerke, daß jedoch in diesem Fall diese Kompres sionsfunktion nicht besser werden würde als das Bit bei einem Zeitverfahren.

Man nehme an, ein Lauf bzw. eine Reihe von stark abgeschrägten Bits sei zu kodie ren. Zum Beispiel ist es mit 98% wahrscheinlich, daß Bits 0 sind und der Kodierer ist so zu konfigurieren, daß er einen Lauf bzw. Durchgang der Länge 0-5 kodiert, wie es in Tabelle 11 gezeigt ist.

Tabelle 11

wobei jeder Ast des Huffman-Baums näherungsweise 98% sein sollte, jedoch die Wahrscheinlichkeitsklasse nur eine Abschrägungseffizient von 90% ermöglichen kann. Ein Huffman-Baum mit diesen Wahrscheinlichkeiten wird in Fig. 8 gezeigt. Der Huffman-Kode kann verwendet werden, um die Anzahl von binären Entscheidungen zu verringern oder sogar zu minimieren und um die stark abgeschrägten Wahrscheinlichkeiten zu verringern. Zum Beispiel hat das erste kodierte Bit (nur) 90% Abschrägung, anstatt daß jedes Bit bei 93% Abschrägung bzw. Versatz kodiert wird. Ein FSM-Kodierer, der Huffmann-Ausgänge kodiert, wird effizienter sein als ein Huffman oder ein FSM-Kodierer, der eine Tabelle mit einem Bit zu einer Zeit einsetzt. Indem einfach der FSM-Kodierer mit einem Bit zu einer Zeit mit den wahrlichen Wahrscheinlichkeiten nach Fig. 8 verwendet wird und das Ereignis aufgezeichnet wird, kann eine Tabelle mit vier Bits zu einer Zeit aufgebaut werden.

Wird das FSM mit zwei Zuständen, wo die p-Klasse 0 für Wahrscheinlichkeiten von weniger als 0,618 verwendet wird und der Huffman-Baum nach Fig. 8 verwendet wird, kann die Tabelle 12 aufgebaut werden. Die Tabelle 10 läuft besser als der Huffman-Kode, weil 80% der Zeit werden in einer Zeile bzw. Reihe zwei Läufe bzw. Abfolgen einer Länge von 5 sein und dies wird ein Bit einsparen.

Tabelle 12

Die Fig. 4 stellt eine Ausführungsform einer Entropiekodiertabelle mit mehreren Symbolen bzw. Mehrfachsymbolen dar, die verwendet werden kann, um ein Kodie ren, wie etwa nach Huffman, oder ein Ablaufkodieren durchzuführen. Bezugnehmend auf Fig. 4 wird eine Entropiekodiertabelle 405 angekoppelt, um einen Eingang mit 14 Bits zu empfangen, der sechs Bits einer Zustandsinformation von dem Zustands register 406 und acht Bits von einem Symbol- oder Ablaufzählwert aufweist. Die acht Bits können irgendwelche ASCII-Charakter oder eine Lauflänge von 0 bis 255 an zeigen. In Folge gibt die Entropiekodiertabelle 405 25 Bits aus, die sechs Bits Zu standsinformationen für das Zustandsregister 406 aufweisen, die den nächsten Zustand darstellen. Die Entropiekodiertabelle 405 gibt auch 15 Ausgangsbits (AUSBITS) und vier Bits aus, die die Größe des Ausgangs anzeigen (AUSGRÖSSE).

Eine Entropiekodiertabelle mit mehreren Tabellen

Die vorliegende Erfindung stellt verschiedene Untersätze einer größeren Beschleuni gungstabelle zur Verfügung, die nützlich sind. Das heißt, in einer Ausführungsform wird die Entropiekodiertabelle mit n Bit zu einer Zeit nur eine einer Anzahl von Nachschlagtabellen sein, die durch das Entropiekodier-FSM eingesetzt wird. Das FSM kann mehrere Tabellen einsetzen, die konstruiert sind, um eine unterschiedliche Anzahl von Bits (zwei oder größer) für individuell fixierte Wahrscheinlichkeiten unterzubringen. Ein System kann eine Tabelle mit einem zu einer Zeit und eine Tabelle enthalten, um verschiedene Bits mit der gleichen Wahrscheinlichkeit zu kodieren. Auf diese Weise werden mehrere Bits mit der gleichen Wahrscheinlichkeit kodiert, so wie z. B., wenn die Wahrscheinlichkeit 50% beträgt oder sehr stark abgeschrägt bzw. erhöht ist (z. B. 99%). Eine spezielle Tabelle für eine beliebige fixe Wahrscheinlichkeit oder selbst ein fixes Muster von Wahrscheinlichkeiten könnte leicht erzeugt werden (z. B. ein 50%iges Bit, dann ein 99%iges Bit, dann zwei 60%ige Bits).

In einer Ausführungsform verwendet die vorliegende Erfindung eine LUT mit einem Bit zu einer Zeit in Verbindung mit einem oder mehreren LUTs mit n Bits zu einer Zeit mit fixer Wahrscheinlichkeit, um Wavelet-Koeffizienten zu kodieren. Die zwei letzten signifikanten Bits der Wavelet-Koeffizienten sind typischerweise mit 50%iger Wahrscheinlichkeit bzw. 50%igem Zufall 1 oder 0 (d. h. die Wahrscheinlichkeiten sind nahe bei 0,5). Die oberen Bits bzw. Kopfbits in dem Koeffizienten, die in dem Artikel von Edward L. Schwartz, Ahmad Zandi, Martin Boliek, "Implementation of Com pression with Reversible Embedded Wavelets", Proc. of SPIE 40th Annual Meeting, Band 2564, San Diego, CA, Juli 1995, sind stark abgeschrägt, näherungsweise bei 99% Nullen. Eine getrennte LUT bringt mehrere Kopfbits zu einer Zeit unter.

Wenn mehrere Tabellen verwendet werden, um den FSM-Kodierer zu realisieren, hält die vorliegende Erfindung die gleichen Kanalzustände als einen Eingang zu sämtlichen der Tabellen aufrecht. In einer Ausführungsform gibt ein einzelnes Kanalzustands register dieselbe Zustandsinformation als einen Eingang zu sämtlichen der Tabellen aus. In einer Ausführungsform wird der nächste Zustand, der von der Tabelle ausge geben wird, als Rückkopplung zu den Kanalzustandsregistern für sämtliche Tabellen verwendet. Man bemerke, daß dies erfordert, daß sämtliche der Tabellen denselben Zustand haben müssen. Die Steuerlogik kann verwendet werden, um zu steuern, auf welche Tabelle auf der Grundlage der Eingänge durch Schalten zwischen den Tabellen zugegriffen wird. Die Steuerlogik kann eine Reaktion über das Passen bzw. Zutreffen für die Eingänge aufweisen. In einer anderen Ausführungsform wird auf sämtliche der Tabellen zu jeder Zeit zugegriffen, wobei jedoch der Ausgang von sämtlichen der Tabellen einem Multiplexen unterzogen wird. In diesem Fall wählt die Steuerlogik nur einen Satz von Eingängen als die Ausgänge des FSM-Kodierers aus. Indem der gleiche Kanalzustand für jede der Tabellen verwendet wird, werden keine Bruchbits verloren, wenn zwischen den Kodierern geschaltet wird.

Bei einer Ausführungsform, in der das Kopfbit bzw. das führende Bit und die letzten signifikanten Bits der Koeffizienten (Schwanzbits) mit einer n Bit-Tabelle (n < 2) kodiert werden, kann eine Tabelle mit einem Bit zu einer Zeit für jene Bits zwischen dem führenden und den Schwanzbits verwendet werden.

Man bemerke, daß derartige Tabellen nicht übermäßig groß sind, weil die Anzahl der Bits, die erforderlich sind, um die Wahrscheinlichkeit darzustellen (z. B. 4 Bits), sich nicht für jedes der Eingangsbits ändert. Die Wahrscheinlichkeit braucht nur einmal gesendet zu werden, anstelle mit jedem Bit, das zu kodieren ist.

Ähnlich zu der oben erörterten, kann die Multi-Symboltabelle bzw. Mehrfach-Symbol tabelle nach Fig. 4 eine der mehreren Tabellen sein, die durch den FSM-Kodierer eingesetzt werden. Die Fig. 5 stellt einen Kodierer dar, der dazu in der Lage ist, die gleiche Operation wie in Fig. 1A vorzunehmen (eine FSM-Tabelle mit einem Bit zu einer Zeit), 3 (eine FSM-Tabelle mit 4 Bit zu einer Zeit, die bei einer fixen Wahr scheinlichkeit von 50% operiert) und 4 (eine FSM-Tabelle mit Huffman-Kode), indem zwei zusätzliche Bits als einem Tabellenselektor verwendet werden. Der Rest der Bits würde gleichbleiben, wie sie in der vorherigen Tabelle verwendet worden sind. Die Eingangs- und Ausgangsgrößen werden auf der Grundlage der maximalen Größe bestimmt, die durch die Subtabellen benötigt werden (plus die Selektorbits). Be zugnehmend auf Fig. 5 empfängt die Entropiekodiertabelle 505 18 Bits des Eingangs, mit 6 Bits über die Zustandsinformationen, den 2 Bits des Tabellenselektors und den 10 tabellenspezifischen Bits. Für das Laufkodieren bzw. Ablaufkodieren können diese eine Lauflänge sein, wobei vier davon vier 50%ige Bits usw. sein könnten. Die Entropiekodiertabelle 505 gibt 27 Bits aus, die 6 Zustandsinformationsbits, die eine Rückkopplung zu dem Zustandsregister 506 sind, 16 Ausgangsbits und 5 Bits sind, die die Größe des Ausgangs anzeigen.

Kombinieren von Tabellen

In einer Ausführungsform kann die Anzahl der Tabellen in einem System, wie etwa die Tabellen in Fig. 1A, durch das Kombinieren von Tabellen verringert werden. Da die Tabelle zum Aktualisieren des Abschätzungszustandes einen Ausgang hat, der als ein Eingang zu der Entropiekodierungszustandstabelle verwendet wird, können die Eingänge und Ausgänge dieser zwei Tabellen kombiniert werden. Die Integration der FSM und der Wahrscheinlichkeitsabschätzungsmaschine (PEM) stellen eine Ver besserung der Geschwindigkeit zur Verfügung, wenn ein Bit zu einer Zeit kodiert wird.

Eine Ausführungsform, die diese kombinierte Tabelle hat, wird in Fig. 6 gezeigt. Bezugnehmend auf Fig. 6 wird ein Kontextspeicher 101 angekoppelt bzw. angeschlos sen, um einen Kontext 110 von einem Kontextmodell (nicht gezeigt, um zu vermei den, daß die vorliegende Erfindung unklar wird) und eine Nächst_np-Zustandsanzeige 612 zu empfangen. Wie oben beschrieben, stellt die Nächst_np-Zustandsanzeige 612 eine Anzeige für den Kontextspeicher 101 zur Verfügung, im Hinblick auf welchen der nächste Wahrscheinlichkeitsabschätzungszustand gilt. Aufgrund dieser Eingänge wird auf den Kontextspeicher 101 zugegriffen und er gibt den gegenwärtigen Wahr scheinlichkeitszustand (np-Zustand) 613 aus.

Die verbundene Wahrscheinlichkeitsabschätzungs- und Entropiekodiertabelle 603 wird angeschlossen, um den np-Zustand 613, das gegenwärtige Bit 616 und einen Ausgang des Kanalzustands 606 zu empfangen. Der Ausgang des Kanalzustands 606 ist in Reaktion auf eine nächste Zustandsanzeige (Nächst_Zustand), die von der verbunde nen Wahrscheinlichkeitsabschätzungs- und Entropiekodiertabelle 601 ausgegeben wird. Basierend auf ihre Eingänge erzeugt die verbundene Wahrscheinlichkeitsabschätzungs- und Entropiekodiertabelle 601 Ausgangsbits, die als Ausgangsbits 121 gezeigt sind, und eine Anzeige der Ausgangsgröße, die als Ausgröße 122 gezeigt ist. Die verbunde ne Wahrscheinlichkeitsabschätzungs- und Entropiekodiertabelle 601 erzeugt auch die Nächst_np-Zustandsanzeige 612, die den nächsten Wahrscheinlichkeitsabschätzungs zustand anzeigt.

Eine Ausführungsform der verbundenen Wahrscheinlichkeitsabschätzungs- und Entropiekodiertabelle 601 wird unten in der Tabelle 13 gezeigt.

Verbundenen Wahrscheinlichkeitsabschätzungs- und Entropiekodiertabelle

Die Dekodertabelle ist unterschiedlich, weil die Kodier- und Dekodier-Kodiererta bellen unterschiedlich sind. Zum Beispiel enthält der Dekodierer die folgenden Eingänge. Einen Eingang für komprimierte Bits, der den komprimierten Bitstrom darstellt, einen Eingang für den Kanalzustand, der den Kanalzustand darstellt, und einen Eingang für den p-Zustand, der den Wahrscheinlichkeitsabschätzungszustand darstellt. Die Ausgänge der Dekoder enthalten das folgende: einen Verschiebungs betrag, der einen Betrag anzeigt, um den eingegebenen komprimierten Bitstrom zu verschieben, eine MPS-Anzeige, einen Neu_p-Zustand, der den nächsten wahr scheinlichen Befehlszustand anzeigt, und eine Nächst_Zustandsanzeige, die den neuen Wahrscheinlichkeitsabschätzungszustand darstellt.

Für eine Pseudo-Zufallswahrscheinlichkeitsabschätzungstabelle ist der verbundene Tabellenkodierer von einer realisierbaren Größe. Die Verwendung einer einzigen Tabelle kann etwas Rechenzeit zu Lasten von Speicher einsparen.

Die Fig. 7 stellt eine geänderte Ausführungsform eines Kodierers dar, in dem der Wahrscheinlichkeitszustand das MPS enthält. Die Verwendung dieser Ausführungs form stellt eine rechnermäßige Verbesserung mit geringeren Speicherkosten als die eines Tabellenmethode dar, die in Verbindung mit Fig. 6 beschrieben worden ist. Diese Ausführungsform erfordert eine Abschätzungstabelle, die zweimal so groß als die Abschätzungstabelle ist, die oben im Hinblick auf Fig. 1A beschrieben worden ist, eliminiert jedoch das Erfordernis des Vergleichs und der Exklusiv-Oder-Operation (XOR).

Bezugnehmend auf Fig. 7 wird ein Kontextspeicher 101 angeschlossen, um einen Kontext 110 und eine Nächst_np-Zustandsanzeige 712 zu empfangen. Die Nächst_np- Zustandsanzeige 712 stellt eine Anzeige für den Kontextspeicher 101 zur Verfügung, im Hinblick auf den der nächste Wahrscheinlichkeitsabschätzungszustand zutrifft und enthält auch das MPS. Basierend auf diesen Eingängen wird auf den Kontextspeicher 101 zugegriffen und er gibt den gegenwärtigen Wahrscheinlichkeitszustand (np- Zustand) 713 aus.

Die Wahrscheinlichkeitsabschätzungstabelle 703 wird angeschlossen, um den p- Zustand 713 und das momentane Bit 116 zu empfangen und gibt auf der Grundlage dieser Eingänge eine Wahrscheinlichkeitsklasse (p-Klasse) 718 aus. Eine Ausführungs form der Wahrscheinlichkeitsabschätzungstabelle wird unten in Tabelle 14 gezeigt.

PEM mit XOR und enthaltendem Vergleich

Die Entropiekodiertabelle 705 ist angeschlossen, um die p-Klasse 718 und einen Ausgang von dem Kanalzustand 106 zu empfangen. Der Ausgang des Kanalzustands 106 ist in Reaktion auf eine nächste Zustandsanzeige, einen Nächst_Zustand 119, der von der Entropiekodiertabelle 705 ausgegeben wird. Auf der Grundlage ihrer Ein gänge erzeugt die Entropiekodiertabelle 705 Ausgangsbits, die als Ausgangsbits 121 gezeigt sind, und eine Anzeige der Ausgangsgröße, die als Ausgröße bzw. Ausgangs größe 122 gezeigt wird.

In Form von Software ist es vernünftig, ein fixes Feld mit einem Bit mit einem Feld mit neun Bits zu kombinieren, so daß der Kontextspeicher 101 von 4 Bytes pro Kontext (2 Bytes Abschätzungszustand + 1 Byte MPS-Anzeige + ein Byte Auffüllung bzw. Reserve) auf 2 Bytes pro Kontext verringert werden kann.

Systemanwendungen

Der hier beschriebene Entropiekodierer kann bei einer Vielzahl von Kompressions systemen verwendet werden. Zum Beispiel könnte der Entropiekodierer in dem JPEG- System verwendet werden. In einer Ausführungsform können der SSM-Kodierer und die Wahrscheinlichkeitsabschätzung den QM-Kodierer des Standard-JPEG-Systems ersetzen. Diese Ersetzung würde wahrscheinlich nur von den kombinierten Abschät zungs- und Entropiekodiertabellen profitieren. Eine alternative Ausführungsform könnte den Huffman-Kode von dem JPEG-Standard mit der M-fachen Version des hier beschriebenen FSM ersetzen. In der Tat verwendet der JPEG-Standard "Mantis senbits" und "Make-up-Bits" bzw. "Aufmachungsbits" in den Kodes. Die "Mantissen bits" könnten durch das M-fach-FSM kodiert werden und die "Aufmachungsbits" könnten durch das fixe N bei einer zeitlich 50%igen Bittabelle kodiert werden.

Gleichermaßen könnte der Entropiekodierer mit dem CREW-Wavelet-Kompressions system verwendet werden, wie es in dem Artikel von Edward L. Schwartz, Ahmad Zandi, Martin Boliek, "Implementation of Compression with Reversible Embedded Wavelets", Proc. of SPIE 40th Annual Meeting, Band 2564, San Diego, CA, Juli 1995, beschrieben. In dem CREW-System gibt es führende Bits bzw. Kopfbits, von denen es sehr wahrscheinlich ist, daß sie 0 sind. Diese führenden Bits bzw. Kopfbits könnten ein Kode sein, der eine fixe Wahrscheinlichkeit von z. B. 95% durch einen FSM-Kodierer mit n Bits zu einer Zeit verwendet. Ähnlich sind viele der "Schwanz bits" gleichermaßen wahrscheinlich gleich 0 oder 1 und könnten unter Verwendung eines FSM-Kodierers mit n Bits zu einer Zeit für eine 50%ige Wahrscheinlichkeit kodiert werden. Es gibt verschiedene Wege, über die die Kopf- oder Schwanzbits kodiert werden könnten. Zum Beispiel könnten vier Schwanzbits von einem einzigen Koeffizienten zusammen kodiert werden. Alternativ könnten die vier letzten signifi kanten Bits von vier verschiedenen Koeffizienten zusammen kodiert werden. Es gibt viele andere Möglichkeiten, die den Fachleuten im Stand der Technik ersichtlich sind. Es ist deutlich, daß andere Wavelet-Bildkompressionssysteme und selbst Text- oder Schall-Kompressionssysteme die verschiedenen Kodierungsmöglichkeiten des FSM-Kodierers der vorliegenden Erfindung verwenden können.

Während viele Abänderungen und Modifikationen der vorliegenden Erfindung einem Fachmann im Stand der Technik ohne Zweifel vor Augen geführt werden, so er die voranstehende Beschreibung liest, ist es zu verstehen, daß die besondere Ausführungs form, die im Wege einer Illustration gezeigt und beschrieben worden ist, nicht dazu gedacht ist, als einschränkend in Betracht gezogen zu werden. Deshalb ist es nicht beabsichtigt, daß Bezugnahmen auf Einzelheiten der vorliegenden Ausführungsform den Schutzbereich der Ansprüche beschränken, die in sich selbst nur jene Merkmale wiedergeben, die für die Erfindung als wesentlich angesehen werden.

Die vorliegende Erfindung betrifft eine Vorrichtung zum Kodieren und/oder Dekodie ren, die zum Komprimieren bzw. zum Expandieren bzw. Dekomprimieren von Daten verwendet wird. Eine Maschine mit finitem Zustand bzw. mit endlichem Zustand weist eine Anzahl von Tabellen auf, die zusammen mehrere Zustände haben. Eine der Tabellen kodiert Symbole mit mehreren Bits für fixe Wahrscheinlichkeiten.

Claims

1. Kodierer zum Kodieren von Dateneingängen, wobei der Kodierer aufweist:
eine Kanalzustandsspeichereinrichtung; und
eine Entropiekodiertabelle, die angeschlossen bzw. angekoppelt ist, um Zu standsinformationen von der Kanalzustandsspeichereinrichtung zu empfangen, und die konfiguriert ist, um n Bits von den Eingangsdaten zu einer Zeit in Reaktion auf die Zustandsinformationen zu kodieren, wobei n größer als oder gleich 2 ist.

2. Kodierer nach Anspruch 1, wobei die Entropiekodiertabelle n Bits bei einer fixen Wahrscheinlichkeit kodiert.

3. Kodierer nach einem der Ansprüche 1 oder 2, wobei die n Bits ein Symbol aufweisen.

4. Kodierer nach einem der Ansprüche 1 bis 3, wobei die Entropiekodiertabelle einen Huffman-Kodierer aufweist.

5. Kodierer nach einem der Ansprüche 1 bis 4, wobei die Entropiekodiertabelle einen Lauflängenkodierer aufweist.

6. Kodierer nach einem der Ansprüche 1 bis 5, wobei die Entropiekodiertabelle letzte signifikante Bits von Koeffizienten kodiert.

7. Kodierer nach einem der Ansprüche 1 bis 6, wobei die Entropiekodiertabelle führende Bits bzw. Kopfbits von Koeffizienten in dem Dateneingang kodiert.

8. System zum Kodieren von Eingangsdaten, insbesondere mit dem Kodierer nach einem der Ansprüche 1 bis 7, wobei das System aufweist:
ein Kontextmodell, das konfiguriert ist, um eine Reihe von binären Ent scheidungen in Reaktion auf Kontexte zu erzeugen;
ein Wahrscheinlichkeitsabschätzungsmodell, das an das Kontextmodell ange koppelt bzw. angeschlossen ist, um Wahrscheinlichkeitsabschätzungen für die Reihen von binären Entscheidungen zu erzeugen;
eine Kanalzustandsspeichereinrichtung; und
mehrere Entropiekodiertabellen, die angekoppelt sind, um Zustandsinformatio nen von dem Kanalzustandsspeicher zu empfangen, und konfiguriert sind, um Bits von den Eingangsdaten in Reaktion auf die Zustandsinformationen zu kodieren, wobei eine der mehreren Entropiekodiertabellen konfiguriert ist, um n Bits zu einer Zeit bzw. zur gleichen Zeit zu kodieren, wobei n größer als oder gleich 2 ist.

9. System nach Anspruch 8, wobei die eine der mehreren der Entropiekodierta bellen n Bits bei einer fixen Wahrscheinlichkeit kodiert.

10. System nach einem der Ansprüche 8 oder 9, wobei die eine der mehreren der Entropiekodiertabellen einen Huffman-Kodierer aufweist.

11. System nach einem der Ansprüche 8 bis 10, wobei die eine der mehreren der Entropiekodiertabellen einen Lauflängenkodierer aufweist.

12. System nach einem der Ansprüche 8 bis 11, wobei die eine der mehreren der Entropiekodiertabellen die letzten signifikanten Bits der Koeffizientenschwänze bzw. -enden kodiert.

13. System nach einem der Ansprüche 8 bis 12, wobei die eine der mehreren der Entropiekodiertabellen vorderte Bits bzw. Kopfbits der Koeffizienten in dem Datenein gang kodiert bzw. verschlüsselt.

14. System nach einem der Ansprüche 8 bis 13, wobei zumindest eine der mehre ren der Entropiekodiertabellen eine verbundene Wahrscheinlichkeitsabschätzungs- und Entropiekodiertabelle aufweist.

15. System nach einem der Ansprüche 8 bis 14, das ferner einen Schalter aufweist, der konfiguriert ist, um einzelne Tabellen der mehreren der Entropiekodiertabellen auszuwählen, um eines oder mehrere Bits der Eingangsdaten auf der Grundlage der Wahrscheinlichkeit zu kodieren.

16. System nach einem der Ansprüche 8 bis 15, wobei das Wahrscheinlichkeits abschätzungsmodell eine Tabelle aufweist.

17. System nach Anspruch 16, wobei das Kontextmodell eine Wahrscheinlichkeits zustandsanzeige zur Verfügung stellt, die eine Anzeige für ein wahrscheinlichstes Symbol (MPS) darin hat.

18. Kodierer zum Kodieren von Dateneingängen, insbesondere für ein System nach einem der Ansprüche 8 bis 17, wobei der Kodierer aufweist:
eine Kanalzustandsspeichereinrichtung; und
eine verbundene Wahrscheinlichkeitsabschätzungs- und Entropiekodiertabelle, die angekoppelt bzw. angeschlossen ist, um Zustandsinformationen von der Kanal zustandsspeichereinrichtung zu empfangen, und konfiguriert ist, um n Bits der Ein gangsdaten zu einer Zeit in Reaktion auf die Zustandsinformationen zu kodieren bzw. zu verschlüsseln, wobei n größer als oder gleich 2 ist.

19. Kodierer nach Anspruch 18, wobei die Entropiekodiertabeller n Bits bei einer fixen Wahrscheinlichkeit kodiert.

20. Kodierer nach Anspruch 18 oder 19, wobei die n Bits ein Symbol aufweisen.

21. Kodierer nach einem der Ansprüche 18 bis 20, wobei die Entropiekodiertabelle einen Huffman-Kodierer aufweist.

22. Kodierer nach einem der Ansprüche 18 bis 21, wobei die Entropiekodiertabelle einen Lauflängenkodierer aufweist.

23. Kodierer nach einem der Ansprüche 18 bis 22 bzw. nach Anspruch 8, wobei die Entropiekodiertabelle am wenigsten signifikante Bits von Koeffizienten kodiert.