DE69431981T2

DE69431981T2 - Fehlerkorrektursysteme mit veränderter Viterbidekodierung

Info

Publication number: DE69431981T2
Application number: DE69431981T
Authority: DE
Inventors: Richard V. Cox; Reed Thorkildsen; Yong Zhou
Original assignee: AT&T Corp
Current assignee: AT&T Corp
Priority date: 1993-12-22
Filing date: 1994-12-09
Publication date: 2003-11-13
Anticipated expiration: 2014-12-10
Also published as: JPH07221655A; EP0660534B1; US5539757A; EP0660534A2; JP3280183B2; DE69431981D1; EP0660534A3

Description

Technisches Gebiet

Die vorliegende Erfindung betrifft Systeme, die digitale Informationen zur Übertragung über einen Kommunikationskanal codieren und decodieren, und Verfahren und Mittel für eine solche Codierung und Decodierung unter Verwendung von Faltungscodes.

Allgemeiner Stand der Technik

Die Kanalcodierung führt effizient Redundanz in eine Sequenz von Datensymbolen ein, um die Übertragungszuverlässigkeit zu verbessern. Zwei wesentliche verwendete Techniken sind Block- und Faltungscodierung. Siehe zum Beispiel Error Control Coding-Fundamentals and Applications by S. Lin und D. J. Costello, Prentice- Hall, 1983.
Die Faltungscodierung mit Viterbi-Decodierung wird häufig als eine Vorwärtsfehlerkorrekturtechnik verwendet. Sowohl aufgrund der Einfachheit ihrer Implementierung als auch der relativ hohen Codierungsgewinne, die sie erzielen kann. Solche Codierungsgewinne ergeben sich im wesentlichen aus der Leichtigkeit, mit der diese Technik Demodulator-Soft- Entscheidungen verwenden und dadurch ungefähr 2 dB mehr Gewinn als der entsprechende Hart- Entscheidungsdecodierer bereitstellen kann.
Bei einem Verfahren zur Erzeugung von Faltungscodes werden Informationssequenzen durch Schieberegister geleitet und die Registerstufen mit linear-algebraischen Funktionsgeneratoren verbunden. Ein selektives Verknüpfen der Ausgangssignale der Funktionsgeneratoren erzeugt die codierte Ausgangssequenz. Ein Faltungscode mit Räte R = b/n erzeugt für alle b Eingangsbit mit K b-Tuple-Stufen in dem Codierungsschieberegister n Ausgangsbit. Die Erzeugung von Faltungscodes kann auch eine Auswahl von Codes aus einer Nachschlagetabelle umfassen.
Faltungscodes sind eine Art von Baumcode. Ein Baumcode ohne Rückkopplung wird als Trellis-Code bezeichnet. Ein linearer Trellis-Code ist ein Faltungscode.
A. J. Viterbi führte die Viterbi-Decodierung von Faltungscodes in "Error Bounds for convolutional Codes and an Asymptotically Optimum Decoding Algorithm", IEEE Trans. on Info. Theory, Band IT-13, S. 260-269, 1967, ein. Die Viterbi-Decodierung erscheint außerdem in G. D. Forney, Jr., The Viterbi Algorithm" Proceedings of the IEEE, Band 16, S. 268-278, 1973.
Außerdem zeigte Forney in "Maximum Likelihood Sequence Estimation of Digital Sequences in the Presence of Intersymbol Interference", IEEE Trans. on Info. Theory, Band IT-18, S. 363-378, 1972, daß bei der Viterbi- Decodierung für Trellis-Codes eine Maximum-Likelihood- Decodierung erfolgt und verwendete diese zur Entzerrung von Kanälen mit Zwischensymbolstörungen. Die Viterbi- Decodierung wurde auch zur Demodulation einer Trelliscodierten Modulation verwendet. Siehe G. Ungerbock, "Channel Coding With Multilevel Phase Signals", IEEE Trans. on Info. Theory, Band IT-28, S. 55-67, Januar 1982.
Somit ist ersichtlich, daß die Viterbi-Decodierung bei der Decodierung von Codes, die im allgemeinen durch eine Trellis-artige, Struktur gekennzeichnet werden können, vorteilhaft arbeitet.
Gute Ergebnisse wurden mit Faltungscodes unter Verwendung von Soft-Demodulationsausgangssignalen und einer Maximum-Likelihood-Decodierung mit Viterbi- Decodierung erhalten (siehe die oben zitierte Literaturstelle von Lin und Costello). Faltungscodes können für die kontinuierliche Datenübertragung oder durch Rahmenbildung von Daten zu Blöcken verwendet werden.
Die Soft-Entscheidungs-Decodierung bezieht sich auf die Zuweisung im Empfänger einer der Menge möglicher Codesequenzen auf der Grundlage mehrschichtig quantisierter Informationen am Ausgang des Kanaldemodulators. Somit wird zum Beispiel das empfangene, durch Rauschen verfälschte Signal aus dem Kanal an eine Menge angepaßter Filter angelegt, die jedem möglichen Codewort entspricht. Die Ausgangssignale der angepaßten Filter werden dann verglichen und das Codewort, das dem größten Ausgangssignal angepaßter Filter entspricht, wird als das empfangene Codewort gewählt. "Größtes" bedeutet in diesem Sinne in der Regel das Größte als Funktion von Abtastwerten entsprechend jedem Bit in dem empfangenen Codewort.
Bei einem Faltungscode mit der Zwangsbedingungslänge K gibt es 2(K-1) = N Zustände und 2K = 2N Zustandsübergangsverzweigungen. Bei der Viterbi-Decodierung muß in jeder Decodierungsstufe (für jedes decodierte Bit) die Metrikerhöhung für jede dieser 2 N Verzweigungen berechnet werden, um Überlebendenwege zu bestimmen und akkumulierte Metriken in den N Zuständen zu aktualisieren. Deshalb wächst die Komplexität des Viterbi-Decodierers exponentiell mit der Zwangsbedingungslänge K. Ein Soft-Entscheidungs-Decodierer mit einer Rate R = 1/n erfordert n2K = 2nN Multiplikationen, 2nN Additionen und N Vergleiche in jeder Decodierungsstufe. Dadurch werden die Bemühungen, den Codierungsgewinn zu erhöhen, durch weitere Vergrößerung der Zwangsbedingungslänge beschränkt.
Eine Aufgabe der Erfindung ist die Verbesserung von Kommunikationssystemen. Eine andere Aufgabe der Erfindung ist eine Vereinfachung der Viterbi- Decodierung. Aus EP-A-0485921 ist ein System gemäß dem Oberbegriff von Anspruch 1 bekannt.

Kurze Darstellung der Erfindung

Ein System und Verfahren gemäß der Erfindung werden in den unabhängigen Ansprüchen definiert, wobei bevorzugte Formen in den abhängigen Ansprüchen definiert werden.

Kurze Beschreibung der Zeichnungen

Fig. 1 ist ein Kommunikationssystem, das Merkmale der Erfindung realisiert.
Fig. 2 ist ein Blockschaltbild eines Faltungscodierers mit R = 1/2 und K = 3.
Fig. 3 ist ein Zustandsdiagramm des Codierers in Fig. 2 mit R = 1/2 und K = 3.
Fig. 4 ist das Trellis-Diagramm des Faltungscodierers von Fig. 2 mit R = 1/2 und K = 3.
Fig. 5 ist ein Beispiel für die Faltungsdecodierung mit einem Trellis-Diagramm.
Fig. 6 ist eine Zustandsübergangstabelle für Faltungscode mit einer Zwangsbedingungslänge K.
Fig. 7 ist ein Trellis-Diagramm eines Faltungscodes der Rate 1/n.
Fig. 8 ist ein Diagramm mit Begleiterzuständen und Verzweigungen bzw. Zweigen eines Faltungscodes.
Fig. 9A ist ein Diagramm der Zustandsübergänge für K = 5 in einem herkömmlichen Viterbi-Decodierer.
Fig. 9B ist ein Diagramm von Begleiterzuständen für K = 5 in einem modifizierten Viterbi-Decodierer, der die Erfindung realisiert.
Fig. 10 ist ein Diagramm der Metrikaktualisierung in Begleiterzuständen.
Fig. 11 ist ein Diagramm von Metrikerhöhungen für Kernzweige.
Fig. 12 bis 14 sind Tabellen von rechnerischen Vergleichen für Faltungscodes der Rate 1/2, 1/3 und 1/4.
Fig. 15 ist ein Diagramm der In-Place- Metrikaktualisierung für die Faltungscodierung.
Fig. 16, 17 und 18 sind Flußdiagramme von Einzelheiten von Schritten in Fig. 1.

Ausführliche Beschreibung bevorzugter Ausführungsformen

