2A02:3035:603:6853:9A4C:2FD6:51C:2DC3: /* Varianten */Weiteres Deppenleerzeichen

2024-04-30T02:44:24Z

Varianten: Weiteres Deppenleerzeichen

Neue Seite

'''Run Length Limited''' (RLL) ist eine Gruppe von [[Leitungscode]]s, welche im Bereich der [[Telekommunikation]] und bei Speichermedien wie magnetischen [[Plattenspeicher]]n als [[Schreibverfahren]] verwendet werden. Diese Codes sind dadurch gekennzeichnet, dass bei ihnen die Länge einheitlicher Datenfolgen aus den Zuständen ''Logisch-0'' oder ''Logisch-1'' beschränkt ist. Von dieser Eigenschaft leitet sich die Bezeichnung 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ßrechner]]serie 4300 eingesetzt.<ref name="ibmquart" /><ref name="uspat3689899" /> Einfache RLL-Codes wurden in den 1980er und 1990er Jahren im Bereich der Datenaufzeichnung von [[Festplattenlaufwerk|Festplatten]] verwendet. Sie werden mit Adaptierungen auch heute noch in dem Bereich der magnetischen Datenaufzeichnung und bei optischen Speichermedien wie [[Compact Disc]] (CD) angewandt.

== Einteilung ==
RLL-Codes werden in der Literatur durch zwei Parameter ''d'' und ''κ'' klassifiziert und in der Form (''d'',''κ'')-RLL geschrieben.
Der Parameter ''d'' spezifiziert die minimale und ''κ'' die maximale Anzahl von logisch-''0'', die 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 [[Non Return to Zero#NRZI|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 [[Signalflanke]]n 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 [[Endlicher Automat|endlichen Automaten]] beschreiben, welcher über κ+1 Zustände verfügen muss. Ein bestimmter RLL-Code kann dann als eine [[Zustandsübergangsdiagramm|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]], der 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:

: <math> k = \lfloor \log_2 N(n) \rfloor</math>

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

: <math>C(d,\kappa) = \lim_{n\to\infty} \frac{1}{n} \log_2 N(n) = \log_2 \lambda_\mathrm{max}</math>

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.<ref name="proakiscap" />

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

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

{| class="wikitable" style="margin-left:2em"
|- class="hintergrundfarbe6"
! Eingangsdaten !! Codewort
|-
! 0
| 10
|-
! 1
| 11
|}

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

{| class="wikitable" style="margin-left:2em"
|- class="hintergrundfarbe6"
! Eingangsdaten !! Codewort
|-
! 0
| x0
|-
! 1
| 01
|}

Der 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 ===
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|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-Codes sind, d. h. nicht alle GCR-Codes sind automatisch (0,2)-RLL.

{| style="margin-left:2em"
|
{| class="wikitable"
|- class="hintergrundfarbe6"
! Eingangsdaten !! Codewort
|-
! 0000
| 11001
|-
! 0001
| 11011
|-
! 0010
| 10010
|-
! 0011
| 10011
|-
! 0100
| 11101
|-
! 0101
| 10101
|-
! 0110
| 10110
|-
! 0111
| 10111
|}
|
{| class="wikitable" style="margin-left:2em"
|- class="hintergrundfarbe6"
! 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:

{| class="wikitable" style="margin-left:2em"
|- class="hintergrundfarbe6"
! Eingangsdaten !! Codewort
|-
! 0
| 01
|-
! 10
| 10
|-
! 11
| 11
|}

=== (2,7)-RLL ===
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:

{| class="wikitable" style="margin-left:2em"
|- class="hintergrundfarbe6"
! Eingangsdaten !! Codewort
|-
! 10
| 0100
|-
! 11
| 1000
|-
! 011
| 001000
|-
! 010
| 100100
|-
! 000
| 000100
|-
! 0010
| 00100100
|-
! 0011
| 00001000
|}

=== (1,7)-RLL ===
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:

{| class="wikitable" style="margin-left:2em"
|- class="hintergrundfarbe6"
! 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 ([[Nicht-Gatter|NOT]] x, x [[Und-Gatter|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 [[Fano-Bedingung|Präfixbedingung]] erfüllt, ist die Reihenfolge der Zeilen bei der Codewortbildung wesentlich.<ref name="Mee" />

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 [[Kanal (Informationstheorie)|Kanäle]] übertragen werden soll, die keine Gleichsignale übertragen können, beispielsweise Funkkanäle oder [[Impulstransformator]]en zur [[Galvanische Trennung|galvanischen Trennung]] in elektrischen Schaltungen.

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

{| class="wikitable" style="margin-left:2em"
|- class="hintergrundfarbe6"
! Eingangsdaten !! Codewort
|-
! 00
| x01
|-
! 01
| 010
|-
! 10
| x00
|-
! 11 00
| 010 001
|-
! 11 01
| x00 000
|-
! 11 10
| x00 001
|-
! 11 11
| 010 000
|}

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

== Literatur ==
* {{Literatur|Autor=John G. Proakis, Masoud Salehi|Titel=Communication Systems Engineering|Auflage=2.|Verlag=Prentice Hall|Jahr=2002|ISBN=0-13-095007-6}}

== Einzelnachweise ==
<references>
<ref name="ibmquart">
{{Literatur
|Autor=J. M. Harker, D. W. Brede, R. E. Pattison, G. R. Santana, L. G. Taft
|Titel=A Quarter Century of Disk File Innovation
|Sammelwerk=IBM Journal of Research and Development
|Band=Band 25, Ausgabe 5
|Jahr=1981
|Seiten=677–690
|DOI=10.1147/rd.255.0677}}
</ref>
<ref name="uspat3689899">
P. A. Franaszek: ''Run-Length-Limited Variable Length Coding with Error Propagation Limitation.'' 1972, US-Patent Nr. 3689899
</ref>
<ref name="proakiscap">
{{Literatur
|Autor=John G. Proakis, Masoud Salehi
|Titel=Communication Systems Engineering
|Auflage=2.
|Verlag=Prentice Hall
|Jahr=2002
|ISBN=0-13-095007-6
|Seiten=512}}
</ref>
<ref name="Mee">
{{Literatur
|Autor=C. Denis Mee, Eric D. Daniel
|Titel=Magnetic Storage Handbook
|Auflage=2.
|Verlag=McGraw Hill
|Jahr=1996
|ISBN=0-07-041275-8}}
</ref>
</references>

[[Kategorie:Speichertechnologie]]
[[Kategorie:Leitungscode]]

Run Length Limited - Versionsgeschichte

2A02:3035:603:6853:9A4C:2FD6:51C:2DC3: /* Varianten */Weiteres Deppenleerzeichen