DE60215807T2

DE60215807T2 - Verfahren zur decodierung einer sequenz von codeworten variabler länge

Info

Publication number: DE60215807T2
Application number: DE60215807T
Authority: DE
Inventors: Catherine Lamy; Olivier Pothier
Original assignee: Koninklijke Philips Electronics NV
Current assignee: Koninklijke Philips NV
Priority date: 2001-05-22
Filing date: 2002-05-21
Publication date: 2007-09-13
Anticipated expiration: 2022-05-22
Also published as: US6891484B2; KR20030036624A; WO2002095955A1; JP2004533766A; ATE344551T1; DE60215807D1; EP1397869A1; EP1397869B1; US20040155802A1; CN1463500A

Description

Die vorliegende Erfindung bezieht sich auf ein Verfahren zur Quellendecodierung von Sequenzen von Codeworten variabler Länge, wobei die genannte Quellendecodierung auf einem assoziierten Zustandsdiagramm basiert mit einer Vielzahl von Zuständen und auf einem Code basiert, wobei ein Zustand ein Knoten in der Graphik ist, durch die etwaige decodierte Codewortsequenzen passieren können. Die vorliegende Erfindung bezieht sich auch auf einen Decoder, wobei der genannte Decoder das genannte Verfahren anwendet.
Ein derartiges Verfahren kann in jedem beliebigen System angewandt werden, das Codes mit variabler Länge verwendet, wie beispielsweise ein Video- oder Audiokommunikationssystem.
Ein Videokommunikationssystem umfasst typischerweise ein Quellencodiersystem, einen Kanal und ein Quellendecodiersystem. Das genannte Quellencodiersystem erzeugt eine Codewortsequenz und überträgt diese über den genannten Kanal zu dem genannten Quellendecodiersystem, das sie durch einen gemeinsamen Code decodiert. Dergenannte gemeinsame Code definiert eine Vielzahl von Symbolen. Eine Codewortsequenz umfasst eine Anzahl Symbole. Die Decodierung erfolgt über ein Zustandsdiagramm (bekannt als Bit gerichtete Graphik), wie in 1 dargestellt.
Das Zustandsdiagramm umfasst eine X-Achse, die Bitzeiten darstellt, und eine Y-Achse, die ein Alphabet des gemeinsamen Codes darstellt, der einen Satz mit Werten umfasst. In 1 umfasst das Alphabet drei Werte "1", "01", "00". Eine Box stellt einen Zustand des Zustandsdiagramm dar. Eine Strecke wird durch Übergänge zwischen verschiedenen Zuständen dargestellt und eine decodierte Sequenz wird durch eine Strecke mit einem Anfangszustand (im Allgemeinen den Zustand 0) und einem Endzustand dargestellt.
Da es einige Störungen über den Kanal gibt, enthält die empfangene Codewortsequenz Fehler; folglich gibt es eine Vielzahl möglicher decodierter Codewortsequenzen. Das genannte Zustandsdiagramm gibt die möglichen decodierten Codewortsequenzen, wobei ein Zustand ein Knoten in der Graphik ist, durch den die möglichen decodierten Codewortsequenzen hindurchgehen können. Ein optimales Verfahren ist mit Hilfe des Codes nach dem Ganzen möglicher decodierter Codewortsequenzen zu suchen, unabhängig von der empfangenen Sequenz und die beste decodierte Codewortsequenz am Ende der Zu standsdiagrammkonstruktion zu selektieren. Eine L die beste komplette decodierte Codewortsequenz zu finden ist dann, unter diesen Sequenzen nach derjenigen Sequenz zu suchen, die den kleinsten Abstand (entsprechend einer gewählten Metrik) von der empfangenen Sequenz hat.
Ein großes Problem bei der Lösung ist, dass die Graphik komplexer ist, je nachdem die gesendete Codewortsequenz länger ist, je komplexer die Graphik ist und je mehr die Anzahl decodierter Codewortsequenzen nach Erweiterungen sucht. Deswegen ist, wie beschrieben in: "Joint source-channel decoding for variable length encoded data by exact and approximate map sequence estimation", "Proceedings of the IEEE Conference on acoustics, Speech and Signal Processing referenced ICASSP'99", Seiten 2451-2454, 15. – 19. März 1999, von Park und Miller, eine vorgeschlagene Lösung für dieses komplexe Problem die Anzahl Zustände zu reduzieren durch Selektion zu jeder Bitzeit der decodierten Codewortsequenz, welche die beste Metrik hat, aus einem Satz der Zustände, die denselben Symbolwert innerhalb des Alphabets des gemeinsamen Codes haben. Diese Lösung aber bietet kein befriedigendes Paketfehlerratenleistung.
Auf entsprechende Weise ist es u. a. eine Aufgabe der vorliegenden Erfindung, ein Verfahren und einen Decoder zur Quellendecodierung von Codewortsequenzen mit variabler Länge mit einer Anzahl Symbole zu schaffen, wobei die genannte Quellendecodierung auf einem assoziierten Zustandsdiagramm mit einer Anzahl Zustände basiert und auf einem Code basiert, der durch einen Satz von Symbolwerten definiert ist, wobei ein Zustand ein Knoten ist, durch den mögliche decodierte Codewortsequenzen passieren können und einer Bitzeit sowie einem Symbolwert entspricht, was zu einer effizienten Decodierung mit einer angemessenen Komplexität führt.
Dazu umfasst das Verfahren nach der vorliegenden Erfindung einen Schritt zum Reduzieren der Zustände in dem Zustandsdiagramm, und zwar derart, dass bei einer Bitzeit, assoziiert mit einer Gruppe von Zuständen nur Zustände mit der besten Metrik in der Gruppe von Zuständen gespeichert werden, ungeachtet des Symbolwertes.
Außerdem umfasst der Decoder nach der vorliegenden Erfindung Zustandsreduktionsmittel, vorgesehen um zu einem Bitzeitpunkt, assoziiert mit einer Gruppe von Zuständen, nur Zustände zu speichern, welche die besten Metriken in der Gruppe von Zuständen haben, ungeachtet des Symbolwertes.
Wie nachstehend noch detailliert beschrieben wird, ermöglicht ein derartiges Verfahren einerseits eine Reduktion der Zustände in dem Zustandsdiagramm bei jedem Schritt der Diagrammkonstruktion und andererseits eine bessere Leistung durch das Kriterium, das von der teilweisen Metrikberechnung hergeleitet worden ist.
In einer ersten Ausführungsform weist das Verfahren zur Quellendecodierung das Kennzeichen auf, dass das Kriterium derart ist, dass nur ein einziger Zaustand S aus all den Zuständen einer Gruppe G gespeichert wird, welche dieselbe Anzahl Symbole SY haben, entsprechend einem besten Metriklage.
Wie nachstehend noch näher erläutert wird, wird die Anzahl Zustände N an der Oberseite durch die Bitzeit begrenzt, folglich wird die Komplexität durch eine derartige obere Grenze begrenzt. Deswegen führt ein derartiges Kriterium zu Leistungen, ähnlich dem optimalen bekannten Verfahren mit weniger Komplexität.
Bei einer zweiten Ausführungsform weist das Verfahren zur Quellendecodierung das Kennzeichen auf, dass das Kriterium derart ist, dass die gespeicherten Zustände die besten Metriken in der Gruppe von Zuständen haben.
Wie nachstehend noch erläutert wird, ist die Anzahl Zustände N in diesem Fall eine fest Anzahl. Deswegen führt ein derartiges Kriterium zu einem Zustandsdiagramm, dessen Komplexität stabil ist und nicht mit der Bitzeit zunimmt, dies im Gegensatz zu dem optimalen Fall, und ein derartiges Kriterium führt zu einem Zustandsdiagramm, das nicht länger von der Länge der gesendeten Codewortsequenz abhängig ist. Weiterhin gibt es eine gute Paketfehlerratenleistung, dies im Gegensatz zu dem bekannten Verfahren von Park & Miller.
Ausführungsbeispiele der vorliegenden Erfindung sind in der Zeichnung dargestellt und werden im Folgenden näher beschrieben. Es zeigen:
1 ein Zustandsdiagramm eines Verfahrens zur Quellendecodierung von Codewortsequenzen mit variabler Länge nach dem Stand der Technik,
2 eine schematische Darstellung eines Video-Kommunikationssystemms, wobei das Verfahren zu Quellendecodierung nach der vorliegenden Erfindung angewandt wird,
3 ein erstes Zustandsdiagramm eines Verfahrens zur Quellendecodierung von Codewortsequenzen variabler Länge nach einer ersten Ausführungsform der vorliegenden Erfindung,
4 ein zweites Zustandsdiagramm eines Verfahrens zur Quellendecodierung von Codewortsequenzen variabler Länge nach einer zweiten Ausführungsform der vorliegenden Erfindung,
5 eine erste Graphik mit einer ersten Leistung des Verfahrens nach dervorliegenden Erfindung, dargestellt in 3 und 4,
6 eine zweite Graphik mit einer zweiten Leistung des Verfahrens nach der vorliegenden Erfindung, dargestellt in 3 und 4, und
7 eine dritte Graphik mit Komplexitätsergebnissen des Verfahrens nach der vorliegenden Erfindung, dargestellt in 3 und 4, und
8 ein drittes Zustandsdiagramm mit einer Implementierung des Verfahrens nach der vorliegenden Erfindung, dargestellt in 3 und 4.
In der nachfolgenden Beschreibung werden einem Fachmann durchaus bekannte Funktionen oder Konstruktionen nicht detailliert beschrieben, da dies die vorliegende Erfindung unnötig vernebeln würde.
Die vorliegende Erfindung bezieht sich auf ein Verfahren zur Quellendecodierung von Codewortsequenzen variabler Länge auf Basis eines assoziierten Zustandsdiagramms mit einer Anzahl Zustände. Das genannte Verfahren wird insbesondere in einem VLC Decoder ("Variable-Length-Code") angewandt, wie in 2 dargestellt, und zwar innerhalb einer Video-Kommunikationssystems VS. Außerdem das genannte Video-Kommunikationssystem VS umfasst ein Quellencodierungssystem S-ENC, das einen VLC Codierer VLC-ENC, einen Kanal CH und ein Quellendecodiersystem S-DEC mit dem genannten VLC Decoder umfasst. Das Quellencodiersystem S-ENC codiert eine Codewortsequenz SQ über den VLC Codierer und überträgt diese über den genannten Kanal CH während einer Anzahl Bitzeiten zu dem genannten Quellendecodiersystem S-DEC, das sie über den VLC Decoder VLC-DEC kraft eines gemeinsamen Codes C decodiert. Die Übertragung erfolgt bitweise. Eine Codewortsequenz SQ hat eine variable Länge L_SQ. Dies bedeutet, dass die gesendeten Codewortsequenzen SQs verschiedene Längen haben können, folglich können die empfangenen Codewortsequenzen SQr verschiedene Längen haben. Eine Codewortsequenz SQ umfasst eine Anzahl Symbole SY, die durch den gemeinsamen Code C definiert werden. Es sei bemerkt, dass ein einziges Symbol SY wenigstens ein Bit umfasst.
In einem ersten Beispiel, dargestellt in 3, wird der Code C wie Folgt definiert:

