Spôsob dekódovania samoopravných kódov násobkov zostrojených z najmenej dvoch kódov BCH

Číslo patentu: 277719

Dátum: 17.12.1991

Autor: Farkas Péter

Stiahnuť PDF súbor.

Zhrnutie / Anotácia

Riešenie sa týka spôsobu ochrany údajov prenášaných alebo uchovávaných na rôznych médiách voči chybám. Riešenie umožňuje zvýšiť samoopravnú schopnosť kódu násobku zostrojeného aspoň z dvoch BCH kódov. Podstata spôsobu dekódovania spočíva v tom, že pri dekódovaní prvej série kódových slov sa vykonáva len oprava kombinácií, v ktorých je predpoklad, že je najviac t1 chýb a pri dekódovaní ďalších sérií kódových slov sa vykonávajú opravy ti chýb a označenia tých kódových slov, v ktorých je odhalená neopraviteľná chyba, ako zmazaných. Po dekódovaní všetkých sérií slov použitých v kóde násobku - po ukončení prvého cyklu sa pokračuje ďalším cyklom od prvej série slov, pričom sa vykonávajú opravy t1 chýb a vyznačenia zmazaní a táto informácia sa využíva pri dekódovaní ďalšej série slov, až pokiaľ je ukončený druhý cyklus, pritom dekódovanie samoopravného kódu násobku pozostáva najmenej z dvoch cyklov.

Text

Pozerať všetko

