Zpracování multimediálních dat

VŠB - Technická univerzita Ostrava Fakulta elektrotechniky a informatiky Katedra informatiky

Zpracování multimediálních dat

Semestrální práce Cyklické kódy

2007

Petr Kopřiva, kop173

Obsah : 1. ÚVOD .................................................................................................................................. 1 2. KÓDOVÁNÍ ......................................................................................................................... 2 3. CYKLICKÉ KÓDOVÁNÍ...................................................................................................... 3 3.1 3.2 3.3 3.4 3.5 3.6 3.7

LINEÁRNÍ KÓDOVÁNÍ ................................................................................................................ 3 PRINCIP CYKLICKÉHO KÓDOVÁNÍ.............................................................................................. 3 HARDWAROVÁ REALIZACE CYKLICKÝCH KÓDŮ ........................................................................ 4 SOFTWAROVÁ REALIZACE CYKLICKÝCH KÓDŮ ......................................................................... 5 IMPLEMENTACE CRC-32 .......................................................................................................... 6 CHYBOVÉ CHARAKTERISTIKY CRC .......................................................................................... 7 CYKLICKÉ KÓDOVÁNÍ VS. POČÍTAČOVÁ TECHNIKA ................................................................... 8

4. SHRNUTÍ........................................................................................................................... 10

Úvod

1.

Petr Kopřiva

Úvod

Cílem tohoto referátu by mělo být seznámení čtenářů s pojmem cyklické kódy. K čemu a proč se tyto kódy vlastně používají? Na úvod jen připomeňme, že se těmto kódům také říká CRC kódy. Ano pod tímto názvem jsou známější a používají se výhradně jako tzv. detekční kódy, které mají za úkol odpovědět na otázku „Jsou přenesená data poškozená, či nikoli?". Odpověď poskytovaná detekčními kódy není nikdy absolutně spolehlivá, protože každému detekčnímu kódu může „něco uniknout". Nejlépe jsou na tom ale právě tyto CRC kódy, jejichž spolehlivost se ideálnímu stavu blíží nejvíce. Analogicky je základní princip jejich využití takový, že odesilatel aplikuje na odesílaná data algoritmus, na kterém je dohodnut s příjemcem, a který vyplývá z povahy detekčního kódu. Výsledkem je pak zabezpečovací údaj, který odesilatel „přišpendlí" k původním datům, a odešle je příjemci. Ten aplikuje na přijatá data přesně stejný algoritmus, a výsledek porovná se zabezpečovacím údajem, který obdržel od odesilatele. Jde-li například o zabezpečení kontrolním součtem, spočívá zmíněný algoritmus v prostém sečtení jednotlivých datových bytů či slov, chápaných pro tento účel jako čísla, a zabezpečovacím údajem je pak výsledný součet. CRC kódy jsou podtřídou kódů lineárních a než si o nich něco řekneme, podíváme se v dalších kapitolách na to co je to vůbec pojem kód a kódování dat, jaké podmínky musí kódování splňovat. Dále si upřesníme jak se CRC kódy počítají, podíváme se na hardwarovou a softwarovou realizaci těchto kódů, ukážeme si vztah cyklických kódů k výpočetní technice a naznačíme, jak by mohla vypadat jejich implementace.

-1-

Kódování

2.

Petr Kopřiva

Kódování

Každý z Vás se určitě už setkal s pojmem kódování dat. Představme si případ, kdy potřebujeme data zakódovat. Například při jejich přenosu, kdy si tyto data někdo odchytí a neoprávněně se snaží zjistit jejich obsah. Existuje mnoho algoritmů, které toto dokáží různými způsoby realizovat. Kódy můžeme rozdělit do tří základních skupin na nejkratší (optimální) kódy, bezpečnostní kódy (detekční kódy, samoopravovací kódy) a na kódy speciální (čárové kódy, alfanumerické kódy, číselné kódy). Jednoduchý princip kódování dat je zachycen na obrázku 1. Kódování dat má ale použití také v dalších velmi důležitých odvětvích telekomunikační a výpočetní techniky. Jedním takovým odvětvím je komprese dat. Můžeme říct, že komprese dat je podtřídou kódování dat. Principem komprese dat je, že se hledá nejkratší kód, který by zabral méně místa, než data původní. Tento referát se ale bude zabývat cyklickými kódy (neboli CRC kódy), které spadají do skupiny kódů bezpečnostních a podtřídy detekčních. Nejdříve si ale uveďme definici toho, co to kódování je, a jaké musí splňovat požadavky.

