PatentDe  


Dokumentenidentifikation DE69834320T2 12.04.2007
EP-Veröffentlichungsnummer 0000975125
Titel Verfahren und Vorrichtung zur Folgeschätzung
Anmelder Mitsubishi Denki K.K., Tokyo, JP
Erfinder Kubo, Hiroshi, Chiyoda-ku, Tokyo 100-8310, JP;
Tanada, Kazuo, Chiyoda-ku, Tokyo 100-8310, JP;
Murakami, Keishi, Chiyoda-ku, Tokyo 100-8310, JP
Vertreter PFENNING MEINIG & PARTNER GbR, 80339 München
DE-Aktenzeichen 69834320
Vertragsstaaten DE, FR, GB
Sprache des Dokument EN
EP-Anmeldetag 27.05.1998
EP-Aktenzeichen 991175449
EP-Offenlegungsdatum 26.01.2000
EP date of grant 26.04.2006
Veröffentlichungstag im Patentblatt 12.04.2007
IPC-Hauptklasse H04L 25/03(2006.01)A, F, I, 20051017, B, H, EP

Beschreibung[de]
HINTERGRUND DER ERFINDUNG Gebiet der Erfindung

Die vorliegende Erfindung bezieht sich auf ein Folgeschätzverfahren und eine Folgeschätzvorrichtung zum Schätzen einer übertragenen Signalfolge auf einer Empfangsseite, und insbesondere auf ein Viterbi-Entzerrungsverfahren oder ein Viterbi-Decodierverfahren, auf der Grundlage eines empfangenen Signals und einer Charakteristik eines Kanals, oder einer Codierregel in einem digitalen Datenübertragungssystem wie einem Fahrzeug-Funktelefon.

Beschreibung des Standes der Technik

Gewöhnlich kann bei einer digitalen Datenübertragung ein von einer Sendeseite übertragenes Signal auf einer Empfangsseite nicht ordnungsgemäß empfangen werden aufgrund eines Zustands des Kanals oder von Störungen, sondern das übertragene Signal wird in einer umgewandelten Form empfangen aufgrund des Zustands des Kanals oder der Störungen. Ein Modell für das im Kanal umgewandelte Signal ist in 13 dargestellt. Wie in 13 dargestellt ist, wird das eingegebene Signal in dem Kanal verzögert und mit einer Störung kombiniert. Demgemäß wird, wenn das übertragene Signal gleich Ik ist, ein empfangenes Signal rk durch die folgende Formel (1) ausgedrückt.

Hierin stellt "L" eine Speicherlänge des Kanals, der die Verzögerung des übertragenen Signals bewirkt, dar, "ci" stellt einen Anzapfkoeffizienten dar und "wk" stellt eine Störkomponente dar. Der Anzapfkoeffizient und die Störkomponente werden durch eine Charakteristik des Kanals bestimmt. Wenn der Anzapfkoeffizient als eine Decodierregel gelesen wird, arbeitet der Anzapfkoeffizient als eine Viterbi-Decodierung. Ein Empfänger empfängt ein empfangenes Signal rk und das empfangene Signal wird durch dieses empfangene Signal rk und dem Anzapfkoeffizienten ci geschätzt. Ein Empfänger (eine Folgeschätzvorrichtung) berechnet einen geschätzten Wert (nachfolgend als "Nachbildung" bezeichnet) eines empfangenen Signals durch Falten eines Kandidaten eines übertragenen Signals und eines bekannten Anzapfkoeffizienten wie in Formel (2).

Weiteren berechnet die Folgeschätzvorrichtung ein Fehlervermögen zwischen einem tatsächlichen empfangenen Signal und der anhand der Formel (2) berechneten Nachbildung des empfangenen Signals.

Die Folgeschätzvorrichtung sucht einen Kandidaten des übertragenen Signals mit einem kleinsten Fehlervermögen, das anhand von Formel (3) berechnet wurde, und schätzt ihn als ein übertragenes Signal. Die Verarbeitung der Folgeschätzung wird erläutert, wenn die Speicherlänge L des Kanals als L=2 ausgedrückt wird. 14 zeigt ein geeignetes Modell für die Folgeschätzvorrichtung, wenn die Speicherlänge L des Kanals gleich 2 ist. Die Folgeschätzvorrichtung ist so ausgebildet, dass sie ein Modell ähnlich dem des Kanals reproduziert. Eine zusätzliche Vorrichtung zum Zuführen der Störung ist für diese Folgeschätzvorrichtung unter den Kanalmodellen des Kanals nicht erforderlich.

Die Folgeschätzvorrichtung enthält einen Speicher mit einer Speicherlänge, die dieselbe wie die des Kanals ist, der einen geschätzten Wert des übertragenen Signals empfängt, eine Multiplikationsvorrichtung zum Multiplizieren des geschätzten Wertes des übertragenen Signals, der von dem Speicher ausgegeben wird, mit einem vorbestimmten Anzapfkoeffizienten, eine Summiervorrichtung zum Berechnen einer Nachbildung eines empfangenen Signals durch Summieren der von der Multiplikationsvorrichtung erhaltenen multiplizierten Werte, eine Differenzberechnungsvorrichtung zum Berechnen der Differenz zwischen der von der Summiervorrichtung ausgegebenen Nachbildung des empfangenen Signals und einem tatsächlichen Empfangssignal, und eine Quadratsummiervorrichtung zum Summieren der von der Differenzberechnungsvorrichtung ausgegebenen Quadratwerte. Der in der Multiplikationsvorrichtung gesetzte vorbestimmte Anzapfkoeffizient ist derselbe wie der aus einer Charakteristik des Kanals erhaltene Anzapfkoeffizient.

Ein Verfahren für eine Maximalwahrscheinlichkeitserfassung gemäß einer derartigen Folgeschätzvorrichtung wird erläutert. Zuerst wird ein Kandidat des übertragenen Signals mit der Übertragungsfolgelänge N empfangen. Dieser Kandidat des übertragenen Signals wird in den Speicher der Folgeschätzvorrichtung eingegeben. Die Multiplikationsvorrichtung multipliziert jedes von dem Speicher ausgegebene Signal mit Anzapfkoeffizienten C1 und C2. Sie multipliziert auch einen Anzapfkoeffizienten Co mit dem Eingangssignal, das nicht durch den Speicher hindurchgeht. Die Summiervorrichtung erhält eine Nachbildung des empfangenen Signals durch Summieren aller Werte, die durch die Multiplikationsvorrichtung multipliziert wurden. Die Differenzberechnungsvorrichtung erhält dann die Differenz zwischen dem tatsächlichen empfangenen Signal und der Nachbildung des empfangenen Signals, die von der Summiervorrichtung erhalten wurde.

Die Quadratsummiervorrichtung summiert das Quadrat des von der Differenzberechnungsvorrichtung ausgegebenen Differenzwerts. Die Quadratsummiervorrichtung liefert eine Summe des Differenzwertes durch Summieren der Summe des Quadrats der Differenz zwischen dem empfangenen Signal und der Nachbildung des empfangenen Signals für alle Signalfolgen. Die Anzahl von Kandidaten dieses übertragenen Signals ist gleich 2N, wenn die Länge der Übertragungsfolge gleich N ist, und alle Kandidaten werden wie vorstehend beschrieben verarbeitet. Eine Maximalwahrscheinlichkeits-Erfassungsvorrichtung schätzt einen Kandidaten des übertragenen Signals als ein übertragenes Signal, wenn die durch die Quadratsummiervorrichtung gelieferte Quadratsumme am kleinsten ist.

Im Fall der Maximalwahrscheinlichkeitserfassung nimmt eine Operationsmenge proportional zu dem Exponenten der Übertragungsfolgelänge N zu. So wird die Maximalwahrscheinlichkeitserfassung unter Verwendung eines Viterbi-Algorithmus verwendet. Die Einzelheiten des Viterbi-Algorithmus sind beschrieben in dem Papier "The Viterbi algorithm", G.D. Forney, Jr., Proc. IEEE, Band 61, Nr. 3, Seiten 268–278, März 1973. Im Fall des Kanalsmodells nach 15 kann ein Fehlervermögen zu einer Zeit k berechnet werden, wenn die übertragenen Daten zu der Zeit k und die übertragenen Daten zu der vorhergehenden Zeit (k-2) bekannt sind. Die Maximalwahrscheinlichkeitserfassung unter Verwendung des Viterbi-Algorithmus verwendet eine Figur, die Datenübergangsinformationen zeigt (nachfolgend als ein "Trellis-Diagramm" bezeichnet), die anhand der Kombination von Daten zwischen zwei Zeiten erhalten wurden, wie in 16 gezeigt ist.

