DE10048872A1

DE10048872A1 - Abschnittsweise Entschachtelung

Info

Publication number: DE10048872A1
Application number: DE10048872A
Authority: DE
Inventors: Michael Schneider; Peter Jung; Joerg Plechinger; Tideya Kella; Markus Doetsch; Burkhard Becker
Original assignee: Infineon Technologies AG
Current assignee: Infineon Technologies AG
Priority date: 2000-10-02
Filing date: 2000-10-02
Publication date: 2002-04-25
Also published as: WO2002030073A3; JP2004511179A; US20030221157A1; US7013412B2; EP1323269A2; WO2002030073A2; CN1582555A

Abstract

Bei einem Verfahren zur Entschachtelung eines gemäß einer vorgegebenen Verschachtelungsvorschrift blockweise verschachtelten Datensignals werden Entschachtelungs-Zieladressen bezüglich eines ersten vorgegebenen Abschnitts der zu entschachtelnden Datensymbole berechnet und in einem Zieladressenspeicher abgelegt. Mittels der berechneten Zieladressen wird dann der betreffende Abschnitt der Datensymbole entschachtelt. Nachfolgend werden diese beiden Schritte so oft wiederholt, bis der gesamte Datenblock abschnittsweise entschachtelt ist.

Description

Die Erfindung betrifft ein Verfahren zur Entschachtelung ei nes blockweise verschachtelten Datensignals.

In der Telekommunikationstechnik ist es üblich, ein über ei nen Kanal zu übertragendes Datensignal einer senderseitigen Verschachtelung zu unterziehen. Durch die Verschachtelung wird erreicht, daß Störungen, die ohne eine Verschachtelung statistisch abhängige (in Gruppen auftretende) Detektionsfeh ler bewirken würde, stattdessen statistisch unabhängige De tektionsfehler erzeugen. Für statistisch unabhängige Detekti onsfehler ist durch Kanalcodierung ein besserer Fehlerschutz grad als für statistisch abhängige Detektionsfehler erreich bar.

Die Ver- und Entschachtelung des Datensignals erfolgt Daten blockweise, d. h. Datenblock für Datenblock wird nach einer jeweils gleichen Verschachtelungsvorschrift vom senderseiti gen Verschachteler verschachtelt und nach der inversen (eben falls jeweils gleichen) Entschachtelungsvorschrift vom Ent schachteler im Empfänger entschachtelt.

Zu diesem Zweck müssen vor der ersten Ver- bzw. Entschachte lung die entsprechenden Zieladressen (Verschachtelungs- Zieladressen bzw. Entschachtelungs-Zieladressen) für die Um sortierung der Datensymbole berechnet werden. Bisher ge schieht dies so, daß vor Durchführung der ersten Ver- bzw. Entschachtelungsprozedur Zieladressen für sämtliche Datensym bole eines Datenblocks berechnet und in einem Verschachte lungs-Zieladressenspeicher bzw. Entschachtelung-Zieladres senspeicher abgelegt werden. Bei einem Datenblock bestehend aus K Datensymbolen müssen die Zieladressenspeicher jeweils K Zieladressen-Speicherplätze umfassen. Die Zieladressenspeicher enthalten somit die kompletten Ver- bzw. Entschachte lungsinformationen.

Nachteilig bei diesem Verfahren der Entschachtelung ist, daß ein großer Speicherplatzbereich im Empfänger eingerichtet sein muß. Für den UMTS-(Universal Mobile Telecommunications System-)Standard, der eine Datenblocklänge K zwischen 40 und 5114 Bits erlaubt, wird für die Abspeicherung der Entschach telungs-Zieladressen ein Speicher mit 5114 Speicherzellen ei ner Adreßdatenbreite von 13 Bit benötigt.

Üblicherweise erfolgt die Verschachtelung eines Datensignals nach der Kanalcodierung. Bei einer speziellen Form der Ka nalcodierung, die als Turbo-Codierung bezeichnet wird, wird jedoch bereits bei der Kanalcodierung eine Verschachtelungs prozedur durchgeführt. Diese im Rahmen der Turbo-Codierung durchgeführte Verschachtelung wird im folgenden als Turbo- Verschachtelung bezeichnet.

Turbo-Codes sind binäre, parallel verkettete, rekursive, sy stematische Faltungscodes. Durch die Verwendung von Turbo- Codes läßt sich insbesondere beim Übertragen von großen Da tenblöcken bestehend aus mehr als z. B. 1000 Bits ein erheb lich besserer Fehlerschutzgrad als mit üblichen Faltungscodes erzielen. Die Struktur eines Turbo-Codes sowie die Erzeugung desselben unter Verwendung eines Turbo-Codierers mit inte griertem Turbo-Verschachteler sind bekannt und beispielsweise detailliert in dem Buch "Analyse und Entwurf digitaler Mobil funksysteme", von P. Jung, Stuttgart, B. G. Teubner-Verlag, 1997, Anhang E, Seiten 343-368, beschrieben.

Beim Empfang des Turbo-codierten, über einen Übertragungska nal (z. B. Mobilfunkkanal) übertragenen Datensignals muß im Empfänger im Zuge der Turbo-Decodierung auch die Turbo-Ver schachtelung rückgängig gemacht werden. Dieser Prozeß wird als Turbo-Entschachtelung bezeichnet und durch einen im Tur bo-Decodierer integrierten Turbo-Entschachteler bewerkstelligt. Die Turbo-Ver- und Entschachtelung des Datensignals er folgt ebenfalls Datenblockweise.

Der Erfindung liegt die Aufgabe zugrunde, ein verbessertes Verfahren zur Entschachtelung, insbesondere Turbo-Entschach telung, eines blockweise verschachtelten Datensignals anzuge ben. Insbesondere soll das Entschachtelungsverfahren einen möglichst geringen Speicherplatzbedarf haben.

Zur Lösung der Aufgabenstellung sind die Merkmale des An spruchs 1 vorgesehen.

