Run Length Limited

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Run Length Limited (RLL) ist eine Gruppe von Leitungscodes, welche im Bereich der Telekommunikation und bei Speichermedien wie magnetischen Plattenspeichern als Schreibverfahren verwendet werden. Die Leitungscodes dieser Gruppe sind dadurch gekennzeichnet, dass einheitliche Datenfolgen aus den Zuständen von Logisch-0 oder von Logisch-1 garantiert in der Länge limitiert sind. Von dieser Eigenschaft leitet sich die Bezeichnung jener Leitungscodes ab.

Erste RLL-Codes wurden von IBM 1972 patentiert und ab 1979 kommerziell in dem Direct Access Storage Device IBM 3370 für die Großrechnerserie 4300 eingesetzt.[1][2] Einfache RLL-Codes wurden in den 1980er und 1990er-Jahren im Bereich der Datenaufzeichnung von Festplatten verwendet. Sie finden mit Adaptierungen auch heute noch in dem Bereich der magnetischen Datenaufzeichnung und bei optischen Speichermedien wie Compact Disc (CD) Anwendung.

Einteilung[Bearbeiten]

RLL-Codes werden in der Literatur durch zwei Parametern d und κ klassifiziert und in der Form (d,κ)-RLL geschrieben. Der Parameter d spezifiziert die minimale und κ die maximale Anzahl von logisch-0, welche zwischen zwei logisch-1 in der Datenfolge auftreten können. κ kann als Grenzfall eines entarteten RLL-Code auch unendlich sein.

Wird der RLL-Code in Verbindung mit dem differentiellen NRZI-Leitungscode verwendet, wie es bei Anwendung der RLL-Codes bei magnetischen Speichermedien üblich ist, können damit bei dem Lesevorgang der Datenfolge genügend viele Signalflanken für die Taktrückgewinnung gewährleistet werden. Diese dynamische Taktrückgewinnung aus den Datensignal ist bei mechanischen Laufwerken und deren Gleichlaufschwankungen bei nur ungefährer Vorgabe der Umdrehungsgeschwindigkeit für die Synchronisation wesentlich.

Alle RLL-Codes lassen sich mittels eines endlichen Automaten beschreiben, welcher über κ+1 Zustände verfügen muss. Ein bestimmter RLL-Code kann dann als eine Zustandsdiagrammmatrix eindeutig angegeben werden, nur die Angabe (d,κ)-RLL klassifiziert nicht einen bestimmten RLL-Code.

Ein weiterer wesentlicher Parameter ist die minimale Länge n der benötigten Codewörter, welche eine gegebene (d,κ) Bedingung erfüllen. Die Längen der konkret gewählten Codewörter können einheitlich sein, müssen dies aber nicht sein. Bei einheitlicher Codewortlänge wird jedes Nutzdatenbit bzw. fixer Block von Nutzdatenbits der Länge k eindeutig einen Codewort der Länge n zugeordnet, wobei die Bedingung gilt: n > k. Ein Beispiel ist der 4B5B-Code welcher 4 Nutzdatenbits eindeutig einem 5 Bit langen Codewort zuordnet. Das Verhältnis k/n ist die Coderate R. Die Anzahl k an Informationsbits welche einer Codewortsequenz der Länge N(n) trägt ist allgemein gegeben als:

 k = \lfloor \mathrm{log}_2 N(n) \rfloor

Die Kapazität C(d,κ) eines RLL-Codes ist

C(d,\kappa) = \lim_{n\to\infty} \frac{1}{n} \mathrm{log}_2 N(n) = \mathrm{log}_2 \lambda_{max}

und kann über das Shannon-Hartley-Gesetz mittels der größten Eigenwerte λ der Zustandsübergangsmatrix bestimmt werden. Tabellen der Kapazität als Funktion von (d,κ) finden sich in einschlägiger Literatur.[3]

Die Effizienz eines bestimmten RLL-Codes ist das Verhältnis aus seiner Coderate R und seiner Kapazität C(d,κ). Bei praktischen Anwendungen wird üblicherweise versucht, RLL-Codes mit möglichst großer Effizienz einzusetzen.

Varianten[Bearbeiten]

(0,1)-RLL - FM[Bearbeiten]

Der einfachste (0,1)-RLL-Code mit fixer Codewortlänge und einer Rate von ½ wird in Kombination mit der differentiellen Leitungscodierung NRZI auch als Frequency Modulation (FM) bezeichnet und durch folgende Codierungstabelle beschrieben:

Eingangsdaten Codewort
0 10
1 11

(1,3)-RLL - MFM[Bearbeiten]

Bei magnetischen Speichermedien wie Disketten findet der (1,3)-RLL Code Anwendung, auch unter der Bezeichnung Modified Frequency Modulation (MFM) bekannt. Auch dieser Code weist eine Rate von ½ auf:

Eingangsdaten Codewort
0 x0
1 01

Das Zustand von x hängt von dem vorherigen Datenbit ab: x ist 1 wenn das vorherige Datenbit 0 war, und 0 wenn das vorherige Datenbit 1 war.