– eine maximale Länge L_MAX, die gleich 2 ist und auch die maximale Länge einen Symbols = 2 darstellt,
– eine Größe K, die gleich 3 ist und auch die Anzahl Symbole darstellt,
– ein Alphabet des Codes C, das einen Satz mit Werten [C₁, C₂, C₃] umfasst, die gleich [0; 10; 11] sind und ebenfalls die Werte darstellen, die die drei Symbole annehmen können. Mit diesen Codewerten sind 3 Erscheinungswahrscheinlichkeiten [Pc₁, Pc₂, Pc₃] assoziiert.

Eine gesendete Codewortsequenz wird wie folgt definiert. Es wird vorausgesetzt, dass SQs' = 0 0 1 1 0 1 0 0 ist. Dann ist nach einem Modulationsschritt in dem Quellencodiersystem S-ENC, beispielsweise einem BPSK Modulationsschritt, was dem Fachmann durchaus bekannt ist, SQs = –1; –1; 1; 1; –1; 1; –1; –1. Dann ist, wegen Störungen des Kanals CH, die Sequenz SQr, die von dem Quellendecodiersystem empfangen worden ist, SQr = –0,8; –0,7; 0,2; 1,2; –0,5; 0,6; –0,3; 0,3.
Von jetzt an muss die empfangene Sequenz SQr decodiert werden um die gesendete Sequenz SQs wieder herzustellen Mit anderen Worten, die Symbole SY, die in der genannten gesendeten Sequenz SQs gesendet worden sind, müssen wiederhergestellt werden. Wegen der Störungen, die zu Fehlern führen, sei bemerkt, dass es dabei viele mögliche decodierte Codewortsequenzen SQd geben kann.
Es wird ein Zustandsdiagramm verwendet um alle möglichen decodierten Codewortsequenzen SQd zu zeigen. 3 zeigt ein derartiges Zustandsdiagramm. Die X-Achse stellt die Bitzeiten dar. Die Y-Achse stellt ein Alphabet des verwendeten Codes C dar, wobei das Alphabet einen Satz mit Werten aufweist, die auch Werte darstellen, die von den Symbolen SY angenommen werden können.
Das Zustandsdiagramm nach 3 umfasst 6 Gruppen von Zuständen G0 bis G5, die je mit einer Bitzeit B0 bis B5 assoziiert sind. Eine Gruppe G entspricht allen berechneten Zuständen zu jeder Bitzeit Bj(j ≥ 0) wenn eine Codewortsequenz SQr empfangen wird, wie das Alphabet des Codes C auch sein mag. Eine Box in dem Zustandsdiagramm stellt einen Zustand S dar. Eine Anzahl T Symbole ist in jeder Zustandsbox angegeben. Sie stellt die Anzahl Symbole SY innerhalb einer teilweise empfangenen Sequenz SQr zu einem bestimmten Bitzeit Bj dar. Sie stellt auch die Anzahl Symbole innerhalb einer entsprechenden möglichen decodierten Codewortsequenz SQd dar.
Während vertikale Linien die Gruppen von Zuständen begrenzen, begrenzen horizontale Linien das Alphabet des Codes c mit drei Werten C₁, C₂, C₃, welche die Symbole annehmen können.
Eine Strecke stellt eine decodierte Codewortsequenz SQd dar. Sie besteht aus einem Endzustand und zwischen liegenden Zuständen. So besteht beispielsweise die Strecke S011-S111-S321-S412-S512 aus dem Endzustand S512 und drei zwischen liegenden Zuständen S111, S321 und S412, mit denen die Symbole "0", "10", "0" bzw. "0" übereinstimmen. Die gesamte Anzahl Symbole ist gleich 4.
Es sei bemerkt, dass wir einen Zustand S mit den Indizes Sklm darstellen, wobei k = Anzahl der Gruppe, l = Anzahl Werte innerhalb des Alphabets des Codes C, und m = Rangordnung des Zustandes in der Gruppe und des Codewertes. So beideutet beispielsweise S211, dass dieser Zustand S zu der Gruppe G2, zu dem Codewert C1 gehört und der erste Zustand in dieser Gruppe G2 für den Codewert C1 ist.
Wie aus dem Zustandsdiagramm ersichtlich, kann ein Zustand der Endzustand oder ein zwischen liegender Zustand verschiedener Strecken sein, deswegen lässt sich sagen, dass ein derartiger Zustand S zu einer Bitzeit Bj einen Knoten in der Graphik darstellt, durch den mögliche decodiere Codewortsequenzen hindurch gehen können, die auch als decodiere Symbolsequenzen bezeichnet werden.
Um die beste decodierte Codewortsequenz SQd zu selektieren, die am besten mit der gesendeten Codewortsequenz SQs übereinstimmt, wird ein erster Schritt 1) zum Reduzieren der Zustände in dem Zustandsdiagramm durchgeführt. Zu einer Bitzeit Bj(j ≥ 0) wird nur eine Anzahl N Zustände in einer Gruppe G mit Zuständen in Bezug auf ein Kriterium auf Basis einer teilweisen Metrikberechnung gespeichert und sonst unabhängig von dem Alphabet des genannten Codes C, wobei eine Gruppe G mit einer Bitzeit Bj assoziiert ist.
Wie nachher noch näher erläutert wird, wird in einer ersten Ausführungsform die Anzahl Zustände N an der Oberseite durch die Bitzeit begrenzt, oder gleich einem bestimmten Wert NBMAX in einer zweiten Ausführungsform.
Auf diese Weise umfasst der Reduktionsschritt zwei Subschritte. In einem ersten Subschritt A) werden Berechnungen teilweiser Metriken an teilweisen Sequenzen durchgeführt. Das Adjektiv teilweise bedeutet, dass eine Berechnung einer Metrik durchgeführt wird, und zwar vor dem Ende des Empfangs der ganzen Sequenz SQr. Die Metrikberechnung erfolgt entsprechend einem MAP-Kriterium ("Maximum A Posteriori"), das, wie dem Fachmann bekannt, der Berechnung eines Euklidischen Abstandes zwischen einer teilweisen empfangenen Sequenz SQr und der teilweisen gesendeten Sequenz SQs nach der Modulation entspricht, wonach eine Gewichtung um einen Faktor folgt, und zwar abhängig von den Erscheinungswahrscheinlichkeiten des Codewortes.
Die Formel für die ganze Metrikberechnung ist: m(i) = Σi(||SQri – Ci||2 + ln(PCi))wobei SQr; ein Teil der gesendeten Sequenz SQr ist entsprechend der Emission des Codes Ci. Eine Teilmetrik kann auf einfache Weise aus dem Obenstehenden hergeleitet werden, als aus nur den ersten Termen der Summe bestehend.
Wie ersichtlich wird die Konstruktion des Zustandsdiagramms als eine Funktion der empfangenen Sequenz SQr effektuiert, dies im Gegensatz zu dem optimalen Verfahren, wie in dem Stand der Technik. Tat sachlich gibt es zu jeder Bitzeit einige Zustände, die auf Basis der Teilmetrikberechnungen entfernt werden, die von teilweise empfangenen Sequenzen abhängig sind, während in dem Stand der Technik keine Zustände entfernt werden und ganze Metrikberechnungen am Ende der Zustandsdiagrammkonstruktion durchgeführt werden, oder die Zustandsentfernungstechniken sind nicht nahe genug bei der optimalen Technik.
In einem zweiten Subschritt B) wird das Reduktionskriterium angewandt.
In einer ersten Ausführungsform, wie in 3 dargestellt, ist das Kriterium derart, dass nur ein einziger Zustand unter allen Zuständen einer Gruppe G gespeichert wird, welche die gleiche Anzahl T Symbole SY haben, dies entsprechend einer besten Metriklage.
Eine Metrik assoziiert mit einem betrachteten Zustand S ist eine der Teilmetriken, berechnet in dem ersten Subschritt A) einer Teilsequenz, die sich bis an den genannten betrachteten Zustand S erstreckt.
Auf diese Weise suchen wir in 3 beispielsweise bei einer Bitzeit = 2 nach dem Zustand S, der die beste Metrik unter alle Zuständen der dritten Gruppe G2 hat, die T = 1 Symbol SY haben. Der zweite Zustand S221 und der dritte Zustand S231 in der dritten Gruppe G2 haben T = 1 Symbol SY. Der zweite Zustand S221 wird gespeichert, weil er eine bessere Metrik hat als der dritte Zustand S231. Für die Anzahl Symbole T = 2 gibt es nur einen Zustand S211, welcher genannte Zustand beibehalten wird. Dasselbe tun wir für die Bitzeit = 3 und die Anzahl Symbole T = 2, usw.
Ein Vorteil dieser ersten Ausführungsform ist, dass die Komplexität des Zustandsdiagramms nun auf einfache Art und Weise begrenzt werden kann: der Bitzeitwert ist im Wesentlichen eine deutliche Vergrößerung der Anzahl N Zustände. Da aber die genannte Anzahl N Zustände nicht fest liegt, ist diese noch immer von der Länge der gesendeten Codewortsequenz SQs abhängig. Deswegen wird die Komplexität mit der Bitzeit zunehmen.
In einer zweiten bevorzugten Ausführungsform, wie in 4 dargestellt, ist das Kriterium derart, dass die gespeicherten Zustände S die beste Metrik haben, ungeachtet des Symbols oder des Bitwertes, oder der Anzahl Symbole oder Bits. Die Anzahl N der gespeicherten Zustände wird definiert als ein gegebener Wert NBMAX und wird als eine Funktion der Leistung genommen, die wir erreichen möchten und der Komplexität, die wir haben möchten. Es werden keine weitere Bedingungen verwendet. Auf diese Weise ist beispielsweise die Anzahl zu speichernder Zustände NBMAX = 2. In 4 zu der Bitzeit = 4, werden der erste und der sechste Zustand S411 und S432 gespeichert, weil sie die besten Metrik haben. Die anderen Zustände werden entfernt. Es sei bemerkt, dass alle Zustände S mit derselben Anzahl Symbole SY, hier mit der Anzahl 3, entfernt werden können.
Die Vorteile der zweiten Ausführungsform im Vergleich zu dem Stand der Technik sind:

– NBMAX kann, falls erwünscht, festgelegt werden,
– da NBMAX invariabel ist, nimmt die Komplexität nicht mit der Bitzeit oder folglich mit der Länge der gesendeten Codewortsequenz SQs zu, dies im Gegensatz zu dem optimalen Verfahren oder Park & Miller Verfahren nach dem Stand der Technik.

Es sei bemerkt, dass dies für die zwei Ausführungsformen, wenn ein Zustand S entfernt wird, bedeutet, dass die Zweige, die davon kommen würden, nicht länger als wahrscheinliche Kandidaten betrachtet werden. Die Reduktion des Zustandsdiagramms ist deutlich bemerkenswert, da die Anzahl überlebender Zustände in dem Zustandsdiagramm zu der Bitzeit Bj (d.h. für eine Teilsequenz von j Bits) höchstens gleich j für die erste Ausführungsform und höchstens gleich NBMAX für die zweite Ausführungsform ist. Weiterhin ist, wie oben erwähnt, deutlich, dass die Komplexität dieses letzteren Diagramms nicht mehr von der Länge der gesendeten Codewortsequenz SQs abhängig ist.
Es sei ebenfalls bemerkt, dass abgesehen von dem Einfluss in der Metrikherleitung der Reduktionsschritt unabhängig von dem Code C Alphabet oder der Erscheinungswahrscheinlichkeit der Elemente durchgeführt wird, dies im Gegensatz zu dem Park & Miller Verfahren.
Am Ende der Diagrammkonstruktion, wenn innerhalb einer Codewortsequenz keine weiteren Bits mehr gesendet werden, eine Endentscheidung, die für die beiden Ausführungsformen die gleiche ist, getroffen wird. Diese besteht aus einem zweiten Schritt 2) der Selektion eines schlussendlichen besten Zustandes Skalierungsfaktoren, aus den gespeicherten Zuständen, als der Zustand mit der besten Metrik, und aus der Bestimmung der besten decodierten Codewortsequenz SQd, welche die gleiche Anzahl Symbole SY hat wie die gesendete Codewortsequenz SQs.
Es sei bemerkt, dass vorgeschlagen worden ist, dass einerseits der VLC Decoder die Anzahl Symbole NB_SY, die von dem VLC Codierer innerhalb einer gesendeten Sequenz SQs gesendet wurden, und, andererseits die Länge L_SQs in Bits der genannten gesendeten Sequenz SQs für das Ende der Diagrammkonstruktion kennt.
Es sei bemerkt, dass, wie in der Literatur gefunden werden kann und dem Fachmann durchaus bekannt ist, unter der besten Metrik verstanden wird, die Sequenz, welche die beste, folglich höchste Wahrscheinlichkeit in dem Sinne des MAP Kriteriums erreicht, was der besten, folglich kleinsten minimalen Abstand in dem Sinne der oben definierten Metrik m(i) entspricht.
Es wird eine Annäherung durchgeführt, weil dieser schlussendliche beste Zustand Skalierungsfaktoren als die beste Metrik innerhalb aller möglichen Zustände aufweisend betrachtet wird, die alle möglichen decodierten Codewortsequenzen bestimmen, obschon sie nur unter den gespeicherten Zuständen durchgeführt wird. Folglich wird das Verfahren nach der vorliegenden Erfindung als ein Annäherungsverfahren bezeichnet.
Zum Schluss wird in einem dritten Schritt 3) die Decodierung dadurch effektuiert, dass von dem selektierten schlussendlichen besten Zustand Skalierungsfaktoren über die Strecke der entsprechenden Sequenz in dem Zustandsdiagramm rückwärts gegangen wird, um die Werte der Symbole SY wiederherzustellen, die durch die gesendete Sequenz SQs gesendet worden sind.
Leistungen der ersten und der zweiten Ausführungsform des Verfahrens nach der vorliegenden Erfindung werden nachstehend dargestellt.
Leistungsvergleich mit anderen Quellendecodierverfahren
5 und 6 zeigen Leistungen des Verfahrens nach der vorliegenden Erfindung im Vergleich zu anderen Verfahren zur Quellendecodierung von Codewortsequenzen variabler Länge. Die nachfolgenden Verfahrensleistungen werden dargestellt:

