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