 |
FehlererkennungCodes für die Fehlererkennung sind so zu konstruieren, daß h = 2 ist --> "fehlererkennende Codes", "prüfbare Codes". Hierzu gehören z.B. alle m-aus-n-Codes (gleichgewichtige Codes). Es wird dazu die Anzahl der 1-Bits im Codewort überprüft. Ist sie ungleich m, liegt mindestens ein Bitfehler vor. Um eine Anzahl e von Fehlern zu erkennen benötigt man einen Hammingabstand von mindestens e + 1. Es gilt also: e = h - 1 Beispiel: Der Code besteht aus den Codeworten 0000 und 1111. 1111 \__________Störung_____________ 1110 1 Fehler 0000 / 1001 2 Fehler 1000 3 Fehler h = 4 --> e = h - 1 = 3 Welche Möglichkeiten bieten sich?- Fehlererkennung durch Pritätsprüfung (parity check) Ungesicherte Codes (h = 1) können durch die Hinzunahme eines Prüfbits (parity bit) auf h = 2 erweitert werden - 1-Bit-Fehler werden erkannt. Zwei Codeworte, die sich zunächst nur um eine Stelle unterscheiden, unterscheiden sich mit dem Paritätsbit nun um zwei Stellen. Der Wert des Paritätsbits wird folgender- maßen ermittelt:
- gerade Parität (even parity):
Die Anzahl der 1-Bits im erweiterten Codewort ist gerade.
Das Wort wird auf eine gerade Anzahl von 1-Bits erweitert.
- ungerade Parität (odd parity):
Die Anzahl der 1-Bits im erweiterten Codewort ist ungerade.
Das Wort wird auf eine ungerade Anzahl von 1-Bits erweitert.
Die Erweiterung des Codewortes um ein Paritätsbit wird auch
"Querparität" oder "Zeichenparität" genannt. Die
Überprüfung der empfangenen Codeworte kann durch Bildung der Quersumme
(Addition modulo 2, d.h. ohne Berücksichtigung des Übertrags)
erfolgen.
Jede ungeradzahlige Anzahl von 1-Bit-Fehlern im Codewort wird
erkannt, geradzahlige Bitfehlerzahl wird nicht erkannt.
- Fehlererkennung durch Prüfzeichen
Mehrere ungesicherte Codeworte bilden einen (Daten-)Block (in
der Praxis zwischen 16 und 64 Codeworte). Über die gleichwertigen
Stellen der Codeworte eines Blocks wird die Parität gebildet.
Diese Paritätsbits geben dann die Blockparität. Auch hier
ist gerade und ungerade Parität möglich. --> Längsparität,
LRC (longitudinal redundancy check). Durch die Blockparität wird
der Hammingabstand ganzer Datenblöcke vergrößert.
Beispiel "ASCII", gerade Parität:
A 1 0 0 0 0 0 1
S 1 0 1 0 0 1 1
C 1 0 0 0 0 1 1
I 1 0 0 1 0 0 1
I 1 0 0 1 0 0 1
-----------------------
Parity: 1 0 1 0 0 0 1
- Was tun nach Erkennen eines Fehlers?
- Ausgabe einer Fehlernachricht
- Wiederholungsaufforderung
- Prüfziffern
Eine Prüfziffer wird an das eigentliche Codewort angehängt und
zusammen mit dem Code übermittelt. Stimmt die gelesene Prüfziffer
nicht mit der vom Decoder errechneten überein, wird der
Code nicht akzeptiert. Verwendung z. B. bei Strichcodes oder
der ISBN (Internationale Standard-Buchnummer). Das folgende
Beispiel zeigt die Prüfziffernrechnung Modulo 10, Wichtung 3:
- Quersumme aller Ziffern in ungerader Position
- Quersumme aller Ziffern in gerader Position
- Multiplikation von b) mit 3
- Summe von a) und c)
- Differenz von d) zum nächsten Vielfachen von 10
Beispiel: 8 6 1 3 2 5 1 8
a) 8 + 1 + 2 + 1 = 12
b) 6 + 3 + 5 + 8 = 22
c) 22 * 3 = 26
d) 12 + 26 = 78
e) 80 - 78 = 2
- Prüfsumme bei Datenblöcken
Alle Datenworte werden aufsummiert und diese Summe an den Datenblock
angehängt. Auf Empfängerseite wird ebenfalls summiert
--> beide Summen müssen gleich sein. Oft wird die Summe auf die
Wortbreite der Datenworte "gekappt" (Prüfsumme modulo M).
Beispiel: Strichcode
Am interessantesten ist sicher der EAN-Code, den es in 13- oder
8-stelliger Version gibt. Dieser Code hat zugleich auch den kompliziertesten
Aufbau, denn er soll das Lesen in beiden Richtungen
ermöglichen. Beim EAN-13 werden nur zwölf der dreizehn Ziffern
direkt codiert, damit sich der Codeblock in zwei Hälften unterteilen
läßt. Die Codierung der 13. Ziffer wird dann in der linken
Hälfte "versteckt". Betrachten wir den EAN-Code nun genauer.
Ein Zeichen, d. h. die Codierung einer Ziffer besteht aus verschieden
breiten Balken und Zwischenräumen, wobei sich jedes
Zeichen aus der Kombination von 7 Balken/Zwischenräumen fester
Breite zusammensetzt. Die Breite eines solchen Elements, eines
Moduls, ist konstant. Um linke und rechte Hälfte des Codes
unterscheiden zu können, werden die Zahlen links und
rechts unterschiedlich codiert, wobei die Codierung der linken
Hälfte wieder mit zwei unterschiedlichen Zeichensätzen
erfolgt. Es gibt also drei verschiede Zeichensätze. Sehen Sie
sich dazu einmal die Codierung der "0" an:
Die gesamte Codetabelle ist weiter unten abgedruckt. (0 = weiß,
1 = schwarz). Nun ist noch zu klären, wo die 13. Ziffer versteckt
wird (es ist übrigens die ganz links vor dem Code gedruckte
Ziffer). Diese Ziffer wird durch die Kombination von Zeichensatz
A und B in der linken Hälfte des Barcodes festgelegt. Wie
die Zuordnung ist, zeigt die zweite Tabelle unten. Der EAN-8-Code
besteht nur aus zwei Blöcken zu je 4 Zeichen aus den
Zeichensätzen A (links) und C (rechts).
Die drei Zeichensätze des EAN-Barcodes
| | Zeichensatz A | Zeichensatz B | Zeichensatz C |
|---|
| 0 | 0 0 0 1 1 0 1 | 0 1 0 0 1 1 1 | 1 1 1 0 0 1 0 |
| 1 | 0 0 1 1 0 0 1 | 0 1 1 0 0 1 1 | 1 1 0 0 1 1 0 |
| 2 | 0 0 1 0 0 1 1 | 0 0 1 1 0 1 1 | 1 1 0 1 1 0 0 |
| 3 | 0 1 1 1 1 0 1 | 0 1 0 0 0 0 1 | 1 0 0 0 0 1 0 |
| 4 | 0 1 0 0 0 1 1 | 0 0 1 1 1 0 1 | 1 0 1 1 1 0 0 |
| 5 | 0 1 1 0 0 0 1 | 0 1 1 1 0 0 1 | 1 0 0 1 1 1 0 |
| 6 | 0 1 0 1 1 1 1 | 0 0 0 0 1 0 1 | 1 0 1 0 0 0 0 |
| 7 | 0 1 1 1 0 1 1 | 0 0 1 0 0 0 1 | 1 0 0 0 1 0 0 |
| 8 | 0 1 1 0 1 1 1 | 0 0 0 1 0 0 1 | 1 0 0 1 0 0 0 |
| 9 | 0 0 0 1 0 1 1 | 0 0 1 0 1 1 1 | 1 1 1 0 1 0 0 |
Codierung des 13. Zeichens
| 0 | A A A A A A |
| 1 | A A B A B B |
| 2 | A A B B A B |
| 3 | A A B B B A |
| 4 | A B A A B B |
| 5 | A B B A A B |
| 6 | A B B B A A |
| 7 | A B A B A B |
| 8 | A B A B B A |
| 9 | A B B A B A |
Von links nach rechts besteht der gesamte EAN-13-Barcode aus:
- Randzeichen aus drei Modulen (101)
- sechs Nutzzeichen aus je 7 Modulen der Zeichensätze A und B
- Trennzeichen aus fünf Modulen (01010)
- sechs Nutzzeichen aus je 7 Modulen des Zeichensatzes C
- Randzeichen aus drei Modulen (101)
Die letzte Ziffer (ganz rechts) ist eine Prüfziffer, die
folgendermaßen ermittelt wird:
- Quersumme aller Ziffern in ungerader Position
- Quersumme aller Ziffern auf gerader Position
- Ergebnis von b) multipliziert mit 3
- Summe von a) und c)
- Differenz von d) zum nächsten Vielfachen von 10
(ergibt sich hier 10, wird die Prüfziffer 0 genommen)
Beispiel:
Code: 0 1 1 3 7 3 5 5 9 2 4 3 PZ
a) 0 + 1 + 7 + 5 + 9 + 4 = 26
b) 1 + 3 + 3 + 5 + 2 + 3 = 17
c) 17 * 3 = 51
d) 26 + 51 = 77
e) 80 - 77 = 3 --> Prüfziffer 3
Von links nach rechts besteht der gesamte EAN-8-Barcode aus:
- Randzeichen aus drei Modulen (101)
- vier Nutzzeichen aus je 7 Modulen des Zeichensatzes A
- Trennzeichen aus fünf Modulen (01010)
- vier Nutzzeichen aus je 7 Modulen des Zeichensatzes C
- Randzeichen aus drei Modulen (101)
Auch hier ist wieder das letzte Zeichen ganz links ein Prüfzeichen
zur Fehlererkennung.
|
|
|
DIENSTE