In diesem Trellis-Diagramm nach 16 wird die Kombination von Daten zwischen zwei Zeiten durch eine Linie verbunden, wobei die folgende Charakteristik berücksichtigt wird. Die Charakteristik wird wie folgt ausgedrückt. Wenn ein in einem Speicher zu einer bestimmten Zeit gespeichertes Signal beispielsweise einen Zustand "00" zeigt, geht der Zustand zu der nächsten Zeit entweder zu einem Zustand "10" oder einem Zustand "00" über, jedoch geht er niemals zu einem Zustand "01" oder einem Zustand "11" über. Dies ergibt sich daraus, dass, wenn ein Schiebewiderstand eines Zustands "000" einmal verschoben wird, nur "000" oder "100" erhalten wird. Demgemäß wird bei Verbinden einer Kombination von Daten zwischen zwei Zeiten durch eine Linie angenommen, dass der Zustand "00" und der Zustand "10" bzw. der Zustand "00" und der Zustand "00" durch Linien verbunden sind. Jedoch sind der Zustand "00" und der Zustand "01" bzw. der Zustand "00" und der Zustand "11" nicht durch Linien verbunden.

Auf diese Weise wird das Trellis-Diagramm unter Berücksichtigung der Charakteristik des Übergangs gebildet. In 16 hat eine durch eine Linie verbundene Kombination eine Möglichkeit eines Übergangs, und eine nicht durch eine Linie verbundene Kombination hat keine Möglichkeit eines Übergangs. Eine den Übergang des Zustands zeigende Linie wird nachfolgend als ein Zweig bezeichnet. Das Trellis-Diagramm hat ausgezogene Linien und gestrichelte Linien. Die ausgezogene Linie bedeutet, dass ein Signal 0 eingegeben wird und der Zustand übergeht, während die gestrichelte Linie bedeutet, dass ein Signal 1 eingegeben wird und der Zustand übergeht. Eine Kombination von Daten über drei Zeiten kann bestimmt werden durch Verbinden einer Kombination von Daten zwischen zwei Zeiten durch eine Linie, wie in dem Trellis-Diagramm nach 16 gezeigt ist. Das Fehlervermögen kann durch Verwendung eines derartigen Diagramms erhalten werden.

