PatentDe  


Dokumentenidentifikation DE69921529T2 29.06.2006
EP-Veröffentlichungsnummer 0000946014
Titel Verfahren zur Detektion einer Symbolfolge aus einem empfangenen Signal, und Viterbi-Prozessor zur Durchführung des Verfahrens
Anmelder Eads Telecom, Montigny Le Bretonneux, FR
Erfinder Belveze, Fabrice, 78310 Maurepas, FR;
Chancel, Florence, 78000 Versailles, FR
Vertreter PRÜFER & PARTNER GbR, 81545 München
DE-Aktenzeichen 69921529
Vertragsstaaten CH, DE, FI, GB, LI
Sprache des Dokument FR
EP-Anmeldetag 22.03.1999
EP-Aktenzeichen 994006989
EP-Offenlegungsdatum 29.09.1999
EP date of grant 03.11.2004
Veröffentlichungstag im Patentblatt 29.06.2006
IPC-Hauptklasse H04L 1/00(2006.01)A, F, I, 20051017, B, H, EP
IPC-Nebenklasse H04L 25/03(2006.01)A, L, I, 20051017, B, H, EP   H03M 13/00(2006.01)A, L, I, 20051017, B, H, EP   

Beschreibung[de]

Die vorliegende Erfindung befindet sich auf den Bereich der digitalen Übertragungen.

Es wird die Übertragung einer Information von numerischer bzw. digitaler Natur betrachtet, d.h. unter der Form von Symbolen, die eine begrenzte Anzahl ND von Werten d0, ... dND-1 annehmen, und auf diskrete Weise im Verlauf der Zeit, es gibt daher eine Folge digitaler Symbole Dm (m = 0, 1, 2, ...), die zu einem definierten Alphabet {di, 0 ≤ i < ND} gehören.

Die Rolle des Detektors im Sinn der vorliegenden Erfindung ist es, ausgehend von einem Beobachtungssignal "Code", das auf der Ebene eines Empfängers verfügbar ist, Abschätzungen für aufeinanderfolgende Symbole Dm einer zu detektierenden Folge zu liefern. Der "Codierer", der dem Detektor das Beobachtungssignal liefert, das für die zu detektierende Folge steht, muss im allgemeinsten Sinne genommen werden: er kann als eine Black Box angesehen werden, die von dem Entwerfer entwickelt ist oder nicht. Er kann z.B. ein fehlerkorrigierender Codierer sein (in diesem Fall ist das Beobachtungssignal gleich einer digitalen Folge und der "Detektor" ist ein korrigierender Decodierer) oder eine Gesamtheit von korrigierendem Codierer – Modulator – Ausbreitungskanal – Demodulator (das Beobachtungssignal ist dann eine mit Fehler versehene numerische Folge), oder auch die einfachere Gesamtheit aus Modulator-Ausbreitungskanal (der "Detektor" ist dann ein Demodulator).

Der Detektor ist mit harten Eingängen ("hard inputs") versehen, wenn das Beobachtungssignal, das er bearbeitet, eine digitale Folge von Symbolen mit diskreten Werten ist, und mit weichen Eingängen ("soft inputs"), wenn das Beobachtungssignal eine Folge von abgetasteten und quantifizierten Werten ist oder von diskreten Abschätzungen, die mit jeweiligen Gewichtungen versehen sind, die das Vertrauen wiedergeben, das man in diese Abschätzungen hat.

Der Detektor ist mit weichen Ausgängen ("soft outputs") versehen, wenn die Symbolabschätzungen, die er liefert, mit jeweiligen Gewichtungen verbunden sind, die das Vertrauen darstellen, das man in diese Abschätzungen hat, und mit harten Ausgängen ("hard outputs"), wenn er einfach diskrete Abschätzungen liefert.

In wirklichen Übertragungssystemen ist es üblich, Signale zu verarbeiten, die ein Gedächtnis besitzen, d.h., dass das Signalsegment, das zu einem gegebenen Zeitpunkt die Information trägt, nicht nur von dieser Information zum selben Zeitpunkt abhängt, sondern auch von der vergangenen Information oder von den vergangenen Segmenten des Signals. Wenn dieses Gedächtnis bestimmte Eigenschaften verwirklicht, insbesondere die Tatsache, dass es ein Netzwerk gibt, das den Vorgang des Erzeugens des Beobachtungssignals beschreibt, dann kann der Empfänger die von dem Beobachtungssignal getragenen Informationssymbole im Sinn der maximalen Wahrscheinlichkeit entscheiden dank dem Viterbi-Algorithmus (s. G. D. Forney Jr., "The Viterbi algorithm", Proc. IEEE, Bd. 61, Nr. 3, März 1973, S. 268–278) oder dem MAP-Algorithmus (Maximum A Posteriori), der ebenfalls in dem Artikel von G. D. Forney dargelegt ist.

Verschiedene Versionen des MAP-Algorithmus sind in den folgenden Bezugsstellen beschrieben: K. Abend et B. D. Fritchman, "Statistical Detection for Communication Channels with Intersymbol Interference", Proc. IEEE, Bd. 58, Nr. 5, Mai 1970, S. 779–785; R. W. Chang et J. C. Hancock, "On Receiver Structures for Channels Having Memory", IEEE Trans. on Information Theory, Bd. IT-12 Nr. 4, Oktober 1966, S. 463–468; sowie L. R. Bahl u.a., "Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate", IEEE Trans, on Information Theory, Bd. IT-20, März 1974, S. 284–287.