(S , C , f ) ,

Kód K je trojice

kde S je konečná množina zdrojových jednotek zvaná

zdrojová abeceda, C je množina kódových jednotek zvaná kódová abeceda a

f je zobrazení

+

S → C . Zobrazení f přiřazuje každé kódové jednotce z S právě jedno kódové slovo (sekvenci +

kódových jednotek) z C . Zobrazení f musí být injektivní. To znamená, že nikdy nezobrazuje dvě různé kódové jednotky na stejná kódová slova. Většinou u kódování vyžadujeme tzv., jednoznačnost dekódování. Kód K je jednoznačně dekódovatelný, právě když pro každý řetězec

Y ∈ C + existuje nejvýše jeden řetězec X ∈ S

takový, že platí f ( X ) ∈ Y . Nyní se ale už pojďme podívat na vybraný druh kódování, a to kódování cyklické.

Obrázek 1 - Princip kódování dat

-2-

Cyklické kódování – CRC kódy

Petr Kopřiva

3.

Cyklické kódování

3.1

Lineární kódování

Již v předchozí části jsme se zmínili, že cyklické kódy patří do skupiny kódů lineárních. Dříve než se pustíme do detailního objasnění cyklických kódů, připomeňme si ve zkratce, co jsou to kódy lineární. Kódové slovo chápeme jako řádkový vektor v = [0 0 1]. Lineární kombinací libovolného počtu kódových slov vznikne opět kódové slovo (odtud pojem lineární kódování). Kód se nejčastěji popisuje pomocí tzv. generující matice, kterou tvoří báze kódů :

1  0 G= 0  0  3.2

0 0 1  1 0 1 ; v = z ⋅G . 0 1 1  0 0 1

Princip cyklického kódování

Analogicky jako u kódů lineárních také u kódu cyklických vznikne cyklickým posunem znaků kódového slova opět slovo kódové. Kromě generující matice můžou být popsány generujícím polynomem. My se v tomto referátu omezíme právě na tento generující polynom. Realizace cyklického kódování můžeme shrnout do těchto bodů : a) Slovo dělíme generujícím polynomem G (viz tabulka 1) b) Určíme zbytek po dělení c) Zbytek připojíme za informační slovo d) Celé kódové slovo je nyní dělitelné generujícím polynomem beze zbytku Počet kontrolních bitů

Označení

Generující polynom

8

LRCC-8

z +1

12

CRC-12

z 12 + z 11 + z 3 + z 2 + z + 1

16

LCRC-16

z 16 + 1

16

CRC-16

z 16 + z 15 + z 2 + 1

16

CRC-16 reverzní

16

SDLC

16

SDLC reverzní

z 16 + z 14 + z + 1 z 16 + z 12 + z 5 + 1 z 16 + z 11 + z 4 + 1

8

z 32 + z 26 + z 23 + z 22 + z 16 + 32

CRC-32

z 12 + z 11 + z 10 + z 8 + z 7 + z5 + z4 + z2 + z +1 Tabulka 1 - Typy CRC kódů

-3-

použití Kontrolní Byte je součet datových Byte modulo2 Používá se pro šestibitové znaky Kontrolní součet dvojic Byte modulo2 Binární synchronní protokol Linkový protokol IBM

ETHERNET, HDCL, ZMODEM

Cyklické kódování – CRC kódy

Petr Kopřiva

Pod označením CRC kódy (Cyclic Redundancy Checks) mají tyto kódy velmi velké využití. CRC kódy jsou asi nejznámější kódy. Dříve se používaly hlavně proto, že jejich hardwarová realizace byla velmi rychlá a jednoduchá. Přestože dnes jsou známé jiné kódy, které je možno programovat stejně tak dobře firmwarově i softwarově, jsou CRC kódy doposud velmi populární. Tradiční hardwarová implementace CRC se provádí jednoduše realizovatelnými lineárními zpětnovazebními posuvnými registry, které zpracovávají informaci po jednotlivých bitech. To je vhodné zejména u přenosu dat. V softwarové implementaci je vhodnější pracovat s daty po bytech. Ukážeme si obě varianty realizace CRC kódů.

