Zjišťování a korekce chyb

Zjišťování a korekce chyb představuje proces detekování chyb během přenosu nebo ukládání digitálních dat a jejic...


Zjišťování a korekce chyb představuje proces detekování chyb během přenosu nebo
ukládání digitálních dat a jejich automatického opravování. Obvykle zahrnuje
odesílání nebo ukládání dodatečných bitů dat, jejichž počet a využití závisí na
specifikovaném algoritmu.

Kdykoliv odesíláme data ať již jsou to audio signály přes telefonní linku,
datový tok videa nebo právní dokument někomu jinému, potřebujeme vědět, zda to,
co příjemce obdrží na druhém konci, je identické s tím, co jsme odesílali.
Podobně když ukládáme data na disk nebo na pásku, potřebujeme si být jisti, že
před zpětným načtením dat nedošlo k jejich změně. Přesná data jsou absolutní
nezbytností pro výpočty, uchovávání finančních záznamů, zpracování transakcí i
on-line obchodování. Ukládání a přenosy dat však bohužel vyžadují v reálném
světě působení fyzických entit elektronů, fotonů, atomů, molekul, kabelů,
kontaktů a podobně. To znamená, že vždy existuje určitá úroveň nejistoty; šum
je totiž přítomen v našem fyzickém vesmíru všude a mohl by změnit nebo poškodit
jakýkoliv bit dat.

Detekce chyb
Na začátku počítačové revoluce byly vyvinuty některé výkonné techniky, které
nejdříve detekovaly a posléze opravovaly chyby v datech. Nejzřetelnějším a
možná i nejméně účinným způsobem, jak zjistit, zda došlo ke změně dat, je
opakovat uložení nebo přenos každé jednotky dat několikrát a poté porovnat
kopie. Tato metoda je natolik neúčinná, že se pro detekci chyb nepoužívá
ačkoliv je totožná myšlenka použita u polí disků RAID-1 (zrcadlení disku).
Nejznámější metodou detekce chyb je využití takzvané parity, kdy je ke každému
bajtu dat přidán jeden extra bit, jemuž je přiřazena hodnota 1 nebo 0, obvykle
podle sudého nebo lichého počtu "jedničkových" bitů. Přijímací systém
vypočítává, jaký by měl být paritní bit, a pokud výsledky nesedí, ví, že
nejméně jeden bit byl změněn. Nepozná však, který z nich byl špatný. Je také
možné, že jsou data zcela v pořádku a že došlo k poškození paritního bitu.
Pokud dojde ke změně dvou bitů, změny se vynulují data budou chybná, ale
paritní bit nevydá signál o chybě. Dalšími dvěma zavedenými technikami detekce
chyb jsou kontrolní součet (použití všech bajtů celé zprávy, dokumentu nebo
programu a jejich sečtení do jednoho čísla) a metoda cyklické redundance (CRC),
která postupně používá skupiny bitů a dělení, nikoliv sčítání. Kontrolní součet
a CRC se vypočítávají před a po přenosu nebo duplikaci s následným porovnáním
obou výsledků. Nicméně, kontrolní součty CRC nedokáží ochránit integritu dat
před záměrnou změnou, protože algoritmy jsou známé a je možné provést takové
změny, které tyto metody nedokáží detekovat. Bezpečnějším způsobem je v tomto
případě používání hashovacích šifrovacích funkcí, jednosměrných matematických
operací, které používají tajné šifrovací klíče, jež zamezují provádění
nezjistitelných úprav.

