CRC / XOR / modulo-2 långdivisionskalkylator

Så använder du CRC / XOR / modulo-2 långdivisionskalkylatorn

För att beräkna CRC med modulo-2 division, följ dessa 4 steg:

• Ange det binära meddelandet (databitar) i det första fältet.
• Ange generatorpolynomet som binära bitar i det andra fältet.
• Kalkylatorn lägger till (n − 1) nollbitar, där n är generatorlängden.
• Klicka på Beräkna för att XOR:a ned meddelandet och läs resten som CRC.

Kvoten kasseras vanligtvis i CRC-arbete — resten är kontrollsumman som läggs till meddelandet före sändning.

CRC och modulo-2-aritmetik

En cyklisk redundanskontroll upptäcker överföringsfel genom att behandla ett meddelande som ett stort binärt polynom och dividera det med ett överenskommet generatorpolynom. Divisionen görs i modulo-2 (GF(2))-aritmetik, där addition och subtraktion är identiska och lika XOR — det finns inga carry eller lån. Resten från denna division är CRC. När mottagaren dividerar meddelandet plus CRC med samma generator betyder rest 0 att inget fel upptäcktes. Denna kalkylator återskapar exakt den bitvisa processen.

Hur modulo-2 CRC-division fungerar

Kalkylatorn beräknar CRC genom fem interna åtgärder:

• Lägger till (n − 1) nollbitar till meddelandet, där n är antalet generatorbitar.
• Justerar generatorn under den vänstra 1-biten i aktuell rest.
• XOR:ar generatorn in i dessa bitar (modulo-2 subtraktion utan lån).
• Skiftar till nästa ledande 1-bit och upprepar XOR-justeringen.
• Stannar när kvarvarande bitar är färre än generatorn; dessa bitar är CRC.

Varje kvotbit är 1 där generatorn XOR:as in och 0 annars, men för CRC spelar bara slutresten roll.

Formel för CRC-division

CRC / XOR / modulo-2 långdivisionskalkylatorn beräknar CRC = (M(x) · xⁿ⁻¹) mod G(x) i GF(2), där M(x) är meddelandet, G(x) är generatorn med n bitar och alla additioner är XOR. Den sända ramen är M(x)·xⁿ⁻¹ + CRC, vilket G(x) delar exakt. På mottagarsidan bekräftar noll rest integritet.

CRC / XOR-exempelproblem

Dessa exempel visar modulo-2 division med XOR i varje steg.

Exempel 1 — Meddelande 1101, generator 101

1. Generatorlängd 3, så lägg till 2 nollor: 1101 blir 110100.
2. XOR:a 101 in i ledande bitar upprepade gånger: 110100 → 011100 → 001000 → 000010.
3. De sista 2 bitarna, 10, är CRC-resten.

Exempel 2 — Varför subtraktion är XOR

1. I modulo-2 är 1 + 1 = 0 och 1 − 1 = 0, så addera och subtrahera är samma operation.
2. Den operationen är exakt bitvis XOR, utan carry eller lån.
3. Så varje divisionssteg är en XOR av generatorn in i aktuella bitar.

Exempel 3 — Mottagarkontroll

1. Lägg till CRC till meddelandet och dividera med samma generator.
2. XOR:a ned exakt som tidigare.
3. Rest 0 betyder att inget fel upptäcktes.

Generatorlängd 3, så lägg till 2 nollor: 1101 blir 110100.
XOR:a 101 in i ledande bitar upprepade gånger: 110100 → 011100 → 001000 → 000010.
De sista 2 bitarna, 10, är CRC-resten.

I modulo-2 är 1 + 1 = 0 och 1 − 1 = 0, så addera och subtrahera är samma operation.
Den operationen är exakt bitvis XOR, utan carry eller lån.
Så varje divisionssteg är en XOR av generatorn in i aktuella bitar.

Lägg till CRC till meddelandet och dividera med samma generator.
XOR:a ned exakt som tidigare.
Rest 0 betyder att inget fel upptäcktes.

Genomräknade CRC-problem

Hur beräknar du CRC för 10110 med generator 1011?

Lägg till 3 nollor (generatorlängd 4) för att få 10110000, sedan XOR:a ned. Justera 1011 under varje ledande 1 och XOR:a: 10110000 → 00100000 → efter successiva XOR:ar bildar de sista 3 bitarna CRC-resten. Resten läggs sedan till 10110 så att hela ramen är delbar med 1011 utan rest.

Varför betyder noll rest att data är intakt?

Avsändaren valde CRC så att den sända ramen är en exakt multipel av generatorn. Varje multipel av G(x) dividerad med G(x) lämnar rest 0. Om bitar flippar under överföringen är ramen vanligtvis inte längre en multipel, så mottagarens division lämnar icke-noll rest och flaggar ett fel.

Vanliga CRC / modulo-2-fel

Modulo-2 CRC-division ger 5 frekventa fel:

• Använda vanlig binär subtraktion med lån i stället för XOR.
• Lägga till fel antal nollbitar (det måste vara generatorlängd minus ett).
• Justera generatorn under 0-bit i stället för ledande 1.
• Behandla carry som om de fanns i GF(2)-aritmetik.
• Rapportera kvoten som CRC i stället för resten.

CRC / XOR / modulo-2 långdivisionskalkylatorn XOR:ar i varje steg, lägger till korrekta nollor och returnerar resten som kontrollsumma.

Vanliga fragor