Es kommt auch vor, dass die "Codierer" COD1, COD2, ..., CODN in den Übertragungssystemen (z.B. mehrere fehlerkorrigierende Codierer oder einer oder mehrere fehlerkorrigierende Codierer, denen ein Modulator und ein Ausbreitungskanal folgt), kaskadiert werden, oft mit Vorgängen der Zwischenverschachtelung. In diesem Fall (verkettetes System mit Gedächtnis) kann der betrachtete Empfänger aus einer Kaskade von elementaren Decodierern/Detektoren DECN, DECN-1, ..., DEC1 bestehen. Dieser Empfänger ist optimal im Sinn der maximalen Wahrscheinlichkeit, wenn die Decodierer/Detektoren DECp weiche Ausgänge (für p > 1) und weiche Eingänge aufweisen, wobei der Decodierer/Detektor (DECp (p > 1) jeder diskreten Abschätzung eines decodierten Symbols Dm der zu detektierenden Folge (diese Folge ist die von dem Codierer CODp-1 gelieferte) eine Gewichtung zuordnet, die durch die Wahrscheinlichkeit dargestellt wird, die gleich oder proportional ist dem Logarithmus des Verhältnisses zwischen der Wahrscheinlichkeit, dass das Symbol Dm der unbekannten Folge tatsächlich seiner durch die Decodierung gelieferten Abschätzung entspricht, und der Wahrscheinlichkeit, dass das Symbol Dm verschieden von seiner Abschätzung ist, wobei die in Frage stehenden Wahrscheinlichkeiten bedingte Wahrscheinlichkeiten sind mit der Kenntnis des verfügbaren Beobachtungssignals. In diesem Fall bilden die weichen Ausgänge jedes Decodierers/Detektors die "Beobachtungssignale" für den folgenden Decodierer/Detektor und die Information der Wahrscheinlichkeit geht nicht verloren.

Der Viterbi-Algorithmus hat den Vorteil, dass seine Verwirklichung durch eine Schaltung oder einen Prozessor keine großen Schwierigkeiten mit sich bringt, wobei die Einfachheit der ausgeführten Operationen gegeben ist: Multiplikationen, Additionen/Subtraktionen, Vergleiche. Außerdem ermöglicht es die Regelmäßigkeit des Netzwerks oft, Kunstgriffe der Programmierung oder der Speicherorganisation zu verwenden, die die Verwirklichung des Algorithmus weiter vereinfachen. Das erklärt, dass seine Verwendung heute in verschiedenen Kategorien von Detektoren sehr verbreitet ist. In seiner traditionellen Form liefert er jedoch nicht die Wahrscheinlichkeit der diskreten Abschätzungen, die er liefert, so dass er im Fall eines verketteten Systems mit Gedächtnis nicht die optimale Verarbeitung ermöglicht.

Dagegen liefert der MAP-Algorithmus wesensgemäß die Wahrscheinlichkeiten der Symbole, die er abschätzt, aber er stellt ernsthafte Implementierungsschwierigkeiten: exponentielle Berechnungen, Notwendigkeit, die Varianz des Rauschens zu kennen, Empfindlichkeit gegenüber Irrtümern über diese Varianz, Probleme der numerischen Analyse durch seine sehr kleinen Werte... .

Für die oben erwähnten verketteten Systeme mit Speicher wurden mehrere Verfahren zur Gewichtung der durch einen Viterbi-Detektor erzeugten Abschätzungen vorgeschlagen. Beispiele für diese Verfahren, die "SOVA" (Soft Output Viterbi Algorithm) genannt werden, sind:

  • • Ein Verfahren, das darin besteht, als Wahrscheinlichkeit eine Abschätzung des Unterschieds zwischen der auf der Ebene eines dieser Abschätzung entsprechenden Knotens des Netzwerks akkumulierten Metrik und der Metrik des besten Wegs, der einer anderen diskreten Abschätzung entspricht, zu nehmen (s. C. Berrou u.a., "A Low Complexity Soft-Output Viterbi Decoder Architecture", Proc. ICC'93, Genf, Mai 1993). Diese einfache Technik wird üblicherweise verwendet, ist aber sehr suboptimal;
  • • der Hagenauen-Algorithmus, beschrieben in J. Hagenauer, P. Hoeher, "A Viterbi Algorithm with Soft-Decision Outputs and its Applications", Proc. Globecom'89, Dallas, November 1989, S. 47.1.1–47.1.7;
  • • der Battail-Algorithmus, beschrieben in dem Amerikanischen Patent 4 328 582;
  • • der optimale (OSA) oder sub-optimale (SSA) SOVA, beschrieben in Y. Li, B. Vucetic, Y. Sato, "Optimum Soft-Output Detection for Channels with Intersymbol Interference", IEEE Trans. on Information Theory, Bd. IT-41, Nr. 3, Mai 1995, S. 704–713.

Außer dem OSA bringt jedes dieser Verfahren eine Verschlechterung der Leistungsfähigkeit im Hinblick auf den MAP-Algorithmus mit sich.

Die Algorithmen von Hagenauer, von Battail und von Li, Vucetic und Sato ähneln dem MAP darin, dass Berechnungen in dem Bereich von Wahrscheinlichkeiten ausgeführt werden. Somit schließen sie Berechnungen von Exponentialfunktionen ein, was ihr Verwirklichen mit Hilfe von Schaltungen oder Prozessoren wenig attraktiv macht, auch wenn die Exponentialfunktionen durch Annäherungen ersetzt sind.

Ein Hauptziel der vorliegenden Erfindung besteht darin, ein SOVA-Verfahren mit sinnvoller Komplexität vorzuschlagen, das eine Auswertung der Wahrscheinlichkeiten der durch einen Viterbi-Detektor abgeschätzten Symbole ermöglicht und das wenig Verschlechterung der Fehlerwahrscheinlichkeit im Hinblick auf den optimalen Fall des MAP-Algorithmus mit sich bringt.

Die Erfindung schlägt somit ein Verfahren zum Detektieren einer Folge diskreter Symbole ausgehend von einem Beobachtungssignal vor, dessen Erzeugung mit Hilfe eines Netzwerks aus NE Zuständen Ee (0 ≤ e < NE) und NB Zweigen Bb (0 ≤ b < NB) beschrieben werden kann, wobei jeder Zweig einen Ausgangszustand und einen Zielzustand unter den NE Zuständen aufweist und einem einzigartigen Q-plett von diskreten Symbolen zugeordnet ist, wobei Q eine ganze Zahl ist, die mindestens gleich 1 ist,

wobei das Netzwerk Pfade aufweist, die jeweils aus einer Abfolge von Zweigen gebildet sind, wobei jeder Pfad eine Metrik aufweist, die durch eine Summe der sich auf die ihn bildenden aufeinander folgenden Zweige beziehenden Elementarmetriken definiert ist und einer einzigen möglichen Folge von diskreten Symbolen zugeordnet ist, die durch die Abfolge der Q-pletts gebildet werden, denen jeweils die den Pfad bildenden aufeinander folgenden Zweige zugeordnet sind,

wobei das Beobachtungssignal in aufeinanderfolgenden Zeitsegmenten bearbeitet wird, wobei die für ein Segment n des Beobachtungssignals vorgenommene Bearbeitung aufweist:

  • • für jeden der NB Zweige Bb (0 ≤ b < NB) das Gewinnen einer Elementarmetrik, die einer Kombination des Segments n des Beobachtungssignals mit einem dem Zweig Bb zugeordneten Referenzsignal entspricht, und das Berechnen einer akkumulierten Zweigmetrik MBAb(n), indem die gewonnene Elementarmetrik zu einer akkumulierten Zustandsmetrik MEAe(n – 1) hinzugefügt wird, die sich auf den Ausgangszustand Ee des Zweigs Bb bezieht; und
  • • für jeden der NE Zustände Ee (0 ≤ e < NE) das Aktualisieren der akkumulierten Zustandsmetrik MEAe(n), die gleich einem Optimum der akkumulierten Zweigmetriken MBAb(n) angesetzt wird, die sich auf jene Zweige Bb beziehen, die den Zustand Ee als Zielzustand aufweisen, und das Abspeichern einer Kennung eines verbliebenen Zweigs, für den das Optimum erreicht ist,
wobei nach der Bearbeitung der aufeinanderfolgenden Segmente des Beobachtungssignals einer der NE Zustände Ee0 und ein optimaler Pfad &agr;opt des Netzwerks gewählt werden, der dadurch gebildet wird, dass die verbliebenen Zweige von dem gewählten Zustand aus wieder zusammengefügt werden, und mindestens ein diskretes Symbol Dm aus der zu detektierenden Folge durch den Wert eines entsprechenden Symbols der Folge abgeschätzt wird, der der gewählte optimale Pfad zugeordnet ist, und

wobei für jedes Symbol Dm der zu detektierenden Folge, das nach Auswahl eines Zustands Ee0 und eines optimalen Pfads &agr;opt abgeschätzt wird, eine minimale Differenz zwischen den Metriken des optimalen Pfad und eines konkurrierenden Pfads berechnet wird, der einer Folge zugeordnet ist, deren dem Symbol Dm entsprechendes Symbol einen anderen Wert als die für das Symbol Dm erhaltene Abschätzung aufweist, und die Wahrscheinlichkeit &Lgr;m der Abschätzung des Symbols Dm in Abhängigkeit von der berechneten minimalen Differenz der Metriken bestimmt wird.

Die Wahrscheinlichkeit &Lgr;m der Abschätzung eines Symbols Dm kann gleich oder proportional zu der für das Symbol Dm berechneten minimalen Differenz der Metriken angesetzt werden.

Die Erfinder haben (durch Simulation) festgestellt, dass das Detektionsverfahren Leistungsfähigkeiten aufweist, die dem MAP nahe kommen, was die Fehlerrate betrifft. Sein anderer Vorteil liegt darin, dass es dieselbe Art von einfachen Operationen verwendet wie der klassische Viterbi-Algorithmus (lediglich Additionen/Subtraktionen und Vergleiche). Seine Komplexität ist mit ihm vergleichbar: die Anzahl der zum Gewinnen der Wahrscheinlichkeiten erforderlichen Berechnungen ist annäherungsweise gleich der für den Viterbi-Algorithmus mit diskreten Ausgängen erforderlichen. Es hat jedoch den großen Vorteil, die Wahrscheinlichkeiten der Entscheidungen zu erzeugen. Man weiß, dass auf einem einfachen Gauss'schen Kanal eine Verbesserung bis fast 3 dB (für große Signalrauschverhältnisse) für jede Decodierstufe erzielt werden kann. Das Interesse, über ein solches Verfahren zu verfügen, ist somit groß.

Die angestrebten Anwendungen sind die Verkettungen der Dekodierung, darunter:

  • • eine Demodulation eines Systems mit Gedächtnis, die von einer Decodierung mit weichen Eingängen eines Faltungscodes (mit oder ohne Verschachtelung) oder eines Blockcodes gefolgt sein muss; das System mit Gedächtnis kann eine Übertragung auf einem Kanal mit Interferenz zwischen den Symbolen und/oder eine kontinuierliche Phasenmodulation (CPM: continuous phase modulation, von der GMSK: gaussian minimum shift keying ein Beispiel ist) oder eine lineare sein;
  • • zwei (oder mehrere) weiche Decodierungen verketteter Faltungscodes (mit oder ohne Vorhandensein von Verschachtelung zwischen den Codes); ein Anwendungsbeispiel in diesem Fall ist das Decodieren von Turbocodes; oder auch die weiche Decodierung eines Faltungscodes, gefolgt von einer weichen Decodierung eines Blockcodes;
  • • die weiche Decodierung eines Faltungscodes, gefolgt von einem Decodierer für Bilder oder Sprache, der die Qualität der (binären oder nichtbinären) decodierten Symbole kennen müsste, um die Qualität des wiederhergestellten Signals zu verbessern (Beispiel: Sprachdecodierer in einem Zellulärfunkkommunikationssystem vom Typ GSM);
  • • in einem System der Wiedererkennung von Formen (Wiedererkennung von Bildern, Buchstaben oder Sprache), das die Modulierung durch versteckte Markov-Ketten verwendet (und das daher im allgemeinen einen Viterbi-Algorithmus zum Fällen seiner Entscheidung verwendet) und das die Wahrscheinlichkeit der Entscheidung kennen muss (zum Beispiel um gerade keine Entscheidung zu treffen, wenn die Wahrscheinlichkeit eine bestimmte Schwelle nicht erreicht).

In einer bevorzugten Ausführungsform des Verfahrens wird während der Bearbeitungen, die für L0 + L1 aufeinanderfolgende Zeitsegmente n – r des Beobachtungssignals bis zu einem Segment n, n – L0 – L1 < n – r ≤ n, vorgenommen werden, wobei L0 eine positive ganze Zahl oder Null ist und L1 eine streng positive ganze Zahl ist, für jeden Zweig b, 0 ≤ b < NB, der Abstand &dgr;b(n – r) = |MBAb(n – r) – MEAe(n – r)| zwischen der akkumulierten Zweigmetrik MBAb(n – r) und der akkumulierten Zustandsmetrik MEAe(n – r) abgespeichert, der für den Zielzustand Ee des Zweigs Bb aktualisiert wurde. Nach der Bearbeitung der L1 aufeinander folgenden Segmente des Beobachtungssignals bis zu einem Segment n und bis zur Auswahl eines Zustands Ee0 wird zu einer rekursiven Berechnung auf der Grundlage der Metrikabstände übergegangen, die während der für die L0 + L1 vorhergehenden Segmente n – r, n – L0 – L1 < n – r ≤ n, durchgeführten Bearbeitung gespeichert wurden, um die minimale Metrikdifferenz im Hinblick auf jedes Symbol Dm zu bestimmen, das mit Hilfe der Folge abgeschätzt wurde, welcher der optimale Pfad zugeordnet ist, der durch erneutes Zusammenfügen der verbliebenen Zweige von dem ausgewählten Zustand aus bestimmt ist.

Unter diesen Umständen können nach der Bearbeitung von L1 aufeinanderfolgenden Segmenten des Beobachtungssignals bis zu einem Segment n und der Auswahl eines Zustands Q × L1 Symbole Dm abgeschätzt werden, die sich auf L1 vorhergehende Segmente n – r beziehen wie zum Beispiel n – L0 – L1 ≤ n – r < n – L0, und die jeweiligen Wahrscheinlichkeiten der Abschätzung dieser Q × L1 Symbole Dm bestimmt werden, wobei die Abschätzungen von Q Symbolen im Hinblick auf ein vorhergehendes Segment n – r jeweils durch die Werte des Q-pletts der Symbole gebildet werden, denen der (r + 1)-te verbliebene Zweig des optimalen Pfads zugeordnet ist, der durch erneutes Zusammenfügen von dem ausgewählten Zustand aus durchlaufen wurde.

Die Parameter L0 und L1 sind gemäß einem Kompromiss ausgewählt, der zwischen dem für das Durchführen des Verfahrens erforderlichen Speicherplatz und der Menge der durchzuführenden Berechnungen gesucht wird.

Sobald nach der Bearbeitung der L1 aufeinander folgenden Segmente des Beobachtungssignals bis zu einem Segment n ein Zustand Ee0 gewählt wurde, werden vorteilhafterweise Zustandsnoten Xe, die sich auf NE Zustände Ee (0 ≤ e < NE) beziehen, zu Xe = |MEAe(n) – MEAe0(n)| initialisiert, und dann werden für jeden Wert der ganzen Zahl r, die von 0 bis L0 + L1 – 1 läuft, die folgenden Operationen ausgeführt:

  • • die Auswahl des gespeicherten verbliebenen Zweigs Bb0 für den ausgewählten Zustand Ee0 während der für das Segment n – r ausgeführten Bearbeitung, gefolgt von der Aktualisierung des ausgewählten Zustands Ee0, der als Ausgangszustand des ausgewählten verbliebenen Zweigs BbC angesetzt wird;
  • • für jeden der NB Zweige Bb (0 ≤ b < NB) die Berechnung einer Zweignote Zb, indem der Zustandsnote Xe, die sich auf den Zielzustand Ee des Zweigs Bb bezieht, der Metrikabstand &dgr;b(n – r) hinzugefügt wird, der für den Zweig Bb gespeichert wurde;
  • • für jeden der NE Zustände Ee (0 ≤ e < NE), die Aktualisierung der Zustandsnote Xe, die gleich der kleinsten der Zweignoten Zb angesetzt wird, welche für jene Zweige Bb berechnet wurden, die den Zustand Ee als Ausgangszustand aufweisen;
  • • wenn r ≥ L0 ist: die Abschätzung von Q Symbolen der zu detektierenden Folge durch die Werte des Q-pletts von Symbolen, dem der ausgewählte verbliebene Zweig Bb0 zugeordnet ist; und
  • • wenn r ≥ L0 ist: für jede für eines der Q Symbole Dm erhaltene Abschätzung di die Bestimmung der minimalen Differenz der Metriken als kleinste der Zweignoten Zb, die für diejenigen Zweige Bb berechnet wurden, welche Q-pletts zugeordnet sind, deren dem Symbol Dm entsprechendes Symbol einen Wert dj aufweist, der sich von der Abschätzung di unterscheidet.

Ein weiterer Aspekt der vorliegenden Erfindung bezieht sich auf einen Viterbi-Prozessor, der ein Mittel zum Berechnen von Elementarmetriken und ein Mittel zur sequentiellen Verarbeitung enthält, die an das Durchführen des obigen Verfahrens angepasst sind. Ein solcher Viterbi-Prozessor kann insbesondere Teil eines Digitalsignaldemodulators oder auch eines Decodierers sein wie z.B. eines fehlerkorrigierenden Decodierers.

Die Erfindung wird besser verstanden beim Lesen der folgenden detaillierten Beschreibungen von nicht einschränkenden Ausführungsbeispielen mit Bezug auf die beigefügten Zeichnungen, in denen:

1 und 2 Darstellungen eines Beispiels für ein Netzwerk der Demodulierung und eines Beispiels für ein Netzwerk des fehlerkorrigierenden Detektierens sind;

3, die durch Aneinanderlegen der 3A, 3B und 3C untereinander gebildet wird, ein Organigramm eines Detektionsverfahrens gemäß der Erfindung ist;

4 und 5 synoptische Darstellungen eines Senders zur Funkkommunikation und eines entsprechenden Empfängers sind, die die Erfindung verwirklichen;

6 und 7 synoptische Darstellungen eines Senders für ein Digitalsignal und eines entsprechenden Empfängers sind, die die Erfindung verwirklichen; und

8 eine Grafik ist, die die Leistungsverbesserung zeigt, die durch das Verwirklichen der Erfindung in einem Beispiel eines digitalen Demodulators erzielt wird.

Ein Markov-Verfahren, das die Erzeugung eines Beobachtungssignals R ausgehend von einer Folge diskreter Symbole D0, D1, ..., Dm, ... modelliert, kann durch ein Netzwerk beschrieben werden, das NE Zustände Ee (0 ≤ e < NE) und NB elementare Zweige Bb (0 ≤ b < NB) aufweist. Jedes diskrete Symbol der Folge kann eine Anzahl ND von verschiedenen Werten d0, d1, ..., dND-1 annehmen. Jeder Zweig Bb hat einen Ausgangszustand EP(b) und einen Zielzustand ES(b) (0 ≤ P(b) < NE, 0 ≤ S(b) < NE), und er ist einem einzigen Q-plett von diskreten Symbolen didec(b, 0), ..., didec(b, Q-1), zugeordnet, wobei Q eine ganze Zahl ist, die mindestens gleich 1 ist. Jedem Paar, das durch einen Zustand Ee und ein Q-plett von Symbolen gebildet ist, entspricht ein einziger Zweig Bb, der diesem Q-plett zugeordnet ist und den Zustand Ee als Ausgangszustand hat (e = P(b)).

Zur Veranschaulichung zeigt 1 so ein Netzwerk mit NE = 3 Zuständen und NB = 12 Zweigen, bei dem der Ausgangszustand EP(b) eines Zweiges Bb als Index den Quotienten der euklidischen Teilung von b durch 4 hat (P(b) = b div 4), und der Zielzustand ES(b) eines Zweigs Bb als Index den Rest der euklidischen Teilung von b durch 3 hat (S(b) = b mod 3). Jeder Zweig Bb ist zwei Bit zugeordnet, die beispielsweise dem Rest der euklidischen Teilung von b durch 4 (b mod 4) entsprechen. In diesem Beispiel können die Symbole entweder quaternär sein (Q = 1, ND = 4, mit idec(b, 0) = b mod 4) oder binär (ND = 2, Q = 2, mit idec(b, q) = Bit des Gewichts 2q von b mod 4).

2 zeigt ein anderes Beispiel des Netzwerks mit NE = 4 Zuständen und NB = 8 Zweigen, bei dem P(b) = b div 2 und S(b) = b mod 4 ist. In diesem Beispiel sind die Symbole binär (ND = 2, Q = 1 mit idec(b, 0) = b mod 2).

Es wird ein Netzwerk dieser Art betrachtet, das über L Schritte ausgebildet ist bezogen auf L aufeinanderfolgende Zeitsegmente n des Beobachtungssignals R (0 ≤ n < L) entsprechend LxQ Symbolen der zu detektierenden Folge. Die aufeinanderfolgenden Segmente des Beoachtungssignals stellen eventuell Überlappungen dar. Jeder Pfad in dem Netzwerk, der aus einer Aufeinanderfolge von Zweigen Bb(0), Bb(1), Bb(L-1) besteht, so dass S[b(n-1)] = P[b(n)] für 0 < n < L – 1 ist, ist einer einzigen möglichen Folge von LxQ Symbolen zugeordnet, die aus einer Aufeinanderfolge der Q-pletts bestehen, denen jeweils die Zweige Bb(0), Bb(1), Bb(L-1) zugeordnet sind.

Das Netzwerk beschreibt die Erzeugung des Beobachtungssignals in dem Sinn, dass das Wahrscheinlichkeitsgesetz eines Segments n des Beobachtungssignals durch den Zweig Bb(n) festgelegt ist, der in dem entsprechenden Schritt n in dem Netzwerk beschritten wird, oder anders ausgedrückt durch den Ausgangszustand EP[b(n)], der ein gewisses Gedächtnis der vorausgehenden Symbole bewahrt und durch das Q-plett von Symbolen, dem der Zweig Bb(n) zugeordnet ist. Die Detektion gemäß der maximalen Wahrscheinlichkeit besteht von da aus darin, den optimalen Pfad in dem Netzwerk zu identifizieren, d.h. die Aufeinanderfolge von Zweigen, die die Wahrscheinlichkeit des Auftretens des aufgenommenen Beobachtungssignals maximiert. Die abgeschätzten Symbole werden dann aus der Folge herausgezogen, der dieser optimale Pfad zugeordnet ist.

Die Identifizierung des optimalen Pfades läuft auf eine Maximierung (bzw. je nach den verwendeten Konventionen Minimierung) einer entlang des Pfades angesammelten Metrik auf, die gleich einer Summe von Elementarmetriken ist, die für die aufeinander folgenden, den Pfad bildenden Zweige berechnet werden, wobei die Elementarmetriken über die probabilistischen Abhängigkeit zwischen den Segmenten des Beobachtungssignals und den Zweigen informieren.

Durch M(&agr;) sei die Metrik eines über L Schritte entwickelten Pfads &agr; des Netzwerks bezeichnet, durch CBb(n) die Gesamtheit der Pfade des Netzwerks, die im Schritt n den Zweig Bb durchlaufen, durch

die Gesamtheit von Pfaden des Netzwerks, die in dem Schritt N in dem Zustand Ee ankommen, und durch MEAe(n, &agr;), die Metrik eines Pfads &agr; aus CEe(n), die nur bis zu dem Schritt n angesammelt wurde.

Im folgenden wird der Fall betrachtet, in dem die für den Zweig Bb in dem Schritt n berechnete Elementarmetrik MBb(n) das Skalarprodukt RE(<sb|rn>) zwischen dem Segment n des Beobachtungssignals R (einem aus reellen oder komplexen mit rn bezeichneten Abtastwerten gebildeten Segment) und einem dem Zweig Bb zugeordneten reellen oder komplexen Referenzsignal sb ist, wobei die Referenzsignale sb so erstellt werden, dass eine Optimierung der Metriken eine Maximierung ist (es wäre eine Minimierung, wenn mit denselben Referenzsignalen sb als Elementarmetrik das Quadrat des euklidischen Abstands zwischen dem Segment rn und dem Referenzsignal sb festgehalten wird, d.h. ||rn – sb||2).

Der Viterbi-Algorithmus zieht Nutzen aus der Tatsache, dass der "beste" Pfad der Gesamtheit CEe(n), d.h. derjenige, der die Gesamtmetrik M(&agr;) über die L Schritte optimiert (in dem betrachteten Fall maximiert), auch die Metrik MEAe(n, &agr;) optimiert. Demzufolge reicht es, bei jedem Schritt n (wobei n von 0 bis L – 1 geht) für jeden Zustand Ee die akkumulierte Metrik:

sowie den Index surve(n) des Zweigs zu speichern, wobei der verbleibende Zweig, der den Zustand Ee als Zielzustand hat und für den die durch MBAb(n) = MEAP(b)(n – 1) + MBb(n) definierte angesammelte Zweitmetrik optimal ist:

Nach L Schritten wählt der Viterbi-Algorithmus den einen der NE Zustände und baut den optimalen Pfad auf, indem er die verbliebenen Zweige von diesem ausgewählten Zustand aus zurückverfolgt.

Der ausgewählte Zustand kann derjenige sein, für den die akkumulierte Zustandsmetrik MEAe(L – 1) optimal ist, wenn keine Grenzbedingung auferlegt ist. Er kann auch ein vorbestimmter Zustand sein, wenn die Folge mit bekannten Symbolen endet. In ähnlicher Weise hängt die Initialisierung des Algorithmus durch die Metrikwerte MEAe(–1) von der Kenntnis ab, die man a priori von dem Beginn der zu detektierenden Folge hat.

Durch MXe(n) wird nun die "beste" der Gesamtmetriken von Pfaden bezeichnet, die in dem Schritt n in dem Zustand Ee ankommen, und durch MZb(n) die "beste" der Gesamtmetriken der Pfade, die in dem Schritt n den Zweig Bb durchlaufen:

Durch

wird die Gesamtheit der Pfade des Netzwerks bezeichnet, die Folgen zugeordnet sind, bei denen das Symbol Dm an der Stelle m = nQ + q den Wert di (0 ≤ i < ND, 0 ≤ Q, 0 ≤ n < L) annimmt, und durch MDiq(n) die "beste" der Gesamtmetriken der Pfade der Gesamtheit CDiq(n):

Der klassische Viterbi-Algorithimus berechnet nicht die Größen MXe(n), MZb(n) und MDiq(n). Nichtsdestoweniger verläuft in jedem der Schritte n der optimale Pfad &agr;opt, den er bestimmt, durch den Zweig Bb0(n), der die Größe MZb(n) optimiert, und kommt in dem Zustand Ee0(n) an, der die Größe MXe(n) optimiert:

Die Wahrscheinlichkeit der Abschätzung di eines Symbols Dm = DnQ+q, die durch den Viterbi-Algorithmus gewonnen wird, ist proportional zu dem logarithmischen Verhältnis der bedingten Wahrscheinlichkeiten:

wobei &sgr;2 die Varianz des in dem Beobachtungssignal enthaltenen Rauschens ist.

Durch Annähern der Summen der Exponentialfunktionen durch die größte Exponentialfunktion, was Annäherungen sind, die sich in einem großen Maß im Zähler und im Nenner kompensieren, wird der Ausdruck (8) zu:

Wenn die abgeschätzten Symbole binär sind (ND = 2), kann man daher als Wahrscheinlichkeit der Abschätzung di des Symbols Dm die Größe:

oder eine proportionale Größe nehmen, wobei di' die Entscheidung ist, die von der erhaltenen Abschätzung di verschieden ist. Die Wahrscheinlichkeit könnte auch in einem nicht binären Fall (ND > 2) gemäß der Beziehung (10) berechnet werden, wobei di' dann die "beste" Entscheidung wäre, die von der erhaltenen Abschätzung di verschieden ist:

Die optimale Metrik M(&agr;opt) wird im Gegensatz zu der Metrik MDi'q(n) des derzeitigen Pfads durch den klassischen Viterbi-Algorithmus berechnet.

Um auf die Metrik MDi'q(n) des derzeitigen Pfades zuzugreifen, ist es möglich, auf die folgende Weise zu einer rekursiven Berechnung der Größen MXe(n) und MZb(n) überzugehen:

  • – bei jedem Schritt n des Durchlaufens des Netzwerks in der direkten Richtung: Speichern der Abweichung der Metriken &dgr;b(n) = |MBAb(n) – MEAS(b)(n)| = MEAS(b)(n) – MBAb(n) für jeden Zweig Bb (0 ≤ b < NB);
  • – nach dem Auswählen eines Zustands e0 in dem Schritt n: Gewinnen der Metriken MXe(n) = MEAe(n) für 0 ≤ e < NE);
  • – in jedem Schritt n – r des Durchlaufens des Netzwerks in der umgekehrten Richtung (r = 0, 1, ...), ausgeführt nach dem Auswählen eines Zustands in dem Schritt n: Berechnen der Metrik MZb(n – r) = MXS(b)(n – r) + &dgr;b(n – r) für jeden Zweig Bb (0 ≤ b < NB), anschließend Berechnen für 0 ≤ e < NE:

Man verfügt somit über die in Beziehung (4) definierten Metriken MZb(n), indem man einfach die Abweichungen &dgr;b(n) gespeichert hat (oder Größen, die es ermöglichen, sie leicht wiederzufinden) und indem eine begrenzte Anzahl von wenig komplexen Operationen (Additionen/Subtraktionen, Vergleiche) durchgeführt wurden. Ausgehend von den Metriken MZb(n) ist es leicht, entsprechend der Beziehung (5) die Metriken MDiq(n) abzuleiten, die Metriken MDi'q(n) der konkurrierenden Pfade für jedes abgeschätzte Symbol zu identifizieren und daher ein gutes Maß an Wahrscheinlichkeiten zu liefern.

Wenn es in einem nicht binären Fall (ND > 2) vorkommt, dass die derzeitigen Pfade, die zu unterschiedlichen Entscheidungen di' ≠ di'' führen, nahe beieinander liegende Metriken MDi'q(n) ≈ MDi''q(n) < MDiq(n) = M(&agr;opt) führen, besteht eine Option darin, die Annäherung der Wahrscheinlichkeit im Hinblick auf den Ausdruck (10) zu verbessern, indem ein Korrekturterm abgezogen wird. Im Extremfall, wenn die optimalen Metriken bezüglich aller möglichen Entscheidungen gleich sind (MDi'q(n) = MDi''q(n)∀i', i'' ≠ i), wird die kleinste Differenz der Metriken M(&agr;opt) – MDi'q(n) nach der Beziehung (9)

Der Korrekturterm kann proportional zu &sgr;2 sein (das somit abgeschätzt werden muss) mit einem Multiplikationsfaktor, der von (1/2)·ln(ND – 1) zu 0 abnimmt mit der Verteilung der Metriken der konkurrierenden Pfade.

Wenn das Durchführen des Viterbi-Algorithmus auf einer zu minimierenden Elementarmetrik gründet wie beispielsweise dem Quadrat des euklidischen Abstands, ist es selbstverständlich, dass die Maxima der Beziehungen (1) bis (7), (12) und (13) durch die Minima ersetzt werden müssen, die Abweichungen der Metriken &dgr;b(n) = MBAb(n) – MEAS(b)(n) sind und die Wahrscheinlichkeit &Lgr;m gemäß der Beziehung (10) wird: &Lgr;m = MDi'q(n) – M(&agr;opt) ≈ &sgr;2·LLRim(15)

3 zeigt ein Ausführungsbeispiel eines Verfahrens gemäß der Erfindung, in dem, um die Berechnungen weiter einzugrenzen, nicht explizit die Metriken MXe(n), MZb(n) (Beziehungen (3) und (4)) berechnet werden, sondern die Differenzen zwischen der Metrik M(&agr;opt) des gemäß dem Viterbi-Algorithmus bestimmten optimalen Pfades und diesen Metriken MXe(n), MZb(n).

Das durch 3 veranschaulichte Verfahren enthält für das direkte Durchlaufen des Netzwerks eine Hauptschleife mit dem Index n der Segmente des empfangenen Beobachtungssignals. Ein umgekehrtes Durchlaufen ("backtracking") wird in dem Netzwerk alle L1 Iterationen in dieser Schleife durchgeführt, wobei der erste umgekehrte Durchlauf am Ende der L0 + L1 ersten Iterationen durchgeführt wird. Die ganzzahligen Parameter L0 und L1 sind so gewählt, dass 1 ≤ L1 ≤ L und 0 ≤ L0 ≤ L – L1 gilt. Während des umgekehrten Durchlaufens, das am Ende der L0 + k × L1 ersten Iterationen (k ≥ 1) durchgeführt wird, werden die Abschätzungen der Symbole DQ·(k-1)·L1 bis DQ·k·L1-1 und die entsprechenden Wahrscheinlichkeiten berechnet.

Die Abweichungen der Metriken &dgr;b(n) und die verbliebenen Zweige surve(n) werden während L0 + L1 aufeinander folgenden Iterationen in der Schleife gespeichert, um für jedes umgekehrte Durchlaufen verfügbar zu sein. Die anderen berechneten Größen brauchen nur während der laufenden Iteration gespeichert zu werden (daher wird der Bezug auf n in den in 3 für diese Größen verwendeten Bezeichnungen weggelassen).

Die Anzahl L0 + L1 bestimmt somit die Größe des für die Berechnung der Wahrscheinlichkeiten erforderlichen Speichers. Im allgemeinen könnte L0 gleich der Tiefe des Abstutzens sein (in dem oben zitierten Artikel von G. D. Forney mit &dgr; bezeichnet), ausgehend von dem es sehr wahrscheinlich ist, dass alle verbliebenen Pfade zusammengewachsen sind. Ein großer Wert für L1 führt zu einer relativ großen Größe des Speichers, begrenzt aber die durchzuführenden Berechnungen. Im Grenzfall, wenn L1 = L ist (L0 = 0), wird das umgekehrte Durchlaufen nur einmal durchgeführt, wobei das Erhalten der Abweichungen der Metriken &dgr;b(n) über die gesamte Länge L des Netzwerks erforderlich ist. Umgekehrt grenzt ein kleiner Wert für L1 die Größe des Speichers ein, erfordert aber mehr Berechnungen. Im Grenzfall, wenn L1 = 1 ist, wird ein umgekehrter Durchlauf der Tiefe L0 + 1 ausgehend von n = L0 bei jeder Iteration durchgeführt, um nur Q Symbole auf einmal abzuschätzen.

In der Iteration n der Hauptschleife stellt MEAe (0 ≤ e < NE) die Zustandsmetrik MEAe(n – 1) dar, die bis zu dem Schritt n – 1 akkumuliert ist, und We stellt die akkumulierte Zustandsmetrik MEAe(n), die im Verlauf des Schritts n berechnet wird. Bevor zu einer neuen Iteration übergegangen wird (Initialisierung 11 durch n = 0 oder Inkrementieren des Index n im Schritt 13), werden die akkumulierten Zustandsmetriken MEAe in dem Schritt 10 oder 12 aktualisiert. Im Schritt 12 besteht das Aktualisieren einfach darin, MEAe = We für 0 ≤ e < NE zu nehmen. In dem Schritt 10 werden die Werte MEAe(–1) bezogen auf die Anfangsbedingungen angenommen. In dem in 3A dargestellten Beispiel gibt es a priori keine Kenntnis von dem Ausgangszustand, so dass die Metriken MEAe in dem Schritt 10 alle auf denselben Wert (0) initialisiert werden. Wenn der Ausgangszustand bekannt ist (z.B. weil der zu detektierenden Folge eines bekannte Synchronisationsfolge vorausgeht), kann man für diesen bekannten Zustand eine Anfangsmetrik zu 0 bestimmen und für die anderen Zustände beliebig kleine Metriken (–∞).

In jeder Iteration n wird damit begonnen, den Variablen We beliebig kleine Werte (–∞) zu geben und den Zweigindex b mit Ziffer 0 zu initialisieren (Schritte 14 und 15). Für jeden Wert von b wird in Schritt 16 die Elementarmetrik MB = MBb berechnet, in dem betrachteten Beispiel durch das Skalarprodukt zwischen dem Segment rn des Beobachtungssignals und dem dem Zweig Bb zugeordneten Referenzsignal sb. Im Schritt 17 wird die akkumulierte Zweigmetrik MBAb = MBAb(n) berechnet; indem die Elementarmetrik MB der akkumulierten Zustandsmetrik MEAP(b) bezogen auf den Ausgangszustand des Zweigs Bb hinzugefügt wird. Im Schritt 18 wird die oben berechnete akkumulierte Zweigmetrik MBAb mit der Variablen WS(b) verglichen. In Schritt 19 wird survS(b)(n) = b und WS(b) = MBAb nur dann genommen, wenn MBAb > We ist.

Dann wird der Zweigindex in Schritt 20 mit der Anzahl von Zweigen NB verglichen. Wenn b < NB – 1 ist, wird der Index b in dem Schritt 21 um eine Einheit erhöht, bevor zu Schritt 16 zurückgekehrt wird zum Verarbeiten des folgenden Zweigs.

Wenn in Schritt 20 b = NB – 1 ist, sind die neuen akkumulierten Zustandsmetriken in den Variablen We und die verbliebenen Zweige in den Variablen surve(n) gespeichert, die in dem Speicher gehalten werden. Der folgende Vorgang 22 ist das Speichern der Abweichungen der Metriken &dgr;b(n) = WS(b) – MBAb für jeden der Zweige Bb (0 ≤ b < NB).

Wenn n < L – 1 ist und wenn n nicht von der Form L0 + k × L1 – 1 ist, wobei k eine ganze Zahl ≥ 1 ist (Test 23), wird die Iteration n in der Hauptschleife durch Rückkehr zu den Schritten 12 und 13 beendet.

Ein umgekehrter Durchlauf wird in dem Netz durchgeführt, wenn der Test 23 zeigt, dass n = L0 + k × L1 – 1 ist (oder dass n = L – 1 ist).

Der umgekehrte Durchlauf beginnt in dem Schritt 24 (3B) mit der Auswahl eines Zustands Ee0.

Wenn a priori keine Kenntnis bezüglich des Endzustands vorliegt, ist der ausgewählte Zustand Ee0 derjenige, für den die Zustandsmetrik We0, die bis zu der Iteration n der Hauptschleife akkumuliert ist, maximal ist. In Schritt 25 werden jeweils für 0 ≤ e < NE Zustandsnoten Xe angesetzt, die gleich den Differenzen We0 – We sind, d.h. Xe = M(&agr;opt) – MXe(n). Wenn der Zustand am Ende der Folge bekannt ist (z.B. weil der zu detektierenden Folge eine bekannte Synchronisationsfolge folgt), dann ist es dieser bekannte Zustand Ee0, der in Schritt 24 bei der Enditeration n = L – 1 ausgewählt wird, wobei dann in Schritt 25 für diesen Zustand Ee0 eine Zustandsnote 0 angesetzt wird und für die anderen Zustände beliebig große Zustandsnoten angesetzt werden (was darauf hinausläuft, Xe = M(&agr;opt) – MXe(n) zu setzen, wenn die beliebig kleinen Elementarmetriken für die Zweige angesetzt sind, die am Ende der Folge zu einem anderen Zustand als Ee0 führen).

Der umgekehrte Durchlauf in dem Netzwerk enthält eine zweite Schleife, die durch eine ganze Zahl r indiziert ist, die von 0 bis L0 + L1 – 1 durchläuft. In jeder Iteration r dieser zweiten Schleife wird für jeden Zweig Bb (0 ≤ b < NB) eine Zweignote Zb = M(&agr;opt) – MZb(n – r) berechnet, und wenn r < L0 + L1 – 1 ist, werden für die folgende Iteration für 0 ≤ e < NE erneut Zustandsnoten Ye berechnet, die jeweils gleich M(&agr;opt) – MXe(n – r – 1) sind.

In der Iteration r dieser zweiten Schleife, die sich auf die Iteration n – r der Hauptschleife bezieht, bezeichnet die Größe Xe die Note des Zustands Ee, die in der Iteration r – 1 berechnet wurde (oder in dem Schritt 25 initialisiert wurde, wenn r = 0 ist) und gleich M(&agr;opt) – MXe(n – r) ist. Bevor zu einer neuen Iteration in dieser zweiten Schleife übergegangen wird, (Initialisierung 26 für r = 0 oder Inkrementierung des Index r im Schritt 28), werden die Zustandsnoten Xe in dem Zustand 25 bzw. 27 aktualisiert. In Schritt 27 besteht die Aktualisierung einfach darin, Xe = Ye anzusetzen.

Bei jeder Iteration r der Schleife des umgekehrten Durchlaufs wird damit begonnen, den verbliebenen Zweig Bb0 zu wählen, der für den ausgewählten Zustand Ee0 gespeichert ist, und dann wird ein neuer Zustand Ee0 gewählt, der dem Ausgangszustand Ep(b0) des ausgewählten verbliebenen Zweigs entspricht (Schritte 29 und 30). Den Variablen Ye (0 ≤ e < NE) werden beliebig große Werte (+∞) zugeordnet, und dann wird der Zweigindex b zu 0 initialisiert (Schritte 31 und 32). Für jeden Wert von b wird in Schritt 33 die Zweignote Zb berechnet, indem aus dem Speicher der Wert der Metrikabweichung &dgr;b(n – r) gelesen wird und der gelesene Wert der Note XS(b) des Zielzustands des Zweigs Bb hinzugefügt wird. In Schritt 34 wird die Variable YP(b) gleich der Zweignote Zb angesetzt, wenn Zb kleiner als der vorausgehende Wert dieser Variablen YP(b) ist, und in dem entgegengesetzten Fall unverändert gehalten. Der Zweigindex b wird dann in Schritt 35 mit der Anzahl von Zweigen NB in dem Netzwerk verglichen. Wenn b < NB – 1 ist, wird der Zweigindex b in Schritt 36 inkrementiert, bevor zur Berechnung der nächsten Zweignote zu Schritt 33 zurückgekehrt wird. Wenn in Schritt 35 b = NB – 1 ist, wird die Berechnung der Zweignoten Zb und der neuen Zustandsnoten Ye beendet. Wenn r < L0 und n < L – 1 ist (Test 37), wird die Iteration r in der Schleife des umgekehrten Durchlaufens durch Rückkehren zu den Schritten 27 und 28 beendet.

Anderenfalls (r ≥ L0 oder n = L – 1) geht man wie in 3C dargestellt zum Abschätzen der Symbole der Ränge m = Q × (n – r) bis m = Q × (n – r + 1) – 1 über und zur Berechnung der entsprechenden Wahrscheinlichkeiten.

Für jedes der Q abzuschätzenden Symbole, die durch den Index q bezeichnet sind (0 ≤ q < Q), wobei q in Schritt 39 zu 0 initialisiert wird), wird in Schritt 40 die Position m = Q × (n – r) + q bestimmt sowie der Index i des Schätzwerts di des Symbols Dm, der durch i = idec(b0, q) gegeben ist, wobei b0 der Index des in dem vorausgegangenen Schritt 29 ausgewählten verbliebenen Zweigs ist. Eine Entscheidungsnote &Dgr;j wird für jede der möglichen Entscheidungen dj (0 ≤ j < ND) auf einen beliebig großen Wert (+∞) initialisiert, und dann wird der Zweigindex b auf 0 initialisiert (Schritte 41 und 42). Für jeden Wert von b, bei dem der Zweig Bb zu einer Entscheidung dj für das Symbol vom Rang q führt (Schritt 43), wird die Zweignote Zb in Schritt 44 mit der Variablen &Dgr;j verglichen. Die Variable &Dgr;j wird mit der Zweignote Zb aktualisiert, wenn diese Note Zb kleiner als der vorige Wert dieser Variablen &Dgr;j ist, und anderenfalls unverändert beibehalten. In Schritt 45 wird der Zweigindex b mit der Anzahl der Zweige NB des Netzwerks verglichen. Wenn b < NB – 1 ist, wird der Zweigindex b in Schritt 46 vor dem Rückkehren zu Schritt 43 für die Verarbeitung des nächsten Zweiges inkrementiert. Wenn in Schritt 45 b = NB – 1 ist, wird die Berechnung der Entscheidungsnoten &Dgr;j beendet, und man erhält &Dgr;i = 0 und für j ≠ i &Dgr;j = M(&agr;opt) – MDjq(n – r).

