Fehlererkennende Codes

Paritätsprüfung

• Paritätsbit / Prüfbits• Ergänzt Bitsumme zu gerader (even) oder

ungerader (odd) Anzahl unterschiedliche Paritätsprotokolle

• Ungerade Anzahl von Bitfehlern kann erkannt, aber nicht behoben werden

• Weiterentwicklungen: Hamming-Code, ECC

Beispiel (even)10011101 | P = 1 (5 Einsen)10100110 | P = 0 (4 Einsen)

10

Fehlererkennende Codes

Hamming-Distanz

• Richard W. Hamming (1915 – 1998)

• Hamming-Distanz zweier binärer Blöcke gleicher Länge ergibt sich aus Anzahl der Nicht-Übereinstimmungen im bitweisen Vergleich( Einsen bei XOR-Operation)

• Hamming-Distanz eines Codes aus Wörtern gleicher Länge: Minimum der paarweisen Hamming-Distanzen

Fehlererkennende Codes

Hamming-Distanz

• kleine Hamming-Distanz Fehlerkorrektur schwieriger

• Allgemein: um r Bitfehler korrigieren zu können, muss für die Hamming-Distanz h eines Codesgelten:

h ≤ 2r + 1

Beispielh = 3, c = {010, 101} alle ungültigen Code- wörter können erkannt und korrigiert werden {000, 110, 011} für 010

Fehlererkennende Codes

Hamming-Code

• Fehlerkorrigierender Code mit Mindest-Hammingabstand von 3

• (7,4) ist einfachster Hamming-Code: 4 Bit Nutzdaten, 3 Prüfbits

• Hamming-Codes sind perfekt, d.h. jedes Wort ist entweder Codewort oder hat Hamming-Abstand von 1 zu gültigen Codewort

• Bits werden durchnummeriert, Positionen mit Zweierpotenz werden Prüfbits

• Paritäten für Reihen von Einzelbits bestimmen( jedes Bit kann in mehrere Prüfbits eingehen)

• Erstellung der Kontrollmatrix, Bestimmung der Prüfbits

Fehlererkennende Codes

Hamming-Code – Beispiel

• (15,11)-Code: 00 01 01 11 00 1

0 0 0 1 0 1 1 P3 1 0 0 P2 1 P1 P0

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

P0 (20 = 1)

P1 (21 = 2)

P2 (22 = 4)

P3 (23 = 8)

Fehlererkennende Codes

Hamming-Code – Beispiel

• (15,11)-Code: 00 01 01 11 00 1

0 0 0 1 0 1 1 P3 1 0 0 P2 1 P1 P0

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

P0 (20 = 1) x

P1 (21 = 2) x

P2 (22 = 4) x

P3 (23 = 8) x

Fehlererkennende Codes

Hamming-Code – Beispiel

• (15,11)-Code: 00 01 01 11 00 1

0 0 0 1 0 1 1 P3 1 0 0 P2 1 P1 P0

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

P0 (20 = 1) x

P1 (21 = 2) x x

P2 (22 = 4) x x

P3 (23 = 8) x x

Fehlererkennende Codes

Hamming-Code – Beispiel

• (15,11)-Code: 00 01 01 11 00 1

0 0 0 1 0 1 1 P3 1 0 0 P2 1 P1 P0

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

P0 (20 = 1) x x

P1 (21 = 2) x x

P2 (22 = 4) x x x

P3 (23 = 8) x x x

Fehlererkennende Codes

Hamming-Code – Beispiel

• (15,11)-Code: 00 01 01 11 00 1

0 0 0 1 0 1 1 P3 1 0 0 P2 1 P1 P0

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

P0 (20 = 1) x x

P1 (21 = 2) x x

P2 (22 = 4) x x x x

P3 (23 = 8) x x x x

Fehlererkennende Codes

Hamming-Code – Beispiel

• (15,11)-Code: 00 01 01 11 00 1

0 0 0 1 0 1 1 P3 1 0 0 P2 1 P1 P0

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

P0 (20 = 1) x x x

P1 (21 = 2) x x x

P2 (22 = 4) x x x x

P3 (23 = 8) x x x x x

Fehlererkennende Codes

Hamming-Code – Beispiel

• (15,11)-Code: 00 01 01 11 00 1

0 0 0 1 0 1 1 P3 1 0 0 P2 1 P1 P0

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

P0 (20 = 1) x x x

P1 (21 = 2) x x x x

P2 (22 = 4) x x x x

P3 (23 = 8) x x x x x x

usw.

Fehlererkennende Codes