Korekce chyb
Prostřednictvím výše uvedených technik lze nalézt chyby v datech, ale co pak?
Jednou cestou k nápravě je požádat odesílající stranu nebo zařízení, aby
poslalo data znova. Pokud ale data obsahují hodně chyb nebo je komunikační
trasa dlouhá, třeba přes polovinu naší hlučné zeměkoule, může opakovaný přenos
dat velmi podstatně snížit rychlost komunikace. Je tedy třeba použít systém,
který nalezne veškeré chyby a automaticky je opraví. Technicky jsme schopni
takové algoritmy (označované jako ECC kódy korekce chyb) vytvářet v jakémkoliv
stupni preciznosti, kterou potřebujeme, ale výměnou za zvýšení režie. Většinou
se tedy spokojíme s kódy, které dokáží detekovat a opravit chyby v jednom bitu
a detekovat, ale neopravit chyby ve dvou nebo více bitech. Dnes se ECC používá
v celé řadě různých zařízení, od CD přehrávačů k počítačům. Možná nejznámějším
je použití ve speciálních ECC RAM pro servery, kde jsou extra bity navrženy
přímo do čipů dynamických RAM.
V blízké budoucnosti by si technologie ECC mohly získat větší pozornost a
prosadit se na trhu bezdrátové komunikace. Obliba bezdrátové komunikace bude
totiž podle předpovědí analytiků dále růst nicméně šířka přenosového pásma a
průchodnost bezdrátových kanálů bude vždy podstatně menší než u kabelových
spojení.

Co se stane v procesu kontroly a korekce chyb, pokud dojde během přenosu ke
změně dvou bitů dat? V našem jednoduchém příkladě zaměníme bity 4 a 5. Protože
ECC nesouhlasí, došlo k chybě. Hodnota 011 naznačuje chybu v bitu 3, pokusíme
se tedy o jeho změnu, ale tím stále nezískáme správný triplet ECC. Tedy víme,
že máme neopravitelnou chybu ve dvou nebo více bitech. Proč obrázek používá
sedm datových bitů místo více obvyklých osmi? Použití osmi datových bitů s
pouze třemi ECC bity v tomto zjednodušeném procesu by vedlo k jedné ze dvou
situací: Buď by jeden datový bit nemohl být zahrnut do jednoho ze tří subsetů,
a v tomto případě bychom nemohli detekovat chybu v tomto bitu; nebo by byly dva
nebo více datových bitů zahrnuto do přesně stejných subsetů, a pokud by chyba
nastala v jednom z nich, mohli bychom detekovat přítomnost chyby, ale nemohli
bychom určit, který bit je chybný. ECC algoritmy používané ve skutečnosti jsou
mnohem složitější a efektivnější a berou v úvahu možnost, že by mohly být
nekorektní samotné bity ECC.
ECC přidává k datům několik paritních bitů. Výpočty jsou obvykle aplikovány na
kompletní slova (typicky 32 nebo 64 bitů), ne na jednotlivé bajty. Každý ECC
bit představuje paritu různého subsetu datových bitů a každý datový bit je
normálně zahrnut do více než jednoho ECC bitu. Tak můžeme detekovat
jednobitovou chybu, identifikovat problematický bit a opravit jej. Rovněž
můžeme detekovat, nikoliv ale opravit, chybu dvou bitů. Abychom viděli, jak ECC
pracuje ve velmi zjednodušené formě, podívejme se na sedmibitový kus binárních
dat na prvním obrázku. K němu jsme přidali tři další bity pro ECC data, každý
vypočtený jako paritní bit pro některou ze subsad (subsetů) sedmi bitů. Obrázek
1 ukazuje tři subsady se vzorovými daty a vypočtenými ECC bity.
Pro simulaci chyby změňme třetí bit zleva z 1 na 0. Nyní přijatá data vypadají
jako na obrázku 2, přičemž rozdíly jsou označené červeně.
Vidíme, že vypočtené ECC bity nesedí. Víme tedy, že došlo k chybě. Protože ECC
1 je v pořádku, chyba nemůže být v bitech 1, 2, 4 nebo 5. Tak nám zbývají pouze
bity 3, 6 a 7. Jak můžeme určit, který je chybný? Tři subsety datových bitů
použitých pro vytvoření ECC bitů v tomto příkladu byly vybrány tak, že výměna
jakéhokoliv jednoho datového bitu vytvoří jinou hodnotu ECC než výměna
jakékoliv jiného datového bitu. Pokud budeme předpokládat, že chyba je v bitu
7, můžeme jej změnit a přepočítat ECC hodnoty na 110. Protože to nesedí s
přijatou hodnotou 100, zkusíme bit 6, který vrátí 101, a tedy také nesedí.
Zůstává nám tak bit 3; změnou jeho hodnoty dostaneme správné bity ECC, a
potvrdíme tak správnost vypočtených dat.









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.