Die Verarbeitung eines Viterbi-Algorithmus unter Verwendung eines derartigen Trellis-Diagramms wird im Einzelnen erläutert. Wenn die Speicherlänge des Kanals gleich L ist, wird die Anzahl von Zuständen als 2L ausgedrückt. Mit anderen Worten, die Anzahl von Zuständen nimmt proportional zu dem Exponenten der Speicherlänge L des Kanals zu. Eine Operationsmenge nimmt entsprechend der Anzahl der Zustände zu. Während die Folgeschätzvorrichtung nach 13 Kandidaten für alle Signale sucht, kann der Viterbi-Algorithmus die Anzahl von Verarbeitungsschritten für deren Suche herabsetzen. 17 zeigt einen Prozess des Viterbi-Algorithmus zu jeder Zeit. Nachfolgend wird ein Zustand XX zur Zeit k beschrieben als "s[k, XX]", und eine Route, die zur Zeit k1 einen Zustand XX hat und zu einem Zustand ## übergeht, wird ausgedrückt als "s [k1, XX]/s [k2, ##]".

  • (1) Ein Quadratfehler für jeden Zweit (ein Liniensegment von 16) wird berechnet. Dieser Quadratfehler für jeden Zweig wird als eine Zweigmetrik bezeichnet. Beispielsweise bedeutet ein Zweig, der einen Zustand s[0, 00] und einen Zustand s[1, 00] verbindet, das Daten über drei Zeiten gleich [000] sind. Jeweilige Daten werden mit einem Anzapfkoeffizienten multipliziert, und eine Differenz zwischen dem multiplizierten Ergebnis und dem tatsächlichen empfangenen Signal wird berechnet, und das Differenzergebnis wird quadriert, um einen Quadratfehler zu berechnen. Auf diese Weise werden die Quadratfehler für alle Zweige berechnet.
  • (2) Ein Pfad zum Erreichen eines Zustands zu einer bestimmten Zeit ("00", "10", "01" und "11" in 16) wird herausgezogen. Eine Pfadmetrik wird berechnet durch Akkumulieren der Zweigmetriken der Zweige, die die herausgezogenen Pfade bilden. Die Pfadmetrik wird für alle Pfade von allen Zuständen berechnet. Beispielsweise gibt es zwei Pfade, die einen Zustand s[2,00] erreichen, nämlich einen Pfad s[0,00]/s[1,00]/s[2,00] und einen Pfad s[0,11]/s[1,01]/s[2,00]. Die Pfadmetrik wird für diese beiden Pfade berechnet.
  • (3) Pfadmetriken von mehreren Pfaden, die für jeden Zustand herausgezogen sind, werden miteinander verglichen. Dieser Vergleich wird für alle Zustände durchgeführt.
  • (4) Als ein Ergebnis des Vergleichs wird ein Pfad mit der kleinsten Pfadmetrik als der zuverlässigste Pfad gespeichert, und die kleinste Pfadmetrik wird auch für jeden Zustand gespeichert. Als ein Ergebnis des Vergleichs wird der Pfad mit der kleinsten Pfadmetrik als "Survivor" bezeichnet, und die Pfadmetrik des Survivors wird als "Survivor-Metrik" bezeichnet. Beispielsweise wird eine Pfadmetrik eines Pfads s[0,00]/s[1,00]/s[2,00] vergleichen mit einer Pfadmetrik eines Pfades s[0,11]/s[1,01]{s[2,00], die beide den Zustand s[2,00] erreichen, wobei ein kleinerer Pfad der Survivor wird.
  • (5) In dem Viterbi-Algorithmus wird schließlich ein Survivor aus mehreren Pfaden, die einen bestimmten Zustand erreichen, ausgewählt.

Es ist der Viterbi-Algorithmus, der die vorbeschriebenen Prozesse für jede zeit durchführt. 18 zeigt ein Ergebnis der Durchführung der Viterbi-Algorithmus unter Verwendung des Trellis nach 16; und welches den Survivor zeigt, der schließlich erhalten wird. Ein Pfad mit der kleinsten Pfadmetrik wird als ein endgültiger Pfad aus den Survivorn zu einer letzten Zeit ausgewählt, wenn die vorbeschriebene Verarbeitung für einen Rahmen durchgeführt wird. In 18 ist ein Pfad, der mit einer dicken ausgezogenen Linien und einer dicken strichlierten Linie illustriert ist, der endgültige Pfad. Eine Signalfolge, die von dem endgültigen Pfad erhalten wird, wird als ein übertragenes Signal geschätzt.

Die Maximalwahrscheinlichkeitserfassung unter Verwendung dieses Viterbi-Algorithmus wird als "Maximalwahrscheinlichkeits-Folgeschätzung (MLSE)" bezeichnet, wie in dem Papier "Maximu-likelihood sequence estimation of digital sequence in the presence of intersymbol interference", G.D. Forney, Jr., IEEE Trans. Inform. Theory, Band IT-18, Nr. 3, Seiten 363–378, Mai 1972 festgestellt wird. Bei dieser MLSE ist, wenn die Speicherlänge des Kanals gleich L ist, die Anzahl von Zuständen des Viterbi-Algorithmus gleich 2L. Auf diese Weise ist die MLSE eine Technik zum eindeutigen Bestimmen eines Wertes eines Kanalspeichers für den Zweig, der den Zustandsübergang zeigt. 19 zeigt ein Modell eines Kanals bei L=5. Wenn die MLSE auf dieses Modell angewendet wird, beträgt die Anzahl von Zuständen 25, d.h. 32.

Obgleich die vorbeschriebene MLSE die Anzahl von Verarbeitungsschritten im Vergleich mit der Maximalwahrscheinlichkeits-Erfassungsvorrichtung nach 13 herabsetzen kann, nimmt die Anzahl von Zuständen exponentiell gemäß der Speicherlänge L des Kanals zu, so dass die Anzahl von Verarbeitungsschritten noch sehr hoch ist. Eine Technik zum Lösen dieses Problems wird als "Folgeschätzung mit verzögerter Entscheidungsrückführung (DFSE)" bezeichnet, die in einem Papier "Delayed decisioin-feedback sequence estimation", A. Duel-Halle et al., IEEE Trans. Commun., Band COM-37, 5, Seiten 428–436, Mai 1989, beschreiben ist. Die Technik DFSE ändert einen Teil der Verarbeitung der vorbeschriebenen MLSE. Ein Verarbeitungsunterschied zwischen der DFSE und MLSE wird kurz unter Verwendung von 20 erläutert. Da die Anzahl von Kanalspeichern in 20 gleich 5 ist, müssen die Zustände durch die fünf Speicher gebildet werden, um alle Kandidaten zu verwenden. In diesem Fall ist die Anzahl von Zuständen bei der MLSE gleich 32. Obgleich ein Kanalspeicher bei der DFSE gleich 5 ist, werden zwei Speicher berücksichtigt, um Zustände zu bilden. Wenn Zustände anhand von zwei Speichern gebildet werden, sind jedoch die Daten für drei Symbole in der hinteren Hälfte nicht ausreichend, um den Speicher des Kanals zu verwenden. Daher wird der von dem Survivor erhaltene Wert als Daten für drei Symbole in der hinteren Hälfte des Survivors verwendet unter Verwendung der Survivor, die mit dem Zustand zu der Zeit (k-1) verbunden sind. Die Anwendung einer derartigen DFSE kann die Anzahl von Zuständen von 32 auf 4 reduzieren.

Ein Listenausgangs-Viterbi-Algorithmus, der eine Erweiterung des Viterbi-Algorithmus ist, ist in einem Papier "A List-type reduced-constraint generalization of the Viterbi Algorithm", T. Hashimoto, IEEE Trans. Inform. Theory, Band IT-33, 6, Seiten 866–876, November 1987, beschrieben. Der Listenausgangs-Viterbi-Algorithmus verallgemeinert den Viterbi-Algorithmus wie folgt:

  • • eine Speicherlänge des Viterbi-Algorithmus wird kürzer als die Grenzlänge L des Kanals oder des Codes gesetzt, und
  • • die Anzahl der Survivor, die mit jedem Zustand verbunden sind, wird auf S anstatt auf eins verallgemeinert.

Die erstgenannte Verallgemeinerung ist dasselbe Konzept wie das der DFSE. Andererseits wird bei der zweiten Verallgemeinerung eine Zweiwerteübertragung angenommen, S Pfade mit der höchsten Wahrscheinlichkeit werden aus zwei S Eintrittspfaden ausgewählt. Auf diese Weise wird, da dieser Algorithmus diese Liste auf der Grundlage der Metrik für jeden Zustand bildet, er als Listenausgangs-Viterbi-Algorithmus anstelle eines allgemeinen Viterbi-Algorithmus genannt.

Die Arbeitsweise des Listenausgangs-Viterbi-Algorithmus ist in 21 dargestellt, wobei die Anzahl von Zuständen gleich vier ist und die Anzahl S von Survivorn zwei ist. Ausgezogenen Linien drücken Survivor mit der höchsten Wahrscheinlichkeit in jedem Zustand aus, und strichlierte Linien beschreiben Survivor mit der zweithöchsten Wahrscheinlichkeit in jedem Zustand. In jedem Zustand sind zwei Survivor gespeichert. Beispielsweise sind in einem Zustand "00" zur Zeit k Übergänge von einem Zustand "00" und einem Zustand "01" zur Zeit (k-!). In einem Zustand "00" zur Zeit (k-1) gibt es zwei Arten von Survivorn von einem Zustand "00" und einem Zustand "01" zur Zeit (k-2). In gleicher Weise gibt es in einem Zustand "01" zur Zeit (k-1) zwei Arten von Survivorn von einem Zustand "10" und einem Zustand "11" zur Zeit (k-2).

In einem Zustand "00" zur Zeit k wird eine Pfadmetrik für die vorgenannten vier Pfade berechnet, und zwei höhere Pfade unter diesen werden als Survivor betrachtet. Die Survivor werden nicht immer ausgewählt von einem Zustand "00" zur Zeit (k-1) und ein anderer von einem Zustand "01" zur Zeit (k-1). Es besteht eine Möglichkeit, dass beide Pfade von einem Zustand "00" zu einer Zeit (k-1) ausgewählt werden, wie beide durch die ausgezogene und die strichlierte Linie gezeigt sind. In diesem Fall sind die Zustände dieser zwei Survivor zur Zeit (k-1) dieselben, aber Zustände zur Zeit (k-2) sind unterschiedlich. Eine derartige Flexibilität ist ein spezifisches Merkmal des Listenausgangs-Viterbi-Algorithmus. Um zwei Pfade aus vier Pfaden auszuwählen, ist es erforderlich, die Pfade in der Reihenfolge von Pfadmetriken anzuordnen. Mit anderen Worten, eine Sortierung ist erforderlich. Im Allgemeinen ist eine große Verarbeitungsmenge für das Sortieren erforderlich, und eine lange Verarbeitungszeit wird benötigt, selbst wenn der Algorithmus durch eine Schaltung realisiert ist.

22 ist ein Blockschaltbild, das eine Vergleichs- /Auswahlverarbeitung bei dem gewöhnlichen Viterbi-Algorithmus zeigt. Das Blockschaltbild nach 22 enthält Survivor-Eingangsanschlüsse 33, Pfadmetrik-Eingangsanschlüsse 34, einen Survivor-Ausgangsanschluss 35, einen Pfadmetrik-Ausgangsanschluss 36, eine Auswahlvorrichtung B 39-2 und einen Komparator 100. Der Komparator 100 gibt die Auswahlinformationen aus, um die Werte von zwei Pfadmetriken zu vergleichen, und wählt die kleinere aus. Die Auswahlvorrichtung B 39-2 wählt einen der beiden Survivor und die beiden Pfadmetriken auf der Grundlage der vorgenannten Auswahlinformationen aus.

23 ist ein Blockschaltbild, das eine Vergleichs- /Auswahlverarbeitung in dem Listenausgabe-Viterbi-Algorithmus zeigt. In diesem Blockdiagramm wird angenommen, dass der Listenausgabe-Viterbi-Algorithmus ein Modell von S=4 ist, was bedeutet, dass vier Pfadmetriken aus den acht Pfadmetriken ausgewählt werden. Das Blockschaltbild nach 23 enthält Survivor-Eingangsanschlüsse 33, Pfadmetrik-Eingangsanschlüsse 34, Survivor-Ausgangsanschlüsse 35, Pfadmetrik-Ausgangsanschlüsse 36, eine Auswahlvorrichtung A 39-1 und einen Sortierkomparator 101. Der Sortierkomparator 101 vergleicht die acht Pfadmetriken, ordnet die Ergebnisse in einer aufsteigenden Folge von einem kleinsten aus an und gibt die Auswahlinformationen, die vier kleinere auswählen, aus. Die Auswahlvorrichtung A 39-1 wählt jeweils vier Survivor aus acht Survivorn und acht Pfadmetriken auf der Grundlage der vorgenannten Auswahlinformationen aus.

24 ist eine detaillierte Konstruktion des Sortierkomparators 101 nach 23. Das Blockschaltbild nach 24 enthält einen Auswahlinformations-Ausgangsanschluss 42, Pfadmetrik-Eingangsanschlüsse 104 und einen 8/1-Komparator 106-1. Der 8/1-Komparator 106-1 wählt die kleinste Pfadmetrik aus acht Pfadmetriken aus und gibt eine Adresse zum Identifizieren dieser Pfadmetrik, die für die Auswahlinformationen verwendet wird, aus. Als Nächstes wählt ein 8/1-Komparator 106-2 die zweitkleinste Pfadmetrik aus acht Pfadmetriken aus. Der 8/1-Komparator 106-3 und ein 8/1-Komparator 106-4 arbeiten in derselben Weise.

15 ist eine detaillierte Konstruktion des 8/1-Komparators 106 in 25. Das Blockschaltbild nach 25 enthält 2/1-Komparatoren 40, eine Maximalwert-Zwangseinfügungsschaltung 102, Maximalwert-Zwangseinfügungsanzeige-Eingangsanschlüsse 103, Pfadmetrik-Eingangsanschlüsse 104 und einen Pfadmetrik-Auswahlinformations-Ausgangsanschluss 105. Die Maximalwert-Zwangseinfügungsschaltung 102 empfängt das Maximalwert-Zwangseinfügungsanzeigesignal und fügt zwangsweise den Maximalwert an einem spezifischen Anschluss der Pfadmetrik ein. Dann suchen die 2/1-Komparatoren 40 die kleinste Pfadmetrik durch ein Turniersystem und geben die Pfadmetrik-Auswahlinformationen aus.

Für den Fall, dass eine Sortierung von 25 bis S unter der Survivorzahl S durchgeführt wird, beträgt die Gesamtanzahl der 2/1-Komparatoren (2S2-S) und die Anzahl der maximalen Stufen des 2/1-Komparators beträgt (log2S+1)S. Mit anderen Worten, gemäß einer Zunahme von S wächst ein Schaltungsmaßstab im Verhältnis von 2S2 und eine Verzögerungszeit nimmt im Verhältnis von Slog2S zu. Gewöhnlich wird ein Zweig des quadratischen euklidschen Abstands, der in der Formel (3) ausgedrückt ist, verwendet für einen Metrikwert des Viterbi-Algorithmus. Wenn eine Zweigmetrik gleich &Ggr;k zur Zeit k ist, wird die Formel (4) erhalten.

Andererseits wird die folgende, durch Formel (5) gezeigte Zweigmetrik durch das Papier "Adaptive maximum-likelihood receiver for carrier-modulated datatransmission systems", G. Ungerboeck, IEEE Trans. Commun., Band COM-22, Nr. 5, Seiten 624–636, Mai 1974, vorgeschlagen.

Vorstehend bedeutet * eine komplexe Konjugation, und Yk und xs sind wie folgt in den Formeln (6) bzw. (7) definiert.

Yk ist äquivalent einem Anpassungsfilter-Ausgangssignal und xs ist äquivalent einer Autokorrelation der Charakteristik des Kanals.

Eine quadratische Metrik und eine modifizierte Metrik sind gleich, wenn der perfekte Viterbi-Algorithmus (MLSE) verwendet wird. Aber wenn DFSE verwendet wird, sind ihre Bitfehlerraten (BER) unterschiedlich. 26 zeigt BER-Charakteristiken, wenn der Anzapfkoeffizient der Charakteristik des Kanals gleich 1, 2, 0, 0, 0, 4 ist und die Speicherlänge L des Kanals gleich fünf ist. 27 zeigt BER-Charakteristiken, wenn der Anzapfkoeffizient der Charakteristik des Kanals gleich 1, 0, 1, 0, 1, 0 ist und die Speicherlänge L des Kanals gleich fünf ist. In 26 und in 27 zeigt Sqr, eine quadratische Metrik an und Mod. zeigt eine modifizierte Metrik an. Bei Verwendung von DFSE wird die geeignetste Metrik zwischen der quadratischen Metrik und der modifizierten Metrik gemäß der Charakteristik des Kanals bestimmt. In 27 verschlechtert sich die BER der modifizierten Metrik stark.

Bei einem herkömmlichen Folgeschätzverfahren besteht das Problem, dass ein Schaltungsumfang im Verhältnis einer Potenz der Speicherlänge des Kanals zunimmt entsprechend dem Anstieg der Anzahl von Zuständen, wenn MLSE in dem Kanal mit einer langen Verzögerungszeit verwendet wird. Wenn der Listenausgabe-Viterbi-Algorithmus verwendet wird und die Anzahl der Survivor S mehr als zwei Beträgt, wird eine Sortierverarbeitung benötigt. Daher tritt ein anderes Problem dahingehend auf, dass der Schaltungsumfang zunimmt und die Arbeitsgeschwindigkeit langsam wird, da das volumen gemäß der Zunahme von Elementen des Sortierobjekts zunimmt.

Weiterhin besteht, wenn die modifizierte Metrik zum Berechnen der Zweigmetrik verwendet wird, ein Problem, dass die Charakteristik sich bemerkenswert verschlechtert in dem Kanal mit einer großen Zeitstreuung einer Autokorrelation der Kanalimpulsantwort (CIR). Wenn die quadratische Metrik zum Berechnen der Zweigmetrik verwendet wird, besteht ein Problem dahingehend, dass die Charakteristik sich bemerkenswert verschlechtert in dem Kanal mit einer großen Zeitstreuung einer Anzapfleistung einer Kanalimpulsantwort (CIR).

Hekstra, A.P.: "An Alternative to Metric Rescaling in Viterbi Decoders", IEEE TRANSACTIONS ON COMMUNICA-TIONS, Band 37, Nr. 11, 1. November 1989 (1989-11-01), Seiten 1220–1222, XP000074542, weist darauf hin, dass in dem Viterbi-Algorithmus Pfadmetriken unbegrenzt zunehmende Zeitfunktionen sind. Für eine Implementierung müssen daher alle Variablen auf einen endlichen. Bereich beschränkt werden. Zwei Wege für Beschränkungen werden vorgeschlagen:

  • 1) Die Wiederskalierungsmaßnahme, bei der jede Iteration der minimalen Metrik von allen Metriken subtrahiert wird, da der Viterbi-Algorithmus nur von Differenzen von Metriken abhängt, und die Differenz zwischen Metriken ist begrenzt.
  • 2) Die arithmetische Maßnahme des Komplements der beiden. die einen Überlauf nicht vermeidet, wie bei der Wiederskalierungsmaßnahme, sondern stattdessen den Überlauf in einer solchen Weise aufnimmt, dass er die Korrektheit der Ergebnisse nicht beeinträchtigt. Diese Maßnahme verwendet die Eigenschaft des Viterbi-Algorithmus, dass sein Verhalten unveränderlich bleibt, wenn ein modularer Operator auf die Metriken angewendet wird, vorausgesetzt, dass sein Bereich ausreichend groß und angenähert symmetrisch um null herum ist.