Fig. 1 zeigt ein System, das die Erfindung realisiert und die modifizierte Viterbi-Decodierung gemäß einem Aspekt der Erfindung verwendet. Hierbei leitet eine Datenquelle 100 die digitalen Signale zu einem wahlweisen Blockcodierer 102, der geeignete Redundanz, wie zum Beispiel Paritätsprüfbit, zu dem Ausgangssignal der Datenquelle 100 hinzufügt. Das Ausgangssignal des Blockcodierers 102 wird dann zu einem Faltungscodierer 104 geleitet, der eine Faltungscodierung durchführt. Ein Modulator 107 moduliert einen Träger mit den codierten Signalen aus dem Faltungscodierer 104 und leitet sie zu einem Übertragungskanal 110, der Rauschen und andere Verzerrungen, darunter Fading, aufweisen kann. Die Datenquelle 100, der Faltungscodierer 104 und der Modulator 107 sind in der Technik wohlbekannt. Der Kanal 110 ist ebenfalls ein herkömmlicher Kanal.
Ein Demodulator 114 empfängt das Ausgangssignal des Kanals 110 und führt auf zu der Modulation des Modulators 107 komplementäre Weise eine Standarddemodulation durch. Ein Faltungsdecodierer 117 am Ausgang des Demodulators 114 leitet die decodierten Signale dann zu einem wahlweisen Blockdecodierer 120 führt eine zu dem Blockcodierer 102 komplementäre Blockdecodierung durch. Ein Datenempfänger 124 empfängt die decodierten Daten. Der Faltungsdecodierer liegt in Form eines herkömmlichen Viterbi-Decodierers vor, der so modifiziert ist, daß er die Schritte der Erfindung durchführt.
Die Blöcke in dem Faltungsdecodierer 117 stellen die von dem Faltungsdecodierer durchgeführten Schritte dar. Hierbei wird im Schritt 130 wie bei einem Standard- Viterbi-Decodierer der Anfang eines ankommenden Worts in einem Block von Wörtern identifiziert, indem ein Index i (wobei i gleich 0, 1, 2, ... sein kann) auf 0 gesetzt wird. In dem folgenden Schritt 134 werden die Metriken aller N Zustände des Codes initialisiert, wobei die Metrik im 0-Zustand höher als der Rest der N Zustände ist. Dabei wird berücksichtigt, daß der Codierungsvorgang von dem 0-Zustand ausgeht. Der folgende Schritt 137 umfaßt ein Lesen und Umsetzen jeder von m + 1 Komponenten des i-ten ankommenden Eingangskanalworts zu einem gegebenen Bereich. Der nächste Schritt 140 identifiziert einen Startpunkt für einen Zustand durch Setzen eines Zustands j (mit j = 0, 1, 2, ...) auf 0. Die Schritte 134, 137 und 140 sind ebenfalls die eines Standard-Viterbi-Decodierers.
Danach berechnet im Schritt 144 der Decodierer 117 die j-te Metrikerhöhung an einem gewählten Zweig oder Kern, er berechnet die j-te Kernmetrikerhöhung. Dies steht zu der Standard-Viterbi-Decodierung im Kontrast, bei der der Decodierer Metrikerhöhungen an zwei Zweigen, die zu dem Zustand j kommen, berechnet.
Im Schritt 147 vergleicht der Decodierer 117 die akkumulativen Metriken und wählt Überlebenden für zwei neue Zustände. Dies unterscheidet sich von dem Standard-Viterbi-Decodierer, der die beiden akkumulativen Metriken vergleicht und einen Überlebenden wählt.
Im Schritt 150 sichert der Decodierer 117 die Überlebendeninformationen für neue Zustände. Dies steht zu der Standard-Viterbi-Decodierung im Kontrast, die für den neuen Zustand den einzigen Überlebenden sichert.
Im Schritt 154 erhöht der Decodierer 117 j um eins und fragt dann im Schritt 157, ob der Wert j kleiner als N/2 ist, wobei N die Gesamtzahl von Zuständen ist. Wenn ja, kehrt der Decodierer 117 zum Schritt 144 zurück, und wenn nein, schreitet der Decodierer zum Schritt 160 voran. Schritt 157 steht insofern zu einem Standard- Viterbi-Decodierer in Kontrast, als letzterer j nicht wie bei der Erfindung auf N/2, sondern auf N erhöht.
Die übrigen Schritte 160, 164 und 167 sind die eines Standard-Viterbi-Decodierers. Im Schritt 160 wird der Index i des ankommenden Blocks von Wörtern schrittweise um 1 verändert, um das nächste Wort zu identifizieren. Im Schritt 164 fragt der Decodierer 167, ob der Wert von i kleiner als ein Block von L von Wörters (oder Informationsbit) plus K - 1 Nachspannbit ist, um L + K - 1 Codewörter zu erzeugen, wobei K die Speicherzwangsbedingungslänge des Faltungscodes ist. Im Schritt 167 verfolgt der Decodierer 117 vom Zustand 0 aus zurück, um einen Überlebendenweg auszusuchen.
Die Funktionsweise des Decodierers 117 läßt sich am besten durch Betrachtung der folgenden Erläuterung der Faltungscodierung und Viterbi-Decodierung verstehen.

Faltungscodierer

Fig. 2 zeigt Einzelheiten eines Faltungscodierers, der gemäß einer Ausführungsform der Erfindung den herkömmlichen Codierer 104 bildet. Im allgemeinen definieren drei ganze Zahlen n, b und K einen Faltungsdecodierer. Ein Faltungscodierer der Rate R = b/n erzeugt jeweils für b Eingangsbit n Ausgangsbit. Die ganze Zahl K ist ein als die Zwangsbedingungslänge bekannter Parameter, der die Anzahl von b-Tuple-Stufen in einem Codierungsschieberegister darstellt, das einen Teil des Faltungscodierers bildet. Obwohl seine Implementierung für jede Codierungsrate gilt, werden an diesem Punkt der Einfachheit halber nur Codes der Rate 1/n betrachtet.
In Fig. 2 empfängt der Faltungscodierer 204 zum Beispiel eine Sequenz binärer Bit an seinem Eingang IN1 aus dem Blockcodierer 102. Der Faltungscodierer 204 kann in beliebiger Form vorliegen, ist jedoch gemäß einer Ausführungsform als ein Faltungscodierer mit R = 1/2 mit der Zwangsbedingungslänge K = 3 mit Schieberegistern SR1 mit einem b = 1-Eingang IN1 und drei Stufen ST1, ST2 und ST3 gezeigt. Der Faltungscodierer der Zwangsbedingungslänge K verwendet ein K-stufiges Schieberegister SR1 und addiert die Ausgangssignale gewählter Stufen in n Modulo-2- Addierern AD1 und AD2, um die codierten Bit zu bilden. Der Codierungsprozeß beginnt mit allen Registerstufen ST1, ST2 und ST3 im gelöschten Zustand. Informationsbit werden von dem Eingang IN1 aus in das dreistufige Schieberegister geschoben und der Inhalt jeder Stufe ST1, ST2 und ST3 wird in die nächste Stufe auf der rechten Seite geschoben. (Der Inhalt der rechtesten Stufe ST3 fällt weg.) Für jedes Informationsbit geben die zwei Modulo-2-Addierer AD1 und AD2 zwei Bit an den Kanal aus, und zwar jeweils eins aus jedem. Ein Schalter SW1 dient als Multiplexer für die Ausgangssignale der Addierer AD1 und AD2.
Die Verbindungen zwischen den Schieberegisterstufen ST1 und ST2 und den Modulo-2-Addierern AD1 und AD2 werden gewöhnlich durch Generatorsequenzen beschrieben. Die Generatorsequenzen g(0) = [111] und g(1) [101] stellen die oberen bzw. unteren Verbindungen dar, wie in Fig. 2 gezeigt, wobei die äußersten linken Komponenten der Sequenzen die Verbindungen der äußersten linken Stufe des Registers SR1 darstellen, die das aktuelle Eingangsbit halten. Am Ende der Codierung werden K - 1 = 2 als Nachspannbit bezeichnete Nullen in die Register SR1 geschoben, um das Register auszuräumen und um sicherzustellen, daß das Nachspannende des Eingangsbitstroms mit der vollen Länge aus dem Register herausgeschoben wird.
Das Eingangsbit und der Inhalt der K - 1 linken Stufen der Register, bevor das Eingangsbit hereingeschoben wurde, bestimmen eindeutig die Ausgangsbit an jeder Codierungsstufe. Diese Inhalte stellen die vergangenen K - 1 Eingangsbit dar, und stellen den "Zustand" des Faltungscodierungssystems dar. Somit weist ein Faltungscode der Zwangsbedingungslänge K 2(K-1) Zustände auf.
Das in Fig. 2 gezeigte Beispiel erzeugt 4 Zustände: 00, 10, 01 und 11, wobei das linke Bit die äußerste linke Stufe darstellt.
Ein Zustandsdiagramm für Fig. 2 erscheint in Fig. 3 und stellt alle möglichen Zustandsübergänge für den Faltungscodierer 204 in Fig. 2 dar. Die Zustände werden in den Knoten NO1, NO2, NO3 und NO4 des Diagramms gekennzeichnet. Von jedem Zustand gehen nur zwei Zustände aus, entsprechend den beiden möglichen Eingangsbit, und nur zwei Übergänge laufen zu jedem Zustand zusammen. Neben jedem Weg PA (oder einem Zweig) zwischen zwei Zuständen befindet sich ein Zweigcodewort von zwei Ausgangsbit, das dem Zustandsübergang zugeordnet ist. Der Einfachheit halber erscheinen Codezweige, die sich aus einem "0"-Eingangsbit ergeben, als durchgezogene (oder gepunktete) Linien, und Codezweige, die aus einem "1"-Eingangsbit hervorgehen, erscheinen gestrichelt.
Eine Umordnung des Zustandsübergangsdiagramms und Wiederholung der Struktur für jedes sukzessive Eingangsbit führt zu einer Trellis-Diagrammdarstellung des Faltungscodierers. Dies erscheint in Fig. 4, wobei sich an der obersten Stelle ein Eingangsstrom IS und an der untersten Stelle ein Ausgangsstrom OS befindet. Die Zustände ST erscheinen links. Da der Codierungsprozeß von dem Zustand 00 ausgeht, und im Zustand 00 endet, indem K - 1 Nachspannbit in das Register hereingeschoben werden, erreicht das Trellis-Diagramm nicht alle möglichen Zustände an beiden Enden. In jedem gegebenen Zustand folgt der Zustandsübergang für ein "0"-Eingangsbit der durchgezogenen Linie und für ein "1"-Eingangsbit der gestrichelten Linie. Das Zweigcodewort, das an dem zugeordneten Übergangszweig erscheint, wird an den Kanal 110 ausgegeben. Bei dem in Fig. 4 gezeigten Beispiel erzeugt ein Eingangsbitstrom 1 1 0 1 1 plus 2 Nachspannbit einen Ausgangsbitstrom 1 1 0 1 0 1 0 0 0 1 0 1 1 1, der dem Codierungsweg A-B-C- D-E-F-G-H entspricht.