SLOVENSKÁ REPUBLIKA ,(19) SK Číslo prihlášky 832-90(Sl) Int C 1.5 Číslo prioritnej prihlášky H o M 13/00 Dátum priority. Krajina priority ÚRAD i Dátum zverejnenia 17.12.91 PRIEMYSELNÉHO vLAsTNjcTvA Dátum oznámenia o udelení vo Vestníku 10.08.94 SLOVENSKEJ REPUBLIKY Číslo PCT(73) Majiteľ patentu Slovenská technická miiverzita, Elektrotechnická fakulta, Bratislava, SK(72) Pôvodca vynálezu FARKAŠ Peter Ing. CSc., Bratislava, SK(54) Názov vynálezu Spôsob dekódovania samoopravných kódov násobkov msmjených z najmenej dvoch kódov BCH(57) Anotácia Riešenie sa týka spôsobu ochrany údajov prenášaných alebo uchovávaných na rôznych médiách voči chybám. Riešenie umožňuje zvýšiť samoopravnú schopnosť kódu násobku zostmjenélm aspoň z dvoch BCH kódov. Podstata spôsobu dekódovania spočíva v tom, že pri dekódovam prvej série kódových slov sa vykonáva len oprava kombinácii, v ktorých je predpoklad, že je najviac tl chýb a pri dekódovaní ďalších sérií kódových slov sa vykonávajú opravy ti chýb a označenia tých kódových slov, v ktorých je odhalená neopravíteľná chyba, ako zmazaných. Po dekódovani všetkých sérii slov použitých v kode násobku - po ukončení prvého cyklu sa pokračuje ďalším cyklom od prvej série slov, pričom sa vykonávajú opravy t chýb a vyznačenía mazani a táto infonnácia sa využíva pri dekódovaní ďalšej série slov, až pokiaľ je ukončený druhý cyklus, pritom dekódovatue samoopravného kódu násobku pozostáva najmenej z dvoch cyklov.Vynález sa týka spôsobu dekodovania samoopravných kódov násobkov zostrojených z naj menej dvoch kódov BCI-I.Doterajšl spôsob dekódovania samoopravných kódov násobkov publikovali Reddy S. NL a Robinson J. P. v práci Random error and burst correction by itemted codes. IEEE Trans. Info. Theory, 18, 1972, s. 182-185 a tato metoda je popísaná pre kód násobok pozostávajúci z dvoch kódov sírčiniteľov BCH niekedy nazývaných stĺpcovým a riadkovým kódom, pretože kódom násobkom C C 1.C 2 dvoch kódov Cl a C 2 sanazývakód, ktorého slovami sú všetky dvojrozrnerné tabuľky, ktorých ríadky sú slovami kódu c 1 a stĺpce sú slovami kódu cz. Množinu všetkých kódových slov kódu Ci budeme nazývať i-tou sériou slov. Je známe, že ak kódová vzdialenosť minimálna Hammingova vzdialenosť dvoch ľubovolných rôznych kódových slov určitého kódu C 1 je dl a kódova vzdialenosť kódu C 2 je d 2, tak pre kódovú vzdialenosť kódu C platia kód C umožňuje zaručene opraviť t chýb v kódovom slove pričomts(d 1.d 2-l)/2. (2) Pri známom spôsobe dekódovanie je v slovách prvej série opravovaných tl chýb pričom 2.tl l s dl (3)a súčasne sú robené zmamnia odhalených v danom okamžiku neopraviteľných chýb a kódovému slovu prvej série sa priradí po dekódovani číslo mj, ktoré udáva počet vykonaných opráv. Číslo (nj je Hammingovou váhou odhadu ei (j) chybového vektora j-teho kódového slova prvej série. Potom sa dekódujú kódové slová druhej se» rie tak, že sa vykonajú opravy chýb a zmamní, pričom sa využíva aj informácia dana číslami (nj. Známy spôsob je opísaný pre kód nasobok pozostávajúci z dvoch kódov BCH, jeho roůírenie na kód násobok pozostávajúci z N kódov BCH je zrejmé. Pre kód C C 1.C 2 Ci CNpotom vzťah (l) prejde do vzťahu d dl.d 2 dN, (4) vzťah (2) do vzťahu ts(d 1.d 2 dt~I- l) /2 (5)a pre počet opraviteľných chýb v slove i-tej série platí 2.ti 1 s di. (6)Známy spôsob umožňuje zaručene opraviť t chýb v kódovom slove kódu C a časť kombinácii, v ktorých je viac ako t chýb. Nevýhodou je, že samoopravuý kód násobok dáva možnosť opraviť väčšiu časť kombinácii chýb, v ktorých počet chýb je väčší ako t, to znamená, že samoopravná schopnosť kódu sa môže zväčšiť.Iný mámy spôsob, ktorý je blízky spôsobu navrhovanému v týchto podkladoch, je podľa patentu DE 371 7223 Al, ktorý sa týka dekódovania kódov násobkov zostrojených z dvoch kódov súčiniteľov a ktorý pozostáva z nasledovných krokova) Zozbieranie úplného bloku kódovćho slova násobkub) Určenie všetkých syndrómov prvých kódových slov a druhých kódových slov a zostrojenie rozlišovacích mačiek pre každé kódové slovo, ktorého syndróm je rôzny od nuly.c) Sčítanie počtu rozlišovacich mačiek pre všetky prvé kódové slova a zvlášť sčítanie počtu rozlišovaclch mačiek pre všetky druhé kódové slová.d) Určenie polohy chyby pre jedno z prvých kódových slov s nenulovým syndrómom.e) Detekcia jedného druhého kódovćho slova označeného rozlišovacou značkou, ktoré obsahuje tuto chybnú pozíciu, pri kladnom výsledku detekcia oprava tejto pozicie, v opačnom prípade prechod na ďalšie slovo podľa d).t) Aktualizácia syndrómov príslušného prvého kódového slova a príslušného druhého kódového slova po korektúre podľa kroku e), aktualimcia rozlišovacích mačiek a deluementácia výsledkov súm počtov rozlišovacích mačiek v prípade, že oba syndrómy sú nulové a prechod na ďalšie kódové slovo - krok d).g) Zmena funkcie prvých a druhých kódových slov a opakovanie krokov d), e), f) po spracovaní všetkých ako chybne označených prvých kódových slov, až kým ďalšie dve vykonania krokov d), e) a t) pre všetky aktuálne prvé kódové slová nevedú k žiadným zmenám. h) Vydanie kódového slova kódu nasobku spolu so sígnalizáciou či je považované m správne alebo nesprávne.Autor DE 371 7223 A 1 uvádza, že výhodou takéhoto riešenia je, že za predpokladu, že nastanú súčasne dve chyby v jednom kódovom slove prvého alebo druhého kódu súčiniteľa, míži sa pravdepodobnosť vykonania chybnej opravy tým, že sa kontroluje druhé kódové slovo. Nevýhodou takéhoto riešenia je, že obsahuje veľa zbytočných krokov v prípade, že je pravdepodobnosť nezávislých chýb na vstupe nizka, ako to je napr. pri reálnych optických pamäťových systémoch typu CD ROM na vstupe dekodéra prídavného kódu,kde p 104 . V tomto pripade je pravdepodobnosť,že chyby zasiahol jeden blok kódového slova kódu násobku jednej chyby v bloku približne 1.l 0-7 a pravdepodobnosť dvoch chýb v bloku približne 1.1045. Aj za predpokladu, že nastane udalosť vmiku dvoch chýb v bloku kódového slova násobku, je pravdepodobnosť udalosti, že tieto dve chyby zasiahnu to isté kódové slovo jedného kódového súčiniteľa F 2 0,059. Podobné úvahy platia aj vo všeobecnejšom prípade, ak pre uvedené kódové slová mąjú primeranú veľkosť. Ďalšou nevýhodou riešenia podľa DE 371 7223 A 1 je skutočnosť, že týmto spôsobom je možné deloódovať len kódy násobky zostrojené z dvoch kódov sůčiniteľov. Pri väčšom počte kódov sůčiniteľov by značne vzrástla náročnosť tohto spôsobu, konkrétne kroku e),a nie je ani mámy spôsob riadenia rozhodovania pre väčší počet kódov súčiniteľov ako dva.Tieto nevýhody odstraňuje spôsob dekódovania samoopravných kódov násobkov podľa vynálezu zo SK 277719 B 6strojených z najmenej dvoch kódov BCH, pri ktorom dochádza k viacnásobnému dekódovaniu, ktorého podstata spočíva v tom, že pri dekódovaní prvej série kódov súčiniteľov kódu násobku sa vykonáva len oprava najviac tl chýb a pri dekódovaní ďalších sérií slov kódov súčiniteľov sa vykonávajú opravy chýb a označenie zístených kódových slov pri danom kroku neopraviteľných- zmazaní, mazanie je vlastne informáciou o nespoľahlivosti príslušných symbolov a túto informáciu je možné pri ďalších krokoch dekódovania využiť na zvýšenie samoopravnej schopnosti kódu a táto informácia sa využíva pri dekódovani nasledujúcich sérií slov, pri dekódovaní ktorých sa vykonáva oprava najviac ti chýb v jednom slove i -tej série alalebo oprava zmazaní. Po dekódovani všetkých sérií slov použitých v kode násobku po ukončení prvého cyklu sa pokračuje ďalším cyklom od prvej série slov, pričom sa vykonávajú opravy tl chýb a vyznačenia znamni slov, v ktorých sú odhalená v danom okamžiku neopraviteľné chyby. Pri dekódovani ďalších sérií kódových slov sa vykonávajú opravy chýb,vždy v i-tejsa upravujú kombinácie, v ktorých sa predpokladá, že je najviac ti chýb, a robia sa označenia tých kódových slov, v ktorých je odhalená v danom okamžiku neopraviteľna chyba ako nnazaných, alebo sa vykonáva oprava zmazani až pokiaľ je ukončené dekódovanie, pritom dekódovanie samoopravného kódu násobku pozostáva najmenej z dekódovania troch sérií.Spôsob dekódovania samoopravných kódov, podľa navrhovaného riešenia, umožňuje dosiahnuť väčšiu samoopravnú schopnosť kódu násobku pomstávajúeeho najmenej z dvoch kódov BCH ako spôsob opísaný v práci Random error and burst correction by interated codes. Kvantitatlvne boli porovnané účinky doteraz mámeho riešenia s navrhovaným riešením na konkrétnej realizácii programového dekodéra pre systém CD ROM,v ktorom je kód násobok realizovaný z dvoch RS kódov(RS kódy sú podmnožinou BCH kódov). Porovnávactm kritériom bola zvyšková bloková chybovosť P P počet chybných slov kódu násobku po dekódovanl /počet všetkých dekódovaných slov kódu násobkuDosiahnuté hodnoty veličiny P pre známy spôsob a pre spôsob navrhovaný, súznázomené v grafickej forme na obr.l, z ktorého je zrejmé, že navrhované riešenie nnožřirýe opraviť podstatne väčší počet kombinácií chýb, v ktorých počet chýb je väčší ako t.Spôsob dekódovania samoopravných kódov podľa navrhovaného riešenia umožňuje dosiahnut aspoň takú samoopravnú schopnosť kódu nasobku pozostavajůceho z dvoch kódov súčiniteľov ako spôsob oplsaný v DE 37 7223 A 1, pričom sa odstránia zbytočné kroky súvisiace s ošetxentm udalosti, ktoré môžu nastať so zanedbateľne malou pravdepodobnosťou v pripade, že v údajoch vstupujúcich do dekodéra sa vyskytujú nezávislé chyby s pravdepodobnosťou menšou ako rádovo 10, ako je to v mnohých prípadoch reálnych aplikácii, napr. v systémoch typu CD ROM. Spôsob podľa navrhovaného riešenia okrem toho v porovnaní s DE 37 7223 Al je možné použiť na dekódovanie údajov chránených voči chybám aj kódmi násobkami zostrojenýrni z viac ako dvoch kódov súčiniteľov.Vysvetlenie obrázkov na výkreseNa obrázku je znázornená hodnota P v závislosti od počtu chýb v kódovom slove t. pred dekódovaním, pričom čiarkovanou lcrivkou sú znázomené hodnoty P prenajbližšie známe riešenie a plnou čiarou sú znázomené hodnoty P pre navrhované riešenie.Spôsob dekódovania podľa navrhovaného riešenia bol využitý v programovom dekodere pre systém CD ROM, v ktorom je použitý tzv. kód EDC - kód násohok zostrojený z dvoch RS kódov, pričom kód Cl aj kód C 2 majú rovnakú kódovú wdialenosť dl d 2 3. V dekodére sa najprv dekóduje prvá séria kódových slov kódu Cl, pričom sa opravuje jedna chyba v slove kódu C 1 a potom sa dekóduje dmhá séria slov kódu C 2, pričom sa opravuje jedna chyba v kódovom slove kódu C 2, alebo sa vyznačuje mazanie, potom sa dekóduje opäť prvá séria slov kódu C 1, pričom sa opravuje jedna chyba v kódovom slove, alebo dve zmazaniu. Po dokončení dekódovania prvej série slov sa dekóduje druha séria slov, pričom sa vykonávajú opravy jednej chyby v kódovom slove, alebo sa vykonávajú opravy dvoch zmazaní, pokiaľ tieto boli vytvorené dekodérom prvej série slov, v prípade, že bolo vytvorené len jedno zmaIanie dekodér druhej série si vytvorí druhé zmazanie,pričom toto mazanie urobí v náhodne vybranom slove kódu C 1 z množiny tých kódových slov, v ktorých dekóder kódu Cl vykonal opravu, alebo pokiaľ dekóder kódu C 1 nevykonal žiadnu ďalšiu opravu z množiny ostatných slov nennazaných.l. Spôsob dekódovania samoopravných kódov násobkov zostrojených z najmenej dvoch samoopravných kódov BCH, pri ktorom dochádza k viacnásobnému dekódovanimvyznačujúci sa tým, že pri dekódovaní prvej serie slov kódov súčiniteľov kódu násobku sa vykonáva len oprava chýb a pri dekódovanl ďalších sérii kódov súčiniteľov sa vykonávajú opravy chýb a označenie zistených kódových slov pri danom kroku neopraviteľných - zmazruu a táto informácie. sa využíva pri dekódovaní nasledujúcej série kódov a po takomto dekódovani všetkých sérií kódov použitých v kode nasobku -cykle sa pokračuje znovu od prvej série kódov, pričom sa vykonávajú opravy a vyznačenie zmazani a táto informácia sa využíva pri dekódovani nasledujúcej série kódov súčiniteľov až do ukončenia dekódovania, pritom dekódovanie samoopravněho kódu násobku pozostáva najmenej z dekódovania troch2. Spôsob podľa bodu l, vyznačuj úci s a t ý m , že pri vykonávaní oprav sa vyznačuje tiež počet vykonávaných opráv v každom kódovom slove kódov súčiniteľov a táto informácia sa využíva pri dekódovaní nasledujúcej série kódov súčiniteľov.3. Spôsob podľa bodu 1, vyznačujúci s a tý m , že všetky syndromy všetkých kódov súčiniteľov, ktoré sú vypočítaná, sa uchovávajú v pamäti a pri každej vykonanej oprave sa moditikujú tak, aby zodpovedali aktuálnemu stavu po oprave a po každej sérii sa vykonáva kontrola hodnôt syndrómov, až kým sú všetky syndrómy nulové a všetky zmazania sú opravené, potom sa dekódovanie ukončí.4. Spôsob podľa bodu l a podľa bodu 2, v y značujúci sa tým, že všetky syndrómy všetkých kódov sťrčiniteľov, ktoré sú vypočítaná, sauchovávajú v pamati a pri každej vykonanej oprave sa modiñkujú tak, aby zodpovedali aktuálnemu stavu po oprave, a po každej sérii sa vykonáva kontrola hodnôt syndrómov, až kým sú všetky syndrómy nulové a všetky zmazaniu sú opravené, potom sa dekódovanie ukončí. 5

MPK / Značky

MPK: H03M 13/00

Značky: dvoch, kódov, násobkov, zostrojených, samoopravných, spôsob, najmenej, dekódovania

Odkaz

<a href="http://skpatents.com/5-277719-sposob-dekodovania-samoopravnych-kodov-nasobkov-zostrojenych-z-najmenej-dvoch-kodov-bch.html" rel="bookmark" title="Databáza patentov Slovenska">Spôsob dekódovania samoopravných kódov násobkov zostrojených z najmenej dvoch kódov BCH</a>

Podobne patenty