Demnach wird jeder Datenblock sukzessive entschachtelt, indem Entschachtelungs-Zieladressen zunächst nur für einen vorbe stimmten Abschnitt des Datenblocks berechnet werden, nachfol gend eine Entschachtelung des entsprechenden Abschnitts des erhaltenen (verschachtelten) Datenblocks durchgeführt wird, und dieser Vorgang so oft wiederholt wird, bis der gesamte Datenblock Abschnitt für Abschnitt entschachtelt ist. Auf diese Weise wird der Speicherplatzbedarf bei der Entschachte lung wesentlich reduziert, weil lediglich die Entschachte lungs-Zieladressen von Datenblockabschnitten und nicht des gesamten Datenblocks gespeichert werden müssen.

Demzufolge kennzeichnet sich eine vorteilhafte Ausgestaltung der Erfindung dadurch, daß die in dem nächsten Schritt be rechneten Entschachtelungs-Zieladressen unter Überschreiben der zuvor in dem Zieladressenspeicher abgelegten Zieladressen abgespeichert werden.

Eine weitere vorteilhafte Ausgestaltung des erfindungsgemäßen Verfahrens kennzeichnet sich dadurch, daß die Verschachtelung nach mehreren unterschiedlichen Verschachtelungsvorschriften durchführbar ist, daß eine Erzeugungsregel zur Berechnung der unterschiedlichen Verschachtelungsvorschriften vorgegeben ist, und daß die Vorausberechnung der Entschachtelungs- Zieladressen bezüglich der Abschnitte von Datensymbolen unmittelbar aus der Erzeugungsregel ohne vorhergehende Berech nung von Zieladressen für die Verschachtelung vorgenommen wird. Aufgrund des Wegfalls der Berechnung der Verschachte lungs-Zieladressen wird eine weitere Verminderung des Spei cherplatzbedarfs für die Entschachtelung erreicht.

Bei der Erzeugungsregel kann es sich um den UMTS-Standard TS 25.212 handeln, welcher für jede Datenblocklänge K eine Tur bo-Verschachtelungsvorschrift in Form einer Koordinaten- Transformationsmatrix bestehend aus R Zeilen und C Spalten definiert. In diesem Fall kann jeder der vorgegebenen Ab schnitte eines Datenblocks eine Anzahl von nz.C aufeinander folgenden Datensymbolen des verschachtelten Datensignals auf weisen, wobei nz eine ganze Zahl gleich oder größer 1 ist.

Vorzugsweise ist nz = 1, d. h. es wird eine zeilenweise Turbo- Entschachtelung des Datenblocks vorgenommen.

Nachfolgend wird die Erfindung anhand eines die Turbo-Ent schachtelung (gemäß UMTS-Standard TS 25.212) betreffenden Ausführungsbeispiels unter Bezugnahme auf die Zeichnung näher erläutert; in dieser zeigt:

Fig. 1 ein Blockschaltbild eines bekannten Turbo-Codierers zur Erzeugung eines Turbo-Codes;

Fig. 2 ein Blockschaltbild eines bekannten Turbo-Decodierers zur Decodierung eines Turbo-codierten Empfangssignals;

Fig. 3 eine Darstellung zur Erläuterung einer Verschachte lungs-Permutationsmatrix und der inversen Permuta tionsmatrix sowie des erfindungsgemäßen Prinzips der abschnittsweisen Turbo-Entschachtelung;

Fig. 4 eine Darstellung zur Erläuterung der Intra-Zeilen Per mutation bei der Erzeugung einer Verschachtelungs- Transformationsmatrix für K = 3840 im UMTS-Standard; und

Fig. 5 eine Darstellung entsprechend Fig. 4, in welcher die Hintereinanderausführung von zwei Koordinatentrans formationen zur Realisierung der Intra-Zeilen Permuta tion und einer Koordinatentransformation zur Realisie rung der Inter-Zeilen Permutation für die Erzeugung der UMTS-Verschachtelungs-Transformationsmatrix darge stellt sind.

Fig. 1 zeigt beispielhaft das Blockschaltbild eines Turbo- Codierers TCOD, wie er in einem UMTS-Sender zur Erzeugung ei nes Turbo-codierten Datensignals D eingesetzt werden kann. Im Rahmen der Erfindung können auch andere Turbo-Codierer ver wendet werden.

Der Turbo-Codierer TCOD weist einen Turbo-Verschachteler IL, zwei identische, rekursive, systematische Faltungscodierer RSC1 und RSC2 (z. B. 8-Zustands-Faltungscodierer), zwei optio nale Punktierer PKT1 und PKT2 und einen Multiplexer MUX auf.

Die Aufgabe des Turbo-Codierers TCOD besteht darin, einem di gitalen Eingabesignal X zur Fehlerschutzcodierung Redundanz hinzuzufügen. Das Eingabesignal besteht aus einer Folge von Datensymbolen, z. B. Bits. Bei dem digitalen Eingabesignal X kann es sich beispielsweise um ein quellencodiertes Sprach- oder Videosignal handeln.

Der Turbo-Codierer TCOD erzeugt ein digitales Ausgabesignal D, das durch Multiplexen des Eingabesignals X (sogenanntes systematisches Signal), eines von RSC1 codierten und ggf. von PKT1 punktierten Signals Y1 und eines von IL verschachtelten, von RSC2 codierten und ggf. von PKT2 punktierten Signals Y2 erzeugt wird.

Der Turbo-Verschachteler IL führt eine blockweise Verschach telung des Eingabesignals X durch. Das heißt, daß der Turbo- Verschachteler IL in ständiger Wiederholung jeweils K Datensymbole (K ist eine ganze, positive Zahl und bezeichnet die Datenblocklänge) entgegennimmt, umsortiert und in geänderter Reihenfolge wieder ausgibt. Das Umsortieren (Permutieren) der Datensymbole erfolgt nach einer für eine konstante Daten blocklänge K immer gleichen Vorschrift.

