Run length limited

Run length limited (RLL, v českém překladu omezená délka běhu) je linkový kód používaný pro přenos libovolných dat komunikačním kanálem s omezenou šířkou pásma. Používá se v telekomunikacích a v systémech pro ukládání dat, u kterých se pohybuje médium vůči pevné záznamové hlavě.

Označení RLL znamená, že u těchto linkových kódů je omezena délka běhů – úseků opakovaných bitů, během kterých nedochází ke změně signálu. Pokud jsou běhy příliš dlouhé, je problém s obnovou hodin (synchronizace) – v případě, že jsou příliš krátké, signál obsahuje vysoké frekvence, které jsou komunikačním kanálem příliš tlumeny. Pomocí linkového kódu lze snížit časovou nejistotu při dekódování uložených nebo přijatých dat, která může vést k chybnému vložení nebo vypuštění bitů.

RLL kódy byly široce používány u pevných disků až do poloviny 80. let 20. století, a jsou stále používány u digitálních optických disků jako je CD, DVD, MD, Hi-MD a Blu-ray. RLL zajišťuje, že je vždy možné nalézt hranici mezi bity (zamezení prokluzu bit), a zároveň efektivně používá média k spolehlivému uložení maximálního množství dat v daném prostoru. První disky používaly velmi jednoduché metody kódování jako RLL (0,1) FM kód, u novějších disků se používají kódy RLL (2,7) a RLL (1,7), které se staly de facto standardem pro pevné disky vyrobené po roce 1990.

Na pevném disku jsou informace zaznamenány pomocí změn ve směru magnetického pole na disku. V počítači je informace reprezentována různým napětím ve vodiči: napětí blízké nule může znamenat binární nulu, kladné napětí v určitém rozsahu představuje binární jedničku. Naproti tomu u magnetických médií nese informaci magnetický tok – bud "severní“ pól nebo "jižní“ pól. Aby bylo možné převést magnetické pole na binární data, je zapotřebí použít nějakou metodu kódování, k překladu mezi magnetickým polem, a binárními daty.

Jeden z nejjednodušších praktických kódů, modifikovaný inverzní kód bez návratu k nule (anglicky Modified Non-Return-to-Zero-Inverted, NRZI) jednoduše kóduje jedničku jako změnu magnetické polarity ("obrácení toku") a nulu jako zachování polarity. Pokud disk rotuje konstantní rychlostí, každý bit představuje pevný časový interval ("datové okno") magnetického signálu, který reprezentuje tento bit; obrácení magnetického toku se může objevit pouze na začátku tohoto okna (starší disky používají stejnou délku datového okna pro celý disk, u moderních disků se na vnějších stopách používají kratší doby než na vnitřních viz zónový záznam).

Tato metoda je sice jednoduchá, ale je náchylná k chybám při čtení dlouhé posloupnosti nul.

Jednoduchý příklad: Binární vzorek '101', s datovým oknem 1 ns. Na disku bude uložen jako změna, následovaná žádnou změnou, a pak další změna. Pokud předchozí magnetická polarita byla pozitivní, může výsledný vzor vypadat takto: '−−+'. Hodnota 255 neboli samé jedničky, by byla zapsána jako '−+−+−+−+' nebo '+−+−+−+−'. Nulový bajt by byl zapsán jako '++++++++' nebo '−−−−−−−−'. 512bytový sektor nul by byl zapsán jako posloupnost 4096 bitů se stejnou polaritou.

Protože disk je fyzické zařízení, jeho otáčky se mohou mírně měnit v důsledku kolísání otáček motoru nebo teplotní roztažnosti disku. I fyzické médium diskety se může poněkud deformovat, a časovací obvod v diskovém řadiči může mít malou odchylku rychlosti. Pak se u dlouhého řetězce nul může stát, že poloha čtecí hlavy není známa zcela přesně, takže neexistuje žádný způsob, jak přesně zjistit počet nulových bitů. Odchylka rychlosti o pouhé 0,01% – což je mnohem lepší, než co lze zaručit u disketové mechaniky – může mít za následek, že chyba určení délky u posloupnosti 4096 bitů bude čtyři bity. Bez nějaké formy synchronizace a opravy chyb, by byla data zcela nepoužitelná.

Dalším problémem je maximální hustota záznamu, kterou umožňuje samotné magnetické médium: na určitou délku stopy lze zapsat určité množství změn polarity, což omezuje, kolik jedniček za sebou lze zapsat.

