DE10196688B3

DE10196688B3 - Ein Decodierer für eine trellis-basierte Kanalcodierung

Info

Publication number: DE10196688B3
Application number: DE10196688T
Authority: DE
Inventors: John Sadowsky
Original assignee: Intel Corp
Current assignee: Intel Corp
Priority date: 2000-09-28
Filing date: 2001-09-26
Publication date: 2013-10-17
Anticipated expiration: 2021-09-27
Also published as: CN1466818A; WO2002029977A2; TW548914B; GB2381724A; WO2002029977A3; DE10196688T1; GB2381724B; US7234100B1; GB0303959D0; JP2004511162A; AU2001294838A1; CN1302624C; KR20030036845A

Abstract

Ein System, aufweisend: einen digitalen Signalprozessor mit einem mit einem Speicher verbindbaren Bus; und mehreren mit dem Bus verbundene Butterfly-Einheiten zum Ausführen von Butterfly-Operationen, wobei die Butterfly-Einheiten eine von dem digitalen Signalprozessor eingeplante Operation ausführen, wobei die Butterfly-Operationen der Butterfly-Einheiten parallele Operationen sind, wobei der digitale Signalprozessor ferner einen mit dem Bus gekoppelten Datenadreßgenerator aufweist, wobei der Datenadreßgenerator für eine anfordernde Einrichtung den Speicher adressiert.

Description

