CZ305599A3

CZ305599A3 - Metoda pro kódování víceslovní informace prokládáním slov s protichybovou ochranou a metoda pro dekódování takové informace, zařízení pro kódování a/nebo dekódování takové informace a nosič s takovou informací

Info

Publication number: CZ305599A3
Application number: CZ19993055A
Authority: CZ
Inventors: Ludovicus Marinus Gerardus Maria Tolhuizen; Dijk Marten Erik Van; Constant Paul Marie Jozef Baggen
Original assignee: Koninklijke Philips Electronics N. V.
Priority date: 1997-12-29
Filing date: 1998-12-21
Publication date: 2000-02-16
Also published as: EP0965173A1; ID24253A; CA2282305A1; BR9807633B1; HUP0100551A2; WO1999034271A2; HUP0100551A3; IL131627A; AU766901B2; TR199902089T1; TW425773B; CZ301101B6; WO1999034271A3; JP2001515641A; HU223894B1; ZA9811897B; KR20000075856A; AR014200A1; AU1501199A; RU2224358C2

Description

Metoda pro kódování víceslovní informace prokládáním slov s protichybovou ochranou^ kdy—se—z©--s-l-ov—s—vysokou-ochranou ©dvozug-í—vodítka—polohy—-ehyfe,——která—jsou_nas®ěrována—na -slova—s—nízkou—-oehrano&i As metoda pro dekódování takové informace, zařízení pro kódování a/nebo dekódování takové informace a nosič s takovou informací.

Oblast techniky

Tento vynález se týká metody, tak jak je popsána v preambuli patentového nároku 1 v patentu US 4,559,625, Berlekamp et al a US 5,299,208, Blaum et al.

Dosavadní stav techniky

V těchto patentech je popsáno dekódování informačních slov, která jsou prokládána a zabezpečena proti chybám, které se vyznačuje tím, že z chybné struktury, která je nalezena v prvním slovu, se může nalézt poloha chyb v dalším slovu ze stejné skupiny slov. Použito je standardního formátu a chybového modelu, který obsahuje několik chybných znaků v různých slovech. Přítomnost chyby v určitém slovu naznačuje, že je velmi pravděpodobné, že se objeví chyba na místě odpovídajícího znaku v dalším slovu nebo slovech. Tento postup obvykle zvyšuje počet opravených chyb. Autoři tohoto vynálezu našli v tomto principu chybu: vodítko se uskuteční pouze v tom případě, kdy vodítkové slovo bylo úplně opraveno.

Podstata vynálezu

Důsledkem kromě jiného je, že cílem tohoto vynálezu je popsat kódový formát, ve kterém by byla vodítková slova správně dekódována s větším stupněm určitosti, než cílové slovo. Takže podle jednoho ze svých aspektů se vynález vyznačuje vlastnostmi, které jsou popsány v patentovém nároku 1. Nalezené vodítko může mít za následek vymazání znaku a nebo může na něj poukázat. Pomocí takovéhoto poukazování postupuje oprava chyb efektivněji. Ve skutečnosti mnoho kódů opraví maximálně t chyb v případě, že nejsou známy indikace pozic chyb. Pokud je dostupná informace o pozicích vymazaných znaků, může být obecně opraveno větší množství, e>t, znaků. Také se zlepší ochrana proti shlukům chyb a náhodným chybám. Dále, tím, že se zjistí informace o poloze výmazu, bude zapotřebí pouze menšího množství příznakových znaků, a tím se výpočet zjednoduší. V podstatě s tento vynález může použít jak při ukládání, tak i při přenosu informace.

Tento vynález se týká také metody na dekódování takto zakódované informace, přístroje na kódování a/nebo dekódování, které používá výše uvedenou metodu a také nosiče, na kterém je zaznamenaná informace jako rozhraní pro takové kódování a/nebo dekódování. Další výhodné aspekty jsou uvedeny v doprovodných patentových nárocích.

Přehled obrázků na výkrese

Tyto a další aspekty a výhody tohoto vynálezu budou detailněji popsány v dalším textu spolu s odkazy na popis • · ft ftft ftft 4*4444 ft · 4 4 4 4 f) • 4 · · *44 9 4 · 4 4 «· 4» výhodných provedení a zvláště s odkazy na doprovodné obrázky, ve kterých je znázorněno:

obr. 1 systém s kodérem, nosnou a dekodérem obr. 2 princip kódového formátu obr. 3 formát výsledného kódu obr. 4 kód s největší vzdáleností LCD a kód indikátoru shluku chyb obr. 5 tyčkový kód a subkód indikátoru shluku obr. 6 formát subkódu indikátoru shluku obr. 7 tyčkový kód a produktový subkód obr. 8 jeho různé aspekty obr. 9 alternativní formát obr. 10 detail prokládání