Aby se tomuto problému předešlo, jsou data kódována, takže nedochází k dlouhému opakování téhož bitu. Omezení maximálního počtu nul zapsaných za sebou zabraňuje ztrátě synchronizace, zatímco omezení počtu jedniček se sníží maximální potřebnou frekvenci změn polarity, což umožňuje uložit více dat na stejný disk.

Všechny kódy používané pro záznam na magnetické disky mají omezený počet nulových přechodů a proto je lze považovat za RLL kódy. Zatímco nejstarší a nejjednodušší varianty mají své názvy, například Modifikovaná frekvenční modulace (anglicky Modified Frequency Modulation, MFM), označení „RLL“ se často používá pouze pro složitější varianty, které vlastní název nemají. To však není technicky správně.

Terminogie RLL v oblasti pevných disků, konkrétně RLL (2,7), pochází od inženýrů firmy IBM, a byla poprvé použita v roce 1979 u zařízení IBM 3370 DASD^[1][2][3] používaných na střediskovém počítači série 4300.

Na konci 80. let 20. století začaly pevné disky pro osobní počítače používat varianty RLL složitější než MFM.

RLL kódy našly téměř univerzální použití v praxi u optického záznamu na disk, od roku 1980. Ve spotřební elektronice se používají RLL kódy jako EFM (anglicky Eight-to-Fourteen Modulation, česky osm ze čtrnácti): rychlost = 8/14, d = 2, k = 10), tento se používá pro kompaktní disky (CD) a MiniDisky (MD). Kód EFMPlus (rychlost = 8/16, d = 2, k = 10), se používá na DVD. Parametry d a k jsou minimální a maximální povolená délka běhu. Pro další informace o technologiích ukládání dat použijte odkazy uvedené na konci článku.

Délka běhu je počet bitů, pro které zůstává signál nezměněn. Délka běhu 3 pro bit 1 je posloupnost '111'. Pokud záznam na disku obsahuje posloupnost magnetických polarizací '+−−−−++−−−++++++', jedná se o běhy délky 1, 4, 2, 3, a 6. Terminologie technologie Run length limited předpokládá kódování NRZI, takže bity 1 indikují změny a bitu 0 označující nepřítomnost změny, takže výše uvedené posloupnosti by byly vyjádřeny jako '11000101001000001 ", a počítají se pouze běhy nulových bitů.

V jiném pojetí je délka běhu počet nul (v předchozím příkladě 0, 3, 1, 2 a 5) mezi sousedními jedničkami, což je o jedna méně než je počet bitových intervalů, po jejichž dobu signál skutečně zůstává nezměněn. Run length limited posloupnosti jsou charakterizovány dvěma parametry, (d) a (k), které udávají minimální a maximální délku běhu nul, která se může v posloupnosti objevit. Každý RLL je pak obecně specifikován zápisem (d, k) RLL. např.: (1,3) MFM RLL.

Předpokládejme, že magnetická páska dovoluje zapsat až 3200 obrácení magnetického toku na palec. Kódování MFM neboli (1,3) RLL používá pro uložení každého datového bitu dva bity, ale protože je zaručeno, že mezi každými dvěma jedničkovými bity (obrácení toku) bude nula (bez obrácení toku), je možné na jeden palec pásky uložit 6400 zakódovaných bitů, což je 3200 datových bitů. Kódování (1,7) RLL může uložit také 6400 zakódovaných bitů na palec pásky, ale protože používá jen 3 kódové bity k uložení 2 datových bitů, je výsledná hustota 4267 datových bitů na palec. Kódování (2,7) RLL používá 2 kódové bity k uložení jednoho datového bitu, ale protože zaručuje, že mezi libovolnými dvěma jedničkovými bity budou dva nulové bity, je možné uložit 9600 zakódovaných bitů na palec, což je 4800 datových bitů na palec.

Hustoty obrácení toku na pevných discích jsou výrazně vyšší, ale různé systémy kódování dovolují stejné zvýšení hustoty.

V kódovaného formátu jednička indikuje obrácení toku, zatímco nula znamená, že se v daném časovém intervalu magnetické pole na disku nezmění.

Protože termín „RLL kód“ se používá pro propracovanější kódování, tak diferenciální kód Manchester lze považovat za kód 1/2 RLL s jednoduchou rychlostí. Přidané jedničkové bity se označují jako hodinové (časovací).