ZUSAMMENFASSUNG DER ERFINDUNG

Es ist eine Aufgabe der vorliegenden Erfindung, die Arbeitsgeschwindigkeit bei dem minimalen Schaltungsumfang in dem Kanal mit einer langen Verzögerungszeit zu erhöhen und ein Folgeschätzverfahren und eine Folgeschätzvorrichtung vorzusehen, die die Charakteristik hiervon verbessern können.

Es ist eine andere Aufgabe der vorliegenden Erfindung, die geschätzte Charakteristik durch die Übertragungscharakteristik nicht zu stark zu verschlechtern und die geschätzte Charakteristik zu verbessern, eher als wenn die Metrik auf irgendeine der Metriken fixiert ist.

Es ist eine weitere Aufgabe der vorliegenden Erfindung, die geschätzte Charakteristik zu verbessern, eher als wenn die Metrik auf eine der von der quadratischen Metrik oder der modifizierten Metrik fixiert ist.

Es ist noch eine weitere Aufgabe der vorliegenden Erfindung, die Metrik als Antwort auf die Übertragungscharakteristik sicher auszuwählen.

Die Aufgaben gemäß der Erfindung werden gelöst durch ein Folgeschätzverfahren mit den Merkmalen des Anspruchs 1 bzw. eine Folgeschätzvorrichtung mit den Merkmalen des Anspruchs 3. Ein bevorzugtes Ausführungsbeispiel des Verfahrens ist in Anspruch 2 definiert, und ein bevorzugtes Ausführungsbeispiel der Vorrichtung ist in Anspruch 4 definiert.

Gemäß einem ersten Aspekt der Erfindung ist ein Folgeschätzverfahren zum Schätzen einer übertragenen Signalfolge, die von einer Sendeseite übertragen wurde, unter Verwendung eines Listenausgabe-Viterbi-Algorithmus zum Bestimmen eines oder mehrerer Survivor für jeden Zustand eines Viterbi-Algorithmus, enthaltend einen oder mehr Zustände, durch Eingabe einer Charakteristik eines empfangenen Signals und eines Kanals, aufweisend einen Auswahlverarbeitungsschritt zum Auswählen von Survivorn höherer Ordnung anstelle des Sortierens in der Ordnung von Metriken, gekennzeichnet durch eine Zweigmetrik-Berechnungsschritt zum Berechnen jeder von mehreren Zweigmetriken für jeden Zweig des Zustandsübergangs, der den Viterbi-Trellis bildet, durch Eingabe der empfangenen Signalfolge und ihrer Schätzsignalfolge, unter Verwendung eines Verfahrens zum Berechnen einer quadratischen Zweigmetrik &Ggr;k zu der Zeit k unter Verwendung der Formel wobei L die Speicherlänge des Kanals ist, rk das empfangene Signal ist, re k ein geschätzter Wert des empfangenen Signals ist, ci ein Anzapfkoeffizient des Kanals und I das übertragene Signal ist, und eines Verfahrens zum Berechnen einer modifizierten Zweigmetrik &Ggr;k zu der Zeit k unter Verwendung der Formel wobei * eine komplexe Konjugation bezeichnet, einen Auswahlschritt zum Auswählen der quadratischen Zweigmetrik, wenn eine Leistung PB > eine Leistung PA ist, und zum Auswählen der modifizierten Zweigmetrik, wenn PA > PB ist, worin wobei V die Speicherlänge des Trellis des Viterbi-Algorithmus ist; und einen Pfadmetrik-Berechnungsschritt zum Berechnen des Pfadmetrikwertes für jeden Pfad, der den Viterbi-Trellis bildet, auf der Grundlage des für jeden Zwei ausgewählten Zweigmetrikwertes, wobei der Auswahlverarbeitungsschritt S Survivor höherer Ordnung auswählt anstelle des Sortierens in der Reihenfolge der Pfadmetrik nach der Auswahl S Survivorn gemäß den Pfadmetrikwerten.

Gemäß einem bevorzugten Ausführungsbeispiel weist der Auswahlverarbeitungsschritt weiterhin die Verringerung der Anzahl von Bits des Pfadmetrikwertes der Survivor auf.

Gemäß einem zweiten Aspekt der Erfindung ist eine Folgeschätzvorrichtung zum Schätzen einer übertragenen Signalfolge, die von einer Sendeseite übertragen wurde, unter Verwendung eines Listenausgabe-Viterbi-Algorithmus zum Bestimmen eines oder mehrerer Survivor für jeden Zustand eines Viterbi-Algorithmus, enthaltend einen oder mehr Zustände durch Eingabe einer Charakteristik eines empfangenen Signals und eines Kanals, aufweisend einen Auswahlprozessor zum Auswählen von Survivorn höherer Ordnung anstelle des Sortierens in der Reihenfolge von Metriken, gekennzeichnet durch eine Zweigmetrik-Berechnungsvorrichtung zum Berechnen jeder von mehreren Zweigmetriken für jeden Zweig des Zustandsübergangs, der den Viterbi-Trellis bildet, durch Eingabe der empfangenen Signalfolge und ihrer Schätzsignalfolge, unter Verwendung eines Verfahrens zum Berechnen einer quadratischen Zweigmetrik &Ggr;k zu der Zeit k unter Verwendung der Formel wobei L die Speicherlänge des Kanals ist, rk das empfangene Signal ist, re k ein geschätzter Wert des empfangenen Signals ist, ci ein Anzapfkoeffizient des Kanals ist, und I das übertragene Signal ist, und eines Verfahrens zum Berechnen einer modifizierten Zweigmetrik &Ggr;k zu der Zeit k unter Verwendung der Formel wobei * eine komplexe Konjugation bezeichnet, eine Auswahlvorrichtung zum Auswählen der quadratischen Zweigmetrik, wenn eine Leistung PB > eine Leistung PA ist, und zum Auswählen der modifizierten Zweigmetrik, wenn PA > PB ist, worin wobei V die Speicherlänge des Trellis des Viterbi-Algorithmus ist; und eine Pfadmetrik-Berechnungsvorrichtung zum Berechnen des Pfadmetrikwertes für jeden Pfad, der den Viterbi-Trellis bildet, auf der Grundlage des für jeden Zweig ausgewählten Zweigmetrikwertes; wobei der Auswahlprozessor S Survivor höherer Ordnung auswählt anstelle des Sortierens in der Reihenfolge der Pfadmetrik nach der Auswahl von S Survivorn gemäß den Pfadmetrikwerten.

