DE60108892T2

DE60108892T2 - Modul, vorrichtung und verfahren zum hochbitratigen dekodieren eines verketteten codes

Info

Publication number: DE60108892T2
Application number: DE60108892T
Authority: DE
Inventors: Patrick Adde; Ramesh Pyndiah
Original assignee: Groupe Des Ecoles De Telecommunications-Etablissement Enst De Bretagne; France Telecom SA; Ecole Nationale Superieure des Telecommunications de Bretagne
Current assignee: Groupe Des Ecoles De Telecommunications-Etablissement Enst De Bretagne; Orange SA; IMT Atlantique Bretagne Pays de la Loire
Priority date: 2000-11-10
Filing date: 2001-11-09
Publication date: 2006-04-06
Anticipated expiration: 2021-11-10
Also published as: FR2816773A1; KR100822463B1; CN1479975A; WO2002039587A3; ES2236354T3; US20040054954A1; CN1320771C; WO2002039587A2; JP3898129B2; KR20030063376A; EP1332557B1; US7219291B2; EP1332557A2; FR2816773B1; JP2004523936A; DE60108892D1; HK1061937A1

Description

Die Erfindung betrifft das Codieren digitaler Daten aus einer Folge oder aus mehreren Folgen von Quellendaten, die gesendet oder übertragen werden sollen, insbesondere in Gegenwart von Rauschen aus verschiedenen Quellen sowie mit dem Decodieren der so übertragenen codierten Daten.
Genauer gesagt betrifft die Erfindung eine Verbesserung der Technik zum Decodieren der insbesondere unter dem Namen „Turbo-Codes" (eingetragenes Markenzeichen) bekannten Codes und dabei insbesondere des iterativen Verfahrens zum Decodieren von verketteten Codes.
Die Übertragung der Information (Daten, Bilder, Sprache usw.) beruht immer mehr auf den digitalen Sendetechniken. Es wurden viele Anstrengungen bezüglich der Quellencodierung unternommen, um den numerischen Durchsatz zu verringern, bei gleichzeitigem Erhalt einer guten Qualität. Diese Techniken erfordern selbstverständlich einen besseren Schutz der binären Elemente gegenüber den Sendestörungen. So wurde in diesen Übertragungssystemen die unbedingte Notwendigkeit zum Verwenden von Korrekturcodes mit hohem Wirkungsgrad erkannt. Die Technik der „Turbo-Codes" wurde insbesondere zu diesem Zweck vorgeschlagen.
Das allgemeine Prinzip der „Turbo-Codes" wurde insbesondere in der französischen Patentschrift Nr. FR-91 05280 mit der Überschrift „Fehlerkorrigierendes Codierverfahren mit mindestens zwei systematischen, parallelen faltenden Codierungen, iteratives Decodierverfahren, entsprechende Decodierungs- und Codierungsmodule" sowie im Artikel von C. Berrou, A. Glavieux und P. Thitimajshima mit der Überschrift „Near Shannon limit errorcorrecting coding and decoding: Turbo-codes" (Fehlerkorrigierendes Codieren und Decodieren in der Nähe der Shannon-Grenze: Turbo-Codes), veröffentlicht im Mai 1993 in IEEE International conference on Communication, ICC'93, Band 2/3, Seiten 1064-1071, beschrieben. Ein Stand der Technik wird im Artikel von C.
Berrou und A. Glavieux „Near Optimum Error Correcting Coding and Decoding: „Turbo-Codes" (Nahezu optimales Fehler korrigierendes Codieren und Decodieren: „Turbo-Codes") (IEEE Transactions on Communications, Band 44, Nr. 10, Seiten 1261-1271, Oktober 1996) wieder aufgerufen.
Nach dieser Technik wird der Einsatz einer Codierung „paralleler Verkettung" vorgeschlagen, die sich auf die Verwendung von mindestens zwei elementaren Codierern stützt. Dies macht es möglich, beim Decodieren über zwei aus zwei verschiedenen Decodern kommenden Redundanzsymbole zu verfügen. Zwischen den zwei elementaren Codierern werden Permutationsmittel eingesetzt, damit jeder dieser elementaren Codierer von denselben, jedoch in verschiedenen Reihenfolgen genommenen, digitalen Quellendaten gespeist werden.
Eine Ergänzung zu dieser Art von Technik, die den Erhalt von „Turbo-Codes" genannten Block-Codes oder TCB ermöglicht, dient der Block-Codierung (verkettete Codes). Diese verbesserte Technik wird im Artikel von R. Pyndiah, A. Glavieux, A. Picart und S. Jacq im Artikel „Near optimum decoding of product code" (Nahezu optimales Decodieren des Produkt-Codes) (veröffentlicht in IEEE Transactions on Communications, Band 46, Nr. 8, Seiten 1003 – 1010 im August 1998), in der Patentschrift FR-93 13858 mit der Überschrift „Procede pour transmettre des bits d'information en appliquant des codes en blocs concatenes" (Verfahren zum Senden von Informationsbits durch Anwendung der Codes in verketteten Blöcken) sowie im Artikel von O. Aitsab und R. Pyndiah „Pertormance of Reed Solomon block turbo-code" (Leistung des Reed-Solomon Block-Turbo-Codes) (IEEE Globecom'96 Conference, Band 1/3, Seiten 121-125, London, November 1996) beschrieben.
Diese Technik beruht insbesondere auf der Verwendung von durch P. Elias eingeführten Produktcodes, die in seinem Artikel „Error-free coding" (Fehlerfreies Codieren), veröffentlicht in der Zeitschrift „IRE Transactions on Information Theory" (Band IT4, Seiten 29-27) im September 1954, beschrieben wurden. Die Produktcodes basieren auf der Serienverkettung von Block-Codes. Man hat über längere Zeiträume die Produktcodes nach Algorithmen mit hartem Ein- und Ausgang decodiert, d.h., ein Elementardecoder von Block-Codes akzeptiert Binärelemente am Eingang und liefert ebensolche am Ausgang.
Um die „Block-Turbo-Codes" zu decodieren, wurde die Verwendung von Decodierungsmitteln mit weichem Ein- und Ausgang ins Auge gefasst, d.h., ein elementarer Decodierer von Block-Codes akzeptiert nicht binäre Elemente am Eingang und liefert ebensolche am Ausgang, wobei diese nicht binären Elemente als Funktion ihrer Wahrscheinlichkeit gewichtet sind.
Die „Block-Turbo-Codes" sind besonders attraktiv, wenn das Codieren der Daten auf kleine Blöcke angewandt wird (beispielsweise kleiner als 100 Bits) oder wenn der Wirkungsgrad des Codes (d.h., die Zahl der nützlichen Datenbits geteilt durch die Zahl der codierten Datenbits, beispielsweise 0,95) hoch und die angepeilte Fehlerrate klein ist. In der Tat variiert die Leistungshöhe des Codes, die im allgemeinen nach der verbleibenden Fehlerrate als Funktion eines gegebenen Signal/Rausch-Verhältnisses gemessen wird, als Funktion des minimalen Hamming-Abstandes des Codes, der im Falle der „Block-Turbo-Codes" sehr gut ist (9, 16, 24, 36 oder sogar höher).
Die verschiedenen Techniken des „Turbo-Decodierens" werden immer interessanter für digitale Kommunikationssysteme, von denen eine immer höhere Zuverlässigkeit verlangt wird. Darüber hinaus werden die Senderaten immer höher. Man kann insbesondere durch Verwendung von Sendekanälen über optische Fasern Größenordnungen von Gigabits oder sogar von Terabits erreichen.
Aus dem Stand der Technik sind zwei verschiedene Architekturen von Decodern für „Block-Turbo-Codes" bekannt, die als Basis folgendes haben:

– eine Modularstruktur oder
– eine von Neumannsche Struktur.