Data	Zakódováno
0	10
1	11

Příklad:

Data:        0 0 1 0 1 1 0 1 0 0 0 1 1 0
Zakódováno: 1010111011111011101010111110
Hodiny:     1 1 1 1 1 1 1 1 1 1 1 1 1 1

Prodloužením maximální délky běhu 2 přilehlých bitů s hodnotou 0, se zlepší datová rychlost na 4/5. Jedná se o variantu IBM kódování group code recording.

Data Zakódováno 0000 11001 0001 11011 0010 10010 0011 10011 0100 11101 0101 10101 0110 10110 0111 10111

Data Zakódováno 1000 11010 1001 01001 1010 01010 1011 01011 1100 11110 1101 01101 1110 01110 1111 01111

Příklad:

Data:        0010 1101 0001 1000
Zakódováno: 10010011011101111010

Modifikovaná frekvenční modulace začne být zajímavá, protože používá omezení na D = 1 (minimálně jedna nula mezi každými dvěma jedničkami), což umožňuje trochu rychlost nahrávání rovnající se dvojnásobku toku odúčtování meze. Ačkoli kódovací rychlost MFM je pouze 1/2, dvojnásobná rychlost záznamu z ní činí metodu ekvivalentní kódům rychlosti 1.

Data	Zakódováno
0	x0
1	01

Kde „x“ je doplněk předchozího bitu. Slovo „modifikovaný“ v názvu kódu pochází z toho, že až na bit x má MFM stejnou tabulku jako FM. Vložené hodinové bity jsou nulové, kromě případů, kdy se hodinový bit vkládá mezi dva nulové bity (pak se vkládá jednička).

Příklad:

Data:        0 0 1 0 1 1 0 1 0 0 0 1 1 0
Zakódováno: x010010001010001001010010100
Hodiny:     x 1 0 0 0 0 0 0 0 1 1 0 0 0

Pokud do tabulky zahrneme předchozí bit (tj. bit n-1), dostáváme:

Data (bit n)	Data (bit n-1)	Zakódováno
0	0	10
	1	00
1	0	01
	1	01

Kód (1,7) RLL mapuje 2 bity dat na 3 bity na disku, přičemž kódování se provádí pro skupiny dvou nebo čtyř bitů. Pravidla pro kódování jsou: (x, y) se kóduje jako (NOT x, x AND y, NOT y), kromě případu (x, 0, 0, y), který se kóduje jako (NOT x, x AND y, NOT y, 0, 0, 0) ^[4]

Data	Zakódováno
00 00	101 000
00 01	100 000
10 00	001 000
10 01	010 000
00	101
01	100
10	001
11	010

Příklad:

Data:       0 0 1 0 1 1 0 1 0 0 0 1 1 0
Zakódováno: 101 001 010 100 100 000 001

(2,7) RLL mapuje n bitů dat na 2n bitů na disku; kódují se skupiny 2, 3 nebo 4 bitů.

Data	(2,7) RLL Zakódováno
11	1000
10	0100
000	000100
010	100100
011	001000
0011	00001000
0010	00100100

Příklad:

Data:        1 1  0 1 1  0 0 1 1
Zakódováno: 1000 001000 00001000

Alternativní kódování (1,7) RLL, která má nulovou stejnosměrnou složku (anglicky DC free), což pomáhá při posílání signálu dálkovými linkami a pro některé typy záznamových médií.

Data	Zakódováno
00	x01
01	010
10	x00
11 00	010 001
11 01	x00 000
11 10	x00 001
11 11	010 000

Kde „x“ je doplněk předchozího zakódovaného bitu (tj. 1, pokud předchozí bit byl 0, a 0 pokud předchozí bit byl 1).

Příklad:

Data:       0 1 0 0 1 1 0 1 0 1
Zakódováno: 010 101 000 000 010

• PRML
• Run-length encoding
• Linkový kód
• Samoopravný kód
• Komprese dat
• Modulace
• Fyzická vrstva
• Samosynchronizační kód a bitová synchronizace
• Kódování 8b/10b
• Eight-to-fourteen modulation a EFMplus jsou (2,10) RLL kódy bez stejnosměrné složky používané na CD a DVD.
• Ztráta bitové synchronizace

V tomto článku byl použit překlad textu z článku Run-length limited na anglické Wikipedii.

• Digital Magnetic Tape Recording