Der Detektor kann also in Schritt 47 die Abschätzung D^m = di des Symbols Dm liefern sowie die zugeordnete Wahrscheinlichkeit &Lgr;m, die für j ≠ i gleich der kleinsten der Entscheidungsnoten &Dgr;j ist. Diese Wahrscheinlichkeit &Lgr;m entspricht der minimalen Differenz der Metriken zwischen dem optimalen Weg &agr;opt und dem "besten" konkurrierenden Weg bezogen auf das Symbol Dm, so wie siw in der Beziehung (10) definiert ist.

Wenn nicht alle Symbole bezogen auf die Iteration r des umgekehrten Durchlaufs abgeschätzt wurden (q < Q – 1 bei dem Test 48), wird der Index q in Schritt 49 vor dem Zurückkehren zu Schritt 40 inkrementiert. Wenn bei dem Test 48 q = Q – 1 ist, wird der Index r mit der Tiefe des umgekehrten Durchlaufs verglichen (Test 50). Wenn r < L0 + L1 – 1 ist, wird die Iteration r in der Schleife des umgekehrten Durchlaufens durch Rückkehr zu den Schritten 27 und 28 beendet.

Wenn r = L0 + L1 – 1 ist, wird der Index n der Iteration in der Hauptschleife in Schritt 51 mit der Länge L der Folge verglichen. Wenn n < L – 1 ist, wird die Iteration n durch Rückkehr zu den Schritten 12 und 13 beendet. Der Vorgang des Abschätzens der Symbole der Folge ist erreicht, wenn in Schritt 51 n = L – 1 ist.

