Hoorcollege 14
CRC staat voor Cyclic Redundancy Check. Komt neer op r bits toevoegen, algoritme:
- zender en ontvanger gebruiken een generator polynoom G(x) van graad r
G(x) = xr + gr-1xr-1 + ··· + g1x + g0
- Coëfficiënten van G(x) zijn 0 of 1 (rekenen modulo 2)
- D(x) is de data (als polynoom geïnterpreteerd)
- voeg toe r 0 bits achter D(x): geeft D(x) · xr
- deel D(x) · xr door G(x) (reken modulo 2) geeft quotiënt Q(x) en rest R(x): D(x) · xr = G(x).Q(x)
+ R(x)
- Verstuur M(x) = D(x) · xr - R(x) ontvanger controleert of deelbaar is door G(x)
- vindt veel fouten, vooral bursts.
We rekenen met bits: modulo 2:
- D.w.z. Veelvouden van 2 worden weggegooid, hierdoor werk je in domein 0 en 1 wat precies
genoeg is.
- 0+0 = 0
- 0+1 = 1
- 1+0 = 1
- 1+1 = 0 (=2-2)
- Aftrekken is hetzelfde als optellen
Bij de staartdeling komt er een 1 als het te delen getal met een 1 begint anders een 0.
We gaan bitrijen interpreteren als coëfficiënten van polynomen, dus:
101 => 1x2 + 0x + 1
11001 => 1x4 + 1x3 + 0x2 + 0x + 1
Vergelijk dit met: (2, -3, 7) => 2x2 - 3x + 7
Met als kanttekening dat de coëfficiënten nu 0 of 1 zijn.
Merk op dat we polynomen kunnen vermenigvuldigen en delen, b.v. in het domein van de reeële
getallen:
(2x2 - 3x + 7) * (x + 2) = 2x3 + 4x2 - 3x2 - 6x + 7x + 14 = 2x3 + x2 + x + 14
Of: (2, -3, 7) * (1, 2) = (2, 1, 1, 14)
Evenzo: (2x3 + x2 + x + 14) / (x + 2) = (2x2 - 3x + 7)
Ofwel: (2, 1, 1, 14) / (1, 2) = (2, -3, 7)
, Alle bits die we sturen en wat daarbij samenhangt gaan interpreteren als polynoom. D(x) is de data
als polynoom geïnterpreteerd, b.v.: 1010 => x3 + x
1101 => x3 + x2 + 1 We rekenen modulo 2, waardoor bits optellen en aftrekken gelijk zijn aan
elkaar. We hanteren een generator polynoom G(x) met bewezen error detection eigenschappen,
bijvoorbeeld: G(x) = x2 + 1 (of, als bitrij: 101), G(x) heeft graad r (hier: 2)
We willen r bits toevoegen (redundantie) als CRC code aan data D(x), om te controleren of het
pakket wel correct is aangekomen. Om dat te doen schuiven we D(x) r posities naar links, ofwel we
vermenigvuldigen D(x) met xr : D(x) * xr
We weten: D(x) * xr = Q(x) * G(x) + R(x) voor zeker quotiënt Q(x) en rest R(x)
Dus: D(x) * xr - R(x) = Q(x) * G(x) We rekenen R(x) uit, dit is onze CRC code We versturen dan M(x) =
D(x) * xr - R(x). Onder modulo 2 is dit gelijk aan M(x) = D(x) * xr + R(x). Bij correcte ontvangst is M(x)
nu deelbaar door G(x), zonder rest (immers: M(x) = Q(x) * G(x) ). De M(x) die we willen versturen is
onze data met xr naar links geschoven, + een R(x).
We bepalen rest R(x) door D(x) * xr / G(x) uit te rekenen. Ofwel: we nemen de met r posities naar
links geschoven data D(x) en delen door het generator polynoom G(x). Dit levert een quotiënt Q(x)
en een rest R(x) op. Q(x) is voor ons niet interessant, R(x) is onze CRC code => staartdelen met
bitrijen (DIV), gelukkig wel modulo 2. Merk op: rest R(x) heeft maximaal graad r, waardoor R(x) past
in de posities die we aan D(x) hebben toegevoegd (anders zou R(x) nog deelbaar zijn door G(x)).
M(x) = D(x) * xr + R(x) is dan eenvoudig te bepalen, praktisch gezien: M = (D << r) OR CRC code
We hebben generatorpolynoom G: 101(x2 +1) gebruiken. Als data hebben we D:
1101. Nu is de vraag welk bericht we naar de andere kant moeten sturen (M) en
wat is onze rest (R). We beginnen met de D R posities naar links te schuiven. De
maximale macht van G is 2, dus we gaan D 2 posities naar links schuiven, ofwel
(110100).
Vervolgens moeten we het bericht(M) gaan bepalen en daar hebben we de
rest(R) voor nodig. We komen aan de rest door onze data die we naar links
hebben geschoven te delen door het generator polynoom (G), dit is een
staartdeling. Hierbij komt eruit dat R = 10. Dus M = De R en de D samengevoegd,
dus 1101 10.
De andere kant moet aan de hand van deze informatie kunnen controleren of
het bericht correct is ontvangen. De andere kant ontvangt dus 110110, G is 101.
Nu gaat ontvanger controleren of M correct is. De andere kant gaat M delen
door het generator polynoom, hierbij is een deling zonder rest omdat de rest die
eruit zal moeten komen bij het vorige voorbeeld al afgehandeld is. Onder de
streep staat nu 00 en dit komt goed uit, de ontvangen M is dus OK.
