Nederlands
Menu

Wat is CRC (cyclic redundancy check)?

Methode voor foutdetectie die de databits als polynoom behandelt, de rest van de deling door een generatorpolynoom toevoegt en de ontvanger de berekening laat herhalen om fouten te detecteren. Ze wordt veel gebruikt in Ethernet, PCI Express, USB en bestandsformaten.

Japanse benaming: CRC(巡回冗長検査)

“CRC (cyclic redundancy check)” komt voor in 8 oefenvragen uit 3 onderwerpen, bijv. Basis van informatietheorie en codering, Logische schakelingen, Interfaces en busstandaarden.

Vakgebied: Interfaces en busstandaarden

Hoe het werkt

Een CRC behandelt de databits als de coëfficiënten van een polynoom in modulo 2-rekenkunde en berekent de rest na deling door een generatorpolynoom. In modulo 2-rekenkunde zijn optellen en aftrekken allebei XOR, zodat de deling bestaat uit het herhalen van „is de voorste bit 1, XOR dan de generator en schuif één positie op”. Bij een CRC van w bits wordt de rest van w bits die ontstaat na het toevoegen van w nullen met de gegevens meegestuurd, en herhaalt de ontvanger de berekening om te controleren of die overeenkomt. Echte standaarden voegen afspraken toe zoals een beginwaarde, het spiegelen van de bits van elke byte en een afsluitende XOR.

Fouten die worden gedetecteerd en toepassingen

Een CRC van w bits detecteert elke burstfout met een lengte van w of minder, en de kans dat andere willekeurige fouten worden gemist, is ongeveer 2⁻ʷ. Ze detecteert fouten echter alleen en kan ze niet corrigeren, zodat systemen herstellen door opnieuw te verzenden. CRC's worden gebruikt in de Ethernet-FCS (CRC-32), PCI Express-pakketten, USB, CAN-bus, opslagopdrachten en bestandsformaten zoals ZIP en PNG, en in hardware kunnen ze worden berekend met een lineair teruggekoppeld schuifregister dat is opgebouwd uit flipflop-trappen en XOR-poorten.

Nu oefenen: vragen over CRC (cyclic redundancy check)

Aan de gegevens 1101 moeten de 3 controlebits worden toegevoegd van een CRC met het generatorpolynoom x³ + x + 1 (bitreeks 1011). De controlebits zijn de rest van de deling van 1101000, de gegevens gevolgd door drie nullen, door 1011, waarbij in de deling de exclusieve OF in plaats van aftrekken wordt gebruikt. Wat zijn de controlebits?

  1. A001
  2. B101
  3. C110
Antwoord en toelichting tonen

Antwoord: A. 001

Deel 1101000 door 1011. De exclusieve OF van de voorste 1101 en 1011 is 0110; na het bijhalen van de volgende bit krijgt men 1100, waarvan de exclusieve OF met 1011 gelijk is aan 0111; 1110 met 1011 geeft 0101; en ten slotte geeft 1010 met 1011 de waarde 0001, dus de rest is 001. Verzonden wordt 1101001, en de ontvanger oordeelt dat er geen fout is als de rest na deling door 1011 gelijk is aan 0.

Welke beschrijving van een CRC waarvan het generatorpolynoom graad r (r controlebits) en een constante term 1 heeft, is juist?

  1. ABij een fout van 1 bit is het belangrijkste gebruik te bepalen welke bit fout is en die te corrigeren
  2. BZe detecteert elke burstfout (een fout die binnen een aaneengesloten gebied valt) met een lengte van r bits of minder
  3. CMet een goed gekozen generatorpolynoom detecteert ze elk mogelijk foutpatroon
Antwoord en toelichting tonen

Antwoord: B. Ze detecteert elke burstfout (een fout die binnen een aaneengesloten gebied valt) met een lengte van r bits of minder

Wordt het foutpatroon weergegeven als een polynoom E(x), dan mist een CRC een fout alleen wanneer E(x) deelbaar is door het generatorpolynoom G(x). Een burstfout met een lengte van r of minder kan worden geschreven als x^i × B(x) (B(x) van graad r − 1 of minder met constante term 1), wat niet deelbaar is door een G(x) van graad r met constante term 1, dus ze wordt altijd gedetecteerd. Daarentegen worden deelbare patronen, zoals een fout met dezelfde vorm als G(x) zelf, niet gedetecteerd. CRC's worden vooral gebruikt om fouten te detecteren, en wordt er een fout gevonden, dan worden de gegevens opnieuw verzonden.

Veelgestelde vragen

Hoe verschilt een CRC van een checksum?

Een checksum gebruikt een eenvoudige bewerking zoals het optellen van bytes en mist makkelijk verwisselde gegevens of fouten die elkaar opheffen, terwijl een CRC is gebaseerd op polynoomdeling, bitposities onderscheidt en burstfouten betrouwbaar opvangt.

Kan een CRC fouten corrigeren?

In het algemeen niet. Een CRC detecteert of er een fout is opgetreden, maar niet welke bit fout is, dus geheugens die correctie nodig hebben, gebruiken een ECC zoals een Hamming-code.

“CRC (cyclic redundancy check)” in de toelichting

Vragen met “CRC (cyclic redundancy check)” (8)

  1. Aan de gegevens 1101 moeten de 3 controlebits worden toegevoegd van een CRC met het generatorpolynoom x³ + x + 1 (bitreeks 1011). De controlebits zijn de rest van de deling van 1101000, de gegevens gevolgd door drie nullen, door 1011, waarbij in de deling de exclusieve OF in plaats van aftrekken wordt gebruikt. Wat zijn de controlebits?
  2. Welke beschrijving van een CRC waarvan het generatorpolynoom graad r (r controlebits) en een constante term 1 heeft, is juist?
  3. Wanneer is de uitgang van een XOR-poort (exclusieve OF) met 2 ingangen 1?
  4. Wat is een typische toepassing van een lineair teruggekoppeld schuifregister (LFSR), waarin de XOR van een deel van de uitgangen naar de ingang wordt teruggevoerd?
  5. Gegevens worden byte voor byte opgeteld, en de laagste 8 bits van de som worden als controlewaarde (checksum) meegestuurd. Welke van de volgende fouten kan deze controle niet detecteren?
  6. Welke beschrijving van ARQ (automatic repeat request) en FEC (forward error correction), methoden om fouten in communicatie op te vangen, is juist?
  7. Wat doet de datalinklaag van PCI Express bij bitfouten tijdens de transmissie?
  8. Als bij PCI Express veel pakketten worden verzonden die kleine data van 64 bytes schrijven, wordt de effectieve bandbreedte aanzienlijk kleiner dan de theoretische waarde. Wat is de belangrijkste reden?

Verwante termen

PCI Express Schuifregister BIST (built-in self-test) Forward error correction (FEC) 128b/130b-codering 8b/10b-codering AXI Bitfoutenpercentage (BER) Clock-and-data-recovery (CDR) Creditgebaseerde flowcontrol

Naar de woordenlijst