Compress Cryptography Recovery Sortings Ostatni
VE VYSTAVBE!

Principy samoopravnych algoritmu (Recovery)


Funkce OR
	xy z=xORy
	---------
	00 0     
	01 1     
	10 1     
	11 0     


Kontrolni, synchronizacni a opravne kody (kody kontroly obsahu)
--------------------------


Kontrolni kod
-------------

Synchronizacni kod
------------------
Kvuli ztrate synchronizace.


Rec - Samoopravny kod (Recovery data)
---------------------

	Kod, jehoz pouzitim je mozne nahradit uplne jeden z chybejicich disku.
	Nevyhodou je, ze mame o disk navic.
	Pouziva se pro 2-3 disky, casti dat.
	Data se rozdeli na 3 (nejcasteji) stejne casti a k nim se vytvori 4ta cast s opravnym kodem.
	Pouziva se v odmene treba u CD.
	(hadam, ze data jsou ukladana po blocich vsechny disk1, pak disk2, 3 a 4)
	(navic bych pridal jeste disk 5, ktery by byl opravny pro vsechny 4 disky, pro jistotu)
	(nebo lepsi je prokladat to na stridacku a promichat nejakym pravidlem vsechny disky...)

Priklad:

	Vytvoreni:
	----------

	101101 a - disk 1 (data)
	001011 b - disk 2 (data)
	100100 c - disk 3 (data)
	------
	000010 o - disk 4 (recovery data)
	o = a OR b OR c (o ... opravny) 

	abc OR
	------
	000 0
	001 1
	010 1
	011 0
	100 1
	101 0
	110 0
	111 1


	Pouziti:
	--------

	b is bad (disk b je vadny) ... CheckSum
	b = a OR c OR o

	101101 a
	100100 c
	000010 o
	------
	001011 b





CheckSum (Check summary) - Kontrolni soucet
------------------------

	Je to udaj, ktery se prida k datovym udajum pro overeni platnosti dat.
	Opet data nabyva na velikosti

	Paritni kod  (Parity code)
	-----------

	Nejjednodussi kontrola
	Kontroluje jaky je pocet 1 nebo 0 pouhym sectenim funkci OR nebo jinym rychlejsim zpusobem.

	111010010011 - 1
	(lichy pocet jednicek - kod 1, sudy - kod 0)
	(a1 OR a2 OR a3 OR a4 ... = 1)


	Parita bytu (Parity bytes)
	-----------

	211 22 3 45 0 67 92 - x
	x = a OR b OR c ...	(jako Rec)
	(x = 01001000 b = 201 = 'D')


	(Parita) bytu ((Parity) bytes)
	-------------

	211 22 3 45 0 67 92 - 184
	x = Suma (Data) <0-255> = 211+22+3+45+0+67+92 = 440(-256) = 184

	x typu Byte, max hodnota je 255, prictenim dalsiho cisla se zacina od nuly
	 (x = 244 + 44 = 255 (255 max) + 33 = 256 (0) + 32 = 32)
	Byte = 8 bite = 0-255


	Soucet bytu (Suma bytes)
	-----------

	211 22 3 45 0 67 92 - 2 1 184
	x = Suma (Data) <0-xxx> = 211+22+3+45+0+67+92 = 440
	440 = 1x256+184 = 1 184 (2 byte code)


	Soucty souctu, parit... (Suma sumas, all...)
	-----------------------

	1110-1 1001-0 0011-0 -  1
	     1      0      0 parity 4-bite blocks (parita)
				1 parity of parites (parita z parit)
	
	211 22 -233  3 45 -48  0 67 -67  - 184
		233	   48	     67  - 184




je dobr' si vsimnout komutativity a asociativity: 

a xor b = b xor a
(a xor b) xor c = a xor (b xor c)

zajímavá vlastnost je tak': 
    
a xor b xor b = a
a xor b xor a = b
a xor 0 = a
a xor a = 0




CRC-16bit, CRC-32bit; mozná i CRC-64bit nebo CRC-128bit.

