DE69425400T2

DE69425400T2 - Verfahren und Vorrichtung zur Verschachtelung einer Folge von Datenelementen

Info

Publication number: DE69425400T2
Application number: DE69425400T
Authority: DE
Inventors: Fabrice De Seze; Frederic Gourgue
Original assignee: Alcatel SA
Current assignee: Alcatel Lucent SAS
Priority date: 1993-06-02
Filing date: 1994-05-31
Publication date: 2001-03-08
Anticipated expiration: 2014-06-01
Also published as: EP0996232A2; PT627821E; ES2148295T3; EP0627821A1; US5742612A; DE69432571T2; FR2706054A1; EP0996232B1; DE69425400D1; FR2706054B1; ES2197570T3; EP0996232A3; DE69432571D1; FI942512A0; EP0627821B1; FI942512A7

Description

Die Erfindung betrifft die Verschachtelung von Datenelementen von digitalen Quellsignalen. Die Verschachtelungstechniken haben zahlreiche Anwendungen auf dem Gebiet der Verarbeitung digitaler Signale, insbesondere bei der Verschlüsselung und/oder Übertragung dieser Signale.
So erlaubt im Fall der digitalen Übertragung (oder Verbreitung) die Verschachtelung, die Probleme aufgrund von diversen Störungen des Übertragungskanals wie insbesondere Erscheinungen der schnellen Dämpfung oder von Störimpulsen zu unterdrücken oder wenigstens zu begrenzen.
Die Datensignale werden nämlich mit Hilfe von Fehlerkorrekturcodes wie etwa Faltungscodes codiert, die es erlauben, am Empfang das Quellsignal wiederherzustellen, selbst wenn bestimmte Datenelemente in falscher Form empfangen werden. Eine solche Korrektur ist jedoch nur möglich, wenn es eine begrenzte Zahl r von falschen Datenelementen unter p aufeinanderfolgenden Datenelementen gibt (wobei p und r abhängig vom verwendeten Code sind). Es ist jedoch nicht selten, daß eine Dämpfung eine Dauer hat, die der Übertragung von mehreren aufeinanderfolgenden Datenelementen entspricht.
Die Verschachtelung erlaubt es, diesen Nachteil zu lindern, indem die Datenelemente in einer solchen Weise umgeordnet werden, daß zwei Datenelemente, die im Quellsignal eine Entfernung von p haben, im übertragenen (verschachtelten) Signal weit genug von einander entfernt sind, daß sie nicht beide von einer gleichen Dämpfung betroffen werden können.
Die Effektivität eines Verschachtelers mißt sich nach seiner · Fähigkeit, einen umfangreichen Block von Fehlern zu spalten. Dies läßt sich in folgender Weise formalisieren, wenn q die Länge des aufzuspaltenden Fehlerblocks in Bits und p die Zahl von aufeinanderfolgenden Bits ist, auf der es wünschenswert ist, keine Anhäufung von Fehlern zu haben; der Verschachteler ist geeignet, wenn zwei Bits, die unter q nach Verschachtelung aufeinanderfolgenden Bits ausgewählt sind, vor der Verschachtelung wenigstens p Bits voneinander entfernt sind. Gegenwärtig sind im wesentlichen zwei Verschachtelungstechniken bekannt, die Matrix-Verschachtelung und die Faltungs- Verschachtelung.
Die Matrix-Verschachtelungstechnik besteht darin, die Datenelemente einer Quellfolge zeilenweise in eine Matrix zu schreiben und diese Datenelemente spaltenweise zu lesen, um eine verschachtelte Folge zu bilden.
Es ist bekannt, daß, um eine problemlose Decodierung zu gewährleisten, die Zeilenzahl der Matrix größer oder gleich der Maximalzahl (q) von Datenelementen sein muß, die in einer Dämpfung enthalten sein können (oder genauer gesagt, die in einer Dämpfung mit der maximalen vom Übertragungssystem tolerierten Dauer enthalten sind) und daß die Zahl der Spalten der Matrix größer oder gleich der Zahl p von aufeinanderfolgenden Datenelementen sein muß, unter denen sich nicht mehr als ein falsches Datenelemente befinden darf.
Dies erfordert also, daß die Länge jeder verschachtelten Folge L = xy aufeinanderfolgende Datenelemente beträgt. Es ist jedoch nicht immer möglich, diese Anforderung einzuhalten, insbesondere wenn die Länge N jeder Folge durch das Übertragungssystem vorgegeben ist. Dies ist insbesondere der Fall, wenn N prim ist, oder allgemeiner, wenn es keine zwei ganzen Zahlen x und y gibt, die die obigen Bedingungen erfüllen und Teiler von N sind. N kann z. B. die Zahl von Datenelementen sein, die in einer von dem System gehandhabten Protokolleinheit (Rahmen, Paket...) enthalten sind.
Ein anderer Nachteil der Matrixtechnik ist, daß das erste und das letzte eingetragene Datenelement nicht verschoben werden. Wenn man also zwei Folgen von L Datenelementen verarbeiten, bleibt das erste Element der zweiten Folge der direkte Nachfolger des letzten Elements der ersten Folge, auch nach Verschachtelung. Wenn eine Dämpfung während der Übertragung dieser Elemente auftritt, kann die Decodierung unmöglich sein.
Die Faltungsverschachtelung ist an die Übertragung von Bits in Serie in dem Rahmen angepaßt, wo der Verschachteler (und der Entschachteler) die Bits einzeln aufnehmen und liefern, im Gegensatz zum vorhergehenden Fall, wo die Bits gesammelt werden, bevor sie ver-(oder ent-) schachtelt werden und dann blockweise geliefert werden. Es wird gezeigt, daß dieser Typ von Verschachteler Stopfbits -erzeugt, was die Kapazität der Systeme reduziert, insbesondere wenn die zu übertragenden Meldungen kurz sind.
Ein erheblicher Nachteil der Faltungs-Verschachtelungstechnik ist, daß sie zur Einfügung von Stopfbits zwischen den Nutzdatenelementen führt. Daraus resultiert also ein Effektivitätsverlust des Übertragungssystems hinsichtlich der Übertragungsrate.
Es ist ferner aus dem Dokument EP-A-0 235 477 ein Verfahren zum Verschachteln einer Folge von B codierten Wörtern zu je n Symbolen bekannt, bei dem diese codierten Wörter in B Zeilen zu je n Symbolen einer Verschachtelungsmatrix geordnet werden, und bei dem die Verschachtelung durch eine besondere Leseabfolge der Matrix realisiert wird, die im folgenden definiert wird:
xk = x&sub0; + k p (modulo Bn), wobei x&sub0; ein Ausgangsrang und p die Schrittweite der Folge ist, wobei p eine mit Bn Teilerfremde ganze Zahl ist und k die Werte 0,1, ... Bn-1 annimmt.
Ziel dieses Dokuments ist, eine Verschachtelung durchzuführen, die es erlaubt, eine Übertragung zu erzielen, die unempfindlich gegen die Störung durch einen periodischen Störer ist, der gleichmäßig in der Zeit beabstandete Störimpulse von B Symbolen aussendet (was mit der herkömmlichen Matrix-Verschachtelung nicht möglich ist), und ohne dabei eine Lesung der Matrix nach einer pseudozufälligen Regel durchzuführen (um einen Mindestwert des Abstands zwischen den Symbolen eines gleichen codierten Worts einzuhalten).
Ziel der Erfindung ist insbesondere, die diversen Nachteile des Standes der Technik zu lindern.
Genauer gesagt ist ein wesentliches Ziel der Erfindung, ein Verfahren zum Verschachteln der Datenelemente einer Folge mit N Datenelementen für einen beliebigen Wert von N anzugeben. Mit anderen Worten ist Ziel der Erfindung, ein solches Verfahren anzugeben, das die blockweise Verschachtelung von Elementblöcken (Pakete, Rahmen...) beliebiger Größe ermöglicht.
Ein anderes Ziel der Erfindung ist, ein solches Verfahren anzugeben, das die Verschachtelung der Datenelemente in Abhängigkeit von der Struktur des zu übertragenden Signals (z. B. Architektur der Protokolleinheiten, Übertragungstechniken) erlaubt.
Ziel der Erfindung ist auch; ein solches Verschachtelungsverfahren anzugeben, das einen ausreichenden Abstand zwischen aufeinanderfolgenden Datenelementen einer Folge von N Datenelementen, aber auch zwischen den Datenelementen von zwei aufeinanderfolgenden Folgen herstellt.
Ein anderes Ziel der Erfindung ist, ein solches Verfahren anzugeben, das zu keiner Veränderung, das heißt Verringerung, der Rate des verarbeiteten Signals führt.
Ein besonderes Ziel der Erfindung ist, ein solches Verfahren anzugeben, das einfach anzuwenden ist und wenig Verarbeitungszeit, eine geringe Zahl durchzuführende Operationen und wenig Speicherkapazität erfordert.
Diese Ziele sowie andere, die nachfolgend deutlich werden, werden erfindungsgemäß erreicht durch ein Verfahren zum Verschachteln einer Quellfolge, die N Datenelemente umfaßt, wobei der Wert von N beliebig ist, und das eine der Quellfolge entsprechende verschachtelte Folge ergibt, wobei das Verfahren wenigstens einen Verschachtelungsschritt umfaßt, der das Datenelement mit Index j der verschachtelten Folge dem Datenelement mit Index i der Quellfolge zuordnet, wobei der Wert j anhand des Werts i auf folgende Weise bestimmt wird:
j = (a.i + b) [modulo N] + 1,
wobei
1 ≤ i ≤ N und 1 ≤ j ≤ N,
a eine mit N vorgegebene ganze Zahl ist, derart, daß
2 ≤ a ≤ N-1 ist;
und b eine vorgegebene ganze Zahl ist, derart, daß
0 ≤ b ≤ N-1 ist.
So kann die Länge N der Quellfolge einen beliebigen Wert annehmen, und das erfindungsgemäße Verfahren erlaubt es, die Beschränkungen zu überwinden, die mit der Matrix-Verschachtelung verknüpft sind, insbesondere die, nach der die Länge der Verschachtelungsfolge gleich L = xy Datenelemente sein muß.
Außerdem werden die ersten und letzten Datenelemente jeder Quellfolge verschoben. So erzeugt das erfindungsgemäße Verfahren einen ausreichenden Abstand nicht nur zwischen den aufeinanderfolgenden Datenelementen einer gleichen Folge, sondern auch zwischen den aufeinanderfolgenden Datenelementen zweier aufeinanderfolgender Folgen (nämlich dem letzten Element der einen und dem ersten Element der anderen).
Schließlich führt das erfindungsgemäße Verfahren kein Stopfbit ein. Dadurch kann eine Verringerung der Rate des verarbeiteten Signals vermieden werden.
Vorteilhafterweise werden die Datenelemente vorher mit Hilfe eines Fehlerkorrekturcodes codiert, der höchstens r Fehler unter p aufeinanderfolgenden Datenelementen in der Quellfolge toleriert, wobei die Zahl a größer oder gleich der Zahl p ist.
Die Zahl a entspricht dem minimalen Abstand in Datenelementen zwischen zwei Elementen der Quellfolge (sowie in theoretisch auch der entschachtelten Folge), die zwei aufeinanderfolgenden Datenelementen der verschachtelten Folge entsprechen.
Infolgedessen wird dadurch, daß a ≥ p gewählt wird, sichergestellt, daß am Empfang eine angemessene Decodierung es erlaubt, die fehlerhaften Elemente zu korrigieren, wenn zwei aufeinanderfolgende Fehler (das heißt zwei aufeinanderfolgende fehlerhafte Elemente) durch wenigstens p fehlerfreie Datenelemente getrennt sind.
Vorteilhafterweise ist die verschachtelte Folge zur Übertragung auf einem Übertragungskanal zu einem Empfänger bestimmt, wobei der Kanal Dämpfungen mit einer maximalen Dauer von q.T aufweisen kann, ohne den Empfang im Empfänger zu beeinträchtigen, wobei T die Übertragungsdauer eines Datenelements und q eine ganze Zahl ist und die Zahl a so gewählt ist, daß E (N/a ≥ q ist, wobei die Funktion E() diejenige Funktion ist, die einer reellen Zahl ihren ganzzahligen Teil zuordnet.
Auf diese Weise ist sichergestellt, daß in der verschachtelten Folge die aufgrund ein und derselben Dämpfung fehlerhaften Datenelemente (Elemente, die deshalb aufeinanderfolgen und maximal q Elemente umfassen), in der Quellfolge nicht benachbart sind. Vorzugsweise ist die Zahl a so gewählt, daß der kleinere der zwei Werte a und E(N/a) maximiert wird, wobei E() die Funktion ist, die einer reellen Zahl ihren ganzzeiligen Teil zuordnet.
Auf diese Weise wird ein Kompromiss zwischen den zwei vorhergehenden Anforderungen, nämlich a ≥ p und E(N/a) ≥ q, erreicht.
Vorzugsweise wird das Verfahren angewendet auf die Verschachtelung von digitalen Signalen, die in Blöcken von Datenelementen mit je N Datenelementen organisiert sind.
Bei einer bevorzugten Ausgestaltung der Erfindung wird das Verfahren in einem System zur Übertragung von Datenelementen durch Rahmen eingesetzt, wobei jeder der Rahmen wenigstens ein Paket umfaßt und jedes der Pakete wenigstens zwei Zonen von Nutzdatenelementen, getrennt durch wenigstens eine Zone von Strukturdatenelementen umfaßt, wobei der Verschachtelungsschritt ausschließlich auf den Nutzdatenelementen durchgeführt wird.
Auf diese Weise wird die Effektivität der Verschachtelung weiter verbessert, weil die Zonen von Strukturelementen, nämlich die Rahmenheader, die zu Beginn, in der Mitte und am Ende des Pakets befindlichen Zonen (im folgenden als "Präambel", "Mittambel" und "Postambel" bezeichnet) es erlauben, den Abstand zwischen den Datenelementen nach Verschachtelung zu vergrößern.
Die N zu verschachtelnden Datenelemente eines Blocks kommen entweder aus einem gleichen Paket oder aus mehreren aufeinanderfolgenden Paketen (die z. B. einen Rahmen bilden). Vorteilhafterweise umfaßt das Verfahren einen Schritt der Bestimmung der Zahlen a und b unter Berücksichtigung wenigstens eines Parameters, der zu der Gruppe gehört, welche umfaßt:
- die Struktur der Rahmen;
- die Struktur der Pakete.
Im Fall einer Anwendung des erfindungsgemäßen Verfahrens in einem Übertragungssystem mit Frequenzsprung, das wenigstens zwei Übertragungsfrequenzen verwendet, umfaßt die Gruppe von Parametern auch:
- die zu einem gegebenen Zeitpunkt verwendete Frequenz;
- die Frequenzsprung-Zeitpunkte.
Bei einer bevorzugten Ausgestaltung der Erfindung umfaßt das Verfahren die folgenden Schritte:
- Bestimmung einer Funktion fN,a,b, parametrisiert durch das Tripel (N, a, b), derart, daß q = fN,a,b(p) ist, wobei * p die Zahl von aufeinanderfolgenden Datenelementen der Quellfolge ist, auf der keine Akkumulation von Fehlern erwünscht ist, so daß ein Fehlerkorrekturcode es erlaubt, die fehlerhaften Datenelemente zu korrigieren;
* q die maximale Zahl von aufeinanderfolgenden fehlerhaften Datenelementen der verschachtelten Folge ist, die einer Dämpfung entspricht, die ein Übertragungskanal, auf der die verschachtelte Folge übertragen wird, induzieren darf, ohne den Empfang an einem am Ausgang des Übertragungskanals angeordneten Empfänger zu beeinträchtigen,
- Berechnen, für jeden einzelnen Wert des Tripels (N, a, b), eines Werts Pmin der Zahl p, so daß pmin der maximale Wert von p ist, für den fN,a,b (p) kleiner oder gleich p ist;
- Wahl der Zahlen a und b, die dem maximalen Wert pmin entsprechen.
Es läßt sich zeigen, daß unabhängig vom Wert des Tripels (N, a,b) die Funktion fN,a,b abnimmt und wenigstens einen Schnittpunkt mit der ersten Bisektrix aufweist.
Zu beachten ist, daß N im allgemeinen durch das Übertragungssystem, z. B. aufgrund der Struktur der Rahmen oder Pakete vorgegeben ist.
Bei einer vorteilhaften Ausgestaltung der Erfindung sind die Datenelemente binäre Elemente und das Verfahren wird in einem System zur digitalen Funkkommunikation eingesetzt.
Vorteilhafterweise umfaßt das Verfahren wenigstens zwei aufeinanderfolgende Verschachtelungsschritte, einen ersten Verschachtelungsschritt, der das Datenelement mit Index j einer Zwischenfolge dem Datenelement mit Index i der Quellfolge zuordnet, wobei der Wert j anhand des Werts i auf folgende Weise bestimmt wird:
j = (a&sub1;.i + b&sub1;) [modulo N] + 1,
und einen zweiten Verschachtelungsschritt, der das Datenelement mit Index j der verschachtelten Folge dem Datenelement mit Index i der Zwischenfolge zuordnet, wobei der Wert j anhand des Werts i in folgender Weise bestimmt wird:
j - (a&sub2;.i + b&sub2;) [modulo N] +1,
wobei
a&sub1; und a&sub2; mit N vorgegebene ganze Zahlen sind und
b&sub1; und b&sub2; vorgegebene ganze Zahlen sind, derart, daß:
0 ≤ b&sub1; ≤ N-1 und 0 ≤ b&sub2; ≤ N-1.
Dies entspricht einer Mehrfachverschachtelung. Das Prinzip eines jeden der aufeinanderfolgenden Verschachtelungsschritte entspricht dem zuvor im Fall eines einzigen Verschachtelungsschritts erläuterten Prinzip.
Die Erfindung betrifft auch eine Verschachtelungsvorrichtung, die Mittel zur Ausführung eines erfindungsgemäßen Verschachtelungsverfahrens aufweist.
Andere Merkmale und Vorteile der Erfindung ergeben sich anhand der Lektüre der nachfolgenden Beschreibung eines bevorzugten Ausführungsbeispiels der Erfindung, das als erläuterndes und nicht beschränkendes Beispiel angegeben wird, und der beigefügten Zeichnungen, in denen:
die Fig. 1 ein Blockschema eines Übertragungssystems darstellt, das es erlaubt, das allgemeine Prinzip der Verschachtelung zu erläutern;
Fig. 2 ein Beispiel einer Korrespondenztabelle zwischen den Indices der Elemente einer Quellfolge und den Indices der Elemente einer Verschachtelungsfolge darstellt, die mit einer besonderen Ausgestaltung des erfindungsgemäßen Verfahrens erhalten sind;
Fig. 3 ein Beispiel der Strukturierung eines Zuges von Datenelementen darstellt, die in einem System wie in Fig. 1 dargestellt übertragen werden, wobei diese Strukturierung besonders an eine vorteilhafte Anwendung des erfindungsgemäßen Verfahrens angepaßt ist;
Fig. 4 drei Beispiele der Veränderung der Zahl q = fN,a,b (p) in Abhängigkeit von der Zahl p darstellt, wobei jedes Beispiel einem unterschiedlichen Wert des Tripels (N, a, b) entspricht.
Die Erfindung betrifft also ein Verschachtelungsverfahren sowie eine Verschachtelungsvorrichtung (oder einen Verschachteler), der ein solches Verfahren anwendet.
Das zu übertragende Signal wird von einem Modulator 1 geformt, bevor es auf dem Übertragungskanal 2 gesendet wird. Dieser Übertragungskanal 2 verschlechtert jedoch das Signal, was zu Fehlern am Ausgang des Demodulators 3 führt. Diese Verschlechterung des Signals wird teilweise kompensiert durch die Verwendung eines Fehlerkorrekturcodes, der einerseits in einem Codierer 4, der vor dem Modulator 1 angeordnet ist (Kanalcodierung), und andererseits in einem Decodierer 5 ausgeführt wird, der hinter dem Demodulator 3 angeordnet ist (Decodierung)
Die Erfahrung zeigt, daß die durch den Übertragungskanal 2 hervorgerufenen Fehler paketweise auftreten können. Man spricht dann von Signalschwund, dessen Länge als Zahl von der aufeinanderfolgenden fehlerhaften Datenelementen gemessen werden kann. Solche Signalschwunde treten insbesondere bei Mobilfunkkanälen auf.
Die Fehlerkorrekturcodes sind jedoch effektiver, wenn die Fehler isoliert sind. Aus diesem Grund wird ein Verschachteler 6 zwischen dem Codierer 4 und dem Modulator 1 sowie ein Entschachteler zwischen dem Demodulator 3 und dem Decodierer angeordnet. So wird der binäre Strom vor dem Senden verschachtelt und dann beim Empfang entschachtelt, um so die Fehlerpakete aufzuspalten und die Effizienz des Fehlerkorrekturcodes zu verbessern.
Die erfindungsgemäße Verschachtelungsprozedur ist von dem Typ, die eine verschachtelte Folge liefert, die einer Quellfolge mit N Datenelementen entspricht.
Dieses Verfahren umfaßt wenigstens einen Verschachtelungssschritt, derart, daß das Datenelement mit Index i der Quellfolge verschoben wird und einem Datenelement mit Index j der verschachtelten Folge entspricht, wobei der Wert j anhand des Werts i auf folgende Weise bestimmt wird:
j = (a.i + b [modulo N] +1,
wobei a eine mit N vorgegebene erste ganze Zahl ist, derart, daß
2 ≤ a ≤ N-1 und
b eine vorgegebene ganze Zahl ist, derart, daß
0 ≤ b ≤ N-1.
Fig. 2 zeigt ein Beispiel einer Korrespondenztabelle zwischen den Indices der Elemente einer Quellfolge und den Indices der Elemente einer verschachtelten Folge von Datenelementen. Bei dieser speziellen Ausgestaltung ist N = 17, a = 4 und b = 0. So nimmt z. B. das Datenelement, das in der Quellfolge den 14. Platz (Index 14) einnimmt, den 6. Platz in der verschachtelten Folge (Index 6) ein. Es gilt nämlich: (4 · 14 + 0) [modulo 17] +1 = 5+1 = 6.
Im folgenden wird angenommen, daß der verwendete Fehlerkorrekturcode von dem Typ ist, der maximal einen Fehler unter p aufeinanderfolgenden Datenelementen in der Quellfolge toleriert. Mit anderen Worten ist p die Zahl von aufeinanderfolgenden Datenelementen, auf der es wünschenswert ist, keine Anhäufung von Fehlern zu haben. In diesem Fall ist das erfindungsgemäße Verfahren derart, daß Zahl a so gewählt wird, daß a ≥ p.
In der nachfolgenden Beschreibung wird ferner angenommen, daß der Übertragungskanal Signalschwund mit einer maximalen Dauer q.T aufweisen kann, wobei T die Dauer der Übertragung eines Datenelements und q eine ganze Zahl ist. Mit anderen Worten ist q die Länge (als Zahl von Datenelementen angegeben) des zu zerlegenden Fehlerpakets.
In diesem Fall ist das erfindungsgemäße Verfahren derart, daß die Zahl a so gewählt wird, daß E (N/a) ≥ q, wobei E die Funktion ist, die einer reellen Zahl ihren ganzzahligen Teil zuordnet.
Ein Beispiel für einen Kompromiss zwischen den zwei Anforderungen an a, nämlich a ≥ p und E (n/a) ≥ q, besteht z. B. darin, die Zahl a so zu wählen, daß der kleinere der zwei Werte a und E (N/a) maximiert wird. Mit anderen Worten geht es darum, diejenige Zahl a zu bestimmen, die die Funktion Maxa [Min a,E (N/a)] maximiert.
Wenn diese zwei Anforderungen erfüllt sind, ist die Verschachtelung an den Fehlerkorrekturcode einerseits und den Übertragungskanal andererseits angepaßt. Mit anderen Worten sind zwei unter q nach Verschachtelung aufeinanderfolgenden Datenelementen ausgewählte Datenelemente vor der Verschachtelung um wenigstens p Datenelemente von einander entfernt.
b kann einer Phase gleichgesetzt werden. Der Wert von b wird so gewählt, daß die effizienteste Verschachtelung erhalten wird. Diese Auswahl kann zahlreiche Parameter berücksichtigen, insbesondere die Struktur des zu verschachtelnden Blocks.
Es ist zu beachten, daß, um die Verschachtelung weiter zu verbessern, das erfindungsgemäße Verfahren wenigstens zwei aufeinanderfolgende Verschachtelungsschritte vom oben beschriebenen Typ umfassen kann. So werden in dem Fall, wo es zwei aufeinanderfolgende Schritte gibt, die Elemente der Quellfolge zunächst verschachtelt, um eine Zwischenfolge zu bilden, dann werden die Elemente der Zwischenfolge verschachtelt, um die auf dem Übertragungskanal gesendete Folge zu bilden.
Wenn mit i, j und k der Index eines gleichen Datenelements in der Quellfolge, der Zwischenfolge bzw. der verschachtelten Folge bezeichnet wird, gilt:
j = (a&sub1;.i + b&sub1;> [modulo N] + 1
k = (a&sub2;.i + b&sub2;) [modulo n] + 1,
wobei n&sub1; und n&sub2; mit N vorgegebene erste ganze Zahlen sind und b&sub1; und b&sub2; vorgegebene ganze Zahlen sind, derart, daß:
0 ≤ b&sub1; ≤ N-1 und 0 ≤ b&sub2; ≤ N-1.
Die verschiedenen Koeffizienten (a&sub1;, a&sub2;, b&sub1;, b&sub2;) werden so gewählt, daß die durch die Aufeinanderfolge der zwei Verschachtelungsschritte erhaltene Gesamtverschachtelung derart ist, daß zwei unter q nach Verschachtelung aufeinanderfolgenden Datenelementen vor Verschachtelung um wenigsten p Datenelemente voneinander entfernt sind.
Die Zahl N von Datenelementen der zu verschachtelnden Quellfolge kann einen beliebigen vorgegebenen Wert annehmen, das erfindungsgemäße Verfahren ist perfekt angepaßt an die Verschachtelung von digitalen Signalen, die in Form von Blöcken von Datenelementen organisiert sind, die jeweils N Datenelemente umfassen.
Eine spezielle Ausgestaltung des erfindungsgemäßen Verfahrens wird nachfolgend für den Fall eines digitalen Funk- Kommunikationssystems beschrieben, wobei die Datenelemente in diesem Fall binäre Elemente sind. Es ist jedoch offensichtlich, daß das erfindungsgemäße Verfahren nicht auf eine solche Anwendung beschränkt ist und bequem an zahlreiche andere Fälle angepaßt werden kann, ohne den Rahmen der Erfindung zu verlassen.
Bei einem digitalen Funk-Kommunikationssystem werden die Datenelemente (genauer gesagt Bits) in Rahmen übertragen.
Fig. 3 zeigt ein Beispiel der Struktur eines Zugs von zu übertragenden Bits. Der Zug besteht aus einer Folge von Rahmen (..., RAHMEN X, RAHMEN (X+1), ...). Jeder Rahmen besteht seinerseits aus einer Folge von Paketen, vier Paketen bei diesem Beispiel, (PAKET 1 bis PAKET 4). Im Fall eines TDMA-Systems (Englisch Time Division Multiple Access) kehren zu einer gegebenen Kommunikation gehörende Pakete nur mit einer bestimmten Rate wieder. So werden bei dem dargestellten Beispiel, nämlich dem TDMA-4-System, vier Kommunikationen zeitlich gemultiplext, und die Pakete einer gleichen Kommunikation kehren alle vier Pakete wieder.
Jedes Paket enthält fünf Zonen:
- einerseits drei Zonen von Strukturdatenelementen, die am Beginn, in der Mitte und am Ende des Pakets angeordnet sind und im folgenden als "Präambel" "Mittambel" bzw. "Postambel" bezeichnet werden, und
- andererseits zwei Zonen von Nutzdatenelementen.
Die Zonen 31, 32 von Nutzdatenelementen transportieren die Information als solche, wohingegen die Zonen 33 bis 35 mit Strukturdatenelementen für die Funktion des Systems erforderlich sind, aber den von dem System übertragenen Durchsatz an Nutzdaten begrenzen.
Die Verschachtelung betrifft nur die Informationsbits (d. h. die Nutzdatenelemente der mit 31, 32 bezeichneten Zonen).
Ein Block von N Datenelementen, der eine Quellfolge bildet, kann somit den Bits eines gleichen Pakets oder mehrerer Pakete entsprechen. Eine solche Nutzung der Rahmen- und Paketstruktur erlaubt es, die Effektivität der Verschachtelung zu erhöhen. Die Strukturdatenelementzonen erhöhen nämlich den Abstand zwischen den Informationsbits nach der Verschachtelung. Dies läuft auf eine Vergrößerung des möglichen Werts von q für einen gegebenen Wert von p hinaus.
Ein Schritt der Bestimmung der Zahlen a und b geht im allgemeinen dem Verschachtelungsschritt voraus. Im Fall eines Paketübertragungssystems besteht der Bestimmungsschritt darin, die Zahlen a und b unter Berücksichtigung der Struktur der Rahmen und/oder der Struktur der Pakete zu wählen.
Wenn das Verfahren in einem Übertragungssystem mit Frequenzsprung verwendet wird, das wenigstens zwei Übertragungsfrequenzen verwendet, können die zu einem gegebenen Zeitpunkt benutzte Frequenz und/oder die Zeitpunkte der Frequenzsprünge ebenfalls in dem Schritt der Bestimmung der Zahlen a und b berücksichtigt werden.
Bei dem nachfolgenden Beispiel, das lediglich zur Verdeutlichung angegeben ist, ist die Verschachtelung auf das Innere eines einzigen Pakets beschränkt. In diesem Fall wird die Mittambel genutzt, um die Verschachtelung der Nutzdatenelemente der zwei entsprechenden in dem Paket enthaltenen Zonen zu verbessern.
In diesem Beispiel enthalten die erste und die zweite Zone 31 und 32 von Nutzdatenelementen n&sub1; bzw. n&sub2; Elemente, wobei n&sub1; + n&sub2; = N.
Die Quellfolge besteht somit aus der Verkettung:
von n&sub1; Elementen mit Index i zwischen 1 und n&sub1; und
von n&sub2; Elementen mit Index i zwischen (n&sub1;+1) und N.
Der Verschachtelungsschritt besteht, wie bereits oben beschrieben, darin, das 1-te Nutzdatenelement der Quellfolge so zu verschieben, daß es den j-ten Platz der verschachtelten Folge einnimmt, wobei j wie folgt definiert ist:
j = (a.i + b) [modulo N] +1,
wobei a eine mit N vorgegebene erste ganze Zahl ist, derart, daß
2 < n ≤ N-1 und
b eine vorgegebene ganze Zahl ist, derart, daß
0 ≤ b ≤ N-1.
Die Zahlen a und b sind z. B. in folgender Weise festgelegt:
- Es wird eine Funktion fN,a,b festgelegt, die durch das Tripel (N, a, b) parametrisiert ist, derart, daß q = fN,a,b (p)
- für jeden unterschiedlichen Wert des Tripels (N,a,b) wird ein Wert pmin der Zahl p bestimmt, wobei pmin der größte Wert von p ist, für den fN,a,b (p) kleiner oder gleich p wird;
- die Zahlen a und b werden entsprechend dem größten Wert pmin gewählt.
Es läßt sich zeigen, daß diese Funktion fN,a,b abnehmend ist, und daß
* für jedes Tripel (N, a,b) gilt: fN,a,b (N) = 1;
* fN,a,b (1) ≥ 1.
Folglich existiert immer ein Wert Pmin, unabhängig davon, was der Wert des Tripels (N,a,b) ist.
Ein Beispiel der Anwendung eines solchen Verfahrens zur Optimierung der Auswahl der Zahlen a und b ist in Beziehung zu Fig. 4 dargestellt. Bei diesem Beispiel ist N = 432 und b = 0 vorgegeben, und es geht darum, die Zahl a zu bestimmen.
Zur Vereinfachung zeigt Fig. 4 lediglich drei Beispiele der Veränderung der Zahl q = fw,a,b (p) in Abhängigkeit von der Zahl p, wobei jedes Beispiel einem anderen Wert des Tripels (N,a,b) entspricht. Da in diesem Fall N und b festgelegt sind, entspricht jedes Beispiel einem anderen Wert von a.
Es gilt:
- für a = 199: Pmin,1 = 13;
- für a = 151: pmin,2 = 20;
- für a = 103: pmin,3 = 21;
Folglich wählt man a = 103, was dem größten Wert von Amin entspricht, nämlich pmin,3 = 21.
Es liegt auf der Hand, daß zahlreiche andere Ausgestaltungen des Schritts der Bestimmung der Zahlen a und b denkbar sind.
Allgemein können Simulationen und Versuche für einen Satz von verschiedenen Werten von Zahlen a und b vorgesehen werden, z. B. mit Hilfe einer digitalen Recheneinrichtung, wobei die beibehaltenen Werte diejenigen sind, die sich für die Decodierung als am effektivsten erweisen.
Es ist auf jeden Fall zweckmäßig, zu überprüfen, daß die ausgewählten Zahlen eine auch an den Übertragungskanal angepaßte Verschachtelung erlauben.

Claims

1. Verfahren zum Verschachteln einer Quellfolge, die N Datenelemente umfaßt, das eine der Quellfolge entsprechende verschachtelte Folge ergibt,

mit wenigstens einem Verschachtelungsschritt, der das Datenelement mit Index j der verschachtelten Folge dem Datenelement mit Index i der Quellfolge zuordnet, wobei der Wert j anhand des Werts i auf folgende Weise bestimmt wird:

j = (a.i + b)[modulo N]+1,

wobei 1 ≤ i ≤ N und 1≤ j ≤ N ist;

a eine mit N vorgegebene ganze Zahl ist, derart,

daß 2 ≤ a ≤ N-1 ist; und

b eine vorgegebene ganze Zahl ist, derart, daß

0 ≤ b ≤ N-1 ist,

dadurch gekennzeichnet, daß die Zahl a so gewählt wird, daß der kleinere der zwei Werte a und E(N/a) maximiert wird, wobei die Funktion E() die Funktion ist, die einer reellen Zahl ihren ganzzahligen Teil zuordnet.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß es für die Verschachtelung von digitalen Signalen eingesetzt wird, die in Form von Blöcken von Datenelementen mit je N Datenelementen organisiert sind.

3. Verfahren nach einem beliebigen der Ansprüche 1 oder 2, dadurch gekennzeichnet, daß die Datenelemente binäre Elemente sind.

4. Verfahren nach einem beliebigen der Ansprüche 1 oder 3, dadurch gekennzeichnet, daß es in einem digitalen Funkkommunikationssystem eingesetzt wird.

5. Vorrichtung (6) zum Verschachteln einer Quellfolge, die N Datenelemente umfaßt, wobei die Vorrichtung eine der Quellfolge entsprechende verschachtelte Folge liefert, mit Mitteln zum Durchführen von wenigstens einem Verschachtelungsschritt, der das Datenelement mit Index j der verschachtelten Folge dem Datenelement mit Index i der Quellfolge zuordnet, wobei der Wert j anhand des Werts i auf folgende Weise bestimmt wird:

j = (a.i + b) [modulo N] + 1,

wobei 1 ≤ i ≤ N und 1 ≤ j , N ist;

a eine mit N vorgegebene ganze Zahl ist, derart,

daß 2 ≤ a ≤ N-1 ist; und

b eine vorgegebene ganze Zahl ist, derart, daß

0 ≤ b ≤ N-1 ist,

dadurch gekennzeichnet, daß die Zahl a so gewählt ist, daß der kleinere der zwei Werte a und E(N/a) maximiert wird, wobei die Funktion E() die Funktion ist, die einer reellen Zahl ihren ganzzahligen Teil zuordnet.