3.3

Hardwarová realizace cyklických kódů Pro

jednoduchost

uvažujme

dále

konkrétní

CRC–16

s generujícím

polynomem

g ( x ) = x + x + x + 1 s r = 16 kontrolními bity. Všimněme si, že posun zleva doprava 16

15

2

v registru znamená násobení obsahu registru proměnnou x a zpětná vazba zajišťuje modulování polynomem g(x). Opravdu, je-li

c0 + c1 x + ... + c15 x15 polynom odpovídající původnímu obsahu

registru, potom po posunu doprava o jednu pozici dostáváme podle obrázku 2 nový obsah registru

(

v( x ) = c15 + c0 x + (c1 + c15 )x 2 + c 2 x 3 ... + c13 x14 + (c14 + c15 )x15 . Tento výraz je roven

)

(

)

x ⋅ c0 + c1 x + ... + c14 x14 + c15 x 15 + c15 x16 + x15 + x 2 + 1 = x ⋅ c( x ) mod g ( x ) , což jsme chtěli ověřit. Přidáme-li datové bity

d k −1 , d k − 2 , d1 , d 0 do zpětné vazby podle obrázku 2, vynásobí se

r

vlastně mocninou x , neboť to odpovídá jejich vstupu na poslední pozici (r=16) registru. V dalších krocích registru se datové bity v jednotlivých buňkách registru násobí postupně vždy proměnnou x, a to tolikrát, kolikrát se s ním registr posune. Zároveň se však výsledek moduluje polynomem g(x), což automaticky provádí zpětná vazba. Jestliže na počátku registr vynulujeme, pak tedy po průchodu posledního datového bitu v registru zůstává

d0

d 0 x r + d 1 x r +1 + ... + d k −1 x r + k −1 mod g ( x ) . Tento výraz není nic jiného než

x r d ( x ) mod g ( x ) , tj. přímo CRC podle definice (viz. Softwarová realizace cyklických kódů). CRC se pak z registru jenom přečte a připojí za informační bity. Kódování je tedy velmi jednoduché. Jak jsme viděli, délka informační části může být dlouhá dle libosti. Ovlivňuje se jí ovšem schopnost detekce o doba trvání výpočtu CRC. Výpočet CRC-16 od posloupnosti (10000101) je uveden v příkladu 1 v části Softwarová realizace cyklických kódů.

-4-

Cyklické kódování – CRC kódy

Petr Kopřiva

Obrázek 2 - Hardwarová realizace CRC kódů

3.4

Softwarová realizace cyklických kódů

Při softwarové realizaci je možno přesně kopírovat postup hardwarový, nebo využít triku, který nám umožní pracovat přímo s byty (eventuálně s wordy nebo slovy obecné délky). Budeme pracovat v binárním poli , které má pouze dva prvky : 0 a 1. Operace sčítání je definována jako XOR a operace násobení jako AND. Dělení je jednoduché, neboť je definováno jen pro jedničku a to je identita. Binární polynom je potom nám známý tradiční polynom, ale s binárními koeficienty. Každou

posloupnost

bitů

(a0 , a1 ,..., a n )

můžeme

ztotožnit

s polynomem

a ( x ) = a 0 x 0 + a1 x + ... + a n x n . Práce s binárními polynomy je stejná jak s polynomy reálnými včetně dělení a násobení, s tím rozdílem, že s koeficienty pracujeme v binárním poli (bude ukázáno na příkladu). Data o k bitech (informační část kódu), ke kterým připočítáme CRC, označme

d = (d 0 , d 1 , d k −1 ) a jim odpovídající polynom

vypočítaný CRC o r bitech označíme

d ( x ) = d 0 + d 1 x + ... + d k −1 x k −1 . K nim

c = CRC (d ) = (c0 , c1 ,..., c r −1 ) a jemu odpovídající polynom

