Délka běhu omezena - Run-length limited

Run-length limited nebo RLL coding is a line coding technique that is used to send arbitrary data over a communications channel with bandwidth limits. Kódy RLL jsou definovány čtyřmi hlavními parametry: m , n , d , k . První dva, m / n , odkazují na rychlost kódu, zatímco zbývající dva specifikují minimální d a maximální k počet nul mezi po sobě jdoucími. Používá se v telekomunikačních i paměťových systémech, které pohybují médiem kolem pevné záznamové hlavy .

Konkrétně RLL ohraničuje délku úseků (běhů) opakovaných bitů, během nichž se signál nemění. Pokud jsou běhy příliš dlouhé, obnova hodin je obtížná; pokud jsou příliš krátké, mohou být vysoké frekvence tlumeny komunikačním kanálem. Tím, modulaci na údaje , RLL snižuje nejistotu načasování dekódování uložených dat, což by vedlo k možnému chybnému vložení nebo odstranění bitů při čtení dat zpět. Tento mechanismus zajišťuje, že hranice mezi bity lze vždy přesně najít (zabraňující sklouznutí bitů ), zatímco efektivně využívají média ke spolehlivému uložení maximálního množství dat v daném prostoru.

Časné diskové jednotky používaly velmi jednoduchá kódovací schémata, jako je RLL (0,1) FM kód, následovaný RLL (1,3) MFM kódem, které byly široce používány v pevných discích až do poloviny 80. let a jsou stále používány v digitálním formátu optické disky jako CD , DVD , MD , Hi-MD a Blu-ray . Kódy RLL (2,7) a RLL (1,7) s vyšší hustotou se na počátku 90. let staly de facto průmyslovým standardem pro pevné disky.

Potřeba kódování RLL

Na jednotce pevného disku jsou informace představovány změnami ve směru magnetického pole na disku a na magnetickém médiu je výstup přehrávání úměrný hustotě přechodu toku. V počítači jsou informace představovány napětím na vodiči. Žádné napětí na vodiči ve vztahu k definované úrovni země by nebylo binární nula a kladné napětí na vodiči ve vztahu k zemi představuje binární napětí. Na druhé straně magnetické médium vždy nese magnetický tok - buď „severní“ pól, nebo „jižní“ pól. Aby bylo možné převést magnetická pole na binární data, je třeba k překladu mezi těmito dvěma způsoby použít některou metodu kódování.

Jeden z nejjednodušších praktických kódů, modifikovaný non-return-to-zero-inverted ( NRZI ), jednoduše kóduje 1 jako přechod magnetické polarity, známý také jako „obrácení toku“, a nulu jako žádný přechod. Když se disk otáčí konstantní rychlostí, každému bitu se přidělí stejné časové období, „datové okno“ pro magnetický signál, který tento bit představuje, a na začátku tohoto okna dojde k obrácení toku, pokud existuje. (Poznámka: starší pevné disky používaly jednu pevnou dobu jako datové okno na celém disku, ale moderní disky jsou komplikovanější; další informace viz pásmový záznam bitů .)

Tato metoda není tak jednoduchá, protože výstup přehrávání je úměrný hustotě jedniček, dlouhý běh nul znamená vůbec žádný výstup přehrávání.

V jednoduchém příkladu zvažte binární vzor 101 s datovým oknem 1 ns (jedna nanosekunda nebo jedna miliardtina sekundy). To se uloží na disk jako změna, následuje žádná změna a pak další změna. Pokud byla předchozí magnetická polarita již kladná, výsledný vzor může vypadat takto: −− +. Hodnota 255 nebo všechny binární hodnoty by byly zapsány jako - + - + - + - + nebo + - + - + - + -. Nulový bajt by byl zapsán jako +++++++++ nebo −−−−−−−−. 512bajtový sektor nul by byl zapsán jako 4096 sekvenčních bitů se stejnou polaritou.

Vzhledem k tomu, že disková jednotka je fyzickým hardwarovým prvkem, může se rychlost otáčení jednotky mírně měnit v důsledku změny rychlosti motoru nebo tepelné roztažnosti talíře disku. Může se také zdeformovat fyzické médium na disketě, což způsobí větší chyby časování a časovací obvod na samotném řadiči může mít malé odchylky v rychlosti. Problém je v tom, že s dlouhým řetězcem nul neexistuje možnost, aby řadič diskové jednotky znal přesnou polohu čtecí hlavy, a tedy žádný způsob, jak přesně vědět, kolik nul existuje. Změna rychlosti dokonce 0,1%, což je přesnější než u jakékoli praktické disketové mechaniky, může mít za následek přidání nebo odebrání 4 bitů z 4096bitového datového proudu. Bez nějaké formy synchronizace a opravy chyb by se data stala zcela nepoužitelnými.