Příklady provedení vynálezu

Na obr. 1 je zobrazen systém podle tohoto vynálezu, který obsahuje kodér, nosič a dekodér. Toto provedení je určeno pro kódování, uchovávání a konečně dekódování sekvence vzorků či vícebitových znaků, které jsou odvozeny z audio či video signálu nebo z dat. Terminál 20 přijímá tok znaků, které mají v tomto příkladu velikost osmi bitů. Rozdělovač 22 rekurentně a cyklicky přesouvá první znaky určené na vodítková slova na kodér 24. Rozdělovač 22 dále přesouvá všechny další znaky na kodér 26. V kodéru jsou vodítková slova formována zakódováním přidružených dat do kódového slova prvního víceznakového opravného kódu. Tímto kódem může být Reed-Somononův kód, produktový kód, prokládaný kód nebo jejich kombinace. V kodéru 26 jsou • 4 ♦ · · «««· • · 4 · · · · ·»···« • · · » · · · • · · * · ♦ · « · · 51 * « · « « cílová slova formována kódováním do kódových slov druhého víceznakového opravného kódu. V provedení budou mít všechna kódová slova stejnou délku, ale toto není striktní požadavek. Oba kódy by měly výhodně být Reed-Solomonovy kódy, kdy první je subkódem druhého kódu. Jak je více zřejmé s odkazem na obr. 2, budou mít vodítková slova obecně daleko větší stupeň ochrany proti chybám a budou obsahovat relativně méně neredundandních znaků.

V bloku 28 jsou takto utvořená kódová slova předána na jeden či více výstupů, jejichž počet je volitelný, aby rozprostření na médiu bylo uniformní, což bude diskutováno později. Blok 30 představuje samotné médium, které přijímá zakódovaná data. Toto se může vztahovat na řízení zápisu ve vhodné kombinaci záznamového mechanismu a nosiče. Alternativně může být médium realizováno jako kopie masteru zakódovaného média, výlisek. Ukládání bude s výhodou optické a plně sériové, ale mohou být použity i další konfigurace. V bloku 32 budou z média znovu čtena různá slova. Pak budou vodítková slova prvního kódu poslána na dekodér 34 a dekódována s ohledem na jejich vlastní redundance. Bude dále zřejmé z další diskuse obr. 2, že takové dekódování může dát vodítka o místech chyb jinde než v těchto vodítkových slovech. Stupeň 35 přijímá tato vodítka a obsahuje program pro použití jedné nebo více různých strategií na překlad takových vodítek pro výmaz míst. Cílová slova jsou dekódována v dekodéru 36. Při řízení výmazu pozic je zvýšena protichybová ochrana cílového slova na přijatelnou úroveň. Nakonec jsou všechna dekódovaná slova demultiplexována pomocí elementu 38 v souladu s původním formátem na výstupu 40. Z důvodu stručnosti byly vypuštěny znaků. Záznam začátkem na a 12 mají 8 Další slova popisy mechanických konfigurací vzájemných rozhraní různých subsystémů.

Na obr. 2 je znázorněn relativně jednoduchý kódový formát. Jak je ukázáno, zakódovaná informace byla imaginárně uspořádána do bloku 16 řádků a 32 sloupců znaků, t.j. 512 na médium je sériový, sloupec po sloupci se horním levém sloupci. Vyšrafováná oblast obsahuje kontrolní znaky a slova 0, 4, 8 kontrolních znaků a tvoří vodítková slova, obsahují 4 kontrolní znaky a tvoří cílové slovo. Celý blok obsahuje 432 informačních znaků a 80 kontrolních znaků. Kontrolní znaky mohou být rozprostřeny spolu s jim příslušejícími slovy. Část informace může být tvořena prázdnými znaky. Reed-Solomonův kód umožní korekci každého vodítkového slova až do čtyřech znakových chyb. Skutečné znakové chyby jsou označeny křížky. Následkem mohou být všechna vodítková slova dekódována správně, protože neměla více než čtyři chyby. Zvláště slova 2 a 3 však nemusí být dekódována pouze na základě svých redundantních znaků. Nyní všechny chyby na obr. 2, kromě 62, 66 a 68, reprezentují chybové řetězce. Nicméně pouze řetězce 52 a 58, které přecházejí alespoň tři následná vodítková slova se považují za shluky chyb, takže alespoň všechna mezilehlá místa znaků budou označena výmazovou značkou. Cílová slova mohou také dostat na dané pozici výmazovou značku před chybou prvního vodítka shluku a cílovými slovy těsně za poslední chybou vodítka shluku, v závislosti na použité strategii. Řetězec 54 se nepokládá za shluk, protože je příliš krátký.

