Fehlererkennende Codes Paritätsprüfung Paritätsbit / Prüfbits Ergänzt Bitsumme zu gerader...

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)

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

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

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

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)

• (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

• (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

• (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

• (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

• (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

• (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

• (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

• (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

• (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

• (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

• (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

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

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

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

1101011011

11010110110000

1101011011000010011 10011

1101011011000010011 10011 10011 10110

1101011011000010011 10011 10011 10110 10011 10100

1101011011000010011 10011 10011 10110 10011 10100 10011 1110

AnmerkungBestimmte Generatorpolynomeempirisch besser geeignet CRC-32 CRC-16

Fehlererkennende Codes Paritätsprüfung Paritätsbit / Prüfbits Ergänzt Bitsumme zu gerader...

Documents

Modellreihe 551-565 Series 551-565 - myschlick.com · full cone nozzles produce and extremely even full cone. This makes the nozzles much better suited for the even spraying of large

Visualisierungs- und Beratungstool · zum Break-Even 13,73 Jahre 10,97 Jahre Kosten bis zum Break-Even 18.712,33 €13.631,45 Wertung ökologischer ökonomischer • Wir stehen gegenwärtig

จับยามสามตาย · 2015. 7. 15. · จับยามสามตาย Odd Thomas ดีน คูนท์ซ เขียน พรรษพร ชโลธร

LookBook 18 - staeudle.com€¦ · for decorative objects or plants. The use of sturdy casters allows even large structures to be moved around easily on even surfaces. 58 59 Die Tischsysteme

Break-Even-Analyse im Mehrproduktfall unter …...76 Die Ermittlung der Gewinnschwelle (Break-Even-Rechnung) gehört zu einem der beliebtes-ten Instrumente in der Praxis und wird in

ENGINEERING COLLEGES 18 Odd Semester IMPORTANT …

Even-Cosmetics Schulungskatalog

Kompakt-Wissen Hauptschule - Mathematik · Volumen – Mantelfläche – Oberfläche – gerader Kreiszylinder – Kreisringzylinder (Hohlzylinder) ... Den Mantel kann man abwickeln

Folientunnel mit gerader Stehwand - Sabtec...Folientunnel mit gerader Stehwand 640S 960S mit Hebelüftung Typ Breite Höhe Binderabstand Stehwand Durchfahrtshöhe Rovero 640S 6,40m

Booklet zum Joao de Deus Even 16.-18. Juli

Hans J. Even: 10 E-Commerce Trends - TWT

44. Volumen gerader Prismen – Volumseinheiten

Odd Fellows Family Tour 2011 24. bis 26. Juni

Vorlesung OC-V - uni-due.de · Ireland-Claisen-Umlagerung. Vorlesung OC-V Allgemeine Formel der Woodward-Hoffmann-Regeln „odd supra dis even antara con“ Title: PowerPoint-Präsentation

Helles Licht und gerader Weeg zu denen Naturgeheimnüsse

PowerPoint-Präsentationfiles.thinkpool.com/files/bbs/2016/11/28/... · Marktdaten AG Pro Biosimilars 09/2016 . ODD* gesamt patentgeschützte Biopharmazeutika patentfreie Biopharmazeutika

- Gastrobedarf Interlaken AGfiles.hobeda-shop.ch/messerschleifmaschine_tormek.pdf · SVD-110 Vertikal Äxte SVA-170 Vertikal Zimmermannsdexel mit gerader, inwendiger Schneide US-105

EGE-NPT Gerader Einschraubstutzen mit · PDF fileI DIN-Verschraubungen I65 Katalog 4100-9/DE X1) O-Ring OR EGE-NPT Gerader Einschraubstutzen mit Dichtkegel NPT Einschraubzapfen (SAE

Projektspezifische Datenschemata erstellenIDE SummerSchool 2013, Chemnitz Projektspezifische Datenschemata erstellen XML Schema, ROMA/ODD Martina Semlak Zentrum für Informationsmodellierung,

GE-NPT Gerader Einschraubstutzen