CZ9904739A3 - Způsob, zařízení a nosič pro kódování víceslovných informací - Google Patents

Description

ZPŮSOB, ZAŘÍZENÍ A NOSIČ PRO KÓDOVÁNÍ VÍCESLOVNÝCH INFORMACÍ

Oblast techniky

Vynález se týká způsobu uvedeného v úvodní části nároku 1.

Dosavadní stav techniky

US Patenty 4 559 625 Berlekamp a kol. a 5 299 208 Blaum a kol. zveřejňují dekódování prokládaných a proti chybám chráněných informací, kde chybová kombinace, nalezená v prvním slově, může být klíčem k nalezení chyb v jiném slově stejné skupiny slov. Označené chyby jsou poměrně těsnější nebo souvislejší než ostatní symboly slova, které by generovaly klíč. Odkazy používají standardizovaný formát a chybový model s vícesymbolovými chybovými bursty přes různá slova. Z přítomnosti chyby v konkrétním slově může vyplynout vysoká pravděpodobnost přítomnosti chyby v označeném symbolu v dalším slově nebo slovech. Postup často zvýší počet chyb, které mohou být opraveny před tím, než mechanizmus selže.

Vynálezce rozpoznal problém této metody: klíč se vytvoří poměrně pozdě v procesu, kdy bude informace vytvářející klíč demodulována, a také úplně opravena. To znesnadní použití opatření vyšší úrovně, jako je nový pokus o čtení dat během pozdější otočky disku. Vynálezce také rozpoznal, že část všech klíčů lze získat dokonce za nižší

79 101 • 9

9* 99 99 99 náklady ve smyslu množství redundance.

Podstata vynálezu

Proto je, kromě jiného, předmětem vynálezu zajistit formát kódování s nižší režií, který by umožnil dřívější generování alespoň části klíčů. Nyní je tedy vynález podle jednoho ze svých hledisek charakterizován význakovou částí nároku 1.

Vynález se také týká způsobu pro dekódování takovýchto informací, zařízení pro kódování a/nebo dekódování těchto informací a nosiče s těmito informacemi. Další výhodná hlediska vynálezu jsou uvedena v závislých nárocích.

Přehled obrázků na výkresech

Vynález bude blíže vysvětlen prostřednictvím konkrétních příkladů provedení znázorněných na výkresech, na kterých představuje obr. 1 systém s kodérem, nosičem a dekodérem;

obr. 2A - 2C uspořádání vzorových syne kombinací;

obr. 3 princip kódovacího formátu;

obr. 4 picket kód a dílčí kód indikace burstů.

Příklady provedení vynálezu

Klíč nebo kombinace klíčů, jakmile jsou nalezeny, mohou způsobit rozpoznání jednoho nebo více nespolehlivých symbolů. Díky tomuto rozpoznání, jako například definováním * · · · φ »4 · · · 4 ·· 44 4 4 *4 »· 44 mazacích symbolů (erasure symbols), bude oprava chyb účinnější. Mnoho kódů opraví nejvýše t chyb, pokud nejsou známá žádná místa chyb. Pokud je dáno jedno či více míst výmazů, může být často opraven vysoký počet výmazů e>t. Jsou možné i jiné typy rozpoznávání kromě mazacích symbolů. Lze také vylepšit i ochranu proti kombinaci burstů a náhodných chyb. Eventuálně bude zajištění míst výmazů pro konkrétní chybovou kombinaci vyžadovat použití pouze nižšího počtu syndromových symbolů, čímž se zjednoduší výpočet. Vynález může být použit v prostředí pro uchovávání nebo v prostředí pro přenos.

Obr. 1 ukazuje systém podle vynálezu uspořádaný k vytváření dvou druhů klíčů, jednoho odvozujícího ze skupin synchronizačních bitů a popřípadě druhého z klíčových slov chráněných proti chybám, v uvedeném pořadí. Provedení je použito ke kódování, uchovávání a nakonec dekódování posloupnosti vícebitových symbolů odvozených ze zvukových nebo obrazových signálů nebo z dat. Vývod 20 přijímá popořadě takové symboly, které mají například osm bitů. Dělička 22 opakovaně a cyklicky přenáší symboly určené pro klíčová slova do kodéru 24 a všechny ostatní symboly do kodéru 26. V kodéru 24 jsou vytvářena klíčová slova kódováním datových symbolů do kódových slov prvního vícesymbolového kódu opravy chyb. Tímto kódem může být ReedSolomonův kód, produktový kód, prokládaný kód nebo jejich kombinace. V kodéru 26 jsou vytvářena cílová slova kódováním do kódových slov druhého vícesymbolového kódu opravy chyb. V tomto provedení budou mít všechna kódová slova jednotnou délku, ale není to nutné. Oba kódy mohou být ReedSolomonovými kódy, přičemž první je dílčím kódem druhého. Jak bude ukázáno na obr. 4, klíčová slova mají vyšší stupeň ochrany proti chybám.

