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.
hier ist eine auflistung getesteter standard polynome:
· 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)
Hey, ich lese bereits schon häufiger auf deinem Blog mit und verfolge die Beiträge mit großer Aufmerksamkeit. Die Artikel gefallen mir gut. Sie sind sehr “erfrischend” und sind gut neben dem Beruf zu lesen. Okay, soweit zum Lob. Dafür bekomme ich den Feed nicht in mein Feedprogramm hinein, es gibt auch keine Fehlermeldung , es passiert einfach nichts. Ich probiere es nächstes Mal einfach nochmal aus. Ich plane ein Ähnliches Blog zu starten, meinst du das macht in diesem Bereich überhaupt noch Sinn oder sollte ich mir lieber weniger “besiedelten” Bereich suchen? Ist ja nicht ganz so einfach heute noch erfolgreich ein eigenes Blog zu relaunchen und neue Besucher zu gewinnen. Wie stehst du dazu?