KURZBESCHREIBUNG DER ZEICHNUNGEN

Ein weiterer Bereich der Anwendbarkeit der vorliegenden Erfindung wird augenscheinlich anhand der nachfolgend gegebenen detaillierten Beschreibung. Jedoch ist darauf hinzuweisen, dass die detaillierte Beschreibung und spezifische Beispiele, während sie bevorzugte Ausführungsbeispiele der Erfindung anzeigen, nur im Wege der Illustration gegeben sind, da verschiedene Änderungen und Modifikationen innerhalb des Geistes und des Bereichs der Erfindung für den Fachmann anhand dieser detaillierten Beschreibung augenscheinlich werden.

1 ist ein Blockschaltbild, das eine Position einer Viterbi-Entzerrungsvorrichtung in einem Empfänger nach der vorliegenden Erfindung zeigt.

2 ist ein Blockschaltbild, das die Viterbi-Entzerrungsvorrichtung in dem Empfänger nach 1 zeigt.

3 ist ein Blockschaltbild, das einen Zweigmetrikgenerator nach 2 des ersten Ausführungsbeispiels der vorliegenden Erfindung zeigt.

4 ist ein Blockschaltbild, das eine Zweigmetrik-Auswahlsignal-Bildungsschaltung in dem Zweigmetrikgenerator nach 3 zeigt.

5 ist ein Blockschaltbild, das eine Zweigmetrik-Bildungsschaltung vom Auswahltyp in dem Zweigmetrikgenerator nach 3 zeigt.

6 zeigt Charakteristiken einer Bitfehlerraten(BER)-Charakteristik von sechs Wellen, die jeweils eine gleiche Leistung unter dem Rayleigh-Fading haben, durch das Folgeschätzverfahren nach dem ersten Ausführungsbeispiel der vorliegenden Erfindung.

7 ist ein Blockschaltbild, das einen Vergleichs-/Auswahlprozessor nach 2 bei einem zweiten Ausführungsbeispiel der vorliegenden Erfindung zeigt.

8 ist ein Blockschaltbild, das einen Komparator/eine Auswahlvorrichtung in dem Vergleichs-/Auswahlprozessor nach 7 zeigt.

9 ist ein Blockschaltbild, das einen vereinfachten Komparator (4/2) in dem Komparator/der Auswahlvorrichtung nach 8 zeigt.

10 ist ein Blockschaltbild, das einen vereinfachten Komparator (8/4) in dem Komparator/der Auswahlvorrichtung nach 8 zeigt.

11 ist ein Blockschaltbild, das einen vereinfachten Komparator nach dem dritten Ausführungsbeispiel der vorliegenden Erfindung zeigt.

12 ist ein Blockschaltbild, das einen bitonischen Folgegenerator in dem vereinfachten Komparator nach 11 zeigt.

13 ist ein allgemeines Diagramm zur Erläuterung eines Modells, das eine Umwandlung eines Signals in dem Kanal zeigt.

14 ist ein allgemeines Diagramm zur Erläuterung eines Modells einer Folgeschätzvorrichtung, die für einen Fall, in welchem eine Speicherlänge L eines Kanals gleich zwei ist, am geeignetsten ist.

15 ist ein allgemeines Diagramm zur Erläuterung eines Modells des Kanals zum Berechnen einer Fehlerleistung zu einer gegenwärtigen Zeit k gemäß den übertragenen Daten während der um zwei vorhergehenden Zeit (k-2) und gegenwärtigen Zeit k.

16 ist ein Trellis-Diagramm, das eine Datenübergangsinformation gemäß einer Kombination über zwei Zeiten zeigt.

17 ist ein Flussdiagramm, das eine Verarbeitungsfolge zu jeder Zeit eines Viterbi-Algorithmus zeigt.

18 ist ein allgemeines Diagramm, das das Ergebnis der Durchführung des Viterbi-Algorithmus unter Verwendung des Trellis-Diagramms nach 16 zeigt.

19 ist ein allgemeines Diagramm, das ein Modell des Kanals zeigt, wenn die Speicherlänge L des Kanals gleich fünf ist.

20 ist ein allgemeines Diagramm zur Erläuterung einer Differenz zwischen der Arbeitsweise nach DFSE und der nach MLSE.

21 ist ein allgemeines Diagramm zur Erläuterung der Arbeitsweise eines Listenausgabe-Viterbi-Algorithmus, wenn eine Zustandsanzahl gleich vier ist und die Anzahl von Survivorn gleich zwei ist.

22 ist ein Blockschaltbild, das eine Vergleichs-/Auswahlverarbeitung zum Realisieren eines gewöhnlichen Viterbi-Algorithmus zeigt.

23 ist ein Blockschaltbild, das eine Vergleichs-/Auswahlverarbeitung bei dem Listenausgabe-Viterbi-Algorithmus zeigt.

24 ist ein Blockschaltbild, das einen Sortierkomparator für die Vergleichs- /Auswahlverarbeitung nach 23 zeigt.

25 ist ein Blockschaltbild, das einen 8/1-Komparator in dem Sortierkomparator nach 24 zeigt.

26 zeigt BER-Charakteristiken, wenn die Anzapfkoeffizienten gleich 1, 2, 0, 0, 0, 4 sind und die Speicherlänge L des Kanals gleich fünf ist.

27 zeigt BER-Charakteristiken, wenn die Anzapfkoeffizienten gleich 1, 0, 1, 0, 1, 0 sind und die Speicherlänge L des Kanals gleich fünf ist.

DETAILLIERTE BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSBEISPIELE

1 zeigt eine Viterbi-Entzerrungsvorrichtung in einem Empfänger, der den Viterbi-Algorithmus anwendet. Die Viterbi-Entzerrungsvorrichtung nach 1 enthält Antennen 1, quasi kohärente Detektoren 2, eine adaptive Viterbi-Entzerrungsvorrichtung 3, eine Zeitschätzvorrichtung 4 und einen Entscheidungsausgangsanschluss 5. In der Viterbi-Entzerrungsvorrichtung nach 1 wird ein übertragenes Signal von der Antenne über den Kanal eingegeben, wird semisynchron erfasst und wird ein Basisband-Empfangssignal. Die Taktschätzvorrichtung 4 empfängt dieses empfangene Signal zum Reproduzieren eines Taktsignals. Die adaptive Viterbi-Entzerrungsvorrichtung 3 empfängt das empfange Signal und das Taktsignal und gibt einen Schätzwert für übertragene Daten (eine Entscheidung) aus.

2 zeigt eine adaptive Viterbi-Entzerrungsvorrichtung 3 nach 1 im Einzelnen. Die adaptive Viterbi-Entzerrungsvorrichtung 3 nach 2 enthält einen Entscheidungsausgangsanschluss 5, einen Zweigmetrikgenerator 6, einen Pfadmetrikgenerator 7, einen Vergleichs-/Auswahlprozessor 8, einen Pfadmetrikspeicher 9, einen Survivorspeicher 10, einen Entscheidungsgenerator 11, eine Kanalcharakteristik-Schätzvorrichtung 12, eine Lerntabelle 13 und Empfangssignal-Eingangsanschlüsse 14. Der Zweigmetrikgenerator 6 empfängt das empfangene Signal von den quasi kohärenten Detektoren 2, eine Kanalcharakteristik von der Kanalcharakteristik-Schätzvorrichtung 12 und einen Survivor von dem Survivorspeicher 10 und bildet eine Zweigmetrik. Der Pfadmetrikgenerator 7 empfängt die Zweigmetrik und eine von dem Pfadmetrikspeicher 9 eingegebene Pfadmetrik und bildet eine Pfadmetrik.