Další problém je způsoben limity samotného magnetického média: je možné zapsat tolik změn polarity pouze v určitém prostoru, takže existuje horní hranice toho, kolik z nich lze také zapsat postupně, záleží na lineárním rychlost a mezera v hlavě.

Aby se tomuto problému zabránilo, jsou data kódována takovým způsobem, aby nedocházelo k dlouhému opakování jedné binární hodnoty. Omezením počtu nul zapsaných za sebou to umožňuje, aby řadič pohonu zůstal synchronizovaný. Omezením počtu těch zapsaných v řadě se sníží celková frekvence změn polarity, což umožňuje jednotce uložit více dat na stejné množství prostoru, což má za následek buď menší balíček pro stejné množství dat, nebo více úložiště v balíček stejné velikosti.

Dějiny

Všechny kódy používané k záznamu na magnetické disky mají omezenou délku běhů bez přechodu a lze je tedy charakterizovat jako kódy RLL. Nejstarší a nejjednodušší varianty dostaly specifická jména, například modifikovanou frekvenční modulaci (MFM), a název „RLL“ se běžně používá pouze pro složitější varianty, které takové konkrétní názvy nedostaly, ale termín se technicky vztahuje na všechny.

První "RLL" kód používaný na pevných discích byl RLL (2,7), vyvinutý inženýry IBM a poprvé komerčně použitý v roce 1979 na IBM 3370 DASD , pro použití s mainframem řady 4300 . Během konce 80. let 20. století začaly pevné disky PC používat vlastní RLL (tj. Varianty složitější než ty, které dostaly svá vlastní vlastní jména, například MFM). Kódy RLL našly téměř univerzální použití v praxi nahrávání optických disků od roku 1980. Ve spotřební elektronice se RLL jako kód EFM (rychlost = 8/17, d  = 2, k  = 10) používají na kompaktních discích (CD) a MiniDisc (MD) a kód EFMPlus (rychlost = 8/16, d  = 2, k  = 10) použitý na DVD . Parametry d a k jsou minimální a maximální povolené délky běhu. Pro větší pokrytí technologií úložiště jsou užitečné odkazy uvedené v tomto článku.

Technický přehled

Obecně délka běhu je počet bitů, pro které signál zůstává nezměněn. Délka běhu 3 pro bit 1 představuje sekvenci 111. Například vzor magnetických polarizací na disku může být + −−−− ++ −−− ++++++, s běhy délky 1, 4, 2, 3 a 6. Terminologie kódování s omezenou délkou běhu však předpokládá kódování NRZI, takže 1 bit označuje změny a 0 bitů označuje absenci změny, výše uvedená sekvence by byla vyjádřena jako 11000101001000001 a pouze běhy nulových bitů se počítají.

Poněkud matoucí je, že délka běhu je počet nul (0, 3, 1, 2 a 5 v předchozím) mezi sousedními, což je o jednu méně, než je počet bitů, kdy signál ve skutečnosti zůstane nezměněn. Sekvence s omezenou délkou běhu jsou charakterizovány dvěma parametry, d a k , které stanoví minimální a maximální délku běhu s nulovým bitem, které mohou v sekvenci nastat. Kódy RLL jsou tedy obecně specifikovány jako ( d , k ) RLL, např .: (1,3) RLL.

Kódování

V kódovaném formátu bit „1“ označuje přechod toku, zatímco „0“ označuje, že magnetické pole na disku se pro daný časový interval nezmění.

FM: (0,1) RLL

Obecně se termín „RLL kód“ používá k označení komplikovanějších kódování, ale původní kód Frequency Modulation , nazývaný také diferenciální Manchester kódování , lze považovat za jednoduchý kód RLL s rychlostí 1/2. Přidaných 1 bitů se označuje jako hodinové bity.

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
Encoded: 1010111011111011101010111110
Clock:   1 1 1 1 1 1 1 1 1 1 1 1 1 1

GCR: (0,2) RLL

Rozšířením maximální délky běhu na 2 sousední 0 bitů lze datovou rychlost zlepšit na 4/5. Toto je původní varianta záznamu s kódováním skupiny IBM

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

Tam, kde je to možné (11 z 16 kódů), bitový vzor abcdje kódován podle prefixu s komplementem : . V 5 případech, kdy by to porušilo jedno z pravidel ( nebo ), je nahrazen kód začínající 11 ( , kde e = a ∨ d ). aabcd000dab0011bea