c( x ) = CRC (d (x )) = c0 + c1 x + ... + c r −1 x r −1 (pro jednoduchost CRC nazývejme jen kontrolní část kódu). Výsledné kódové slovo je pak

v = (v0 , v1 ,..., v n ) = (c0 , c1 ,..., c r −1 , d 0 , d 1 ,..., d k −1 ) ,

n = k + r je celková délka kódu. Tento způsob kódování má tu výhodu, že vlastní informace je v něm obsažena v nezměněné podobě a může proto například odcházet do linky (bit d k −1 jako

kde

první). Při vysílání se však postupně dá vypočítávat CRC. Po vyslání celé informační části je CRC již vypočten a může se okamžitě vyslat nebo uložit za ní. Tím pádem také dekódování probíhá stejně – přijímá se informační část, průběžně se vypočítává CRC, a po přijetí posledního datového bitu se vypočtený CRC porovnává s přijatým.

-5-

Cyklické kódování – CRC kódy

Petr Kopřiva

Víme, že k danému r-bitovému CRC existuje generující polynom každé kódové slovo je jakožto polynomem jeho násobkem :

g ( x ) stupně r tak, že

v( x ) = 0 mod g ( x ) . Generující

polynomy u nejznámějších CRC jsou shrnuty v tabulce 1 (viz. předchozí kapitola). Vyjádříme-li si kódové

v( x ) =c 0 +c1 x + ... + c r −1 x r −1 + d 0 x r + d1 x r +1 + ... + d r + k −1 x r + k −1

slovo

ve

tvaru

v( x ) = c( x ) + x r d ( x ) mod g ( x ) , dostaneme odtud, že c( x ) + x r d ( x ) = 0 mod g ( x ), tj., že

c( x ) = x r d ( x ) mod g ( x ) .

CRC tedy můžeme počítat jako zbytek po dělení výrazu

x r d ( x ) generujícím polynomem

g ( x ) . A to se právě výhodně realizuje hardwarově lineárním posuvným registrem, viz. obrázek 2. Příklad 1 : Výpočet CRC -16 dat (10000101) Řešení : Konstrukce polynomu

(

d ( x ) = 1x 0 + 0 x + 0 x 2 + 0 x 3 + 0 x 4 + 1x 5 + 0 x 6 + 1x 7

Vypočtěme

x r d ( x ) = x16 ⋅ 1x 0 + 0 x + 0 x 2 + 0 x 3 + 0 x 4 + 1x 5 + 0 x 6 + 1x 7

Vypočtěme

c( x ) = x r d ( x ) mod g ( x ) =

)

x16 + x 21 + x 23 mod x 16 + x15 + x 2 + 1 = x15 + x 9 + x 8 + x 7 + x 6 + x 2 + 1

(x + x + x ) : (x + x − (x + x + x + x ) 23

21

23

16

22

16

9

15

)

+ x2 +1 = x7 + x6 +1

7

−−−−−−−−−−−−−−− x 22 + x 21 + x 16 + x 9 + x 7

(

− x 22 + x 21 + x 8 + x 6

)

−−−−−−−−−−−−−−− x16 + x 9 + x 8 + x 7 + x 6

(

)

− x 16 + x 15 + x 2 + 1

−−−−−−−−−−−−−−− x15 + x 9 + x 8 + x 7 + x 6 + x 2 + 1 = zbytek ⇒ 1x 0 + 0 x 1 + 1x 2 + 0 x 3 + 0 x 4 + 0 x 5 + + 1x 6 + 1x 7 + 1x 8 + 1x 9 + 0 x10 + 0 x11 + 0 x12 + 0 x13 + 0 x14 + 1x15 je polynomem c( x ) . CRC

c = (c0 ,..., c15 ) je tedy (1010001111000001) a celé kódové slovo má tedy

tvar

v = (c 0 ,..., c15 , d 0 ,..., d 7 ) : (101000111100000110000101).

3.5

Implementace CRC-32

Výpočet 32-bitového CRC je implementován podle rotace průběžného zbytku a odečítáním kontrolního polynomu. Aby se však výpočet urychlil, a nemusel se vstupní datový tok zpracovávat po bitech, využívá se toho, že je možné vypočítat 32 bitovou konstantu, kterou je třeba XOROVAT průběžný zbytek v případe, že horních 8bitu má určitou hodnotu. Výpočet této konstanty je velmi jednoduchý, stačí pouze předpokládat, že kromě nejvyššího bytu obsahuje