Viterbi-Decodierung

Die Viterbi-Decodierung verwendet die Prinzipien eines Maximum-Likelihood-Decodierers, der die Likelihood- Funktionen oder Metriken für jede mögliche übertragene Sequenz berechnet, diese vergleicht und sich zugunsten des Maximums entscheidet. Wenn alle zu codierenden Informationssequenzen gleich wahrscheinlich sind, erzielt der Maximum-Likelihood-Decodierer eine minimale Blockfehlerwahrscheinlichkeit.
Die Viterbi-Decodierung mit Faltungscodierung führt im wesentlichen eine Maximum-Likelihood-Decodierung durch. Sie verringert jedoch die rechnerische Last durch Ausnutzung der speziellen Struktur in dem Trellis- Diagramm des Faltungscodes. Fig. 4 zeigt, daß die möglichen übertragenen Codezweige kontinuierlich wieder zusammenlaufen, und viele Nicht-Maximum-Metrik-Wege in dem Trellis-Diagramm können zu dem Zeitpunkt, an dem sie mit anderen Wegen zusammenlaufen, beseitigt werden. Es muß nur in jedem Knoten der Überlebendenweg behalten werden, der maximale Metrik aufweist. Die akkumulierte Metrik des Überlebendenwegs in jedem Knoten wird zum Vergleich in der nächsten Decodierungsstufe präserviert. Dadurch wird die Komplexität des Faltungsdecodierers stark verringert.
Fig. 5 ist ein Trellis-Diagramm eines Beispiels für die Faltungsdecodierung mit R = 1/2 und K = 3. Die empfangene Sequenz von Bit RS befindet sich an der untersten Stellen und die decodierte Sequenz DS an der obersten. Die Zustände ST befinden sich links. Fig. 5 zeigt die Viterbi-Decodierung der Kanalsequenz, die mit dem in Fig. 4 gezeigten Faltungscodierer erzeugt wurde. Zwei Bit wurden falsch empfangen, wie in Fig. 5 durch ein "X" angegeben ist. In diesem Beispiel ist die Metrik eines Weges gleich der Summe der Zweig-Hamming- Distanzen auf dem Weg. In jeder Stufe berechnet der Decodierer die Hamming-Distanz (die Anzahl unterschiedlicher Bit) zwischen dem empfangenen Kanalwort und jedem Decodierer-Zweigwort. Dann wird in jedem Knoten das akkumulierte Distanzmaß durch Vergleichen zweier in Frage kommender akkumulierter Distanzen, die durch zwei zugeordnete Vorgängerknoten bereitgestellt werden, und Auswählen der mit dem kleineren Distanzmaß aktualisiert. Die Informationen über den überlebenden Vorgängerzustand in jedem Zustand werden zur späteren Rückverfolgungsoperation gesichert. Dieser Prozeß wird fortgesetzt, bis das Ende der Kanalsequenz erreicht wurde.
Nachdem die Überlebendenweginformationen durch das Trellis bestimmt wurden, kann man den Maximum- Likelihood-Weg durch Zurückverfolgen des Trellis- Diagramms vom Nullzustand (00) am Ende des Trellis ableiten. Das decodierte Bit jeder Stufe wird durch den aktuellen Rückverfolgungszustand bestimmt. Zum Beispiel erzeugen die Zustände 00 und 01 ein decodiertes Bit 0, und die Zustände 10 und 11 erzeugen ein decodiertes Bit 1. Mit den Vorgängerzustandsinformationen wird dann der Vorgängerzustand auf dem Maximum-Likelihood-Weg bestimmt. Dieser Prozeß wiederholt sich, bis das gesamte Trellis durchverfolgt wurde (a-b-c-d-e-f-g-h) und die vollständige decodierte Sequenz (11011) erzeugt ist.
Bei großer Codierungslänge kann dies aufgrund der langen Decodierungsverzögerung und der enormen Menge Wegspeichers möglicherweise nicht praktikabel sein. Deshalb können suboptimale Decodierungsalgorithmen verwendet werden, wie zum Beispiel ein Speicherabtrennalgorithmus.

Soft-Entscheidungs-Decodierung

In einem typischen Kommunikationssystem wird die von dem Kanalcodierer ausgegebene Codewortsequenz zu einem Modulator weitergeleitet, in dem die Codewörter zu Signalkurvenformen transformiert werden. Auf der Empfangsseite kann ein Demodulator auf vielfältige Weisen konfiguriert werden. Für das binäre Signal kann er so implementiert werden, daß er hart entscheidet, ob das Demodulatorausgangssignal eine 0 oder eine 1 darstellt. Im Fall der harten Entscheidung wird das Ausgangssignal auf zwei Pegel 0 und 1 quantisiert und in den Decodierer eingespeist. Der Decodierer verarbeitet dann die durch den Demodulator getroffenen harten Entscheidungen und wird deshalb als Hart- Entscheidungs-Decodierer bezeichnet. Man nehme an, daß alle Sequenzen gleich wahrscheinlich sind. Die optimale Prozedur im Hart-Entscheidungs-Fall besteht dann darin, die Codewortsequenz auszusuchen, die sich in der kleinsten Anzahl von Bitpositionen von der empfangenen Sequenz unterscheidet. Das heißt, die Maximum- Likelihood-Entscheidung wird zu der Minimum-Distanz- Entscheidung.
Der Demodulator kann auch so konfiguriert werden, daß er dem Decodierer einen quantisierten Wert zuführt, der größer als zwei Pegel ist, so daß dem Decodierer mehr Informationen zur Verfügung stehen als im Hart- Entscheidungs-Fall bereitgestellt werden. Der Decodierer, der an den durch den Demodulator getroffenen Mehrfachpegelentscheidüngen operiert, wird als der Soft-Entscheidungs-Decodierer bezeichnet. Bei einem Gaußschen Kanal führt eine Quantisierung mit acht Pegeln zu einer Verbesserung der Leistungsfähigkeit des erforderlichen Signal/Rausch-Verhältnisses von ungefähr 2 dB im Vergleich zu der Quantisierung mit zwei Pegeln. Eine wichtige Aufgabe besteht darin, eine geeignete Wahrscheinlichkeitsfunktion für den Decodierer zur Verwendung bei den Soft-Entscheidungen zu definieren. Es kann gezeigt werden, daß bei gleich wahrscheinlichen Sequenzen der Maximum-Likelihood-Decodierer im Soft- Entscheidungs-Fall eine Entscheidung trifft, die die euklidische Distanz zwischen den möglichen Codewortsequenzen und der empfangenen Sequenz minimiert.

