DE60122200T2

DE60122200T2 - Stopkriterien für interative dekodierung

Info

Publication number: DE60122200T2
Application number: DE60122200T
Authority: DE
Inventors: Ba-Zhong Irvine SHEN; B. Kelly Irvine CAMERON; T. Steven Irvine JAFFE
Original assignee: Broadcom Corp
Current assignee: Broadcom Corp
Priority date: 2000-11-06
Filing date: 2001-11-02
Publication date: 2007-08-23
Anticipated expiration: 2021-11-03
Also published as: WO2002037691A2; DE60122200D1; US6982659B2; US6518892B2; US20020196165A1; US20040140915A1; AU2002225857A1; US20020067294A1; WO2002037691A3; US6686853B2; EP1334561A2; EP1334561B1

Description

Die vorliegende Erfindung bezieht sich auf ein Verfahren zum Beenden eines Vorgangs eines iterativen Decodierens und auf eine Vorrichtung zum Erzeugen eines Stopkriteriums für einen iterativen Decoder.
Kanalcodierung hat in letzter Zeit größeres Interesse hervorgerufen. Zum Beispiel lautet ein kürzlicher maßgeblicher Text:
"Kanalcodierung bezieht sich auf die Klasse von Signalumwandlungen, welche dafür ausgebildet sind, Kommunikationsleistung zu verbessern, indem ermöglicht wird, dass die übertragenen Signale den Auswirkungen von verschiedenen Kanalbeeinträchtigungen, wie Rauschen, Interferenz und Fading besser widerstehen. Diese Signal-verarbeitenden Verfahren können als Mittel zum Erreichen wünschenswerter Systemkompromisse betrachtet werden (zum Beispiel Fehlerverhalten gegenüber Bandbreite, Energie gegenüber Bandbreite). Warum nehmen Sie an, dass Kanalcodierung ein derart beliebtes Verfahren geworden ist, um diese vorteilhaften Auswirkungen zu erbringen? Die Verwendung von hochintegrierten Schaltkreisen (LSI = Large-Scale Integrated Circuits) und von Hochgeschwindigkeitsverarbeitungsverfahren für digitale Signale (DSP = Digital Signal Processing) haben es möglich gemacht, durch diese Verfahren soviel wie 10 dB Leistungsverbesserung zu liefern, mit viel geringeren Kosten als durch die Verwendung der meisten anderen Verfahren, wie Sender mit höherer Leistung oder größere Antennen." Aus "Digital Communications" Fundamentals and Applications Second Edition by Bernard Sklar, Seite 305 ^© 2000 Prentice Hall PTR.
Es gibt mehrere moderne Decodierverfahren, welche iterative wahrscheinlichkeitstheoretische Decodierverfahren einsetzen. Unter der Liste an iterativen wahrscheinlichkeitstheoretischen Verfahren sind Verfahren wie MAP Decodierung, Soft Output Viterbi Decodierung und andere. Wegen der Verwendung von iterativen Decodierverfahren besteht auf dem Gebiet ein Bedarf für verbesserte iterative Decodierverfahren.
In der Veröffentlichung "Two simple stopping criteria for turbo decoding" von Shao R. et al. in IEEE Transactions on Communications, IEEE Inc. New York, USA, Vol. 47, Nr. 8, August 1999, Seiten 1117–1120, XP000848102, ISSN: 0090-6778 ist das CE Kriterium für ein Beenden des Iterationsvorgangs bei Turbodecodierung beschrieben.
In der Veröffentlichung "Signature analyzers in built-in self test circuits: a perspective" von Rajashekhara T. N. in Proceedings of the 1990 IEEE Southern Tier Technical Conference (Katalognr. 90TH0313-7), Binghampton, NY, USA, 25. April 1990, Seiten 275–281, XP010010765, 1990, New York, NY, USA, IEEE, USA sind Signatur-Analyse-Einheiten in Schaltungen mit eingebautem Selbsttest beschrieben. Signatur-Analyse ist ein Komprimierungsverfahren, welches auf dem Konzept zyklischer Redundanzüberprüfung basiert und in Hardware verwertet wird, welche lineare Feedback-Schieberegister verwenden.
Die vorliegende Erfindung stellt ein Verfahren zum Beenden eines Vorgangs eines iterativen Decodierens eines Decoders gemäß dem Gegenstand des unabhängigen Patentanspruchs 1 und eine Vorrichtung zum Erzeugen eines Stopkriteriums für einen iterativen Decoder gemäß dem Gegenstand des unabhängigen Patentanspruchs 4 bereit. Vorteilhafte Ausführungsformen der Erfindung sind in den abhängigen Ansprüchen definiert.
Ein Verfahren zum Erzeugen eines Stopkriteriums für einen iterativen Decoder wird beschrieben. Das Verfahren schließt ein Ermitteln der Varianz (VAR_k) extrinsischer Information zu einer k-ten Wiederholung des iterativen Decoders und ein Anhalten des Decoders ein, wenn VAR_k < T₁, wobei T₁ ein erster Schwellwert und D_k (differentielle Varianz) < T₂, wobei T₂ ein zweiter Schwellwert ist.
In einer Ausführungsform der Erfindung wird ein Verfahren zum Ermitteln eines Schwellwerts T₁ für eine bestimmte Codierung beschrieben. Das Verfahren schließt ein Auswählen eines Wertes für E_b/N₀, ein Erzeugen eines Signals mit der bestimmten Codierung, ein Hinzufügen eines Rauschvektors zu dem Signal, um ein verschlechtertes Signal zu erzeugen, ein iteratives Decodieren des verschlechterten Signals, bis die Iteration konvergiert und ein Zuordnen eines Wertes kleiner als VAR_k zu T₁ ein.
Die Merkmale, Ausführungsformen und Vorteile der vorliegenden Erfindung, welche in der obigen Zusammenfassung beschrieben worden sind, sind unter Bezugnahme auf die folgende Beschreibung, die angefügten Ansprüche und Zeichnungen besser zu verstehen, worin:
1 eine graphische Darstellung einer Umgebung ist, in welcher Ausführungsbeispiele der vorliegenden Erfindung arbeiten können.
2 ein Blockdiagramm eines Modells eines Datenübertragungssystems darstellt.
3 ein Blockdiagramm einer Simulation des in 2 erläuterten Übertragungssystems darstellt.
4 ein Blockdiagramm eines Teils eines Decoders gemäß einem Ausführungsbeispiel der Erfindung darstellt.
5 eine graphische Darstellung von Tabelle 1 bis Tabelle 3 ist, welche die Beziehung zwischen Decodieriterationen und Bitfehlern erläutert.
6 ein Blockdiagramm einer Signaturschaltung gemäß einem Ausführungsbeispiel der Erfindung darstellt.
7 eine graphische Darstellung von Tabelle 4 bis Tabelle 7 ist, welche die Beziehung zwischen Decoder-Iterationen, Signatur-Stopkriterien, Varianz-Kriterien und Decodierfehlern erläutert.
8 einen Graphen zeigt, welcher die Bitfehlerrate (BER = Bit Error Rate) gegenüber E_b/N₀ für verschiedene Stopkriterien darstellt.
Ausführliche Beschreibung der Ausführungsbeispiele der Erfindung
1 ist eine graphische Darstellung einer Umgebung, in welcher Ausführungsbeispiele der vorliegenden Erfindung arbeiten können. Die bei 101 abgebildete Umgebung ist ein Datenverteilungssystem, wie es in einem Kabelfernsehen-Verteilungssystem aufgefunden werden kann.
In 1 werden Daten an das Übertragungssystem durch eine Informationsquelle 103 geliefert. Zum Zwecke der Erläuterung kann die in 1 abgebildete Informationsquelle als eine Systemkopfstelle für Kabelfernsehen angesehen werden, welche Videodaten zu Endverbrauchern liefert. Ausführungsbeispiele der Erfindung sind nicht auf irgendeine Art von Informationsquelle begrenzt und jede andere Datenquelle könnte äquivalent eingesetzt werden. Ein Formatierer 105 nimmt Daten von der Informationsquelle 103 an. Die von der Informationsquelle 103 gelieferten Daten können analoge oder digitale Signale wie (aber nicht begrenzt auf) Videosignale, Audiosignale, und Datensignale aufweisen. Der Formatierblock 105 formatiert empfangene Daten zu einer geeigneten Form, wie die bei 107 abgebildeten Daten. Die formatierten Daten 107 werden dann an den Kanalcodierer 109 geliefert. Der Kanalcodierer 109 codiert die an ihn gelieferten Daten 107. In einigen Ausführungsbeispielen der vorliegenden Erfindung kann der Kanalcodierer 109 ein Codieren bereitstellen, welches abhängig von unterschiedlichen Zielen des speziellen Systems unterschiedlich ausgebildet ist. Zum Beispiel kann das Codieren verwendet werden, um das Signal stabiler zu machen, um die Fehlerwahrscheinlichkeit zu reduzieren, um das System mit einem geringeren Verbrauch von Übertragungsenergie zu betreiben oder um ein effizienteres Decodieren des Signals zu ermöglichen.
Der Kanalcodierer 109 liefert codierte Daten an einen Sender 111. Der Sender 111 überträgt die von dem Kanalcodierer 109 gelieferten codierten Daten zum Beispiel unter Verwendung einer Antenne 113. Das von der Antenne 113 gesendete Signal wird von einem Relaysatelliten 115 empfangen und dann wieder zu einer terrestrischen Empfangsantenne gesendet, wie die Erdstationsantenne 117. Die Erdstationsantenne 117 erfasst das Satellitensignal und liefert das erfasste Signal an einen Empfänger 119. Der Empfänger 119 verstärkt und demoduliert/detektiert das Signal, wie angemessen, und liefert die detektierten Signale an einen Decoder 121.
Der Decoder 121 kehrt im Wesentlichen den Prozess des Kanalcodierers 109 um und stellt die Daten 123 wieder her, welche eine gute Schätzung der Daten 107, welche gesendet worden waren, darstellen sollten. Der Decoder 121 kann eine Vorwärts-Fehlerkorrektur (FEC = Forward Error Correction) verwenden, um Fehler in dem empfangenen Signal zu korrigieren. Die von dem Decoder gelieferten Daten 123 werden dann an eine Formatiereinheit 125 geliefert, welche die empfangenen Daten für eine Verwendung durch eine Informationssenke vorbereitet, wie das bei 127 dargestellte Fernsehen.
2 zeigt ein Blockdiagramm, welches ein Modell eines Übertragungssystems erläutert. In 2 werden Daten 203 an einen Codierer 205 geliefert. Der Codierer 205 kann, abhängig von der Anwendung, unterschiedliche Arten von Codierung bereitstellen. Zum Beispiel kann der Codierer 205 ein Trellis-Codierer, ein parallel verknüpfter Codierer (PCE = Parallel Concatenated Encoder), ein Paritätsüberprüfungscodierer mit niedriger Dichte (LDPC = Low Density Parity Check) oder eine Vielfalt von anderen Arten von Codierern sein. Nachdem die Daten von dem Codierer 205 codiert worden sind, werden die codierten Daten an einen Kanal 207 geliefert. Der Kanal 207 weist eine Kanalsteuerung, das tatsächliche Kanalmedium und einen Kanalempfänger auf. Der Kanal 207 kann eine Vielfalt von verschiedenen Arten von Kanalmedien aufweisen, wie, aber nicht begrenzt durch, Funk- oder Glasfasermedien.
In dem Übertragungssystem-Modell empfängt der Kanal 207 auch eine Eingabe von einem Rauschblock 209. Der Rauschblock 209 kann eine Vielfalt von unterschiedlichen Arten von Rauschen von verschiedenen Quellen aufweisen. Das auf dem Kanal 207 eingebrachte Rauschen dient einer Verschlechterung des von dem Decoder 205 gelieferten codierten Signals. Das Ergebnis des Hinzufügens von Rauschen 209 zu dem Kanal 207 ist ein verschlechtertes Datensignal 211, welches eine Kombination von codierten Daten und hinzugefügtem Rauschen darstellt. Das verschlechterte Datensignal 211 wird an den Decoder 213 geliefert. Der Decoder 213 versucht das verschlechterte Datensignal zu decodieren und die ursprünglichen Daten 203 wiederherzustellen. Der Decoder 213 liefert eine Datenausgabe 215.
Das Übertragungssystem von 2 ist ein Modell eines realen Kommunikationskanals. Der bei 213 abgebildete Decoder ist ein Decodertyp, welcher als ein "iterativer" Decoder bekannt ist. Der Decoder 213 ist ein iterativer Decoder, da er die Ausgabedaten bei 215 erzeugt, indem er die empfangenen Daten und das empfangene Rauschen mehrere Male verarbeitet, d.h., er führt mehrere Wiederholungen über die Daten durch. Der Decoder 213 nimmt mehrere iterative Durchgänge durch die empfangenen Daten vor, wobei er eine Schätzung der übertragenen Daten oder eine andere Wahrscheinlichkeitsmetrik berechnet, welche mit der Verlässlichkeit der in jedem nachfolgenden Durchgang erzeugten Verlässlichkeit der Datenschätzung, verbunden ist.
Ein iteratives Decodieren kann verwendet werden, um verschiedene Arten von Codierung probabilistisch zu decodieren, indem Schätzungen der Daten erfolgreich verfeinert werden. In einer derartigen iterativen Decodierung kann eine erste Iterationsschätzung einen Startpunkt für eine zweite Iterationsschätzung liefern etc. In derartigen Typen von iterativem Decodieren werden Datenschätzungen, zum Beispiel in der Form von Wahrscheinlichkeiten oder Entfernungsmetriken, von einer Iteration zu der nächsten weitergegeben und erfolgreich verfeinert und hoffentlich verbessert. Die Ausgabe von einer Datenverarbeitungsiteration wird die Eingabe an die nächste Verarbeitungsiteration.
Verschiedene Arten von Codes sind empfänglich für den iterativen Decodiertyp. Zum Beispiel können serielle und parallele verknüpfte Codes, auch als serielle und parallele Turbo-Codes bekannt, iterativ decodiert werden. Zusätzlich können Produkt-Codes, Paritätsüberprüfungscodes mit geringer Dichte (LDPC = Low Density Parity Check Codes), Reed Solomon Codes, Graph-Codes, und Belief Propagation Codes iterativ decodiert werden. Die hierin beschriebenen Verfahren können mit all den zuvor genannten Codes verwendet werden.
Beispiele des Erfindungsgedankens werden hierin über die Verwendung von parallelen verknüpften (Turbo-)Codes erläutert. Fachleute werden erkennen, dass das gleiche iterative Decodierverfahren, welches zur Erläuterung auf Turbo-Codes angewendet wird, auch genauso gut auf andere iterative Decodierverfahren angewendet werden kann. Die Verwendung von Turbo-Codes, um Ausführungsbeispiele der Erfindung zu erläutern, wurde aus Gründen der Einfachheit gewählt, als ein Beispiel, mit welchem der Fachmann wahrscheinlich vertraut ist. Jedoch besteht nicht die Absicht, den hierin beschriebenen Erfindungsgedanken auf Turbo-Codes oder eines der oben genannten Beispiele für iterative Codes zu beschränken. Die hierin beschriebenen und erläuterten Konzepte sind gleichermaßen auf jedes iterative Decodierverfahren anwendbar.
3 zeigt ein Blockdiagramm einer Simulation des in 2 erläuterten Übertragungssystems. Die Simulation von 3 wird verwendet, um hierin beschriebene iterative Decodierverfahren zu erläutern, zu untersuchen und zu quantifizieren. Die Simulation von 3 kann vollständig auf einem Computer programmiert sein, oder Teile davon können in vielfältigen Formen realisiert sein. Zum Beispiel kann der Decoder 313 ein tatsächlicher Hardware-Decoder oder eine Softwaresimulation sein. Um die Erklärung einfach zu gestalten, wird die Simulation 301 als eine vollständige Softwaresimulation behandelt.
Die Eingangsdaten 303 können mehrere Datenblöcke aufweisen. Die Eingangsdaten 303 für die Softwaresimulation können in einer Computerdatei enthalten sein und somit sind die Datenwerte bekannt. Die Daten 303 werden an den Codierer 305 geliefert, welcher die Daten codiert. Ein Rauschvektor 309 wird zu den codierten Daten in dem Addierer 307 addiert. Da der Rauschvektor 309 ein simulierter Rauschvektor ist, kann der Umfang der zu dem codierten Signal hinzugefügten Verschlechterung durch ein Steuern des Wertes des hinzugefügten Rauschvektor gesteuert werden. Das Ergebnis der Addition der codierten Daten und des Rauschvektors 309 in dem Addierer 307 ist ein verschlechtertes Datensignal 311. Der Rausch- und Datenvektor 311 kann dann von einem Decoder 313 decodiert werden. Ausführungsbeispiele der Erfindung können innerhalb des Decoders 313 arbeiten und können das Decodieren der Daten innerhalb des Decoders 313 steuern. Wiederholungen des Decoders 313 können an jedem Punkt unterbrochen werden, um die Effektivität des Ausführungsbeispiels der Erfindung, welche das Decodieren steuert, zu analysieren.
Die Ausgabe des Decoders 313 ist ein Datenblock 315. Der Datenblock 315 kann mit den Originaldaten 303 in einer Vergleichseinheit 317 verglichen werden und die Ergebnisse von jeder Zahl von Iterationen in einer Ergebnisdatei 319 zur Analyse gespeichert werden.
Durch Verwendung der Simulation von 3 können Ausführungsbeispiele der Erfindung getestet und analysiert werden. In der gesamten vorliegenden Beschreibung werden Testergebnisse, welche über die Verwendung von zu der in 3 erläuterten Simulation äquivalenten Simulationen erreicht wurden, verwendet, um verschiedene Ausführungsformen und Ausführungsbeispiele der vorliegenden Erfindung zu erläutern.
4 stellt ein Blockdiagramm eines Teils eines iterativen Decoders gemäß einem Ausführungsbeispiel der Erfindung dar. In 4 wird ein beispielhaftes Decodiersystem für parallele verknüpfte (Turbo-)Codes erläutert, wobei ein derartiger Decoder innerhalb des Decodierblockes 313 von Ausführungsbeispielen der Erfindung gesteuert werden kann. 4 nimmt an, dass der Codierer 305 ein (Turbo-)Codierer ist.
In 4 weist der Decoder 313 zwei Soft-in Soft-out (SISO) Komponentendecoder 403 und 405 auf. Derartige Decoder können einen MAP(= Maximum A Posteriori)-Algorithmus implementieren und daher kann der Decoder auch alternativ als ein MAP Decoder oder ein MAP Turbo-Decoder bezeichnet werden. Ein weiche Ausgabe an den harten Ausgabe-Konverter 407 empfängt die Ausgabe des SISO Decoders 405. Der Konverter 407 konvertiert die weichen Werte des SISO Decoders 405 zu harten Ausgabewerten.
Der SISO Decoder 403 liefert a priori Werte für SISO Decoder 405. SISO Decoder 405 empfängt die a priori Werte von SISO Decoder 403 und liefert dann extrinsische weiche Werte an den Konverter 407, welche zu harten Werten konvertiert werden. Der Konverter 407 ist kein üblicher Teil eines Turbo-Decoders. Der Konverter 407 wird verwendet, um den tatsächlichen Datenwert zu bestimmen, welcher decodiert werden würde, wenn die aktuelle Decodieriteration die letzte Iteration wäre. Mit anderen Worten, der Konverter 407 wird verwendet, um zu bestimmen, wie viele Fehler vorhanden wären, wenn die aktuelle Iteration zu harten Werten konvertiert werden würde. Die extrinsischen Werte von dem SISO 405 werden auch für ein iteratives Verarbeiten von den SISO 403 angenommen. Bei der Verwendung einer derartigen Anordnung kann das von jeder Decoderiteration erzeugte Ergebnis analysiert werden.
Da die Ausgabe von dem SISO 403 und 405 weiche Werte sind, sind sie nicht lediglich 0 oder 1 Werte. Die von dem SISO erzeugten weichen Werte sind Werte, welche den Wert des decodierten Signals und auch das Vertrauen in den Wert des decodierten Signals darstellen. Zum Beispiel können die MAP Decoder Werte zwischen –7 und +7 ausgeben. Eine –7 kann einen binären Wert von 0 mit einem hohen Vertrauen darstellen. Das Minuszeichen zeigt eine binäre 0 an und der Wert 7 zeigt an, dass der Wert 0 mit einem hohen Grad an Vertrauen bekannt ist. In ähnlicher Weise würde eine SISO Decoderausgabe von –3 auch einen digitalen Wert 0 anzeigen, jedoch mit geringerem Vertrauen als –7. Eine Ausgabe von einer –1 würde eine digitale 0 mit noch geringerem Vertrauen als –7 oder –3 darstellen. Eine Ausgabe von 0 würde anzeigen, dass die digitalen Werte 1 und 0 gleich wahrscheinlich sind. Im Gegensatz dazu würde eine +1 einen digitalen Wert 1 mit einem niedrigen Grad an Vertrauen anzeigen. Eine +3 würde einen digitalen Wert von 1 mit mehr Vertrauen als ein +1 darstellen und ein Wert von +7 würde einen digitalen Wert von 1 mit mehr Vertrauen als eine +1 oder eine +3 darstellen.
Da die Eingabedaten 303 an die Simulation harte binäre Werte von 0 oder 1 aufweisen, wird die Ausgabe des SISO Decoders 405 zu harten, d.h. entweder 1 oder 0, digitalen Werten konvertiert, bevor sie mit dem Eingangsdatenblock 303 verglichen werden. Der Konverter 407 konvertiert die weichen Ausgabewerte des SISO 405 in harte digitale Werte.
Sobald die weichen Werte von dem SISO 405 zu harten Werten konvertiert und an den Datenblock 315 geliefert worden sind, können die harten Werte mit den ursprünglichen Daten 303 verglichen werden.
Die Simulation von 3 ist nützlich, weil Daten von nachfolgenden Iterationen des Decoders 313 mit den ursprünglichen Daten 303 verglichen werden können. Sobald die Ergebnisse einer Iteration mit den Eingangsdaten 303 verglichen werden, kann ein Ergebnis 319, welches die Fehleranzahl in dem Datenblock 315 aufweist, bestimmt werden.
Die SISOs 403 und 405 decodieren jeweils zwei einzelne Faltungscodes der Turbo-Codierung, welche von dem Codierer 305 erzeugt wird. In jedem iterativen Decodierzyklus geben die SISOs 403 und 405 extrinsische Information aneinander aus. In jeder Decoderiteration verwendet der SISO 405 die von SISO 403 in der vorhergehenden Iteration bereitgestellte extrinsische Information. SISO 403 verwendet die von SISO 405 in der vorhergehenden Iteration bereitgestellte extrinsische Information. SISO 405 erzeugt auch eine posterior Wahrscheinlichkeitssequenz in jeder Iteration. Die von dem SISO 405 in der k-ten Iteration erzeugte posterior Wahrscheinlichkeitssequenz kann von Lx^k _i dargestellt werden, wobei i der Index des gerade decodierten Wertes ist. Diese posterior Wahrscheinlichkeitssequenz wird von dem „weich zu hart" Konverter 407 verwendet, um harte Werte zu erzeugen. Wenn die posterior Wahrscheinlichkeitssequenz in der k-ten Iteration gleich der späteren Wahrscheinlichkeitssequenz in der (k-1)-ten Iteration ist, d.h. (Lx^k-1 _i) = (Lx^k _i), dann konvergierte die spätere Wahrscheinlichkeitssequenz. Jedoch tritt vielleicht eine Konvergenz viele Iterationen lang nicht auf. In der Praxis wird eine iterative Decodierung üblicherweise nach einer festen Anzahl von Iterationen gestoppt.
Die Genauigkeit von harten Entscheidungen kann aus der Konvergenz der posterior Wahrscheinlichkeitswerte. In einer k-ten Iteration empfängt der „weich zu hart" Konverter 407 die posterior Wahrscheinlichkeitswerte Lx^k _i und erzeugt entsprechende harte Werte x^k _i. Wenn die harten Werte in einer k-ten Decoderiteration x^k _i mit den harten Werten in einer (k-1)-ten oder einer (k-2)-ten Iteration übereinstimmen, d.h. (x^k _i = x^k-1 _i oder x^k _i = x^k-2 _i), dann ist die Sequenz x^k _i ein fester Punkt.
Das Konzept des festen Punktes ist nicht neu. In einem Artikel mit dem Titel "The geometry of turboing dynamics" von T. Richardson, veröffentlicht in den IEEE Transactions on Information Theory, Band 46, Januar 2000, welcher durch Bezugnahme hierin eingeschlossen ist, definiert Richardson einen festen Punkt im Sinne einer Wahrscheinlichkeitsdichte, d.h. (Lx^k _i).
Richardson behauptete, dass, wenn Lx^k _i und Lx^k-1 _i die gleiche "bitweise Randverteilung" ("bit wise marginal distribution") aufweisen, dann stellt x^k _L einen festen Punkt dar. In anderen Worten (BZ hier müssen wir sagen, was "bit wise marginal distribution".
Nach einer Anzahl von Iterationen kann der Decoder 313 (siehe 3) zu einem festen Punkt konvergieren. Es können jedoch mehrere feste Punkte existieren. Ein fester Punkt muss nicht notwendigerweise eine korrekte Wiedergabe der gesendeten Daten darstellen. Zusätzlich können einige feste Punkte nicht stabil sein, d.h., obwohl ein fester Punkt erreicht worden ist, ändern sich die decodierten Werte, wenn die Decodieriterationen fortgesetzt werden. D.h., wenn der Decoder seine Iterationen für zusätzliche n-Iterationen fort setzt, stimmt ein fester Punkt der weiteren Iteration x^k+n _L nicht mit dem gleichen Wert überein wie der feste Punkt x^k _i. Als Beispiel ist Tabelle #1 von #5 zu betrachten.
Tabelle #1 ist ein Beispiel einer Simulation einer Rate 2/3, 8 Phase Shift Keying (PSK) Turbo Trellis Code mit einer Blocklänge von 10.240 Bits. Das Signal-Rausch-Verhältnis, E_b/N₀, welches für die Simulation verwendet wird, beträgt 3,70 dB. Diese in Tabelle 1 erläuterte Simulation fand einen nicht stabilen festen Punkt in der sechsten Iteration. In der sechsten Iteration wurden 5 Bitfehler in dem decodierten Block gefunden, was den in einer fünften Iteration des Decoders gefundenen 5 Bitfehlern entspricht. Jedoch ergab die zwölfte Iteration des Decoders auch einen stabilen festen Punkt.
Die Simulationserläuterung in Tabelle 1 von 5 erläutert auch, dass nach dem ersten nicht stabilen festen Punkt in Iteration 6 der Decoder anfängt, Fehler fortzupflanzen, bis in der achten Iteration 180 Bitfehler vorhanden sind. Demgemäss erzeugt ein wie in Tabelle 1 arbeitender Decoder tatsächlich eine schlechtere Ausgabe, wenn er in der achten Iteration gestoppt wird, im Vergleich dazu, wenn er in der sechsten Iteration gestoppt wird. Eine derartige Gegebenheit, in welcher weitere Decodieriterationen mehr Fehler erzeugen, wird "Fehlerfortpflanzung" genannt. Im Rahmen von 80.000 Simulationen wurden 5 derartige nicht stabile feste Punkte aufgefunden.
Auch wenn die Sequenz x^k _i der gesendeten Bitsequenz entspricht, ist die Sequenz x^k _i vielleicht nicht ein fester Punkt. Ein derartiger Fall ist in Tabelle #2 von 5 erläutert. In dem in Tabelle #2 erläuterten Decodierbeispiel erzeugt die vierte Iteration eine Ausgabesequenz mit 0 Fehlern. Jedoch ist die vierte Iteration kein fester Punkt, da nachfolgende Iterationen eine Decodierung mit zwei Fehlern in jedem decodierten Block erzeugen.
Tabelle 3 von 5 erläutert einen Fall, in welchem alternativ zwei feste Punkte auftreten. Die ungeraden Iterationen nach Iteration 4 zeigen 2 Fehler pro Decodierung, wohingegen die geraden Iterationen nach Iteration 4 0 Fehler pro Decodierung zeigen.
Gemäß Simulationen werden feste Punkte so ausgewählt, dass sie weniger als 10 Bitfehler enthalten. Dementsprechend kann, um eine Fehlerfortpflanzung zu vermeiden, die iterative Decodierung gestoppt werden, nachdem ein fester Punkt erreicht worden ist. Eine Vorrichtung zum Stoppen der Decodierung in einer bestimmten Iteration ist in 6 erläutert.
6 zeigt ein Blockdiagramm einer Signaturschaltung gemäß einem Ausführungsbeispiel der Erfindung.
In 6 stellt Block 601 einen iterativen Decoder, zu Erläuterungszwecken ein Turbo-Decoder, dar, welcher einen MAP Algorithmus ausführt (MAP Decoder). Der SISO weist zwei einzelne Soft in Soft out (SISO) Decoder auf. Fachleute erkennen, dass jeder iterative oder probabilistische Decoder von Block 601 dargestellt werden kann. Die Turbo-Decodierung für Block 601 wurde zum Zwecke einer Erläuterung und nicht einer Beschränkung ausgewählt.
Die Ausgabe von Block 601 ist eine Sequenz von weichen a posteriori Werten, welche an einen „weich zu hart" Konverter 603 geliefert werden. Der „weich zu hart" Konverter konvertiert die Sequenz von weichen a posteriori Werten zu einer Sequenz von harten Werten, d.h., Einsen und Nullen. Die Sequenz von Einsen und Nullen stellt eine Schätzung der von dem Sender übertragenen Sequenz dar, wie von der aktuellen Iteration geschätzt, d.h., von dem iterativen Decoder 601. Die Schätzung der von der k-ten Decoderiteration gesendeten Sequenz wird seriell an eine Signaturschaltung 605 geliefert.
Die Signaturschaltung 605 weist eine Reihe von Datenspeicherelementen 607A bis 607N auf, wobei N eine beliebige ganze Zahl ist, wie zum Beispiel 32. Die Speicherelemente sind seriell angeordnet. D.h., Speicherelement 607B empfängt zum Beispiel seine Eingabe von der Ausgabe des Speicherelements 607A. Wenn von dem Takt 613 getaktet, wird der Wert von Speicherelement 607A in Speicherelement 607B getaktet. Speicherelement 607B wird in Speicherelement 607C getaktet usw. Die Speicherelemente 607 können eine Vielfalt von Speicherelementen, wie zum Beispiel D-Typ Flip-Flops, sein. Die Ausgabe des letzten Speicherelements 607N wird an einen Modulo-2 Addierer 609 geliefert. Der Addierer 609 empfängt auch, als eine zweite Eingabe, die geschätzten harten Werte der k-ten Decoderiteration. Die Ausgabe von dem Addierer 609 wird an den Eingang der ersten Speichervorrichtung 607A der Signaturspeicherkette 607A bis 607N geliefert.
Nach jeder Iteration des iterativen Decoders 601 wird eine von dem Decoder 601 gelieferte Sequenz von weichen Werten zu einer Sequenz von harten Werten in dem Konverter 603 konvertiert. Die in dem Konverter 603 erzeugte Sequenz von harten Werten wird dann an die Signaturschaltung 605 geliefert. Die Signatur der Iteration ist der Zustand der Speichervorrichtung 607A bis 607N.
In dem gegenwärtigen Beispiel von 6 bilden 32 Speichervorrichtungen 607 den Zustand der Signaturschaltung 605 und daher hat die Signatur 32 Bits. Signaturschaltungen können mehr oder weniger als 32 Bits aufweisen, abhängig von der Größe des decodierten Blockes, den erwarteten Signal-Rausch-Verhältnissen und einer Vielzahl von anderen Faktoren. Die Signatur von der k-ten Iteration wird mit der Signatur von der K-1 und der K-2 Iteration verglichen. Wenn die Signatur von der k-ten Iteration mit der Signatur von der k-1 oder der k-2 Iteration übereinstimmt, stoppt das iterative Decodieren.
Unter Verwendung von 32 Bits als die Länge (die Zahl von Speichereinheiten) der Signaturschaltung 605 wurden 80.000 Blöcke der Rate 2/3, 8 Phase Shift Keying (8-psk) Turbo-Trellis kodierte Modulation (TTCM) simuliert. Die Blocklänge des TTCM Codes betrug 10.240 Symbole mit jeweils 2 Bits. Das simulierte E_b/N₀ betrug 3,70 dB. Die Signatureinheit wurde verwendet, um ein Stoppkriterium für die Decodersimulation zu erzeugen, wie auch ein Stoppen der Decodierung nach einer festen Anzahl (8) von Decodierzyklen.
Die Signatureinheit wurde mit lauter Nullen zwischen den Iterationen initialisiert und die geschätzte Sequenz von harten Werten wurde an die Signatureinheit geliefert. Wenn die Signatureinheit einen Wert in der k-ten Iteration zeigte, welcher gleich groß wie der Signaturwert in der k-1 oder k-2 Iteration des Decoders war, wurde der Decoder gestoppt.
Das Ergebnis der Simulation des Decodierens von 80.000 Blöcken mit Rate 2/3 TTCM Code, wie zuvor beschrieben, wird in Tabelle 4 von #6 zusammengefasst.
Die Signaturkriterien lieferten mehr Blöcke mit Fehlern als der Decoder mit 8 festen Iterationen. Die Signaturschaltung erzeugte 162 Blöcke mit Fehlern gegenüber 95 für den 8 Iterationsdecoder; jedoch erzeugte eine Verwendung des Signaturkriteriums eine kleinere Anzahl von Bitfehlern, d.h. 401 gegenüber 530, als die 8 Iterationsdecodierung. Die Signatur decodierung führte auch zu einer niedrigeren Bitfehlerrate 2,447 e^–7 gegenüber 2,325 e^–7 für das 8 Iterationsdecodieren.
Das Signaturverfahren benötigt nur einen Durchschnitt von 5,5 Iterationen, um einen festen Punkt zu erreichen. Das Signaturverfahren benötigt ein Maximum von 9 Iterationen in 9 von 80.000 decodierten Blöcken. Die feste Zahl von Iterationen, die ein Decoder verwendet, waren 8 Iterationen. Das Signaturverfahren reduziert, zusätzlich dazu, dass es weniger Zeit in Anspruch nimmt, die benötigten Iterationen von 8 auf einen Durchschnitt von 5,5 Iterationen. Nur 9 von 80.000 Blöcken benötigten mehr als 8, d.h. 9 Iterationen bei dem Decodieren.
Das Signaturverfahren stoppte das Decodieren bei einer Vielzahl von verschiedenen Iterationen. Die Iteration, bei welcher das Signaturverfahren, sind prozentual in Tabelle 5 aufgelistet. Das Signaturverfahren führt zu weniger Fehlern und zu weniger Zeit (Iterationen) zum Decodieren und zeigte daher, dass nicht nur die iterative Decodierzeit verkürzt wurde, sondern auch dass das Signaturdecodieren das Problem der Fehlerfortpflanzung in zukünftigen Iterationen verringert. Fehlerfortpflanzung tritt in einem Decoder mit fester Anzahl auf, wenn ein fester Punkt erreicht wird, aber, da die Maximalzahl an Iterationen noch nicht erreicht ist, der iterative Decodierprozess andauert, mit dem Ergebnis, dass die Anzahl von Fehlern in dem Block über die Fehler an dem festen Punkt erhöht wird. Durch ein Vermeiden von Fehlerfortpflanzung, welche aus einer iterativen Decodierung darüber hinaus resultiert, wo ein fester Punkt erreicht wird, wird das Decodieren durch das Signaturverfahren verbessert.
Andere Stoppkriterien sind vorgeschlagen worden. In "Reduction of the Number of Iterations in Turbo Decoding Using Extrinsic Information", veröffentlicht in IEEE TenCon, Seite 494–496, welche durch Bezugnahme eingeschlossen wird, schlagen B. Kim und H. Lee zum Beispiel ein Stoppkriterium vor, welches eine Vielfalt von extrinsischer Information verwendet. Ihr Verfahren funktioniert nicht in allen Decodern. Ein modifiziertes Verfahren wird hierin vorgeschlagen.
E_kx_i gebe die extrinsische Information eines SISO (Soft in Soft out) Decoders, beispielsweise einer, der einen MAP Algorithmus ausführt, in der k-ten Iteration an. Wenn der Mittelwert, M_k, für die k-te Iteration definiert ist als:
Dann ist die Varianz der extrinsischen Information:
worin N die Blockgröße des iterativ decodierten Blockes ist.
Im Allgemeinen existiert für ein festes Signal-Rausch-Verhältnis ein Schwellwert T in der Weise, dass, wenn VAR_k < T. Die posterior Wahrscheinlichkeitssequenz hat konvergiert. Jedoch besitzt diese Regel Ausnahmen und somit ist ein zusätzliches Kriterium nötig. Ein derartiges Kriterium ist die differenzielle Varianz D_k. D_k ist definiert als: Dk = |VARk – VARk-1| Gleichung 3
Eine neue Schwellwertregel kann wie folgt festgelegt werden, Stoppen der Iteration des Decoders, nur wenn zusätzlich VARk < T1 and Dk < T2 Gleichung 5 worin T₁ und T₂ Schwellwerte sind. Die Werte für T, T₁ und T₂ können durch die Verwendung einer Simulation bestimmt werden, beispielsweise, indem eine Simulation, wie in 3 erläutert, verwendet wird. Der ausgewählte Schwellwert hängt von dem Signal-Rausch-Verhältnis ab, immer benötigt, und einer Vielzahl von anderen Implementierungsdetails.
Ein Verfahren zur Bestimmung der Schwellwerte T, T₁ und T₂ lautet wie folgt: Zuerst wird ein Signal-Rausch-Verhältnis ausgewählt und ein Rauschvektor 309 eingebracht, um das ausgewählte Signal-Rausch-Verhältnis aufzunehmen. Nachfolgende Iterationen werden dann auf die Fehleranzahl und Schwellwerte T, T₁ und T₂ überprüft. Je größer die Anzahl an Simulationen, desto genauer können die Werte von T, T₁ und T₂ bestimmt werden. Die bestimmten Schwellwerte hängen natürlich von derartigen Faktoren wie das Signal-zu-Rausch-Verhältnis, Coderate, usw. ab.
Als ein erläuterndes Beispiel wurde eine Rate 2/3 8-Phase Shift Keying Turbo Trellis Code Modulation mit einer Blocklänge von 10240 und einem E_b/N₀ = 3,70 dB ausgewählt. Unter Verwendung eines T und T₂ gleich 10 und eines T₁ gleich 100 wurden 80000 Blöcke simuliert. Die Ergebnisse sind in Tabelle 6 von 7 erläutert.
Zusätzlich zu dem Signaturkriterium kann ein Cross entropy Kriterium bei der Bestimmung eines Stoppkriteriums für ein iterativen Decodieren eingesetzt werden. In "Suboptimum Decoding Using Kullback Principle", veröffentlicht in Lecture Notes in Computer Science, Nr. 313, B. Bouchon et al., Eds., 1988, Seite 93–101, G. Battail und R. Sfes, welche durch Bezugnahme eingeschlossen ist, wird beispielsweise das Konzept einer Decodierung unter Verwendung einer Minimierung der Cross Entropy erläutert. Zusätzlich erläutern J. Hagenauer, E. Offer und L. Papke Cross Entropy in "Iterative Decoding of Binary Block and Convolutional Codes", veröffentlicht in IEEE, Transactions on Information Theory, Band 42, März 1996, Seite 429–445, welches hiermit durch Bezugnahme eingeschlossen wird.
Wenn ein Decoder, zu Erläuterungszwecken ein Turbo -Decoder mit 2 SISO Einheiten, eine Sequenz extrinsischer Information erzeugt, kann die extrinsische Information von dem ersten SISO dargestellt werden als E^k ₁x_i und der zweite SISO kann dargestellt werden als E^k ₂x_i. Die Cross Entropy kann dann definiert werden als:
Der Decoder kann dann den Decodierprozess beenden, indem er den Wert von T_(k)/₍₁₎ überprüft, um zu sehen, ob er weniger als ein gewisser vorbestimmter Schwellwert ist. Wie zuvor kann der Schwellwert für ein bestimmtes Signal-Rausch-Verhältnis durch die Verwendung von Simulationen bestimmt werden, wobei Simulationen, wie zum Beispiel in 3 erläutert, verwendet werden.
Ein Vergleich der Simulation von 80.000 Blöcken mit einer Rate 2/3, 8 psk Turbo Trellis codierter modulierter Code mit einem E_b/N₀ = 3,75 dB wurde simuliert. Die Ergebnisse sind wie in Tabelle 7 von 7 zu sehen.
8 zeigt einen Graph, welcher eine Bitfehlerrate gegen E_b/N₀ für verschiedene Stoppkriterien darstellt. Wie zu sehen ist, erzeugt das Signaturkriterium eine Bitfehlerrate (BER = Bit Error Rate), welche größer ist als das 8 Iterationsdecodieren bei einem E_b/N₀ von 3,75 dB. Das Varianzstoppkriterium erzeugt ein BER, welches größer ist als die 8 Iterationsdecodierung bei allen getesteten E_b/N₀.

Claims

Verfahren zum Beenden eines Vorgangs eines iterativen Dekodierens eines Decoders (313), welcher einen ersten und einen zweiten Soft in-Soft out SISO Decoder (403, 405) aufweist, welche in der Weise miteinander verbunden sind, dass in jeder Iteration der zweite SISO Decoder (405) extrinsische Information verwendet, welche von dem ersten SISO Decoder (403) in einer vorhergehenden Iteration bereitgestellt worden ist und der erste SISO Decoder (403) die extrinsische Information verwendet, welche von dem zweiten SISO Decoder (405) in der vorhergehenden Iteration bereitgestellt worden ist, wobei das Verfahren die Schritte aufweist: Ermitteln der Varianz VAR_k der extrinsischen Information zu einer k-ten Iteration des Vorgangs gemäß der folgenden Gleichung:
worin: k die k-te Iteration bezeichnet; E^kx_i die extrinsische Information einer der Soft in-Soft out SISO Decoder angibt; M_k den Mittelwert für die k-te Iteration angibt; und N die Blockgröße eines Blockes ist, welcher iterativ dekodiert wird; und Ermitteln eines Stopkriteriums zum Beenden des Vorgangs basierend auf der Varianz; Ermitteln der Varianz VAR_k-1 extrinsischer Information zu einer k-1-ten Iteration des Vorgangs; und Beenden des Vorgangs eines iterativen Dekodierens, falls: VAR_k < T₁, wobei T₁ einen ersten Schwellwert bezeichnet; dadurch gekennzeichnet, dass der Vorgang nur dann beendet wird, falls zusätzlich: D_k = |VAR_k – VAR_k-1| < T₂, wobei T₂ einen zweiten Schwellwert bezeichnet.
Verfahren gemäß Anspruch 1, dadurch gekennzeichnet, dass der erste Schwellwert T₁ ermittelt wird, indem die folgenden Schritte ausgeführt werden: Auswählen eines Wertes für ein Signal-Rausch-Verhältnis E_b/N₀; Erzeugen eines Signals mit der bestimmten Kodierung; Hinzufügen eines Rauschvektors zu dem Signal, um ein verschlechtertes Signal zu erzeugen; iteratives Dekodieren des verschlechterten Signals bis die Iteration konvergiert; und Zuordnen eines Wertes kleiner als VAR_k zu T₁.
Verfahren gemäß Anspruch 1 oder 2, dadurch gekennzeichnet, dass der zweite Schwellwert T₂ ermittelt wird, indem die folgenden Schritte ausgeführt werden: Auswählen eines Wertes für ein Signal-Rausch-Verhältnis E_b/N₀; Erzeugen eines Signals mit der bestimmten Kodierung; Hinzufügen eines Rauschvektors zu dem Signal, um ein verschlechtertes Signal zu erzeugen; iteratives Dekodieren des verschlechterten Signals bis die Iteration konvergiert; und Zuordnen eines Wertes größer als D_k zu T₂.
Vorrichtung zum Erzeugen eines Stopkriteriums für einen iterativen Decoder (313), welcher einen ersten und einen zweiten Soft in-Soft out SISO Decoder (403, 405) aufweist, welche in der Weise miteinander verbunden sind, dass in jeder Iteration der zweite SISO Decoder (405) extrinsische Information verwendet, welche von dem ersten SISO Decoder (403) in einer vorhergehenden Iteration bereitgestellt worden ist und der erste SISO Decoder (403) die extrinsische Information verwendet, welche von dem zweiten SISO Decoder (405) in der vorhergehenden Iteration bereitgestellt worden ist, wobei die Vorrichtung aufweist: Mittel zum Ermitteln der Varianz VAR_k extrinsischer Information zu einer k-ten Iteration des iterativen Decoders, wobei die Varianz gemäß der folgenden Gleichung definiert wird:
worin: k die k-te Iteration bezeichnet; E^kx_i die extrinsische Information einer der Soft in-Soft out SISO Decoder angibt; M_k den Mittelwert für die k-te Iteration angibt; N die Blockgröße eines Blockes ist, welcher iterativ dekodiert wird; und Mittel zum Beenden der Iteration basierend auf der Varianz; wobei ein Mittel zum Ermitteln der Varianz VAR_k-1 extrinsischer Information zu einer k-1-ten Iteration des Vorgangs bereitgestellt wird; und das Mittel zum Beenden der Iteration dafür ausgebildet ist, die Iteration zu beenden, falls: VAR_k < T₁, wobei T₁ einen ersten Schwellwert bezeichnet; dadurch gekennzeichnet, dass das Mittel zum Beenden die Iteration nur dann beendet, falls zusätzlich: D_k = |VAR_k– VAR_k-1| < T₂, wobei T₂ einen zweiten Schwellwert bezeichnet.
Vorrichtung gemäß Anspruch 4, dadurch gekennzeichnet, dass sie aufweist: eine Vorrichtung zum Ermitteln des ersten Schwellwertes T₁ für eine bestimmte Kodierung für einen bestimmten Wert für ein Signal-Rausch-Verhältnis E_b/N₀, wobei die Vorrichtung zum Ermitteln von T₁ aufweist: Mittel zum Erzeugen eines Signals mit der bestimmten Kodierung; Mittel zum Hinzufügen eines Rauschvektors zu dem Signal, um ein verschlechtertes Signal zu erzeugen; Mittel zum iterativen Dekodieren des verschlechterten Signals bis die Iteration konvergiert; und Mittel zum Zuordnen eines Wertes kleiner als VAR_k zu T₁.