Samenvatting Computer architecture and networks hoorcollege 14
14 views 0 purchase
Course
Computer architecture and networks
Institution
Universiteit Utrecht (UU)
Computer architectuur en netwerken hoorcollege 14. Aantekeningen van het hoorcollege Computerarchitectuur en netwerken (INFONW). Samenvatting wordt ondersteunt met plaatjes en voorbeelden voor extra duidelijkheid. Les gegeven op Universiteit Utrecht, Informatica.
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:
, 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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller luukvaa. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.21. You're not tied to anything after your purchase.