Es ist anzumerken, dass das durch 3 dargestellte Abschätzungsverfahren gut geeignet ist für verschiedene Kunstgriffe der Programmierung, die es ermöglichen, seine Ausführung zu vereinfachen oder zu beschleunigen. Beispielsweise können die Verarbeitungen 1619, 3334 und 4344, die für verschiedene Zweige Bb des Netzwerks durchgeführt werden, ganz oder teilweise parallel durchgeführt werden. Andererseits kann es die Regelmäßigkeit des Aufbaus vieler verwendbarer Netzwerke (wie z.B. derjenigen aus 1 und 2) ermöglichen, das Verfahren in zahlreichen Fällen zu vereinfachen.

Vorteilhafterweise sind die Metrikabweichungen &dgr;b(n), die gespeichert werden müssen, in einer Speichereinheit abgelegt, die nach dem Modus zuletzt eingegeben – zuerst ausgegeben (LIFO) organisiert ist. Das ermöglicht es, den Mechanismus der Adressierung in dieser Speichereinheit für das Berechnungsorgan weitgehend zu vereinfachen, wenn nicht zu unterdrücken. In der Tat ist anzumerken, dass die Metrikabweichungen &dgr;b(n) in dem Speicher in Schritt 33 in der umgekehrten Reihenfolge gelesen werden als in der, in der sie in den Schritten 22 geschrieben worden sind. Das gilt auch für die Identifikationen surve(n) der verbliebenen Zweige.