Hamming-Code – Beispiel

• (15,11)-Code: 00 01 01 11 00 1

0 0 0 1 0 1 1 P3 1 0 0 P2 1 P1 P0

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

P0 (20 = 1) x x x x x x x x

P1 (21 = 2) x x x x x x x x

P2 (22 = 4) x x x x x x x x

P3 (23 = 8) x x x x x x x x

Fehlererkennende Codes

Hamming-Code – Beispiel

• (15,11)-Code: 00 01 01 11 00 1

0 0 0 1 0 1 1 1 1 0 0 P2 1 P1 P0

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

P0 (20 = 1) x x x x x x x x

P1 (21 = 2) x x x x x x x x

P2 (22 = 4) x x x x x x x x

P3 (23 = 8) x x x x x x x x gerade Anzahl

Fehlererkennende Codes

Hamming-Code – Beispiel

• (15,11)-Code: 00 01 01 11 00 1

0 0 0 1 0 1 1 1 1 0 0 0 1 P1 P0

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

P0 (20 = 1) x x x x x x x x

P1 (21 = 2) x x x x x x x x

P2 (22 = 4) x x x x x x x x

P3 (23 = 8) x x x x x x x x

Fehlererkennende Codes

Hamming-Code – Beispiel

• (15,11)-Code: 00 01 01 11 00 1

0 0 0 1 0 1 1 1 1 0 0 0 1 1 P0

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

P0 (20 = 1) x x x x x x x x

P1 (21 = 2) x x x x x x x x

P2 (22 = 4) x x x x x x x x

P3 (23 = 8) x x x x x x x x

Fehlererkennende Codes

Hamming-Code – Beispiel

• (15,11)-Code: 00 01 01 11 00 1

• P0 = 1, P1 = 1, P2 = 0, P3 = 1

0 0 0 1 0 1 1 1 1 0 0 0 1 1 1

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

P0 (20 = 1) x x x x x x x x

P1 (21 = 2) x x x x x x x x

P2 (22 = 4) x x x x x x x x

P3 (23 = 8) x x x x x x x x

Fehlererkennende Codes

Hamming-Code – Beispiel (Erkennung)

• (15,11)-Code: 000 101 110 000 111

0 0 0 1 0 1 1 1 0 0 0 0 1 1 1

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

P0 (20 = 1) x x x x x x x x

P1 (21 = 2) x x x x x x x x

P2 (22 = 4) x x x x x x x x

P3 (23 = 8) x x x x x x x x

Fehler bei P0, P1 und P2

Fehler an Stelle 20 + 21 + 22 = 1 + 2 + 4 = 7

Fehlererkennende Codes

CRC – zyklische Redundanzprüfung

• CRC beruht auf Polynomdivision, d.h. Folge von zu übertragenden Bits wird als Polynom betrachtet

Ablauf1. Bitfolge wird um Grad(G(x)) Nullen ergänzt und

durch festgelegtes Polynom G(x) (Generatorpolynom) geteilt (mit Rest!)

2. Rest wird bei Übertragung an Datenblock angehängt

3. Empfangener Datenblock wird wieder durch Generatorpolynom geteilt, bei fehlerfreier Übertragung bleibt Rest 0

Fehlererkennende Codes

CRC – BeispielDatenframe: 1101011011Generator: G(x) = x4 + x + 1 (10011)

1101011011

Fehlererkennende Codes

CRC – BeispielDatenframe: 1101011011Generator: G(x) = x4 + x + 1 (10011)

11010110110000

Fehlererkennende Codes

CRC – BeispielDatenframe: 1101011011Generator: G(x) = x4 + x + 1 (10011)

1101011011000010011 10011

Fehlererkennende Codes

CRC – BeispielDatenframe: 1101011011Generator: G(x) = x4 + x + 1 (10011)

1101011011000010011 10011 10011 10110

Fehlererkennende Codes

CRC – BeispielDatenframe: 1101011011Generator: G(x) = x4 + x + 1 (10011)

1101011011000010011 10011 10011 10110 10011 10100

Fehlererkennende Codes

CRC – BeispielDatenframe: 1101011011Generator: G(x) = x4 + x + 1 (10011)

1101011011000010011 10011 10011 10110 10011 10100 10011 1110

Fehlererkennende Codes

CRC – BeispielDatenframe: 1101011011Generator: G(x) = x4 + x + 1 (10011)

1101011011000010011 10011 10011 10110 10011 10100 10011 1110

AnmerkungBestimmte Generatorpolynomeempirisch besser geeignet CRC-32 CRC-16