Ralf Eisenreich

die zyklische redundanzprüfung (crc – cyclic redundany check) wird vor allem bei der verarbeitung von bitfolgen (übertragung, speicherung) genutzt.
dabei wird einer bitfolge eine fcs (frame check sequence) angehangen, die meist 12, 16 oder 32 bit lang ist.
damit soll sichergestellt werden, dass die emfangenen daten auch tatsächlich fehlerfrei sind und nicht durch störungen auf dem übertragungsweg (z.b. rauschen der leitung) bitfehler aufgetreten sind.
diese fehlererkennungsmethode ist viel leistungsfähiger als paritätsbits oder fehlerprüfsummen, d.h. man kann also mehr bitfehler oder bitfehlerfolgen (fehlerbursts) erkennen.
ein weiterer vorteil von crc ist, dass man nur wenige bits (ingesamt bilden diese die fcs) hinzufügen muss, es entsteht also wenig redundanz.
(redundanz entsteht immer dann wenn einer bitfolge für die datensequenz “wertlose” bits hinzugefügt werden.)
bei einem ethernet werden zum beispiel an frames, die 12000bit groß sind nur 32bit (fcs) angehangen, trotzdem ist die erkennung von fehlern bei der fcs als sehr hoch einzuschätzen.
erkennt der empfänger einer datensequenz einen übertragungsfehler, wird die entsprechende einheit verworfen und eine erneute übertragung beim sender angefordert.

das crc-verfahren basiert auf einer bitweisen (also ohne überträge!) binärarithmetik modulo 2 (was einer xor-operation entspricht).
es gilt also für addition und subtraktion:

0 + 1 = 1   1 + 0 = 1   0 - 1 = 1   1 - 0 = 1

0 + 0 = 0   1 + 1 = 0   0 - 0 = 0   1 - 1 = 0

multiplikation wird als sukzessive (bitweise) addition und division als sukzessive subtraktion ausgeführt:

1100101        0110001

+ 1010100      - 1010100

--------       --------

0110001        1100101

der algorithmus basiert nun darauf, dass man die zu übertragende bitfolge (folge von 0en und 1en) als polynome mit den koeffizienten 0 und 1 interpretiert. bei m bits hat man dann m terme — von b^(m-1) bis b^0.

hierzu ein beispiel:

0101101 --> 0 + b^5 + 0 + b^3 + b^2 + 0 + b^0

0101101 -->     b^5   +   b^3 + b^2   +   b^0

0101101 -->     b^5   +   b^3 + b^2   +   1

die fcs (frame check sequence) wird mit hilfe eines generator-polynoms berechnet, das sender und empfänger definieren.
für die weitere betrachtung definieren wir folgendes:
- das generatorpolynom g(b) besteht aus g bits
- das daten-polynom m(b) besteht aus m bits
- r ist der grad der generator-polynoms g(b)
- das daten-polynom t(b) mit fcs besteht aus t bits

einem zu übertragenden rahmen (frame) wird nun die fcs angehangen (man nennt diese auch trailer, anhang). dabei ist der rahmen (der die datenbits enthält) durch m bits so zu ergänzen, dass das polynom aus datenbits und fcs durch das generatorpolynom teilbar ist.

–> der algorithmus:
1.)
anhängen von r 0-bits an das ende des zu übertragenden frames m(b)
der neue rahmen hat jetzt also (m + r) bits, was folgendem polynom entspricht: b^r * m(b)

2.)
dividiere die bitfolge b^r * m(b) durch die bitfolge des generator-polynoms g(b) gemäß modulo-2-arithmetik

3.)
der divisionsrest (< = r bits) ist die fcs. diese wird jetzt der zu übertragenden nachricht m(b) angehangen.
das resultat ist die neue zu übertragende bitfolge (frame + fcs) t(b).

–> anmerkung:
die fcs werden in der praxis einfach mit shift- und xor-registern berechnet.