– harte VLC Decodierung "HARD" (Kreisen),
– optimal weiche VLC Decodierung "OPTIMAL" (Quadrate)
– Park & Mittel VLC Decodierung "P&M" (aufrecht stehende Dreiecke), und
– eine erste Ausführungsform des Verfahrens zum Decodieren nach der vorliegenden Erfindung "AMAP-1" (Kreuze),
– eine zweite Ausführungsform des Verfahrens zum decodieren nach der vorliegenden Er findung "AMA-2" (nach rechts zeigende Dreiecke).

Das harte VLC Verfahren ist ein Verfahren, das meistens auf Codewortsequenzen mit festen Länge angewandt wird.
Das optimale Verfahren, wie in dem Stand der Technik definiert, ist ein verfahren ohne Zustandsreduktion und ohne Annäherung. Die anderen Verfahren sind Annäherungsverfahren.
In diesen zwei Figuren ist insbesondere die Leistung der Ausführungsformen des Verfahrens nach der vorliegenden Erfindung ersichtlich, die eine "vertikale" Situation benutzen (da dies einige Zustände als eine Funktion einer Gruppe beibehalten, die mit einer Bitzeit assoziiert ist), gegenüber der Leistung des P&M Verfahrens, das eine "horizontale" Situation benutzt (da dies einige Zustände als eine Funktion des Wertes eines Symbols SY beibehalten).
Die beiden Graphiken von 5 und 6 zeigen die Leistung in Termen von Paketfehlerrate PER gegenüber Signal-Rauschverhältnis Einbruchnachricht/N0, wobei ein Paket einer Codewortsequenz SQ entspricht. Es sei bemerkt, dass die Berechnung des Signal-Rauschverhältnisses dem Fachmann durchaus bekannt ist. Mit anderen Worten, wir berechnen eine Leistung zu Kosten. Die Leistung zeigt, ob eine Codewortsequenz gut decodiert worden ist, und die Kosten zeigen, wie viel Energie verwendet worden ist um die Bits einer Codewortsequenz SQ zu senden. Danach selektieren wir, abhängig von dem Fehler, den wir akzeptieren und/oder von der Energie, die wir verwenden wollen, die beste Lösung. Diejenigen des optimalen Verfahrens und diejenigen des harten Verfahrens begrenzten alle Leistungen.
Für die zweite Ausführungsform wird die Anzahl NBMAX = 3 Zustände, die beibehalten werden müssen, wird derart gewählt, dass diese der Anzahl entspricht oder kleiner ist als die Anzahl, die für das P&M Verfahren erhalten wurde, damit ein ehrlicher Vergleich in Bezug auf das P&M Verfahren gemacht werden kann. Für das P&M Verfahren gibt es tatsächlich zu jeder Bitzeit K Zustände, d.h. die decodierte Codewortsequenz, welche die beste Metrik für jeden Satz mit Zuständen hat, wobei die Symbole den gleichen Wert [C_l, ...., C_i, .... C_k] haben, der eingehalten wird.
Für die erste Graphik in 5 wird ein Code CA für die vier oben genannten Verfahren betrachtet.

