D - Koblenz

Übungen zur Vorlesung
Grundlagen der Rechnernetze
Zusätzliche Übungen
Hamming-Abstand d
Der Hamming-Abstand d zwischen zwei Codewörtern c1 und c2 ist die
Anzahl der Bits, in denen sich die beiden Codewörter unterscheiden.
Beispiel :
c1 10001001
c2 10100000
 00101001
Hamming Abstand d(10001001, 10100000) = 3
Hamming-Abstand D eines vollständigen Codes C
Der Hamming-Abstand D eines vollständigen Codes C = {c1, c2, . . . , cn}
ist der minimale Hamming-Abstand d zweier Codewörter c1 und c2.
D(C) = min{ d(c1, c2), c1, c2 ∈ C, c1 = c2}
Hamming-Abstand
Code C:
Distanzen d:
Zeichen
a
b
c
d
e
Codewort
0000 0000
0000 0111
0011 1000
1100 0001
0001 1110
Zeichen
a
b
c
d
e
Hamming-Distanz D = 3
Anzahl garantiert korrigierbarer Bitfehler = 1
a b c d
- 3 3 3
e
4
3
-
6
3
3
3
4
6
4
3
- 6 3
6 - 7
3 7 -
4
Hamming-Abstand
Die Fähigkeit eines Hamming-Codes, Fehler zu erkennen und Fehler zu
beheben, hängt von seinem Hamming-Abstand ab.
Erkennen von n-Bit Fehlern:
Ein Abstand von n + 1 wird benötigt
Beheben von n-Bit Fehlern:
Ein Abstand von 2n + 1 wird benötigt
Konstruktion eines Hamming-Codes
●
●
●
Gegeben: Datenwörter von m-Bit Länge
Datenwörter sind durch eine Hammingcodierung so abzusichern,
dass alle 1-Bit Fehler sicher korrigiert werden können
Gesucht: Um r Redundanzbits angereicherte legale Codewörter der
Länge n = m + r mit einem Hamming-Abstand D = 3
Konstruktion eines Hamming-Codes
●
legale Codewörter = korrekt und ohne Fehler übertragene
Codewörter
●
illegale Codewörter = durch 1-Bit Fehler verfälschte Codewörter
●
legale und illegale Codewörter müssen disjunkte Mengen bilden
●
zu jedem illegalen Codewort gibt es höchstens ein legales Codewort
mit Hamming-Abstand d = 1
Wieviel Redundanz braucht man?
Das zu sichernde Datenwort bestehe aus m Bits.
Das Codewort der Länge n besteht dann aus m Datenbits plus r
Prüfbits:
n = m + r,
m Datenbits, r Prüfbits
Frage:
Wie viele Prüfbits werden benötigt, um jeden 1-Bit-Fehler beheben zu
können?
Wieviel Redundanz braucht man?
n = m + r, m Datenbits, r Prüfbits
●
●
Es gibt 2m legale Codewörter der Länge n Bits.
Pro legalem Codewort gibt es mindestens n illegale Codewörter
mit Hamming-Abstand 1.
(Invertieren eines Bits soll zu einem illegalem Codewort führen.)
● 2n ist die Gesamtzahl der darstellbaren Codewörter.
n = m + r, m Datenbits, r Prüfbits
(n + 1) 2m = 2n = 2m+r (n illegale + 1 legales Wort)
(n + 1) = 2r
(m + r + 1) ≤ 2r
Das ergibt die untere Grenze für die erforderliche Anzahl der
Prüfbits r
Wieviel Redundanz braucht man?
Beispiele:
Datenbreite
Prüfbits
Codebreite
Prüfbits/Datenbits
4
3
7
75%
8
4
12
50%
16
5
21
31%
32
6
38
19%
64
7
71
11%
128
8
136
6%
256
9
265
4%
●
●
●
Konstruktion eines Hamming-Codes
r Prüfbits ergeben 2r verschiedene Prüfwerte
Codewortbreite m + r ist auf jeden Fall kleiner als 2r
Ziel: Aus dem Prüfwert, also den r Prüfbits, auf einfache Art
● erkennen, ob ein Fehler bei der Übertragung aufgetreten ist
und
● die Position des gekippten Bits ermitteln.
Konstruktion eines Hamming-Codes
●
●
Der Hamming-Code besteht aus m Daten-Bits (D0,D1, . . . ,Dm−1)
und r Redundanz-Bits (R0,R1,..Rr−1),
zusammen n = m + r Bits.
Diese Bits werden von 1 (nicht von 0 an!) bis m wie folgt
Durchnummeriert:
●
Redundanzbit Ri bekommt die Nummer 2i
● Die Datenbits (D ,D ,… D
) erhalten der Reihenfolge nach
0
1
m−1
die jeweils freien Nummern, also D0 die Nummer 3, D1 die
Nummer 5 usw.
● Diese Nummern entsprechen genau den n Bitpositionen im
Codewort.
Beispiel:
●
●
●
Datenwörter der Länge 8, also Daten-Bits (D0,D1, . . .,D7).
Es werden 4 Redundanz-Bits gebraucht (8 + 4 + 1 = 13 ≤ 24
=16 ).
Anordnung der Bits im Codewort
Bitposition
1
2
3
4
5
6
7
8
9
10
11
12
Inhalt
R0
R1
D0
R2
D1
D2
D3
R3
D4
D5
D6
D7
●
●
●
●
Jedes Redundanz-Bit wird nach dem even parity Verfahren
berechnet unter Einbeziehung bestimmter Daten-Bits.
Diese Datenbits befinden sich an bestimmten Bitpositionen im
Codewort.
Man sagt :
Jedes Redundanz-Bit überwacht eine Reihe bestimmter
Bitpositionen.
Dabei gilt:
Redundanz-Bit Ri überwacht Bitposition k genau dann, wenn in
der Binärdarstellung von k an Stelle i eine 1 ist.
(Stellen werden beginnend mit 0 für das niederwertigste Bit
gezählt.)
Beispiel 1: Bitposition 5 (Datenbit D1)
●
510 = 01012
●
Eine 1 befindet sich an den Stellen 0 und 2.
●
Position 5 wird also von den Redundanz-Bits R0 und R2
überwacht.
Beispiel 2: Redundanz-Bit R1 (Bitposition 2)
●
Überwacht werden alle Bitpositionen mit einer 1 an Stelle 1 in der
Binärdarstellung
●
●
Das sind 00102, 00112, 01102, 01112, 10102 und 10112, also die
Positionen 2, 3, 6, 7, 10 und 11.
11102 und 11112 also 14 und 15 überschreiten die Codewortbreite,
brauchen also nicht berücksichtigt zu werden.
Bitposition
1
2
3
4
5
6
7
8
9
10
11
12
Inhalt
R0
R1
D0
R2
D1
D2
D3
R3
D4
D5
D6
D7
R0
1
0
1
0
1
0
1
0
1
0
1
0
R1
0
1
1
0
0
1
1
0
0
1
1
0
R2
0
0
0
1
1
1
1
0
0
0
0
1
R3
0
0
0
0
0
0
0
1
1
1
1
1
Binärdarstellung der Bitposition
hier Position 510 = 01012
Bitposition
1
2
3
4
5
6
7
8
9
10
11
12
Inhalt
R0
R1
D0
R2
D1
D2
D3
R3
D4
D5
D6
D7
R0
1
0
1
0
1
0
1
0
1
0
1
0
R1
0
1
1
0
0
1
1
0
0
1
1
0
R2
0
0
0
1
1
1
1
0
0
0
0
1
R3
0
0
0
0
0
0
0
1
1
1
1
1
R0  D0  D1  D3  D4  D6 = 0
↔ R0 = D0  D1  D3  D4  D6
Bitposition
1
2
3
4
5
6
7
8
9
10
11
12
Inhalt
R0
R1
D0
R2
D1
D2
D3
R3
D4
D5
D6
D7
R0
1
0
1
0
1
0
1
0
1
0
1
0
R1
0
1
1
0
0
1
1
0
0
1
1
0
R2
0
0
0
1
1
1
1
0
0
0
0
1
R3
0
0
0
0
0
0
0
1
1
1
1
1
R1  D0  D2  D3  D5  D6 = 0
↔ R1 = D0  D2  D3  D5  D6
Aufgabe 8
Bitposition
1
2
3
4
5
6
7
8
9
10
11
12
Inhalt
R0
R1
D0
R2
D1
D2
D3
R3
D4
D5
D6
D7
R0
1
0
1
0
1
0
1
0
1
0
1
0
R1
0
1
1
0
0
1
1
0
0
1
1
0
R2
0
0
0
1
1
1
1
0
0
0
0
1
R3
0
0
0
0
0
0
0
1
1
1
1
1
R2  D1  D2  D3  D7 = 0
↔ R2 = D1  D2  D3  D7
Aufgabe 8
Bitposition
1
2
3
4
5
6
7
8
9
10
11
12
Inhalt
R0
R1
D0
R2
D1
D2
D3
R3
D4
D5
D6
D7
R0
1
0
1
0
1
0
1
0
1
0
1
0
R1
0
1
1
0
0
1
1
0
0
1
1
0
R2
0
0
0
1
1
1
1
0
0
0
0
1
R3
0
0
0
0
0
0
0
1
1
1
1
1
R3  D4  D5  D6  D7 = 0
↔ R3 = D4  D5  D6  D7
Berechnung der Prüfbits
R0 = D0 ⊕ D1 ⊕ D3 ⊕ D4 ⊕ D6
R1 = D0 ⊕ D2 ⊕ D3 ⊕ D5 ⊕ D6
R2 = D1 ⊕ D2 ⊕ D3 ⊕ D7
R3 = D4 ⊕ D5 ⊕ D6 ⊕ D7
Hamming-Code: Codierung
Schritt 1:
● Berechne die Prüfbits R
i
Schritt 2
● Setze die Daten- und Prüfbits an die entsprechenden
Bitpositionen im Codewort
Hamming-Code: Decodierung
Schritt 1
● Überprüfen der Paritätsgleichungen
● Setze Testwert auf 0
i
● Für alle R : Ist R falsch, addiere 2 zum Testwert
i
i
Schritt 2
● Eventuell Korrektur vornehmen
● Ergibt sich ein Testwert von 0, war die Übertragung korrekt
● Ergibt sich ein Testwert ungleich 0, ist das Bit an der
Position gekippt, welche dem Testwert entspricht, also
invertiere dieses Bit
Schritt 3
● Extrahiere die Datenbits
Beispiel
Codieren Sie folgende Datenblöcke (D0, . . . ,D4) indem Sie die
Redundanzbits (R0,... ,R3) berechnen und an den entsprechenden
Positionen einfügen (Die Positionen 1 bis 9 geben Sie
bitte wie in der Tabelle von links nach rechts an):
1) (01101) :
1)
(D0, D1, D2, D3, D4) = ( 0 1 1 0 1)
R0 = D0 ⊕ D1 ⊕ D3 ⊕ D4
R1 = D0 ⊕ D2 ⊕ D3
R2 = D1 ⊕ D2 ⊕ D3
R3 = D4
=0
=1
=0
=1
Bitposition
1
2
3
4
5
6
7
8
9
Inhalt
R0
R1
D0
R2
D1
D2
D3
R3
D4
(Codewort)
0
1
0
0
1
1
0
1
1
27
1)
(D0, D1, D2, D3, D4) = ( 0 1 1 0 1)
Bitposition
1
2
3
4
5
6
7
8
9
Inhalt
R0
R1
D0
R2
D1
D2
D3
R3
D4
x
x
0
x
1
1
0
x
1
(Codewort)
Pos:R3R2R1R0
01 0 1 =5
01 1 0 =6
 10 0 1 =9