-6-

Cyklické kódování – CRC kódy

Petr Kopřiva

zpráva samé nuly, konkrétně 3 byty nul. Konstanty je nutné postupně spočítat pro všech 256 kombinací horních osmi bytů. Tyto hodnoty se předpočítají pouze jedenkrát na začátku programu a uloží do lookup tabulky. Algoritmus výpočtu CRC (kódování i dekódování) se provádí podle následujícího postupu. Na počátku se průběžný zbytek inicializuje nulovou hodnotou a pro každý byte kódovaného řetězce se provádí následující posloupnost operací. Určí se hodnota nejvyššího bytu průběžného zbytku a průběžný zbytek se posune o 8 bitů doleva. Na nejnižších 8 bitu průběžného zbytku se umístí byte načtený z kódovaného řetězce a průběžný zbytek se VYXORUJE hodnotou z lookup tabulky, jejíž index určuje zapamatovaná hodnota nejvyššího bytu. Příklad zdrojového kódu :

crc = 0; for (i=0; i < len; i++) { j = (crc >> 24) & 0xFF; crc = (crc << 8) | data[i]; crc = crc ^ tabulka[j]; }

//nejvyšší byt (index do tabulky) //posun CRC doleva + nový byt

Ze zadání je zřejmé, že je nutné vstupní soubor zpracovávat po osmi bytech. Kódování se provádí tak, že za načtených osm bytu se doplní 4 byty nul a z těchto 12 bytu se vypočte CRC. Hodnotou vypočteného CRC, která má velikost 4 byty, se přepíši čtyři byty nul a všech 12 bytu se uloží do výstupního souboru. Dekódování se realizuje po blocích délky 12 bytu. Nad těmito bloky se spočítá CRC, které musí být nyní rovno 0, neboť původní 8 bytová zpráva byla doplněna o 4 byty zbytku. Pokud je vypočtené CRC různé od nuly, zkouší se postupnou změnou každého bitu na opačnou hodnotu opravit jednochybu. Tato změna se provádí pro každý z 96 bitu. Pokud se v některém případě podaří vypočíst hodnotu CRC rovnou nule, byla detekována chyba, kterou je možné opravit a do výstupního souboru se zapíše správný výstup. V případě, že se nepodařilo testováním jednochybu nalézt, program končí vypsáním chybové hlášky na standardní chybový výstup. Protože se soubor zpracovává po blocích, tak fakt, že nebyl načtený celý blok nám říká, že byl dosažen konec souboru. Nemusí proto být v souboru být uložena jeho délka, neboť v případě kódování očekáváme velikost souboru dělitelnou osmi a v případě dekódování velikost dělitelnou dvanácti. Pokud není velikost dekódovaného souboru dělitelná 12, znamená to, že ani velikost vstupního kódovaného souboru nebyla dělitelná osmi.

3.6

Chybové charakteristiky CRC

Schopnosti detekovat chyby jsou u různých součtů CRC podobné a lze je jednoduše vyjádřit pomocí počtu kontrolních bitů r. Všechny stoprocentně detekují libovolnou shlukovou chybu o délce menší nebo rovno r (je to chyba, jejíž krajní bity uvozují, včetně sebe, r-bitový řetězec dat). Ze shlukových chyb, které mají délku

r + 1 , je jich jen 1 : 2 r +1 nedetekovatelných a

ze shlukových chyb o délce větších než r + 1 CRC nedetekuje jen jednu z 2 . U konkrétních CRC lze pak vyvozovat i podrobnější závěry. Například CRC-16, uvažujeme - li délku bloku dat menší než 32751 bitů, detekuje všechny jednoduché, dvojité a trojité chyby a všechny chyby o lichém počtu chybových bitů. Velmi dobrá schopnost detekovat r

-7-

Cyklické kódování – CRC kódy

Petr Kopřiva