Příklad:

Data:     0010 1101 0001 1000
Encoded: 10010011011101111010

Všimněte si, že ke splnění definice (0,2) RLL nestačí pouze to, že každý 5bitový kód neobsahuje více než dvě po sobě jdoucí nuly, ale je také nutné, aby jakákoli dvojice 5bitových kódů jako kombinace postupně nesmí obsahovat více než dvě po sobě jdoucí nuly. To znamená, že pro poslední dva libovolně vybrané kódy nesmí být mezi posledním bitem v prvním kódu a prvním bitem ve druhém kódu více než dvě nuly. To je vyžadováno, protože pro jakýkoli kód RLL platí limity délky běhu - v tomto případě 0 a 2 - pro celkový modulovaný bitový tok, nejen pro jeho komponenty, které představují diskrétní sekvence bitů jednoduchých dat. (Toto pravidlo musí platit pro libovolnou dvojici kódů bez výjimky, protože vstupními daty mohou být libovolné sekvence bitů.) Výše ​​uvedený kód IBM GCR splňuje tuto podmínku, protože maximální délka běhu nul na začátku 5 -bitový kód je jeden a rovněž maximální délka běhu na konci libovolného kódu je jedna, takže celková délka běhu je dva na křižovatce mezi sousedními kódy. (Příklad maximální délky běhu mezi kódy lze vidět ve výše uvedeném příkladu, kde kód pro data „0010“ končí nulou a kód pro další data, „1101“, začíná nulou, vytvoření spojení dvou nul na křižovatce těchto dvou 5bitových kódů.)

MFM: (1,3) RLL

Modifikovaná frekvenční modulace začíná být zajímavá, protože její speciální vlastnosti umožňují zápis jejích bitů na magnetické médium s dvojnásobnou hustotou libovolného bitového proudu. Existuje omezení toho, jak blízké mohou být přechody toku času pro čtecí zařízení k jejich detekci, a to omezuje, jak těsně lze bity zaznamenávat na médium: V nejhorším případě s libovolným bitovým tokem existují dva po sobě jdoucí, který produkuje dva po sobě jdoucí přechody toku v čase, takže bity musí být rozmístěny dostatečně daleko od sebe, aby mezi těmito přechody toku byl dostatek času, aby je čtenář mohl detekovat. Ale tento kód ukládá omezení d  = 1, tj. Mezi každým dvěma je minimálně jedna nula. To znamená, že v nejhorším případě jsou přechody toku dva bitové časy od sebe, takže bity mohou být dvakrát tak blízko sebe jako u libovolného bitového proudu, aniž by došlo k překročení schopností čtečky.

Tato zdvojnásobená hustota záznamu kompenzuje rychlost kódování 1/2 tohoto kódu (trvá dva bity, aby představoval jeden bit skutečné informace) a činí jej ekvivalentem kódu rychlosti 1.

Data	Zakódováno
0	x0
1	01

Zde je „x“ doplňkem předchozího kódovaného bitu (což je také předchozí datový bit). Kromě hodinových bitů - bit „x“ a „0“ v kódu „01“ - je to stejné jako u tabulky FM, a tak tento kód získává své jméno. Vložené hodinové bity jsou 0 s výjimkou mezi dvěma 0 datovými bity.

Příklad:

Data:     0 0 1 0 1 1 0 1 0 0 0 1 1 0
Encoded: x010010001010001001010010100
Clock:   x 1 0 0 0 0 0 0 0 1 1 0 0 0

(1,7) RLL

(1,7) RLL mapuje 2 bity dat na 3 bity na disku a kódování se provádí ve 2 nebo 4 bitových skupinách. Pravidla kódování jsou: ( x , y ) se stává (NOT x , x AND y , NOT y ), kromě ( x , 0, 0, y ) se stává (NOT x , x AND y , NOT y , 0, 0, 0 ). Při kódování podle níže uvedené tabulky je třeba použít nejdelší (poslední v tabulce) shodu; jedná se o situace zpracování výjimek, kdy by použití dřívějších pravidel vedlo k porušení omezení kódu.

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

Příklad:

Data:    0 0 1 0 1 1 0 1 0 0 0 1 1 0
Encoded: 101 001 010 100 100 000 001

(2,7) RLL

(2,7) je RLL rate- 1 / 2 kód, mapování n bitů dat na 2 n bitů na disku, jako MFM, ale proto, že minimální délka běhu je 50% delší (3-bitové krát namísto 2), přičemž bity lze zapisovat rychleji a dosáhnout tak o 50% vyšší efektivní hustoty dat. Kódování se provádí ve 2, 3 nebo 4 bitových skupinách.

