Teoretyczny problem z alorytmem CRC

kemych · Postautor: **kemych** » 13 gru 2006, o 19:39

Mialem zaimplementowac w swoim programie algorytm liczenia sumy kontrolnej CRC-CCITT. Postac wielomianu jest taka: X^16 + X^12 + X^5 +1. Wartosc poczatkowa: 0xFFFF.
Dostalem gotowy dokument przepis , ktory wyglada tak:

NOTES:
A = new byte
B = temp byte
CRCHI = High byte (most significant) of the 16-bit CRC
CRCLO = Low byte (least significant) of the 16-bit CRC

START:
FOR A = FIRST_BYTE TO LAST_BYTE IN BLOCK DO:
A = A XOR CRCHI
CRCHI = A
SHIFT A RIGHT FOUR TIMES (ZERO FILL)
A = A XOR CRCHI { I J K L M N O P }
CRCHI = CRCLO { swap CRCHI, CRCLO }
CRCLO = A
ROTATE A LEFT 4 TIMES { M N O P I J K L }
B = A { temp save }
ROTATE A LEFT ONCE { N O P I J K L M }
A = A AND $1F { 0 0 0 I J L L M }
CRCHI = A XOR CRCHI
A = B AND $F0 { M N O P 0 0 0 0 }
CRCHI = A XOR CRCHI { CRCHI complete }
ROTATE B LEFT ONCE { N O P 0 0 0 0 M }
B = B AND $ E0 { N O P 0 0 0 0 0 }
CRCLO = B XOR CRCLO ( CRCLO complete }
DOEND;

Powiem szczerze nie zrozumialem z tego wszystkiego ale znalazlem gotowy algorytm w C liczenia sumy CCITT i faktycznie realizuje on te kroki. Suma jest liczona dobrze.

Moj problem jest czysto teoretcyzny. Mianowicie mam teraz napisac do tego sprawozdanie wiec musze zaczac od jakiegos wstepu o sumach kontrolnych. Wszedzie mozna znalezc przyklady, ze jest to reszta z dzielenia danego wyrazenia przez okreslony wielomian. Dodatkowo przed dzieleniem dopisuje sie do dzielnej tyle zer ile wynosi stopien wielomianu.
Sprawdzilem na kartce papieru. Dziala.
Problem ,ktory mnie nurtuje to jak sie to teoretyczne liczenie odnosi do tego algorytmu ,ktory wkleilem powyzej. Niewidze tam w ogole wykorzystania zadnego wielomianu ?? Wykorzystuje sie natomiast wartosc poczatkowa, ktora z kolei nie byla wykorzystywana w tych teoretycznych obliczeniach na kartce papieru.

Piotr · Postautor: **Piotr** » 13 gru 2006, o 22:29

Bardzo dobry cykl artykulow na ten temat znajdziesz w EP w 2005 roku. Nie pamietam dokladnie, w ktorych numerach, ale moze ktorys z forumowiczow ma archiwum pod reka. Jesli nie, to daj znac na priva, odszukam.
Pzdr
PZb

radzio · Postautor: **radzio** » 13 gru 2006, o 23:20

Bardzo dobry cykl artykulow na ten temat znajdziesz w EP w 2005 roku. Nie pamietam dokladnie, w ktorych numerach, ale moze ktorys z forumowiczow ma archiwum pod reka.

Jeśli chodzi o cykl "CRC doda Ci pewności" to jest w numerach 1-5/2003.

Piotr · Postautor: **Piotr** » 13 gru 2006, o 23:34

Tak o to mi chodzilo ;-))
Czas szybko leci, dzieki!
Pzdr
PZb

kemych · Postautor: **kemych** » 14 gru 2006, o 00:34

Mam to juz te artykuly pobrane od tygodnia ale nie wyjasnily moich watpliwosci.

gavi · Postautor: **gavi** » 14 gru 2006, o 09:11

Mam to juz te artykuly pobrane od tygodnia ale nie wyjasnily moich watpliwosci.

Artykuły są napisane znakomicie i wyjaśniają wszystko bardzo dobrze. Jednak temat jest bardzo zawily pojęciowo i trzeba dobrze parę razy je przeczytać, aby dokladnie zrozumieć ich sens . Musisz śledzić przedstawiony trok rozumowania i upewniać sie że na pewno kolejne implikacje są dla Ciebie oczywiste. Wtedy wszystko stanie sie jasne.

Teoretyczny problem z alorytmem CRC

Kto jest online