4 und 5 veranschaulichen das Durchführen der Erfindung in einem Digitalsignaldemodulator.

4 zeigt schematisch einen Sender zur Funkkommunikation, der digitale Symbole ap übertragen soll. Ein Kanalcodierer 60 verarbeitet den digitalen Fluss {ap} entsprechend einem Redundanzcode, dessen Eigenschaften die Entdeckung und/oder Korrektur von Übertragungsfehlern ermöglichen. Eine Einheit 61 führt auf klassische Weise eine Verschachtelung der von dem Codierer 60 gelieferten Symbole durch, um die Leistungsfähigkeit des korrigierenden Codes beim Vorliegen von Übertragungsfehlern, die paketweise auftreten, zu verbessern. Der Modulator 62 empfängt die von der Verschachtelungseinheit 61 ausgegebenen Symbole Dm sowie eine vordefinierte Synchronisationsfolge. Es werden somit aufeinanderfolgende Rahmen des Digitalsignals gebildet, von denen jeder eine oder mehrere Synchronisationsfolgen und eine oder mehrere Folgen von Informationssymbolen Dm enthält.

Als Beispiel kann der Modulator 62 auf die Signalrahmen eine quaternäre kontinuierliche Phasenmodulation (CPM) mit dem Modulationsindex h = 1/3 anwenden mit einem Phasenpuls von einer Dauer, die gleich. vier Symbolzeiten ist. Eine solche Modulation kann durch ein Netzwerk wie das in 1 gezeigte beschrieben werden, wenn der Phasenpuls moduliert ist als beschränkt auf seine zentrale Symbolzeit in der Konzeption des Empfängers. (s. B. E. RIMOLDI, "A Decomposition Approach to CPM", IEEE Trans. on Information Theory, Bd. 34, Nr. 2, März 1988, S. 260–270).