Western Digital WD5010A, WD5011A, WD50C12

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

Seagate ST11R, IBM

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

Perstor Systems ADRC

Data	(2,7) RLL kódováno
11	1000
10	0100
000	100100
010	000100
001	001000
0111	00001000
0110	00100100

Zakódované formuláře začínají maximálně 4 a končí maximálně 3 nulovými bity, což dává maximální délku běhu 7.

Příklad:

Data:    1 1  0 1 1  0 0 1 1
Encoded: 1000 001000 00001000

Bez DC (1,7) RLL

K dispozici je také alternativní (1,7) kódování RLL, které se někdy používá k zabránění zkreslení stejnosměrného proudu (což pomáhá při odesílání signálu na velkou vzdálenost nebo u některých typů 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	x 00 001
11 11	010 000

Zde je „x“ doplňkem předchozího kódovaného bitu (tj. 1, pokud byl předchozí bit 0, a 0, pokud byl předchozí bit 1).

Příklad:

Data:    0 1 0 0 1 1 0 1 0 1
Encoded: 010 101 000 000 010

HHH (1,13)

Kód HHH (1,13) je kód rychlosti 2/3 vyvinutý třemi výzkumníky IBM (Hirt, Hassner a Heise) pro použití ve fyzické vrstvě IrDA VFIR 16 MB / s . Na rozdíl od magnetického kódování je toto navrženo pro infračervený vysílač, kde 0 bit představuje „vypnuto“ a 1 bit představuje „zapnuto“. Protože 1 bit spotřebovává více energie k přenosu, je navržen tak, aby omezil hustotu 1 bitu na méně než 50%. Zejména se jedná o (1,13 | 5) RLL kód, kde konečných 5 označuje další omezení, že existuje maximálně 5 po sobě jdoucích „10“ bitových párů.

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

Prvních osm řádků popisuje standardní (1,7) -RLL kód. Dodatečné šest výjimky zvýšit maximální běh nul do 13 (v právním vzoru 100 000 000 000 001, což představuje 10 11 10 11 a následně 01), ale omezují maximální průměrnou hustotu těmi, 1 / 3 . Nejdelší běh 1–0 párů je 000 101010 101 000.

Tento kód omezuje hustotu těmi, mezi 1 / 12 a 1 / 3 , s v průměru o 25,8%.

Příklady

Například kódujme bitovou sekvenci 10110010 s různými kódováními

Kódování	Data	Zakódováno
RLL (0,1)	10110010	1110111110101110
RLL (0,2)	1011 0010	01011 10010
RLL (1,3)	10110010	0100010100100100
RLL (1,7)	10 11 00 10	001010 101001
RLL (2,7)	10 11 0010	0100 1000 00100100

Hustoty

Předpokládejme, že magnetická páska může obsahovat až 3200 obrácení toku na palec. Modifikovaný frekvenční modulace , nebo (1,3) kódování RLL, ukládá každý bit dat jako dva bity na pásce, ale vzhledem k tomu, že je zaručeno, že jeden 0 (žádný tok obrácení) bit mezi libovolnými 1 (tok pro obracení) bitů, pak se je možné na pásku uložit 6400 bitů kódovaných na palec nebo 3200 datových bitů na palec. A (1,7) RLL kódování může také na pásku uložit 6400 kódovaných bitů na palec, ale protože uložení 2 datových bitů vyžaduje pouze 3 kódované bity, je to 4267 datových bitů na palec. A (2,7) RLL kódování trvá 2 kódované bity pro uložení každého datového bitu, ale protože je zaručeno, že mezi libovolnými 1 bity budou dva 0 bity, je možné na pásku uložit 9600 kódovaných bitů na palec, nebo 4800 datových bitů na palec.

Hustoty obrácení toku na pevných discích jsou podstatně větší, ale stejná vylepšení hustoty úložiště se projevují použitím různých kódovacích systémů.

Viz také

• Kódování 8b / 10b
• Bit skluzu
• Osm až čtrnáct modulace a EFMplus jsou RLL kódy bez DC (2,10) používané na CD, respektive DVD.
• Chyba při opravě kódů
• Řádkový kód
• Modulace
• Fyzická vrstva
• PRML
• Kódování délky běhu
• Samosynchronizační kód a bitová synchronizace
• Zdrojové kódování

Reference

Tento článek je založen na materiálu převzatém z Free On-line Dictionary of Computing před 1. listopadem 2008 a začleněného za podmínek „relicensing“ GFDL , verze 1.3 nebo novější.

externí odkazy

• Digitální záznam na magnetickou pásku