Možná hledáte: Run-length encoding – metoda komprese dat.

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.

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

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

Reference

editovat

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

  1. A Quarter Century of Disk File Innovation, IBM Journal of Research and Development.
  2. P.A. Franaszek (1972), “Run-Length-Limited Variable Length Coding with Error Propagation Limitation”, (US Patent 3689899).
  3. 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
  4. MEE, C. Denis, Eric D. Daniel. Magnetic Storage Handbook, 2nd Edition. [s.l.]: McGraw Hill, 1996. ISBN 0-07-041275-8. 

Externí odkazy

editovat