16
PolynomDivision Modulo 2 Grundlagen der Rechnernetze Übertragungssicherung 14 X 6 + X 4 + X 2 + X 1 + 1 : X 3 + X 2 + 1 = SS 2012

Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

Polynom‐Division Modulo 2

Grundlagen der Rechnernetze ‐ Übertragungssicherung 14

X6 + X4 + X2 + X1 + 1 : X3 + X2 + 1 =

SS 2012

Page 2: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

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

Page 3: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

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

Page 4: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

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

Page 5: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

Fehlerkorrektur

Grundlagen der Rechnernetze ‐ Übertragungssicherung 18SS 2012

Page 6: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

Ablauf der Fehlerkorrektur

Grundlagen der Rechnernetze ‐ Übertragungssicherung 19Bildquelle: William Stallings, „Data and Computer Communications“, 2004

SS 2012

Page 7: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

Beispiel Two‐Dimensional‐Parity

Grundlagen der Rechnernetze ‐ Übertragungssicherung 20

0 1 0 11 1 1 00 1 1 01 0 0 1

SS 2012

Page 8: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

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

Page 9: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

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

Page 10: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

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

Page 11: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

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

Page 12: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

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

Page 13: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

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

Page 14: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

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

Page 15: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

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

Page 16: Polynom Division Modulo 2 - Uni Koblenz-Landauunikorn/lehre/gdrn/ss15/03... · Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 + X4 + X2 +

Umgang mit Bit‐Fehler‐Bursts

Grundlagen der Rechnernetze ‐ Übertragungssicherung 29Bildquelle: Andrew S. Tanenbaum, „Computer Networks“, Fourth Edition, 2003

Also:

SS 2012