Das Ausgangssignal des Modulators 62 wird in 63 in analoge Form gewandelt und dann über eine Stufe 64 in ein Funksignal. Das so ausgesendete Funksignal wird von einem Empfänger wie dem in 5 dargestellten empfangen, nachdem es einem Ausbreitungskanal gefolgt ist.

Der Empfänger in 5 enthält eine Funkstufe 66, die nach geeigneten Filterungen ein Basisbandsignal zurückgewinnt, das durch einen Wandler 67 digitalisiert wird. Das digitale Basisbandsignal ist ein komplexes Signal, das dem Demodulator 68 zugeführt wird, der einerseits eine Einheit 69 zur Synchronisation und Abschätzung des Kanals enthält und andererseits einen Viterbi-Prozessor 70.

Auf der Grundlage der von dem Sender in die Signalrahmen eingefügten Synchronisationsfolgen liefert die Einheit 69 dem Prozessor 70 die Synchronisationsinformation, die es ihm ermöglicht, die Segmente Rn des digitalen Basisbandsignals zu finden, das das Beobachtungssignal R bildet, das in dem Verfahren gemäß der Erfindung verwendet wird.

Die Einheit 69 geht auch zu einer Abschätzung der Antwort des Kanals über, um die Referenzsignale sb zu liefern, die beim Durchführen des Viterbi-Algorithmus verwendet werden. Bei fehlender Interferenz zwischen den Symbolen schätzt die Einheit 69 einfach eine komplexe Zahl ab, die die Dämpfung und die Phase wiedergibt, die durch den Kanal eingeführt werden, und multipliziert sie mit vordefinierten Impulsen, um die Referenzsignale sb zu liefern. Wenn eine Interferenz zwischen Symbolen berücksichtigt wird, wird eine Impulsantwort des Kanals durch die Einheit 69 abgeschätzt und mit vordefinierten Impulsen gefaltet, um die Referenzsignale sb zu bilden.

Der Viterbi-Prozessor 70 berechnet die Abschätzungen D^m der dem Modulator 62 des Senders zugeführten Symbole Dm und die entsprechenden Wahrscheinlichkeiten Am entsprechend dem oben dargestellten Verfahren. Die elementaren Zweigmetriken, die gemäß der Konvention als Skalarprodukt berechnet werden, können durch eine Bank von angepassten Filtern 71 des Prozessors 70 erzeugt werden, die das Basisbandsignal R empfangen und deren Koeffizienten durch die Referenzsignale sb definiert sind. Der Prozessor 70 enthält darüber hinaus eine Einheit zur sequentiellen Verarbeitung 72, die wie oben beschrieben die Berechnungen nach dem Viterbi-Algorithmus mit weichen Ausgängen (SOVA) durchführt, und eine Speichereinheit 73 vom Typ LIFO, in die die SOVA-Einheit 72 die Metrikabweichungen &dgr;b(n) und die Bezeichnungen surve(n) der verbliebenen Zweige schreibt und aus der sie diese liest.

Bei der betrachteten CPM-Modulation wird das Verfahren durchgeführt mit ND = 4, Q = 1, wenn der Kanalcodierer 60 quaternäre Symbole liefert, und mit ND = 2, Q = 2, wenn die Ausgangssymbole des Kanalcodierers 60 Bits sind.

Wie durch den Pfeil f in 5 symbolisiert, können die von der SOVA-Einheit 72 abgeschätzten Symbole in dem Fall, in dem die Veränderlichkeit des Ausbreitungskanals erfordert, dass er auf adaptive Weise abgeschätzt wird, als Rückwirkung der Einheit 69 zum Abschätzen des Kanals zugeführt werden.

Am Ausgang des Demodulators 68 führt eine Entschachtelungseinheit 75 eine Vertauschung der Symbole durch, die umgekehrt zu der von der Verschachtelungseinheit 61 des Senders durchgeführten ist, und liefert die weichen Abschätzungen der entschachtelten Symbole an den Kanaldecodierer 76, der zu dem Codierer 60 dual ist. Die Tatsache, dass der Decodierer 76 weiche Eingänge aufweist, ermöglicht es, in den Abschätzungen âp der von dem Sender übertragenen Symbole ap einen beträchtlichen Zugewinn bezüglich der Fehlerrate zu erzielen. Der Decodierer 76 kann harte Ausgänge aufweisen. Er kann auch weiche Ausgänge aufweisen (in diesem Fall kann er insbesondere die Erfindung durchführen), wenn eine Information über die Wahrscheinlichkeit in der weiteren Verarbeitung der decodierten Symbole nützlich ist.

6 und 7 zeigen eine andere Anwendung der Erfindung in einer digitalen Übertragungskette.

6 zeigt einen Sender für ein Digitalsignal, der zwei Codierstufen enthält. Ein erster Codierer 80 oder "interner Codierer" empfängt die zu übertragenen Symbole ap. Nach einer Verschachtelung durch eine Einheit 81 werden die von dem internen Codierer 80 gelieferten Symbole Dm einem zweiten Codierer oder "externen Codierer" 82 zugeführt. Der Fluss der durch den externen Codierer 82 gelieferten Symbole wird auf einen Übertragungskanal geschickt, der von einer beliebigen Natur sein kann (er kann insbesondere beispielsweise wie mit Bezug auf 4 und 5 beschrieben einen Modulator, einen Ausbreitungskanal und einen Demodulator enthalten; er kann auch einen Speicher enthalten, in dem die übertragene Informationen während einer mehr oder weniger langen Zeitspanne gespeichert ist).

Der externe Codierer 82 verarbeitet den Digitalfluß {Dm} entsprechend einem Redundanzcode, dessen Eigenschaften das Entdecken und/oder Korrigieren von Übertragungsfehlern ermöglicht. Der interne Codierer kann ebenfalls ein Redundanzcodierer sein (die zwei Stufen 80, 82 wenden also einen Produktcode oder Turbocode an).

Zur Veranschaulichung kann der externe Codierer 82 gemäß einem Faltungscode arbeiten, für den es üblich ist, ihn vermittels des Viterbi-Algorithmus zu decodieren. Es ist beispielsweise der Faltungscode CC(2, 1, 3) mit einem Wirkungsgrad 1/2 und einer Belastungslänge 3, in welchem Fall das Decodiernetzwerk das in 2 dargestellte sein kann.

Der in 7 dargestellte Empfänger empfängt von dem Übertragungskanal das Beobachtungssignal R, das in aufeinander folgende überlappende Segmente rn aufgeteilt ist. In dem angesprochenen Beispiel des Faltungscodes CC(2, 1, 3) deckt jedes Segment rn 6 sechs Bit des gesendeten Signals ab. Wenn der Übertragungskanal durch einen Demodulator wie der Demodulator 68 von 5 abgeschlossen ist, entspricht jeder Abtastwert des Beobachtungssignals R einem reellen Wert, dessen Vorzeichen die Abschätzung eines Ausgangsbits des externen Codierers 82 darstellt und dessen Absolutwert der zugeordneten Wahrscheinlichkeit entspricht.

Der externe Decodierer 84 des Empfängers von 7 enthält eine Einheit 85 zur Berechnung der Elementarmetriken MBb(n) eine Einheit 86 zur sequentiellen Verarbeitung SOVA und eine Speichereinheit 87 vom Typ LIFO, um die Metrikabweichungen &dgr;b(n) und die Angaben surve(n) der verbliebenen Zweige aufzunehmen. Jedes Referenzsignal sb besteht aus sechs Bits mit Vorzeichenwert ±1, die zwei dem Ausgangszustand Es(b) entsprechenden Bits und dem dem Zweig Bb entsprechenden Bit (d.h. b mod 2) entsprechen. Diese sechs vorzeichenbehafteten Bits werden mit den Abtastwerten jedes Segments rn multipliziert und dann von der Einheit 85 addiert, um die Elementarmetriken MBb(n) zu liefern. Die SOVA-Einheit 86 arbeitet nach der oben beschriebenen Weise, um die Abschätzungen D^m der Eingangsbits Dm des externen Codierers 82 und die entsprechenden Wahrscheinlichkeiten &Lgr;m zu liefern.

Diese Abschätzungen und Wahrscheinlichkeiten werden von einer Einheit 88 entschachtelt, die die umgekehrte Vertauschung durchführt wie die der Einheit 81 des Senders. Der interne Decodierer 89, dual zu dem internen Codierer 80, kann also die erforderliche Decodierung durchführen mit harten oder weichen Entscheidungen ap, indem er von der Wahrscheinlichkeitsinformation &Lgr;m an seinen weichen Eingängen profitiert. Daraus resultiert eine Verbesserung der globalen binären Fehlerrate.

In einer anderen Ausführung ist der interne Codierer 80 ein Sourcecodierer. In diesem Fall bearbeitet er nicht einen Fluss von Symbolen ap, sondern ein zu codierendes Signal (Audio, Video, ...). Es ist beispielsweise ein Sprachcodierer. Der zugeordnete Decodierer 89 könnte die Wahrscheinlichkeitsinformation &Lgr;m in Abhängigkeit von der Art der durch die betroffenen Bits übertragenen Information auswerten. Für bestimmte Parameter eines Sourcecodierers kann es beispielsweise vorzuziehen sein, eine Extrapolation auf der Grundlage von vorher empfangenen Parametern durchzuführen, statt einen neuen Parameterwert anzunehmen, dem eine geringe Wahrscheinlichkeit zugeordnet ist.

8 zeigt die Ergebnisse, die durch Simulieren eines Beispiels eines Übertragungssystems gemäß 4 und 5 gewonnen wurden, wobei der Kanalcodierer 60 einen Faltungscode CC(2, 1, 3) auf Binärsymbole ap anwendet, die Einheit 61 eine Verschachtelung in Blöcken der Größe (20, 14) anwendet; der Modulator 62 eine quaternäre CPM mit Index h = 1/3 anwendet; der Demodulator 68 die quaternären Symbole (ND = 4, Q = 1) abschätzt, indem er die Wahrscheinlichkeiten nach der Beziehung (10) auswertet ausgehend von einem Netzwerk nach 1; und der Decodierer 76 gemäß dem klassischen Viterbi-Algorithmus mit weichen Eingängen und harten Ausgängen arbeitet. Andererseits führt der Demodulator 68 zwei Demodulationen durch, die eine vom Anfang des Rahmens zu dem Ende hin und die andere von dem Ende des Rahmens zu dem Anfang hin, und der Decodierer 76 stellt die Decodierung der so gewonnenen zwei Serien von gewichteten Abschätzungen sicher, um schließlich den Satz von Symbolen ap auszuwählen, der der Gegenstand der kleinsten Anzahl von Fehlerkorrekturen auf dem Rahmen ist (vgl. EP-A-0 821 500). Die Kurven in 8 wurden gewonnen durch Simulieren eines Rayleigh-Kanals mit einem flachen Schwund mit einer Doppelfrequenz gleich dem 2,6 × 10–3-fachen der Frequenz der Symbole. Die Kurve I zeigt die Binärfehlerrate BFR, die abhängig von dem Signalrauschverhältnis SRV beim Durchführen der Erfindung beobachtet wurde. Die Kurve II zeigt dieselbe Größe, die in dem Fall gewonnen wurde, in dem die Wahrscheinlichkeiten &Lgr;m nicht verwendet wurden, wobei der Kanaldecodierer 76 mit harten Eingängen versehen ist. Die durch die Erfindung erreichte beträchtliche Verbesserung ist erkennbar in der Größenordnung von 3 dB des Signalrauschverhältnisses für eine binäre Fehlerrate von 10–2, was zeigt, dass die Leistungsfähigkeit des Verfahrens nahe der des MAP liegt.