Im UMTS-Standard ist die Blocklänge K variabel und liegt zwi schen 40 und 5114 Bits. Wie später noch näher erläutert wird, ist für jede Datenblocklänge im Standard eine spezielle Ver schachtelungsvorschrift vorgeschrieben.

Das fehlerschutzcodierte Datensignals D wird dann in geeigne ter Weise auf einen Träger moduliert und über einen Übertra gungskanal (z. B. Mobilfunkkanal) übertragen.

Die Decodierung eines Turbo-codierten Empfangssignals in ei nem Empfänger wird nachfolgend unter Bezugnahme auf den in Fig. 2 gezeigten, bekannten Turbo-Decodierer TDEC erläutert. Auch andere Bauweisen von Turbo-Decodierern sind möglich und können zur Durchführung des erfindungsgemäßen Verfahrens ein gesetzt werden.

Der Turbo-Decodierer TDEC umfaßt einen ersten und einen zwei ten Demultiplexer DMUX1 und DMUX2, einen Speicher MEM, einen ersten und zweiten Faltungsdecodierer DEC1 und DEC2, einen Turbo-Verschachteler IL', einen ersten und einen zweiten Tur bo-Entschachteler DIL1 und DIL2 sowie eine Entscheidungslogik (Schwellenwertentscheider) TL.

Von einem Demodulator (nicht dargestellt) des Empfängers wird eine entzerrte Datenfolge bereitgestellt, die die im Emp fänger rekonstruierte codierte Datenfolge D ist.

Die Funktionsweise des in Fig. 2 gezeigten Turbo-Decodierers TDEC wird im folgenden kurz erläutert.

Der erste Demultiplexer DMUX1 spaltet das entzerrte Datensi gnal in das entzerrte systematische Datensignal (rekonstruierte Version des Eingabesignals X) und ein ent zerrtes Redundanzsignal auf. Letzteres wird von dem zwei ten Demultiplexer DMUX2 in die beiden entzerrten Redundanz- Teilsignale 1 und 2 (rekonstruierte Versionen der Redun danz-Teilsignale Y1 und Y2) aufgespalten.

Die beiden Faltungsdecodierer DEC1 und DEC2 können z. B. MAP- Symbolschätzer sein. Der erste Faltungsdecodierer DEC1 be rechnet ausgehend von den Datensignalen und 1 und einem Rückkoppelsignal Z logarithmische Zuverlässigkeitsdaten Λ1 in Form von LLRs (Log-Likelihood Ratios).

Die Zuverlässigkeitsdaten Λ1 werden von dem Turbo-Verschach teler IL' verschachtelt und die verschachtelten Zuverlässig keitsdaten Λ1_I werden dem zweiten Faltungsdecodierer DEC2 zu geführt. Die Arbeitsweisen der Turbo-Verschachteler IL und IL' sind identisch. Der zweite Faltungsdecodierer DEC2 be rechnet aus den verschachtelten Zuverlässigkeitsdaten Λ1_I und aus den rekonstruierten Redundanz-Teilsignaldaten 2, die in dem Speicher MEM bereitgehalten werden, ein verschachteltes Rückkoppelsignal Z_I und verschachtelte zweite logarithmische Zuverlässigkeitsdaten Λ2_I, ebenfalls in Form von LLR's.

Das verschachtelte Rückkoppelsignal Z_I wird von dem ersten Turbo-Entschachteler DIL1 entschachtelt und ergibt das Rück koppelsignal Z.

Die dargestellte Rekursionsschleife wird mehrmals (z. B. 5 Mal) durchlaufen. Jedem Durchlauf liegen die Daten desselben Datenblocks zugrunde. Die beim letzten Durchlauf erhaltenen verschachtelten zweiten Zuverlässigkeitsdaten Λ2_I werden von dem zweiten Entschachteler DIL2 entschachtelt und als ent schachtelte Zuverlässigkeitsdaten Λ2 der Entscheidungslogik TL zugeführt. Diese bestimmt daraufhin ein Datensignal E(X), welches eine Folge von Schätzwerten für die Datensymbole des Eingabesignals X ist.

Nach der Turbo-Decodierung eines Datenblocks und Ausgabe der entsprechenden Folge von Schätzwerten E(X) wird der nächste Datenblock Turbo-decodiert.

Eine detaillierte Beschreibung der Arbeitsweise eines Turbo- Decodierers ist in dem Kapitel E.3.3 "Rekursive MAP-Symbol schätzung" des genannten Buchs von P. Jung auf den Seiten 353 bis 361 angegeben, die hiermit zum Inhalt dieser Schrift wird.