Následkem toho vutvoří dvě chyby ve slovu 4 značku výmazu na obou přidružených sloupcích. To způsobí, že je •8 9 8 0 9 9 0 8 * 8 9 9 0 8 0 900009 · 0 9 9 9 8

8899 899 899 90 99 99 možné slova 2 a 3 opravit, každé s jedním chybovým znakem a dvěma znaky výmazu. Avšak náhodné chyby 62, 68, ani řetězec 54, netvoří vodítka pro slova 5, 6 a 7, protože každý z nich obsahuje jen jedno vodítkové slovo. V určitých situacích může výmaz zapříčinit nulový chybový obrazec, protože náhodná chyba v 8-bitovém znaku má pravděpodobnost 1/256, že bude znak správný. Podobně dlouhý shluk, který prochází určitým vodítkovým slovem v něm může vytvořit správný znak. Spojením strategie mezi předcházejícím a následujícím vodítkovým znakem stejného shluku je tento správný znak včleněn do shluku a stejným způsobem, jako chybné vodítkové znaky, interpretován jako chybné hodnoty pro příslušné cílové znaky. Výše uvedená rozhodnutí mohou být doplněna podle dekódovacího systému další kontrolou dalšími parametry.

Diskuse praktického formátu

V dalším bude popsán praktický formát. Na obr. 3 je znázorněn produktový kódový formát. Slova jsou horizontální a vertikální a parita je vytečkována. Na obr. 4 je znázorněn tzv. kód s největší vzdáleností se zvláštní detekcí shluku v horních několika slovech, která mají více parity. Tento vynález popisuje tzv. tyčkový kód, který může být sestaven jako kombinace pravidel z obr. 3 a 4. Zápis je podél šipek z obr. 3 a 4 vždy sekvenční.

Praktické aspekty tohoto vynálezu jsou vytvořeny novými metodami digitálního optického záznamu. Zvláštní vlastností je, že v případě bezdotykového čtení substrátu má svrchní propustná vrstva tloušíku pouze 100 mikrometrů. Kanálové • · · · · · · » * použili chybový model které začínají náhodně s pevnou velikosti s pravděpodobností bity mají velikost kolem 0,14 mikrometrů, takže jeden byte dat s kanálovou rychlostí 2/3 bude mít délku pouze 1,7 mikrometrů. Průměr paprsku na nejvyšším povrchu má průměr kolem 125 mikrometrů. Krabička nebo obal disku zmenší pravděpodobnost dlouhých shluků, Nicméně nevhodné částečky o velikosti menší než 50 mikrometrů mohou způsobit krátké výpadky. Autoři vynálezu použili mimo jiného chybový model, ve kterém podobné výpadky vinou šíření chyb mohou vést ke shlukům o velikosti 200 mikrometrů, což odpovídá přibližně 120 bytům. Autoři vynálezu zvláště shluku 120 bytů, na byte 2,6*10⁵, nebo průměrně jeden shluk na blok 3 2 kB. Tento vynález byl podpořen vývojem záznamu na optický disk, nicméně jiné způsoby záznamu, jakými jsou několikastopý pásek a jiné technologie jako magnetický a magnetooptický záznam mohou také těžit z vylepšeného přístupu, který je zde popsán.

Na obr. 5 je znázorněn tyčkový kód a subkód indikátoru shluku. Tyčkový kód se sestává ze dvou subkódů A a B. Subkód indikátoru shluku (BIS) obsahuje vodítková slova. Je to formát s hluboce prokládaným kódem s největší vzdáleností, který umožňuje lokalizaci polohy několika shluků chyb. Takto nalezené chybové obrazce jsou zpracovány a získá se tak informace pro výmaz pro cílová slova, která jsou konfigurovaná v tomto provedení jako produktový subkód (PS). Produktový subkód opraví kombinace několika shluků chyb a náhodných chyb pomocí použití značek výmazu, které se získají od subkódu indikátoru shluku.

Následuje doporučený formát:

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

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

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

- takže rychlost kódování je 0,872

- v bloku je 256 synchronizačních bloků formátováno následovně

- každý sektor obsahuje 16 synchronizačních bloků

- každý synchronizační blok obsahuje 4 skupiny 37 bytů

- každá skupina 37 bytů obsahuje 1 byte hluboce prokládaného BIS a dále 36 bytů PS.