Bei der Modularstruktur werden Module oder Elementardecoder kaskadiert, wobei jedes dieser Module eine halbe Iteration ausführt. Diese Verarbeitung ist gut für Codierungsalgorithmen mit gewichteten Ein- und Ausgängen, in dem Maße, in dem eine Vielzahl von Funktionen dieser Algorithmen klassischerweise als Sequenz ausgeführt werden, wobei ihr Einsatz sich dann als einfach erweist.
Ein Hauptnachteil dieser früheren Technik ist, dass sie eine erhebliche Latenzzeit bei der Verarbeitung der Daten einführt, wobei diese Latenzzeit die Zahl der aus dem Decoder kommenden abgetasteten Werte ist, bevor ein am Eingang vorhandener Datenwert sich wieder am Eingang befindet. Diese Latenzzeit erhöht sich mit der Zahl der Module. Ferner ist der Platzbedarf des Schaltkreises auch relativ groß und erhöht sich mit der Zahl der Module. Die Latenzzeit- und Platzbedarfparameter des Schaltkreises werden schnell zu einem wesentlichen Nachteil, wenn die Zahl der Iterationen und/oder die Länge des Codes zunehmen.
Bei der von Neumannschen Struktur führt der Schaltkreis mehrere Iterationen durch, wobei für die Gesamtheit der Iterationen nur eine Speichereinheit und eine Verarbeitungseinheit verwendet werden. Ein elementares Decodierungsmodul wird als Schleife auf sich selbst zurückgeführt. Mit dieser Architektur wird die erforderliche Zahl von Datenspeichern verringert. Der Gewinn an Speicherflächenschaltkreis ist erheblich, da die Speicherfläche unabhängig von der Zahl der Iterationen ist. Dennoch besteht ein Hauptnachteil dieser Struktur darin, dass sie eine Verringerung des Datendurchsatzes bewirkt.
Die Erfindung hat nach ihren verschiedenen Aspekten insbesondere den Zweck, diesen Nachteilen des Standes der Technik entgegen zu wirken.
Genauer gesagt, besteht ein Zweck der Erfindung im Liefern eines Moduls, eines Verfahrens und einer Vorrichtung zum Decodieren, die derart gestaltet sind, dass sie gute Leistungen bezüglich Fehlerrate liefern, wobei die für die Verarbeitung (elementare Decodierungen) und die Datenspeicher erforderliche Fläche begrenzt wird.
Ein weiterer Zweck der Erfindung ist das Liefern eines Moduls, eines Verfahrens und einer Vorrichtung zum Decodieren, die in der Lage sind, hohe Durchsätze bei einer gegebenen Betriebstaktfrequenz zu bewältigen.
Die Erfindung bezweckt ebenfalls eine Verringerung der Decodierungslatenzzeit in einem derartigen Modul, einem derartigen Verfahren und einer derartigen Vorrichtung zum Decodieren.
Diese Ziele sowie andere, die im Nachhinein ersichtlich werden, erreicht man mit mindestens einem Modul zum Decodieren von mindestens zwei Elementarcodes entsprechenden verketteten Codes, wobei das Modul Speichermittel einsetzt, in denen Muster der zu dekodierenden Daten gespeichert sind. Nach der Erfindung umfasst das Modul mindestens zwei Elementardecoder von mindestens einem dieser elementaren Codes, wobei die mit einem der Elementarcodes assoziierten Elementardecoder gleichzeitig in paralleler Arbeitsweise verschiedene in den Speichermitteln enthaltene Codewörter verarbeiten.
Somit beruht die Erfindung auf einem gänzlich neuen und erfinderischen Ansatz für das Decodieren, wobei in einem Modul die Zahl der Decoder verdoppelt wird, ohne dabei die Zahl der Speichermittel zu verdoppeln, was einen Vorteil gegenüber dem Stand der Technik bringt, bei dem der Fachmann zum Erhöhen der Durchsätze in natürlicher Weise die Zahl der Speicher und der Decoder verdoppelt, wobei der Speicher den größten Platzbedarf in einem Decodierschaltkreis beansprucht (so kann beispielsweise der Speicher 80% der Gesamtfläche des Schaltkreises beanspruchen).
Die Erfindung kann vorteilhafterweise auf iterative Decoder und insbesondere auf „Turbo-Decoder" verwendet werden. Die Erfindung kann auf verschiedene Decoderstrukturen und insbesondere auf von Neumannsche Strukturen (bei denen Empfangs- und/oder Datenverarbeitungsspeicher sowie Verarbeitungseinheiten für mehrere Iterationen verwendet werden, was eine Flächeneinsparung beim Schaltkreis ermöglicht, aber für eine gegebene Betriebsgeschwindigkeit, die Decodiergeschwindigkeit begrenzt) sowie auf modulare Strukturen angewandt werden (bei denen Empfangs- und/oder Datenverarbeitungsspeicher sowie Verarbeitungseinheiten für eine einzige halbe Iteration verwendet werden, was einen Geschwindigkeitsgewinn bewirkt, aber eine hohe Latenzzeit beim Decodieren aufrecht erhält), wobei diese Strukturen weiter unten im Detail erläutert werden.
Allgemein bietet die Erfindung das Interesse einer Geschwindigkeitszunahme beim Decodieren (Fall insbesondere der auf eine von Neumannsche Struktur angewandten Erfindung, wobei die Geschwindigkeit das Hauptproblem dieser von Neumannschen Struktur ist) und/oder eines Gewinns bei der Decodierungslatenzzeit (Fall insbesondere der auf eine modulare Struktur angewandten Erfindung), wobei eine relativ geringe Schaltkreisoberfläche erhalten bleibt.
Somit ermöglicht die Erfindung das Erreichen von hohen Durchsätzen bei der Datenübertragung.
Nach einer vorteilhaften Eigenschaft sind die Speichermittel für die zu dekodierenden Daten in Form einer Matrix organisiert, welche n₁ Zeilen, die jeweils ein elementares Codewort und n₂ Spalten, die jeweils ein elementares Codewort enthalten, aufweist, wobei das Decodierungsmodul n₁ (bzw. n₂) Elementardecoder umfasst, die jeweils durch eine der Zeilen (bzw. der Spalten) der Matrix gespeist werden.
Anders ausgedrückt, lässt sich die Erfindung vorteilhafterweise auf seriell verkettete Codes anwenden.
Nach einer besonderen Eigenschaft ist, da die Speichermittel in Form einer Matrix organisiert sind, welche n₁ Zeilen aufweist, von denen k₁ jeweils ein elementares Codewort sowie n₂ Spalten, von denen k₂ jeweils ein elementares Codewort enthalten, das Decodierungsmodul dadurch bemerkenswert, dass es k₁ (bzw. n₂) Elementardecoder umfasst, die jeweils durch eine der Zeilen (bzw. der Spalten) der Matrix gespeist werden.
Somit lässt sich die Erfindung vorteilhafterweise auf parallel verkettete Codes anwenden.
Sie ermöglicht ebenfalls eine Paralleldecodierung der Zeilen (bzw. der Spalten) einer dem verwendeten Code entsprechenden Matrix, wodurch die Decodiergeschwindigkeit erhöht oder die Latenzzeit verringert wird, wobei eine relativ geringe Schaltkreisfläche erhalten bleibt, da die Elementardecoder im allgemeinen eine geringe Schaltkreisfläche (oder allgemein eine geringe Zahl von Transistoren) im Vergleich zu der für die Aufnahmespeicher und für die Datenverarbeitungsspeicher benötigten Flächen erfordern.
Nach einer bevorzugten Eigenschaft der Erfindung sind die Speichermittel so organisiert, dass sie den gleichzeitigen Zugriff auf mindestens zwei elementaren Codewörtern gestatten.
So lassen sich Daten, die mindestens zwei Codewörtern entsprechen, parallel während der elementaren Decodierungen verarbeiten, was einen Geschwindigkeitsgewinn und/oder eine Verringerung der Latenzzeit ermöglicht.
Vorteilhafterweise handelt es sich bei den Speichermitteln um RAM-Speicher mit nur einem Port.
Somit ermöglicht die Erfindung den Einsatz von üblichen Speichern, die keinen Zugriff auf an zwei verschiedenen Adressen gespeicherten Daten ermöglichen und keinen Einsatz von Speichern mit mehreren Ports benötigen (auch wenn dies nicht verboten ist).
Bevorzugterweise sind die Speichermittel nach Fächern organisiert, die jeweils eine einzige Adresse haben und jeweils mindestens zwei Elementardaten eines elementaren Codes enthalten.
Somit erlaubt die Erfindung den Zugriff auf einem einzigen Speicherfach, das mindestens zwei Elementardaten (im Allgemeinen gewichtete oder nicht gewichtete Binärdaten) enthält, wobei diese Daten gleichzeitig von mindestens zwei Elementardecodern verwendet werden können. Dies ermöglicht den gleichzeitigen Zugriff auf Daten, deren Inhalt unabhängig ist, so dass die Betriebsfrequenz (und somit der Verbrauch) der Speicherschaltkreise begrenzt wird, wobei die globale Decodiergeschwindigkeit relativ hoch ist.
Nach einer vorteilhaften Eigenschaft ermöglicht das Decodiermodul den gleichzeitigen Zugriff auf m elementaren Codewörtern und zu 1 elementaren Codewörtern, wobei m > 1 und/oder l > 1, die das gleichzeitige Speisen von mindestens zwei Elementardecodern ermöglichen.
So erlaubt die Erfindung den besten Vorteil aus dem Zerteilen nach Elementarcodes zu ziehen, wobei jedem Elementarcode ein elementarer Decoder zugeordnet ist. So ermöglicht die Erfindung das Optimieren der Decodiergeschwindigkeit und/oder der Latenzzeit.
Nach einer besonderen Eigenschaft entsprechen die gleichzeitig zugänglichen Wörter benachbarten Zeilen und/oder Spalten einer Eingangsmatrix n₁ Zeilen und n₂ Spalten, wobei jede der benachbarten Zeilen und/oder Spalten ein elementares Codeworte enthalten.
Nach einer besonderen Ausführung sind die Elementarcodes derselbe C Code.
Somit ermöglicht die Erfindung das Optimieren der Decodiergeschwindigkeit und/oder der Latenzzeit, wenn die Elementarcodes identisch sind.
Vorteilhafterweise ist das Decodiermodul so konzipiert, dass es mindestens zwei elementare Decodieroperationen ausführt.
Nach einer ersten Ausführung handelt es sich beim verketteten Code um ein in Serie verketteten Code.
Nach einer zweiten Ausführung handelt es sich beim verketteten Code um einen parallel verketteten Code.
So lässt sich die Erfindung sowohl auf die eine als auf die andere Art dieser wichtigen verketteten Codes anwenden.
Die Erfindung betrifft ebenfalls eine Decodiervorrichtung eines verketteten Codes, wobei mindestens zwei Module wie oben beschrieben zum Einsatz kommen, die jeweils eine elementare Decodieroperation durchführen.
Ferner betrifft die Erfindung ein Decodierverfahren eines verketteten Codes, der zwei Elementarcodes entspricht und mindestens zwei gleichzeitige Schritte elementarer Decodierung von mindestens einem der Speisecodes umfasst, wobei diese Schritte von denselben Speichermitteln gespeist werden.
Nach einer vorteilhaften Eigenschaft ist das Decodierverfahren dadurch bemerkenswert, dass die Speichermittel so organisiert sind, dass ein einziger Zugriff auf eine Adresse der Speichermittel den Zugriff auf mindestens zwei elementaren Codewörtern ermöglicht, so dass mindestens zwei elementare Decodierschritte gleichzeitig gespeist werden.
Nach einer besonderen Ausführung ist das Decodierverfahren iterativ.
Bevorzugterweise sind mindestens einige der verarbeiteten Daten gewichtet.
So wird die Erfindung vorteilhafterweise im Rahmen der „Turbo-Codes" eingesetzt, die insbesondere das Erzielen guter Leistungen bezüglich der restlichen Fehlerrate nach dem Decodieren ermöglichen.
Die Vorteile der Decodiervorrichtungen und -verfahren sind dieselben wie die des Decodiermoduls und werden nicht weiter detailliert erläutert.
Weitere Eigenschaften und Vorteile der Erfindung werden deutlicher beim Lesen der nachfolgenden Beschreibung einer bevorzugten Ausführung, die zur Veranschaulichung und ohne einschränkende Wirkung vorgestellt wird sowie beim Betrachten der beigefügten Figuren, wobei:
1 eine Struktur einer Matrix vorstellt, die ein Produkt-Codewort oder „Block-Turbo-Code" nach der Erfindung darstellt, einer besonderen Ausführung entsprechend;
2 ein Organigramm der Decodierung eines an sich bekannten „Turbo-Codes" zeigt;
3 eine schematische Darstellung eines Blockdiagramms einer Verarbeitungseinheit zeigt, die eine ebenfalls an sich bekannte halbe „Turbo-Decodierungs"-Iteration ausführt;
4 eine schematische Darstellung eines Blockdiagramms einer Verarbeitungseinheit zeigt, die eine ebenfalls an sich bekannte halbe „Turbo-Decodierungs"-Iteration ausführt;
5 eine schematische Darstellung eines Blockdiagramms eines Turbo-Decoder-Moduls in einer modularen Struktur nach dem Stand der Technik zeigt;
6 eine schematische Darstellung eines Blockdiagramms eines Turbo-Decoder-Moduls in einer modularen Struktur nach dem Stand der Technik zeigt, wobei die Struktur der Speicher hervorgehoben wird;
7 eine schematische Darstellung eines Blockdiagramms eines Turbo-Decoder-Moduls in einer von Neumannschen Struktur nach dem Stand der Technik zeigt, wobei die Struktur der Speicher hervorgehoben wird;
8 eine schematische Darstellung eines auf hohe Durchsätze angepassten Decoderblocks mit Parallelisierung von Decodern nach der Erfindung zeigt, einer ersten besonderen Ausführung entsprechend;
9 eine schematische Darstellung eines Speicherfachs nach der Erfindung zeigt, einer zweiten besonderen Ausführung entsprechend;
10 eine schematische Darstellung eines Speicherfachs mit seiner Zuordnung zu Verarbeitungseinheiten nach der Erfindung zeigt, einer Variante einer besonderen Ausführung entsprechend;
11 ein Blockdiagramm eines Turbo-Decoders nach der Erfindung zeigt, einer Variante einer besonderen Ausführung entsprechend.
Das allgemeine Prinzip der Erfindung beruht auf einer besonderen Architektur der bei einem Decodierungsverfahren verketteter Codes, und insbesondere beim Decodieren dieser Codes, verwendeten Speicher.
Es sei zuerst daran erinnert, dass man im Allgemeinen einen seriell verketteten Code in Form einer binären Matrix [C] der Dimension 2, wie in 1 gezeigt, darstellen kann. Diese Matrix [C] umfasst n₁ Zeilen und n₂ Spalten und:

– die Binären Informationsmuster werden durch eine Untermatrix 10, [M], mit k₁ Zeilen und k₂ Spalten dargestellt;
– jede der k₁ Zeilen der Matrix [M] wird durch einen Elementarcode C₂(n₂, k₂, δ₂) codiert (die Redundanz wird durch eine Zeilenredundanz-Untermatrix 11 dargestellt);
– jede der n₂ Spalten der Matrix [M] wird durch einen Elementarcode C₁(n₁, k₁, δ₁) codiert (die den binären Informationsmustern entsprechende Redundanz wird durch eine Spaltenredundanz-Untermatrix 12 dargestellt; die der Zeilenredundanz der Untermatrix 11 entsprechende Redundanz wird durch eine Redundanzuntermatrix 13 der Redundanz dargestellt).

Wenn der Code C₁ linear ist, so sind die von C₁ konstruierten (n₁–k₁) Zeilen Wörter des Codes von C₂ und können demnach wie die ersten k₁ Zeilen decodiert werden. Ein seriell verketteter Code ist durch n₁ Codewörter von C₂ nach den Zeilen und durch n₂ Codewörter von C₁ nach den Spalten gekennzeichnet. Die Codes C₁ und C₂ kann man aus faltenden Elementarcodes erhalten, die als Block-Codes oder als Linearblock-Codes verwendet werden.
Die verketteten Codes werden iterativ decodiert, indem zuerst jeder der Elementarcodes nach den Zeilen und dann jeder der Elementarcodes nach den Spalten decodiert wird.
Nach der Erfindung werden, zum Verbessern des Decodierungsdurchsatzes, die Elementardecoder parallelisiert:

– zum Decodieren der n₁ Zeilen verwendet man m₁ (2 ≤ m₁ ≤ n₁) Elementardecoder des Codes C₂ und/oder
– zum Decodieren der n₂ Spalten verwendet man m₂ (2 ≤ m₂ ≤ n₂) Elementardecoder des Codes C₂.

