CRC előállítása bitenkénti eltolással


Először elég nehezen boldogultam a CRC-k kavalkádjában és nehezen tudtam követni a számoló programok által átadott eredményeket az általam kiszámítottak tükrében.
Az irodalmak böngészése elég fárasztó, és miután kezd derengeni valami, rájön az ember, hogy ezt sokkal lényegretörőbben is el lehetne magyarázni, ill. jól áttekinthető példát lehet írni, ami többet mond minden polinom elméleti leírásnál. Itt most igyekszem egy ilyen példán keresztül a lehető legegyszerűbb módon bemutatni a CRC kiszámolásának módját.
Ha megértettük a folyamatot, akkor már könnyen készíthetünk kódot bármely nyelven. Kódot  nem mutatok be, mert bevallom én nem sokra mentem a kész példák böngészésével, mert a folyamat lényegét és egyszerűségét nem értettem meg belőlük. A leghatékonyabb számomra az volt, hogy gyalog módszerrel végig lépegettem a folyamaton.
.
Így több alapkérdést sikerült kibogoznom:
Négyféle számítási módszer van.
1. Adatbájtok és a kiszámolt CRC kód bitjei eredeti sorrendben vannak.
2. Adatokbájt bitek nincsenek, a kiszámolt CRC bitjeit fordított sorrendben használjuk(a CRC bitejeit, csak a kiszámolás után írjuk fel fordítva).
3. Adatbájtok bitjei fordítottak(csak a bájtokon belüli bitek sorrendje fordított, a bájtok sorrendje nme változik az átvitel során.) , a CRC bitjei nem.
    Az adatbájtok bitjeit még a számítások alőtt megfordítjuk(nem inveráljuk, hanem fordított sorrendben írjuk fel).               
4. Az Adat és a CRC bitjei is fordított sorrenben vannak kezelve.

Nem igazán értem a jelentőségét a 4 módnak, erről nem sok infót találtam, de tény, hogy az általam használt CRC számoló programban ki lehet választani ezeket a lehetőségeket. Ha keresni kéne az okot, akkor esetleg a hardveres léptetőregiszteres CRC kódoló-dekódoló áramkörök felépítésében találhatnánk magyarázatot, mert matematikailag a felderített hibák valószínűsége nem változik(szerintem. ha még is kérem jelezzétek, hogy javíthassam ezen kijelentésemet!).
Érdekes, hogy azoknál a CRC-t számoló programoknál, ahol nem lehet kiválasztani a módokat, ott a 4-es mód az alapértelmezett. Ezzel szemben az irodalmak az 1-es mód szerint magyarázzák a polinomok és a CRC-k számításának mikéntjét.

Tehát készítettem egy táblázatot, amelyben mind a 4 módot levezettem. A táblázatban linkeltem az egyik CRC-t számoló weboldalt, ahol le lehet ellenőrizni saját készi próbálkozásainkat. Az oldalon több linket, és egyébb magyarázó szöveget is találunk a témához(angol).
A táblázatban a CRC-16 eredeti generátor polinomját használom: x16+x15+x2+1, ahol az x=2.
Ez így egy bináris számot alkot, ahol a kiválasztott hatványnál 1 a helyiérték értéke: 1-1000-0000-0000-0101.
A számításokban az x16. bitet nem szoktuk használni, mert értéke mindig 1.
Így jön ki az irodalmakban jelzett 0x8005 generátor polinom. (1000-0000-0000-0101). Ezzel számolok a példában is.
A generátor polinomokat hosszas matematikai elemzés után válaszják ki. Több ilyen polinomot is használnak és szabványosítottak, ezekről az irodalmakban lehet infót találni, én itt nem is részletezném, talán csak annyit, hogy bármely polinommal kipróbálható a táblázatban megfigyelhető szekvencia. A folyamat több bites (pl. CRC32) polinomokkal is működik természetesen, csak akkor a kiegészítő nullák száma meg kell feleljen a választott polinom fokszámának(CRC32-nél 32db nulla kell, a táblázatban a CRC16 esetében 16db.)

Az említett táblázat:
CRC16_számítás_kézzel.xls

Több részletes irodalmat lehet találni, talán ez az egyik legjobban kidolgozott(Szerző: Kiss József):
CRC Kódolás.doc


watt
wattmep@tvn.hu
2008.04.26