– die betreffende variable Länge Codegröße ist K = 3,
– die maximale Länge L_MAX = 2,
– das Alphabet des Codes umfasst die Werte [C₁; C₂; C₃] = [0; 10; 11],
– die assoziierten Symbolwahrscheinlichkeiten [Pc₁₍₀₎, Pc₂₍₁₀₎, Pc₃₍₁₁₎] sind derart gewählt worden, dass sie gleich [0,5; 0,25; 0,25] sind, und
– die Anzahl gesendeter Symbole NB_SY = 100.

Wie aus der ersten Graphik ersichtlich, zeigt sich, dass die zwei Ausführungsformen des Verfahrens nach der vorliegenden Erfindung besser leisten als das P&M Verfahren. Ihre Leistungen liegen näher bei den Leistungen des optimalen Verfahrens als die des P&M Verfahrens.
Für die zweite Graphik in 6 wird ein Code CB für die vier oben genannten Verfahren betrachtet.

– die betreffende variabler Länge Codegröße ist K = 6,
– die maximale Länge L_MAX = 4,
– das Alphabet des Codes umfasst die Werte [C₁; C₂; C₃; C₄; C₅; C₆] = [0; 100; 101; 110; 1110; 1111],
– die assoziierten Symbolwahrscheinlichkeiten Pc₁₍₀₎, Pc₂₍₁₀₀₎, Pc₃₍₁₀₁₎, Pc₄₍₁₁₀₎, PC_5(1110), PC_6(1111)], und
– die Anzahl gesendeter Symbole = 100.