Jak ukazuje obr. 5, řádky jsou z disku čteny sekvenčně, počátkem předchozího synchronizačního obrazce. Každá řádka obsahuje 4 byty BIS znázorněného tečkované a konsekutivně číslovaného a odděleného 36 dalšími byty. Šestnáct řádek tvoří jeden sektor a 256 řádek tvoří jeden synchronizační blok.

Na obr. 6 je znázorněn pouze jeden subkód indikátoru shluku stejných 64 očíslovaných bytů na sektor z obr. 5 a je sestaven následovně:

- 16 řádků, každý s (64, 32, 33) RS kódem s t=16.

- sloupce se sekvenčně odvozují z disku tak, jak ukazuje šipka, takže skupina čtyř sloupců se odvodí z jednoho sektoru pro rychlé adresování.

- BIS může indikovat alespoň 16 shluků, každý s 592 byty (asi lmm).

zvláště 16 bytů hlavičky DVD, 5 bytů parity za hlavičkou, aby se umožnilo rychlé adresování čtení a 11 bytů uživatelských dat.

Na obr. 7 je znázorněn tyčkový kód a jeho produktový subkód, který je sestaven z cílových slov. Byty produktového subkódu jsou číslovány v takovém pořadí, v jakém jsou čteny • φ φ · · Φ· ΦΦΦΦ·· * · φφφ · · φφφφ φφφ φφφ φφ ·φ ·» z disku, BIT byty se ignorují.

Na obr. 8 jsou znázorněny další aspekty tohoto provedení produktového subkódu. Zvláště, produktový subkód je [256,228,29]*[144,143,2] produktový kód Reed-Solomonova kódu. Počet datových bytů je 228*143=32604, což je šestnáct krát [2048+11] uživatelských bytů plus 12 volných bytů.

Na obr. 9 je znázorněn alternativní formát k obrázku 8, kde je úplně vynechán horizontální Reed-Solomonův kód. Velikost horizontálního bloku je 36 bytů (jedna čtvrtina z obr. 7) a používá [256,224,33] Reed-Solomonův kód. Každý sektor má 2368 bytů a nejsou potřeba žádné prázdné byty.

Kód v prvním sloupci je formován ve dvou krocích. Z každého sektoru je nejdříve 16 bytů hlavičky zakódováno do [20,16,5] kódu, aby se umožnila rychlá obnova adresy. Výsledných 20 bytů a dalších 32 uživatelských bytů na sektor tvoří datové byty a jsou společně zakódovány dále. Datové znaky jednoho 2K sektoru mohou ležet pouze v jednom fyzickém sektoru, jak je popsáno dále. Každý sloupec [256,224,33] kódu obsahuje 8 paritních znaků na 2k sektor. Dále, každý [256,208,49] kód má 12 paritních znaků na 2K sektor a 4 paritní znaky [20,16,5] kódu a vytváří [256,208,49] kód se 48 redundandními byty.

Na obr. 10 je toto prokládání znázorněno detailněji. Zde křížek znamená byty hlavičky, čtvereček parity [20,16] kódu, tečka 32 dalších datových bytů a 12 paritních bytů kódu [256,208].

Claims

Patentové nároky

1. Metoda pro kódování víceslovní informace, která je založena na vícebitových znacích relativně sobě blízkých s ohledem na médium, která provádí prokládání slov a kódové prostředky pro protichybovou ochranu slov a poskytuje vodítka na pozice chyb ve víceslovných skupinách vyznačující se tím, že tato vodítka začínají ve vysoce chráněných vodítkových slovech a jsou namířeny na nízce chráněná cílová slova.
2. Metoda podle bodu 1 vyznačující se tím, že taková vodítková slova mají jednotnou velikost a jsou rozmístěna druhým stejným způsobem.
3. Metoda podle bodu 1 vyznačující se tím, že je použitá při záznamu na optické médium.
4. Metoda podle bodu 1 vyznačující se tím, že zmíněná vodítková slova obsahují hlavičku, která obsahuje informace o přidružených sektorech uvnitř bloku, které obsahují výše zmíněné kódové prostředky a informace v jejichž hlavičce jsou přivedeny na zmíněné médium v sekvencích na pozice v příslušných sektorech.
5. Metoda podle bodu 4 vyznačující se tím, že v sektoru má informace v hlavičce přídavnou protichybovou ochranu mimo zmíněných kódových prostředků.
6. Metoda pro dekódování přijaté vícebitové informace, která je založena na vícebitových znacích, které se nacházejí v relativní blízkosti s ohledem k médiu, kterou se provádí extrakce slov a dekódování kódových prostředků protichybové ochrany, včetně vyhodnocení vodítek pozice chyb ve víceslovné skupině