Wie beispielhaft an dem in Fig. 2 dargestellten Turbo-De codierer TDEC ersichtlich, umfaßt eine Turbo-Decodierung bei jedem Schleifendurchlauf eine Turbo-Verschachtelungsprozedur (IL') und eine Turbo-Entschachtelungsprozedur (DIL1) sowie eine abschließende Turbo-Entschachtelungsprozedur (DIL2). Die beiden Turbo-Entschachtelungsprozeduren sind identisch.

Die Verschachtelungsvorschrift kann mathematisch durch eine Permutation beschrieben werden. Die Permutation ordnet jeder Ausgangs- oder Quellenadresse eindeutig eine Zieladresse für die Umsortierung der Datensymbole eines Datenblocks zu. Quel lenadresse ist die ursprüngliche Stelle des Datensymbols im Datenblock und die Zieladressen ist die Stelle des umsor tierten Datensymbols im verschachtelten Datenblock.

In Fig. 3 wird das der Erfindung zugrundeliegende Prinzip an hand eines einfachen Beispiels erläutert.

Zunächst wird der Verschachtelungsvorgang betrachtet. Eine einen Datenblock bildende Datenfolge bestehend aus K = 9 Daten symbolen {a, b, c, d, e, f, g, h, i} soll verschachtelt werden. Fig. 3, oberer Teil, zeigt einen als 3 × 3-Speicherzellen-Matrix dargestellten Verschachtelungs-Eingabedatenspeicher V_iDS, einen als 3 × 3-Speicherzellen-Matrix dargestellten Verschachtelungs-Ausgabedatenspeicher V_fDS und eine 3 × 3-Permutations matrix P, deren Elemente ebenfalls in einem Speicher (Zieladressenspeicher) abgelegt sind.

Die Datenfolge wird in den Verschachtelungs-Eingabedaten speicher V_iDS eingelesen und dort, wie in Fig. 3 darge stellt, in Zeilenrichtung abgespeichert.

Die Speicherplätze der Datenspeicher V_iDS und V_fDS sind in Zeilenrichtung mit Adressen n = 1 bis 9 durchnumeriert. Die Adressen n sind im rechten oberen Eck der jeweiligen Spei cherzellen eingetragen.

Die Permutationsmatrix P gibt für das im Verschachtelungs- Eingabedatenspeicher V_iDS in der Speicherzelle mit Adresse n abgespeicherte Datensymbol die Verschachtelungs-Zieladresse V-Adr(n) im Verschachtelungs-Ausgabedatenspeicher V_fDS an. Beim Verschachteln wird demnach das in V_iDS auf Speicher platz 1 abgespeicherte Datensymbol, nämlich a, in V_fDS auf dem Speicherplatz 3 abgespeichert, das in V_iDS auf Speicher platz 2 abgespeicherte Datensymbol, nämlich b, wird in V_fDS auf dem Speicherplatz 7 abgespeichert, . . usw. Das Auslesen des Verschachtelungs-Ausgabedatenspeichers V_fDS erfolgt ebenfalls in Zeilenrichtung, d. h. die verschachtelte Daten folge lautet {g, e, a, c, h, f, b, i, d}.

Das Entschachteln wird gemäß Fig. 3, unterer Teil, analog dem Verschachteln, jedoch unter Verwendung der inversen Permuta tionsmatrix (der Begriff invers bezieht sich auf die Operati on der Nacheinanderausführung von Permutationen), bezeichnet als P^-1, durchgeführt. Die inverse Permutationsmatrix P^-1 ist in Fig. 3 angegeben. Die Elemente der inversen Permutations matrix sind in einem Entschachtelungs-Zieladressenspeicher gespeichert.

Es wird nun angenommen, daß der Verschachteler in der Lage sein soll, eine Vielzahl von unterschiedlichen Verschachtelungsvorschriften auszuführen. Dabei sollen die diversen Ver schachtelungsvorschriften nicht in Form einer Vielzahl von im Verschachteler abgespeicherten Permutationsmatrizen bereitge halten werden, sondern es wird im folgenden vorausgesetzt, daß eine spezielle Erzeugungsregel existiert, mit der die verschiedenen Permutationsmatrizen in Abhängigkeit von einem oder mehreren Erzeugungsparametern (z. B. der Datenblocklänge K) aufgebaut werden können. Wie im folgenden noch dargelegt, sind diese Voraussetzungen bei der Turbo-Verschachtelung ge mäß dem UMTS-Standard erfüllt.

Die herkömmliche Vorgehensweise zur Durchführung der Ent schachtelung ist die folgende: Zunächst wird gemäß der Erzeu gungsregel die gewünschte Permutationsmatrix P vollständig (d. h. sämtliche Verschachtelungs-Zieladressen) berechnet. Dann wird die vollständig berechnete Permutationsmatrix P in vertiert. Mittels der invertierten Permutationsmatrix P^-1 wird dann die Entschachtelung vorgenommen.

Das erfindungsgemäße Vorgehen bei der Turbo-Entschachtelung unterscheidet sich von der herkömmlichen Vorgehensweise da durch, daß zunächst nur ein bestimmter, vorgegebener Ab schnitt der inversen Permutationsmatrix P^-1, z. B. die in der ersten Zeile angegebenen Entschachtelungs-Zieladressen E- Adr(n) = 7, 5, 1, (schraffiert dargestellt) für n = 1, 2, 3 be stimmt werden. Anschließend, d. h. vor der Bestimmung weiterer Entschachtelungs-Zieladressen, wird eine erste teilweise Ent schachtelung des verschachtelten Datensignals vorgenommen. Dabei werden die ersten drei Datensymbole g, e, a der ver schachtelten Datenfolge, die in dem Entschachtelungs-Einga bedatenspeicher E_iDS (entspricht V_fDS) auf den ersten drei Speicherplätzen abgespeichert sind, in die Speicherplätze 7, 5, 1 des Entschachtelungs-Ausgabedatenspeichers E_fDS ge schrieben. Anschließend wird ein weiterer vorgegebener Ab schnitt der inversen Permutationsmatrix P^-1, z. B. die in der zweiten Zeile angegebenen Entschachtelungs-Zieladressen 3, 8, 6, berechnet. Dann wird wiederum der diesbezügliche Schreibvorgang durchgeführt. Diese Vorgehensweise wird solan ge fortgesetzt, bis die verschachtelte Datenfolge vollständig entschachtelt ist.

Mit anderen Worten werden weder die Permutationsmatrix P noch aus dieser die inverse Permutationsmatrix P^-1 vollständig be rechnet, sondern es werden immer nur jeweils die Matrixele mente (Entschachtelungs-Zieladressen) der inversen Permutati onsmatrix P^-1 berechnet, die für die Entschachtelung des vor gegebenen Abschnitts des verschachtelten Datenblocks gerade benötigt werden. Vorteilhaft ist dabei der geringe Speicher platzbedarf zum Abspeichern der Entschachtelungs-Zieladressen im Entschachtelungs-Zieladressenspeicher, da in jedem Ent schachtelungsschritt die im vorhergehenden Entschachtelungs schritt verwendeten Zieladressen überschrieben werden können. Bei dem erläuterten Beispiel (d. h. bei einer zeilenweisen Entschachtelung) muß der Entschachtelungs-Zieladressen speicher nicht neun sondern nur drei Speicherzellen umfassen.

Es wird bemerkt, daß die Möglichkeit, die Verschachtelungs- Permutationsmatrix P mittels der Erzeugungsregel gezielt für bestimmte, vorgegebene Abschnitte berechnen zu können, nicht impliziert, daß auch eine abschnittsweise Berechnung der in versen Permutationsmatrix P^-1 bezüglich vorgebbarer Abschnit te möglich ist. Berechnet man z. B. die Verschachtelungs- Zieladressen der ersten Zeile der Permutationsmatrix P, er hält man die Werte 3, 7, 4. Mit diesen Werten lassen sich die Adressen 1, 2, 3 der inversen Permutationsmatrix P^-1 (punktiert dargestellt) berechnen, die jedoch nicht zur Entschachtelung eines vorgegebenen Abschnitts von Datensymbolen, z. B. der in der ersten Zeile des Speichers E_iDS abgespeicherten Daten symbole, ausreichen. Dieses Beispiel macht deutlich, daß selbst dann, wenn eine abschnittsweise Berechnung der Permu tationsmatrix P möglich sein sollte, für die Berechnung eines vorgegebenen Abschnitts der inversen Permutationsmatrix P^-1 zunächst im allgemeinen die vollständige Permutationsmatrix P zu berechnen ist.

Im folgenden wird für den Fall des UMTS-Standards eine Mög lichkeit der partiellen Berechnung der inversen Permutations matrix P^-1 (Entschachtelungs-Zieladressenmatrix) angegeben. Die Erkenntnis, daß eine solche abschnittsweise Berechnung der inversen Permutationsmatrix P^-1 im UMTS-Standard möglich ist, ist Teil der Erfindung.

Wie bereits erwähnt, ist in dem UMTS-Standard eine Erzeu gungsregel angegeben, mittels der für jede mögliche Blocklän ge K eine spezielle Verschachtelungsvorschrift generiert wer den kann. Jede Verschachtelungsvorschrift ist in Form einer Koordinatentransformation zwischen dem Entschachtelungs- Eingabedatenspeicher E_iDS und dem Entschachtelungs-Ausgabe datenspeicher E_fDS angegeben.

Zum besseren Verständnis der Erfindung wird nachfolgend zu nächst die im UMTS-Standard TS 25.212 V3.3.0 vereinbarte Er zeugungsregel zur Bestimmung der zugehörigen Koordinaten- Transformationsmatrix wiedergegeben. Die Koordinaten-Trans formationsmatrix enthält die gleiche Information wie die an hand Fig. 3 erläuterte Permutationsmatrix, unterscheidet sich von dieser jedoch dadurch, daß die Permutationsvorschrift in Form einer zweidimensionalen Koordinatentransformation (und nicht einer eindimensionalen Zieladressen-Zuweisungsvor schrift) dargestellt ist.

1. Schritt (Definition der Transformationsmatrix)

1.1 Definition der Anzahl R der Zeilen:
R = 5, falls K = 40 bis 159 Bits (Fall 1)
R = 10, falls K = 160 bis 200 Bits oder K = 481 bis 530 Bits (Fall 2)
R = 20, andernfalls (Fall 3)
1.2 Definition der Anzahl C der Spalten:
Fall 2, für K = 481 bis 530 Bits: C = p = 53 sonst:

a) Suche der minimalen Primzahl p, so daß
0 ≦ (p + 1) - K/R
b) falls 0 ≦ p - K/R, dann gehe zu (iii) sonst: C = p + 1
c) falls 0 ≦ p - 1 - K/R, dann: C = p - 1 sonst: C = p