· daten-frame: 1101011011
· generator-polynom: b^4 + b + 1

–> daraus folgt
· daten-polynom: b^9 + b^8 + b^6 + b^4 + b^3 + b^1 + b^0
· generator-frame: 10011

–> also

Frame:              1 1 0 1 0 1 1 0 1 1

Generator:          1 0 0 1 1

–> hinzufügen von r=4 (grad des generators) 0-bits

Frame mit 0-Bits:   1 1 0 1 0 1 1 0 1 1  0 0 0 0

–> division durch generator-polynom g(b)

Division:

1 1 0 1 0 1 1 0 1 1 0 0 0 0  /  1 0 0 1 1  =  1 1 0 0 0 0 1 0 1 0

1 0 0 1 1 ------------------------------------+ | |             |

---------                                       | |             |

1 0 0 1 1                                     | |             |

1 0 0 1 1 ------------------------------------+ |             |

---------                                       |             |

0 0 0 0 1                                     |             |

0 0 0 0 0 ------------------------------------+    . . .    |

---------                                                   |

0 0 0 1 0                                                 |

0 0 0 0 0                                                 |

---------                                                 |

0 0 1 0 1                                               |

0 0 0 0 0                                               |

---------                                               |

0 1 0 1 1                                             |

0 0 0 0 0                                             |

---------                                             |

1 0 1 1 0                                           |

1 0 0 1 1                                           |

---------                                           |

0 1 0 1 0                                         |

0 0 0 0 0                                         |

---------                                         |

1 0 1 0 0                                       |

1 0 0 1 1                                       |

---------                                       |

0 1 1 1 0                                     |

0 0 0 0 0 ------------------------------------+

---------

1 1 1 0  =  Rest

–> es entsteht der frame mit prüfsumme t(b)

1 1 0 1 0 1 1 0 1 1  1 1 1 0

–> kontrolle
der empfänger erhät nun die bitfolge t(b) und kann dann, indem er t(b) durch g(b) dividiert (rechnung äquivalent zu oben) überprüfen, ob der frame korrekt übertragen wurde. das ergebnis muss dann nämlich einen rest von 0 haben.

nehmen wir an, die übertragung wird gestört und es wird statt des erwarteten frames t(b) der fehlerhafte frame t(b) + e(b) empfangen.
jedes 1-bit in e(b) entspricht einem bitfehler, wobei ein einzelnes 1-bit ein singlebitfehler ist und eine 1 gefolgt von 0 oder 1 und wieder 1 ein burst, (alle anderen bits in e(b) sind 0).

folgende bitfehler können also erkannt werden:
1.) singlebitfehler: e(b) = b^i
für die erkennung muss g(b) mindestens 2 terme haben!

2.) 2 singlebitfehler: e(b) = b^i + b^j mit i > j
g(b) darf nicht durch b^k + 1 teilbar sein für k=1..m (framelänge)

3.) ungerade anzahl von bitfehlern:
g(b) muss den faktor b + 1 enthalten!

4.) burstfehler:
ein polynom des grads r erkennt alle burstfehler einer länge < = r.
dazu muss g(b) einen b^0-term enthalten. bursts der länge r+1 werden mit einer wahrscheinlichkeit von 0.5^(r-1) nicht erkannt.
die gesamtwahrscheinlichkeit, dass ein gestörter frame durchkommt, ist 0.5^r, unter der voraussetzung, dass alle bitmuster gleichmässig verteilt sind.

· crc-8:     b^8 + b^2 + 11 (atm)

· crc-10:    b^10 + b^9 + b^5 + b^4 +b^1 + 1 (atm)

· crc-12:    b^12 + b^11 + b^3 + b^2 + b^1 + 1

· crc-16:    b^16 + b^15 + b^2 + 1

· crc-ccitt: b^16 + b^12 + b^5 + 1 (hdlc)

· crc-32:    b^32 + b^26 + ... + b^2 + b^1 + 1 (ethernet, fddi)