Anspruch[de]
  1. Verfahren zum Detektieren einer Folge diskreter Symbole aus einem Beobachtungssignal (R), dessen Erzeugung mit Hilfe eines Netzwerks aus NE Zuständen Ee, 0 ≤ e < NE, und NB Zweigen Bb, 0 ≤ b < NB, beschrieben werden kann, wobei jeder Zweig einen Ausgangszustand und einen Zielzustand unter den NE Zuständen aufweist und einem einzigen Q-Plett von diskreten Symbolen zugeordnet ist, wobei Q eine ganze Zahl ist, die mindestens gleich 1 ist,

    wobei das Netzwerk Pfade aufweist, die jeweils aus einer Abfolge von Zweigen gebildet sind, wobei jeder Pfad eine Metrik aufweist, die durch eine Summe der sich auf die ihn bildenden aufeinanderfolgenden Zweige beziehenden Elementarmetriken definiert ist und einer einzigen möglichen Folge von diskreten Symbolen zugeordnet ist, die durch die Abfolge der Q-pletts gebildet wird, denen jeweils die den Pfad bildenden aufeinanderfolgenden Zweige zugeordnet sind,

    wobei das Beobachtungssignal in aufeinanderfolgenden Zeitsegmenten bearbeitet wird, wobei die für ein Segment n des Beobachtungssignals vorgenommene Bearbeitung enthält:

    – für jeden der NB Zweige Bb, 0 ≤ b < NB, das Gewinnen einer Elementarmetrik, die einer Kombination des Segments n des Beobachtungssignals mit einem dem Zweig Bb zugeordneten Referenzsignal entspricht, und das Berechnen einer akkumulierten Zweigmetrik MBAb(n), indem die gewonnene Elementarmetrik zu einer akkumulierten Zustandsmetrik MEAe(n – 1) hinzugefügt wird, die sich auf den Ausgangszustand Ee des Zweigs Bb bezieht; und

    – für jeden der NE Zustände Ee, 0 ≤ e < NE, das Aktualisieren der akkumulierten Zustandsmetrik MEAe(n), die gleich einem Optimum der akkumulierten Zweigmetriken MBAb(n) angesetzt wird, die sich auf jene Zweige Bb beziehen, die den Zustand Ee als Zielzustand aufweisen, und das Abspeichern einer Kennung eines verbliebenen Zweigs, für den das Optimum erreicht ist,

    wobei nach der Bearbeitung der aufeinanderfolgenden Segmente des Beobachtungssignals einer der NE Zustände Ee0 und ein optimaler Pfad &agr;opt des Netzwerks gewählt werden, der dadurch gebildet wird, dass die verbliebenen Zweige von dem gewählten Zustand aus wieder zusammengefügt werden, und mindestens ein diskretes Symbol Dm aus der zu detektierenden Folge durch den Werts eines entsprechenden Symbols der Folge abgeschätzt wird, der der gewählte optimale Pfad zugeordnet ist, und

    wobei eine Wahrscheinlichkeit &Lgr;m der Abschätzung jedes Symbols Dm ermittelt wird,

    dadurch gekennzeichnet,

    dass für jedes Symbol Dm der zu detektierenden Folge, das nach Auswahl eines Zustands Ee0 und eines optimalen Pfads &agr;opt abgeschätzt wird, eine minimale Differenz zwischen den Metriken des optimalen Pfads und eines konkurrierenden Pfads berechnet wird, der einer Folge zugeordnet ist, deren dem Symbol Dm entsprechendes Symbol einen anderen Wert als die für das Symbol Dm erhaltene Abschätzung aufweist, und

    dass die Wahrscheinlichkeit &Lgr;m der Abschätzung des Symbols Dm in Abhängigkeit von der berechneten minimalen Differenz der Metriken bestimmt wird.
  2. Verfahren nach Anspruch 1, bei dem die Wahrscheinlichkeit &Lgr;m der Abschätzung des Symbols Dm gleich oder proportional zu der für das Symbol Dm berechneten minimalen Differenz der Metriken angesetzt wird.
  3. Verfahren nach Anspruch 1 oder 2, bei dem, wenn das Symbol Dm eine Zahl ND der möglichen Werte d0, ..., dND-1 aufweist, die größer ist als zwei, ND-1 Metrikdifferenzen berechnet werden, die sich auf ND-1 mögliche, sich von der für das Symbol Dm erhaltenen Abschätzung di unterscheidende Werte beziehen, wobei die Metrikdifferenz &Dgr;j, die sich auf einen Wert dj, 0 < j < ND, j ≠ i, bezieht, gleich der Differenz zwischen der Metrik M(&agr;opt) des optimalen Pfads und der Metrik MDjq (n) eines konkurrierenden sich auf den Wert dj beziehenden Pfads ist, der eine optimale Metrik unter all den Pfaden zeigt, die Folgen zugeordnet sind, deren dem Symbol Dm entsprechendes Symbol den Wert dj aufweist, und die minimale Differenz der Metriken für das Symbol Dm derart bestimmt ist, dass sie die kleinste der ND – 1 Metrikdifferenzen ist, die sich auf die Werte dj, 0 ≤ j < ND, j ≠ i, beziehen.
  4. Verfahren nach Anspruch 3, bei welchem die Wahrscheinlichkeit &Lgr;m der Abschätzung des Symbols Dm gleich oder proportional zu der minimalen Metrikdifferenz verringert um einen Term angesetzt wird, der von der Streuung der ND – 1 Metrikdifferenzen abhängt, die sich auf die Werte dj, 0 ≤ j < ND, j ≠ i, beziehen.
  5. Verfahren nach einem der Ansprüche 1 bis 4, bei dem

    während der Bearbeitungen, die für L0 + L1 aufeinanderfolgende Zeitsegmente n – r des Beobachtungssignals bis zu einem Segment n, n – L0 – L1 < n – r ≤ n, vorgenommen werden, wobei L0 eine positive ganze Zahl oder Null ist und L1 eine streng positive ganze Zahl ist, für jeden Zweig b, 0 ≤ b < NB, der Abstand &dgr;b(n – r) = |MBAb(n – r) – MEAe(n – r)| zwischen der akkumulierten Zweigmetrik MBAb(n – r) und der akkumulierten Zustandsmetrik MEAe(n – r) abgespeichert wird, der für den Zielzustand Ee des Zweigs Bb aktualisiert wurde, und

    nach der Bearbeitung der L1 aufeinander folgenden Segmente des Beobachtungssignals bis zu einem Segment n und bis zur Auswahl eines Zustands Ee0 zu einer rekursiven Berechnung auf der Grundlage der Metrikabstände übergegangen wird, die während der für die L0 + L1 vorhergehenden Segmente n – r, n – L0 – L1 < n – r ≤ n, durchgeführten Bearbeitung gespeichert wurden, um die minimale Metrikdifferenz im Hinblick auf jedes Symbol Dm zu bestimmen, das mit Hilfe der Folge abgeschätzt wurde, welcher der optimale Pfad zugeordnet ist, der durch erneutes Zusammenfügen der verbliebenen Zweige von dem ausgewählten Zustand aus bestimmt ist.
  6. Verfahren nach Anspruch 5, bei dem

    nach der Bearbeitung von L1 aufeinanderfolgenden Segmenten des Beobachtungssignals bis zu einem Segment n und der Auswahl eines Zustands Q × L1 Symbole Dm abgeschätzt werden, die sich auf L1 vorhergehende Segmente n – r beziehen wie zum Beispiel n – L0 – L1 ≤ n – r < n – L0, und

    die jeweiligen Wahrscheinlichkeiten der Abschätzung dieser Q × L1 Symbole Dm bestimmt werden,

    wobei die Abschätzungen von Q Symbolen, die sich auf ein vorhergehendes Segment n – r beziehen, jeweils durch die Werte des Q-pletts der Symbole gebildet werden, denen der (r + 1)-te verbliebene Zweig des optimalen Pfads zugeordnet ist, der durch erneutes Zusammenfügen von dem ausgewählten Zustand aus durchlaufen wurde.
  7. Verfahren nach Anspruch 6, bei dem

    sobald nach der Bearbeitung der L1 aufeinander folgenden Segmente des Beobachtungssignals bis zu einem Segment n ein Zustand Ee0 gewählt wurde, Zustandsnoten Xe, die sich auf NE Zustände Ee, 0 ≤ e < NE, beziehen, zu Xe = |MEAe(n) – MEAe0(n)| initialisiert werden und dann für jeden Wert der ganzen Zahl r, die von 0 bis L0 + L1 – 1 läuft, die folgenden Operationen ausgeführt werden:

    – die Auswahl des gespeicherten verbliebenen Zweigs Bb0 für den ausgewählten Zustand Ee0 während der für das Segment n – r ausgeführten Bearbeitung, gefolgt von der Aktualisierung des ausgewählten Zustands Ee0, der als Ausgangszustand des ausgewählten verbliebenen Zweigs Bb0 angesetzt wird;

    – für jeden der NB Zweige Bb, 0 ≤ b < NB, die Berechnung einer Zweignote Zb, indem der Zustandsnote Xe, die sich auf den Zielzustand Ee des Zweigs Bb bezieht, der Metrikabstand &dgr;b(n – r) hinzugefügt wird, der für den Zweig Bb gespeichert wurde;

    – für jeden der NE Zustände Ee, 0 ≤ e < NE, die Aktualisierung der Zustandsnote Xe, die gleich der kleinsten der Zweignoten Zb angesetzt wird, welche für jene Zweige Bb berechnet wurden, die den Zustand Ee als Ausgangszustand aufweisen;

    – wenn r ≥ L0 ist: die Abschätzung von Q Symbolen der zu detektierenden Folge durch die Werte des Q-pletts von Symbolen, dem der ausgewählte verbliebene Zweig Bb0 zugeordnet ist; und

    – wenn r ≥ L0 ist: für jede für eines der Q Symbole Dm erhaltene Abschätzung di die Bestimmung der minimalen Differenz der Metriken als kleinste der Zweignoten Zb, die für diejenigen Zweige Bb berechnet wurden, welche Q-pletts zugeordnet sind, deren dem Symbol Dm entsprechendes Symbol einen Wert dj aufweist, der sich von der Abschätzung di unterscheidet.
  8. Verfahren nach einem der Ansprüche 5 bis 7, bei dem die Abstände der Metriken &dgr;b(n – r) in Speichereinrichtungen abgespeichert werden, die nach dem LIFO-Modus („last in – first out") ausgebildet sind.
  9. Viterbi-Prozessor zum Erfassen einer Folge diskreter Symbole aus einem Beobachtungssignal (R), dessen Erzeugung mit Hilfe eines Netzwerks aus NE Zuständen Ee, 0 ≤ e < NE, und NB Zweigen Bb, 0 ≤ b < NB, beschrieben werden kann, wobei jeder Zweig einen Ausgangszustand und einen Zielzustand unter den NE Zuständen aufweist und dabei einem einzigen Q-plett von diskreten Symbolen zugeordnet ist, wobei Q eine ganze Zahl ist, die mindestens gleich 1 ist,

    wobei das Netzwerk Pfade aufweist, die jeweils aus einer Abfolge von Zweigen gebildet sind, wobei jeder Pfad eine Metrik besitzt, die durch eine Summe der sich auf die ihn bildenden aufeinanderfolgenden Zweige beziehenden Elementarmetriken definiert ist und einer einzigen möglichen Abfolge von diskreten Symbolen zugeordnet ist, welche durch die Abfolge der Q-plett gebildet wird, denen jeweils die aufeinander folgenden Zweige zugeordnet sind, welche den Pfad bilden,

    wobei er Recheneinrichtungen (71; 85) zum Berechnen der Elementarmetriken enthält, wobei jede Elementarmetrik MBb(n) einer Kombination aus einem Zeitsegment n des Beobachtungssignals und einem Referenzsignal entspricht, das einem der NB Zweige Bb zugeordnet ist, sowie Einrichtungen (72; 86) zur sequentiellen Bearbeitung des Beobachtungssignals mit aufeinander folgenden Zeitsegmente, die so ausgebildet sind, dass für jedes Segment n des Beobachtungssignals eine Bearbeitung vorgenommen wird, welche folgendes enthält:

    – für jeden der NB Zweige Bb, 0 ≤ b < NB, das Berechnen einer akkumulierten Zweimetrik MBAb(n), indem die von der Einrichtung zur Berechnung von Elementarmetriken gelieferte Elementarmetrik MBb(n) zu einer akkumulierten Zustandsmetrik MEAe(n – 1) hinzugefügt wird, die sich auf den Ausgangszustand Ee des Zweigs Bb bezieht; und

    – für jeden der NE Zustände Ee, 0 ≤ e < NE, das Aktualisieren der akkumulierten Zustandsmetrik MEAe(n), die gleich einem Optimum der akkumulierten Zweigmetriken MBAb(n) angesetzt wird, die sich auf jene Zweige Bb beziehen, die den Zustand Ee als Zielzustand aufweisen, und das Abspeichern einer Kennung eines verbliebenen Zweigs, für den das Optimum erreicht ist,

    wobei die Einrichtungen zur sequentiellen Bearbeitung in der Weise ausgebildet sind, dass einer der NE Zustände Ee0 und ein optimaler Pfad &agr;opt des Netzwerks gewählt werden, nachdem die aufeinander folgenden Zweige des Beobachtungssignals bearbeitet wurden, wobei der optimale Pfad &agr;opt dadurch gebildet wird, dass die verbliebenen Zweige von dem gewählten Zustand aus wieder zusammengefügt werden, mindestens ein diskretes Symbol Dm aus der zu detektierenden Folge durch den Werts eines entsprechenden Symbols der Folge abgeschätzt wird, der der gewählte optimale Pfad zugeordnet ist, und eine Wahrscheinlichkeit &Lgr;m der Abschätzung jedes Symbols Dm ermittelt wird,

    dadurch gekennzeichnet, dass die Einrichtungen zur sequentiellen Bearbeitung so ausgebildet sind,

    dass sie für jedes Symbol Dm der zu detektierenden Folge, das nach Auswahl eines Zustands Ee0 und eines optimalen Pfads &agr;opt abgeschätzt wird, eine minimale Differenz zwischen den Metriken des optimalen Pfads und einem konkurrierenden Pfad berechnen, der einer Folge zugeordnet ist, deren dem Symbol Dm entsprechendes Symbol einen anderen Wert als die für das Symbol Dm erhaltene Abschätzung aufweist, und

    dass sie die Wahrscheinlichkeit &Lgr;m der Abschätzung des Symbols Dm in Abhängigkeit von der minimalen kleinstmöglichen Differenz zwischen der Metriken bestimmen.
  10. Viterbi-Prozessor nach Anspruch 9, bei welchem die Einrichtungen zur sequentiellen Bearbeitung (72; 86) die Wahrscheinlichkeit &Lgr;m der Abschätzung des Symbols Dm gleich oder proportional zu der für das Symbol Dm berechneten minimalen Differenz der Metriken bestimmen.
  11. Viterbi-Prozessor nach Anspruch 9 oder 10,

    der Speichereinrichtungen (73; 87) aufweist, in denen die Einrichtungen zur sequentiellen Bearbeitung (72; 86) während der Bearbeitungen, die für L0 + L1 aufeinanderfolgende Zeitsegmente n – r des Beobachtungssignals bis zu einem Segment n, n – L0 – L1 < n – r ≤ n, vorgenommen werden, für jeden der NB Zweige Bb, 0 5 b < NB, den Abstand &dgr;b(n – r) = |MBAb(n – r) – MEAe(n – r)| zwischen der akkumulierten Zweigmetrik MBAb(n – r) und der akkumulierten Zustandsmetrik MEAe(n – r) aufzeichnen, der für den Zielzustand Ee des Zweigs Bb aktualisiert wurde, wobei L0 eine positive ganze Zahl oder Null ist und L1 eine streng positive ganze Zahl ist,

    und bei dem die Einrichtungen zur sequentiellen Bearbeitung so ausgebildet sind, dass sie nach der Bearbeitung der L1 aufeinander folgenden Segmente des Beobachtungssignals bis zu einem Segment n und bis zur Auswahl eines Zustands Ee0 zu einer rekursiven Berechnung auf der Grundlage der Metrikabstände übergehen, die in der Speichereinrichtung aufgezeichnet wurden, um die minimale Metrikdifferenz im Hinblick auf jedes Symbol Dm zu bestimmen, das mit Hilfe der Folge abgeschätzt wurde, welcher der optimale Pfad zugeordnet ist, der durch erneutes Zusammenfügen der verbliebenen Zweige von dem ausgewählten Zustand aus bestimmt ist.
  12. Viterbi-Prozessor nach Anspruch 11, bei dem die Einrichtungen zur sequentiellen Bearbeitung

    nach der Bearbeitung von L1 aufeinander folgenden Segmenten des Beobachtungssignals bis zu einem Segment n und der Auswahl eines Zustands Q × L1 Symbole Dm abschätzen, die sich auf L1 vorhergehende Segmente n – r beziehen wie zum Beispiel n – L0 – L1 ≤ n – r < n – L0, und

    die jeweiligen Wahrscheinlichkeiten der Abschätzung dieser Q × L1 Symbole Dm bestimmen, wobei die Abschätzungen von Q Symbolen, die sich auf ein vorhergehendes Segment n – r beziehen, jeweils durch die Werte des Q-pletts der Symbole gebildet werden, denen der (r + 1)-te verbliebene Zweig des optimalen Pfads zugeordnet ist, der durch erneutes Zusammenfügen von dem ausgewählten Zustand aus durchlaufen wurde.
  13. Viterbi-Prozessor nach Anspruch 12, bei dem die Einrichtungen zur sequentiellen Bearbeitung (72; 86), sobald sie nach der Bearbeitung von L1 aufeinander folgenden Segmenten des Beobachtungssignals bis zu einem Segment n einen Zustand Ee0 ausgewählt haben, Zustandsnoten Xe, die sich auf NE Zustände Ee, 0 ≤ e < NE, beziehen, zu Xe = |MEAe(n) – MEAe0(n)| initialisieren und dann für jeden Wert der ganzen Zahl r, die von 0 bis L0 + L1 – 1 läuft, die folgenden Operationen ausführen:

    – die Auswahl des gespeicherten verbliebenen Zweigs Bb0 für den ausgewählten Zustand Ee0 während der für das Segment n – r ausgeführten Bearbeitung, gefolgt von der Aktualisierung des ausgewählten Zustands Ee0, der als Ausgangszustand des ausgewählten verbliebenen Zweigs Bb0 angesetzt wird;

    – für jeden der NB Zweige Bb, 0 ≤ b < NB, die Berechnung einer Zweignote Zb, indem der Zustandsnote Xe, die sich auf den Zielzustand Ee des Zweigs Bb bezieht, der Abstand der Metriken &dgr;b(n – r) hinzugefügt wird, der für den Zweig Bb gespeichert wurde;

    – für jeden der NE Zustände Ee, 0 ≤ e < NE, die Aktualisierung der Zustandsnote Xe, die gleich der kleinsten der Zweignoten Zb angesetzt wird, welche für jene Zweige Bb berechnet wurden, die den Zustand Ee als Ausgangszustand besitzen;

    – wenn r > L0 ist: die Abschätzung von Q Symbolen der zu detektierenden Folge durch die Werte des Q-pletts von Symbolen, dem der ausgewählte verbliebene Zweig Bb0 zugeordnet ist; und

    – wenn r ≥ L0 ist: für jede für eines der Q Symbole Dm erhaltene Abschätzung di die Bestimmung der minimalen Differenz der Metriken als kleinste der Zweignoten Zb, die für diejenigen Zweige Bb berechnet wurden, welche Q-pletts zugeordnet sind, deren dem Symbol Dm entsprechendes Symbol einen Wert dj aufweist, der sich von der Abschätzung di unterscheidet.
  14. Viterbi-Prozessor nach einem der Ansprüche 11 bis 13, bei dem die Speichereinrichtungen (73; 87) nach dem LIFO-Modus („last in – first out") ausgebildet sind.
  15. Demodulator für ein Digitalsignal mit

    Einrichtungen zur Abschätzung des Kanals (69), um ausgehend von einem Beobachtungssignal (R) Referenzsignale (sb) zu bestimmen, die jeweils NB Zweigen (Bb) eines Netzwerks zugeordnet sind, und

    einem Viterbi-Prozessor (70) nach einem der Ansprüche 9 bis 14, der die Bezugssignale und das Beobachtungssignal empfängt, das in aufeinanderfolgende Segmente (rn) unterteilt ist, und der Abschätzungen (D^m) von diskreten Symbolen vornimmt, die von einem Modulator (62) bearbeitet wurden, sowie Wahrscheinlichkeiten (&Lgr;m) ermittelt, die diesen Abschätzungen jeweils zugeordnet sind.
  16. Dekodierer für ein Digitalsignal mit einem Viterbi-Prozessor (84) nach einem der Ansprüche 9 bis 14, der ein in aufeinanderfolgende Segmente (rn) unterteiltes Beobachtungssignal (R) empfängt und Abschätzungen (D^m) von diskreten Symbolen erzeugt, die von einem Codierer (82) bearbeitet wurden, sowie Wahrscheinlichkeiten (&Lgr;m) ermittelt, die diesen Abschätzungen jeweils zugeordnet sind.
Es folgen 6 Blatt Zeichnungen






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

  Patente PDF

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