1.3 Die Eingabedatensequenz wird dann Zeile für Zeile in eine R×C-Eingabedaten-Speichermatrix (entspricht V_iDS) ge schrieben.

2. Schritt (Intra-Zeilen Permutation) Fall A: C = p

1. Auswahl einer primitiven Wurzel g aus der folgenden Ta belle:
2. Konstruktion einer Basissequenz c(i) für die Intra- Zeilen Permutation nach:
c(i) = [g.c(i - 1)]modp, i = 1, 2, . ., (p - 2) c(0) = 1
wobei mod die Modulo-Operation bezeichnet.
3. Suche nach dem Satz {q_j} der minimalen Primzahlen, j = 1, 2, . ., R - 1, mit:
- - ggT{q_j, p - 1} = 1 (ggT = größter gemeinsamer Teiler)
- - q_j < 6
- - q_j < q_j-1
- - q₀ = 1
4. Der Satz {g_j} wird permutiert, der durch die Permutation erhaltene Satz mit {p_j} bezeichnet, die Permutationsvor schrift lautet:
p_PX(j) = q_j, j = 0, 1 . . ., R - 1,
wobei P_X(j) die Inter-Zeilen Permutation ist, die im dritten Schritt definiert wird.
5. Durchführen der j-ten Intra-Zeilen Permutation, j = 0, 1, . . ., R - 1, nach:
c_j(i) = c([i.p_j]mod(p - 1)), i = 0, 1, 2, . ., (p - 2) und c_j(p - 1) = 0,
wobei c_j(i) die Position des Eingabebits des i-ten Aus gangs nach der Permutation der j-ten Zeile ist.

Fall B: C = p + 1

1. Wie Fall A1
2. Wie Fall A2
3. Wie Fall A3
4. Wie Fall A4
5. Durchführen der j-ten Intra-Zeilen Permutation, j = 0, 1, . . ., R - 1, nach:
c_j(i) = c([i.p_j]mod(p - 1)), i = 0, 1, 2, . ., (p - 2) und c_j(p - 1) = 0, und c_j(p) = p,
6. Falls K = C.R, dann tausche c_R-1(p) gegen c_R-1(0) aus, wobei c_j(i) die Position des Eingabebits des i-ten Ausgangs nach der Permutation der j-ten Zeile ist.