··

V bloku 28 jsou kódová slova přenesena na jeden nebo více výstupů, ze kterých byl ukázán libovolný počet, takže rozprostření na médiu, které bude probráno později, se sjednotí. Před samotným zápisem na médium jsou všechny kódové symboly modulovány do kanálových bitů. Dobře známé pravidlo modulace nutně zachovává omezení (d,k) = (l,7), které určuje minimální a maximální vzdálenosti mezi po sobě jdoucími signálovými přechody. Modulace přizpůsobuje posloupnost kanálových bitů lépe přenosu nebo možnosti uchování v řetězci kodér - médium - dekodér.

Z tohoto hlediska ukazuje obr. 2A vzorová syne kombinace, jak je uložena na disku, podle pit/no pit dichotomie. Kombinace, jak je ukázána, se skládá z posloupnosti devíti no-pit pozic, ihned následovaných kombinací devíti pit pozic. Taková kombinace poruší standardní omezení modulace, pokud k odpovídá délce posloupnosti menší než devět pit/no pit pozic. Pro stručnost byl vynechán detekční signál získaný při prohlížení takové posloupnosti. Celá kombinace může být bitové invertována. Původní a koncová bitová pozice kombinace mohou být použity k jiným účelům, vždy za předpokladu, že přechody nemohou nastat v bezprostředně následujících bitových pozicích.

Nyní na obr. 1 symbolizuje blok 30 samotné jednotné médium, jako je páska nebo disk, které přijímá zákódovaná data. Z toho může plynout přímý zápis v kombinaci zapisovacího mechanizmu a média. Případně může být médium realizováno kopírováním zakódovaného originálu média jako otisku. V bloku 32 jsou kanálové bity čteny znovu z média a bezprostředně poté demodulovány. Tím se vytvoří rozpoznané syne kombinace, a také kódové symboly, které musí být dále • · · · · ft ft ftftft ·* ·· «· ft* «· ftft dekódovány. Nyní se obecně syne kombinace vyskytují na pozicích, kde je přehrávací zařízení skutečně očekává, což vede k závěru, že synchronizace je správná. Ovšem správné syne kombinace se mohou nacházet na neočekávaných pozicích. To může znamenat ztrátu synchronizmu, který musí být znovu nastolen obtížným postupem, který je sám založen na různých přijatých za sebou následujících syne kombinacích. Obecně je synchronizace udržována setrvačným postupem nebo je založena na většinovém rozhodování mezi množstvím následujících syne kombinací. Správná syne kombinace se může díky jedné nebo více chybám kanálových bitů eventuálně nacházet v datech na jiných pozicích, než náležejí syne kombinacím. Obecně to bude osamocený výskyt a nepovede k pokusům o opětovnou synchronizaci. Na druhou stranu může demodulátor na očekávané pozici selhat při hledání synchronizační kombinace. Často bude chybou náhodný bit, který lze obnovit vlastní redundancí synchronizační kombinace. To povede ke správné syne kombinaci a umožní pokračovat standardním způsobem bez dalšího uvažování obnovené synchronizační kombinace pro ostatní kanálové bity. Eventuálně je chyba dostatečně vážná k usouzení, že jsme narazili na burst. Takový burst může pak poskytnout klíč k označení ostatních symbolů ve svém fyzickém sousedství, jako chybných, stejným způsobem, jak bude dále popsáno s. ohledem na klíčová slova. V zásadě by mohly klíče odvozené od syne stačit ke zlepšení standardní ochrany proti chybám. K tomuto účelu by se neměly nacházet příliš daleko od sebe. Pokud jsou klíče odvozeny od synchronizačních kombinací stejně jako od klíčových slov, mohou být synchronizační kombinace použity jako oddělený mechanizmus ke generování klíčů i před začátkem dekódování klíčových slov. To může umožnit použití dvou mechanizmů s klíči vedle sebe, jedné ze synchronizační kombinace a jednoho z klíčových slov. Eventuálně mohou být klíče ze ···· » · ♦ « ··· · ** «· ·* ·· ·· synchronizační kombinací a z klíčových slov zkombinovány. Výběr mezi různými právě popsanými mechanizmy může být proveden na základě statických nebo dynamických pravidel. Celkem často může být použito kombinování s klíči nalezenými při dekódování klíčových slov k získání silnějšího dekódování cílových slov.