Am Eingang eines jeden Elementardecoders findet man Daten, die aus einem Empfangs- und/oder Verarbeitungsspeicher stammen und dieser Elementardecoder liefert an seinem Ausgang Daten, die in einem Empfangs- und/oder Verarbeitungsspeicher gespeichert werden. Um den Decodierdurchsatz noch weiter zu verbessern, bei Erhalt einer immerhin noch vernünftigen Schaltkreistaktgeschwindigkeit, werden am Eingang oder am Ausgang des Decoders mehrere Daten in einem einzelnen Speicherfach zusammengefügt. Fügt man beispielsweise 4 Elementardaten (wobei jeder Elementardatenwert einem gewichteten oder nicht gewichteten binären Datenwert entspricht) in einem einzelnen Speicherfach zusammen, und werden diese Daten am Eingang der Speicher demultiplexiert (bzw. am Ausgang der Speicher multiplexiert), so wird der Datendurchsatz am Speichereingang bzw. -ausgang bei einer gegebenen Taktgeschwindigkeit des Schaltkreises, vervierfacht, was eine globale Erhöhung der Decodiergeschwindigkeit und/oder Verringerung der Latenzzeit ermöglicht.
Die Erfindung betrifft in gleicher Weise parallel verkettete Codes. Es wird daran erinnert, dass man im Allgemeinen einen parallel verketteten Code in Form einer binären Matrix [C] der Dimension 2, wie in 1 gezeigt, darstellen kann. Diese Matrix [C] umfasst n₁ Zeilen und n₂ Spalten und:

– die binären Informationsmuster werden durch eine Untermatrix 10, [M] mit k, Zeilen und k₂ Spalten dargestellt;
– jede der k₁ Zeilen der Matrix [M] wird durch einen Elementarcode C₂(n₂, k₂, δ₂) codiert (wobei die Redundanz durch eine Untermatrix 11 für die Zeilenredundanz dargestellt wird);
– jede der k₂ Spalten der Matrix [M] wird durch einen Elementarcode C₁(n₁, k₁, δ₁) codiert (wobei die den binären Informationsmustern entsprechende Redundanz durch eine Untermatrix 12 für die Spaltenredundanz dargestellt wird; im Falle der parallel verketteten Codes gibt es keine Redundanz der Redundanz).

Die „Turbo-Decodierung" eines der Matrix C aus 1 entsprechenden Codes besteht in einer gewichteten Eingangs- und Ausgangsdecodierung aller Zeilen und danach aller Spalten der Matrix C, dem in 2 dargestellten iterativen Verfahren entsprechend.
Nach Empfang 21 der zu verarbeitenden Daten wird eine vorgegebene Zahl (Nb_Iter_Max) der folgenden Operationen ausgeführt:

– Decodierung 22 der Spalten (eine halbe Iteration);
– Wiederherstellung 23 der Matrix;
– Decodierung 24 der Zeilen (eine halbe Iteration);
– Wiederherstellung 25 der Matrix.

Diese Operationen werden demnach so oft wiederholt, wie die Zahl i der bei jeder Iteration inkrementierten (26) Iterationen, kleiner Nb_Iter_Max bleibt (27), wobei die Zahl i vorher zu Null initialisiert wurde (28).
Die mit D_k notierten decodierten Daten werden dann verarbeitet (29).
Ganz allgemein werden die von einer halben Iteration 22, 25 zu einer anderen Iteration ausgetauschten Informationen durch 3 definiert.
R_k entspricht der vom Kanal enthaltenen Information, R'_k der aus der vorherigen halben Iteration kommenden Information und R'_k ⁺ der bei der nachfolgenden halben Iteration gesendeten Information. Der Ausgang einer jeden halben Iteration gleicht demnach der Summe 36 von R_k und der von außen wirkenden Information W_k, wobei die Summe dann mit einem Rückkopplungs – oder Konvergenzkoeffizienten alpha multipliziert wird (31). Diese von außen wirkende Information entspricht dem Beitrag des Decoders 32. Sie wird durch die Differenz 33 zwischen dem gewichteten Ausgang F_k des Decoders und dem gewichteten Eingang desselben Decoders erhalten.
Verzögerungen 34 und 35 sind vorgesehen, um die Latenzzeit des Decoders 32 zu kompensieren.
Es wird danach der Decoder mit gewichtetem Ein- und Ausgang als Block aufgefasst, der R_k und R'_k (über q Bits abgetastet) als Eingang hat und R'_k ⁺ und R_k ⁺ (über q Bits abgetastet) mit einer gewissen Latenzzeit L (erforderliche Verzögerung, um den Decodierungsalgorithmus einzusetzen) am Ausgang liefert. Er wird Verarbeitungseinheit (UT) 30 genannt.
Der Decoder 32 liefert andererseits eine binäre Entscheidung D_k, die bei der letzten halben Iteration eines „Turbo-Decodier"-Vorgangs verwendet wird und einem decodierten Datenwert entspricht, der bei der im Zusammenhang mit 2 veranschaulichten Operation 29 gesendet wird.
Betrachtet man eine andere Unterteilung des Blockdiagramms der 3, so kann R'_k durch die von außen wirkende Information W_k ersetzt werden, die zum Eingang-Ausgang der Verarbeitungseinheit 40 wird, wobei der Wert R'_k, der immer noch am Eingang des Decoders 32 verwendet wird, dann eine interne Variable ist. Diese Variante ist in 4 dargestellt.
Wie bereits erwähnt ermöglicht eine funktionelle Analyse des „Turbo-Decodierungs"-Algorithmus das Identifizieren zweier möglicher Architekturen für einen „Turbo-Decoder" Schaltkreis eines Produktcodes (wobei die eine modular ist und die andere einer so genannten von Neumannschen Maschine verwandt ist). Diese zwei Strukturen werden nun genauer beschrieben.

a) Modulare Struktur Man kann sich, ausgehend vom Funktionsdiagramm des Algorithmus, für den „Turbo-Decoder" eine modulare Struktur denken, bei der jeder untergeordnete Schaltkreis eine halbe Decodierungsiteration ausführt (d.h., eine Decodierung der Zeilen oder der Spalten einer Datenmatrix, [R] und [W] oder [R']). Dabei müssen [R] und [W] (oder [R']) nach dem Blockdiagramm der gewählten Verarbeitungseinheit 30 oder 40 gespeichert werden). Der vollständige Schalkreis besteht dann aus identischen, in Kaskaden angeordneten Modulen, wie in 5 dargestellt. Für 4 Iterationen verwendet der Schaltkreis beispielsweise 8 Module oder Elementardecoder. Mit der Modulararchitektur werden die Daten sequentiell (ein abgetasteter Wert nach dem anderen) verarbeitet. Diese Verarbeitung ist den Decodierungsalgorithmen mit gewichteten Ein- und Ausgängen in dem Maße gut angepasst, in dem eine Vielzahl der Funktionen in diesen Algorithmen klassischerweise sequentiell ausgeführt werden und dann einfach einzusetzen sind. Jedes Modul fügt eine Latenzzeit von (n₁n₂+L) abgetasteten Werten ein. Die Latenzzeit ist die Zahl der abgetasteten Werte, die aus dem Decoder herauskommen, ehe ein am Eingang vorhandener Datenwert selbst am Ausgang steht. In diesem Ausdruck entsprechen die ersten n₁n₂ abgetasteten Werte dem Auffüllen einer Datenmatrix und die nachfolgenden L abgetasteten Werte der eigentlichen Decodierung einer Zeile (bzw. Spalte) dieser Matrix.
b) Von Neumannsche Struktur Die zweite Architektur ist einer von Neumannschen sequentiellen Maschine ähnlich. Sie verwendet eine einzige und selbe Verarbeitungseinheit, um mehrere Iterationen durchzuführen. Verglichen mit der früheren Lösung, hat diese hauptsächlich den Zweck den Platzbedarf des „Turbo-Decoders" zu verringern. Sie bietet ferner den Vorteil, die in den Schaltkreis eingeführte globale Latenzzeit auf höchstens 2·n₁n₂ abgetastete Werte zu begrenzen, unabhängig von der Zahl der ausgeführten Iterationen (n₁n₂ zum Auffüllen einer Matrix und n₁n₂ für das Decodieren).