chyby, výhodná hardwarová realizace a teoretická rozpracovanost, umožňující poměrně přesně stanovit detekční vlastnosti, jsou důvodem širokého využívání CRC. Ale přes všechny uvedené pozitivní vlastnosti CRC je jasné, že žádný instrukční soubor známých mikroprocesorů neobsahuje instrukce pro přímou realizaci lineárních posuvných registrů se zpětnou vazbou. Pokud budeme postaveni před úlohu značně urychlit výpočet kódu oproti CRC, budeme se pochopitelně ohlížet zejména po kódech rychle realizovatelných jednoduchými instrukcemi našeho mikroprocesoru. Aritmetické instrukce jsou proto nejvhodnějšími kandidáty na toto použití. Jeden takový kód vznikl koncem 70. let a byl navržen Johnem G. Fletcherem z Lawrence Livermore Laboratory v Kalifornii. Má o málo horší detekční vlastnosti než CRC, ale jeho realizace může být až o jeden řád rychlejší!! Kód se obecně nazývá Fletcherův kontrolní součet (FKS), je to ale celá třída kódů, majících za parametry aritmetický modul a počet kontrolních bytů. Jen ještě jako zajímavost, jeho poslední verze (modul M=255, a počet kontrolních bytů R=2) byla schválena pro použití v transportní vrstvě síťového protokolu ISO. Přestože je standardem a má velmi dobré vlastnosti, není tak dobře znám a používán. To je důvod, proč stojí za to, na něho v tomto referátu upozornit.

3.7

Cyklické kódování vs. počítačová technika