Po demodulaci jsou klíčová slova poslána do dekodéru 34 a dekódována na základě jim vlastní redundance. Jak bude dále zřejmé z popisu obr. 3, takové dekódování může zavést klíče k místům chyb v jiných slovech, než jsou tato klíčová. Člen 35 přijímá tyto klíce a případné ostatní údaje šipkou 33 a pracuje na základě uloženého programu pro použití jedné nebo více různých strategií k převodu klíčů na místa výmazu nebo jiných údajů pro rozpoznání nespolehlivých symbolů. Vstup na lince 33 může představovat klíče vytvořené demodulací skupin syne bitů, nebo případně jiných údajů, jako jsou výsledky obecné kvality přijatého signálu, například odvozené od jeho frekvenčního spektra. Cílová slova jsou dekódována v dekodéru 36. Pomocí míst výmazů nebo jiných údajů je ochrana cílových slov proti chybám zvýšena na vyšší úroveň. Nakonec jsou všechna dekódovaná slova příslušným způsobem multiplexována pomocí členu 38 na původní formát na výstup 40. Pro stručnost bylo vynecháno mechanické rozhraní mezi různými subsystémy.

Obr. 2B, 2C znázorňují další uspořádání vzorových syne kombinací, jak jsou šířeny v informačním toku; Každá jednotlivá syne kombinace může vypadat jako na obr. 2A. Na prvním místě mohou být tyto syne kombinace pouze zdroji pro klíčové informace. Jsou přednostně zařazovány do periodicky rozložených míst v informačním toku. Případně se klíče mohou odvozovat jak od syne kombinací, tak od klíčových slov. Obr. 2B, 2C znázorňují druhý případ. Na nich byly pozice symbolů klíčových slov označeny křížky’. Pozice skupin syne bitů byly označeny tečkami. Na obr. 2B, 2C jsou vzdálenosti mezi symboly klíčových slov větší na místě skupiny syne bitů než jinde, takže jsou lokálně řidší. Na obr. 2A je jejich vzdálenost méně než dvojnásobek jejich hodnoty jinde. Na obr. 2B je rovna dvojnásobku jejich hodnoty jinde. Jiné rozložení je možné.

Obr. 3 znázorňuje jednoduchý kódovací formát, na kterém se nepodílejí skupiny syne bitů. Zakódované informace 512 symbolů byly pomyslně uspořádány do bloku o 16 řádcích a 32 sloupcích. Uložení na médiu je sériové po sloupcích s počátkem vlevo nahoře. Šrafováná oblast obsahuje kontrolní symboly a klíčová slova 0, £, 8^ a 12 mají každé 8 kontrolních symbolů. Každé cílové slovo obsahuje 4 kontrolní symboly. Celý blok obsahuje 432 informačních symbolů a 80 kontrolních symbolů. Naposledy uvedené mohou být umístěny rozprostřenějším způsobem ve svých odpovídajících slovech. Část informačních symbolů mohou být vyplňovací (prázdné) symboly. Reed-Solomonův kód umožňuje opravit v každém klíčovém slově až čtyři chyby symbolů. Právě přítomné chyby symbolů byly označeny křížky. Proto pak mohou být- všechna klíčová slova dekódována správně, pokud ovšem nikdy neobsahují více než čtyři chyby.. Slova 2 a 3 nemohou být evidentně dekódována pouze na základě svých vlastních redundantních symbolů. Nyní na obr. 3 všechny chyby, kromě 62, 66 a 68, představují chybové řetězce, ale jenom řetězce 52 a 58 kříží nejméně tři po sobě jdoucí klíčová slova. Ty se považují za chybové bursty a způsobí příznaky výmazu ve všech mezilehlých místech symbolů. Podle strategie může dostat jedno nebo více cílových slov před první chybou klíčového slova burstu a jedno nebo více cílových slov ihned