Jeder abgetastete Wert wird sequentiell verarbeitet und muss in einer Zeit decodiert werden, die nicht länger ist, als der Umkehrwert des Produktes des Datendurchsatzes und der Zahl der auszuführenden Halb-Iterationen. So kann für vier Iterationen der Datendurchsatz nur mit einem mindestens achtmal geringeren Rhythmus als der der Verarbeitung erfolgen. Dies impliziert dass, zwischen der modularen Architektur und der von Neumannschen Architektur der maximale Datendurchsatz durch einen Faktor geteilt wird, der zumindest der Zahl der verwendeten Halb-Iterationen gleicht.
Bei der von Neumannschen Struktur ist die Latenzzeit geringer (höchstens 2 n₁n₂ abgetastete Werte gegen (n₁n₂+L)·it bei der anderen, wobei it die Zahl der halben Iterationen ist), wobei jedoch der Durchsatz für dieselbe Datenverarbeitungsgeschwindigkeit geringer ist.
Die maximale Zahl der im Schaltkreis integrierbaren Iterationen ist durch den gewünschten Durchsatz und durch die von der verwendeten Technik zugelassenen betrieblichen Höchstfrequenz begrenzt.
Es werden nun die Speicheraspekte im Zusammenhang mit diesen zwei Strukturen beschrieben. In jedem Fall ergibt sich der Platzbedarf des Schaltkreises im Wesentlichen aus der Größe und der Zahl der eingesetzten Speicher. Unabhängig von der allgemeinen gewählten Architektur ist es nämlich unbedingt erforderlich, die Matrizen [R] und [W] (oder [R']) während der gesamten Dauer der laufenden halben Iteration zu speichern (wobei eine halbe Iteration einem Decodieren der Zeilen oder der Spalten einer Datenmatrix entspricht). Die Verarbeitung der Daten nach Zeilen und dann nach Spalten macht es erforderlich, einen ersten Speicher zum Aufnehmen der Daten und einen zweiten um diese zu Verarbeiten vorzusehen. Diese zwei Speicher arbeiten abwechselnd im Schreib- und Lesemodus, wobei ein Automat die Reihenfolge regelt. Jeder Speicher ist nach einer Matrix organisiert und besteht, für einen Code der Länge n₁n₂ und einer Quantifizierung der Daten über q Bits, aus Speichervorrichtungen von je q·n₁n₂ Bits.
a) Modulare Struktur
Im Falle der modularen Struktur ist die allgemeine Organisation des Schaltkreise über einer halben Iteration die der 5 und 6.
Das in 5 dargestellte Modul 50 umfasst eine Verarbeitungseinheit 40 (wie in 4 dargestellt) und 4 Speicher:

– einen Speicher 51 zum Speichern, der die Daten [R] enthält;
– einen Arbeitsspeicher 52, der die Daten [R] enthält;
– einen Speicher 53 zum Speichern, der die Daten [W] (oder [R'], abhängig von der Verarbeitungseinheit) und
– einen Arbeitsspeicher 54, der die Daten [W] (oder [R']) enthält.

Die über q Bits codierten Daten [R] 57₁ (bzw. [W] 57₂ ), die beim Decodiermodul 50 ankommen, sind nach den Zeilen des im Schreibmodus arbeitenden Empfangspeichers 51 (bzw. 53) angeordnet, wobei der logische Schalter 55, (bzw. 55₃ ) am Eingang des Speichers 51 (bzw. 53) (der beispielsweise in Form eines Adressierungsbits eingesetzt wird, welcher die Wahl des Speichers 51 (bzw. 53) bei einem Schreibvorgang ermöglicht) dann geschlossen ist, während der Schalter 56 ₁ (bzw. 56₃ ) am Eingang des Speichers 52 (bzw. 54) offen ist. Die Daten [R] am Eingang des ersten Moduls kommen unmittelbar aus dem Sendekanal, während die Daten [R] aus jedem der nachfolgenden Module aus dem Ausgang [R] 59₁ des vorhergehenden Moduls kommen. Die Daten [W] am Eingang des ersten Moduls sind null, während die Daten [W] eines jeden der nachfolgenden Module vom Ausgang [W] 59₂ des vorhergehenden Moduls kommen.
Parallel dazu werden die Daten der vorher empfangenen Matrix nach den Spalten der Arbeitsspeicher 52 und 54 aufgelesen, die im Lesemodus arbeiten, wobei der logische Schalter 56₂ (bzw. 55₄ ) am Ausgang des Speichers 52 (bzw. 54) (der beispielsweise in Form eines Adressierungsbits eingesetzt wird, welcher die Wahl des Speichers 52 (bzw. 54) bei einem Lesevorgang ermöglicht) dann geschlossen ist, während der Schalter 56₂ (bzw. 56₄ ) am Ausgang des Speichers 51 (bzw. 53) offen ist.
Nachdem die Empfangspeicher voll sind, gehen die Arbeitsspeicher in den Schriftmodus über (anders ausgedrückt, werden die Rollen der Speicher 51 und 52 (bzw. 53 und 54) untereinander ausgetauscht, während die logischen Schalter 55₁ , 55₂ , 55₁ und 56₂ (bzw. 55₃ , 55₄ , 56₃ und 56₄ ) „die Lage wechseln"), um die dem nachfolgenden Codewort entsprechenden Daten zu speichern. Durch Kaskadieren zweier Module, das eine zum Decodieren der Spalten und das andere zum Decodieren der Zeilen einer codierten Matrix, wird eine vollständige Iteration ausgeführt.
Die verwendeten Speicher 51, 52, 53 und 54 lassen sich problemlos auf der Grundlage von klassischen, nach Zeilen und Spalten adressierbaren RAM-Speichern (Random Access Memory, Speicher mit freiem Zugriff) mit nur einem Port konzipieren. Es sind weitere Lösungen denkbar (beispielsweise Verschieberegister), aber sie weisen einen größeren Platzbedarf auf.
Es sei darauf hingewiesen, dass die auf dem in 5 dargestellten Datenbus ausgetauschten Daten über q Bits codiert sind, während bei einer in 6 dargestellten Variante, die Daten über 2·q Bits codiert sind, wobei jeder Datenwert dann q Bits enthält, die einem Datenwert [R] entsprechen und q Bits, die einem Datenwert [W] (oder (R']) entsprechen.
Das in 6 dargestellte Modul 60 ermöglicht die Durchführung einer halben Decodierungsiteration und enthält eine Verarbeitungseinheit 40 (wie in 4 dargestellt) sowie zwei Speicher:

– einen Speicher 62 zum Speichern oder Empfangen, der die Daten [R] und [W] (oder [R'], falls die Verarbeitungseinheit so ist, wie die in 3 dargestellte Einheit 30) und
– einen Arbeitsspeicher 63, der die Daten [R] und [W] (bzw. [R']) enthält.

Die über 2·q Bits codierten Daten 61, die beim Decodiermodul ankommen, werden nach den Zeilen des im Schriftmodus arbeitenden Empfangsspeichers 62 angeordnet. Parallel dazu werden die Daten der vorher empfangenen Matrix nach den Spalten des im Lesemodus arbeitenden Arbeitsspeichers 62 aufgelesen. Nachdem der Empfangsspeicher 62 voll ist, geht der Arbeitsspeicher in den Schreibmodus über, um die dem nachfolgenden Codewort entsprechenden Daten zu speichern. Durch Kaskadieren zweier Module, das eine zum Decodieren der Spalten und das andere zum decodieren der Zeilen einer codierten Matrix, wird eine vollständige Iteration ausgeführt.
Die verwendeten Speicher 62, 63 lassen sich problemlos auf der Grundlage von klassischen, nach Zeilen und Spalten adressierbaren RAM-Speichern (Random Access Memory, Speicher mit freiem Zugriff) mit nur einem Port konzipieren. Es sind weitere Lösungen denkbar (beispielsweise Verschieberegister), aber sie weisen einen größeren Platzbedarf auf.
Praktisch gesehen bietet die modulare Lösung den Vorteil, dass sie eine hohe Betriebsfrequenz zulässt und ein hohes Maß an Verwendungsflexibilität bietet. Dagegen bewirkt das Kaskadieren mehrerer Module eine Verlängerung der Latenzzeit und des Platzbedarfs des Schaltkreises. Diese Parameter werden schnell zu unüberwindbaren Nachteilen, wenn die Zahl der Iterationen und/oder die Codelänge zunimmt (zunehmen).
b) Sogenannte von Neumannsche Struktur
Diesmal führt der Schaltkreis mehrere Iterationen durch, wobei vier Speichereinheiten 70, 71, 72 und 73 verwendet werden, die in 7 dargestellt sind. Es wird ein Decodiermodul auf sich selbst zurückgekoppelt. Mit dieser Architektur umfasst der gesamte Schaltkreis lediglich vier Speicher 70, 71, 72 und 73, unabhängig von der Zahl der durchgeführten Iterationen. Diese Speicher 70, 71, 72 und 73 müssen jedoch sowohl nach Zeilen als auch nach Spalten gelesen und beschrieben werden.
Die verwendeten Speicher 70, 71, 72 und 73 sind klassische RAM-Speicher mit nur einem Port, in denen man einen durch seine Adresse gekennzeichneten Datenwert lesen oder schreiben kann. Da man direkten Zugriff zu jedem abgetasteten Wert hat, lässt sich die Matrix sowohl nach Zeilen als auch nach Spalten decodieren. Diese Speicher sind ähnlich zu denen für die modulare Lösung gewählten, aber da der Schaltkreis nur vier Stück umfasst, hat man einen gewaltigen Flächengewinn (80 % für vier Iterationen). Es sei jedoch darauf hingewiesen, dass diese Verringerung der Fläche, bei gleicher Betriebsgeschwindigkeit, auf Kosten des Datendurchsatzes erzielt wird (der Durchsatz wird mindestens durch it für it/2 Iterationen geteilt: bei dieser Berechnung muss nämlich die Latenzzeit einer jeden Elementardecodierung berücksichtigt werden).
Die über q Bits codierten Daten [R] 76 (bzw. [W] 75), werden nach den Zeilen des im Schreibmodus arbeitenden Empfangsspeichers 80 (bzw. 72) angeordnet, wobei die logische Weiche 77₁ (bzw. 78₁ ) die Daten zum Speicher 70 (bzw. 72) dirigiert (diese Weiche wird beispielsweise in Form eines Adressierungsbits eingesetzt, der bei einem Schreibvorgang die Wahl des Speichers 70 (bzw. 72) ermöglicht). Die am Eingang befindlichen Daten [R] 76 kommen unmittelbar aus dem Sendekanal. Die Eingangsdaten [W] sind null bei der ersten halben Iteration, während die Daten [W] einer jeden der nachfolgenden halben Iterationen aus dem Ausgang [W] 75 der vorhergehenden halben Iteration kommen.
Parallel dazu werden die vorher empfangenen Daten [R] nach den Spalten des im Lesemodus arbeitenden Arbeitsspeichers 71 aufgelesen, wobei die logische Weiche 77₂ am Ausgang der Speicher 71 und 70 (beispielsweise in Form eines Adressierungsbits eingesetzt) die Wahl des Speichers 71 bei einem Lesevorgang ermöglicht. Parallel dazu werden die aus einer vorherigen halben Iteration stammenden Daten [W] (die null sind, wenn es sich um die erste halbe Iteration handelt) nach den Spalten des im Lesemodus arbeitenden Arbeitsspeichers 73 abgegriffen, wobei die logische Weiche 78₂ am Ausgang der Speicher 72 und 73 die Wahl des Speichers 72 bei einem Lesevorgang ermöglicht.
Nach dem Auffüllen des Empfangsspeichers von [W] (d.h., am Ende einer jeden halben Iteration), werden die Rollen des Arbeitsspeichers und des Empfangsspeichers von [W] ausgetauscht: der Arbeitsspeicher von [W] geht in den Schreibmodus über und wird zum Empfangsspeicher (anders ausgedrückt, die logischen Weichen 78₁ und 78₂ „wechseln ihre Lage"), um die dem nachfolgenden Codewort entsprechenden Daten zu speichern, und der Empfangsspeicher von [W] geht in den Lesemodus über und wird zum Arbeitsspeicher.
Nach dem Auffüllen des Empfangsspeichers von [R] (d.h., am Ende eines jeden Turbo-Decodier-Vorgangs eines Blocks, wenn die Datenübertragung als kontinuierlich angenommen wird), werden die Rollen des Arbeitsspeichers und des Empfangsspeichers von [R] ausgetauscht: der Arbeitsspeicher von [R] geht in den Schreibmodus über und wird zum Empfangsspeicher (anders ausgedrückt, die logischen Weichen 77₁ und 77₂ „wechseln ihre Lage"), um die dem nachfolgenden Codewort entsprechenden Daten zu speichern, und der Empfangsspeicher von [R] geht in den Lesemodus über und wird zum Arbeitsspeicher. Werden als Variante die Daten im Paketmodus (oder „burst in Englisch) übertragen, und wenn jedes Paket auf einmal decodiert werden muss, wobei die Decodierung vor der Ankunft eines neuen Pakets fertig ist, so ist es für eine von Neumannsche Struktur nicht erforderlich, zwei Speicher, nämlich einen Arbeitsspeicher bzw. einen Empfangsspeicher für die Daten [R], zu haben, sondern es genügt ein einziger Speicher.
Die verwendeten Speicher 70, 71, 72 und 73 lassen sich problemlos auf der Grundlage von klassischen, nach Zeilen und Spalten adressierbaren RAM-Speichern (Random Access Memory) mit nur einem Port konzipieren. Es sind weitere Lösungen denkbar (beispielsweise Verschieberegister), aber sie weisen einen größeren Platzbedarf auf.
Es sei darauf hingewiesen, dass die über den in 7 gezeigten Datenbussen ausgetauschten Daten über q Bits codiert werden.
Es sei ebenfalls darauf hingewiesen, dass als Variante der in den 5, 6, und 7 dargestellten Ausführungen, die Verarbeitungseinheit 40 durch eine Verarbeitungseinheit 30, wie in 3 dargestellt, ersetzt werden kann. Die Daten des Typs [W] werden dann in den Speichern durch Daten des Typs [R'] ersetzt.
Nach dem Stand der Technik besteht eine Architektur mit hohem Durchsatz in der Verdoppelung der Zahl der in den 6 oder 7 dargestellten Module.
Die Erfindung schlägt einen neuen Ansatz vor, der einer Architektur mit hohem Durchsatz eines „Turbo-Decoders" mit verketteten Codes besonders angepasst ist.
Es wurde gezeigt, dass die verketteten Codes die Eigenschaft aufweisen, Codewörter auf allen Zeilen (bzw. Spalten) der Ausgangsmatrix C zu haben.
Nach der Erfindung wird die Decodierung nach dem in 8 dargestellten Prinzip parallelisiert, das ein Modul 80 beschreibt, welches das Ausführen einer halben Iteration erlaubt, wobei die Module 80 kaskadiert werden können, um eine modulare Turbo-Decodierungsstruktur zu bilden. Die Matrix 81 (Arbeitsspeicheranordnung von n₁·n₂ abgetasteten Werten von 2q Bits, welche die Daten [R] und [W] (oder [R'], je nach Art der Verarbeitungseinheit enthält), speist eine Vielzahl von Elementardecodern (oder Verarbeitungseinheit 30 oder 40, wie in den 3 und 4 dargestellt) 82₁ bis 82_m .
Die Zahl der Elementardecoder des Codes C₁ (oder C₂) wurde nämlich auf m Elementardecoder 82₁ bis 82_m verdoppelt. So kann man eine Höchstzahl von n₁ (oder n₂) Codewörtern verarbeiten, jedoch unter der Voraussetzung, dass die Speicherzugänge im Lese- oder im Schreibmodus zu verschiedenen Zeitpunkten erfolgen (es können mehrere Speicherpunkte einer Matrix nicht gleichzeitig gelesen oder beschrieben werden, es sei denn, man verwendet, RAM-Speicher „mit mehreren Ports"). Wird dieser einengende Zwang eingehalten, so lässt sich ein Faktor n₂ (oder n₁) im Verhältnis F_Durchsatz/F_VEmax gewinnen (wobei F_Durchsatz der nutzbare Durchsatz am Ausgang des Turbo-Decoders und F_VEmax die Arbeitsgeschwindigkeit einer Verarbeitungseinheit ist), da zu einem gegebenen Zeitpunkt, n₂ (oder n₁) abgetastete Werte bearbeitet werden können.
Die Matrix 83 (Empfangsspeicheranordnung von n₁·n₂ abgetasteten Werten von 2q Bits) wird durch eine Vielzahl von Elementardecodern 82₁ bis 82_m eines vorhergehenden Moduls 80 gespeist.
Es sei darauf hingewiesen, dass beim ersten Modul die Daten [R] direkt aus dem Kanal kommen, während die Daten [W] null sind (oder man verwendet als Variante, am Eingang der Elementardecoder im ersten Modul, nur einen, den Daten [R] entsprechenden halben Bus).
Bei jeder halben Iteration werden die jeweiligen Rollen der Speicher 81 und 83 ausgetauscht, wobei diese Speicher abwechselnd Arbeits- oder Empfangsspeicher sind.
Es sei darauf hingewiesen, dass die Daten nach den Spalten der Empfangsspeicheranordnungen geschrieben und nach den Zeilen der Arbeitsspeicheranordnungen gelesen werden. So erhält man vorteilhafterweise ein leicht einzusetzendes Mittel zum Verschachteln bzw. Entschachteln (falls die Verschachtelungsvorrichtung des Turbo-Coders gleichmäßig ist, d.h., in der Verschachtelungsvorrichtung werden die Daten Zeile um Zeile geschrieben und Spalte um Spalte gelesen), indem die Module kaskadiert werden, wobei die Ausgänge der Elementardecoder eines Moduls mit der Empfangsspeicheranordnung des nachfolgenden Moduls verbunden sind.
Der Hauptnachteil dieser Architektur ist, dass die Speicher 81 und 83 bei der Frequenz m·F_VEmax arbeiten müssen, wenn man m parallel geschaltete Elementardecoder hat.
Nach einer ersten Variante der Modularstruktur ist die Matrix 81 nach zwei Arbeitsspeicheranordnungen von n₁·n₂ abgetasteten Werten von q Bits unterteilt, wobei beide Anordnungen jeweils die Daten [R] bzw. [W] (oder [R'] je nach Art der Verarbeitungseinheit) enthalten. Ferner ist die Matrix 83 selbst nach zwei Empfangsspeicheranordnungen von n₁·n₂ abgetasteten Werten von q Bits unterteilt, die jeweils Daten [R] bzw. [W] enthalten.
Als Variante wird der „Turbo-Decoder" nach einer von Neumannschen Struktur realisiert. Nach dieser Variante ist die Arbeitsspeicheranordnung nach einer mit den Daten [R] assoziierten Arbeitsspeicheranordnung (unter der Annahme, dass die Daten in kontinuierlicher Weise übertragen werden) und einer mit den Daten [W] (oder [R'], je nach Ausführung der Verarbeitungseinheit) assoziierten Arbeitsspeicheranordnung unterteilt. In gleicher Weise ist die Arbeitsspeicheranordnung nach einer mit den Daten [R] assoziierten Empfangsspeicheranordnung und einer mit den Daten [W] assoziierten Empfangsspeicheranordnung unterteilt. In gleicher Weise wie bei der in 7 dargestellten Struktur, werden die Rollen der Verarbeitungs- und Empfangsspeicher der Daten [R] bei jeder halben Iteration ausgetauscht, während die Rollen der Verarbeitungs- und Empfangsspeicher der Daten [W] bei jedem Turbo-Decodierungsvorgang eines Blocks ausgetauscht werden. Es sei jedoch darauf hingewiesen, dass nach der Erfindung, bei einer von Neumannschen Struktur, die Arbeitsspeicher der Daten [R] und [W] m Elementardecoder speisen, und dass die Ausgänge [W] dieser Decoder auf den Empfangsspeicher der Daten [W] zurückgekoppelt werden. Nach dieser Variante, wenn die Daten im Paketmodus (Englisch burst) übertragen und wenn jedes Paket auf einmal decodiert werden muss, wobei die Decodierung vor der Ankunft eines neuen Pakets fertig ist, ist es nicht erforderlich, über zwei Speicher, nämlich einen Arbeitsspeicher bzw. einen Empfangsspeicher für die Daten [R], zu verfügen, sondern es genügt ein einziger Speicher.
Nach einem vorteilhaften Aspekt der Erfindung kann man dieselbe Arbeitsgeschwindigkeit des Speichers aufrechterhalten und den Durchsatz erhöhen, indem nach dem in 10 dargestellten Prinzip, mehrere Daten an einer selben Adresse gespeichert werden. Es ist jedoch erforderlich, diese Daten sowohl nach Zeilen als auch nach Spalten verwenden zu können. Daher ergibt sich die folgende Organisation: an dieser Adresse findet man Daten, die beim Lesen (oder Schreiben) benachbart sind, sowohl nach Zeilen als auch nach Spalten.
Man betrachte zwei benachbarte Zeilen i und i+1 sowie zwei benachbarte Spalten j und j+1 der in 9 vorgestellten Ausgangsmatrix 90.
Die 4 abgetasteten Werte (i, j), (i, j+1), (i+1, j) und (i+1, j+1) bilden ein Wort 105 der in 10 dargestellten neuen Matrix 100, die 4 Mal weniger Adressen (I, J), dafür aber 4 Mal größere Wörter hat. Seien n₁ und n₂ gerade,
dann gilt: wenn 1 ≤ I ≤ n₁/2, i = 2*I – 1.
In gleicher Weise wenn 1 ≤ J ≤ n₂/2 j = 2*J – 1.
Für die Zeilendecodierung werden die abgetasteten Werte (i, j) und (i, j+1) 101 einer Verarbeitungseinheit VE1, (i+1, j) und (i+1, j+1) 102 einer Verarbeitungseinheit VE2 zugeordnet. Für das Decodieren nach Spalten muss man (i, j), (i+1, j) 103 für VE1 und (i, j+1), (i+1, j+1) 104 für VE2 nehmen. Sind die Verarbeitungseinheiten in der Lage, diese Paare abgetasteter Werte am Eingang (Lesen der RAM) und am Ausgang (Schreiben der RAM) in derselben Zeit 1/F_vEmax zu verarbeiten, so ist die Verarbeitungszeit der Matrix 4 Mal schneller als im Falle der Anfangsmatrix (10).
Diese 10 ist selbstverständlich nur ein Beispiel für das „Zerteilen" des Speichers in 4 Teile.
Um dies zu verallgemeinern, wenn ein Wort 105 der neuen Matrix 100 m abgetastete Werte einer Zeile und l abgetastete Werte einer Spalte enthält, so ist die Verarbeitungszeit der Matrix m·l schneller mit nur m Verarbeitungseinheiten für das Decodieren nach „Zeilen" und l Verarbeitungseinheiten für das Decodieren nach „Spalten".
Wenn die Codes C₁ und C₂ identisch sind, so sind es die „Zeilen"-VE und die „Spalten"-VE ebenfalls, wie in 11 dargestellt. Dann ist m=l und es sind m Verarbeitungseinheiten 112₁ bis 112_m erforderlich (wie die in den 3 und 4 dargestellten Verarbeitungseinheiten 30 oder 40). Ein Demultiplexierer 114 liefert die Daten der Matrix 111 (Verarbeitungsspeicheranordnung mit n1n2/m² Wörtern zu 2q·m² Bits) und die m elementaren Verarbeitungseinheiten (VE) 112₁ bis 112_m , wobei jede Verarbeitungseinheit gleichzeitig einen abgetasteten Wert von 2qm Bits empfängt.
Ein Multiplexierer 115 wird mit abgetasteten Werten von 2qm Bits durch die Elementardecoder 112₁ bis 112_m gespeist. Der Multiplexierer 115 speist dann mit abgetasteten Werten von 2q·m² Bits die Arbeitsspeicheranordnung 113 des der nachfolgenden Iteration entsprechenden Moduls.
Diese Organisation der Datenmatrizen benötigt keine besondere Speicherarchitektur und auch keine höhere Geschwindigkeit. Wenn andererseits die Komplexität der VE kleiner als m Mal die der vorhergehenden VE bleibt, so ist die gesamte Komplexität geringer für eine m² höhere Geschwindigkeit (dieses letzte Ergebnis hätte man durch Anwendung von m² VE, wie in 8 vorgeschlagen, erreichen können).
Der Speicher umfasst m² Mal weniger Wörter als die Ausgangsmatrix C. Bei identischer Technologie ist die Zugriffszeit somit geringer.
Die Erfindung schlägt demnach eine Decodierungsarchitektur der verketteten Codes vor, die mit hohem Durchsatz arbeitet. Diese Codes können somit aus faltenden Codes oder aus linearen Blockcodes erhalten werden. Die Erfindung besteht im Wesentlichen darin, die Ausgangsorganisation des Speichers C zu ändern, um die Decodierungsgeschwindigkeit zu beschleunigen. Während einer Zeit 1/F_VEmax werden m abgetastete Werte in einem jeden der Elementardecoder verarbeitet, was zu einem Durchsatzgewinn von m² führt. Wenn die Verarbeitung dieser m Abtastwerte die Oberfläche des Elementardecoders nicht im nennenswerten Umfang vergrößert, so liegt der Oberflächengewinn nahe bei m, wenn man diese Lösung mit derjenigen vergleicht, bei der m² Decoder benötigt werden.
Nach einer Variante demultiplexiert der Demultiplexierer 114 jeden der von der Speicheranordnung 111 empfangenen abgetasteten Werte mit 2q·m² Bits und serialisiert sie, um m Folgen von m abgetasteten Werten zu je 2q Bits zu erhalten. Jede dieser Folge wird an eine der elementaren Verarbeitungseinheiten 112₁ bis 112_m geliefert. Jede der Verarbeitungseinheiten 112₁ bis 112_m speist dann den Mutliplexierer 115 mit Folgen von 2q Bits. Der Mutliplexierer verarbeitet die m gleichzeitig aus den Verarbeitungseinheiten 112 bis 112_m kommenden Folgen, um die Empfangsspeicheranordnung 113 des der nachfolgenden halben Iteration entsprechenden Moduls mit abgetasteten Werten von 2q·m² Bits zu speisen. Nach dieser Variante erhält man eine m mal höhere Decodiergeschwindigkeit als nach dem Stand der Technik, bei gleicher Taktgeschwindigkeit, mit einer einzigen Arbeitsspeicheranordnung in jedem Modul.
Nach den in 11 beschriebenen Ausführungen ist, mit den Speicheranordnungen 111 und 113, welche über 2q·m² Bits codierte Daten enthalten, die Zahl der Wörter in den Empfangs- und Arbeitsspeichern geringer und die Zugriffszeit auf diese Speicher wird verkürzt.
Selbstverständlich ist die Erfindung nicht auf die oben erwähnten Ausführungsbeispiele beschränkt.
Insbesondere kann der Fachmann jede Variante bei der Art der verwendeten Speicher einsetzen, wobei diese beispielsweise RAM-Speicher mit nur einem Port oder RAM-Speicher mit mehreren Ports sein können.
Ferner ist die Erfindung sowohl auf die Fälle anwendbar, bei denen die Daten im Paketmodus (Englisch burst) als auch kontinuierlich übertragen werden.
Ferner betrifft die Erfindung sowohl die seriell als auch die parallel verketteten Codes, wobei diese Codes von der faltenden Art oder vom Block-Code Typ sein können.
Die Erfindung betrifft Codes, die sowohl aus zwei verkettete Codes gebildet sind, aber ebenfalls solche, die aus mehr als zwei verkettete Codes gebildet sind.
Allgemein betrifft die Erfindung auch alle „Turbo-Codes", unabhängig davon, ob es sich um Block-Turbo-Codes handelt, die aus Elementarcodes gebildet sind, welche auf eine Informationsfolge (permutiert oder nicht) wirken, wobei mindestens eines der elementaren Codewörter von mindestens zwei Codewörtern gebildet wird.

Claims

Modul zum Dekodieren eines mindestens zwei Elementarcodes entsprechenden verketteten Codes, welches Speichermittel einsetzt, in denen Muster der zu dekodierenden Daten gespeichert sind, dadurch gekennzeichnet, dass es mindestens zwei Elementardecoder (82₁ bis 82_m , 112₁ bis 112_m ) von mindestens einen dieser elementaren Codes umfasst, wobei die mit einem der Elementarcodes assoziierten Elementardecoder (82₁ bis 82_m , 112₁ bis 112_m ) gleichzeitig in paralleler Arbeitsweise verschiedene in den Speichermitteln (81, 83, 90, 111, 113) Codewörter verarbeitet, sowie dadurch, dass die Speichermittel (81, 83, 90, 111, 113) nach Fächern (105) organisiert sind, die jeweils eine einzige Adresse besitzen und mindestens zwei einem elementaren Codewort entsprechende Elementardaten (101, 102, 103, 104) enthalten.
Modul zum Dekodieren nach Anspruch 1, wobei die Speichermittel für die zu dekodierenden Daten in Form einer Matrix (10) organisiert sind, welche n₁ Zeilen, die jeweils ein Codewort der erwähnten Elementarcodes und n₁ Spalten, die jeweils ein Codewort der erwähnten Elementarcodes enthalten, aufweist, dadurch gekennzeichnet, dass es n₁ (bzw. n₂) Elementardecoder (82₁ bis 82_m , 112₁ bis 112_m ) umfasst, die jeweils durch eine der Zeilen (bzw. der Spalten) der Matrix (10) gespeist werden.
Modul zum Dekodieren nach Anspruch 1, wobei die Speichermittel für die zu dekodierenden Daten in Form einer Matrix (10) organisiert sind, welche n₁ Zeilen aufweist, von denen k₁ jeweils ein Codewort der erwähnten Elementarcodes enthalten sowie n₂ Spalten, von denen k₂ jeweils ein Codewort der erwähnten Elementarcodes enthalten, dadurch gekennzeichnet, dass es k₁ (bzw. n₂) Elementardecoder (82₁ bis 82_m , 112₁ bis 112_m ) umfasst, die jeweils durch eine der Zeilen (bzw. der Spalten) der Matrix (10) gespeist werden.
Modul zum Dekodieren nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass die Speichermittel (81, 83, 90, 111, 113) so organisiert sind, dass sie den gleichzeitigen Zugang zu mindestens zwei elementaren Codewörtern gestatten.
Modul zum Dekodieren nach Anspruch 4, dadurch gekennzeichnet, dass es sich bei den Speichermitteln (81, 83, 90, 111, 113) um RAM-Speicher mit nur einem Port handelt.
Modul zum Dekodieren nach einem der Ansprüche 4 oder 5, dadurch gekennzeichnet, dass jedes der Fächer (105) der Speichermittel (81, 83, 90, 111, 113), die jeweils eine einzige Adresse besitzen, m·l Elementardaten (101, 102, 103, 104) umfasst, welche die gleichzeitige Zufuhr zu den folgenden Teilen ermöglichen: – m Elementardecoder nach einer der Zeilen gemäß einem der Ansprüche 2 oder 3 und/oder, – 1 Elementardecoder nach einer der Spalten gemäß einem der Ansprüche 2 oder 3, wobei m und 1 ganze Zahlen sind, die streng größer als 1 sind.
Modul zum Dekodieren nach einem der Ansprüche 4 bis 6, dadurch gekennzeichnet, dass die gleichzeitig zugänglichen Wörter nebeneinander liegenden Zeilen und/oder Spalten einer Ausgangsmatrix (10) mit n₁ Zeilen und n₂ Spalten entsprechen, wobei jede der nebeneinander liegenden Zeilen und/oder Spalten ein elementares Codewort enthalten.
Modul nach einem der Ansprüche 1 bis 7, dadurch gekennzeichnet, dass es sich bei den Elementarcodes um denselben Code C handelt.
Modul zum Dekodieren nach einem der Ansprüche 1 bis 8, dadurch gekennzeichnet, dass es mindestens zwei elementare Dekodieroperationen durchführt.
Modul zum Dekodieren nach einem der Ansprüche 1 bis 9, dadurch gekennzeichnet, dass der verkettete Code ein in Serie verketteter Code ist.
Modul zum Dekodieren nach einem der Ansprüche 1 bis 10, dadurch gekennzeichnet, dass der verkettete Code ein parallel verketteter Code ist.
Vorrichtung zum Dekodieren eines verketteten Codes, dadurch gekennzeichnet, dass sie mindestens zwei Module nach einem der Ansprüche 1 bis 11 einsetzt, wobei diese Module in Kaskade angebracht sind und jeweils eine elementare Dekodieroperation ausführen.
Verfahren zum Dekodieren eines zwei Elementarcodes entsprechenden verketteten Codes, dadurch gekennzeichnet, dass es mindestens zwei gleichzeitige Schritte zum elementaren Dekodieren von mindestens einem der erwähnten Elementarcodes umfasst, die von denselben Speichermitteln (81, 83, 90, 111, 113) versorgt werden, und dadurch, dass die Speichermittel nach Fächern organisiert sind, so dass der Zugang zu einer einzigen Adresse der Speichermittel (81, 83, 90, 111, 113) den Zugang zu mindestens zwei einem elementaren Codewort entsprechenden Elementardaten zulässt, um gleichzeitig mindestens zwei der Schritte zum elementaren Dekodieren zu versorgen.
Dekodierverfahren nach Anspruch 13, dadurch gekennzeichnet, dass es iterativ ist.
Dekodierverfahren nach einem der Ansprüche 13 oder 14, dadurch gekennzeichnet, dass es sich bei mindestens einigen der verarbeiteten Daten um gewichtete Daten handelt.