-
Die
vorliegende Erfindung bezieht sich auf ein Verfahren zum Codieren
von Informationssignalblöcken,
wobei das Informationssignal abgetastet und quantisiert wird zum
Erhalten von Repräsentationssymbolen,
die daraufhin in Codeworte verschiedener Codewortlängen codiert
werden, wobei die Wahrscheinlichkeit des Auftritts für jedes
Repräsentationssymbol
bestimmt wird und Codeworte einer geringen Länge den Repräsentationssymbolen
zugeordnet werden, die eine hohe Wahrscheinlichkeit des Auftritts
haben und Codeworte einer größeren Länge Repräsentationssymbolen
zugeordnet werden, deren Auftrittswahrscheinlichkeit entsprechend
einer vorbestimmten Codierungstechnik gering ist, wobei Information über die
Länge der
Codeworte, die mit jedem Repräsentationssymbol
assoziiert sind, erzeugt wird.
-
Die
vorliegende Erfindung bezieht sich ebenfalls auf eine Anordnung
zum Bilden codierter Informationssignalblöcke mit Mitteln zum Abtasten
und Quantisieren eines Informationssignalblocks zum Erhalten von
Repräsentationssymbolen,
mit Mitteln zum Bestimmen der Auftrittswahrscheinlichkeit jedes Repräsentationssymbols
und mit Mitteln zum Bilden von Codes mit einer variablen Länge für die jeweiligen
Repräsentationssymbole,
wobei diese Codes zu einem Repräsentationssymbolblock
kombiniert werden.
-
Bei
einem derartigen Verfahren wird ein Informationssignal abgetastet
und quantisiert zum Erhalten von Repräsentationssymbolen, wobei diese Repräsentationssymbole,
nötigenfalls
nach einer weiteren Verarbeitung, danach in Codeworte mit verschiedenen
Codewortlängen
codiert werden.
-
In
US-A-5.488.616 ist ein Verfahren und eine Anordnung der oben genannten
Art beschrieben für variable
Längencodierung,
wobei Information über die
Länge der
Codeworte erzeugt wird.
-
Nach
der JPEG-Norm, wie diese beispielsweise in dem Buch: "JPEG Still Image
Compression Standard" von
William P. Pennebaker und Joan C. Mitchell beschrieben worden ist,
ist es bekannt, Codes zu verwenden, die als Huffman-Codes bezeichnet
werden, zur Codierung abgetasteter quantisierter Signale. Ein Huffman-Code
kann komplett dadurch spezifiziert werden, dass die Anzahl Codeworte
jeder beliebigen Codewortlänge
definiert wird. Die JPEG-Norm benutzt entweder feste Huffman-Tabellen,
wobei jedem Code ein festes Symbol zugeordnet wird, oder adaptive
Huffman-Tabellen, wobei eine Codetabelle auf Basis der Auftrittsfrequenz
von Symbolen bestimmt wird. Nach der JPEG-Norm wird ebenfalls ein
Repräsentationssymbol
für jedes
Codewort übertragen,
und zwar im Fall adaptiver Tabellen. Eine Huffman-Codierung basiert
auf dem Gedanken, dass eine effiziente Codierung mit Codeworten
verschiedener Länge
möglich
ist, wenn das kleinste Codewortlänge
denjenigen Codeworten zugeordnet wird, die am häufigsten auftreten.
-
Nach
der JPEG-Norm haben die Codeworte eine Länge, die von 1 bis 16 variiert
und ein Repräsentationssymbol
wird jedem Codewort zugeordnet, wobei diese Repräsentationssymbole von 0 bis
255 reichen.
-
Die
Codierung entsprechend der JPEG-Norm ist nicht effizient genug für bestimmte Anwendungen,
was insbesondere ist, wenn es erforderlich ist, eine relativ große Anzahl
adaptiver Huffman-Tabellen für
eine relativ kleine Menge Daten zu übertragen.
-
Deswegen
ist es u. a. eine Aufgabe der vorliegenden Erfindung, ein Signal
und einen Empfänger
zu schaffen, der es ermöglicht,
dass die Daten, die sich auf die Huffman-Tabellenspezifikation beziehen,
effizienter übertragen
werden als mit den Huffman-Codes
möglich
ist, wie diese in der JPEG-Norm definiert sind, und auch mit der
Codierungstechnik, wie diese in US-A-5.488.616 beschrieben worden
ist.
-
Die
vorliegende Erfindung ist insbesondere aber nicht ausschließlich nützlich zum
Schaffen einer effizienten, adaptiven Huffman-Codierung in dem Fall,
dass die adaptive Frequenz der Huffman-Tabellen hoch ist, d. h.
die Tabellen werden je Zeiteinheit eine Vielzahl male angepasst,
und gleichzeitig umfasst die Anzahl Repräsentationssymbole in dem zu übertragenden
Informationssignal alle oder nahezu alle erlaubten Repräsentationssymbole,
wie dies der Fall sein kann in beispielsweise Audio- und Videosignalen.
-
Das
Verfahren nach der vorliegenden Erfindung weist dazu das Kennzeichen
auf, dass ein codierter Informationssignalblock erzeugt wird, der durch
Information über
die Länge
des Codewortes gebildet wird, das mit jedem möglichen Repräsentationssymbol
assoziiert ist, wobei die Information über die Länge jedes der Codeworte eine
Anzahl Bits erhält,
die der Anzahl Bits entspricht, die erforderlich ist zum Codieren
der Länge
des Codewortes mit der maximalen Länge.
-
Die
Anordnung nach der vorliegenden Erfindung ist gekennzeichnet durch
Mittel zum Erzeugen eines codierten Informationsblocks, der Information über die
Länge des
Codewortes enthält,
das mit jeden Repräsentationssymbol
assoziiert ist, wobei die ge nannte Information eine Anzahl Bits
aufweist, die der Anzahl Bits entspricht, die erforderlich ist zum Codieren
der Länge
des Codewortes mit der maximalen Länge.
-
Nach
der vorliegenden Erfindung wird nur die Länge des zugeordneten Huffman-Codes
für jedes mögliche Repräsentationssymbol übertragen.
Die wirklichen Huffman-Codeworte können auf eine unzweideutige
Art und Weise aus dieser Information hergeleitet werden, wie dies
nachstehend noch näher
erläutert
wird. Dies erfordert an erster Stelle, dass in dem Codierer sowie
in dem Decoder eine gleiche Liste von Symbolen verfügbar ist
und die Huffman-Codewortlängen
in der Sequenz dieser Liste übertragen
werden, während
an zweiter Stelle die Huffman-Codeworte, die aus den Codewortlängen hergeleitet
sind, auf eine vordefinierte Weise den Symbolen zugeordnet werden.
Die vorliegende Erfindung basiert nicht auf irgendwelchen Voraussetzungen
in Bezug auf die Auftrittswahrscheinlichkeit von Symbolen in dem
zu übertragenden
Signal.
-
Für eine effiziente Übertragung
kann nur die Anzahl Codeworte jeder Länge des quantisierten Signals übertragen
werden und auf der Empfangsseite kann ein bestimmtes Repräsentationssymbol
n dem kürzesten
Codewort zugeordnet werden und zunehmend längere Codeworte werden aufeinander
folgenden Repräsentationssymbolen
in einem Decoder zugeordnet. Die Repräsentationssymbole für Audio- und
Videosignale werden typischerweise symmetrisch verteilt, beispielsweise
entsprechend einer Gaußschen
Verteilung, und zwar derart, dass wenn vorausgesetzt wird, dass
die Repräsentationssymbole
symmetrisch gegenüber
dem Symbolwert n liegen und im Wesentlichen monoton gegenüber diesem Wert
abnehmen, treten die Repräsentationssymbole, deren
Codeworte die geringste Länge
haben, am häufigsten
auf und diejenigen, deren Codeworte die größte Länge haben, treten am wenigsten
auf. Um Fehler, entstanden durch die Tatsache, dass die wirklichen
Repräsentationssymbole
nicht übertragen werden,
zu vermeiden, ist es notwendig, dass es ein Codewort für jeden
möglichen
Wert des Repräsentationssymbol
gibt. Da Gebrauch gemacht wird von der Tatsache, dass die Verteilung
symmetrisch ist, ist es notwendig, dass im Falle einer alten Anzahl
Repräsentationssymbole
jedem Repräsentationssymbol, das ≠ n ist, ein
Vorzeichenbit zugeordnet wird, um anzugeben, ob ein Repräsentationssymbol
größer oder kleiner
ist als n. Ein Vorzeichenbit wird ebenfalls dem Repräsentationssymbol
n zugeordnet, in dem Fall einer geraden Anzahl Repräsentationssymbole.
-
Nebst
den Codeworten kann Information über
das Codewort mit der größten Länge, das
in dem übertragenen
Signal auftritt, übertragen
werden. Entsprechend der JPEG-Norm wird die Anzahl für alle Codeworte
mit einer Länge
von 1-16 mit Hilfe einer 8-Bit-Zahl spezifiziert, was bedeutet,
dass dies insgesamt eine Tabelle von 16 × 8 = 128 Bits erfordert.
-
Da
die größte Codelänge, die
auftritt, oft viel kleiner sein wird als 16, kann eine effizientere
Codierungstabelle dadurch erhalten werden, dass nur die Zahl übertragen
wird, die auftritt und außerdem
die maximale Codewortlänge
für die
Codewortlängen, die
wirklich auftreten. Wenn beispielsweise die maximale Codewortlänge L =
5 und die maximal erlaubte Länge
16 beträgt,
erfordert dies 4 Bits um die größte Codewortlänge in einem
zusätzlichen
Datenfeld unterzubringen. Da es niemals mehr als 2L Codeworte mit
der Länge
L gibt, sind nur L Bits erforderlich um die Anzahl Codeworte mit
der Länge
L zu definieren. Für
L = 5 besteht nach der vorliegenden Erfindung die Tabelle folglich
aus 4 + 1 + 2 + 3 + 4 + 5 = 19 Bits, was eine wesentliche Verbesserung
gegenüber
den oben genannten 128 Bits ist.
-
Eine
noch effizientere Codierung wird erhalten durch Minimierung der
Summe der Anzahl Bits, die erforderlich sind zum Spezifizieren der
Tabelle und der Anzahl Bits, die erforderlich sind zum Codieren
der wirklichen Daten. Wenn die maximale Codewortlänge, die
zugeordnet ist, abnimmt, sind weniger Bits notwendig zum Spezifizieren
der Tabelle aber es sind mehr Bits notwendig zum Codieren der Daten, weil
die Effizienz des Codes abnimmt, je nachdem die maximal erlaubte
Codewortlänge
reduziert wird. Durch eine schrittweise Reduktion der erlaubten
Codewortlänge
und durch eine gleichzeitige Überwachung
der gesamten Anzahl Bits, die notwendig sind zum Übertragen
der Information, ist es möglich,
die optimale Codewortlänge
zu finden, für
welche die gesamte Anzahl zu übertragender
Bits minimal ist.
-
Es
ist bekannt, dass in dem Fall, dass es wenig verschiedene Repräsentationssymbole
gibt, beispielsweise 7 Repräsentationssymbole,
die Effizienz der Huffman-Codierung
dadurch gesteigert werden kann, dass eine Anzahl derartiger Repräsentationssymbole
zu einem Symbol oder zu einem Vektor größerer Länge gruppiert werden. Die Effizienz
eines Huffman-Codes ist innerhalb 1 Bit/Repräsentationssymbol der Entropie
des Signals mit den Repräsentationssymbolen
gewährleistet,
was bedeutet, dass im Falle einer geringen Anzahl Repräsentationssymbole
der Huffman-Code relativ ineffizient ist. Dies wird durch die genannte
Gruppierung gelöst.
-
Wenn
Gruppen von Repräsentationssymbolen
verwendet werden, kann das oben beschriebene Verfahren, wobei nur
die Anzahl Codeworte jeder Länge
des quantisierten Signals übertragen
wird, nicht angewandt werden, um die Effizienz zu steigern, weil
die Klassifizierung der Gruppen auf Basis deren Wahrscheinlichkeit
des Auftritts abhängig
ist von der Wahrscheinlichkeit der Repräsentationssymbole, aus denen
eine Gruppe besteht.
-
Dies
kann dadurch gelöst
werden, dass die quantisierte Wahrscheinlichkeit der ursprünglichen Repräsentationssymbole übertragen
wird. Die Wahrscheinlichkeit, die dadurch ermittelt werden kann, dass
die Anzahl Male, dass jedes Repräsentationssymbol
auftritt, ermittelt wird und diese Zahl durch die gesamte Anzahl
Repräsentationssymbole
in dem Informationssignal geteilt wird, kann beispielsweise in 32
Pegeln quantisiert werden.
-
Die
Anzahl quantisierter Wahrscheinlichkeiten kann reduziert werden,
wenn, im Falle einer ungeraden Anzahl Repräsentationssymbole die Verteilung
der Repräsentationssymbole
symmetrisch ist, so dass p(n + K) = p(n – K), wobei n = das zentrale Repräsentationssymbol
ist, Gebrauch gemacht wird von der Tatsache, dass die Summe der
Wahrscheinlichkeiten 1 ist. Dann brauchen nur ((N + 1)/2) – 1 Wahrscheinlichkeiten
für N Repräsentationen übertragen
zu werden. Für
eine symmetrische Verteilung, wobei beispielsweise N = 3 ist, brauchen
nur p(n) gegeben zu werden, weil p(n + 1) = p(n – 1) ist und p(n – 1) + p(n)
+ p(n + 1) = 1 ist.
-
Im
Falle einer geraden Anzahl von N Repräsentationssymbole gelten entsprechende
Erwägungen
und nur N/2–1
Wahrscheinlichkeiten sollen übertragen
werden.
-
Entsprechend
dem oben stehenden Prinzip wird die Wahrscheinlichkeit der gruppierten
Abtastwerte auf Basis der übertragenen
Wahrscheinlichkeiten in dem Codierer sowie in dem Decoder berechnet,
und zwar mit Hilfe desselben Algorithmus. Dies wird dadurch effektuiert,
dass die Wahrscheinlichkeiten der einzelnen Abtastwerte miteinander
multipliziert werden. So wird beispielsweise die Wahrscheinlichkeit
der Gruppe (n, n, n + 1) berechnet durch p(n, n, n + 1) = p(n)·p(n)·p(n +
1). Danach wird für
diesen Vektor ein Huffman-Code erzeugt, wobei die Codierung, die
von dem Codierer und dem Decoder angewandt wird, offenbar dieselbe
ist.
-
In
dem Fall, dass die Verteilung der Repräsentationssymbole symmetrisch
ist, wird nur die Hälfte
der Anzahl Repräsentationssymbole
zur Gruppierung verwendet, was die Größe des Codes wesentlich reduziert.
Für jedes
Repräsentationssymbol
in der Gruppe wird dem Huffman-Codewort ein Vorzeichenbit hinzugefügt; in dem
Fall einer ungeraden Anzahl Repräsentationssymbole
braucht dem Repräsentationssymbol
n kein Vorzeichenbit zugeordnet zu werden.
-
Solange
der Codierer und der Decoder dasselbe Verfahren der Erzeugung der
Huffman-Codes anwenden, kann jede Methode, die zu einer Huffman-Codierung
führt,
angewandt werden. Wenn Huffman-Codes von dem JPEG-Typ verwendet
werden, ist es vorteilhaft, dass die größte Codewortlänge, die
auftritt, auf einfache Weise begrenzt werden kann.
-
Wenn
die Wahrscheinlichkeiten des Auftritts jedes Repräsentationssymbols
auf die oben beschriebene Art und Weise übertragen werden, ist es möglich, andere
Codierungstechniken variabler Länge,
wie arithmetische Codierung, anzuwenden, wobei es in diesem Fall
nicht notwendig ist, Gruppen von Repräsentationssymbolen zu bilden.
-
Die
oben beschriebenen Methoden zum Codieren eines Informationssignals
sind insbesondere geeignet zur Anwendung in einem digitalen Audio-Übertragungssystem,
wobei das Signal in Teilbänder
aufgeteilt wird und wobei die Teilbänder oder Kombinationen von
Teilbändern
mit Hilfe der oben beschriebenen Techniken zur Übertragung der Codierungsinformation
codiert werden. Dies bedeutet, dass wenn die Anzahl Repräsentationssymbole
in (einer Kombination von) Teilbändern
gering ist, beispielsweise 3, 5 oder 7, die Wahrscheinlichkeit des Auftritts
jedes der Symbole übertragen
wird, um es zu ermöglichen,
dass dieselbe Codierungstabelle in dem Codierer sowie in dem Decoder
erzeugt wird, wobei Gruppierung von Repräsentationssymbolen möglich ist.
Wenn die Anzahl Repräsentationssymbole
in (einer Kombination von) Teilbändern
größer ist,
beispielsweise größer als
9, wird die exklusive Übertragung
von Information über
die Anzahl Codeworte jeder Länge
benutzt, wobei jedes Codewort mit einem Repräsentationssymbol assoziiert
wird, wenn dies in Kombination mit Information über das längste Codewort, das auftritt,
erforderlich ist.
-
Ausführungsbeispiele
der Erfindung sind in der Zeichnung dargestellt und werden im vorliegenden
Fall näher
beschrieben. Es zeigen:
-
1a-d
ein Beispiel einer Huffman-Codierung nach einem ersten, zweiten
und fünften
Aspekt der vorliegenden Erfindung,
-
2 ein
Blockschaltbild eines Übertragungssystems
für ein
digitales Audiosignal, wobei die Codierung nach der vorliegenden
Erfindung angewandt wird,
-
3a,
b eine Darstellung eines Verfahrens zum Minimieren der Anzahl zu übertragender
Bits, und
-
4 ein
Flussdiagramm eines Verfahrens zum Reduzieren der Anzahl Bits der
Code-Tabelleninformation.
-
Das
nachfolgende Beispiel basiert auf einem abgetasteten, quantisierten
Signal, dargestellt durch 7 Repräsentationssymbole oder Abtastwerte
0-6. Ein Codierer bestimmt die Wahrscheinlichkeit des Auftritts
jedes dieser 7 Repräsentationssymbole
in dem zu übertragenden
Signalblock, der ein Signalframe oder ein Unterframe sein kann,
und auf Basis davon wird jedem dieser Repräsentationssymbole entsprechend
einem durchaus bekannten Huffman-Codierungsprinzip ein Codewort
variabler Länge
zugeordnet, wie dies u.a. in der oben genannten Norm "JPEG Still Image
Compression Standard" beschrieben
worden ist.
-
1a zeigt
als Beispiel die Reihe Repräsentationssymbole
und die denselben zugeordneten Codeworte. Aus 1a ist
ersichtlich, dass es ein Codewort mit einer Länge 2 gibt, dass es zwei Codeworte
mit einer Länge
3 gibt und dass es vier Codeworte mit einer Länge 4 gibt. Es wird Information über das
Codewort mit der größten Länge, das
auftritt, in dem vorliegenden Fall mit der Länge 4, übertragen. Im Falle einer maximal
erlaubten Länge
16 kann diese Information durch: 0 1 0 0 dargestellt werden. Daraufhin
wird Information über
die Anzahl Codeworte jeder Länge übertragen,
wobei eine Länge
L maximal L Bits erfordert. In dem vorliegenden Beispiel sind die Codes
folglich: 0; 01; 010; 0100. Zum Schluss werden die Codes für die wirklichen
Repräsentationssymbole übertragen.
Wenn die Reihe von Repräsentationssymbolen
1-0-0-2-4-6-0-1 als Beispiel genommen wird, ist die Bitreihe für diese
Symbolreihe nach 1a: 010-00-011-1001-1011-00-010.
Der gesamte übertragene
Bitstrom ist in 1b dargestellt.
-
Auf
Basis dieses empfangenen Bitstroms bestimmt der Decoder zunächst, dass
die maximale Codewortlänge 4 beträgt und welches
Repräsentationssymbol
zu welchen Codewort gehört.
Dies ist möglich,
weil die Huffman-Codierung entsprechend JPEG unzweideutig die Codeworte
definiert: Codeworte einer bestimmten Länge (L) für aufeinander folgende Repräsentationssymbole
werden durch binäre
Zählung
definiert und, bei einer Änderung
zu einem Codewort, dessen Länge
um 1 Bit größer ist
(L + 1), wird das bestehende Codewort der Länge L zunächst binär um Eins erhöht und danach
wird neben dem am wenigsten signifikanten Bit eine 0 eingefügt, wonach binäre Zählung stattfindet
für auf einander
folgende Codeworte gleicher Länge.
Dieses Prinzip ist in der Tabelle nach 1a dargestellt.
-
1c zeigt
schematisch, wie der Decoder bestimmt, welches Codewort zu welchen
Repräsentationssymbol
gehört.
Daraufhin kann der Decoder die ursprüngliche Reihe von Repräsentationssymbolen
auf Basis der empfangenen codierten Repräsentationssymbole herleiten,
wie in 1b dargestellt.
-
1d zeigt,
wie für
das Beispiel nach 1a die Information über die
Huffman-Codeworte nach der vorliegenden Erfindung übertragen
wird. Für
jedes mögliche
Symbol wird nur die Länge
des assoziierten Huffman-Codes übertragen. 1d zeigt
wieder dieselben Repräsentationssymbole
in der linken Spalte, die Huffman-Codeworte des Beispiels nach 1a in
der mittleren Spalte und die übertragene
Information in der rechten Spalte. In dem Fall von n möglichen
Codeworten mit einer maximalen Länge
von L Bits, müssen
L × n
Bits übertragen
werden.
-
Für die herkömmliche Übertragung
nach der JPEG-Norm ist die Anzahl Bits im Falle von beispielsweise
256 Symbolen, gleich der Anzahl Bits, erforderlich für die Information über die
Anzahl Codeworte jeder Länge,
beispielsweise y Bits, plus 256 × 8 Bits zum Spezifizieren
des Symbols, das mit jedem Codewort assoziiert ist. Dies ist insgesamt
(256 × 8)
+ y Bits.
-
Nach
dem Verfahren nach der vorliegenden Erfindung sind im Falle von
Huffman-Codeworten mit einer maximalen Länge von 16 nur 256 × 4 Bits
erforderlich, was durch 4 Bits codiert werden kann (die Länge 0 tritt
nicht auf), d. h. weniger als die halbe Anzahl Bits, die nach der
JPEG-Norm erforderlich sind.
-
Im
Falle des Verfahrens nach der vorliegenden Erfindung berechnet der
Decoder das Histogramm der Codewortlänge als Basis für die Berechnung
des Huffman-Codewortes,
das mit jedem Symbol entsprechend der einzigartigen Beziehung zwischen
den Huffman-Codes und den Codewortlängen derselben assoziiert ist.
Wenn es aber erwünscht
ist, kann dieses Histogramm auf alternative Weise in dem Decoder
berechnet werden und die Histogramminformation kann auf eine effiziente
Weise dem Decoder zugeführt
werden. Dies kann beispielsweise nach dem Standard-JPEG-Verfahren
erfolgen, aber auch das oben beschriebene Verfahren ist möglich.
-
Eine
weitere Steigerung der Effizienz kann dadurch erzielt werden, dass
eine bestimmte Form von Entropie-Codierung angewandt wird zum Spezifizieren
der Codewort längen,
wobei die Information benutzt wird, dass im Allgemeinen lange Codeworte öfter auftreten
als kurze Codeworte. Eine derartige Entropie-Codierung kann fest
oder adaptiv sein.
-
Wenn
alle möglichen
Symbole nicht verwendet werden, ist es ebenfalls möglich, zunächst zu dem
Decoder die Information über
diejenigen Symbole zu übertragen,
die wirklich benutzt werden, und danach auch die Codewortlänge nur
dieser Repräsentationssymbole
zu übertragen.
-
Zum
Schluss ist es nebst der Übertragung der
Codewortlänge
nach der vorliegenden Erfindung auch möglich, die Übertragung von Huffman-Codes zu
benutzen, wobei ein zusätzliches
Bit benutzt wird um dem Decoder mitzuteilen, welche Technik selektiert
worden ist zur Übertragung
der Huffman-Codewortinformation.
-
2 zeigt
schematisch ein Blockschaltbild einer Anordnung zur Übertragung
eines digitalen Audiosignals als Bitstrom, wobei der Bitstrom eine
minimale Anzahl Bits enthält,
die es dennoch ermöglichen,
dass das digitale Audiosignal in einem Empfänger rekonstruiert wird.
-
In 2 empfängt eine
Unterband-Filterbank 1 das abgetastete und quantisierte
digitale Audiosignal und teilt dieses Signal auf bekannte Weise auf,
beispielsweise in 64 Teilbänder.
Jedes der Teilbänder
wird in Unterframes aufgeteilt, die je beispielsweise 24 Symboldarstellungen
aufweisen. Eine Anzahl von beispielsweise 3 Unterframes
bilden ein Frame. In einer Quantisierungseinheit 2 werden
die Unterframes jedes der Teilbänder
in eine bestimmte Anzahl Repräsentationssymbole,
beispielsweise –215 – 215 quantisiert. Diese Quantisierung ist größer als diejenige,
die zum Quantisieren des Signals des der Filterbank 1 zugeführten Signals
benutzt wird.
-
Eine
Variable-Länge-Codierungseinheit 3 kombiniert
alle Unterframes mit einer gleichen Anzahl Repräsentationssymbole. Dies ist
erlaubt, weil vorausgesetzt wird, dass die Wahrscheinlichkeitsdichtenfunktion
für all
diese Teilbänder
die gleiche ist. Für
jede Kombination mit einer gleichen gegebenen Anzahl Repräsentationssymbole
wird die Auftrittswahrscheinlichkeit jedes der Repräsentationssymbole
ermittelt. Dies wird auf einfache Weise effektuiert durch Zählung der
Anzahl jedes der Repräsentationssymbole
und durch Teilung dieser Zahl durch die gesamte Anzahl Repräsentationssymbole.
Da vorausgesetzt worden ist, dass die Verteilung der Wahrscheinlichkeiten
der Repräsentationssymbole
symmetrisch ist, ist p(n + K) = p(n – K), wobei n das zentrale
Repräsentationssymbol
ist.
-
Wenn
die Anzahl Repräsentationssymbole gering
ist, beispielsweise 3, 5 oder 7, werden die Wahrscheinlichkeiten
für jedes
Repräsentationssymbol übertragen
und der Codierer sowie der Decoder definieren eine identische Variable-Länge-Tabelle, beispielsweise
eine Huffman-Codierungstabelle, auf Basis dieser Werte. Wenn eine
Huffman-Codierung angewandt wird, können die Repräsentationssymbole
zunächst
in Gruppen gegliedert werden, beispielsweise in Gruppen von 3 Repräsentationssymbolen, wobei
jeder Gruppe ein einzelner Huffman-Codierer zugeordnet wird, wie
oben beschrieben. Die Codes für
jede Gruppe, im Falle einer Huffman-Codierung, oder für jedes
Repräsentationssymbol
werden nacheinander übertragen
und in einem Empfänger
kann der Decoder die wirklichen Repräsentationssymbole aus diesen
Codes herleiten.
-
Die
gesamte Anzahl Bits, erforderlich zur Übertragung der (Gruppen von)
Repräsentationssymbole(n)
und der Information über
die Wahrscheinlichkeiten, wobei diese Information erforderlich ist zum
Erzeugen derselben Codierungs-/Decodierungstabelle in dem Codierer
bzw. Decoder, wird ständig überprüft und mit
der Anzahl Bits verglichen, die erforderlich sind, wenn für die Repräsentationssymbole Codeworte
einer fester Länge
selektiert werden. Wenn eine Feste-Länge-Codierung eine geringere Anzahl
Bits erfordert als die Variable-Länge-Codierung, wird die erst
genannte Codierung angewandt. Eine derartige Situation kann auftreten,
wenn es nur wenige Abtastwerte für
eine bestimmte Anzahl Repräsentationssymbole
gibt und die Tabellenspezifikation folglich eine relativ große Anzahl
zusätzlicher Bits
erfordert.
-
Wenn
die Anzahl Repräsentationssymbole größer ist,
beispielsweise 9 oder mehr, benutzt die Variable-Länge-Codierungseinheit 4 eine
Huffman-Codierung, wobei entweder nur die Anzahl Codeworte jeder
Länge übertragen
wird und/oder die Codeworte der größten Codewortlänge. Diese
Technik kann mit Reduktion der größten Codewortlänge und
mit dem Testen kombiniert werden, ob dies zu einer Reduktion der
gesamten Anzahl Bits führt,
die erforderlich sind zum Übertragen
der Codetabelleninformation und der wirklichen Codes, welche die
Repräsentationssymbole
darstellen.
-
3a,
b ist ein Flussdiagramm, das die Schritte zeigt, die durchgeführt werden
sollen um dies zu verwirklichen.
-
Eingangsvariablen
für diesen
Prozess sind: BITS = die gesamte Anzahl erforderlicher Bits; N DATA
= dies gesamte Anzahl Codeworte; und MAX-CUR-LEN = die aktuelle
maximale Länge
eines Codewortes.
-
In
einem Block 11 wird die gesamte Anzahl Bits gezählt und
die Ziel-Codewortlänge (TARGET-LEN)
wird zu MAX-CUR-LEN-1 ausgeglichen. In einem Entscheidungsblock 12 wird
ermittelt, ob 2TARGET-LEN > N DATA ist. Sollte
dies nicht der Fall sein, ist eine weitere Reduktion der Codewortlänge nicht möglich und
der Prozess wird in einem Block 13 beendet. Sollte diese
Anforderung erfüllt
werden, so wird die Länge
der Codeworte mit der größten Anzahl Bits
in einem Block 14 mit Hilfe eines Unterprozess-Einstell-BITS, dargestellt
in 3b um Eins verringert.
-
Der
Einstell-BITS-Prozess ist eine Abwandlung des Prozesses, der in
der JPEG-Norm durchgeführt
wird, damit gewährleistet
wird, dass es keinen Code gibt mit einer Länge größer als eine vorbestimmte Länge. Dieser
Prozess ist in dem Anhang A von ISO-DIS 10918-1 beschrieben worden.
-
In
einem Block 21 wird die MAX-CUR-LEN auf I gesetzt. In einem
Entscheidungsblock 22 wird ermittelt, ob es I-Bit Codeworte
gibt; sollte dies nicht der Fall sein, so wird I = I – 1 in dem
Block 22 und es wird entschieden, ob I = TARGET-LEN in
einem Block 23, wenn ja, so wird der Einstell-BITS-Prozess in
dem Block 23 beendet und, wenn nicht, so kehrt das Programm
zu dem Block 22 zurück.
-
Wenn
es Codeworte von I Bits gibt, ergibt dies J = I – 1 in einem Block 25 und
J = J – 1
in einem Block 26. In einem Entscheidungsblock 27 wird
ermittelt, ob es J-Bit Codeworte gibt. Sollte es nicht solche Codeworte
geben, so kehrt das Programm zu dem Block 26 zurück, und
sollte es solche Codeworte geben, so werden die in einem Block 28 angegebenen Änderungen
durchgeführt.
Dadurch werden die Codeworte der größten Länge (I), die immer paarweise auftreten,
paarweise entfernt und durch zwei kürzere Codeworte ersetzt. Nachdem
dies vervollständigt worden
ist, wird die Schleife wieder durchlaufen, bis I = TARGET-LEN ist
-
Weiterhin
wird in dem Block 14 die GAIN ermittelt, d. h. die Anzahl
Bits vor der Codewortreduktion wird auf die Anzahl Bits nach der
Reduktion reduziert, d. h. TOT-BITS – CUR-BITS. Sollte es sich
in einem Block 15 herausstellen, dass GAIN < 0 ist, so wird
der Prozess in den Blöcken 16, 17 beendet
und sollte dies nicht der Fall sein, so wird die Schleife wieder über einen
Block 18 durchlaufen.
-
Auch
in diesem Fall wird, ungeachtet der Techniken, die zum Übertragen
der Codierungsinformation angewandt werden, ermittelt, ob es vielleicht effizienter
ist, eine Codierung mit Feste-Länge-Codeworten
anzuwenden und sollte dies der Fall sein, so wird keine Huffman-Codierung
angewandt.
-
Wenn
eine Huffman-Codierung selektiert wird, kann dies ebenfalls angewandt
werden zum Reduzieren der gesamten Anzahl Bits, erforderlich für die Codetabelleinformation
dadurch, dass Huffman-Codes für
verschiedene Anzahlen Repräsentationssymbole
kombiniert werden. Es ist beispielsweise möglich, 3 Repräsentationssymbole
mit einer Tabelle für
5 Repräsentationssymbole
zu codieren, was weniger effizient sein kann, aber was es ermöglicht, dass
nur eine einzige statt zweier Codierungsinformationstabellen übertragen
werden sollen.
-
4 ist
ein Flussdiagramm für
einen Prozess OPTIMIZE-N, der für
diesen Zweck geeignet ist.
-
Eingangsvariablen
für diesen
Prozess sind das Pegelhistogramm für jeden Huffman-Code; N = die
gesamte Anzahl Huffman-Codes und MAX-N = die vorbestimmte maximal
erlaubte Anzahl Codes.
-
In
einem Block 31 wird MG zu GET-MAX-GAIN ausgeglichen. In
der GET-MAX-GAIN-Subroutine wird die Verstärkung ermittelt, die durch
die Kombination von Huffman-Codes für eine Anzahl Pegel und des
nächst
höheren Pegels
erhalten wird, wobei die Kombination die höchste Verstärkung in selektierten Bits
ergibt. In einem Entscheidungsblock 32 wird ermittelt,
ob MG > 0 ist oder
ob N > MAX-N ist.
Sollte eine der beiden Bedingungen nicht erfüllt werden, so wird der Prozess
in einem Block 33 beendet. Der Vergleich N > MAX-N? wird effektuiert,
weil solange N > MAX-N
ist, der Prozess auch fortschreiten darf, wenn MG < 0 ist. Wenn MG > 0 oder N > MAX-N ist, wird die
Kombination von Histogrammen, selektiert in einem Block 34, effektuiert
und N = N – 1.
Wenn in einem Block 35 gefunden wird, dass N < 1 ist, so wird
der Prozess in dem Block 33 beendet, während wenn N > 1 ist, wird die Schleife
wieder durchlaufen.
-
Die
vorliegende Erfindung eignet sich insbesondere für Frame-basierte Codierung
von Repräsentationssymbolquellen,
wie diese in Audio- und Videocodierungssystemen, beispielsweise
Symbolquellen, ohne Speicher und mit ähnlichen Wahrscheinlichkeitsdichtenfunktionen
auftreten.
-
Text der Zeichnung
-
1a
-
- Repräsentationssymbol
Codewert
-
1b
-
- Maximale Länge
Anzahl jeder Länge
Daten
-
1d
-
- Repräsentationssymbol
Codewort Übertagungsinformation
-
3a
-
-
3b
-
-
4
-