1 01 0
Bitposition
1
2
3
4
5
6
7
8
9
Inhalt
R0
R1
D0
R2
D1
D2
D3
R3
D4
(Codewort)
0
1
0
0
1
1
0
1
1
Beispiel
Decodieren Sie die folgende empfangenen Codewörter:
1) 111001000 :
Aufgabe 13
2) ( 111001000 )
Bitposition
1
2
3
4
5
6
7
8
9
Inhalt
R0
R1
D0
R2
D1
D2
D3
R3
D4
(Codewort)
1
1
1
0
0
1
0
0
0
R0 = D0 ⊕ D1 ⊕ D3 ⊕ D4
R1 = D0 ⊕ D2 ⊕ D3
R2 = D1 ⊕ D2 ⊕ D3
R3 = D4
=1
=0
=1
=0
richtig
falsch
falsch
richtig
gekipptes Bit: 01102 = 610⇒ ändere D2 von 1 auf 0.
Nachricht (D0,D1,D2,D3,D4) = (10000)
30
1) ( 111001000 )
Bitposition
1
2
3
4
5
6
7
8
9
Inhalt
R0
R1
D0
R2
D1
D2
D3
R3
D4
(Codewort)
1
1
1
0
0
1
0
0
0
0
0
0
 0
0
0
0
0
1
1
0
1
1
1
1
1=1
0=2
1=3
0=6
0
← falsch → 610 → D2 => 0
Nachricht (D0,D1,D2,D3,D4) = (10000)
2) ( 111001000 )
Bitposition
1
2
3
4
5
6
7
8
9
Inhalt
R0
R1
D0
R2
D1
D2
D3
R3
D4
(Codewort)
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1=1
0=2
1=3
0 ← korrekt
Nachricht (D0,D1,D2,D3,D4) = (10000)
Bitfolgen interpretiert als Polynome
Beispiel:
10011010
entspricht dem Polynom :
M(x) = 1 x7 + 0 x6 + 0 x5 + 1 x4 + 1 x3 + 0 x2 + 1 x1 + 0 x0
= x7 + x4 + x3 + x1
polynomielle Arithmetik modulo 2
●
Koeffizienten entweder 0 oder 1
●
kein Übertrag zu berücksichtigen
●
Addition und Subtraktion identisch, XOR
Wollen wir eine Bitfolge M(x) angereichert mit CRC-Information
übertragen, senden wir eine um k Bits verlängerte Bitfolge M'(x),
welche ohne Rest durch C(x) teilbar ist.
1. Multipliziere M(x) mit xk, d.h. hänge k Nullen an M(x) an.
Sei T (x) dieses Produkt.
2. Teile T (x) durch C(x) und berechne den Rest R(x).
3. Subtrahiere den Rest R(x) von T (x). Das Ergebnis ist das
gesuchte M'(x).
Was wird also übertragen, wenn gilt:
1)
M (x) = 1 0 0 1 1 0 1 0
C (x) = 1 1 0 1
M' (x) = ?
1)
Was wird also übertragen, wenn gilt:
M(x) = 1 0 0 1 1 0 1 0 und C(x) = 1 1 0 1 = 1∙x3 + 1∙x2 +0∙x1 +1∙x0 => x3+x2+x0
C(x) ist vom Grad 3, also an M(x) 3 Nullen anhängen.
=> T(x) = 1 0 0 1 1 0 1 0 0 0 0
T (x) : 1 0 0 1 1 0 1 0 0 0 0
C (x) : 1 1 0 1
1 0 0 1 1 0 1 0 0 0 0 : 1 1 0 1 = 1 1 1 1 1 0 0 1← Quotient Q(x)
1101
1001
1101
1000
1101
1011
1101
1100
1101
1000
1101
1 0 1 ← Rest R (x)
1)
M(x) = 1 0 0 1 1 0 1 0 und C(x) = 1 1 0 1
C(x) ist vom Grad 3, also an M(x) 3 Nullen anhängen.
=> T(x) = 1 0 0 1 1 0 1 0 0 0 0
R(x) = 1 0 1
=> M'(x) = T(x) − R(x) = 1 0 0 1 1 0 1 0 0 0 0 − 1 0 1
M'(x)
=10011010101
T (x) : 1 0 0 1 1 0 1 0 0 0 0
C (x) : 1 1 0 1
1 0 0 1 1 0 1 0 1 0 1 : 1 1 0 1 = 1 1 1 1 1 0 0 1 ← Q(x)
1101
1001
1101
1000
1101
1011
1101
1100
1101
1101
1101
0 ← R (x)
Welche Fehler können mit CRC erkannt werden?
●
●
Alle Einzelbitfehler, solange die Terme xk und x0 Koeffizienten ungleich Null
haben.
Alle Doppelbitfehler, solange C(x) einen Faktor mit mindestens drei
Termen hat.
●
Jede ungerade Fehlerzahl, solange C(x) den Faktor (x + 1) enthält.
●
Jeden Burstfehler, bei denen die Burstlänge weniger als k Bit beträgt.
Leichte Hardware-Implementation mittels Master-Slave Flip-Flops und XOR-Gattern
●
XOR-Gatter vor Bit n, wenn im Generator der Term xn enthalten ist
●
Nachricht bitweise einschieben
●
Rest steht zum Schluß in Master-Slave-Flip-Flops
●
Anzahl Flip-Flops
: → Anzahl Bits - 1,
XOR-Gatter () : → vor jedem Term xn (Anzahl Einsen - 1)
●
Beispiel: Generator x5  x4  x2  x0 (110101)
●
Es werden 5 Flip-Flops und 3 XOR Gatter benötigt.