Fall C: C = p - 1

1. Wie Fall A1
2. Wie Fall A2
3. Wie Fall A3
4. Wie Fall A4
5. Durchführen der j-ten Intra-Zeilen Permutation, j = 0, 1, . . , R - 1, nach:
c_j(i) = c([i.p_j]mod(p - 1)) - 1, i = 0, 1, 2, . ., (p - 2), wo bei c_j(i) die Position des Eingabebits des i-ten Aus gangs nach der Permutation der j-ten Zeile ist.

3. Schritt (Inter-Zeilen Permutation)

Durchführen der Inter-Zeilen Permutation P_X(j), j = 0, 1, . ., R - 1, X = A, B, C oder D, nach den folgenden Schemata, wobei P_X(j) die ursprüngliche Position der j-ten permutierten Zeile ist:

P_A: {19, 9, 14, 4, 0, 2, 5, 7, 12, 18, 10, 8, 13, 17, 3, 1, 16, 6, 15, 11} für R = 20

P_B: {19, 9, 14, 4, 0, 2, 5, 7, 12, 18, 16, 13, 17, 15, 3, 1, 6, 11, 8, 10} für R = 20

P_C: {9, 8, 7, 6, 5, 4, 3, 2, 1, 0} für R = 10

P_D: {4, 3, 2, 1, 0} für R = 5

Die verschiedenen Schemata werden folgendermaßen eingesetzt:

mit X = A oder B oder C oder D

Fig. 4 erläutert anhand eines Beispiels für K = 3840 den Aufbau der Transformationsmatrix. Dabei werden die einzelnen Elemen te der Matrix anhand ihrer Zeilen-Spalten Koordinaten (j, i) identifiziert und die durch den obigen Standard vorgeschrie bene Koordinaten-Transformationen betrachtet.

Gemäß den Definitionen unter den Punkten 1.1 und 1.2 ergibt sich C = 192 (Anzahl der Spalten) und R = 20 (Anzahl der Zeilen). Die minimale Primzahl lautet p = 191.

Für den 2. Schritt gilt Fall B. Gemäß dem Schritt B1 wird die primitive Wurzel g für p = 191 bestimmt. Es ergibt sich g = 19.

In Schritt B2 wird die Basissequenz c(i) berechnet. Die be rechneten Werte c(i) sind in Fig. 4 in dem fett umrandeten horizontalen Bereich angegeben.

In dem Schritt B3 wird der Satz {q_j} der minimalen Primzah len, j = 0 bis R - 1, berechnet. Der Satz der minimalen Primzah len lautet:

{1, 7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83}

Im folgenden Beispiel wird der Schritt B5 mit dem Satz {g_j} der minimalen Primzahlen durchgeführt; der Übergang auf den Satz der permutierten minimalen Primzahlen erfolgt erst nach folgend bei der Inter-Zeilen Permutation. Somit wird für die j-te Zeile die zugehörige Intra-Zeilen Permutation nach der Gleichung c_j(i) = c ([i.q_j]mod(p - 1)) berechnet. Die Intra-Zeilen Permutationsvorschrift c_j(i) würde, sofern sie gesondert an den Datensymbolen im Verschachtelungs-Eingabedatenspeicher V_iDS ausgeführt würde (was nicht der Fall ist, da sie ledig lich zum Aufbau der Transformationsmatrix dient), bewirken, daß ein in dem Verschachtelungs-Eingabedatenspeicher V_iDS auf die Zeilen-Spalten Koordinate (j, i) eingelesenes Daten symbol auf eine Speicherzelle eines (fiktiven) Zwischenspeichers mit der Zeilen-Spalten Koordinate (j, c_j(i)) abgespei chert würde.

Die Intra-Zeilen Permutation c_j(i) hängt von dem Zeilenindex j ab, d. h. ist für jede Zeile unterschiedlich.

Gemäß der im Schritt B5 angegebenen Gleichung kann die Intra- Zeilen Permutation als Nacheinanderausführung einer "inneren" Intra-Zeilen Permutation nach der Vorschrift

c_in_j(i) = [i.q_j]mod(p - 1)

und einer "äußeren" Intra-Zeilen Permutation nach der Vor schrift

c_out(i) = c(i)

durchgeführt werden.

Die innere Intra-Zeilen Permutation c_in_j(i) ist für jede Zeile unterschiedlich, während die äußere Intra-Zeilen Permu tation c_out(i) für sämtliche Zeilen identisch ist.

Einige der bei der inneren Intra-Zeilen Permutation erhalte nen Spalten-Zielkoordinatenwerte c_in_j(i) sind in der in Fig. 4 dargestellten R×C-Transformationsmatrix eingetragen. Für i = 1 (1-te Spalte) ergibt sich die Sequenz {q_j} der minimalen Primzahlen.

Die Werte in der Spalte i = 4 sind in der Fig. 4 fett umrandet. Sie berechnen sich gemäß der Gleichung c_in_j(4) = [4.q_j]mod190.

Für die Speicherzelle mit der Koordinate i = 4, j = 3 ergibt sich der Wert c_in₃(4) = [4.13]mod190 = 52.

Die innere Intra-Zeilen Permutation, die also die Koordinate (3, 4) auf die Koordinate (3, 52) abbildet, wird in Fig. 5 durch den Pfeil A veranschaulicht.

Die äußere Intra-Zeilen Permutation c_out(i) wird durch den Pfeil B dargestellt. Die Zielkoordinate (3, 52) der inneren Intra-Zeilen Permutation, die die Ausgangskoordinate für die äußere Intra-Zeilen Permutation ist, wird auf die Zielkoor dinate (3, 86) der äußeren Intra-Zeilen Permutation abgebildet (die damit auch die Zielkoordinate der gesamten Intra-Zeilen Permutation ist).

Im Ergebnis folgt für dieses Beispiel:

c₃(4) = c_out(c_in₃(4)) = 86