Begleitarzustandsstruktur des Trellis-Diagramus

Bei einem Faltungscode mit Zwangsbedingungslänge K gibt es 2(K-1) = N Zustände und 2K = 2N Zustandsübergangszweige. Bei der Viterbi-Decodierung muß die Metrikerhöhung für jeden dieser 2N Zweige in jeder Decodierungsstufe (für jedes decodierte Bit) berechnet werden, um Überlebendenwege zu bestimmen und akkumulierte Metriken in den N Zuständen zu aktualisieren. Deshalb wächst die Komplexität des Viterbi-Decodierers exponentiell mit der Zwangsbedingungslänge K. Ein Soft-Entscheidungs- Decodierer mit Rate 1/n erfordert n2K = 2nN Multiplikationen, 2nN Additionen und N Vergleiche in jeder Decodierungsstufe. Dadurch werden die Bemühungen, den Codierungsgewinn durch weiteres Vergrößern der Zwangsbedingungslänge zu vergrößern, beschränkt.
Bei binären Quellen und Codierungssystemen nimmt jede der n Komponenten eines Zweigworts nur zwei Werte 0 und 1 an. Deshalb weist ein Rate-1/n-Code höchstens 2n verschiedene Zweigcodewörter auf. Bei einem Rate-1/2- Code müssen nur 4 Codewörter betrachtet werden. Für jede Decodierungsstufe wird dieselbe Menge von Zweigcodewörtern dupliziert. Dadurch wird angezeigt, daß der Decodierer das empfangene Zweigwort nur mit höchstens 4 verschiedenen Zweigcodewörtern in jeder Stufe vergleichen und 4 Metrikerhöhungen erzeugen muß, um die Metriken für alle 2K-1 Zustände zu aktualisieren. Tatsächlich zeigt folgendes, daß die Anzahl tatsächlich verschiedener Zweigcodewörter bei einem allgemeinen Rate-1/n-Faltungscode kleiner als 2n sein kann.

Begleiterzustände und Kern-Zweige