Pro nase úcely si ukázeme vypocet CRC-4bitov'ho. Jedinym parametrem, kterym muzeme CRC "nastelovat", je tzv. generacní polynom (dále jen GP). Predstavte si ho jako 4bitov' císlo (4bitov', protoze je 4bitov' CRC. Pro 32bitov' CRC by byl GP 32bitovy). Pouzitím jin'ho GP muzeme ovlivnit vhodnost CRC pro urcit' typy chyb.


Takze:

    
    GP = 1001

A data, pro která budeme CRC pocítat:

    
    101101110


Nejprve k datum pridáme nakonec tolik nul, kolik je d'lka GP - resp. kolika bytov' je pocítan' CRC. V nasem prípade 4: 

    
    1011011100000
             ^^^^
    
Dále vezmeme GP a ruzne rotovany doleva ho xorujeme na data tak dlouho, az je vynulujeme:


    1011011100000   0010011100000   0000001100000
    1001              1001                1001
xor -------------   -------------   -------------
    0010011100000   0000001100000   0000000101000



    0000000101000
           1001
xor -------------
    0000000001100
             ^^^^


Po t'to operaci si vsimnete, ze pridan' nuly se nám zmenily na 1100, coz je kyzeny vysledek, tedy 4bitov' CRC.

Ke zpráve posílan' do USA tedy pridáme CRC=1100:


    1011011101100
             ^^^^
V USA pak mají dve moznosti. První je celkem zrejmá, úplne stejnym zpusobem, jako jsem popsal vyse, spocítají CRC znovu a porovnají, zda se CRC shoduje. Zajímavejsí postup overení CRC - v USA spocítají CRC pro celou takto doslou posloupnost znovu a mela by jim vyjít 0:


    1011011101100
    1001
      1001
          1001
           1001
xor -------------
    0000000000000

V tuto chvíli bude rozhodne dobr' si rozmyslet, proc tomu tak vlastne je. Momentálne me nenapadá zádny zpusob, jak tuto vlastnost CRC jednoduse vysvetlit, takze to nechám na vás. Uvaha to zase az tak obtízná není a myslím, ze byste si to meli byt schopni oduvodnit sami. Bude-li nejaky probl'm, napísu o tom dalsí clánek :-)

Je velmi dulezit' si uvedomit, ze je úplne jedno, v jak'm poradí budete GP xorovat. Algoritmus, ktery bude ve skutecnosti CRC pocítat, to samozrejme bude delat postupne. Obecne nám ale nic nebrání to udelat treba takto:


    1011011101100
    1001
          1001
      1001
           1001
xor -------------
    0000000000000




Jak je to s chybou:
Takze, predpokládejme, ze data prisla porusená a ze chybovy vektor je:

    
    0000000100000

Zpráva doslá do USA tedy bude:

    
    1011011101100
    0000000100000
xor -------------
    1011011001100


Jak jsem vyse predestrel, je úplne jedno, v jak'm poradí budeme GP xorovat. Proto zacneme úplne stejne jako u správn' zprávy pocítat CRC:

    
    10110111011000000
    1001
          1001
      1001
           1001
xor -------------
    00000001000000000
    ^^^^^^^^^^^^^
V tuto chvíli samozrejme jeste nejsme u konce vypoctu. Vsimnete si vsak, ze jako mezivysledek nám vysel chybovy vektor. Budeme-li pokracovat ve vypoctu dál, spocítáme tak vlastne CRC chybov'ho vektoru. Bude-li CRC takov'ho chybov'ho vektoru 0, jsou data povazována za správná. Volit GP je tedy potreba tak, aby pro nejpravdepodobnejsí chybovy vektor bylo CRC nenulov'!

Jak volit GP?
Odpoved na tuto otázku jsem hledal docela dlouho a nikde jsem nenasel dostatecne vycerpávající odpoved. Jist' vsak je jedno, není to úplne jednoduch' a v pozadí toho vseho je jistá dávka matematiky. Obvykle si ale GP nevymyslíme, ale pouzíváme GP, kter' jiz nekdo vymyslel za nás. Budete-li hledat na internetu, jiste patricn' hodnoty najdete :-)

Jen velmi krátce príklad: Chcete-li detekovat jednobitovou chybu, je celkem snadn' si oduvodnit, ze pro to stací GP s více jak jednou jednickou.

Autor: Ondrej Holecek - ondra (zavinác) sde (tecka) cz