9

9 • 9

99

99 • · 99 za posledním klíčovým symbolem burstu také příznak výmazu. Řetězec 54 je příliš krátký na to, aby byl pokládán za burst.

Tedy dvě z chyb ve slově £ vytvoří příznak výmazu v odpovídajících sloupcích. To interpretuje slova 2 a _3 jako opravitelná, každé s jedním chybovým symbolem a dvěma symboly výmazu. Ovsem ani náhodné chyby 62, 68, ani řetězec 54 netvoří klíče pro slova 5, 6, Ί_, protože každé z nich obsahuje jen jedno klíčové slovo. Někdy může být výsledkem výmazu nulová kombinace chyby, protože libovolná chyba v osmibitovém symbolu má pravděpodobnost 1/256, že způsobí správný symbol. Podobně může burst křížící určité klíčové slovo, v něm vytvořit správný symbol. Strategie přemosťování mezi předcházejícími a následujícími klíčovými symboly jednoho burstu může zahrnout tento správný symbol do burstu a stejným způsobem se mohou chybové klíčové symboly přenést do výmazů pro odpovídající cílové symboly.

K uplatnění vynálezu se používají nové metody pro digitální optické ukládání. V současnosti může optické čtení používat přenosovou vrstvu tenkou 100 mikronů. Kanálové bity mohou mít velikost kolem 0,14 mikronů, takže datový bajt při kanálové rychlosti 2/3 bude mít délku pouze 1,7 mikronů. Na horním povrchu má paprsek průměr 125 mikronů. Umísťování disků do tzv. caddy snižuje pravděpodobnost velkých trhlin. Ovšem nežádoucí částečky menší než 50 mikronů mohou způsobit krátké poruchy. Výrobci používají chybový model, kde mohou takové poruchy rozšiřováním chyb způsobit ' bursty 200 mikronů, což odpovídá asi 120 bajtům. Tento model předpokládá bursty pevné délky 120B, které začínají náhodně s pravděpodobností 2,6.10^-5 na bajt, nebo v průměru jeden burst na 32 kB blok. Vynálezce se zaobírá otázkou sériového • · 4 · 4 · 4 4 444 44 4

4 4 · 4444 4444 ·· ·* 44 44 ·· 44 ukládání na optickém disku, ale konfigurace jako je vícestopá páska a jiné technologie jako magnetické a magnetooptické by mohly využívat zde vylepšený přístup.

Obr. 4 ukazuje picket kód a dílčí kód indikace burstů.

Picket kód se skládá ze dvou dílčích kódů A a B. Dílčí kód indikace burstů obsahuje klíčová slova. Je formátován jako hluboce prokládaný kód velkých vzdáleností, což umožňuje nalézt pozice více chyb burstů. Takto nalezené chybové kombinace jsou zpracovány k získání informací výmazu pro cílová slova, která jsou konfigurována v provedení jako dílčí kód produktu. Ten opraví kombinace více burstů a náhodných chyb použitím příznaků výmazu získaných z dílčího kódu indikace burstů. Indikátory zajištěné skupinami syne bitů mohou být použity izolovaně nebo v kombinaci s údaji z klíčových slov. Obecně, pokud nejsou dodána vůbec žádná očekávaná slova, počet skupin synchronizačních bitů se zvýší. Vytváření klíčů bude obdobné, jako postup načrtnutý s odkazem na obr. 3 pro klíčová slova.

Je navržen následující formát:

- blok 32 kB obsahuje 16 DVD kompatibilních sektorů

- každý takový sektor obsahuje 2064=2048+16 bajtů dat

- každý sektor po kódování ECC obsahuje 2368 bajtů

- tedy kódovací poměr je 0,872

- v bloku je 256 syne bloků formátováno následovně

- každý sektor obsahuje 16 syne bloků

- každý syne blok se skládá ze 4 skupin po 37B

- každá skupina 37B obsahuje 1B hluboce prokládaného dílčího kódu indikace burstů a 36B dílčího kódu produktu.