Wie aus dieser Graphik ersichtlich, zeigt sich auch hier, dass die zwei Ausführungsformen des Verfahrens nach der vorliegenden Erfindung besser leisten als das P&M Verfahren. Die Leistungen liegen näher bei den Leistungen des optimalen Verfahrens als die des P&M Verfahrens. Es zeigt sich, dass die verschiedenen Ausführungsformen des Verfahrens nach der vorliegenden Erfindung auf gleiche Art und Weise leisten.
Um auf entsprechende Weise das beste Verfahren zu selektieren muss die Komplexität des Zustandsdiagramm für jedes dieser Verfahren studiert werden, aber das harte Verfahren ist in 7 für den ersten Code CA gegeben. Eine Anzahl Übergänge NbT zwischen den Zuständen S in dem ganzen Zustandsdiagramm und die Anzahl NbS Zustände symbolisiert eine Komplexität. Pfeile in einem Zustandsdiagramm stellen die Übergänge dar. Auf diese Weise steht die Komplexität im Verhältnis zu NbT·NbS. Wenn die maximale Länge des Codes K ist (wobei K im Falle des Codes CA gleich 3 ist), ist die Anzahl Übergänge je Zustand K für alle Verfahren. Folglich ist in der Praxis ersichtlich, dass die Komplexität im Wesentlichen in einem Verhältnis zu der Anzahl Zustände NbS steht.
In 7 stellt die X-Achse die Anzahl Bitzeiten dar und die Y-Achse stellt die Anzahl Zustände NbS je Bitzeit dar. Dies bildet eine gute Bewertung der gesamten Verfahrenskomplexität, da die Anzahl Übergänge je Zustand für jedes Verfahren dieselbe ist, wie oben bereits erwähnt.
Es zeigt sich, dass, während das optimale Verfahren und das AMP-1 Verfahren eine Komplexität linear zu den Bitzeiten des Zustandsdiagramms zeigen, das P&M Verfahren und das AMAP-2 Verfahren beide unabhängig von den Bitzeitwerten des Zustandsdiagramms sind.
Ähnliche Ergebnisse können erhalten werden, wenn der Fall des zweiten Codes CB betrachtet wird.
Schließlich zeigt sich aus den Ergebnissen dieser Figuren, dass die insgesamt beste Lösung die zweite Ausführungsform der vorliegenden Erfindung ist, das AMAP-2 Verfahren, da dieses Verfahren eine besserte Paketfehlerrate PER mit einer geringeren Komplexität des Zustandsdiagramms im vergleich zu anderen bestehenden Annäherungsverfahren ergibt. Die Anzahl NBMAX Zustände zum Sparen für die zweite Ausführungsform wird vorzugsweise in dem Intervall zwischen 4 und 10 genommen. Für dieses Intervall gibt es ein gutes Gleichgewicht zwischen der Komplexität, die ansteigt, wenn NBMAX ansteigt, und der Leistung, die nach dem Wert NBMAX = 10 nicht weiter verbessert wird.
Implementierung des verfahrens nach der vorliegenden Erfindung
Hier ist ein Beispiel einer weichen Implementierung des Verfahrens nach der vorliegenden Erfindung.
In der Praxis betrifft das Verfahren nach der vorliegenden Erfindung in einem ersten Schritt eine erste Vorwärtsfortpflanzung mit einem metrischen Berechnungsprozess, wobei Zeiger auf vorhergehende Zustände gespart werden, und in einem zweiten Schritt einen Zurückverfolgungsprozess zum Bilden der besten decodierten Codewortsequenz entsprechend einem Zustand, selektiert aus allen gesparten Zuständen.
In der ersten Ausführungsform des Verfahrens nach der vorliegenden Erfindung behält die erste Vorwärtsfortpflanzung zu jeder Bitzeit nur diejenigen Zustände S bei, welche die beste Metrik unter allen Zuständen der Gruppe H haben, welche die gleiche Anzahl Symbole SY haben, wie oben bereits erwähnt.
Das Zustandsdiagramm wird mit Hilfe der nachfolgenden Strukturen beschrieben.
Eine, die als "Zustand" bezeichnet wird, die Folgendes umfasst:

– die Anzahl Symbole bis zu einem betrachteten Zustand (die mit der Anzahl Symbole der gesendeten Sequenz für die Endentscheidung verglichen wird),
– die Anzahl Bist bis zu dem betrachteten Zustand (die mit der Anzahl aus dem Bitzeitschritt übereinstimmt),
– den Wert des Symbols bei dem Übergang, der zu dem betrachteten Zustand führt (gespart für den Rückverfolgungsprozess),
– die kumulative Metrik bis zu dem Übergang, der zu dem betrachteten Zustand führt,
– einen ersten Zeiger PSTATE_PREV zu den vorhergehenden Zustand,
– einen zweiten Zeiger PSTATE_VERT_NEXT zu dem nächsten "vertikalen" Zustand, der untersucht werden muss.

Eine die als "Trellis" bezeichnet wird, die Folgendes umfasst:

– einen Vektor von ganzen Zahlen, wobei die Anzahl Überlebungszustände für jede Bitzeit gespeichert wird, eine Matrix der Diagrammzustände.

Es sei bemerkt, dass die zwei Zeiger in der Zustandsstruktur für das Verfahren nach der vorliegenden Erfindung entscheidend sind. Der erste PSTATE_PREV ist notwendig für den Rückverfolgungsvorgang und der zweite PSTATE_VERT_NEXT ermög licht die Abtastung der "vertikalen" Zustände, d.h. aller Zustände für dieselbe Bitzeit Bj. Ein Beispiel davon ist zur Illustration in 8 gegeben.
Auf diese Art und Weise wird der Vorwärtsprozess für die erste Ausführungsform wie folgt effektuiert. Zu einer Bitzeit Bj von einem Zustand S1j:

– Für jede neue untersuchte SU(j + 1) Zustandsmöglichkeit:
– wenn es in der Graphik bereits einen Zustand SE(j + 1) mit derselben Bitzeit und derselben Anzahl Symbole gibt, DANN:
– Vergleiche die teilweisen kumulativen Metriken zwischen diesem bestehenden Zustand SE(j + 1) und dem untersuchten SI(j + 1). Der Zustand mit der besten Metrik soll dabei behalten werden.
– Sonst soll der Zustand in der Graphik erzeugt werden und der untersuchte Zustand SI(j + 1) soll darin kopiert werden.
– Untersuchung des nächsten "vertikalen" Zustandes S2j (dem fallweisen Zeiger PSTA-TE_VERT_NEXT folgend) oder, wenn es keinen weiteren "vertikalen" Zustand mehr gibt, (der zweite Zeiger PSTATE_VERT_NEXT gleich NULL), soll zu der nächsten Bitzeit weitergefahren werden.

In der zweiten Ausführungsform des Verfahrens nach der vorliegenden Erfindung behält die erste Vorwärtsfortpflanzung zu jeder Bitzeit NBMAX Zustände bei, welche die beste Metrik haben, wie oben bereits erwähnt.
Die verwendeten Strukturen sind die gleichen wie für die erste Ausführungsform.
Auf diese Weise wird der Vorwärtsprozess für die zweite Ausführungsform wie folgt effektuiert.
Zu einer Bitzeit Bj, von einem Zustand S1j:

– Für jede neue untersuchte SI(j + 1) Zustandsmöglichkeit:
– Wenn es in der Graphik bereits einen Zustand SE(j + 1) mit derselben Bitzeit und derselben Anzahl Symbole gibt, DANN
– Vergleiche die teilweisen kumulativen Metriken zwischen diesem bestehenden Zustand SE(j + 1) und dem untersuchten SI(j + 1). Der Zustand mit der besten Metrik soll dabei behalten werden.
– Sonst
– Wenn die Anzahl bestehender Zustände zu der nächsten Bitzeit Bj + 1 kleiner ist als die Anzahl zu sparender Zustände NBMAX, DANN: soll der Zustand in der Graphik erzeugt werden und der untersuchte Zustand SI(j + 1) soll darin kopiert werden.
– Sonst
– Bestimmung des bestehenden Zustandes SE(j + 1) mit der schlechtesten partiellen kumulativen Metrik, und
– Vergleich des untersuchten Zustandes SI(j + 1) mit diesem schlechtesten bestehenden Zustand SE(j + 1). Derjenige mit der besten Metrik soll beibehalten werden.
– Untersuchung des nächsten "vertikalen" Zustandes S2j (dem fallweisen zweiten Zeiger PSTATE_VERT_NEXT folgend oder, wenn es keinen weiteren "vertikalen" Zustand mehr gibt (den zweiten Zeiger PSTATE_VERT_NEXT gleich NULL), soll zu der nächsten Bitzeit Bj + 1 fortgefahren werden.

Der Rückverfolgungsprozess für die beiden Ausführungsformen wird wie folgt effektuiert.
Erforsche den besten Zustand mit L_SQs Bits mit übereinstimmenden NB_SY Symbolen.

– wenn kein Zustand mit der richtigen Anzahl Symbole gefunden wird:
– Keine Übereinstimmung gefunden
– Sonst
– Eine Übereinstimmung gefunden
– Geh zurück und vermerke die Symbole bei den entsprechenden Übergängen.
– Kehre die Rangordnung der Symbole um die decodierte Codewortsequenz zu erhalten.

Es sei bemerkt, dass die vorliegende Erfindung sich nicht auf die oben genannte Videoapplikation beschränkt. Sie kann bei jeder beliebigen Applikation angewandt werden, wobei Codierung mit variabler Länge angewandt wird und sie kann die Kosten der genannten Codierung unterstützen (in Termen der rechnerischen Komplexität und Zeitverzögerung, wobei die genannte Zeitverzögerung, bei dem Verfahren nach der vorliegenden Erfindung von dem Ende des Empfangs einer ganzen Sequenz abhängig ist, und zwar wegen des Nachverfolgungsprozesses). Typischerweise kann die vorliegende Erfindung Basis-Elektrode bei Video-Audio- oder Textkompression angewandt werden.
Es sei bemerkt, dass das Verfahren nach der vorliegenden Erfindung sich nicht auf die oben genannte Implementierung beschränkt.
Es gibt viele Möglichkeiten zum Implementieren von Funktionen des Verfahrens nach der vorliegenden Erfindung, und zwar mit Hilfe von Hardware- oder Software-Items, oder von beiden, vorausgesetzt, dass ein einziges Hardware- oder Software-Item mehrere Funktionen erledigen kann. Dies schließt die Tatsache nicht aus, dass ein Gebilde von Hardware- oder Software-Items oder von beiden eine Funktion durchführen. So kann beispielsweise der Reduktionsschritt mit der Selektion eines schlussendlichen besten Zustandsschrittes kombiniert werden, wodurch auf diese Art und weise eine einzige Funktion gebildet wird ohne dass dadurch das Verfahren zur Quellendecodierung nach der vorliegenden Erfindung modifiziert wird.
Die genannten Hardware- oder Software-Items können verschiedenartig implementiert werden, wie mit Hilfe verdrahteter Schaltungsanordnungen oder mit Hilfe auf geeignete Art und Weise programmierter integrierter Schaltungen. Die integrierte Schaltung kann sich in einem Computer oder in einem Decoder befinden. In dem zweiten Fall umfasst der Decoder Zustandsreduktionsmittel, dazu vorgesehen, zum Durchführen des Reduktionsschrittes 1) entsprechend dem ersten oder dem zweiten Kriterium, und Selektionsmittel, dazu vorgesehen, den Selektionsschritt 2) durchzuführen, wie oben beschrieben, wobei die genannten Mittel Hardware- oder Software-Items sind, wie oben erwähnt.
Die integrierte Schaltung umfasst einen Satz mit Instruktionen. Auf diese Weise kann der genannte Satz mit Instruktionen, der beispielsweise in einem computerprogrammierten Speicher oder in einem Decoderspeicher untergebracht ist, dafür sorgen, dass der Computer oder der Decoder die verschiedenen Schritte des Quellendecodierverfahrens durchführt.
Der Satz mit Instruktionen kann dadurch in den Programmierungsspeicher eingeladen werden, dass der Datenträger, wie beispielsweise eine Disk, ausgelesen wird. Auch kann ein Service-Provider den Satz mit Instruktionen zur Verfügung stellen, und zwar über ein Kommunikationsnetzwerk, wie beispielsweise das Internet.
Bezugszeichen in den nachfolgenden Patentansprüche sollen nicht ans den Anspruch begrenzend betrachtet werden. Es dürfte einleuchten, dass das Verb "umfassen" und die Konjugationen davon das Vorhandensein anderer Schritte oder Elemente anders als die in dem Anspruch definiert, nicht ausschließt. Der Artikel "ein" vor einem Element oder einem Schritt soll das Vorhandensein einer Anzahl derartiger Elemente bzw. Schritte nicht ausschließen.

Claims

Verfahren zur Quellendecodierung von Sequenzen von Codeworten variabler Länge mit einer Vielzahl von Symbolen, wobei das genannte Quellendecodieren auf einem assoziierten Zustandsdiagramm basiert, das eine Vielzahl von Zuständen (S) aufweist und auf einem Code (C) basiert ist, das durch einen Satz von Symbolwerten definiert wird, wobei ein Zustand ein Knoten ist, durch den etwaige decodierte Codewortsequenzen (SQd) hindurchgehen können und einer Bitzeit und einem Symbolwert entspricht, dadurch gekennzeichnet, dass das Verfahren einen Verfahrensschritt zum Reduzieren der Zustände (S) in dem Zustandsdiagramm umfasst, und zwar derart, dass bei einer Bitzeit (Bj) assoziiert mit einer Gruppe von Zuständen nur Zustände mit der besten Metrik in der Gruppe (G) von Zuständen gespeichert werden, ungeachtet des Symbolwertes.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass nur ein einziger Zustand unter allen Zuständen der Gruppe (G) gespeichert wird, welche dieselbe Anzahl Symbole (SY) haben.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass nur eine feste Anzahl Zustände in der Gruppe (G) von Zuständen gespeichert werden.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass es einen anderen Schritt aufweist zum Selektieren eines letztendlich besten Zustandes (Sf) unter den gespeicherten Zuständen, als der Zustand mit der besten Metrik, und zum Ermitteln einer besten decodierten Codewortsequenz (SQd), welche die gleiche Anzahl Symbole (SY) hat, wie eine gesendete Codewortsequenz (SQs).
Computerprogrammprodukt für einen Decoder, mit einem Satz von Instruktionen, die das Verfahren nach Anspruch 1 bis 4 durchführen, wenn sie in den genannten Decoder geladen worden sind.
Computerprogrammprodukt für einen Computer, mit einem Satz von Instruktionen, die das Verfahren nach Anspruch 1 bis 4 durchführen, wenn sie in den genannten Computer geladen worden sind.
Decoder zur Quellendecodierung von Sequenzen von Codeworten variabler Länge mit einer Anzahl Symbole, wobei die genannte Quellendecodierung auf einem assoziierten Zustandsdiagramm basiert mit einer Anzahl Zustände (S) und auf Basis eines Codes (C) der durch einen Satz von Symbolwerten definiert ist, wobei ein Zustand ein Knoten ist, durch den etwaige decodierte Codewortsequenzen (SQd) hindurch gehen können, und einer Bitzeit und einem Symbolwert entspricht, dadurch gekennzeichnet, dass er Zustandsreduktionsmittel aufweist, vorgesehen um zu einem Bitzeitpunkt (Bj), assoziiert mit einer Gruppe von Zuständen, nur Zustände zu speichern, welche die besten Metriken in der Gruppe (G) von Zuständen haben, ungeachtet des Symbolwertes.