W SoXM?

vyznačující se tím, že odvozením takových vodítek z vodítkových slov s vysokou ochranou, které jsou směrovány k cílovým slovům s nízkou ochranou.
7. Metoda podle bodu 6 vyznačující se tím, že je založena na vodítkových slovech, která mají první stejnou velikost a jsou rozmístěna prvním jednotným způsobem a cílová slova, která mají druhou stejnou velikost a jsou rozmístěna druhým stejným způsobem.
8. Metoda podle bodu 6 vyznačující se tím, že je použita pro záznam na optické médium.
9. Metoda podle bodu 6 vyznačující se tím, že opravené znaky ve vodítkových slovech poskytují příslušná vodítka a následné vodítka v řadě přijaté informace společně dávají výmazové značky pro mezilehlé znaky cílových slov.
10. Metoda podle bodu 9 vyznačující se tím, že mezilehlým nezměněným znakům vodítkového slova v takové řadě je přiřazeno imaginární vodítko.
11. Metoda podle bodu 6 vyznačující se tím, že zmíněné vodítkové slovo obsahuje hlavičku obsahující informaci o příslušných sektorech uvnitř bloku, která obsahuje výše zmíněné kódové prostředky a sestavování zmíněné hlavičky s informací ze zmíněného média na polohách příslušných sektorů, které sekvenčně jim odpovídají.
12. Metoda podle bodu 11 vyznačující se tím, že se provádí protichybová ochrana v sektoru hlavičky s informací mimo zmíněných kódových prostředků.
13. Zařízení pro kódování víceslovní informace, která je založena na vícebitových znacích v s médiem a které obsahuje prostředky relativní blízkosti pro prokládání slov, prostředky pro kódování na zabezpečení prostředků kódové .··. .: .: .··. .··..··. IWST-V • to toto·*··· ^v • · » toto·· ·»· ··· • · ··· «· ···· ··» ··· toto ·· ·· ochrany slov a prostředky pro vytváření vodítek umístění chyb ve víceslovných skupinách vyznačující se tím, že tyto prostředky jsou uspořádány pro vytváření takovýchto vodítek s počátkem ve vodítkových slovech s vysokou ochranou a ukazují na vodítková slova s nízkou ochranou.
14. Zařízení podle bodu 13 vyznačující se tím, že prostředky pro prokládání jsou uspořádány pro prokládání daných vodítkových slov s první stejnou velikostí při rozmístění prvním stejným způsobem s ohledem na cílová slova, která mají druhou stejnou velikost a jsou rozmístěna druhým stejným způsobem.
15. Zařízení pro dekódování přijaté víceslovné informace, která je založena na vícebitových znacích, které jsou v relativní blízkosti s ohledem k médiu a má prostředky pro kompresi slov a prostředky pro dekódování kódu protichybové ochrany a prostředky pro vyhodnocování vodítek polohy chyb ve víceslovných skupinách, vyznačující se tím, že zmíněné prostředky pro vyhodnocování jsou uspořádány pro odvozování zmíněných vodítek z vodítkových slov s vysokou ochranou a jejich použitím v cílových slovech s nízkou ochranou.
16. Zařízení podle bodu 15 vyznačující se tím, že je založeno na vodítkových slovech, které mají první stejnou velikost a jsou rozmístěna prvním stejným způsobem a cílových slovech, které mají druhou stejnou velikost a jsou rozmístěna druhým stejným způsobem.
17 Fyzický nosič, který je vytvořen použitím metody podle bodu 1, který obsahuje pole prokládaných vodítkových slov a cílových slov, zmíněná vodítková slova mají vysokou • · · ·· · ··· protichybovou ochranu s ohledem na zmíněná cílová slova.
18. Nosič vodítková rozmístěna se tím, že zmíněná velikost a jsou ohledem na cílová podle bodu 17 vyznačující slova mají první stejnou prvním stejným způsobem s slova, která mají druhou stejnou velikost a jsou rozmístěna druhým stejným způsobem.
19. Nosič podle bodu 17 vyznačující se tím, že je založený na optickém záznamu.
20. Nosič podle bodu 17 vyznačující se tím, že se používá spolu s bezdotykovým čtením substrátu.
21. Nosič podle bodu 17 vyznačující se tím, že zmíněná vodítková slova obsahují hlavičku s informací o přidružených sektorech v bloku, který obsahuje zmíněný kód a která je nacházejí na zmíněném médiu v odpovídající sekvenci k dispozici příslušných přidružených sektorů.
22. Nosič podle bodu 21 vyznačující se tím, že v sektoru má hlavička s informací protichybovou ochranu vně zmíněného kódu.