Der Vergleichs-/Auswahlprozessor 8 empfängt die von dem Pfadmetrikgenerator 7 gebildete Pfadmetrik zur Durchführung einer Vergleichs-/Auswahlverarbeitung und gibt eine Pfadmetrik und einen Survivor zu dem Pfadmetrikspeicher 9 und dem Survivorspeicher 10 in Abhängigkeit von den Auswahlinformationen aus. Der Entscheidungsgenerator 11 empfängt die Pfadmetrik von dem Pfadspeicher nach der Vergleichs-/Auswahlverarbeitung und gibt eine Entscheidung aus. Die Kanalcharakteristik-Schätzvorrichtung 12 schätzt eine Kanalcharakteristik anhand des empfangenen Signals und einer Entscheidung von dem Entscheidungsgenerator 11 oder von der Lerntabelle 13 eingegebenen Daten. Das Kanalschätzverfahren wird in einzelnen beispielsweise in dem Papier "An adaptive maximum-likelihood sequence estimator for fast time-varying intersymbol interference channels", H. Kubo et al., IEEE Trans. Commun., Band COM-42, Nr. 2/3/4, Seiten 1872–1880, Feb./März/April 1994, beschrieben.

Ausführungsbeispiel 1

3 zeigt eine detaillierte Ausbildung des Zweigmetrikgenerators 6 nach 2. Der Zweigmetrikgenerator nach 3 enthält Empfangssignal-Eingangsanschlüsse 14, einen Kanalcharakteristik-Eingangsanschluss 15, Zweigmetrik-Ausgangsanschlüsse 16, eine Zweigmetrik-Bildungsschaltung 17 vom Auswahltyp und eine Zweigmetrik-Auswahlsignal-Bildungsschaltung 18. Die Zweigmetrik-Bildungsschaltung 17 vom Auswahltyp schaltet eine Zweigmetrikbildungs-Bezugsgröße zu einer quadratischen Metrik und einer modifizierten Metrik gemäß einem Metrikauswahlsignal von der Zweigmetrik-Auswahlsignal-Bildungsschaltung 18.

4 zeigt eine detaillierte Ausbildung der Zweigmetrik-Auswahlsignal-Bildungsschaltung 18 nach 3. Die Zweigmetrik-Auswahlsignal-Bildungsschaltung 18 nach 4 enthält einen Kanalcharakteristik-Eingangsanschluss 15, eine ISI-Restleistungs-Berechnungsschaltung 19, eine Korrelationsrestleistungs-Berechnungsschaltung 20, einen Leistungskomparator 21 und einen Auswahlsignal-Eingabe/Ausgabeanschluss 22. Unter der Annahme, dass die Speicherlänge des Kanals gleich L ist und die Speicherlänge des Trellis des Viterbi-Algorithmus gleich V ist, berechnet die ISI-Restleistungs-Berechnungsschaltung 19 eine Leistung PA als Formel (8).

Die Korrelationsrestleistungs-Berechnungsschaltung 20 berechnet eine Leistung PB in ähnlicher Weise unter Verwendung von Formel (9).

In Formel (9) ist xs ein in Formel (7) definierter Wert. Der Leistungskomparator 21 vergleicht PA und PB und gibt ein Auswahlsignal zur Auswahl der modifizierten Metrik, wenn PA größer ist und ein Signal zur Auswahl der quadratischen Metrik, wenn PB größer ist, aus.

5 zeigt eine detaillierte Ausbildung der Zweigmetrik-Bildungsschaltung 17 vom Auswahltyp nach 3. Die Zweigmetrik-Bildungsschaltung 17 vom Auswahltyp nach 5 enthält einen Empfangssignal-Eingangsanschluss 14, einen Kanalcharakteristik-Eingangsanschluss 15, einen Auswahlsignal-Eingabe/Ausgabe-Anschluss 22, ein Anpassungsfilter 23, einen Kanalcharakteristikkorrelator 24, eine Nachbildungstabelle B 25, eine Nachbildungstabelle A 26, N Zweigmetrik-Berechnungsvorrichtungen B 27, N Zweigmetrik-Berechnungsvorrichtungen A 28, Zweigmetrik-Auswahlschaltungen 29, N Datenkandidatenwert-Eingangsanschlüsse 30, an denen die Daten durch den Trellis und den Survivor bestimmt werden, und N Zweigmetrik-Ausganganschlüsse 31, wobei N eine Gesamtanzahl von Zweigmetriken darstellt.

Das Anpassungsfilter 23 führt eine Anpassungsfilterung des empfangenen Signals gemäß der Kanalcharakteristik durch. Der Kanalcharakteristikkorrelator 24 empfängt die Kanalcharakteristik und gibt einen Korrelationswert hiervon aus. Die Nachbildungstabelle B 25 bildet eine für die modifizierte Metrik verwendete Nachbildungstabelle. Die Nachbildungstabelle A 26 bildet für die quadratische Metrik verwendete Nachbildungstabelle. Die jeweilige Zweigmetrik-Berechnungsvorrichtung B 27 empfängt ein Ausgangssignal von dem Anpassungsfilter 23, einen Wert von der Nachbildungstabelle B 25 und einen Datenkandidatenwert, der von dem Trellis und dem Survivorpfad bestimmt ist, und berechnet eine modifizierte Metrik. Die jeweilige Zweigmetrik-Berechnungsvorrichtung A 28 empfängt ein Empfangssignal, einen Wert von der Nachbildungstabelle A 26 und den Datenkandidatenwert, der durch den Trellis und den Survivorpfad bestimmt ist, und berechnet eine quadratische Metrik. Die jeweilige Zweigmetrik-Auswahlschaltung 29 wählt eines der Ausgangssignale von der entsprechenden Zweigmetrik-Berechnungsvorrichtung B 27 und der entsprechenden Zweigmetrik-Berechnungsvorrichtung A 28 aus und gibt eine von diesen zu dem jeweiligen Zweigmetrik-Ausgangsanschluss 31 gemäß den Auswahlinformationen aus.

6 zeigt eine Bitfehlerraten-BER-Charakteristik von sechs Wellen mit jeweils gleicher Leistung unter dem Rayleigh-Fading. In 6 bedeutet MLSE einen Fall, n welchem eine Speicherlänge V eines Trellis im Viterbi-Algorithmus gleich fünf ist, DFSE bedeutet einen Fall, in welchem die Speicherlänge gleich eins ist, Sqr. bedeutet einen Fall, in welchem eine quadratische Metrik verwendet wird, Mod. bedeutet einen Fall, in welchem eine modifizierte Metrik verwendet wird, Sel. bedeutet einen Fall, in welchem diese Erfindung angewendet wird, und Opt. bedeutet einen Fall, in welchem weniger Fehler für jeden Schlitz in Sqr. oder Mod. ausgewählt werden. Eqr. und Mod. entsprechen einem herkömmlichen Beispiel und Opt. entspricht einem Grenzwert. 6 zeigt, dass diese Erfindung eine günstigere BER-Charakteristik als bei dem herkömmlichen Beispiel realisieren kann.

Ausführungsbeispiel 2

7 zeigt eine detaillierte Ausbildung des Vergleichs-/Auswahlprozessors 8 nach 2. Der Vergleichs-/Auswahlprozessor 8 nach 7 enthält M Komparatoren/Auswahlvorrichtungen 32, Survivor-Eingangsanschlüsse 33, M Pfadmetrik-Eingangsanschlüsse 34, M-Survivor-Ausgangsanschlüsse 35 und M Pfadmetrik-Ausgangsanschlüsse 36. Hierin ist M die Anzahl von Zuständen. In 7 wird der Vorgang der Auswahl von vier Kandidaten aus acht Kandidaten für jeden Zustand erläutert. Der Komparator/die Auswahlvorrichtung 32 empfängt acht Kandidaten für Survivor und acht Pfadmetriken und gibt Survivor und Pfadmetriken entsprechend vier Metriken höherer Ordnung aus.