Na obr. 4 jsou řádky čteny sekvenčně, každý počínaje svou první syne kombinací. Každý řádek obsahuje 3 bajty dílčího kódu indikace burstů zobrazené šedě, postupně ·

4

4« • * · · 4 4 • 4 4 4 4

44 očíslované a oddělené 36 jinými bajty. Šestnáct řádků tvoří jeden sektor a 256 řádků tvoří jeden syne blok. Celková redundance byla vyšrafována. Synchronizační bajty mohou být použity k získání klíčů ze své redundance mimo hlavní kódovací zařízení. Uspořádání hardwaru provedení obr. 1 může provádět zpracování skupin synchronizačních bitů, které tvoří slova jiného formátu než jsou datové bajty v přípravném kroku. Další údaje mohou označovat určitá slova nebo symboly jako nespolehlivá, jako údaje o kvalitě signálu odvozeného z chyb disku nebo demodulace. Všimněme si, že nyní už není na obr. 4 nutný jeden sloupec nalevo pro klíčová slova dílčího kódu indikace burstů BIS. Jak je ukázáno, tento sloupec je naplněn cílovými slovy. Případně je sloupec zcela vynechán. V obou případech je zvýšena další hustota uložení uživatelských dat.

Skupina syne bitů je dobrým nástrojem pro objevování burstů díky její vlastní velké Hammingově vzdálenosti od bursty nejvíce zasažených kombinací. Typický odstup mezi skupinami syne bitů může být okolo 1000 kanálových bitů. Jiný formát spočívá v rozdělení 24 bitové kombinace syne bitů na dvě poloviny po dvanácti bitech, přičemž každá porušuje princip modulace jen jednou. Odstup mezi skupinami syne bitů je potom také rozpůlen na přibližně 500 bitů, takže režie zůstává stejná. K objevování burstů lze výlučně používat předurčené bitové frakce ze skupiny syne bitů. Všimněme si, že na obr. 3 by skupina syne bitů zabírala horizontální řádek nad pozicí prvního klíčového slova.

Zastupuje:

Dr. Pavel Zelený v.r.

• 4 advokát

120 00 Praha 2, Hálkova 2

Claims (20)

1. PATENTOVÉ NÁROKY

   1. Způsob pro kódování víceslovných informací, který je založen na vícebitových symbolech rozmístěných -vzájemně souvisle vzhledem k médiu, který zajišťuje prostředky slovního prokládání a slovního kódu ochrany proti chybám a dále klíče lokalizace chyb ve slovech skupiny více slov, vyznačující se tím, že první takové klíče vznikají ve skupinách synchronizačních kanálových bitů, a jsou určené pro datová slova.
2. 2. Způsob podle nároku 1, vyznačující se tím, že skupiny synchronizačních bitů leží na lokálně řidčeji rozmístěných dalších zdrojích klíčů, které se mají odvodit od nemodulovaných symbolů.
3. 3. Způsob podle nároku 2, vyznačující se tím, že další zdroje klíčů obsahují klíčová slova s vysokou možností ochrany, která jsou určena pro cílová slova s nízkou možností ochrany.
4. 4. Způsob podle nároku 1, vyznačující se tím, že skupina kanálových synchronizačních bitů, pokud není narušena, poruší pravidlo kanálové modulace aplikované na ostatní skupiny kanálových bitů.
5. 5. Způsob pro dekódování víceslovných informací, který je založen na vícebitových symbolech rozmístěných vzájemně souvisle vzhledem k médiu, který ovlivňuje inverzní slovní prokládání a odvozování slovních klíčů lokalizace chyb ve slovech skupiny více slov, vyznačující se

   09 79 101 • · · · • · φ φφφ φ φ «φφ φφ φ •φφφ φφφφ φφφφ ·· ·· φ* φφ φφ φφ tím, že odvozuje první takové klíče od skupin synchronizačních kanálových bitů, jak jsou určena pro datová slova.
