Click here to load reader

Polynom Division Modulo 2 - Uni Koblenz-Landau unikorn/lehre/gdrn/ss15/03... · PDF file Polynom‐Division Modulo 2 Grundlagen der Rechnernetze ‐Übertragungssicherung 14 X6 +

  • View
    1

  • Download
    0

Embed Size (px)

Text of Polynom Division Modulo 2 - Uni Koblenz-Landau unikorn/lehre/gdrn/ss15/03... · PDF file...

  • 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 

  • 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 Polynome CRC‐12 =  X12 + X11 + X3 + X2 + 1 CRC‐16 =  X16 + X15 + X2 + 1 CRC‐CCITT =  X16 + X12 + X5 + 1 CRC‐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 19 Bildquelle: William Stallings, „Data and Computer Communications“, 2004

    SS 2012

  • Beispiel Two‐Dimensional‐Parity

    Grundlagen der Rechnernetze ‐ Übertragungssicherung 20

    0 1 0 1 1 1 1 0 0 1 1 0 1 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 Übertragung im Falle keiner Bitfehler

    Block‐Codes

    Grundlagen der Rechnernetze ‐ Übertragungssicherung 23

    Datenblock Codewort 00 -> 00000 01 -> 00111 10 -> 11001 11 -> 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 Codewort 00 -> 00000 01 -> 00111 10 -> 11001 11 -> 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     11 Daten‐Bits Check‐Bits

    3 = 0 0 1 1 5 = 0 1 0 1 6 = 0 1 1 0 7 = 0 1 1 1 9 = 1 0 0 1

    10 = 1 0 1 0 11 = 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 1 1       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

    Original Code‐Wort

    Ein‐Bit‐Fehler

    3 = 0 0 1 1 5 = 0 1 0 1 6 = 0 1 1 0 7 = 0 1 1 1 9 = 1 0 0 1

    10 = 1 0 1 0 11 = 1 0 1 1

    Check Ergebnis

    Daten‐Bits Check‐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 ≤ 2r Beispiel für unten abgebildeten Hamming‐Code:

    1       2        3       4       5       6        7       8       9       10     11     12     13     14     15 Daten‐Bits Check‐Bits

    Was wenn Daten nur bis 11?

    SS 2012

  • Umgang mit Bit‐Fehler‐Bursts

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

    Also:

    SS 2012

Search related