Hintergrund
Diese Erfindung bezieht sich auf Decodieroperationen, die an kanalcodierten Daten ausgeführt werden, und insbesondere auf Decodierer, welche mit Trellis-Diagrammen arbeiten.
Eine Kommunikation zwischen Systemen ist immer dann möglich, wenn ein gemeinsamer Kanal die Systeme verbindet. Ob über Netzwerkkabel, Telefonleitungen oder Internet-Protokoll-Sockets, die zwischen Einheiten übermittelten Daten breiten sich über ein Kanalmedium aus.
Unglücklicherweise können „Rauschen” und „Störungen” in dem Kanalmedium die Daten während der Übertragung verfälschen. Faktoren, wie beispielsweise die Länge des Kanalmediums, die gesendete Datenmenge, das Vorhandensein falscher Signale in dem Kanal und andere Umgebungsbedingungen, können den Betrag des Rauschens und die Menge der Störungen beeinflussen und somit die Qualität der empfangenen Daten.
Da die Phänomene des Rauschens und der Störungen in einem Kanal erwartet werden, werden die Daten nahezu stets codiert, bevor sie gesendet werden. Ein Datencodierer wird grundsätzlich aus diskreter Logik, wie beispielsweise Flip-Flops und NAND-Gattern, gebildet. Der Datencodierer empfängt einen Strom Datenbits, die als Informationsbits bekannt sind, der über ein Kanalmedium gesendet werden soll, und erzeugt zusätzliche Bits, die als Paritätsbits bekannt sind, auf der Grundlage der Informationsbits selbst. Zusammen bilden die Informationsbits und die Paritätsbits einen codierten Bitstrom.
Diese sorgfältig gebildeten redundanten Informationen sind als Vorwärtsfehlerkorrektur (FEC; Forward Error Correction) oder Kanalcodierung bekannt. Sobald er konstruiert ist, wird der codierte Bitstrom über den Kanal gesendet. In einigen Fällen kann der codierte Bitstrom vor dem Senden moduliert werden.
Bei der Übertragung über den Kanal und der nachfolgenden Demodulation bei dem Empfänger könnten einige der „1”-Bits (oder eine modulierte Darstellung dieser Bits) derart verfälscht werden, daß sie als „0”-Bits empfangen werden. In gleicher Weise könnten einige der „0”-Bits als „1”-Bits empfangen werden. Bei modernen digitalen drahtlosen Empfängern kann der Demodulator darüber hinaus Bit für Bit „Zuverlässigkeitsmetriken” melden. Deutlich empfangene Einsen und Nullen erzeugen eine hohe Zuverlässigkeitsmetrik, während zweideutig oder unklar empfangene Daten eine niedrige Zuverlässigkeitsmetrik (ein niedriges Zuverlässigkeitsmaß) erzeugen. Die Informationsbits oder die Paritätsbits des codierten Bitstroms oder beide können während der Übertragung verfälscht werden.
Zusätzlich zum Demodulator enthält die empfangende Einheit einen Decodierer, dessen Zweck darin besteht, unter Verwendung der Demodulatorausgangssignale und der Kenntnis der Struktur des Codierers diejenigen Informationsbits zu bestimmen, die mit höchster Wahrscheinlichkeit gesendet worden sind. Die oben beschriebene Bitzuverlässigkeitsmetrik kann die Fähigkeiten des Decodierers signifikant verbessern. Erwartungsgemäß kann der Decodierer beträchtlich komplexer als der Codierer sein.
Shannons berühmtes Kanalcodierungstheorem ist der Grund für den Drang nach stets komplexeren codierten digitalen Kommunikationssystemen. Shannons Theorem besagt, daß, solange die Informationsrate (gesendete Informationsbits pro Sekunde) nicht die Kanalkapazität überschreitet, es möglich ist, FEC-Codiersysteme mit einer beliebig geringen Decodierfehlerwahrscheinlichkeit zu entwickeln.
Shannons Theorem ist jedoch ein asymtotisches Ergebnis. Es sagt tatsächlich wenig darüber aus, wie praktische Codiersysteme zu konstruieren sind, sondern nur, daß eine perfekte Decodierung erreichbar ist, wenn die Codierblockgröße (Anzahl der Informationsbits) und Codekomplexität gegen unendlich gehen. Es stellt sich heraus, daß sehr leistungsfähige und somit komplexe Codes leicht zu konstruieren sind.
Die schwierige Aufgabe besteht dann darin, einen effizienten Decodieralgorithmus für diese komplexen Codes zu finden. So besteht die praktische Aufgabe des FEC-Code-Designs darin, Familien von leistungsfähigen (und somit komplexen) Codes aufzufinden, die eine spezielle Struktur aufweisen, die ausgenutzt werden kann, um einen Decodierer praktikabler Implementierungskomplexität zu erlangen. Selbstverständlich werden in dem Maße, wie die digitale Technologie voranschreitet, zunehmend komplexere Decodierer möglich.
Einige Decodieralgorithmen arbeiten mit spezialisierten Zustandsdiagrammen, die als Trellis-Diagramme bekannt sind, um decodierte Ausgangssignale zu erzeugen. Ein Trellis-Diagramm ist eine Zustandsmaschine, die mögliche Zustandsübergänge eines Codierers über der Zeit demonstriert. Trellis-Diagramme beschreiben sämtliche möglichen Zustände des Codierers zu jedem Zeitpunkt. Viele Decodieralgorithmen verwenden Trellis-Diagramme zusammen mit dem Kanalbitstrom, um zu den richtigen Informationsbits zu gelangen.
Das Volumen der Berechungen, die eine Trellis-Decodierung mit sich bringt, kann jedoch schwindelerregend sein. Dementsprechend können Decodierer mit anwendungsspezifischen integrierten Schaltungen (ASICs) implementiert werden, welche spezielle Trellis-Operationen, wie beispielsweise Butterfly-Operationen, sehr effizient ausführen. Aufgrund der Komplexität der verschiedenen Decodieralgorithmen werden derartige ASICs üblicherweise für einen einzigen Algorithmus entwickelt.
Die EP 0923197 A1 beschreibt eine Verarbeitungseinheit, die in einem mobilen Kommunikationsgerät integriert ist, um eine ACS-Operation (Addieren, Vergleichen und Auswählen), insbesondere einer Viterbi-Dekodierung, durchzuführen.
Andere Decodierer können digitale Mehrzwecksignalprozessoren (DSPs) enthalten, welche spezielle Befehle zum Ausführen von Trellis-Operationen enthalten können oder auch nicht. Diese Decodierer können derart programmierbar sein, daß bedarfsweise verschiedene Decodieralgorithmen implementiert werden können. Derartige Decodierer können flexibler sein, aber es kann sein, daß sie Kanaldaten bei einer geringeren Rate decodieren als die ASIC-basierten Decodierer.
Somit besteht ein fortgesetzter Bedarf an einem programmierbaren Prozessor, der mit einem digitalen Mehrzwecksignalprozessor zum Ausführen trellis-basierter Decodieroperationen verwendet werden kann.
Kurzbeschreibung der Zeichnungen
1 ist eine Blockdarstellung eines Systems gemäß einem Ausführungsbeispiel der Erfindung;
2 ist ein Schema eines rekursiven systematischen Faltungscodierers gemäß einer Ausführungsform der Erfindung;
3 ist eine Zustandsübergangstabelle für den Codierer gemäß 2 in Übereinstimmung mit einer Ausführungsform der Erfindung;
4 ist eine Trellis für den Codierer gemäß 2 in Übereinstimmung mit einer Ausführungsform der Erfindung;
5 ist ein Trellis-Diagramm für den Codierer gemäß 2 nach einem Ausführungsbeispiel der Erfindung;
6 ist das Trellis-Diagramm gemäß 5, das einen möglichen Pfad bei Verwendung des Codierers gemäß 2 nach einer Ausführungsform der Erfindung veranschaulicht; und
7 ist eine Blockdarstellung des Pfads, den ein Informationsdatenstrom nehmen könnte, gemäß einer Ausführungsform der Erfindung;
8 ist ein Diagramm, das sowohl Zweig- als auch Pfad-Metriken eines Trellis-Diagramms gemäß einem Ausführungsbeispiel der Erfindung veranschaulicht;
9 ist ein Trellis-Diagramm, das verwendet wird, um Butterfly-Operationen zu veranschaulichen, gemäß einem Ausführungsbeispiel der Erfindung;
10 ist eine Blockdarstellung eines Butterfly-Operators gemäß einem Ausführungsbeispiel der Erfindung;
11 ist eine zweite Blockdarstellung eines Butterfly-Operators gemäß einem zweiten Ausführungsbeispiel der Erfindung;
12 ist eine Blockdarstellung des Butterfly-Operators gemäß 10, der bei dem System gemäß 1 verwendet wird, gemäß einem Ausführungsbeispiel der Erfindung;
13 ist ein Ablaufdiagramm eines von dem System gemäß 12 verwendeten Software-Programms gemäß einem Ausführungsbeispiel der Erfindung;
14a und 14b sind schematische Darstellungen, die mögliche Operationen der Butterfly-Einheit veranschaulichen, gemäß einem Ausführungsbeispiel der Erfindung;
15 ist eine Blockdarstellung eines Turbo-Codierers gemäß einem Ausführungsbeispiel der Erfindung; und
16 ist eine Blockdarstellung eines Turbo-Decodierers gemäß einem Ausführungsbeispiel der Erfindung.
Detaillierte Beschreibung
In Übereinstimmung mit verschiedenen hier beschriebenen Ausführungsbeispielen werden ein System und ein Verfahren zum effizienten Ausführen spezieller Operationen offenbart, die beim Decodieren bestimmter Arten von Kanalbitströmen verwendet werden. Die speziellen Operationen sind als Butterfly-Operationen bekannt. Obwohl der Viterbi- und der MAP-Decodieralgorithmus im Detail beschrieben werden, können das System und das Verfahren unter Verwendung anderer Decodieralgorithmen implementiert werden, die mit Trellis-Diagrammen arbeiten.
Die hier beschriebenen Operationen betreffen die Implementierung bestimmter trellis-basierter Algorithmen. Die Algorithmusklasse wird in der Praxis bei einer Reihe von Anwendungen in der Kommunikationstechnik und der Signalverarbeitung verwendet, die eine Codierung und Decodierung von Faltungscodes und Turbo-Codes, eine Kanalausgleichung (equalization) und Sprachcodierung einschließen (aber nicht da rauf beschränkt sind). Eine FEC-Decodieranwendung wird hier lediglich aus Gründen der Veranschaulichung beschrieben und soll in keiner Weise den Umfang der Erfindung einschränken.
Gemäß 1 enthält ein System 100 gemäß einem Ausführungsbeispiel einen digitalen Signalprozessor 10 und einen Butterfly-Coprozessor 28. Digitale Signalprozessoren oder DSPs sind speziellen Mikroprozessoren mit Architekturen, die an die digitale Signalverarbeitung angepaßt sind. DSPs enthalten üblicherweise Schaltungen, die arithmetische Hochgeschwindigkeitsoperationen, Datenübertragungen zu und aus externen Einrichtungen und Mehrfachzugriffe auf Speicher ausführen können. Die DSPs enthalten parallele erweiterte 16- oder 32-Bit-Busse, spezielle Datenadreßgeneratoren zum Zugreifen auf einen Speicher und Multipliziere-Akkumuliere (MAC)-Arithmetikeinheiten.
In 1 enthält der DSP 10 zwei Busse, einen Speicher-Speichere-Bus 22 und einen Speicher-Lade-Bus 24. Der Speicher-Speichere-Bus 22 und der Speicher-Lade-Bus 24 erstrecken sich über den digitalen Signalprozessor 10 zur Verbindung mit einem Speicher 30 hinaus. Bei einer zweiten Ausführungsform sind der Speicher-Speichere- und der Speicher-Lade-Bus 22 und 24 zu einem Bus kombiniert.
Eine Arithmetikeinheit 20 ist mit dem Speicher-Speichere-Bus 22 und dem Speicher-Lade-Bus 24 gekoppelt. Die Arithmetikeinheit 20 kann eine oder mehrere Multipliziere-Akkumuliere-Einheiten, Register und andere Schaltungen zum Ausführen arithmetischer Operationen enthalten. Darüber hinaus ist mit dem Speicher-Speichere-Bus 22 und dem Speicher-Lade-Bus 24 ein Datenadreßgenerator 26 gekoppelt. Der Datenadreßgenerator 26 identifiziert den bestimmten Ort in dem Speicher 30, aus dem entweder geladen oder in den gespeichert werden soll. Der Datenadreßgenerator 26 führt diese Operationen für andere Schaltungen des DSP 10, wie beispielsweise die Arithmetikeinheit 20, aus.
Bei einem Ausführungsbeispiel enthält das System 100 ferner einen Butterfly-Coprozessor 28. Der Butterfly-Coprozessor 28 ist nicht Teil des DSP 10, sondern ist mit dem DSP 10 über den Speicher-Speichere- und den Speicher-Lade-Bus 22 und 24 gekoppelt. Wie auch die Arithmetikeinheit 20 hat der Butterfly-Coprozessor 28 Zugriff auf den Speicher 30 unter Verwendung dieser Busse. Wie es nachfolgend näher beschrieben wird, kann das System 100 in Decodierern verwendet werden, um eine Trellis-Diagramm-Decodierung codierter Kanalbitströme durchzuführen.
Der spezielle DSP 10 dient nur der Veranschaulichung. Die Konfiguration der Schaltung gemäß 1 ist angegeben, um eine von verschiedenen möglichen Implementierungen des Systems 100 zu veranschaulichen. DSPs enthalten üblicherweise weitere Komponenten, wie beispielsweise Register, Steuerblöcke, Schaltungen zum Ausführen eines Direktspeicherzugriffs (DMA) und andere Schaltungen, welche nicht in 1 beschrieben sind. DSPs können mit einem einzigen oder mit mehreren Speicherbussen implementiert sein und können zusätzliche Busse aufweisen, wie beispielsweise für einen Peripheriegerätezugriff.
Der DSP 10 führt ein Speichermanagement für den Butterfly-Coprozessor 28 für die Ausführung von parallelen Butterfly-Operationen hoher Geschwindigkeit aus. Bevor das System 100 im Detail beschrieben wird, soll jedoch eine Einführung in Codierungs- und Decodierungstechniken als Grundlage für das Verständnis der Erfindung zur Verfügung gestellt werden.
Wenn ein Informationsdatenstrom über ein Kanalmedium übermittelt wird, gibt es verschiedene mögliche Wege, Fehler zu korrigieren. Wenn beispielsweise die Fehlerrate zu hoch ist, kann die Senderleistung erhöht werden, um die Fehlerrate zu reduzieren. Bei einigen Anwendungen, wie beispielsweise Mobiltelefonen, ist diese Lösung nicht durchführbar, weil die zur Verfügung stehende Batterieleistung in ihrer Größe begrenzt ist.
Eine andere Lösung könnte darin bestehen, die Übertragung zu duplizieren, indem entweder der gleiche Informationsdatenstrom zweimal über dasselbe Kanalmedium gesendet wird oder indem der Datenstrom über zwei verschiedene Kanäle gesendet wird. Die Duplikatdatenströme können dann miteinander am Empfänger verglichen werden. Redundanz neigt jedoch dazu, die Kosten eines Systems zu erhöhen, und könnte die Zeit für eine Verarbeitung des Informationsdatenstroms ebenso erhöhen.
Eine dritte Möglichkeit könnte für den Empfänger darin bestehen, einen automatischen Wiederholungsanforderungs(ARQ)-Mechanismus zu benutzen. Wenn der Empfänger feststellt, daß die Fehler während der Übertragung auftraten, könnte er ein erneutes Senden des Datenstroms anfordern. Dies ist jedoch kein Codierschema und könnte somit keine gute Lösung für verrauschte Kanäle sein.
Die Vorwärtsfehlerkorrektur (Forward Error Correction) ist eine Technik, bei der zusätzliche Bits zu einem Datenstrom von Informationen vor der Übertragung über einen Kanal hinzugefügt werden. Sobald er gesendet ist, könnte ein Empfänger einen Decodierer enthalten, der irgendwelche Fehler korrigiert, die während der Übertragung aufgetreten sein könnten.
Faltungscodes, die auch binäre Faltungscodes oder BCC (Binary Convolutional Codes) genannt werden, werden aus einem kontinuierlichen Strom eingehender Daten erzeugt. Im Unterschied dazu ergeben sich Blockcodes, wenn der Codierer den eingehenden Datenstrom vor seiner Codierung in Blöcke fester Länge aufteilt. Sowohl Faltungscodes als auch Blockcodes sind Arten von Vorwärtsfehlerkorrekturcodes.
In gleicher Weise sind viele Decodierer dafür bekannt, daß sie sowohl Block- als auch Faltungscodes decodieren. Der Viterbi-Decodieralgorithmus beispielsweise ist für die Decodierung von Faltungscodes populär. Der Viterbi-Algorithmus ist ein „Hard”-Ausgabe-Algorithmus, was bedeutet, daß sich die tatsächlichen Informationsbits aus einer erfolgreichen Ausführung des Algorithmus ergeben. Alternativ dazu ist der Maximale-a-posteriori-Wahrscheinlichkeits(MAP)-Algorithmus ein „Soft”-Ausgabe-Algorithmus, der Wahrscheinlichkeiten oder „Qualitäts”-Informationen über den Wert eines Kanalbits erzeugt.
In jüngster Zeit versprechen Turbo-Decodierer bessere Ergebnisse für kanal-codierte Daten. Turbo-Decodierer enthalten mehrere Decodierer, wie beispielsweise mehrere MAP-Decodierer, welche um ein korrektes Ergebnis miteinander wetteifern (arbitrate). Eine Implementierung eines Turbo-Codierers ist unten anhand von 16 beschrieben.
In 2 ist ein Codierer 50 ein einfacher rekursiver systematischer Faltungscodierer (RSC-Codierer). Ein systematischer Code ist ein Code, bei dem Paritätsbits P_k ₊₁ mit Informationsbits U_k ₊₁ als kontinuierliche Gruppe verbunden werden. Der Codierer 50 gemäß 2 erzeugt systematische Codes. Der Codierer 50 ist rekursiv, weil der Ausgangswert P_k+1 zu einem Eingangswert U_k für eine nachfolgende Verarbeitung zurückgekoppelt wird.
Bei dem RSC-Codierer 50 wird ein Informationsbit U_k in ein Exklusiv-ODER-Gatter oder XOR-Gatter 56 eingespeist. Das Ergebnis wird dann in ein Schieberegister 52 eingegeben. Der frühere Wert des Schieberegisters 52, entweder eine „1” oder eine „0”, wird in ein zweites Schieberegister 54 eingegeben. Codewortbits U_k+1 und P_k+1 werden als Funktionen des aktuellen Zustands, wie er in den Schieberegistern 52 und 54 gespeichert ist, sowie des Eingabewerts U_k erzeugt. Bei dem Codierer 50 gemäß 2 ist das Codewortbit U_k ₊₁ zufällig das gleiche wie der Eingabewert U_k. Das Paritätsbit P_k ₊₁ jedoch ergibt sich aus sowohl dem Zustand (Schieberegister 52 und 54) als auch dem Eingabewert U_k. Zusammen sind U_k+1 und P_k+1 die Codewortbits für die Zeit k + 1.
Bei Faltungscodes ist somit jedes codierte Bitpaar (U_k+1, P_k+1) von dem Eingabewert U_k, welcher einer einer Vielzahl von Informationsbits ist, sowie von den Werten in den Schieberegister 52 und 54 abhängig. Die Schieberegister 52 und 54 speichern Informationen über die vergangenen Werte des Eingabewerts U_k. Nachfolgende Bits U_k+n, P_k+n für n = 1 bis zur Größe des Informationsdatenstroms, sind somit von den vergangenen oder früheren Bits nicht unabhängig.
In 3 weist eine Zustandsübergangstabelle 60 in den Schieberegistern 52 und 54 gespeicherte Werte, die auch als Zustand des Codierers 50 bekannt sind, für jeden Eingabewert U_k (Spalte 0) auf. Die Zustandsübergangstabelle 60 enthält ferner Bits (U_k+1, P_k+1), die von dem RSC-Codierer 50 gemäß 2 erzeugt worden sind, die sich aus den Eingabewerten U_k (Spalte 2) ergeben. Die Zustandsübergangstabelle 60 zeigt den Zustand des Codierers 50 sowohl zum Zeitpunkt k (Spalte 1) als auch zum Zeitpunkt k + 1 (Spalte 3). Die Zustandsübergangstabelle 60 liefert somit eine vollständige Darstellung der Ausgabewerte U_k+1, P_k+1 des Codierers 50 für einen gegebenen Eingabewert U_k sowie liefernden Zustandsinformationen, die in den Schieberegistern 52 und 54 gespeichert sind.
Aus der Zustandsübergangstabelle 60 kann eine Trellis 70 (= ”tree-like structure”) erzeugt werden, wie es in 4 gezeigt ist. Eine Trellis ist eine Zustandsmaschine, die die möglichen Übergänge eines Codierers zwischen zwei Zuständen zeigt. Die Trellis 70 gemäß 4 besteht aus vier Knoten 72k in Stufe k, die mit 00, 01, 10 und 11 bezeichnet sind. (Die Schreibweise 72stufe wird verwendet, um sämtliche Knoten 72 bei einer bestimmten Stufe zu beschreiben).
Die Trellis 70 enthält ferner vier Knoten 72k+1 in Stufe k + 1, die ebenfalls mit 00, 01, 10 und 11 bezeichnet sind. Die Zustände 00, 01, 10 und 11 entsprechen den Werten in den Schieberegistern 52 und 54 des Codierers 50. Die Knoten 72k und 72k+1 repräsentieren den Zustand des Codierers 50 bei den Stufen k beziehungsweise k + 1, wie er in den Spalten 0 beziehungsweise 3 der Zustandsübergangstabelle 60 gemäß 3 gezeigt ist.
Die Knoten 72k mit den Knoten 72k+1 verbinden Zweige 74. Die zwei Zweige 74 zeigen an, daß es zwei mögliche Werte für U_k, 0 oder 1 gibt, welche sich von irgendeinem der vier möglichen Zustände 00, 01, 10 und 11, erstrecken können.
An jedem Zweig 74 der Trellis 70 sind der Eingabewert U_k sowie die Ausgabebits U_k+1, P_k+1 in der Form (U_k, U_k+1, P_k+1) dargestellt. Jeder Zweig 74 identifiziert einen Übergang des Codierers 50 für einen Eingabewert U_k aus dem Zustand links von dem Zweig 74 (in Stufe k) zu dem Zustand rechts von dem Zweig 74 (in Stufe k + 1).
Wie eine Trellis ist ein Trellis-Diagramm eine Zustandsmaschine, die verwendet wird, um das Verhalten eines Codierers zu beschreiben. Das Trellis-Diagramm jedoch demonstriert sämtliche möglichen Zustandsübergänge des Codierers über der Zeit. In 5 enthält ein Trellis-Diagramm 80 mögliche Zustandsübergänge für den RSC-Codierer 50 gemäß 2. Das Trellis-Diagramm 80 ist einfach eine serielle Verkettung der Trellis 70 gemäß 4.
Es sind vier Zustände 72 in dem Trellis-Diagramm 80 möglich: 00, 01, 10 und 11 (man erinnere sich, daß die Zustände 72 den Schieberegistern 52 und 54 des Codierers 50 entsprechend). Die Variable k repräsentiert eine Stufe des Trellis-Diagramms 80. Jede Stufe ist ein bestimmter Zeitpunkt, wobei k = 0 am Beginn des Trellis-Diagramms 80 zum Zeitpunkt 0 ist, k = 1 zu einem nachfolgenden Zeitpunkt ist und so weiter. Das Trellis-Diagramm 80 kann entsprechend der Anzahl von Informationsbits U_k, die dem Codierer 50 eingegeben werden, Hunderte oder sogar Tausende von Stufen enthalten. In 5 sind nur die ersten zehn Stufen des Trellis-Diagramms 80 gezeigt.
Wie auch die Trellis 70 gemäß 4 enthält das Trellis-Diagramm 80 vier Knoten 72 in jeder Stufe k. Die Zustände 00, 01, 10 und 11 sind sequentiell in einer Spalte links von dem Trellis-Diagramm 80 aufgelistet. Jeder der vier Knoten 72 in Stufe k repräsentiert einen der Zustände 00, 01, 10 oder 11. Darüber hinaus erstrecken sich ausgehend von jeden Knoten 72 Zweige 74, wobei ein Zweig jeweils einen Übergang aus den Knoten 72k zu den Knoten 72k+1 darstellt.
In dem 0-ten Zustand erstrecken sich nur zwei Zweige 74 von dem Knoten 72, der den Zustand 00 darstellt. Bei einem Ausführungsbeispiel wird von dem Codierer 50 vorausgesetzt, daß er die Codierung mit einem Wert 0 in dem Schieberegister 52 sowie einem Wert 0 in dem Schieberegister 54 beginnt. Somit sind die übrigen Zustände 01, 10 und 11 in der 0-ten Stufe „unmöglich”, und es erstrecken sich keine Zweige ausgehend von diesen Zuständen.
In der nächsten Stufe (k = 1) erstrecken sich Zweige 74 ausgehend von den Knoten 72, die die Zustände 00 und 10 darstellen, da dies die möglichen Übergänge von der 0-ten Stufe bei gegebenen Eingabewerten 0 und 1 sind. Vom Zustand 10 erstrecken sich Zweige 74 zu den anderen beiden möglichen Zuständen 01 und 11. Somit ist von k = 2 an jede Stufe k mit der Stufe k + 1 identisch und exakt so, wie es in der Trellis 70 gemäß 4 dargestellt ist.
Das Trellis-Diagramm 80 stellt eine vollständige Darstellung des Codierers 50 zur Verfügung: die Eingabewerte, die Zustände und die Ausgabewerte. Durch Verbinden von Zweigen 74 in jeder Stufe k stellt ein Pfad 82, wie beispielsweise in 6, ein codiertes binäres Ausgabecodewort 86, 101110100101000111, für den binären Eingabewert 84, 111100001, dar, wobei k = 9 ist. Der Pfad 82 stellt jedoch nur einen von vielen möglichen Pfaden durch das Trellis-Diagramm 80 dar.
Es sei angenommen, daß der Codierer 50 gemäß 2 den 9-Bit-Informationsdatenstrom 84 mit dem Wert 111100001 empfängt und das binäre 18-Bit-Faltungscodewort 86 mit einem Wert 1011101001000111 erzeugt, wie es in 6 gezeigt ist. Das Codewort 86 wird dann über ein Kanalmedium 90 an einen Empfänger 94 gesendet, welcher einen Decodierer 96 enthält, wie es in 7 gezeigt ist. Der Decodierer 96 empfängt einen Kanalbitstrom 92, welcher der gleiche Bitstrom sein kann wie das Faltungscodewort 86 oder auch nicht.
Der Decodierer 96 erzeugt einen Informationsdatenstrom 98 aus dem Kanalbitstrom 92. Wenn der Informationsdatenstrom 98 identisch dem Informationsdatenstrom 84 ist, so hat der Decodierer 96 den Kanalbitstrom 92 erfolgreich decodiert.
Wegen des Rauschens oder anderer Phänomene in dem Kanalmedium 90 kann der Kanalbitstrom 92 sich oftmals von dem Codewort 86, das über den Kanal 90 gesendet worden ist, unterscheiden. Das Faltungswort 86 jedoch enthält nicht bloß Informationsbits (U_k) sondern auch Paritätsbits (P_k), welche auf den ursprünglichen Informationsbits basieren. Obwohl sich einige Bits unterscheiden können, enthält der Kanalbitstrom 92 in gleicher Weise sowohl Informations- als auch Paritätsbits. Der Decodierer 96 verwendet diese Informationen sowie ein Trellis-Diagramm, welches einen „Blue Print” des Codierers zur Verfügung stellt, um den richtigen Informationsdatenstrom 96 zu extrahieren.
Ein fundamentales Konzept beim Decodieren unter Verwendung von Trellis-Diagrammen besteht darin, daß die codierte Sequenz äquivalent einen Pfad ist, wie beispielsweise dem Pfad 82 gemäß 6 in dem Trellis-Diagramm 80. Der Pfad stellt somit sowohl die Eingabesequenz U_k an den Codierer 50 als auch die Ausgabesequenz U_k+1, P_k+1 aus dem Codierer 50 zur Verfügung, wie es an den Zweigen 74 spezifiziert ist. Irgendwo in dem Trellis-Diagramm 80 könnte der Decodierer 96 den richtigen Pfad 82 aufdecken.
Demzufolge beruhen dort, wo ein Codierer beschrieben wird, der ein Trellis-Diagramm verwendet, die ihm zugeordneten Decodieralgorithmen typischerweise auf dem Trellis-Diagramm 80 zum Rekonstruieren der Eingangssequenz U_k. Der Decodierer 96 entscheidet, bei dem gegebenen Kanalbitstrom 92, welcher Pfad 82 des Trellis-Diagramms 80 der wahrscheinlichste Pfad ist.
Um zu verstehen, wie der Decodierer 96 mit dem Trellis-Diagramm 80 arbeitet, sei die Darstellung der 8 betrachtet. Sechs mit 0 bis 5 bezeichnete Stufen k des Vier-Zustande-Trellis-Diagramms 80 der 5 sind gezeigt. Bei Hard-Ausgabe-Decodieralgorithmen kann der Decodierer 96 an jeder Stufe k bestimmen, ob das codierte Bit ein „1”-Bit oder ein „0”-Bit war. Im Gegensatz dazu wird dann, wenn der Decodierer 96 Soft-Eingabe/Soft-Ausgabe (SISO)-Algorithmen verwendet, die Qualität eines gegebenen Pfades 82 des Trellis-Diagramms 80 bewertet. Der Decodierer 96 liefert somit Wahrscheinlichkeitsdaten anstelle eines „1”- oder „0”-Bits. Demzufolge wird bei Soft-Ausgabe-Algorithmen der Pfad 82 unter Verwendung einer Zahl definiert, die als Metrik bekannt ist. Die Metrik stellt die Wahrscheinlichkeit dar, mit der ein Pfad in dem Trellis-Diagramm 80 bei einem von dem Decodierer 96 empfangenen gegebenen Kanalbitstrom 92 eingeschlagen wird.
Bei dem RSC-Codierer 50 gemäß 2 entsprechen die zwei möglichen Eingabewerte von U_k, 0 oder 1, den zwei möglichen Zweigen 74, die sich von jedem Knoten 72 aus erstrecken. So erstrecken sich in 8 bei der Stufe 1 zwei Zweige 74 von dem Knoten 72 für den „10”-Zustand. Ebenso wird jedem Zweig 74 eine Wahrscheinlichkeit oder eine Zweig-Metrik 106 zugeordnet. In 8 ist die Zweig-Metrik 106 eine den Zweig 104 bezeichnende Zahl. Der obere Zweig 74a weist eine Zweig-Metrik 106 von 0,2 auf. Der untere Zweig 74b weist eine Zweig-Metrik 106 von 0,3 auf.
Die Zweig-Metrik 106 ist eine „Soft”-Information, typischerweise eine Log-Wahrscheinlichkeit (Logarithmus einer Wahrscheinlichkeit), die bei gegebenem Kanalbitstrom 92, der von dem Decodierer 96 empfangen wird, die Wahrscheinlichkeit des Erreichens des nächsten Knotens 72 anzeigt. Der Decodierer 96 berechnet die Zweig-Metrik 106.
Bei dem Viterbi-Algorithmus besteht die Aufgabe des Decodierers 96 darin, den besten Pfad 82 aus dem Trellis-Diagramm 80 zu gewinnen. Bei Soft-Ausgabe-Algorithmen, wie beispielsweise dem MAP-Algorithmus, bestimmt der Decodierer 96 statt dessen in jeder Stufe k der Trellis die Wahrscheinlichkeit, daß das Informationsbit U_k eine 0 oder eine 1 ist. Der Decodierer 96 durchläuft somit iterativ das Trellis-Diagramm 80 stufenweise, wobei er die Wahrscheinlichkeitsinformation auf der Grundlage des empfangenen Bitstroms und des Trellis-Diagramms 80 berechnet.
Im wesentlichen berücksichtigt der Decodierer 96 sämtliche möglichen Pfade 82 des Trellis-Diagramms 80. Für jeden betrachteten Pfad 82 addiert der Decodierer 96 die Zweig-Metriken 106 für den Pfad 82 auf, was eine Pfad-Metrik 108 ergibt. Der Decodierer 96 wählt dann den Pfad 82 mit der größten Pfad-Metrik 108 aus. Der Pfad 82 mit der größten Pfad-Metrik 108 ist der Pfad mit der maximalen Wahrscheinlichkeit. Der ausgewählte Pfad 82 ist auch als der überlebende Pfad bekannt. Aus dem Pfad 82 können dann die Informationsbits U_k bestimmt werden.
Der Decodierer 96 durchläuft somit das Trellis-Diagramm 80, wobei er die Zweig-Metriken 106 und die Pfad-Metriken 108 entlang des Weges berechnet. Bei einigen Algorithmen wird das Trellis-Diagramm 80 ein einziges Mal durchlaufen. Bei anderen Algorithmen jedoch kann das Trellis-Diagramm 80 sowohl in Vorwärts- als auch Rückwärtsrichtung durchlaufen werden. Dennoch können sowohl der Viterbi- als auch der MAP-Algorithmus sowie andere Algorithmen, welche mit dem Trellis-Diagramm 80 arbeiten, eine schwindelerregende Anzahl von Berechnungen ausführen, bevor sie zu dem gewünschten Ergebnis gelangen.
Die Anzahl der möglichen Pfade 82 des Trellis-Diagramms 80 ist beispielsweise 2^{Trellis-Länge}. Wenn somit der Codierer 50 100 Informationsbits codiert, hat der Decodierer 96 2¹⁰⁰ mögliche Pfade 82 zu berücksichtigen (etwa 10³⁰ Pfade). Die Berechnung kann sogar noch komplexer werden, wenn jede der Zweig-Metriken 106 nicht in einem Speicher gespeichert wird.
Gemäß 9 enthält ein Teil des Trellis-Diagramms 80 gemäß 5 die Stufen k, k + 1 und k + 2. Ein gleitendes Fenster 110 schließt die Stufen k und k + 1 ein. Der Decodierer 96 kann das gleitende Fenster 110 verwenden, um beliebig die Zweig-Metriken 106 entlang der Trellis 80 zu berechnen.
Beispielsweise erstrecken sich in der Stufe k ausgehend von dem Knoten 72k, der dem Zustand 00 entspricht, ein Zweig 74c und ein Zweig 74d zu den Knoten 72k+1 (an der Stufe k + 1). In gleicher Weise erstrecken sich ausgehend von dem Knoten 72k, der dem Zustand 01 entspricht, zwei Zweige 74e und 74f. Vom Knoten 72k (Zustand 10) erstrecken sich die Zweige 74g und 74h und ausgehend vom Knoten 72k (Zustand 11) erstrecken sich die Zweige 74i und 74j zu dem Knoten 72k+1 (Stufe k + 1). Die Zweige 74c, 74e, 74g und 74i entsprechen einem „0”-Eingabewert in den Codierer 50, während die Zweige 74d, 74f, 74h und 74j dem 1-Eingabewert entsprechen.
Während sich das gleitende Fenster 110 in der in 9 gezeigten Position befindet, berechnet der Decodierer 96 Zweig-Metriken 106 für jeden der Zweige 74c bis 74j mit einer Gesamtanzahl von acht Berechnungen. Ausgenommen den Fall, wenn k = 0 ist, erstrecken sich ein oder mehrere Pfade 82 zu den Knoten 72k aus früheren Stufen. Einer der Pfade 82 ist der überlebende Pfad. Dementsprechend kann eine neue Pfad-Metrik 108 berechnet werden, indem die Pfad-Metrik 108 des überlebenden Pfades genommen wird. Eine erste Zweig-Metrik 106 kann zu der Pfad-Metrik 108 addiert werden, dann kann eine zweite Zweig-Metrik 106 zu der Pfad-Metrik 108 hinzugefügt werden. Die beiden Ergebnisse können verglichen werden. Der Pfad 82 mit der größeren Pfad-Metrik 108 ist der neue überlebende Pfad für die Stufe k. Diese Gruppe von Berechnungen ist als Butterfly-Operation bekannt.
Sobald die Butterfly-Operation für die Stufe k abgeschlossen ist, kann das gleitende Fenster 110 in Übereinstimmung mit dem Algorithmus vorwärts oder rückwärts bewegt werden, so daß die nächste Gruppe von Butterfly-Operationen ausgeführt werden kann.
Für das gleitende Fenster 110 der 9 können bis zu vier Butterfly-Operationen ausgeführt werden, jeweils eine für jeden Knoten 72k. Die Zweig-Metrik 106 jedes Zweiges 74 wird zu der Pfad-Metrik 108 addiert (Additionsoperation). Jede sich ergebende Pfad-Metrik 108 wird dann mit der anderen Pfad-Metrik 108 verglichen, um festzustellen, welches Ergebnis das größere ist (Vergleichsoperation). Die resultierende Pfad-Metrik 108 beziehungsweise der überlebende Pfad wird ausgewählt (Auswahloperation). Die Butterfly-Operation ist somit manchmal als Additions-Vergleichs-Auswahl- oder ACS-Operation (Add-Compare-Select Operation) bekannt. Schließlich wird der überlebende Pfad gespeichert, wie beispielsweise in einem Speicher.
Gemäß 10 kann gemäß einem Ausführungsbeispiel ein System 200 zum Ausführen von Butterfly-Operationen, wie beispielsweise den oben beschriebenen, verwendet werden. Das System 200 enthält eine oder mehrere Butterfly-Einheiten (BU) 202, eine Zweig-Metrik-Einheit 204 und einen Pfad-Metrik-Speicher 206. Gemeinsam können die Schaltungen des Systems 200 die ACS- oder Log-MAP-Butterfly-Operation ausführen.
Bei einem Ausführungsbeispiel führt die Zweig-Metrik-Einheit 204 die Berechnungen für die Zweig-Metriken 106 aus, die oben in 8 beschrieben sind. Die Zweig-Metriken 106 werden berechnet, indem die Kanaldaten 92 sowie die vier möglichen Ausgangswerte U_k+1, P_k+1, die von dem Codierer 50 erzeugt würden, analysiert werden und eine wahrscheinliche Metrik 106 berechnet wird. Zweig-Metriken 106 werden für jeden Knoten 72k berechnet. Man beachte, daß die Zweig-Metrik-Einheit 204 nicht mit dem Pfad-Metrik-Speicher 206 verbunden ist, da die Pfad-Metrik 108 aus einer früheren Stufe nicht beim Berechnen der Zweig-Metriken 106 berücksichtigt wird.
Bei dem Ausführungsbeispiel gemäß 10 empfängt jede Butterfly-Einheit 202 eine Zweig-Metrik 106 aus der Zweig-Metrik-Einheit 204. Da es vier Knoten 72 in jeder Stufe k gibt, werden vier Butterfly-Einheiten 202 zur Verfügung gestellt. Somit kann gemäß einem Ausführungsbeispiel jede Butterfly-Einheit 202 Berechnungen parallel zu jeder anderen Butterfly-Einheit 202 ausführen, so daß neue Pfad-Metriken für jeden Zustand 00, 01, 10 und 11 gleichzeitig berechnet werden können.
Darüber hinaus empfängt jede Butterfly-Einheit 202 eine Pfad-Metrik 108 aus dem Pfad-Metrik-Speicher 206. Mit diesen Informationen können die Butterfly-Einheiten 202 jeweils Additions-Auswahl-Vergleichs-Operationen für einen gegebenen Knoten 72k des Trellis-Diagramms 80 ausführen.
Der Ausgabepfad jeder Butterfly-Einheit 202 ist außerdem mit dem Pfad-Metrik-Speicher 206 gekoppelt. Jede Butterfly-Einheit 202 kann somit die sich ergebende Pfad-Metrik an den Pfad-Metrik-Speicher 206 zur Speicherung senden, bis ein neuer Satz von Butterfly-Operationen an der Stufe k + 1 ausgeführt wird.
Gemäß 11 implementiert ein zweites Ausführungsbeispiel des Systems 200 den hier beschriebenen MAP-Algorithmus. Der Decodierer 96 kann das System 200 verwenden, um Trellis-Operationen sowohl in Vorwärts- als auch Rückwärtsrichtung an dem Trellis-Diagramm 80 auszuführen. Der MAP-Algorithmus ist ein Zwei-Pfade-Algorithmus, bei dem Trellis-Operationen sowohl in Vorwärts- als auch Rückwärtsrichtung bezüglich des Trellis-Diagramms ausgeführt werden. In sowohl dem Vorwärts- als auch dem Rückwärtsdurchlauf werden Trellis-Knoten-Metriken berechnet.
Während des Vorwärtsdurchlaufs können die Knoten-Metriken in dem Pfad-Metrik-Speicher 206 gespeichert werden. Dann werden während des Rückwärtsdurchlaufs die Metriken des gleitenden Fensters berechnet, dann mit den Vorwärts-Pfad-Metriken, die in den Knoten-Metrik-Speicher 206 gespeichert sind, kombiniert. Alternativ könnte der Rückwärtsdurchlauf dem Vorwärtsdurchlauf in der beschriebenen Weise vorangehen.
Die Trellis weist N Zustände an jeder Stufe auf. Das System 200 gemäß 11 reduziert die Metriken für sämtliche N Zustände sowohl in der Vorwärts- als auch in der Rückwärtsrichtung auf eine Einzelbit-Zuverlässigkeits-Metrik. Dies ist die endgültige Soft-Ausgabe des MAP-Algorithmus.
Unter Verwendung der Anordnung der Butterfly-Einheiten 202, wie sie in 11 gezeigt ist, können somit sowohl eine Vorwärts-Pfad-Metrik als auch eine Rückwärts-Pfad-Metrik berechnet werden. Die oberen drei Butterfly-Einheiten 202 werden für die „1”-Zweige 104 verwendet, während die unteren drei Butterfly-Einheiten 202 für die „0”-Zweige 104 verwendet werden.
In 11 berechnet die Zweig-Metrik-Einheit (BMU; Branch Metric Unit) 204 gemäß einem Ausführungsbeispiel die aktuellen Zweig-Metriken 74 für die Stufe k. Die Butterfly-Einheiten 202 lesen dann eine Vorwärts-(oder eine Rückwärts)Pfad-Metrik 108 aus dem Pfad-Metrik-Speicher 206 sowie die Zweig-Metriken 74 aus der Zweig-Metrik-Einheit 204. Dann kombiniert jede Butterfly-Einheit 202 jeweils zwei der Ergebnisse und subtrahiert die Differenz, um einen A-posteriori-Wahrscheinlichkeitswert zu erzeugen.
Gemäß 12 ist das System 200 der 10 in dem System 100 (1) gemäß einem Ausführungsbeispiel implementiert. Wie erwartet, ist der Pfad-Metrik-Speicher 206 Teil des größeren zur Verfügung stehenden Speichers 30. Auf den Pfad-Metrik-Speicher 206 kann von dem Rest der Schaltung über den Speicher-Speichere-Bus 22 und dem Speicher-Lade-Bus 24 zugegriffen werden.
Gemäß 12 ist die Zweig-Metrik-Einheit 204 Teil der Arithmetikeinheit 20. Die Zweig-Metrik-Einheit 204 benötigt keinen Zugriff auf den Pfad-Metrik-Speicher 206 zum Ausführen ihrer Berechnungen. Statt dessen liefert die Zweig-Metrik-Einheit 204 Informationen an die Butterfly-Einheiten 202.
Dementsprechend enthält bei einem Ausführungsbeispiel die Arithmetikeinheit 20 Register 210, die von dem Datenadreßgenerator 26 adressierbar sind. Beim Abschluß einer Operation speichert die BMU 204 ein Ergebnis in den Registern 210. Die Butterfly-Einheiten 202 können dann die Ergebnisse der Operationen der BMU 204 erlangen, indem sie auf die Register 210 unter Verwendung des Datenadreßgenerators 26 gerade so zugreifen, wie auf den Speicher 30 zugegriffen wird.
Bei einem Ausführungsbeispiel enthält der Butterfly-Coprozessor 28 die vier Butterfly-Einheiten 202. Um die Butterfly-Berechnungen auszuführen, greifen die Butterfly-Einheiten 202 unter Verwendung des Datenadreßgenerators 26 und des Speicher-Lade-Busses 24 auf den Pfad-Metrik-Speicher 206 und die Register 210 zu. Die Butterfly-Einheiten 202 führen dann die Additions-Vergleichs-Auswahl-Operationen aus, um die Pfad-Metrik 108 für die Knoten 72 an der aktuellen Stufe in dem gleitenden Fenster 110 zu berechnen. Sobald die Butterfly-Operationen abgeschlossen sind, speichern die Butterfly-Einheiten 202 die Ergebnisse in dem Pfad-Metrik-Speicher 206, indem die Ergebnisse auf den Speicher-Speichere-Bus 22 gebracht werden.
Bei dem Ausführungsbeispiel gemäß 12 führt der DSP 10 das Speichermanagement für den Butterfly-Coprozessor 28 durch. Darüber hinaus jedoch führt der DSP auch einen Teil der Butterfly-Operationen aus, indem er die Operationen der Zweig-Metrik-Einheit 204 in seinen Arithmetikeinheiten 20 einschließt. Dies ermöglicht es dem Butterfly-Coprozessor 28, seine gesamte Aufmerksamkeit der parallelen Ausführung der verschiedenen Knotenoperationen durch die Butterfly-Einheit 202 zu widmen.
Es sind andere Ausführungsbeispiele zum Implementieren des Systems 200 gemäß 10 möglich. Beispielsweise speichert gemäß 12 die Zweig-Metrik-Einheit 204, sobald die Zweig-Metrik-Einheit 204 die Zweig-Metriken 106 berechnet hat, die Ergebnisse in den in den Arithmetikeinheiten 20 angeordneten Registern 210. Der Datenadreßgenerator 26 greift dann auf die Register 210 bei Anforderung des Butterfly-Coprozessors 28 zu.
Alternativ könnte die Zweig-Metrik-Einheit 204 in dem Butterfly-Coprozessor 28 selbst angeordnet sein. Die alternative Konfiguration vermeidet die Notwendigkeit der Register 210, da die Zweig-Metrik-Einheit 204 direkt mit den Butterfly-Einheiten 202 verbunden sein kann. Der Butterfly-Coprozessor 28 führt sowohl die Operationen der Zweig-Metrik-Einheit als auch die Additions-Vergleichs-Auswahl-Operationen durch.
Darüber hinaus kann bei einigen Ausführungsbeispielen das System 100 programmierbar sein. Beispielsweise können Register die Verbindung (connectivity) zwischen der Zweig-Metrik-Einheit 204 und dem DSP 10 definieren. Ob er nun einfach für das Speichermanagement implementiert ist oder zum Durchführen eines Teils der Butterfly-Operationen, der DSP 10 kann in die Trellis-Decodierung auf einer stufenweise Grundlage involviert sein. Bei einem Ausführungsbeispiel stellt der DSP 10 eine Speicherschnittstelle für den Butterfly-Coprozessor 28 zur Verfügung. Bei einigen Ausführungsbeispielen führt der DPS 10 zusätzlich eine algorithmische Einplanung für den Butterfly-Coprozessor 28 aus.
Der Butterfly-Coprozessor 28 implementiert somit parallele Butterfly-Operationen unter Verwendung mehrere Butterfly-Einheiten. Bei einem Ausführungsbeispiel erhöht das System 100 den Durchsatz der Ausführung der beim Decodieren eines Kanalbitstroms auftretenden sehr komplexen Operationen.
Bei einem Ausführungsbeispiel enthält das System 100 ein Software-Programm 500, das als in dem Speicher 30 gespeichert gezeigt ist. Unter Verwendung des Software-Programms 500 kann das System 100 flexibel für eine Reihe von Decodierschemata implementiert werden. Darüber hinaus kann immer dann, wenn eine neue Decodiertechnik entwickelt wird, ein neues Software-Programm in das System 100 geladen werden.
Gemäß 13 verwaltet das Software-Programm 500 die Decodieroperation gemäß einem Ausführungsbeispiel, indem es eine Decodieranforderung empfängt (Block 502). Bei dem Ausführungsbeispiel gemäß 12 werden die Pfad-Metriken 108 in dem Pfad-Metrik-Speicher 206 gespeichert. Demzufolge könnte das Software-Programm 500 den Speicher 30 unter Verwendung des Datenadregenerators 26 adressieren, um die Pfad-Metriken 108 aus der Pfad-Metrik Einheit 206 wiederzugewinnen (Block 504). Die Pfad-Metriken 108 können dann an den Butterfly-Coprozessor 28 gesendet werden.
Es wird wieder auf 10 Bezug genommen; zusätzlich zum Empfangen der Pfad-Metriken 108 empfangen die Butterfly-Einheiten 202 außerdem die Zweig-Metriken 106 als Eingangswerte. Demzufolge weist gemäß 13 das Software-Programm 500 die Zweig-Metrik-Einheit 204 an, ihre Zweig-Metrik-Berechnungen auszuführen (Block 506). Das Ergebnis könnte dann in den Registern 210, in dem Speicher 30 gespeichert oder direkt auf den Speicher-Speichere-Bus 22 gebracht werden, um an den Butterfly-Coprozessor 28 gesendet zu werden.
Das Software-Programm 500 weist somit das System 100 an, die Pfad-Metrik 108 und die Zweig-Metrik 106 an den Butterfly-Coprozessor 28 zu senden (Block 508). Der Butterfly-Coprozessor 28 kann dann parallel Butterfly-Operationen ausführen (Block 510). So werden die Trellis-Berechnungen für eine einzelne Stufe von dem System 100 ausgeführt. Die Operation der Software 500 gemäß einer Ausführungsform ist abgeschlossen.
Die Butterfly-Einheit 202 kann auf verschiedene Weise implementiert werden. Gemäß den 10 und 11 empfangen die Butterfly-Einheiten 202 jeweils zwei Eingabewerte, einen aus dem Pfad-Metrik-Speicher 206 und den anderen aus der Zweig-Metrik-Einheit 204. Die Butterfly-Einheiten 202 erzeugen dann einen einzigen Ausgabewert, der an den Pfad-Metrik-Speicher 206 gesendet wird.
Gemäß 14a wird die Butterfly-Einheit 202 gemäß einem Ausführungsbeispiel unter Verwendung algorithmischer Summiere-Exponential-Operationen implementiert. Zusätzlich zum Empfangen eines Werts aus dem Pfad-Metrik-Speicher 206 und der Zweig-Metrik-Einheit 204 empfängt die Butterfly-Einheit 202 einen Parameter c. Der Parameter c kann je nachdem, wie es gewünscht ist, in die Butterfly-Einheit 202 fest verdrahtet oder programmierbar sein. Die folgenden Formeln können in der Butterfly-Einheit 202 als diskrete Logik implementiert werden: Z = c lag (e^x/c + e^y/c) = max(x, y) + c log(1 + e^diff/c)
Gemäß 14b führt die Butterfly-Einheit 202 eine max-Operation aus. Die Butterfly-Einheit 202 enthält eine max-Einheit 220, welche sowohl das Maximum als auch die Differenz der Eingabewerte x und y berechnet. Der maximale Ausgabewert wird an einen Addierer 224 gesendet. Der Differenz wird an eine Nachschlagetabelle 222 gesendet, wobei deren Ergebnis dann in den Addierer 224 eingespeist wird. Andere Algorithmen zum Durchführen von Additions-Vergleichs-Auswahl-Operationen sind gut bekannt und können in der Butterfly-Einheit 202 implementiert werden.
Unter Verwendung des Systems 100 können insbesondere bei komplexen Codierschemata substantielle Vorteile verwirklicht werden. Beispielsweise sind Turbo-Codes eine neuere Entwicklung bei der FEC-Kanalcodierung. Turbo-Codes werden in Betracht gezogen für eine Verwendung sowohl bei Breitband- als auch „Code Division Multiple Access”(CDMA)-Standards der dritten Generation (3G), die bei Mobiltelefonen verwendet werden.
Gemäß 15 ist ein Turbo-Codierung 300 ein gut bekanntes Ausführungsbeispiel, das bei der 3G-CDMA-Cellular-Technologie verwendet werden soll. Der Codierer 300 wirkt an einem Block Daten, der in seiner Größe von 320 bis 5120 Bits reichen kann. Ein Block wird parallel von zwei einen Bestandteil bildenden Faltungscodes oder RSC-Codierern 302 und 304 codiert. Vor dem Codieren durch den RSC-Codierer 304 wird der eingegebene Datenblock 310 unter Verwendung eines Verschachtelers 306 bit-verschachtelt.
Durch Verschachteln (interleaving) des Datenblocks 310 vor seinem Senden an den RSC-Codierer 304 ist der Turbo-Codierer 300 wesentlich leistungsfähiger als dann, wenn ein einziges Mal codiert wird. Nach dem Durchlaufen der RSC-Codierer 302 und 304 können der codierte Block 312 und der codierte Block 314 separat über den Kanal 90 (5) gesendet oder kombiniert werden, wie es gewünscht wird.
Im Vergleich zur herkömmlichen Faltungscodierung sind die den Bestandteil bildenden Codes, die bei Turbo-Codierern verwendet werden, viel weniger komplex. Systeme der dritten Generation beispielsweise verwenden einen k9-Faltungscodes für Steuerkanäle, Sprache und Datenverbindungen mit Raten unter 32 kbps. Der k9-Code weist 256 Zustände auf. Im Gegensatz dazu können die Turbo-Bestandteilcodes beispielsweise nur acht Zustände haben.
Gemäß 16 enthält ein Turbo-Decodierer 400 zwei Soft-Eingabe/Soft-Ausgabe(SISO)-Decodierer 406 und 408. Jeder Decodierer 406 und 408 empfängt einen Kanalbitstrom 402 bzw. 404. Der Kanalbitstrom 402 entspricht dem codierten Block 312 der 15. Der Kanalbitstrom 404 entspricht dem codierten Block 314 der 15.
Wie der Turbo-Codierer 300 ist auch der Turbo-Decodierer der 16 gut bekannt. Der SISO-Decodierer 406 empfängt den Kanalbitstrom 402. Nach dem Decodieren werden die Ausgabewerte über einen Verschachteler 410 geleitet und dann von dem zweiten SISO-Decodierer 408 empfangen. Der zweite SISO-Decodierer 408 empfängt ferner den zweiten Kanalbitstrom 404. Nach dem Decodieren sendet der SISO-Decodierer 408 die Ausgabewerte an einen Entschachteler (De-Interleaver) 412, und leitet dann die entschachtelten Daten an den SISO-Decodierer 406 weiter.
Der Prozeß kann verschiedene Male wiederholt werden, bevor die endgültige Ausgabe an den Hard-Entscheidungsblock 414 gesendet wird, welcher die Daten als Hard-Ausgabewerte quantifiziert. Der Turbo-Decodierer 400 arbeitet zum Teil, weil die SISO-Decodierer 406 und 408 Soft-Eingabe und Soft-Ausgabe aufweisen. Dementsprechend können Soft-Informationen zwischen ihnen so oft, wie es gewünscht wird, weitergeleitet werden. Im wesentlichen wird ein Schiedsentscheidungsschema benutzt, um zu einem endgültigen Ausgabewert zu kommen.
Bei einem Ausführungsbeispiel ist der SISO-Decodierer 406 unter Verwendung des MAP-Algorithmus (Maximum-a-posteriori-Wahrscheinlichkeit) implementiert. Wie oben beschrieben, ist MAP ein Soft-Eingabe/Soft-Ausgabe-Algorithmus. Anstelle der Erzeugung von „Hard”-Bit-Entscheidungsausgaben sind MAP-Ausgaben A-posteriori-Wahrscheinlichkeiten (APPs), die die Wahrscheinlichkeit jedes Datenbitwerts kennzeichnen. Im Vergleich dazu, ist der Viterbi-Algorithmus ein Soft-Eingabe/Hard-Ausgabe-Decodierer.
Die MAP-Algorithmus-Komplexität ist etwa viermal so hoch wie die Komplexität des Viterbi-Algorithmus pro Zustand. Darüber hinaus ist der MAP-Algorithmus viel speicherintensiver als der Viterbi-Algorithmus. Jedoch werden beim Implementieren von Turbo-Codes nur acht Zustände berücksichtigt im Vergleich zu 256 Zuständen für den k9-Faltungscode.
Gemäß 16 wiederholt sich der Turbo-Decodierer 400 an dem MAP-Algorithmus, der in beiden SISO-Decodierern 406 und 408 verkörpert ist. Jeder Decodierer 406 und 408 kann das System 100 (12) benutzen, um den MAP-Algorithmus zu implementieren. Da der Turbo-Decodierer 400 zwei Decodierer enthält, die jeweils den MAP-Algorithmus benutzen, kann die parallele Arbeitsweise des Systems 100 zu einer substantiell schnelleren Ausführung führen als frühere Implementierungen.
Somit kann gemäß verschiedenen Ausführungsformen das System 100 bei Decodierern verwendet werden, um den Trellis-Diagrammen zugeordnete Operationen auszuführen. Der MAP-Algorithmus, der Viterbi-Algorithmus und andere führen derartige Operationen aus. Darüber hinaus kann das System 100 entweder für Soft- oder Hard-Ausgabe-Algorithmen implementiert werden. Der DSP und der Butterfly-Coprozessor arbeiten beim Ausführen dieser Operationen zusammen.
Die Aufteilung der Arbeit zwischen dem DSP und dem Butterfly-Coprozessor kann auf verschiedene Weise erreicht werden. Bei einem Ausführungsbeispiel führt der DSP das Speichermanagement und eine algorithmische Einplanung für den Butterfly-Coprozessor aus. Der Butterfly-Coprozessor implementiert parallele Butterfly-Operationen für einen erhöhten Durchsatz während der Decodierung. Darüber hinaus hält das System 100 eine Flexibilität aufrecht zur Verwendung bei einer Reihe von möglichen Decodierumgebungen.
Während die vorliegende Erfindung bezüglich einer beschränkten Anzahl von Ausführungsbeispielen beschrieben worden ist, sind Fachleuten zahlreiche Modifikationen und Variationen dieser Ausführungsformen klar. Es ist beabsichtigt, daß die beigefügten Ansprüche sämtliche derartigen Modifikationen und Variationen, soweit sie in den wahren Geist und Umfang dieser vorliegenden Erfindung fallen, abdecken sollen.