(0,2)-RLL[Bearbeiten]

Ein (0,2)-RLL Code mit fixer Blocklänge ist unter anderem der ursprünglich von IBM für magnetische Speicher entwickelte (0,2)-RLL-Code, welcher zu der Gruppe der Group-Coded Recording (GCR) -Codes zählt. Er ist eine Variante eines 4B5B-Code, aber nicht mit diesem identisch. Außerdem existieren von verschiedenen anderen Firmen weitere GCR-Codes, welche keine (0,2)-RLL Code sind, d.h. nicht alle GCR-Codes sind automatisch (0,2)-RLL.

Eingangsdaten Codewort
0000 11001
0001 11011
0010 10010
0011 10011
0100 11101
0101 10101
0110 10110
0111 10111
Eingangsdaten Codewort
1000 11010
1001 01001
1010 01010
1011 01011
1100 11110
1101 01101
1110 01110
1111 01111

Ein weiterer sehr einfacher (0,2)-RLL Code, allerdings mit variabler Datenlänge und fixer Codewortlänge, ist folgender:

Eingangsdaten Codewort
0 01
10 10
11 11

(2,7)-RLL[Bearbeiten]

Nachfolgender nicht trivial zu konstruierender (2,7)-RLL-Code mit sowohl variabler Datenlänge als auch variabler Codewortlänge wurde in den 1980er und 1990er Jahren von Herstellern von Festplatten mit „RLL-Aufzeichnung“ verwendet (er stammt von Peter Franaszek). Er erfüllt sowohl die Präfixbedingung und weist eine fixe Coderate von ½ auf. Es existieren davon einige Varianten, in folgender Tabelle ist eine mögliche Variante angegeben:

Eingangsdaten Codewort
10 0100
11 1000
011 001000
010 100100
000 000100
0010 00100100
0011 00001000

(1,7) RLL[Bearbeiten]

Ein (1,7)-RLL Code mit einer fixen Rate von 2/3, welcher durch eine boolesche Bildungsvorschrift gekennzeichnet ist und sich dadurch leicht in der Digitaltechnik ohne Tabelle realisieren lässt, ist folgender Code:

Eingangsdaten Codewort
00 00 101 000
00 01 100 000
10 00 001 000
10 01 010 000
00 101
01 100
10 001
11 010

Die Bildungsvorschrift lautet: Genügt die Eingangsdatenfolge der Form (x, 0, 0, y) wird daraus das Codewort (NOT x, x AND y, NOT y, 0, 0, 0) gebildet. Genügen die Eingangsdaten nicht dieser Form, wird aus den Eingangsdaten (x, y) das Codewort (NOT x, x AND y, NOT y) gebildet. Da dieser Code nicht die Präfixbedingung erfüllt, ist die Reihenfolge der Zeilen bei der Codewortbildung wesentlich.[4]

Erwähnenswert sind auch gleichanteilsfreie RLL-Codes. Die Gleichanteilsfreiheit ist dann erfüllt, wenn jede Datenwortfolge durchschnittlich die gleiche Anzahl von Einsen und Nullen aufweist. Anders ausgedrückt, ergibt jede Datenwortfolge eine Folge von Codewörtern, welche bei antipodaler Repräsentation, d.h. logisch-0 erhält den Wert -1, logisch-1 den Wert +1, einen Gleichwert von 0 aufweist. Diese Eigenschaft ist dann wichtig, wenn die Codefolge über Kanäle übertragen werden soll, die keine Gleichsignale übertragen können, beispielsweise Funkkanäle oder Impulstransformatoren zur galvanischen Trennung in elektrischen Schaltungen.

Nachfolgend ein gleichanteilsfreier (1,7)-RLL Code:

Eingangsdaten Codewort
00 x01
01 010
10 x00
11 00 010 001
11 01 x00 000
11 10 x00 001
11 11 010 000

Das Zustand von x hängt von dem letzten unmittelbar davor aufgetreten Bit des Codewortes ab: x ist 1 wenn das letzte Codebit 0 war, und 0 wenn das letzte Codebit 1 war.

Einzelnachweise[Bearbeiten]

  1.  J. M. Harker, D. W. Brede, R. E. Pattison, G. R. Santana, L. G. Taft: A Quarter Century of Disk File Innovation. In: IBM Journal of Research and Development. Band 25, Ausgabe 5, 1981, S. 677–690, doi:10.1147/rd.255.0677.
  2. P. A. Franaszek: Run-Length-Limited Variable Length Coding with Error Propagation Limitation. 1972, US-Patent Nr. 3689899
  3.  John G. Proakis, Masoud Salehi: Communication Systems Engineering. 2. Auflage. Prentice Hall, 2002, ISBN 0-13-095007-6, S. 512.
  4.  C. Denis Mee, Eric D. Daniel: Magnetic Storage Handbook. 2. Auflage. McGraw Hill, 1996, ISBN 0-07-041275-8.

Literatur[Bearbeiten]

  •  John G. Proakis, Masoud Salehi: Communication Systems Engineering. 2. Auflage. Prentice Hall, 2002, ISBN 0-13-095007-6.