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.
Potřeba RLL kódování editovat
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.
Terminologie editovat
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.
Historie editovat
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.
Technický úvod editovat
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.
Kódování editovat
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í.
FM: (0,1) RLL editovat
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
GCR: (0,2) RLL editovat
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.
|
|
Příklad:
Data: 0010 1101 0001 1000 Zakódováno: 10010011011101111010
MFM: (1,3) RLL editovat
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 |
(1,7) RLL editovat
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 editovat
(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
DC Free (1,7) RLL editovat
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
Související články editovat
- 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
Reference editovat
V tomto článku byl použit překlad textu z článku Run-length limited na anglické Wikipedii.
- ↑ A Quarter Century of Disk File Innovation, IBM Journal of Research and Development.
- ↑ P.A. Franaszek (1972), “Run-Length-Limited Variable Length Coding with Error Propagation Limitation”, (US Patent 3689899).
- ↑ Five decades of disk drive industry firsts, DISK/TREND, Inc., publisher of market studies of the worldwide disk drive and data storage industries. web.archive.org
- ↑ MEE, C. Denis, Eric D. Daniel. Magnetic Storage Handbook, 2nd Edition. [s.l.]: McGraw Hill, 1996. ISBN 0-07-041275-8.