Claims

Ein System, aufweisend: einen digitalen Signalprozessor mit einem mit einem Speicher verbindbaren Bus; und mehreren mit dem Bus verbundene Butterfly-Einheiten zum Ausführen von Butterfly-Operationen, wobei die Butterfly-Einheiten eine von dem digitalen Signalprozessor eingeplante Operation ausführen, wobei die Butterfly-Operationen der Butterfly-Einheiten parallele Operationen sind, wobei der digitale Signalprozessor ferner einen mit dem Bus gekoppelten Datenadreßgenerator aufweist, wobei der Datenadreßgenerator für eine anfordernde Einrichtung den Speicher adressiert.
Das System nach Anspruch 1, wobei der digitale Signalprozessor ferner eine Arithmetikeinheit zum Ausführen arithmetischer Operationen in dem digitalen Signalprozessor aufweist.
Das System nach Anspruch 2, wobei die Arithmetikeinheit ferner eine Zweig-Metrik-Einheit zum Ausführen von Zweig-Metrik-Berechnungen aufweist.
Das System nach Anspruch 3, wobei die Arithmetikeinheit ferner ein oder mehrere Register aufweist, in welche die Zweig-Metrik-Einheit ein oder mehrere Ergebnisse speichern kann.
Das System nach Anspruch 4, wobei der Datenadreßgenerator ein oder mehrere Register in der Arithmetikeinheit adressieren kann.
Das System nach Anspruch 1, wobei die mehreren Butterfly-Einheiten ferner Additions-Vergleichs-Auswahl-Operationen unter der Anweisung des digitalen Signalprozessors ausführen.
Das System nach Anspruch 1, wobei die mehreren Butterfly-Einheiten ferner Näherungen von Log-Summations-Exponential-Operationen unter der Anweisung des digitalen Signalprozessors ausführen.
Das System nach Anspruch 1, wobei auf eine aus einem Pfad-Metrik-Speicher wiedergewonnene Pfad-Metrik von dem Datenadreßgenerator des digitalen Signalprozessors zugegriffen wird.
Das System nach Anspruch 8, wobei der Datenadreßgenerator des digitalen Signalprozessors ferner eine Zweig-Metrik aus einer Zweig-Metrik-Einheit wiedergewinnt.
Ein Verfahren, umfassend: Identifizieren einer Stufe eines Trellis-Diagramms; Berechnen von Zweig-Metriken für jeden Knoten der Stufe in einer Arithmetikeinheit, die Register umfasst, die durch einen Datenadreßgenerator adressierbar sind; Transferieren der Zweig-Metriken zu Butterfly-Einheiten durch Zugreifen auf die Register mittels des Datenadressgenerators und Gleichzeitiges Berechnen von zwei oder mehr Pfad-Metriken für die Stufe auf der Grundlage der Zweig-Metriken.
Das Verfahren nach Anspruch 10, ferner umfassend: Speichern der Pfad-Metriken in einem Speicher.
Das Verfahren nach Anspruch 10, wobei das Berechnen der Zweig-Metriken für jeden Knoten der Stufe ferner umfasst: Identifizieren einer Anzahl von Knoten in der Stufe; Identifizieren einer Anzahl von Zweigen, die sich von jedem Knoten aus erstrecken; und Berechnen einer Zweig-Metrik für jeden Zweig.
Das Verfahren nach Anspruch 11, wobei das gleichzeitige Berechnen von zwei oder mehr Pfad-Metriken für die Stufe auf der Grundlage der Zweig-Metriken ferner umfasst: eines Knotens der Stufe; Wiedergewinnen einer früheren Pfad-Metrik aus dem Speicher, wobei die frühere Pfad-Metrik zu dem Knoten führt; Identifizieren einer Anzahl von Zweigen, die sich von dem Knoten in der Stufe aus erstrecken; und Zuweisen einer Butterfly-Einheit für jeden Zweig, der sich von dem Knoten aus erstreckt, wobei die Butterfly-Einheit eine neue Pfad-Metrik aus der früheren Pfad-Metrik in der Zweig-Metrik berechnet.
Ein Verfahren umfassend, Empfangen einer Anforderung zum Decodieren eines Bitstroms, wobei der Bitstrom von einem Codierer codiert wurde und der Codierer unter Verwendung eines Trellis-Diagramms beschrieben wird; Identifizieren einer Stufe des Trellis-Diagramms; Berechnen von Zweig-Metriken für sämtliche Knoten der Stufe in einer Arithmetikeinheit, die Register umfasst, die durch einen Datenadreßgenerator adressierbar sind; Lesen von Pfad-Metriken für eine andere Stufe des Trellis-Diagramms aus einem Speicher; Transferieren der Zweig-Metriken zu Butterfly-Einheiten durch Zugreifen auf die Register mittels des Datenadressgenerators und gleichzeitiges Berechnen neuer Pfad-Metriken für jeden Knoten der Stufe.
Das Verfahren nach Anspruch 14, ferner umfassend: Speichern der neuen Pfad-Metriken für jeden Knoten der Stufe in dem Speicher; und Identifizieren einer neuen Stufe des Trellis-Diagramms.
Das System nach Anspruch 2, wobei der digitale Signalprozessor ferner ein Softwareprogramm aufweist, welches bei seiner Ausführung: eine Stufe eines Trellis-Diagramms identifiziert; eine Anzahl von Knoten in der Stufe identifiziert; und eine Anzahl von sich von jedem Knoten aus erstreckenden Zweigen identifiziert.
Das System nach Anspruch 1, wobei die Anzahl von Butterfly-Einheiten gleich der Anzahl von Knoten in der Stufe ist.
Das System nach Anspruch 17, wobei die ausgeführte Operation das Berechnen von Pfad-Metriken für die Stufe umfasst.
Das System nach Anspruch 18, wobei die Butterfly-Einheiten gleichzeitig eine Pfad-Metrik für jeden Knoten der Stufe berechnen.