In dem 3. Schritt wird die Inter-Zeilen Permutation gemäß dem Schema P_A ausgeführt. Da P_A(j = 3) = 4, wird die Zielkoordinate (3, 86) der Intra-Zeilen Permutation auf die Zielkoordinate (4, 86) der Inter-Zeilen Permutation abgebildet. Die Inter- Zeilen Permutation entspricht einem (tatsächlich nicht statt findenden) Transfer des in der Speicherzelle des fiktiven Zwischenspeichers mit der Koordinate (3, 86) abgespeicherten Datensymbols in die Speicherzelle des Verschachtelungs-Aus gabedatenspeichers V_fDS mit der Koordinate (4, 86). Die In ter-Zeilen Permutation wird in Fig. 5 durch den Pfeil C ver anschaulicht.

Allgemein ergibt sich für die Verschachtelung somit die UMTT- Koordinaten-Abbildungsvorschrift:

(j, i) → (P_X(j), c_j(i))

Aus der Koordinaten-Abbildungsvorschrift der Transformations matrix lassen sich die eindimensionalen Verschachtelungs- Zieladressen der Permutationsmatrix P gemäß der folgenden Be ziehung berechnen:
Quellenadresse: n = j.C + i
Verschachtelungs-Zieladresse: V-Adr(n) = P_X(j).C + c_j(i)

Damit ist die Permutationsmatrix gemäß Fig. 3, oberer Teil, berechenbar.

Für das Beispiel ergibt sich:
Quellenadresse: n = 3.192 + 4 = 580
Verschachtelungs-Zieladresse: V-Adr(579) = 4.192 + 86 = 854

Das heißt, in der Permutationsmatrix P steht in dem Feld mit der Adresse n = 580 (entspricht der Koordinate (3, 4)) der Ver schachtelungs-Zieladressenwert 854.

Im folgenden wird erläutert, wie gemäß der Erfindung die Ent schachtelungs-Zieladressen der ersten Zeile der inversen Per mutationsmatrix P^-1 berechnet werden können, ohne zuvor eine Berechnung der Permutationsmatrix P durchführen zu müssen.

Zunächst wird die Zeilen- und Spaltenzahl der inversen Permu tationsmatrix P^-1 bestimmt. Die Bestimmung erfolgt gemäß dem Schritt 1, das heißt ist identisch mit der Bestimmung der Zeilen- und Spaltenzahl der Permutationsmatrix P.

Die Koordinaten der inversen Permutationsmatrix P^-1 werden in der Form (j, i), das heißt ebenfalls als Zeilen-Spalten- Koordinaten, angegeben.

Zunächst wird die inverse Abbildung der im UMTS-Standard un ter Schritt 3 definierten Inter-Zeilen Permutation ausge führt. Die inversen Inter-Zeilen Permutationen P_X ^-1(j), j = 0, 1, . ., R - 1, lauten für die Fälle X = A, B, C oder D:
P^-1 _A: {4, 15, 5, 14, 3, 6, 17, 7, 11, 1, 10, 19, 8, 12, 2, 18, 16, 13, 9, 0} für R = 20
P^-1 _B: {4, 15, 5, 14, 3, 6, 16, 7, 18, 1, 19, 17, 8, 11, 2, 13, 10, 12, 9, 0} für R = 20
P^-1 _C: {9, 8, 7, 6, 5, 4, 3, 2, 1, 0} für R = 10
P^-1 _D: {4, 3, 2, 1, 0} für R = 5

Die Auswahl X = A, B, C oder D der inversen Inter-Zeilen Permu tation folgt aus dem unter Schritt 3 angegebenen Schema.

Die Koordinaten-Abbildungsvorschrift der inversen Inter- Zeilen Permutation ist:

(j, i) → (P_X ^-1(j), i)

Dabei ist (j, i) die Ausgangskoordinate einer Speicherzelle des Entschachtelungs-Eingabedatenspeichers E_iDS.

In einem nächsten Schritt wird die Zeilen-Koordinate durch aufeinanderfolgendes Ausführen der Umkehrabbildungen der äu ßeren Intra-Zeilen Permutation und der inneren Intra-Zeilen Permutation berechnet.

Die Koordinatentransformation bezüglich der inversen äußeren Intra-Zeilen Permutation lautet:

(P_X ^-1(j), i) → (P_X ^-1(j), c_out^-1(i))

Dabei bezeichnet c_out^-1(i) = c^-1(i) die inverse äußere Intra- Zeilen Permutation.

In einem letzten Koordinaten-Transformationsschritt wird die inverse innere Intra-Zeilen Permutation ausgeführt. Die ent sprechende Abbildungsvorschrift lautet:

Die Berechnung der Entschachtelungs-Zieladressen E-Adr(n) er folgt dann unter Verwendung der nachstehenden Abkürzungen

gemäß der Gleichung

E-Adr(n) = d_j.C + d_i

wobei n = j.C + i die Quellen-Adresse des in dem Entschachte lungs-Eingabedatenspeicher E_iDS abgespeicherten verschach telten Datensignals ist.

Ausnahmen dieses Entschachtelungsschemas treten bei den Spal ten p - 1 und p für den Fall C = p + 1 und für die Spalte p - 1 für den Fall C = p auf.

Diese Spalten werden nicht der Intra-Zeilen Permutation un terworfen, das heißt bei ihnen wird weder die äußere Intra- Zeilen Permutation noch die innere Intra-Zeilen Permutation vorgenommen. Deshalb beschränkt sich der Entschachtelungsab lauf auf die Umkehrung der Inter-Zeilen Permutation.

Bei der Entschachtelung wird bezüglich der Spalte p lediglich die Inter-Zeilen Permutation durchgeführt. Das Ergebnis der Entschachtelung lautet daher:

d_i = i = p

d_j = P_X ^-1(j), X = A, B, C oder D

Die Spalte p - 1 wird bei der Verschachtelung der Inter-Zeilen Permutation unterzogen und dann auf die Spalte 0 abgebildet. Das Ergebnis des Entschachtelungsablaufs ist daher:

d_i = p - 1 für i = 0

d_j = P_X ^-1(j) X = A oder B oder C oder D

Die Berechnung der Entschachtelungs-Zieladressen erfolgt auch hier gemäß der bereits angegebenen Formel E-Adr(n) = d_j.C + d_i

Bei der Durchführung des Entschachtelungsschrittes werden nun zunächst die Ziel-Entschachtelungsadressen E-Adr(n) für einen bestimmten vorgegebenen Abschnitt des Entschachtelungs- Eingabedatenspeichers E_iDS, z. B. in dem beschriebenen Bei spiel die Entschachtelungsadressen n = 0, 1, . ., 191 für eine bestimmte Zeile j, berechnet. Hierzu müssen zu dem Zeilenin dex j der Zeilenkoordinatenwert Wert d_j und sämtliche Spal tenkoordinatenwerte d_i berechnet werden. Die berechneten Ent schachtelungs-Zieladressen E-Adr(n) für die Zeile j werden im Zieladressenspeicher abgespeichert. Dieser muß zu diesem Zweck beim betrachteten Beispiel lediglich 192 Speicherzel len, allgemein maximal 256 Speicherzellen, einer Wortbreite von z. B. 13 Bits aufweisen. Bei einem aus mehreren Zeilen be stehenden Datenblockabschnitt ist der Zieladressenspeicher entsprechend größer auszulegen.

Mittels dieser 192 Zieladressen wird dann eine Entschachte lung der ersten 192 Datensymbole des verschachtelten Datensi gnals durchgeführt. Der Ablauf entspricht der anhand Fig. 3 erläuterten Vorgehensweise.

Nachdem die ersten 192 Datensymbole (bzw. ein anderer frei wählbarer Abschnitt des verschachtelten Datenblocks) ent schachtelt ist, wird der nächste Satz von Entschachtelungs- Zieladressenwerten E-Adr(n) berechnet, und es wird gemäß der berechneten Entschachtelungs-Zieladressenwerte die Umspeiche rung der Datensymbole des zweiten betrachteten Abschnitts des Datenblocks durchgeführt. Sofern eine zeilenweise Entschach telung ausgeführt wird, ist der Datenblock nach R = 5 oder R = 10 oder R = 20 alternierenden Entschachtelungs-Zieladressen- Berechnungsschritten, Entschachtelungs-Zieladressen- Abspeicherungsschritten, wobei die bei der vorhergehenden Prozedur verwendeten Zieladressen überschrieben werden, und Datensymbol-Umspeicherschritten vollständig entschachtelt. Das beschriebene Verfahren der abschnittsweisen oder sequen tiellen Entschachtelung eines blockweise verschachtelten Da tensignals wurde anhand der Turbo-Entschachtelung gemäß dem UMTS Standard erläutert, ist jedoch nicht auf diese Bedingun gen beschränkt, sondern kann allgemein als Entschachtelungs prozedur für blockweise verschachtelte Datensignale einge setzt werden.

Claims

1. Verfahren zur Entschachtelung eines gemäß einer vorgegebe nen Verschachtelungsvorschrift blockweise verschachtelten Da tensignals, wobei ein Datenblock K Datensymbole umfaßt, dadurch gekennzeichnet,
daß Entschachtelungs-Zieladressen (E-Adr(n)) bezüglich ei nes ersten vorgegebenen Abschnitts der K zu entschachteln den Datensymbole eines Datenblocks berechnet und in einem Zieladressenspeicher abgelegt werden;
daß dieser Abschnitt der Datensymbole gemäß den im Ziela dressenspeicher abgelegten Entschachtelungs-Zieladressen entschachtelt wird;
daß in einem nächsten Schritt neue Entschachtelungs-Ziel adressen für einen nächsten vorgegebenen Abschnitt der K zu entschachtelnden Datensymbole dieses Datenblocks berechnet und in dem Zieladressenspeicher abgelegt werden;
daß der nächste Abschnitt der Datensymbole gemäß den im Zieladressenspeicher abgelegten neuen Entschachtelungs- Zieladressen entschachtelt wird; und
daß auf diese Weise der gesamte Datenblock abschnittsweise entschachtelt wird.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß in dem nächsten Schritt berechnete Entschachtelungs- Zieladressen unter Überschreiben der zuvor in dem Ziela dressenspeicher abgelegten Entschachtelungs-Zieladressen abgespeichert werden.

3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet,
daß die Verschachtelung nach mehreren unterschiedlichen Verschachtelungsvorschriften durchführbar ist,
daß eine Erzeugungsregel zur Berechnung der unterschiedli chen Verschachtelungsvorschriften vorgegeben ist, und
daß die Vorausberechnung der Entschachtelungs-Zieladressen bezüglich der Abschnitte von Datensymbolen unmittelbar aus der Erzeugungsregel ohne eine vorherige Berechnung der Zieladressen für die Verschachtelung vorgenommen wird.

4. Verfahren nach Anspruch 3, dadurch gekennzeichnet, daß es sich bei der Entschachtelung um eine Turbo- Entschachtelung, d. h. eine Entschachtelung eines mit einem Turbo-Verschachteler verschachtelten Datensignals, handelt.

5. Verfahren nach Anspruch 3, dadurch gekennzeichnet,
daß es sich bei der vorgegebenen Erzeugungsregel um den UMTS-Standard TS 25.212 handelt, welcher für jede Daten blocklänge K eine Verschachtelungsvorschrift in Form einer Koordinaten-Transformationsmatrix bestehend aus R Zeilen und C Spalten definiert, und
daß jeder der vorgegebenen Abschnitte eine Anzahl von nz.C aufeinanderfolgende Datensymbole des verschachtelten Daten signals aufweist, wobei nz eine ganze Zahl gleich oder grö ßer 1 ist.

6. Verfahren nach Anspruch 5, dadurch gekennzeichnet, daß nz = 1.