6. 6. Způsob podle nároku 5, vyznačující se tím, že se odvozují druhé klíče lokalizace chyb z demodulovaných slov se symboly lokálně řidčeji rozloženými kolem takových skupin synchronizačních kanálových bitů, než jinde.
7. 7. Způsob podle nároku 5, vyznačující se tím, že se odvozují druhé klíče lokalizace chyb z demodulovaných slov vně takových skupin synchronizačních bitů a používá se první a druhý klíč ve vzájemné spolupráci.
8. 8. Způsob podle nároku 5, vyznačující se tím, že se odvozují druhé klíče lokalizace chyb z demodulovaných klíčových slov vysoké možnosti ochrany vně takových skupin synchronizačních bitů a jsou určené pro cílová slova s nízkou možností ochrany.
9. 9. Způsob pro kódování víceslovních informací, které je založené na vícebitových symbolech rozmístěných vzájemně spojitě vzhledem k médiu, obsahující prostředky slovního prokládání, prostředky slovního kódování chráněného proti chybám a generující prostředky pro generování klíčů lokalizace chyb ve slovech skupiny více slov, vyznačující se tím, že generující prostředky uplatní první takové klíče na skupiny synchronizačních kanálových bitů, a jsou určené pro datová slova.
10. 10. Zařízení podle nároku 9, vyznačující se tím, že prostředky prokládání a kódování jsou uspořádány pro uložení skupin synchronizačních bitů mezi lokálně • · 4 * · · ·· «4 ·· řidčeji rozmístěné další zdroje klíčů, které se mají odvodit od nemodulovaných symbolů.
11. 11. Způsob podle nároku 10, vyznačující se tím, že další zdroje klíčů obsahují klíčová slova s vysokou možností ochrany určená pro cílová slova s nízkou možností ochrany.
12. 12. Zařízení podle nároku 9, vyznačující se tím, že skupina synchronizačních kanálových bitů, pokud není narušena, poruší pravidlo kanálové modulace aplikované na ostatní skupiny kanálových bitů.
13. 13. Zařízení pro dekódování víceslovních informací založené na vícebitových symbolech rozložených vzájemně spojitě vzhledem k médiu, obsahující prostředky inverzního slovního prokládání, prostředky slovního dekódování chyb a prostředky lokalizace pro odvozování slovního klíče lokalizace chyb ve slovech víceslovné skupiny, vyznačující se tím, že se první takové klíče odvozují od skupin synchronizačních kanálových bitů, jak jsou směrována na datová slova.
14. 14. Zařízení podle nároku 13, vyznačující se tím, že dekódovací prostředky jsou uspořádány pro odvozování druhých klíčů lokalizace chyb z demodulovaných klíčových slov se symboly lokálně řidčeji rozloženými blízko takových skupin synchronizačních kanálových bitů, než jinde.
15. 15. Zařízení podle nároku 13, vyznačující se tím, že jsou dekódovací prostředky uspořádány pro odvozování druhých klíčů lokalizace chyb z demodulovaných slov vně takových skupin synchronizačních bitů a pro použití • · · · * · · · ftftftft ** ·· ftft ftft ftft ftft prvních a druhých klíčů ve vzájemné spolupráci.
16. 16. Zařízení podle nároku 13, vyznačující se tím, že dekódovací prostředky jsou uspořádány pro odvozování druhých klíčů lokalizace chyb z demodulovaných klíčových slov s vysokou možností ochrany vně takových skupin synchronizačních bitů a určeny pro cílová slova s nízkou možností ochrany.
17. 17. Nosič obsahující víceslovné informace, který je založen na vícebitových symbolech rozmístěných vzájemně spojitě vzhledem k médiu, který má prostředky slovního prokládání, slovního kódu ochrany proti chybám a klíče lokalizace chyb ve slovech víceslovné skupiny, vyznačující se tím, že první takové klíče vznikají ve skupinách synchronizačních kanálových bitů a budou cílena na datová slova.
18. 18. Nosič podle nároku 17, vyznačující se tím, že skupiny synchronizačních bitů jsou uloženy mezi lokálně řidčeji rozloženými dalšími zdroji klíčů tak, . aby se odvodily z demodulovaných symbolů.
19. 19. Nosíc podle nároku 17, vyznačující se tím, že další zdroje klíčů obsahují klíčová slova s vysokou možností ochrany, která jsou určena pro cílová slova s nízkou možností ochrany.

    • φφφ φ ·φ φ φφφφ • · φφ φφ φφ φφ φφ
20. 20. Nosič podle nároku 17, vyznačující se tím, že skupina synchronizačních kanálových bitů, pokud není narušena, poruší pravidlo kanálové modulace aplikované na ostatní skupiny kanálových bitů.