Svět počítačů, počítačových komunikací a digitálních přenosů obecně vděčí za svou existenci a za své fungování výsledkům mnoha vědních oborů - nejen fyziky, která stojí za celou technologií výroby součástek, ze kterých jsou dnešní počítače a další aktivní prvky postaveny. Stejně tak vděčí digitální svět za mnohé například i matematice. Velmi pěkným příkladem zde může být používání tzv. cyklických zabezpečovacích kódů (anglicky: Cyclic Redundancy Checks, zkratkou CRC). Jde o kódy, používané k zabezpečení dat při jejich přenosu (nebo i při jakémkoli jejich „skladování"), a mají za úkol umožnit detekci případných chyb v těchto datech. Jsou to tedy kódy detekční, podobně jako tzv. parita či kontrolních součty. Analogický je základní princip jejich využití takový, že odesilatel aplikuje na odesílaná data algoritmus, na kterém je dohodnut s příjemcem, a který vyplývá z povahy detekčního kódu. Výsledkem je pak zabezpečovací údaj, který odesilatel „přišpendlí" k původním datům, a odešle je příjemci. Ten aplikuje na přijatá data přesně stejný algoritmus, a výsledek porovná se zabezpečovacím údajem, který obdržel od odesilatele. Jde-li například o zabezpečení kontrolním součtem, spočívá zmíněný algoritmus v prostém sečtení jednotlivých datových bytů či slov, chápaných pro tento účel jako čísla, a zabezpečovacím údajem je pak výsledný součet. Spolehlivost zabezpečení pomocí kontrolních součtů ovšem není příliš veliká, a pro mnohé účely nedostatečná. Dostatečnou spolehlivost nabízí až výše avizované cyklické kódy (CRC) - například zabezpečovací údaj, generovaný podle této metody v nejčastěji používaném rozsahu 16 bitů, umožňuje příjemci rozpoznat všechny shluky chybných bitů se stoprocentní jistotou, shluky délky 17 bitů s pravděpodobností 99,9968%, a ostatní chyby s pravděpodobností 99,9984%. Nezní to jako fantazie, nebo dokonce jako nemožnost? Pokud nechcete mému tvrzení věřit a chcete si sami dokázat jeho pravdivost, budete k tomu potřebovat velmi silný matematický aparát, konkrétně aparát algebry, zabývající se okruhy polynomů nad tělesem dimenze 2. Za fungováním cyklických kódů totiž stojí opravdu pokročilá matematika. Pokud ale nejsou tyto partie zrovna vaším koníčkem, vůbec to nevadí. K praktickému používání detekčních mechanismů na bázi cyklických kódů žádný matematický aparát nepotřebujete. Potřebujete pouze velmi konkrétní a ryze praktický návod na to, jak z přenášených

-8-

Cyklické kódování – CRC kódy

Petr Kopřiva

dat vyrobit onen zabezpečovací údaj, který pak k datům připojíte a odešlete směrem k příjemci (výpočet je popsáno v kapitole 3.4). Ten pak zase potřebuje vědět, co má s přijatými daty a zabezpečovacím údajem udělat, aby si mohl odvodit zda jsou poškozená, nebo s hodně velkou pravděpodobností nepoškozená. V obou případech přitom stačí „prohnat" přenášená data přímo triviálním logickým obvodem, který na straně odesílatele vyrobí zabezpečovací údaj, a na straně příjemce řekne ano či ne. Pokud by vás ale přeci jen zajímalo, na jakém principu zabezpečení cyklickými kódy pracuje, pak se pokusím o maximální možné zjednodušení: odesilatel si data určená k odeslání na chvíli představí jako jedno velké číslo (což není tak těžké, vždyť jde ve své podstatě jen o posloupnost nul a jedniček). Toto číslo pak vydělí jiným číslem, na kterém je s příjemcem domluven. Podíl, který mu vyjde, okamžitě zapomene, ale využije zbytek po dělení - ten připojí k vlastním datům jako zabezpečující údaj, a vše pak odešle. Příjemce pak opakuje stejný postup a dívá se, zda dostal stejný zbytek. Podstatnou roli zde přitom hraje číslo (dělitel), kterým se přenášená data dělí, a na kterém musí být obě strany předem domluveny - toto číslo samozřejmě nemůže být ledajaké (z předchozích částí víme, že jde o generující polynom g(x)). Jeho konkrétní hodnotu lze nalézt jen s využitím onoho silného matematického aparátu, a tentýž aparát je pak třeba i k důkazu toho, že s tímto dělitelem vše funguje s onou výše uvedenou báječnou spolehlivostí, velmi se blížící stu procent. Z konkrétní hodnoty tohoto čísla-dělitele (ve skutečnosti polynomu, resp. tzv. vytvářející mnohočlenu, ale při našem maximálním zjednodušení pouhého čísla) pak přímo vyplývá funkce i struktura jednoduchého (ba přímo triviálního obvodu), který obě strany používají pro praktické generování zabezpečovacích údajů a kontrolu správnosti přenesených dat.

-9-

Cyklické kódování – CRC kódy

4.

Petr Kopřiva

Shrnutí

V tomto referátu jsme se dozvěděli, co jsou to CRC kódy, že spadají do skupiny bezpečnostních detekčních kódů. Ukázali jsme si jednoducho hardwarovou realizaci těchto kódů, která spočívá v lineárním posuvném registru se zpětnou vazbou. Ukázali jsem si, že výpočet takového CRC kódu je jednoduchý, stačí výraz

x r d ( x ) modulovat generujícím polynomem

g ( x ) . Takto dostaneme CRC část kódu c( x ) , kterou připojíme před informační slovo. Výsledné slovo má potom podobu

v = (c0 ,..., c r −1 , d 0 ,..., d k −1 ) . Obecně není jedno, jakým polynomem

g ( x ) modulujeme polynom x r d ( x ) . Pro názornost jsou nejpoužívanější generující polynomy shrnuty v tabulce 1. Pokud by někoho zajímalo ověření správnosti těchto polynomů, bude k tomu potřebovat velmi silný matematický aparát, konkrétně aparát algebry, zabývající se okruhy polynomů nad tělesem dimenze 2. Pro naší potřebu stačí vědět, že generující polynom v nejčastěji používaném rozsahu 16 bitů, umožňuje příjemci rozpoznat všechny shluky chybných bitů se stoprocentní jistotou. Ukázali jsem si také příklad implementace 32-bitového CRC kódu (CRC-32). Ale přes všechny uvedené pozitivní vlastnosti CRC je jasné, že žádný instrukční soubor známých mikroprocesorů neobsahuje instrukce pro přímou realizaci lineárních posuvných registrů se zpětnou vazbou. Tímto bych skončil tento referát o CRC kódech, doufám, že pro Vás čtenáře byl něčím užitečný, a že jste se dozvěděli informace, které jste potřebovali.

- 10 -