Polynom‐Division Modulo 2
Grundlagen der Rechnernetze ‐ Übertragungssicherung 14
X6 + X4 + X2 + X1 + 1 : X3 + X2 + 1 =
SS 2012
00101
Auswirkung von Fehlern
Grundlagen der Rechnernetze ‐ Übertragungssicherung 15
10100
10001
T
Tr
E
Sender
Empfänger
Für Generator P(X) und T(X)/P(X) = Q(X) werden nicht teilbare Fehler‐Pattern erkannt:
SS 2012
Erkennbare und nicht erkennbare Fehler
Grundlagen der Rechnernetze ‐ Übertragungssicherung 16
Ein Fehler ist nicht erkennbar genau dann wenn:
Single‐Bitfehler ist immer erkennbar, wenn P(X) mindestens zwei Terme enthält
Bitfehler‐Burst < Anzahl Check‐Bits ist immer erkennbar, wenn P(X) den Term 1 enthält
SS 2012
Weitere CRC‐Fakten
Grundlagen der Rechnernetze ‐ Übertragungssicherung 17
Double‐Bitfehler immer erkennbar, wenn P(X) einen Faktor mit drei Termen besitzt (ohne Beweis)
Ungeradzahlige Bitfehler immer erkennbar, solange P(X) einen Faktor (X+1) enthält (ohne Beweis)
Beliebte PolynomeCRC‐12 = X12 + X11 + X3 + X2 + 1CRC‐16 = X16 + X15 + X2 + 1CRC‐CCITT = X16 + X12 + X5 + 1CRC‐32 = X32 + X26 + X23 + X22 + X16 + X12 + X11
+ X10 + X8 + X7 + X5 + X4 + X2 + X + 1
SS 2012
Fehlerkorrektur
Grundlagen der Rechnernetze ‐ Übertragungssicherung 18SS 2012
Ablauf der Fehlerkorrektur
Grundlagen der Rechnernetze ‐ Übertragungssicherung 19Bildquelle: William Stallings, „Data and Computer Communications“, 2004
SS 2012
Beispiel Two‐Dimensional‐Parity
Grundlagen der Rechnernetze ‐ Übertragungssicherung 20
0 1 0 11 1 1 00 1 1 01 0 0 1
SS 2012
Erkenn‐ und Korrigierbarkeit von Fehlern
Grundlagen der Rechnernetze ‐ Übertragungssicherung 21
0 1 0 1 0
1 1 1 0 1
0 1 1 0 0
1 0 0 1 0
0 1 0 0 1
0 1 0 1 0
1 1 1 0 1
0 1 1 0 0
1 0 0 1 0
0 1 0 0 1
Ein‐Bit‐Fehler immer korrigierbar
0 1 0 1 0
1 1 1 0 1
0 1 1 0 0
1 0 0 1 0
0 1 0 0 1
Zwei‐Bit‐Fehler nicht immer korrigierbar
0 1 0 1 0
1 1 1 0 1
0 1 1 0 0
1 0 0 1 0
0 1 0 0 1
Zwei‐Bit‐Fehler immer erkennbar Nicht‐erkennbarer Fehler
SS 2012
Hamming‐Distanz
Grundlagen der Rechnernetze ‐ Übertragungssicherung 22
Hamming‐Distanz d(v1, v2) zwischen zwei n‐Bit‐Sequenzen v1 und v2
Beispiel: vier 4‐Bit‐Sequenzen mit einer paarweisen Hamming‐Distanz von mindestens 2
Wieviele Bit‐Fehler können erkannt werden?
SS 2012
Allgemein:
Ablauf der Übertragungim Falle keiner Bitfehler
Block‐Codes
Grundlagen der Rechnernetze ‐ Übertragungssicherung 23
Datenblock Codewort00 -> 0000001 -> 0011110 -> 1100111 -> 11110
Erkennen von Bit‐Fehlern: Es sei Code = {b1,...,bk} und es werde b empfangen:
Sender
Empfänger
f : Datenblock Codewort
SS 2012
Korrigieren von Bit‐Fehlern: Es sei Code = {b1,...,bk} und es werde b empfangen:
Korrigieren von Bitfehlern
Grundlagen der Rechnernetze ‐ Übertragungssicherung 24
Empfangen Nächstes gültiges CW Daten
Datenblock Codewort00 -> 0000001 -> 0011110 -> 1100111 -> 11110
SS 2012
Für k Daten‐Bits und n‐Bit Code‐Wörter gilt
Grundlagen der Rechnernetze ‐ Übertragungssicherung 25
Eindeutiges C‐Wort für jeden D‐Block, also
Benötigte Anzahl gültiger Code‐Wörter
Redundante Bits und Code‐Redundanz
Code‐Rate
Code‐Distanz für Code {b1,...,bk}
Benötigtes Verhältnis zwischen k und r=n‐k zum Korrigieren von allen 1‐Bit‐Fehlern?
SS 2012
Hamming‐Code
Grundlagen der Rechnernetze ‐ Übertragungssicherung 26
1 2 3 4 5 6 7 8 9 10 11Daten‐BitsCheck‐Bits
3 = 0 0 1 15 = 0 1 0 16 = 0 1 1 07 = 0 1 1 19 = 1 0 0 1
10 = 1 0 1 011 = 1 0 1 1
Beispiel‐Daten‐Bits:
1 0 0 1 0 0 0
SS 2012
Erkennen eines Ein‐Bit‐Fehlers
Grundlagen der Rechnernetze ‐ Übertragungssicherung 27
0 0 1 1 0 0 11 2 3 4 5 6 7 8 9 10 11
0 0 0 0
0 0 1 1 0 1 1 0 0 0 0
OriginalCode‐Wort
Ein‐Bit‐Fehler
3 = 0 0 1 15 = 0 1 0 16 = 0 1 1 07 = 0 1 1 19 = 1 0 0 1
10 = 1 0 1 011 = 1 0 1 1
Check Ergebnis
Daten‐BitsCheck‐Bits
SS 2012
Hamming‐Code erreicht die Schranke
Grundlagen der Rechnernetze ‐ Übertragungssicherung 28
Wie eben für k Daten‐Bits und n‐Bit Code‐Wörter ausgerechnet:Benötigtes Verhältnis zwischen k und r=n‐k zum Korrigieren von allen 1‐Bit‐Fehlern:
r+k+1 ≤ 2rBeispiel für unten abgebildeten Hamming‐Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Daten‐BitsCheck‐Bits
Was wenn Daten nur bis 11?
SS 2012
Umgang mit Bit‐Fehler‐Bursts
Grundlagen der Rechnernetze ‐ Übertragungssicherung 29Bildquelle: Andrew S. Tanenbaum, „Computer Networks“, Fourth Edition, 2003
Also:
SS 2012