8 zeigt eine detaillierte Ausbildung des Komparators/der Auswahlvorrichtung 32 nach 7. Der Komparator/die Auswahlvorrichtung 32 nach 8 enthält Survivor-Eingangsanschlüsse 33, Pfadmetrik-Eingangsanschlüsse 34, Survivor-Ausgangsanschlüsse 35, Pfadmetrik-Ausgangsanschlüsse 36, einen Metrikumwandler 37, einen vereinfachten Komparator 38 und eine Auswahlvorrichtung A 39-1. Der metrische Wandler 37 empfängt acht Pfadmetriken und führt die Metrikumwandlung für jede Pfadmetrik durch. Beispielsweise wird diese Metrikumwandlung im Einzelnen in einem Papier "A characteristic of a Viterbi decoder in which the number of bits of a path-metric is reduced" (von Makoto Miyake et al., Technical report (B), The Institute of Electronics, Information and Communication Engineers, Band J71-B, 4, Seiten 555–562, April 1988, erläutert. Anders als bei dem vorgenannten Verfahren kann beispielsweise unter der Annahme, dass eine Pfadmetrik gleich H ist, die Metrikumwandlung erhalten werden durch Ausführen einer logarithmischen Umwandlung und dann Umwandeln des Ergebnisses in eine ganze Zahl, wie durch Formel (10) gezeigt ist. H-INT[log2H](10)

In diesem Fall wird unter der Annahme, dass die Bitzahl der Pfadmetrik gleich x ist, die Bitzahl nach der Umwandlung gleich log2X Bits. Der vereinfachte Komparator 38 sortiert nicht, sondern bildet Signale mit vier Kandidaten höherer Ordnung aus den acht Kandidaten. Jedoch müssen die Signale nicht immer in einer Folge der Ordnung der Wahrscheinlichkeit von Metriken sein. Die Auswahlvorrichtung A 39-1 wählt vier Pfadmetriken und vier Survivor gemäß vier Auswahlinformationen aus.

9 zeigt eine detaillierte Ausbildung eines Ausführungsbeispiels des vereinfachten Komparators 38 in 8. Der vereinfachte Komparator 38 nach 9 enthält Pfadmetrik-Eingangsanschlüsse 41 nach der Umwandlung, Auswahlinformations-Ausgangsanschlüsse 42 und vier 2/1-Komparatoren 40. Jeder 2/1-Komparator 40 empfängt zwei Pfadmetriken und eine Adresse (verwendet für eine Auswahlinformation), die die Pfadmetrik identifizieren, und gibt die Pfadmetrik in der Reihenfolge der Wahrscheinlichkeit aus. Es besteht eine Gelegenheit, dass ein Ausgangssignal einer höheren Ordnung der Wahrscheinlichkeit von den zweiten 2/1-Komparatoren 40-2 eines niedrigerer Ordnung der Wahrscheinlichkeit als ein Ausgangssignal einer niedrigeren Ordnung der Wahrscheinlichkeit von den ersten 2/1-Komparatoren 40-1 hat.

Um dies zu erfassen, werden der dritte 2/1-Komparator 40-3 und der vierte 2/1-Komparator 40-4 verwendet. Die Ausgangssignale niedrigerer Ordnung des ersten 2/1-Komparators 40-1 und die Ausgangssignale niedrigerer Ordnung des zweiten 2/1-Komparators 40-2 werden kreuzverbunden. Mit anderen Worten, eine höhere Ordnung der 2/1-Komparators 40-1 und eine niedrigere Ordnung des 2/1-Komparators 40-2 werden in den 2/1-Komparator 40-3 eingegeben, und eine höhere Ordnung des 2/1-Komparators 40-2 und eine niedrigere Ordnung eines 2/1-Komparators 40-1 werden in den 2/1-Komparator 40-4 eingegeben. Zwei Metriken mit höheren Ordnungen unter den vier Pfadmetriken können ausgewählt werden durch Auswahl eines Ausgangssignals der höheren Wahrscheinlichkeit von dem dritten 2/1-Komparator 40-3 und eines Ausgangssignals der höheren Wahrscheinlichkeit von dem vierten 2/1-Komparator 40-4, obgleich die Ordnung der Wahrscheinlichkeit für die ausgewählten beiden Pfade nicht entschieden ist. Die beiden Wahrscheinlichkeitssignale niedrigerer Ordnung, die von dem dritten 2/1-Komparator 40-3 und von dem vierten 2/1-Komparator 40-4 ausgegeben werden, sind in 9 illustriert und werden in 10 erläutert.

10 zeigt eine detaillierte Ausbildung eines anderen Ausführungsbeispiels des vereinfachten Komparators 38 nach 8. Der vereinfachte Komparator 38 in 10 erweitert den vereinfachten Komparator 38 nach 9. Der vereinfachte Komparator 38 in 10 enthält Pfadmetrik-Eingangsanschlüsse 41 nach der Umwandlung, Auswahlinformations-Ausgangsanschlüsse 42 und vier 4/2-Komparatoren 43. Jeder 4/2-Komparator ist äquivalent dem vereinfachten Komparator 38 in 9. In einer derjenigen des vereinfachten Komparators 38 nach 9 ähnlichen Weise empfängt jeder 4/2-Komparator 43 vier Pfadmetriken und eine Adresse (verwendet für eine Auswahlinformation) zum Identifizieren der vier Pfadmetriken, und er identifiziert zwei Metriken mit höheren Ordnungen der Wahrscheinlichkeit und zwei andere Metriken mit niedrigeren Ordnungen der Wahrscheinlichkeit und gibt diese aus.

Es besteht eine Gelegenheit, dass Ausgangssignale von zwei höheren Ordnungen der Wahrscheinlichkeit von den zweiten 4/2-Komparatoren 43-2 niedrigere Ordnungen der Wahrscheinlichkeiten als Ausgangssignale von zwei niedrigeren Ordnungen der Wahrscheinlichkeit von den ersten 4/2-Komparatoren 43-1 haben. Um dies zu erfassen, werden der dritte 4/2-Komparator 43-3 und der vierte 4/2-Komparator 43-4 verwendet. Die Ausgangssignale niedrigerer Ordnung des ersten 4/2-Komparators 43-1 und die Ausgangssignale niedrigerer Ordnung des zweiten 4/2-Komparators 43-2 sind kreuzverbunden. Mit anderen Worten, eine höhere Ordnung des ersten 4/2-Komparators 43-1 und eine niedrigere Ordnung des zweiten 4/2-Komparators 43-2 werden in den dritten 4/2-Komparator 43-3 eingegeben, und eine höhere Ordnung des zweiten 4/2-Komparators 43-2 und eine niedrigere Ordnung des ersten 4/2-Komparators 43-1 werden in den vierten 4/2-Komparator 43-4 eingegeben. Vier Metriken mit höheren Ordnungen unter den acht Pfadmetriken können ausgewählt werden durch Auswahl von zwei Ausgangssignalen der höheren Wahrscheinlichkeit von dem höheren 4/2-Komparator 43-3 und zwei Ausgangssignalen der höheren Wahrscheinlichkeit von dem vierten 4/2-Komparator 43-4, obgleich die Ordnung der Wahrscheinlichkeit für die ausgewählten vier Pfade nicht entschieden ist. Auf diese Weise kann unter der Annahme, dass U eine natürliche zahl ist, ein Komparator mit 2U/2U-1 Eingängen ausgebildet werden.

Diese vereinfachte Vergleichs-/Auswahlverarbeitung ist nicht nur auf die Viterbi-Entzerrung anwendbar, sondern sie kann auch leicht auf die Viterbi-Decodierung angewendet werden. Bei der Vergleichs-/Auswahlverarbeitung gemäß der vorliegenden Erfindung ist eine Gesamtzahl von 2/1-Komparatoren gleich S2, und eine maximale Stufenzahl von 2/1-Komparatoren ist gleich S. Mit anderen Worten, da der Schaltungsumfang im Verhältnis zu S2 zunimmt und die Verzögerungslänge im Verhältnis Slog2S zunimmt, ist die Gesamtzahl von Komparatoren angenähert 1/2, und die Verzögerungslänge ist angenähert 1/(Log2S+1) im Vergleich mit der herkömmlichen Schaltung. In 6 ist eine Beziehung zwischen der Anzahl von Survivorn S und einer Speicherlänge eines Trellis des Viterbi-Algorithmus ein konstanter Wert wie S2V=8, mit Ausnahme der MLSE im Fall von V=L. In 6 bezieht sich "fast" auf die vorliegende Erfindung und "conv" bezieht sich auf das herkömmliche Verfahren. 6 illustriert, dass eine Ausdehnung von S wirksam ist und die Verschlechterung der Charakteristik durch die vorliegende Erfindung klein ist.

Ausführungsbeispiel 3

11 zeigt einen vereinfachten Komparator eines dritten Ausführungsbeispiels der vorliegenden Erfindung. Der vereinfachte Komparator nach 11 entspricht dem vereinfachten Komparator 38 nach 8. Der vereinfachte Komparator nach 11 umfasst Pfadmetrik-Eingangsanschlüsse 41 nach der Umwandlung der Metrik, Auswahlinformations-Ausgangsanschlüsse 42, einen bitonischen Folgegenerator 50, Ausgänge 51 des bitonischen Folgegenerators 50 und vier 2/1-Komparatoren 52. Der bitonische Folgegenerator 50 empfängt acht an den Pfadmetrik-Eingangsanschlüssen 41 eingegebene Pfadmetriken und Adressen (verwendet als Auswahlinformationen) zum Identifizieren dieser Pfadmetriken. Der bitonische Folgegenerator 50 gibt dann eine bitonische Acht-Element-Folge {b1, b2, ... b8} aus, die aus acht Pfadmetriken und der Adressenfolge {a1, a2, ..., a8} zum Identifizieren der acht Pfadmetriken besteht, die die bitonische Folge bilden. Der 2/1-Komparator 52 hat dieselbe Funktion wie die des 2/1-Komparators 40 nach 9.

Der bitonische Folgegenerator 50 ordnet die von den Pfadmetrik-Eingangsanschlüssen 41 eingegebenen acht Pfadmetriken, um eine bitonische Folge {b1, b2, ..., b8} zu erzeugen, deren zyklische Verschiebung der Formel (11) genügt. b1 ≤ b2 ≤ ... ≤ bj ≥ bj+1 ... ≥ b8(1 ≤ j ≤ 8)(11)

Gleichzeitig erzeugt der bitonische Folgegenerator 50 die Adressenfolge {a1, a2, ..., a8} entsprechend ihrer bitonischen Folge. Der bitonische Folgegenerator 50 gibt dann acht Paare (b1, a1), (b2, a2), ..., (b8, a8) parallel aus, von denen jedes eine Kombination jedes Elements der bitonischen Folge und eines Elements der Adressenfolge entsprechend dem Element der bitonischen Folge ist. Diese acht Ausgangssignale 51 des bitonischen Folgegenerators 50 werden jeweils in den 2/1-Komparator 52 der nächsten Stufe eingegeben. Aufgrund der Charakteristik der bitonischen Folgen können die vier Auswahlinformationen hoher Wahrscheinlichkeit erhalten werden durch einen Vergleich in einer Stufe unter Verwendung von vier 2/1-Komparatoren. Die Charakteristiken der bitonischen Folge werden im Einzelnen erläutert in "Sorting networks and their appllcations" (Proc. AFIPS, 1968, Spring Joint Comput. Conf., Band 32, Seiten 307–314, April – Mai 1968).

12 zeigt ein Beispiel für die innere Ausbildung des bitonischen Folgegenerators 50. Der bitonische Folgegenerator 50 nach 12 enthält sechs 2/1-Komparatoren 60 (60-1 bis 60-6) und sechs 2/1-Komparatoren R61 (61-1 bis 61-6). Die sechs 2/1-Komparatoren 60 haben dieselbe Funktion wie diejenige des 2/1-Komparators 52 in 11. Die 2/1-Komparatoren R61 haben dieselbe Funktion wie die der 2/1-Komparatoren 60, mit der Ausnahme, dass die Reihenfolge der Ausgangssignale umgekehrt ist. Die acht von den Pfadmetrik-Eingangsanschlüssen 41 eingegebenen Pfadmetriken werden durch die 2/1-Komparatoren 60-1 und 60-2 und die 2/1-Komparatoren R61-1 und R61-2 in der ersten Stufe wieder in zwei bitonische Folgen mit jeweils vier Elementen geordnet. Eine der bitonischen Folgen mit vier Elementen weist das Ausgangssignal der 2/1-Komparatoren 60-1 und das Ausgangssignal der 2/1-Komparatoren R61-1 auf. Die andere bitonische Folge mit vier Elementen weist das Ausgangssignal der 2/1-Komparatoren 60-2 und das Ausgangssignal der 2/1-Komparatoren R61-2 auf. Die zwei bitonischen Folgen mit vier Elementen werden jeweils in der aufsteigenden Ordnung und in der absteigenden Ordnung sortiert und werden durch die 2/1-Komparatoren und die 2/1-Komparatoren R in der zweiten und der dritten Stufe in eine bitonische Folge mit acht Elementen vereinigt. Im Allgemeinen können, wenn U eine natürlich Zahl ist, größere bitonische Folgen erzeugt werden durch Wiederholen des Sortierens und des Vereinigens. Schließlich können bitonische Folgen mit 2U Elementen gebildet werden.

Der vereinfachte Komparator zur Auswahl von vier Elementen aus acht Elementen wird vorstehend erläutert. In gleicher Weise kann, wenn U eine natürlich Zahl ist, der vereinfachte Komparator zur Auswahl von 2U-1 Elementen aus 2U Elementen leicht ausgebildet werden.

Wenn q eine natürliche Zahl ist, selbst wenn das Modulationssystem mit dem Modulationsindex Q=2q verwendet wird, kann der vereinfachte Komparator zur Auswahl 2U-1 Elementen aus 2U-1+q Elementen leicht ausgebildet werden.

Diese Vereinbarung des vereinfachten Komparators wird nicht nur auf die Viterbi-Entzerrung angewendet, sondern in einfacher Weise auch auf die Viterbi-Decodierung. Bei dem Vergleichs-/Auswahl-Vorgang von 2S in S gemäß der vorliegenden Erfindung nimmt die Summe der 2/1-Komparatoren aufgrund der Zunahme von S wie folgt zu.

Die maximale Anzahl von Schritten der 2/1-Komparatoren wird wie folgt erhalten.

Mit anderen Worten, der Schaltungsumfang ist proportional zu S(log2S)2 und die Verzögerung nimmt proportional zu (log2S)2 zu. Somit ist die Erfindung nach dem dritten Ausführungsbeispiel im Vergleich mit dem zweiten Ausführungsbeispiel vorteilhafter, wenn S zunimmt.


Anspruch[de]
Folgeschätzverfahren zum Schätzen einer übertragenen Signalfolge, die von einer Sendeseite übertragen wurde, unter Verwendung eines Listenausgangs-Viterbi-Algorithmus zum Bestimmen eines oder mehrerer Survivor für jeden Zustand eines Viterbi-Algorithmus, enthaltend einen oder mehr Zustände, durch Eingabe einer Charakteristik eines empfangenen Signals und eines Kanals, aufweisend einen Auswahlverarbeitungsschritt zum Auswählen von Survivorn höherer Ordnung anstelle des Sortierens in der Ordnung von Metriken, gekennzeichnet durch

einen Zweigmetrik-Berechnungsschritt zum Berechnen jeder von mehreren Zweigmetriken für jeden Zweig des Zustandsübergangs, der den Viterbi-Trellis bildet, durch Eingabe der empfangenen Signalfolge und ihrer Schätzsignalfolge, unter Verwendung eines Verfahrens zum Berechnen einer quadratischen Zweigmetrik &Ggr;k zu der Zeit k unter Verwendung der Formel wobei L die Speicherlänge des Kanals ist, rk das empfangene Signal ist, re k ein geschätzter Wert des empfangenen Signals ist, ci ein Anzapfkoeffizient des Kanals ist und I das übertragene Signal ist, und eines Verfahrens zum Berechnen einer modifizierten Zweigmetrik &Ggr;k zu der Zeit k unter der Verwendung der Formel wobei * eine komplexe Konjugation bezeichnet, einen Auswahlschritt zum Auswählen der quadratischen Zweigmetrik, wenn eine Leistung PB > eine Leistung PA ist, oder zum Auswählen der modifizierten Zweigmetrik, wenn PA > PB ist, worin wobei V die Speicherlänge des Trellis des Viterbi-Algorithmus ist; und

einen Pfadmetrik-Berechnungsschritt zum Berechnen des Pfadmetrikwertes für jeden Pfad, der den Viterbi-Trellis bildet, auf der Grundlage des für jeden Zweig ausgewählten Zweigmetrikwertes; wobei der Auswahlverarbeitungsschritt S Survivor höherer Ordnung auswählt anstelle des Sortierens in der Reihenfolge der Pfadmetrik nach der Auswahl von S Survivorn gemäß den Pfadmetrikwerten.
Folgeschätzverfahren nach Anspruch 1, bei dem der Auswahlverarbeitungsschritt weiterhin die Verringerung der Anzahl von Bits des Pfadmetrikwertes der Survivor aufweist. Folgeschätzvorrichtung zum Schätzen einer übertragenen Signalfolge, die von einer Sendeseite übertragen wurde, unter Verwendung eines Listenausgangs-Viterbi-Algorithmus zum Bestimmen eines oder mehrerer Survivor für jeden Zustand eines Viterbi-Algorithmus, enthaltend einen oder mehr Zustände, durch Eingabe einer Charakteristik eines empfangenen Signals und eines Kanals, aufweisend einen Auswahlprozessor (32) zum Auswählen von Survivorn höherer Ordnung anstelle des Sortierens in der Reihenfolge von Metriken, gekennzeichnet durch eine Zweigmetrik-Berechnungsvorrichtung (27, 28) zum Berechnen jeder von mehreren Zweigmetriken für jeden Zweig des Zustandsübergangs, der den Viterbi-Trellis bildet, durch Eingabe der empfangenen Signalfolge und ihrer Schätzsignalfolge, unter Verwendung eines Verfahrens zum Berechnen einer quadratischen Zweigmetrik &Ggr;k zu der Zeit k unter Verwendung der Formel wobei L die Speicherlänge des Kanals ist, rk das empfangene Signal ist, re k ein geschätzter Wert des empfangenen Signals ist, ci ein Anzapfkoeffizient des Kanals ist und I das übertragene Signal ist, und eines Verfahrens zum Berechnen einer modifizierten Zweigmetrik &Ggr;k zu der Zeit k unter Verwendung der Formel wobei * eine komplexe Konjugation bezeichnet, eine Auswahlvorrichtung (39-1) zum Auswählen der quadratischen Zweigmetrik, wenn eine Leistung PB > eine Leistung PA ist, und zum Auswählen der modifizierten Zweigmetrik, wenn PA > PB ist, worin wobei V die Speicherlänge des Trellis des Viterbi-Algorithmus ist; und

eine Pfadmetrik-Berechnungsvorrichtung (7) zum Berechnen des Pfadmetrikwertes für jeden Pfad, der den Viterbi-Trellis bildet, auf der Grundlage des für jeden Zweig ausgewählten Zweigmetrikwertes;

wobei der Auswahlprozessor (32) S Survivor höherer Ordnung auswählt anstelle des Sortierens in der Reihenfolge der Pfadmetrik nach der Auswahl von S Survivorn gemäß den Pfadmetrikwerten.
Folgeschätzvorrichtung nach Anspruch 3, bei der der Auswahlprozessor weiterhin die Verringerung der Anzahl von Bits des Pfadmetrikwertes der Survivor aufweist.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com