CRC

[Jan Waclawek]

K tomu "deleniu"...

Najlepsia literatura v danej oblasti je ten "painless guide", je to pre 
rychlu orientaciu prirozsiahle ale pre tych co chcu vediet detaily a 
pozadie tak je to celkom zivo literarne podane.

Inak matematici casto definuju rozne podobne nestandardne veci, lebo im 
to ulahcuje pohlad na rozne problemy (nakoniec ta "dohodnuta" aritmetika 
je tiez len optimalizovana pre nejaky konkretny, avsak pomerne casto v 
praxi pouzivany, problem - vediet si spocitat kusy); problem je len v 
tom, ze ti, co taketo nieco aplikuju, pochytia tu matematicku 
terminologiu len ciastocne (a poriadne nerozumeju, preco treba niektore 
veci nazyvat tak alebo onak) a tak vznikaju rozne podobne nedorozumenia.

"Deli" sa rucne tak, ze sa to najprv rozpise do binarneho tvaru, potom 
sa podpise delitel pod delenec tak, aby sedela lava jednicka, do 
vysledku sa napise jednicka, urobi sa "odcitanie", delitel sa posunie 
doprava tak aby znova bola zarovnana lava jednicka, do vysledku sa 
napise tolko nul o kolko sa posunulo doprava minus 1 a jedna jednicka, 
urobi sa "odcitanie" atd. az kym delitel "nedojde" po pravy doraz.

"Original" CRC je definovane tak, ze na zaciatok sa musi pridat ta 
pociatocna hodnota, a na koniec pridat tie nuly "delenca" ("nondirect" v 
tom javakalkulatore), ale tie nuly sa casto vynechavaju ("direct" v 
javakalkulatore) (to potom samozrejme vychadza ine CRC, to je to "bad" v 
citovanom clanku, ale pouziva sa to castejsie tak). Este pozor, k 
"delitelu" treba na zaciatok pripisat jednu 1.

To "delenie" vyzera na nasom priklade potom takto (vsimnite si, ze 
"odcitanie" tiez nie je odcitanie ale xor) - budeme zahadzovat podiel 
lebo nas zaujima len zvysok a nevyjde mi to na riadok :-) :


0xFFFF410000 "/" 0x11021 =
     1111111111111111010000010000000000000000 / 10001000000100001
"-" 10001000000100001
     0111011111101111110000010000000000000000
"-"  10001000000100001
     0011001111100111100000010000000000000000
"-"   10001000000100001
     0001000111100011101000010000000000000000
"-"    10001000000100001
     0000000011100001101100010000000000000000
"-"         10001000000100001
     0000000001101001101000011000000000000000
"-"          10001000000100001
     0000000000101101101010011100000000000000
"-"           10001000000100001
     0000000000001111101011011110000000000000
"-"             10001000000100001
     0000000000000111001011001110100000000000
"-"              10001000000100001
     0000000000000011011011000110110000000000
"-"               10001000000100001
     0000000000000001010011000010111000000000
"-"                10001000000100001
     0000000000000000010111000000111100000000
"-"                  10001000000100001
     0000000000000000000110000000011101000000
"-"                    10001000000100001
     0000000000000000000010010000010101010000
"-"                     10001000000100001
     0000000000000000000000011000010001011000
"-"                        10001000000100001
     0000000000000000000000001001010001111001 = 9479, co je hladane CRC.


Ako domaca uloha, spocitajte si ten podiel po pridani CRC ku "sprave" - 
ma vyjst nula.


Takyto algoritmus je vsak pre ucely programovej aj hardverovej 
implementacie dost nevhodny. Hardverovo sa to implementuje tym LFSR.

Pre software sa pouzivaju rozne upravene algoritmy ktore pocitaju priamo 
(a casto vychadzaju z nejakej vlastnosti generacneho polynomu ktory je 
navrhnuty tak, aby to vychadzalo jednoducho); alebo castejsie pomocou 
tabuliek (pricom tabulka moze byt bud pevna, alebo generovana prave 
pomocou "normalneho" "pomaleho" CRC) - pointa je, ze do takehoto 
algoritmu vstupuje naraz n bitov (obvykle n=8 alebo 16).

Samozrejme ten LFSR sa v software da napisat tiez ale je to pomale a 
vhodne len pre didakticke ucely (ja som si to napisal tiez "pre 
porovnanie" s tymi ostatnymi metodami, je to napokon len par riadkov).


wek




Danhard wrote:
> Ale je, ze se to realizuje hardwerove seriove, je jina.
> 
> A CRC "checksum" is the remainder of a binary division with no bit carry (XOR used instead of subtraction), of the message bit
> stream, by a predefined (short) bit stream of length n, which represents the coefficients of a polynomial. Before the division, n
> zeros are appended to the message stream.
> 
> Danhard
> *******
> 
> 
> Prestante uz s tou kalkulackou blbnut.
> CRC NIE JE DELENIE!!!! (aspon nie delenie v kalkulackovom zmysle)
> 
> wek
> 
> 
> 
> Danhard wrote:
> 
>>Aby se to jeden zase ucil :o)
>>
>>( 0xFFFF410000 - 0x9479 ) / 0x1021 = 0xFDF37A4  ??
> 
>