Bei einem Rate-1/n-Faltungscodierer mit der Zwangsbedingungslänge K seien die Inhalte der Registerstufen, bevor das i-te Eingangsbit eingeschoben wurde, s&sub0;(i), si(i), ... sK-1(i), wobei s&sub0;(i) der Inhalt der äußersten linken Stufe ist. Man bezeichne die n Generatorsequenzen der Dimension K für den Code als
g(m) = [g&sub0;(m)g&sub1;(m) ... gK-1(m)],
wobei m = 0, 1, ..., n - 1, und gk(m) entweder 0 oder 1 ist, mit der Ausnahme, daß angenommen wird, daß g&sub0;(m) und gK-1(m) gleich 1 sind, Für jedes Eingangsbit x(1) lautet das codierte Zweigwort dann
y(i) = [y&sub0;(i)y&sub1;(i) ... yn(i)
mit
ym(i) = x(i)g&sub0;(m) + s&sub0;(i)g&sub1;(m) + ... + sK-2(i)gK-1(m)
und die Modulo-2-Addition wird durchgeführt. Man definiere eine dem i-ten Eingangsbit zugeordnete Zustandsnummer als
j = s&sub0;(i) + s&sub1;(i)2 + ... + sK-2(i)2K-2
Die Zustandsnummer ist eine bitumgekehrte Darstellung des Zustands:
Zustand Zustandnr.
00...0 0
10...0 1
01...0 2
...
11...0 N-2
11...1 N-1
Ähnlich erhält man unter Verwendung von j' zur Darstellung des Zustands in der Stufe i + 1:
j' = s&sub0;(i-1) + s&sub1;(i+1)2 + ... + sK-2(i+1)2K-2 = s&sub0;(i+1) + s&sub0;(i)2 + ... + sK-3(1)2K-2 = s&sub0;(i+1) + 2jmod(2K-1).
Die Zustandsübergänge für den Rate-1/n-Faltungscode mit der Zwangsbedingungslänge K sind in der Tabelle von Fig. 6 gezeigt, und das entsprechende Trellis-Diagramm in Fig. 7. Die Begriffe Zustand und Zustandsnummer werden hierbei austauschbar verwendet.
Die Zustandsübergangstabelle von Fig. 6 und das Trellis-Diagramm von Fig. 7 zeigen folgendes:
1. Von jedem Zustand gehen 2 Übergangszweige aus.
- Der obere Zweig entspricht einem Eingangssignal 0, und der untere Zweig einem Eingangssignal 1.
- Zwei endende Zustände, aus denen von demselben Vorgängerzustand j übergegangen werden, lauten j'&sub0; = 2j mod N und j'&sub1; = (2J mod N) + 1. Nur die äußerste linke Stufe (das niedrigstwertige Bit oder LSB) dieser beiden neuen Zustände sind verschieden, und die K - 2 Stufen hoher Ordnung sind dieselben. Somit gilt j'&sub1; = j'&sub0; + 1.
- Zweigwörter auf zwei Zweigen, die von demselben Zustand ausgehen, sind einander komplement. Das heißt, wenn eine Komponente eines Zweigworts 0 ist, ist die die gleiche Komponente des anderen Zweigworts 1 und umgekehrt. Der Grund dafür besteht darin, daß diese beiden Ausgangszweigwörter aus demselben Zustand und Komplement-Eingangsbit, 0 und 1, erzeugt werden.
2. Es gibt immer zwei Zweige, die von zwei Vorgängerzuständen zu einem neuen j' zusammenlaufen.
- Beide Zweige entsprechen demselben Eingangsbitwert (entweder 0 oder 1), abhängig von der Parität von j'.
- Bei diesen beiden Vorgängerzuständen ist nur die äußerste rechte Stufe verschieden. Der obere Zweig kommt aus dem oberen Zustand ju = j' div 2, und der untere Zweig aus j&sub1; = j' div 2 + N/2 = ju + N/2, wobei div die ganzzahlige Division ist.
- Zweigwörter auf diesen beiden Zweigen sind einander komplement.
3. Es gibt immer zwei ausgehende Zustände, die nur an zwei andere zusammenlaufende Zustände angeschlossen sind, wie in Fig. 8 gezeigt.
- Vier Zweige, die aus dem Zustand ju und j&sub1; = ju + N/2 ausgehen, laufen immer zu zwei neuen Zuständen j'&sub0; = 2 ju und j'&sub1; j'&sub0; + 1 = 2 ju + 1 zusammen.
- Der zusammenlaufende Zustand j'&sub0; = 2 ju ist dem Eingangssignal 0 und der Zustand j'&sub1; = j'&sub0; + 1 = 2 ju + 1 dem Eingangssignal 1 zugeordnet. Man beachte, daß alle Zustände über ju dargestellt werden können, mit ju = 0, 1, ..., N/2 - 1.
- ju, j&sub1;, j'&sub0; und j'&sub1; bilden einen geschlossenen Flußgraphen, wie ein Schmetterling; keine anderen Zustände sind an diesen Graphen angeschlossen.
- Die Zweigwörter auf dem Zweig, der die Zustände ju und j'&sub0; verbindet, und dem Zweig, der die Zustände j&sub1; und j'&sub1; verbindet, sind dieselben; die Zweigwörter auf dem Zweig, der ju und j'&sub1; verbindet, und dem Zweig, der j&sub1; und j'&sub1; verbindet, sind dieselben. Diese beiden Paare von Zweigwörtern sind einander komplement.
Somit können 2 N Zweige in einer Decodierungsstufe in N/2 sogenannte Begleitergruppen von vier Zweigen aufgeteilt werden. Die 4 Zustände (2 ausgehende Zustände und 2 zusammenlaufende Zustände) und 4 Zweige in jeder Gruppe werden als Begleiterzustände und Begleiterzweige bezeichnet. Da die Zweigwörter in jeder Begleitergruppe entweder dieselben oder einander komplement sind, können sie alle aus einem Zweigwort abgeleitet werden. Dieser Zweig wird als der Kern-Zweig der Begleitergruppe bezeichnet und definiert eindeutig die Codewort- und Metrikerhöhungsstruktur der Gruppe. In aller Allgemeinheit wählt man die Zweige, die die Zustände ju und j'&sub0; = 2 ju, ju = 0, 1, ..., N/2 - 1, verbinden, als die Kern-Zweige, die in Fig. 8 als durchgezogene Linien gezeigt sind, und man verwendet ju als Kern-Zweig-Index, der auch als Kernzustands- (Knoten-)nummer bezeichnet wird und eine der ersten N/2 Zustandsnummern ist. Der Einfachheit halber wird der Zweig mit einem Zweigwort, das mit dem auf dem Kern- Zweig in derselben Begleitergruppe identisch ist, als der Bild-Zweig (als gepunktete Linien gezeigt) bezeichnet, und die Zweige mit Komplement-Zweigwörtern werden als Komplement-Zweige bezeichnet, wie in Fig. 9A und 9B gestrichelt gezeigt ist. Fig. 9A ist ein Diagramm, das Zustandsübergang bei einem herkömmlichen Viterbi-Decodierer zeigt, und Fig. 9B ist ein Diagramm, das Begleiterzustände für K = 5 in einem die Erfindung realisierenden modifizierten Viterbi-Decodierer zeigt. Hierbei gilt R = 1/2, K = 5 und N = 16.
Bei der herkömmlichen Viterbi-Decodierung von Fig. 9A wird in jeder Stufe ein 2-Bit-Kanalwort (ein Codewort möglicherweise mit zusätzlichem Rauschen) empfangen und die Metrikerhöhungen auf allen 2N = 32 Zweigen werden berechnet. Die Metrikerhöhung auf einem Zweig gibt die Wahrscheinlichkeit an, daß das zugeordnete Codewort in der Stufe gesendet wird, wenn das empfangene Kanalwort gegeben ist. Die akkumulativen Metriken für 16 neue Zustände j' werden aus diesen 32 Metrikerhöhungen j bis j' und 16 alter akkumulativer Metrik in altem Zustand erhalten. Da jeder neue Zustand mit zwei alten Zuständen verbunden ist (einer das Trellis-Diagramm herauf und einer das Trellis-Diagramm herab), gibt es nur zwei in Frage kommende akkumulative Metriken für den neuen Zustand, die beide gleich der alten akkumulativen Metrik in dem zugeordneten alten Zustand, plus der Metrikerhöhung auf dem zugeordneten Zweig, sind. Das Minimum von zwei Kandidaten wird als die aktualisierte akkumulative Metrik in dem neuen Zustand ausgewählt. Zum Beispiel ist bei j' = 0 das Minimum die Linie von j = 0 und j = 8, und bei j' = 1 ist das Minimum die Linie von j = 0 und j = 8. Somit müssen bei dem herkömmlichen Viterbi-Decodierungsschema 2N Metrikerhöhungen berechnet werden.
Fig. 9B ist eine Umstruktur des herkömmlichen Trellis auf das Trellis gemäß einer Ausführungsform der Erfindung für eine Stufe. Diese Umstrukturierung ermöglicht eine Vereinfachung der Berechnung der 2 N Metrikerhöhung. Die jedem Zweig zugeordneten Zustandsübergänge und Codewörter sind in Fig. 9A und 9B identisch. Der Unterschied besteht darin, daß die Zeichnung in Fig. 9B N/2 = 8 Gruppen von 4 Zweigen aufweist, die sich nicht überschneiden. Die Symmetrie der vier Codewörter in jeder Gruppe zeigt, daß nur eine Metrikerhöhung, die sogenannte Kernmetrikerhöhung in der Gruppe, berechnet werden muß. Die übrigen Metrikerhöhungen in jeder Gruppe sind entweder dieselbe oder das Negative der Kernmetrikerhöhung. Dadurch kann die Berechnung vereinfacht werden. Jede Gruppe von vier Zweigen wird als eine Begleitergruppe bezeichnet, und der der Kernmetrikerhöhung zugeordnete Zweig wird als der Kern-Zweig in der Gruppe bezeichnet. Der Einfachheit halber wird der die beiden untersten Zustände in jeder Gruppe verbindende Zweig in jeder Gruppe als Kern-Zweige gewählt, wie durch die durchgezogenen Linien in Fig. 9B gezeigt. Die Kern metrikerhöhungen sowie die Kern-Zweige und ihre zugeordneten Begleitergruppen sind folgendermaßen beziffert: 0, 1, ...N/2 - 1.
Aus der Tabelle in Fig. 6 ist ersichtlich, daß für jeden Kern-Zweig sowohl das zugeordnete Eingangsbit als auch das höchstwertige Bit (MSB) der Zustandsnummer 0 sind.
Wie bereits erwähnt, sind diese N/2 Begleitergruppen (oder Schmetterlinge) untereinander elementfremd. Das heißt, kein Zweig verbindet zwei Zustände in verschiedenen Begleitergruppen. Das Trellis-Diagranm wird also auf nicht überschneidende Weise mit einer verschiedenen Anordnung der Zustandsnummern gezeichnet.
Fig. 9B zeigt auf der rechten Seite umgeordnete ausgehende Zustände für einen Faltungscode mit K = 5. Da jede Begleitergruppe eindeutig durch ihren Kern- Zweig bestimmt wird, wird der gesamte Code eindeutig durch die N/2 Kern-Zweige definiert. Diese Begleiterzustands- und Kern-Zweig-Struktur des Faltungscodes führt zu einer Vereinfachung des Codierungs- und Decodierungsprozesses.

Karngeneratormatrix

Die Eigenschaften des Rate-1/N-Faltungscodes werden ersichtlich, indem G als eine n x K-Matrix definiert wird, die aus Komponenten von n Generatorsequenzen g(m), m = 0, 1, ..., n - 1 des Codes zusammengesetzt sind:
Ein Zweigcodewort kann dann folgendermaßen ausgedrückt werden:
y = [xs&sub0;s&sub1; ... sK-2] GT,
wobei T Matrixtransponierung bedeutet. Da das entsprechende Eingangsbit x und das MSB des Zustands sK-2 für Kern-Zweige des Codes beide null sind, kann die erste und die letzte Spalte von G bei der Bestimmung der Kern-Zweigwörter ignoriert werden. Man bezeichne die mittleren K - 2 Spalten von G durch eine n x (K - 2)- Matrix H:
dabei ist
h(k) = [gk(0)gk(1) ... gk(n-1)],
k = 1, 2, ..., K - 2, ein n-dimensionaler Zeilenvektor und enthält die k-te Komponente aller n Generatorsequenzen. Für einen gegebenen Zustand kann das Kern-Zweigwort somit folgendermaßen ausgedrückt werden:
y = [s&sub0;s&sub1; ... sK-3]HT
Die Matrix H wird als die Kern-Matrix des Faltungscodes bezeichnet. Jede Kombination (Modulo 2) der K - 2 Vektoren (h(K)) ist also ein Kern-Zweigwort. Anders ausgedrückt, wird der Kern-Zweigwortraum durch K - 2 Zeilenvektoren h(k), k = 1, 2, ..., K - 2 aufgespannt. Man beachte, daß die Dimension des Zeilenraums von HT (oder des Spaltenraums von H) gleich dem Rang der Matrix H ist, der als v bezeichnet wird. Offensichtlich gilt v = Rang(H) ≤ min(n, K - 2)
Somit enthält die Matrix HT nur v unabhängige Zeilen h(k). Der von diesen v Vektoren aufgespannte Raum, der den binären Körper (Modulo-2-Addition) zugeordnet ist, weist dann also nur 2v verschiedene Vektoren auf. Deshalb werden Faltungscodes mit Rang(H) = v nur 2v verschiedene Kern-Zweigwörter aufweisen.
Zum Beispiel lautet für einen Rate-1/3--Faltungscode mit K = 5 und den Generatorsequenzen
g(0) = [11011]
g(1) = [10101]
g(2) = [11111]
die zugeordnete Kernmatrix
Es ist ersichtlich, daß in diesem Fall v = Rang(H) = 2 gilt. Somit gibt es nur 2² = 4 verschiedene Kern- Zweigwörter:
y(0) = [000]
y(1) = [101
y(2) = [011]
y(3) = [201]
obwohl es in diesem Code 8 Kern-Zweige (insgesamt 32 Zweige) gibt. Es ist interessant, zu sehen, daß v für K - 2 > n nicht weiter K wächst.

Metrikaktualisierung und Berechnung der Zweigmetrikerhöhungen

Um eine geeignete Metrik für eine effiziente Leistung eines Soft-Entscheidungs-Decodierers zu finden, verwendet das System das Skalarprodukt des empfangenen Zweigworts z und des Decodierer-Zweigcodeworts y eines Rate-1/n-Faltungscodes als die Metrikerhöhung auf einem Zweig:
p = ymzm
Der euklidische Abstand zwischen der gesamten empfangenen Sequenz und der Codewortsequenz ist dann gleich der Summe der Skalarprodukte der empfangenen Zweigwörter und der Decodierer-Zweigwörter in den Sequenzen.
Vor der Berechnung der den Decodierer-Zweigwörtern zugeordneten Metrikerhöhungen setzt man die Komponenten des aus dem Soft-Entscheidungs-Demodulator empfangenen Worts in einen Bereich von -V bis V um, wenn sie nicht bereits in diesem Bereich liegen. Der Wert V gibt eine konfidente Entscheidung an, daß das übertragene Bit 1 war, und -V für eine konfidente Entscheidung bezüglich 0. Jeder Zwischenwert gibt einen bestimmten Konfidenzgrad der Entscheidung bezüglich 0 oder 1 an. Ähnlich setzt man die Komponenten der Zweigcodewörter auf dem Decodierungsdiagramm von 0 bis -1 um und läßt 1 unverändert. Das Skalarprodukt der empfangenen Zweigwörter z und des Decodierer-Zweigworts y nach der Umsetzung kann immer noch als Metrikerhöhung für jede Decodierungsstufe verwendet werden, obwohl die Komponenten der beiden Wörter im unterschiedlichen Bereich liegen können. Somit kann die Metrikerhöhung dann folgendermaßen geschrieben werden:
p = ymzm = ± zm
Der maximale Wert von p, nV, gibt eine konfidente Entscheidung an, daß das Codewort gesendet wurde, und der minimale Wert -nV gibt eine konfidente Entscheidung an, daß das Codewort nicht gesendet wurde. Man sieht, daß bei dieser Metrikerhöhungsberechnung keine Multiplikation benötigt wird. Dies ist besonders attraktiv, wenn der Decodierer an durch den Demodulator getroffener Mehrebenenentscheidung operiert.
Nachdem die Metrikerhöhungen für die Kern-Zweige berechnet wurden, können die Metrikerhöhungen auf allen anderen Zweigen abgeleitet werden. Andere Zweigwörter in einer Begleitergruppe sind entweder dasselbe oder das Komplement des Kern-Zweigworts (siehe Fig. 10). Eine Komponente des Komplement-Zweigworts ist -1, wenn die entsprechende Komponente des Kern-Zweigworts 1 ist und umgekehrt. Wenn die Metrikerhöhung auf einem Kern- Zweig also p ist, dann ist die Metrikerhöhung auf zwei Komplement-Zweigen in derselben Begleitergruppe -p. Die Metrikerhöhung auf dem Bild-Zweig ist immer gleich der auf dem Kern-Zweig p. Somit kann die Metrikaktualisierungsoperation für eine Begleitergruppe (siehe Fig. 8) über eine Schmetterling-Operation beschrieben werden:
M(j'&sub0;) = max [M(ju) + p(j), M(j&sub1;) - p(j)]
M(j'&sub1;) = max [M(ju) - p(j), M(j&sub1;) + p(j)].
wobei ju die Kern-Zustandsnummer ist.
Nach der Bestimmung der Metrikerhöhung für einen Kern- Zweig sind 4 Additionen und 2 Vergleiche notwendig, um die Metriken für jeden Schmetterling zu aktualisieren. Da es insgesamt N/2 solche Schmetterlinge der Form von Fig. 10 gibt, sind insgesamt 2 N Additionen und N Vergleiche erforderlich, um die Metrikaktualisierung in jeder Stufe nach der Bestimmung der Metrikerhöhungen abzuschließen. Da nur 2" verschiedene Kern-Zweigwörter vorliegen, gibt es nur 2" verschiedene Kern metrikerhöhungen, die für jede Stufe berechnet werden müssen. Somit erfordert die vollständige Metrikaktualisierung in jeder Stufe keine Multiplikationen, 2v + 2 N Additionen und N Vergleiche. Für K- 2 > n wächst die Anzahl von Metrikberechnungen (Skalarprodukten) nicht mit der Zwangsbedingungslänge K. Die Kern metrikerhöhungen können berechnet werden, bevor die Metrikaktualisierung für jeden beliebigen Zustand beginnt. Für das oben gezeigte Beispiel mit n = 3, K = 5 hat man v = 2; nur 4 Kern metrikerhöhungen müssen berechnet werden, um alle Metriken in allen N = 16 Zuständen zu aktualisieren (siehe Fig. 11). Es kann gezeigt werden, daß die Kern-Zustandsnummern der Begleitergruppen, die sich dieselben Zweigwörter teilen, {0,5}, {1,4}, {2,7} und {3,6} lauten, Im allgemeinen gibt es 2k-2/2v Begleitergruppen, die sich dasselbe Kern-Zweigwort und dieselbe Metrikerhöhung teilen. Die Teilungsstruktur hängt von den Generatorsequenzen eines Faltungscodes ab.
In einem Soft-Entscheidungs-Decodierer für einen Rate- 1/n-Faltungscode mit der Zwangsbedingungslänge K gibt es den folgenden Vergleich bei der Berechnung der Metrikaktualisierung in jeder Decodierungsstufe:
wobei N = 2k-1 die Anzahl von Zuständen, v der Rang der Kern-Generatormatrix H und v ≤ min (n, K-2) ist. Tabellen in Fig. 12 bis 14 zeigen die Anzahl von Multiplikationen und Additionen, die der herkömmliche Decodierer benötigt, und den vorliegenden Vorschlag für eine Menge bester Codes für die Raten R = 1/2, 1/3 und 1/4.
Die Generatorsequenzen werden in Octalform ausgedrückt.

Speicherungsanordnung für Metrik- und Überlebendenweginformationen

Eine weitere signifikante Aufgabe bei der Implementierung der Viterbi-Decodierung ist die Verwaltung der Speicherung für das Aktualisieren von Metriken in N Zuständen in jeder Decodierungsstufe. Aufgrund der unabhängigen Begleitergruppenstruktur des Trellis-Diagramms sieht man, daß, egal wie die Knoten in dem Diagramm umgeordnet werden, es immer dieselbe Schmetterlingberechnung darstellt, solange die Verbindungen in jeder Begleitergruppe aufrechterhalten werden. Man beachte, daß die Metrikaktualisierung nur zur Bestimmung des Überlebendenwegs oder der Vorgängerzustände auf dem Überlebendenweg dient, die später in der Rückverfolgungsoperation verwendet werden, um die decodierten Bit zu bestimmen. Die Knoten-(Zustands-)bezifferung ist also wirklich nicht wichtig, solange in der Rückverfolgungsoperation der Vorgängerzustand korrekt abgeleitet werden kann, um den Maximum-Likelihood-Weg und daher die korrekte decodierte Sequenz zu bestimmen.

Metrikaktualisierung unter Verwendung zweier Metrikpuffer

Bei einem Beispiel der Erfindung werden N Wörter zugeteilt, um die akkumulierten Metriken von Überlebendenwegen in N Zuständen vor und nach der Metrikaktualisierung in jeder Stufe zu halten. Nachdem die neuen Metriken berechnet und gespeichert wurden, wird das Array neuer Metriken in dem Puffer für alte Metriken für die Metrikaktualisierung in der nächsten Metrikstufe dupliziert. Um eine unnötige Datenverschiebung zu vermeiden, werden die Metriken in beiden Puffern unter Beachtung der zugeordneten Zustandsnummer in derselben Reihenfolge gespeichert, so daß nur Zeiger auf diese Puffer ausgetauscht werden müssen. Das Lesen der alten Metriken und die Erzeugung der neuen Metriken erfolgen in verschiedener Reihenfolge (siehe Fig. 11). Gemäß den Ausführungsformen der Erfindung wird eine ordnungsgemäße Indizierung durchgeführt, um sicherzustellen, daß die Metriken für korrekte Zustände aktualisiert und gespeichert werden. Wie aus Fig. 11 hervorgeht, gibt es immer zwei Arten und Weisen, auf die die Speicherung für die Metriken angeordnet werden kann. Eine Möglichkeit ist das Speichern der Metriken für N Zustände in der natürlichen Reihenfolge 0, 1, ..., N-1 in beiden Metrik-Puffern. Es wird ein Zeiger verwaltet, so daß die alten Metriken in der Reihenfolge der Zustandsnummer j = 0, N/2, 1, N/2 + 1, ..., N/2-1, N-1. Die neuen Metriken und die Vorgängerzustandsinformationen werden in der natürlichen Reihenfolge (von oben nach unten) für die neuen Zustände j' = 0, 1, ..., N-1 erzeugt und geschrieben. Diese Ausführungsform ist unkomplizierter, mit der Ausnahme, daß sowohl die Indexerhöhung als auch -erniedrigung verwendet werden muß, um entsprechende alte Metriken zu lesen.
Bei Implementierung auf bestimmten digitalen Signalprozessoren (DSPs) ist eine alternative Ausführungsform schneller. Es ist bekannt, daß, solange die erzeugten Vorgängerzustandsinformationen wahrheitsgetreu die ursprüngliche Decodierungs-Trellis-Struktur wiedergeben, es gleichgültig ist, in welcher Reihenfolge die Metriken tatsächlich gespeichert werden. Das zweite Verfahren ist eine Speicherung der Metriken in der Reihenfolge auf Zustandsnummer 0, N/2, 1, N/2 + 1, ..., N/2-1, N-1 sowohl in dem Alt- als auch dem Neu-Metrik- Puffer. Dann werden die alten Metriken sequentiell in derselben Reihenfolge wie für die Speicherung gelesen und es wird ein Zeiger verwaltet, so daß die resultierenden neuen Metriken für den Zustand j' = 0, 1, N-1 erzeugt und in die entsprechenden Speicherstellen geschrieben werden können. Ihre Positionsindices in dem neuen Metrikpuffer lauten 0, 2, ..., N-2, 1, 3, ..., N-1, was durch jeweiliges Erhöhen um 2 und Verwenden der Modulo-Adressierung am Ende des Puffers erhalten wird. Es wird keine explizite Speicheradressenerniedrigung benötigt.
Da die neuen Metriken immer in beiden Fällen in der natürlichen Reihenfolge erzeugt werden, können die Vorgängerzustandsinformationen ebenfalls leicht erzeugt und in der natürlichen Reihenfolge 0, 1, 2, ..., N-1 gespeichert werden. Dadurch wird die Rückverfolgungsoperation sehr einfach. Im binären Fall gibt es nur zwei Zweige, die zu jedem Zustand zusammenlaufen, und nur ein Bit wird benötigt, um die Vorgängerzustandsinformationen für jeden Zustand darzustellen. Für jede Decodierungsstufe ist zur Speicherung dieser Informationen ein N-Bit-Wort erforderlich. Zum Beispiel wird für jeden Rückverfolgungszustand j' ein Bit 0 an der Bit-j'-Position des Worts gespeichert, wenn der obere alte Zustand ju der Vorgängerzustand ist, und ein Bit 1 für den unteren alten Zustand j&sub1;. Nachdem die Vorgängerzustandsinformationen erzeugt wurden, kann die Rückverfolgungsprozedur folgendermaßen ausgedrückt werden:
(1) Decodiertes Eingangsbit:
w = j' mod 2
(2) Vorgängerzustandsnummer:
j = j' div 2, für q = 0
(j' + N)div 2 für q = 1
wobei q das gesicherte Vorgängerzustandsinformationsbit ist.

In-Place-Metrikaktualisierung

Da in jeder Begleitergruppe zwei Paare von Zuständen einen geschlossenen Flußgraphen bilden (der nicht mit anderen Zuständen in anderen Gruppen verbunden ist), ist die Metrikaktualisierung in jeder Begleitergruppe von anderen Gruppen unabhängig. Anders ausgedrückt, die Metriken werden in zwei alten Zuständen nur zur Berechnung der Metrikaktualisierung in zwei neuen Zuständen in derselben Begleitergruppe verwendet. Dies zeigt an, daß die Speicherstellen für alte Metriken zum Speichern der neuen Metriken verwendet werden können, sobald die Metrikaktualisierung für diese Gruppe abgeschlossen ist. Man nehme an, daß eine Speicherstelle immer zum Speichern der Metrik entweder für den oberen oder den unteren Zustand in derselben Begleitergruppe verwendet wird. Wie in Fig. 10 gezeigt, wird M(j'&sub0;) dann an einer Stelle gespeichert, die für M(j'u) verwendet wird, und M(j'&sub1;) ersetzt M(j'&sub1;). Somit wird nur ein Puffer benötigt. Dies wird als In-Place- Berechnung bezeichnet.
Im allgemeinen wird die jeder Speicherstelle zugeordnete Zustandsnummer nach dem Rückspeichern der neuen Metriken verändert. Also müssen die Zustände bei der Aktualisierung von Metriken in der nächsten Decodierungsstufe wieder umgruppiert werden. Fig. 15 zeigt, wie dieser Prozeß über den gesamten Trellis hinweg für einen Faltungscode mit der Zwangsbedingungslänge K = 4 ausgeführt wird. Es sind nur die zugeordneten Zustandsnummern für 3 Decodierungsstufen gezeigt. Man nehme an, daß die Metriken in N Anfangszuständen in der natürlichen Reihenfolge der Zustandsnummer gespeichert werden, d. h. die Anfangsmetrik M(0)(J) für den Zustand j wird an der Stelle i = j gespeichert. Nach der Metrikaktualisierung in der ersten Stufe (t = 1) wird die Zustandsnummernanordnung zu j(t = 1) 0, 2, ..., N - 2, 1, 3, ..., N - 1, wie in Fig. 15 gezeigt. Es ist interessant, zu bemerken, daß nach K - 1 = 3 Stufen die Zustandsnummernanordnung wieder dieselbe wie die anfängliche Reihenfolge wird. Dieser Prozeß wiederholt sich bis zum Ende der Decodierungssequenz.
Bei der In-Place-Berechnung werden die Metriken auf derselben horizontalen Linie in dem Flußgraphen von Fig. 15 in derselben Speicherstelle gespeichert. Zusätzlich besteht die Berechnung zwischen zwei Arrays von Metriken aus einer Schmetterling-Berechnung, bei der die alten Metrikknoten und die neuen Metrikknoten horizontal benachbart sind. Die In-Place-Berechnung erfordern, daß die Metriken in nichtsequentieller Reihenfolge gespeichert werden und in nichtsequentieller Reihenfolge auf sie zugegriffen wird.
Da die Zustandsbezifferung bei der Analyse der Metrikaktualisierung nicht wichtig ist, wird hier der Positionsindex verwendet, um die Metrikaktualisierungsprozedur mit der In-Place-Berechnung zu besprechen. Man beachte, daß das gesamte Decodierungs-Trellis-Diagraxnm mit der In-Place-Berechnung in identische Segmente von K - 1 = 3 Sub-Stufen unterteilt werden kann (siehe Fig. 15). Die Sub-Stufen werden von links nach rechts folgendermaßen beziffert: t = 1, 2 und 3. Die Sub-Stufen- Nummer wiederholt also dieselbe Sequenz {1,2,3} bis zum Ende des Trellis. Es kann leicht gezeigt werden, daß die Distanz zwischen dem oberen alten Metrikknoten und dem unteren alten Metrikknoten in jeder Begleitergruppe in der Sub-Stufe t Dt = 2K-1-t ist. Sie ist gleich 4 (oder N/2) für t = 1, 2 für t = 2, 1 für t = 3 bei diesem Beispiel. Die In-Place-Metrikaktualisierungsprozedur kann dann folgendermaßen beschrieben werden:
Für jede Sub-Stufe t:
Aktualisieren der Metriken für die Begleitergruppe mit dem Kern-Index
i = [2uDt + v, v = 0, ..., Dt - 1), u = 0, ..., 2t-1 - 1],
wobei sich der innere Schleifenindex u schneller als der äußere Schleifenindex v ändert. Man nehme an, daß die Vorgängerzustandsinformationen in derselben Reihenfolge wie die Metriken in jeder Sub-Stufe gespeichert werden. Die Rückserfolgungsoperation kann folgendermaßen ausgedrückt werden:
Für jede Sub-Stufe t mit dem Rückverfolgungsknotenindex i':
decodiertes Bit:
w = [i'divDt]mod2
Vorgänger
i = i' + Dt(q - w),
wobei q das gesicherte Vorgängerzustandsinformationsbit ist.
Gemäß einer Ausführungsform der Erfindung kann die Metrikaktualisierung auch in anderen Reihenfolgen berechnet werden. Wenn zum Beispiel der Kern-Knoten in der folgenden Reihenfolge gewählt wird:
i = [2uDt + v, u = 0, ..., 2t-1 - 1), v = 0, ..., Dt - 1]
dann ist aus Fig. 15 ersichtlich, daß die zugeordnete Zustandsnummer der neuen Metriken in der natürlichen Reihenfolge 0, 1, ..., N - 1 vorliegen wird. Die Vorgängerzustandsinformationen werden also in der natürlichen Reihenfolge der Zustandsnummern erzeugt und gespeichert. Deshalb wird dasselbe Rückverfolgungsverfahren wie oben beschrieben bezüglich der Metrikaktualisierung unter Verwendung zweier Metrikpuffer verwendet und gibt das ursprüngliche Trellis-Diagramm wieder.
Da die Metrikaktualisierung in jeder Begleitergruppe von denen in anderen Gruppen unabhängig ist, kann man zur Aktualisierung der Metriken für diese Begleitergruppen zur selben Zeit einen parallelen Automaten verwenden. Dadurch wird der Decodierungsalgorithmus für v < K wesentlich beschleunigt.
Fig. 16 ist ein Flußdiagramm von Einzelheiten zum Lesen und Umsetzen des empfangenen Kanalworts, wie im Schritt 137 in Fig. 1 gezeigt. Im Schritt 1604 wird das i-te Kanalwort empfangen, und im Schritt 1607 der Index m (mit m = 0, 1, 2, ... n - 1) auf 0 initialisiert. Im Schritt 1610 liest das System die m-te Komponente 2m des Kanalworts z und setzt im Schritt 1614 2m in den Bereich (-V, V) um. Der Index m wird dann im Schritt 1617 um 1 erhöht. Im Schritt 1620 kehrt das System, wenn m < n (Anzahl von Komponenten in dem Kanalwort) ist, zum Schritt 1610 zurück. Wenn m nicht kleiner als n ist, wird das umgesetzte Kanalwort z im Schritt 1624 gesichert.
Fig. 17 ist ein Flußdiagramm des Blocks 144 in Fig. 1 zur Berechnung der j-ten Kern metrikerhöhung. Beginnend mit dem Index m = 0 im Schritt 1704 und mit sum = 0 im Schritt 1707 wird hier die m-te Komponente zm des Kanalworts im Schritt 1710 gelesen. Im Schritt 1714 wird die m-te Komponente des j-ten Kern-Zweigworts ym gelesen. Im Schritt 1717 wird, wenn ym > 0 ist, die Summe um zm erhöht, wie im Schritt 1720 gezeigt, und andernfalls wird die Summe um zm erhöht, wie im Schritt 1724 gezeigt. Im Schritt 1727 wird m um 1 erniedrigt, und im Schritt 1730 wird bestimmt, ob m < n ist. Wenn ja, kehrt der Prozeß zum Schritt 1710 zurück und geht andernfalls zum Schritt 1734 weiter. Dort wird die j-te Kern metrikerhöhung gleich der Summe gesetzt.
Fig. 18 ist ein Flußdiagramm, das ein Beispiel für die Art und Weise des Vergleichens der akkumulativen Metriken und des Auswählens von Überlebenden für zwei neue Zustände (siehe Schritt 147 in Fig. 1) enthält. Schritt 147 schreitet von Schritt 144 voran, in dem die j-te Kern metrikerhöhung p(j) berechnet wird. Beim Schritt 1800 wird ein neuer Zustand j'0 = 2j ausgewählt. Von dort aus wird beim Schritt 1804 die oberen in Frage kommende Metrik M(j'&sub0;, u) = M(j) + p(j) berechnet. Danach berechnet Schritt 1807 die untere in Frage kommende Metrik M(j'&sub0;, l) = M(j) - p(j).
Im Schritt 1810 fragt das System, ob der Wert M (j'&sub0;, u) größer als M(j'&sub0;, l) ist. Wenn die Antwort ja ist, zeigt Schritt 1814 das Setzen des oberen Zustands auf den Überlebenden für j'&sub0; an. Im Schritt 1817 gilt dann M(j'&sub0;) = M(j'&sub0;, u). Wenn die Antwort im Schritt 1810 nein ist, dann wird im Schritt 1820 festgelegt, daß der untere Zustand der Überlebende für j'&sup0; ist, und im Schritt 1824 gilt M(j'&sub0;) = M(j'&sub0;, l).
Zur selben Zeit, wenn die Schritte 1800 bis 1824 durchgeführt werden, erfolgen die folgenden Schritte. Im Schritt 1830 wählt das System einen neuen Zustand j'&sub1; gleich 2j + 1. Von dort aus wird die obere in Frage kommende Metrik M (j'&sub1;, u) = M (j + N/2) - p(j) berechnet. Im Schritt 1837 wird die untere in Frage kommende Metrik berechnet, so daß M(j'&sub0;, l) = M(j + N/2) + p(j) gilt. Im Schritt 1840 wird bestimmt, ob M(j'&sub1;, u) größer als M(j&sub1;, l) ist. Wenn die Antwort ja ist, wird festgelegt, daß der obere Zustand der Überlebende für j'&sub1; ist (Schritt 1844). Im Schritt 1847 gilt daher M(j'&sub1;) = M(j'&sub1;, u). Wenn die Antwort nein ist, wird im Schritt 1850 festgelegt, daß der untere Zustand der Überlebende für j'&sub1; ist. Daher gilt im Schritt 1854 M(j'&sub1;) = M(j'&sub1;, l).
Abhängig davon, ob die Antworten im Schritt 1810 und im Schritt 1840 ja oder nein sind, werden also zwei der Ergebnisse in den Schritten 1817, 1824, 1847 und 1854 im Schritt 150 als die Überlebendeninformationen gesichert.
Obwohl die oben erwähnten Schritte nützliche Methoden zur Implementierung der Schritte 137 bis 150 in Fig. 1 zeigen, sind Fachleuten andere Verfahren zur Realisierung dieser Effekte ohne weiteres verfügbar. Die Erfindung liefert eine Faltungscodierungsstruktur, die zu einer schnellen und wirtschaftlichen Implementierung des Viterbi-Decodierungsalgorithmus führt. Dadurch wird ein Faltungscode mit einer größeren Zwangsbedingungslänge möglich, um den Codierungsgewinn zu vergrößern.

Claims

1. System, umfassend:

einen Demodulator (114);

einen an den Demodulator angekoppelten modifizierten Viterbi-Decodierer (117) zum Decodieren codierter Wörter in einem Code mit einer Zwangsbedingungslänge K und N = 2(K-1) Wörtern;

wobei der Decodierer ein Mittel zum Lesen von N Zuständen sukzessiver Wörter aus dem Demodulator enthält;

wobei der Decodierer folgendes enthält:

ein Berechnungsmittel (144) zum Berechnen von Kernmetrikerhöhungen;

ein Selektormittel (147) zum Vergleichen akkumulativer Metriken für jede Metrikerhöhung und zum Auswählen von Überlebenden für zwei neue Zustände;

ein Sicherungsmittel (150) zum Sichern von Überlebendeninformationen;

ein Verfolgungsmittel (167) in dem Decodierer zum Zurückverfolgen von einem Nullzustand;

ein Mittel zum Bewirken, daß das Berechnungsmittel bis zu N/2 Metriken herauf sukzessive Metriken berechnet;

dadurch gekennzeichnet, daß das Sicherungsmittel (150) so angeordnet ist, daß es die Überlebendeninformationen zu einem Paar von hervortretenden Zuständen, das an ein Paar von Zusammenführungszuständen, die einander komplementär sind, angeschlossen ist, und zwei Paaren von Verzweigungswörtern, die einander komplementär sind, umordnet, um so N/2 Begleitergruppen zu bilden.

2. System nach Anspruch 1, weiterhin umfassend:

einen Kanal (110);

einen Modulator (107) an einem Ende des Kanals und einen Demodulator am anderen Ende des Kanals; und

einen Faltungscodierer (104) mit einer Zwangsbedingungslänge K und N = 2(K-1) Zuständen, der auf eine Datenquelle reagiert und an den Modulator angekoppelt ist.

3. Verfahren zum Verarbeiten von Informationen, mit den folgenden Schritten:

Lesen einer sukzessiven Gesamtzahl von N Zuständen sukzessiver Wörter in codierten Daten (117);

Berechnen (174) von Kernmetrikerhöhungen;

Vergleichen von Metriken und Auswählen von Überlebenden für zwei neue Zustände (150);

Sichern der Überlebendeninformationen (150); und

Zurückverfolgen von einem ersten Zustand (167);

wobei das Berechnen von Kernmetrikerhöhungen bis zu N/2 Metriken fortgesetzt wird;

dadurch gekennzeichnet, daß das Sichern (150) der Überlebendeninformationen ein Umordnen der Überlebendeninformationen zu einem Paar von hervortretenden Zuständen, das an ein Paar von Zusammenführungszuständen, die einander komplementär sind, angeschlossen ist, und zwei Paaren von Verzweigungswörtern, die einander komplementär sind, umfaßt, um so N/2 Vergleichsgruppen zu bilden.

4. Verfahren zum Verarbeiten von Informationen nach Anspruch 3, weiterhin mit den folgenden Schritten:

Codieren von Daten aus einer Datenquelle in einem Faltungsdecodierer (104);

Modulieren der codierten Daten;

Leiten der modulierten und codierten Daten durch einen Datenkanal (110);

Demodulieren (114) der Daten aus dem Kanal;

Decodieren der demodulierten Daten mit einem modifizierten Viterbi-Decodierer (117).