Kapitel 5 Fehlererkennende Codes. Kapitel 5 © Beutelspacher Juni 2004 Seite 2 Inhalt 5.1 Grundlagen: Was sind Vehler? 5.2 Vertuaschungsfehler 5.3 Der

Kapitel 5

Fehlererkennende Codes

Kapitel 5

Fehlererkennende Codes

Kapitel 5 © Beutelspacher

Juni 2004Seite 2

InhaltInhalt

5.1 Grundlagen: Was sind Vehler?

5.2 Vertuaschungsfehler

5.3 Der ISBN-Code

3-406-45404-6

5.4 Der EAN-Code („Strichcode“)

5.1 Grundlagen: Was sind Vehler?

5.2 Vertuaschungsfehler

5.3 Der ISBN-Code

3-406-45404-6

5.4 Der EAN-Code („Strichcode“)


Juni 2004Seite 3

5.1 Grundlagen: Was sind Vehler? 5.1 Grundlagen: Was sind Vehler?

Bei der Speicherung und Übertragung von Daten (Texten, Zahlen)

entstehen Fehler: Zeichen können verändert werden, vertauscht

werden, wegfallen usw.: Vehler, Feler, Fehlerrr, ...

Definition: Ein Fehler eines Textes (d.h. Buchstaben oder

Zahlenfolge) besteht (für uns) darin,

dass ein oder mehrerer Zeichen verändert werden

(d.h. zu anderen Zeichen werden).

Ziel: Der Empfänger soll erkennen können:

ob ein (oder mehrere) Fehler passiert sind (Fehlererkennung)

wie die Originalzeichen aussehen (Fehlerkorrektur).

Bei der Speicherung und Übertragung von Daten (Texten, Zahlen)

entstehen Fehler: Zeichen können verändert werden, vertauscht

werden, wegfallen usw.: Vehler, Feler, Fehlerrr, ...

Definition: Ein Fehler eines Textes (d.h. Buchstaben oder

Zahlenfolge) besteht (für uns) darin,

dass ein oder mehrerer Zeichen verändert werden

(d.h. zu anderen Zeichen werden).

Ziel: Der Empfänger soll erkennen können:

ob ein (oder mehrere) Fehler passiert sind (Fehlererkennung)

wie die Originalzeichen aussehen (Fehlerkorrektur).


Juni 2004Seite 4

Die MethodeDie Methode

Grundidee: Man fügt der Nachricht etwas hinzu,

eine „Kontrollinformation“, die dazu dient,

eventuelle Übertragungsfehler zu erkennen.

Beispiele:

Namen buchstabieren („Emm o enn enn te a ge“)

Buchstabieralphabete („A wie Anton, B wie Berta, ...“)

Natürliche Sprachen sind redundant (haben überflüssige

Information): man vrsteht alls, auc wnn einge Bchstbn fhln.

Selpst wen groppe recktscreib Felr auftren, ged dr ßinn nich färlohn.

Grundidee: Man fügt der Nachricht etwas hinzu,

eine „Kontrollinformation“, die dazu dient,

eventuelle Übertragungsfehler zu erkennen.

Beispiele:

Namen buchstabieren („Emm o enn enn te a ge“)

Buchstabieralphabete („A wie Anton, B wie Berta, ...“)

Natürliche Sprachen sind redundant (haben überflüssige

Information): man vrsteht alls, auc wnn einge Bchstbn fhln.

Selpst wen groppe recktscreib Felr auftren, ged dr ßinn nich färlohn.


Juni 2004Seite 5

Die PrüfzifferDie Prüfziffer

Beispiel: Wir wollen 4-stellige Zahlen übermitteln. Der Empfänger

soll merken, ob die Daten korrekt sind.

Da man dies an den Daten selbst nicht erkennen kann, fügt man

eine Ziffer hinzu (man erhält also eine 5-stellige Zahl), und zwar so,

dass die Quersumme dieser Zahl eine Zehnerzahl ist.

Die Ziffer an der hinzugefügten Stelle heißt Prüfziffer.

Konkret: man bestimmt die Summe der ersten vier Ziffern und

ergänzt diese Summe durch die Prüfziffer zur nächsten Zehnerzahl.

Beispiel: Wenn die Daten die Zahl 1234 sind, so ist die Prüfziffer 0;

der Datensatz 4813 hat die Prüfziffer 4.

Übermittelt wird dann die Folge 12340 bzw. 48134

Beispiel: Wir wollen 4-stellige Zahlen übermitteln. Der Empfänger

soll merken, ob die Daten korrekt sind.

Da man dies an den Daten selbst nicht erkennen kann, fügt man

eine Ziffer hinzu (man erhält also eine 5-stellige Zahl), und zwar so,

dass die Quersumme dieser Zahl eine Zehnerzahl ist.

Die Ziffer an der hinzugefügten Stelle heißt Prüfziffer.

Konkret: man bestimmt die Summe der ersten vier Ziffern und

ergänzt diese Summe durch die Prüfziffer zur nächsten Zehnerzahl.

Beispiel: Wenn die Daten die Zahl 1234 sind, so ist die Prüfziffer 0;

der Datensatz 4813 hat die Prüfziffer 4.

Übermittelt wird dann die Folge 12340 bzw. 48134


Juni 2004Seite 6

CodeCode

Man spricht von einem Code. Im Beispiel ist der Code die Menge

aller 5-stelligen Zahlen, deren Quersumme durch 10 teilbar ist:

C = {a1a2a3a4a5 ai {0, 1, ..., 9}, a1+a2+a3+a4+a5 ist durch 10 teilb.}.

Die Elemente eines Codes nennt man Codewörter.

Der Empfänger akzeptiert eine Nachricht nur,

wenn sie ein Codewort ist.

Konkret: Der Empfänger summiert die Ziffern (inklusive der

Prüfziffer). Er akzeptiert die Nachricht nur, wenn dies eine

Zehnerzahl ist.

Beispiel: 12340 wird akzeptiert 12840 nicht.

Man spricht von einem Code. Im Beispiel ist der Code die Menge

aller 5-stelligen Zahlen, deren Quersumme durch 10 teilbar ist:

C = {a1a2a3a4a5 ai {0, 1, ..., 9}, a1+a2+a3+a4+a5 ist durch 10 teilb.}.

Die Elemente eines Codes nennt man Codewörter.

Der Empfänger akzeptiert eine Nachricht nur,

wenn sie ein Codewort ist.

Konkret: Der Empfänger summiert die Ziffern (inklusive der

Prüfziffer). Er akzeptiert die Nachricht nur, wenn dies eine

Zehnerzahl ist.

Beispiel: 12340 wird akzeptiert 12840 nicht.


Juni 2004Seite 7

Definition eines ParitätscodesDefinition eines Paritätscodes

Definition. Man bezeichnet die Menge

C = {a1a2... an ai {0, 1, ..., 9}, a1+ a2+ ... + an ist durch 10 teilbar}

als Paritätscode der Länge n zur Basis 10.

5.1.1 Satz: Jeder Paritätscode erkennt Einzelfehler.

Beweis. Sei a1a2...an ein Codewort. Dann ist a1+a2+...+ an durch

10 teilbar. Es sei ein Fehler der ersten Stelle aufgetreten. D.h. a1

wurde in eine andere Ziffer a1' a1 verwandelt.

Angenommen, auch a1’a2...an wäre ein Codewort. Dann wäre auch

a1’+a2+ ...+an durch 10 teilbar.

Definition. Man bezeichnet die Menge

C = {a1a2... an ai {0, 1, ..., 9}, a1+ a2+ ... + an ist durch 10 teilbar}

als Paritätscode der Länge n zur Basis 10.

5.1.1 Satz: Jeder Paritätscode erkennt Einzelfehler.

Beweis. Sei a1a2...an ein Codewort. Dann ist a1+a2+...+ an durch

10 teilbar. Es sei ein Fehler der ersten Stelle aufgetreten. D.h. a1

wurde in eine andere Ziffer a1' a1 verwandelt.

Angenommen, auch a1’a2...an wäre ein Codewort. Dann wäre auch

a1’+a2+ ...+an durch 10 teilbar.


Juni 2004Seite 8

Beweis (Fortsetzung)Beweis (Fortsetzung)

Dann ist (2.1.1) auch die Differenz (a1 + a2 + ... + an) – (a1' + a2 + ... + an) = a1 – a1‘

durch 10 teilbar.

Da a1 und a1‘ Ziffern aus {0, 1, ..., 9} sind, muss gelten:

–9 a1 – a1‘ 9.

Die einzige Zahl in diesem Bereich, die durch 10 teilbar ist, ist 0.

Also folgt: a1 – a1‘ = 0, d.h. a1 = a1‘.

Das ist ein Widerspruch, also ist a1’a2...an kein Codewort.

Dann ist (2.1.1) auch die Differenz (a1 + a2 + ... + an) – (a1' + a2 + ... + an) = a1 – a1‘

durch 10 teilbar.

Da a1 und a1‘ Ziffern aus {0, 1, ..., 9} sind, muss gelten:

–9 a1 – a1‘ 9.

Die einzige Zahl in diesem Bereich, die durch 10 teilbar ist, ist 0.

Also folgt: a1 – a1‘ = 0, d.h. a1 = a1‘.

Das ist ein Widerspruch, also ist a1’a2...an kein Codewort.


Juni 2004Seite 9

5.2 Vertuaschungsfehler5.2 Vertuaschungsfehler

Definition. Wir sagen: Ein Code C erkennt Vertauschungsfehler,

falls für jedes Codewort a1a2... aiai+1...an gilt: Die durch Vertau-schung

der Elemente ai und ai+1 (mit ai ai+1) erzeugte Folge a1a2...

ai+1ai...an ist kein Codewort.

Die bisherigen Paritätscodes erkennen keine Vertauschungsfehler. Da

3 + 5 = 5 + 3 ist, kann man 35 53 nicht erkennen.

Wunsch: Die einzelnen Stellen sollen unterschiedlich „stark“ in die

Quersumme eingehen.

Idee: Jede Stelle wird mit einem „Gewicht” versehen. Die

entsprechende Ziffer wird mit diesem Gewicht multipliziert,

bevor sie in die Quersumme eingeht.

Definition. Wir sagen: Ein Code C erkennt Vertauschungsfehler,

falls für jedes Codewort a1a2... aiai+1...an gilt: Die durch Vertau-schung

der Elemente ai und ai+1 (mit ai ai+1) erzeugte Folge a1a2...

ai+1ai...an ist kein Codewort.

Die bisherigen Paritätscodes erkennen keine Vertauschungsfehler. Da

3 + 5 = 5 + 3 ist, kann man 35 53 nicht erkennen.

Wunsch: Die einzelnen Stellen sollen unterschiedlich „stark“ in die

Quersumme eingehen.

Idee: Jede Stelle wird mit einem „Gewicht” versehen. Die

entsprechende Ziffer wird mit diesem Gewicht multipliziert,

bevor sie in die Quersumme eingeht.


Juni 2004Seite 10

Beispiel (Kontonummern, Loknummern ...) Beispiel (Kontonummern, Loknummern ...)

(Konto)nummer ohne Prüfziffer: 1 8 9 8 2 8 0 1

Gewichtung 1 2 1 2 1 2 1 2

Produkte (Ziffer Gewicht) 1 16 9 16 2 16 0 2

Dann wird die Summe S dieser Produkte bestimmt; es ergibt sich

S = 1 + 16 + 9 + 16 + 2 + 16 + 0 + 2 = 62.

Diese Zahl wird durch die Prüfziffer zur nächsten Zehnerzahl ergänzt.

Die Prüfziffer ist also gleich 8,

und die vollständige Kontonummer lautet 189 828 018.

(Konto)nummer ohne Prüfziffer: 1 8 9 8 2 8 0 1

Gewichtung 1 2 1 2 1 2 1 2



S = 1 + 16 + 9 + 16 + 2 + 16 + 0 + 2 = 62.





Juni 2004Seite 11

Code 1Code 1

Wir beschreiben diesen Code („Code 1”) formal:

C1 = {a1a2a3a4a5a6a7a8a9 10 teilt a1 + 2a2 + a3 + 2a4 + a5 + 2a6 + a7 + 2a8 + a9}.

Vorteil: In diesem Code 1 können wir prinzipiell Vertauschungsfehler

erkennen, da benachbarte Stellen verschieden gewichtet werden.

Nachteil: Code 1 erkennt nicht alle Einzelfehler!

Wenn an einer mit 2 gewichteten Stelle die Zahl 8 mit der Zahl 3

vertauscht wird, so liefert die 8 den Beitrag 16, die Zahl 3 den

Beitrag 6 zur Summe S; also ergibt sich die gleiche Prüfziffer.

Ebenso werden 7 2, 6 1, 5 0 und 9 4 nicht erkannt.

Wir beschreiben diesen Code („Code 1”) formal:

C1 = {a1a2a3a4a5a6a7a8a9 10 teilt a1 + 2a2 + a3 + 2a4 + a5 + 2a6 + a7 + 2a8 + a9}.

Vorteil: In diesem Code 1 können wir prinzipiell Vertauschungsfehler

erkennen, da benachbarte Stellen verschieden gewichtet werden.

Nachteil: Code 1 erkennt nicht alle Einzelfehler!

Wenn an einer mit 2 gewichteten Stelle die Zahl 8 mit der Zahl 3

vertauscht wird, so liefert die 8 den Beitrag 16, die Zahl 3 den

Beitrag 6 zur Summe S; also ergibt sich die gleiche Prüfziffer.

Ebenso werden 7 2, 6 1, 5 0 und 9 4 nicht erkannt.


Juni 2004Seite 12

Code 2Code 2

Kontonummer ohne Prüfziffer: 1 8 9 8 2 8 0 1

Gewichtung 1 2 1 2 1 2 1 2


Quersummen dieser Produkte 1 7 9 7 2 7 0 2

Dann wird die Summe S dieser Quersummen bestimmt:

S = 1 + 7 + 9 + 7 + 2 + 7 + 0 + 2 = 35.


Die Prüfziffer ist also 5,


Kontonummer ohne Prüfziffer: 1 8 9 8 2 8 0 1

Gewichtung 1 2 1 2 1 2 1 2


Quersummen dieser Produkte 1 7 9 7 2 7 0 2

Dann wird die Summe S dieser Quersummen bestimmt:

S = 1 + 7 + 9 + 7 + 2 + 7 + 0 + 2 = 35.


Die Prüfziffer ist also 5,



Juni 2004Seite 13

Code 2 erkennt EinzelfehlerCode 2 erkennt Einzelfehler

5.2.1 Satz. Der Code 2 erkennt alle Einzelfehler.

Beweis. Stellen, die mit 1 gewichtet sind: o.k. (vergleiche 3.2.1.)

Wir betrachten eine mit 2 gewichtete Stelle. Zu zeigen: Die Quer-

summen des Doppelten der Ziffern sind verschieden. (Das ist der

Beitrag, der von dieser Stelle in die Summe S eingeht. Wenn diese

Zahlen alle verschieden sind, dann werden alle Einzelfehler erkannt.)

Ziffer 0 1 2 3 4 5 6 7 8 9

Produkt (Ziffer Gewicht) 0 2 4 6 8 10 12 14 16 18

Quersumme des Produkts 0 2 4 6 8 1 3 5 7 9

5.2.1 Satz. Der Code 2 erkennt alle Einzelfehler.

Beweis. Stellen, die mit 1 gewichtet sind: o.k. (vergleiche 3.2.1.)

Wir betrachten eine mit 2 gewichtete Stelle. Zu zeigen: Die Quer-

summen des Doppelten der Ziffern sind verschieden. (Das ist der

Beitrag, der von dieser Stelle in die Summe S eingeht. Wenn diese

Zahlen alle verschieden sind, dann werden alle Einzelfehler erkannt.)

Ziffer 0 1 2 3 4 5 6 7 8 9

Produkt (Ziffer Gewicht) 0 2 4 6 8 10 12 14 16 18

Quersumme des Produkts 0 2 4 6 8 1 3 5 7 9


Juni 2004Seite 14

5.3 Der ISBN-Code5.3 Der ISBN-Code

ISBN = Internationale Standard Buch Nummer

Jede ISBN hat zehn Stellen, die in vier Gruppen eingeteilt sind.

Erste Gruppe: Sprachraum (0, 1: englisch, 2: französisch, 3:

deutsch, ..., 88: italienisch, ...)

Zweite Gruppe: Verlag (528: Verlag Vieweg)

Dritte Gruppe: Nummer des Buches (z.B. 16783: „In Mathe war ich

immer schlecht ...“).

Vierte Gruppe: Prüfsymbol.

ISBN = Internationale Standard Buch Nummer

Jede ISBN hat zehn Stellen, die in vier Gruppen eingeteilt sind.

Erste Gruppe: Sprachraum (0, 1: englisch, 2: französisch, 3:

deutsch, ..., 88: italienisch, ...)

Zweite Gruppe: Verlag (528: Verlag Vieweg)

Dritte Gruppe: Nummer des Buches (z.B. 16783: „In Mathe war ich

immer schlecht ...“).

Vierte Gruppe: Prüfsymbol.


Juni 2004Seite 15

Berechnung des PrüfsymbolsBerechnung des Prüfsymbols

Sei a1a2a3... a9a10 eine ISBN (also ist a10 das Prüfsymbol). Dieses

wird so bestimmt, dass die Zahl

10a1 + 9a2 + 8a3 + 7a4 + 6a5 + 5a6 + 4a7 + 3a8 + 2a9 +

1a10

eine Elferzahl ist. Das bedeutet: Man bestimmt die Zahl

S = 10a1 + 9a2 + 8a3 + 7a4 + 6a5 + 5a6 + 4a7 + 3a8 + 2a9

und ergänzt diese durch das Prüfsymbol a10 zur nächsten Elferzahl.

Welche Werte kann a10 annehmen? 0, 1, 2, 3, ..., 9 oder 10.

Wenn sich 10 ergibt, so schreibt man X (römische Zehn).

Sei a1a2a3... a9a10 eine ISBN (also ist a10 das Prüfsymbol). Dieses

wird so bestimmt, dass die Zahl

10a1 + 9a2 + 8a3 + 7a4 + 6a5 + 5a6 + 4a7 + 3a8 + 2a9 +

1a10

eine Elferzahl ist. Das bedeutet: Man bestimmt die Zahl

S = 10a1 + 9a2 + 8a3 + 7a4 + 6a5 + 5a6 + 4a7 + 3a8 + 2a9

und ergänzt diese durch das Prüfsymbol a10 zur nächsten Elferzahl.

Welche Werte kann a10 annehmen? 0, 1, 2, 3, ..., 9 oder 10.

Wenn sich 10 ergibt, so schreibt man X (römische Zehn).


Juni 2004Seite 16

Qualität des ISBN-CodesQualität des ISBN-Codes

Formale Beschreibung des ISBN-Codes:

CISBN = {a1a2...a10 11 teilt 10a1 + 9a2 + 8a3 + 7a4 + ... + 3a8 + 2a9 + 1a10}.

Dass der ISBN-Code super ist, sagt der folgende Satz:

5.3.1 Satz. (a) Der ISBN-Code erkennt alle Einzelfehler.

(b) Der ISBN-Code erkennt alle Vertauschungsfehler

– sogar an beliebigen Stellen.

Formale Beschreibung des ISBN-Codes:

CISBN = {a1a2...a10 11 teilt 10a1 + 9a2 + 8a3 + 7a4 + ... + 3a8 + 2a9 + 1a10}.

Dass der ISBN-Code super ist, sagt der folgende Satz:

5.3.1 Satz. (a) Der ISBN-Code erkennt alle Einzelfehler.

(b) Der ISBN-Code erkennt alle Vertauschungsfehler

– sogar an beliebigen Stellen.


Juni 2004Seite 17

BeweisBeweis

Beweis. (a): Übungsaufgabe.

(b) Wir zeigen, dass der ISBN-Code jede Vertauschung der ersten

beiden Stelle erkennt. Sei dazu a1a2a3... a9a10 eine ISBN. Also ist

10a1 + 9a2 + 8a3 + 7a4 + 6a5 + 5a6 + 4a7 + 3a8 + 2a9 + 1a10

eine durch 11 teilbare Zahl.

Nun mögen die ersten beiden Ziffern vertauscht werden; es entsteht

also die Folge a2a1a3... a9a10. Wir können a1 a2 voraussetzen.

Angenommen, auch dies wäre ein Codewort. Dann wäre auch

10a2 + 9a1 + 8a3 + 7a4 + 6a5 + 5a6 + 4a7 + 3a8 + 2a9 + 1a10


Beweis. (a): Übungsaufgabe.

(b) Wir zeigen, dass der ISBN-Code jede Vertauschung der ersten

beiden Stelle erkennt. Sei dazu a1a2a3... a9a10 eine ISBN. Also ist

10a1 + 9a2 + 8a3 + 7a4 + 6a5 + 5a6 + 4a7 + 3a8 + 2a9 + 1a10


Nun mögen die ersten beiden Ziffern vertauscht werden; es entsteht

also die Folge a2a1a3... a9a10. Wir können a1 a2 voraussetzen.

Angenommen, auch dies wäre ein Codewort. Dann wäre auch

10a2 + 9a1 + 8a3 + 7a4 + 6a5 + 5a6 + 4a7 + 3a8 + 2a9 + 1a10



Juni 2004Seite 18

Beweis (Fortsetzung)Beweis (Fortsetzung)

Zusammen folgt mit 2.1.2, dass 11 auch folgende Zahl teilt:

10a1 + 9a2 – (10a2 + 9a1) = a1 – a2.

Nun argumentieren wir wie im Beweis von 3.4.1:

Da a1 und a2 beide zwischen 0 und 9 liegen,

ist die Differenz a1 – a2 eine Zahl zwischen –9 und +9.

Die einzige durch 11 teilbare Zahl in diesem Bereich ist aber 0.

Daher ist a1 – a2 = 0, das heißt a1 = a2.

Dieser Widerspruch zeigt, dass der ISBN-Code Vertauschungen der

ersten beiden Stellen 100%ig erkennt.

Zusammen folgt mit 2.1.2, dass 11 auch folgende Zahl teilt:

10a1 + 9a2 – (10a2 + 9a1) = a1 – a2.

Nun argumentieren wir wie im Beweis von 3.4.1:

Da a1 und a2 beide zwischen 0 und 9 liegen,

ist die Differenz a1 – a2 eine Zahl zwischen –9 und +9.

Die einzige durch 11 teilbare Zahl in diesem Bereich ist aber 0.

Daher ist a1 – a2 = 0, das heißt a1 = a2.

Dieser Widerspruch zeigt, dass der ISBN-Code Vertauschungen der

ersten beiden Stellen 100%ig erkennt.


Juni 2004Seite 19

5.4 Der EAN-Code5.4 Der EAN-Code

EAN = Europäische Artikel Nummer

Ziele: (a) Schutz gegen Einzelfehler und (in geringerem Umfang)

gegen Vertauschungsfehler

(b) Nummer sowohl menschen- als auch maschinenlesbar.

Methoden: (a) Prüfziffer

(b) Strichcode (Barcode) (für Lesbarkeit durch einen Scanner)

Konsequenz: In den „Strichen“ steckt die gleiche Information wie in

den „Ziffern“; darin ist keine „Geheiminformation“ verborgen.

EAN = Europäische Artikel Nummer

Ziele: (a) Schutz gegen Einzelfehler und (in geringerem Umfang)

gegen Vertauschungsfehler

(b) Nummer sowohl menschen- als auch maschinenlesbar.

Methoden: (a) Prüfziffer

(b) Strichcode (Barcode) (für Lesbarkeit durch einen Scanner)

Konsequenz: In den „Strichen“ steckt die gleiche Information wie in

den „Ziffern“; darin ist keine „Geheiminformation“ verborgen.


Juni 2004Seite 20

EANEAN

Eine EAN hat 13 (oder, bei kleinen Artikeln, 8) Stellen,

die in vier Gruppen eingeteilt sind.

Erste Gruppe (2 Ziffern): Land der Herstellung (00-09: U.S.A.,

Canada, 30-37: Frankreich, 40-43: Deutschland, 50: U.K., 54:

Belgien, 57: Dänemark, 76: Schweiz, 80-81: Italien, 90-91:

Österreich, ...)

Zweite Gruppe (5 Ziffern): bundeseinheitliche Beztriebsnummer

Dritte Gruppe (5 Ziffern): Herstellespezifische Artikelnummer

Vierte Gruppe (1 Ziffer): Prüfziffer

Eine EAN hat 13 (oder, bei kleinen Artikeln, 8) Stellen,

die in vier Gruppen eingeteilt sind.

Erste Gruppe (2 Ziffern): Land der Herstellung (00-09: U.S.A.,

Canada, 30-37: Frankreich, 40-43: Deutschland, 50: U.K., 54:

Belgien, 57: Dänemark, 76: Schweiz, 80-81: Italien, 90-91:

Österreich, ...)

Zweite Gruppe (5 Ziffern): bundeseinheitliche Beztriebsnummer

Dritte Gruppe (5 Ziffern): Herstellespezifische Artikelnummer

Vierte Gruppe (1 Ziffer): Prüfziffer


Juni 2004Seite 21

Die Prüfziffer beim EAN-CodeDie Prüfziffer beim EAN-Code

EAN ohne Prüfz.: 4 0 0 0 4 1 7 0 2 0 0 0

Gewichtung 1 3 1 3 1 3 1 3 1 3 1 3

Produkte 4 0 0 0 4 3 7 0 2 0 0 0


S = 4 + 0 + 0 + 0 + 4 + 3 + 7 + 0 + 2 + 0 + 0 + 0 = 20.

Diese Zahl wird durch die Prüfziffer zur nächsten Zehnerzahl

ergänzt.


und die vollständige EAN lautet 40 00417 02000 0.

EAN ohne Prüfz.: 4 0 0 0 4 1 7 0 2 0 0 0

Gewichtung 1 3 1 3 1 3 1 3 1 3 1 3

Produkte 4 0 0 0 4 3 7 0 2 0 0 0


S = 4 + 0 + 0 + 0 + 4 + 3 + 7 + 0 + 2 + 0 + 0 + 0 = 20.

Diese Zahl wird durch die Prüfziffer zur nächsten Zehnerzahl

ergänzt.


und die vollständige EAN lautet 40 00417 02000 0.


Juni 2004Seite 22

Eigenschaften des EAN-CodesEigenschaften des EAN-Codes

5.4.1. Satz. Der EAN Code erkennt alle Einzelfehler

Der EAN-Code erkennt nicht alle (aber die meisten)

Vertauschungsfehler.

Beweis: Übungsaufgabe

Bemerkung: Da beim Lesen durch einen Scanner praktisch keine

Vertauschungsfehler vorkommen, war es entscheidend, eine sehr

gute Einzelfehlererkennung zu gewährleisten.

5.4.1. Satz. Der EAN Code erkennt alle Einzelfehler

Der EAN-Code erkennt nicht alle (aber die meisten)

Vertauschungsfehler.

Beweis: Übungsaufgabe

Bemerkung: Da beim Lesen durch einen Scanner praktisch keine

Vertauschungsfehler vorkommen, war es entscheidend, eine sehr

gute Einzelfehlererkennung zu gewährleisten.


Juni 2004Seite 23

Der StrichcodeDer Strichcode

Die Übersetzung einer EAN in den maschinenlesbaren Strichcode

erfolgt auf raffinierte Art und Weise.

Zusätzliche Ziele: 1. Man muss erkennen könne, in welcher Richtung

die Ziffern gelesen werden (von vorne nach hinten o.u.).

2. Man möchte zwei Hälften aus 6 Ziffern haben; daher wird die

erste Ziffer implizit durch die andern codiert. Konsequenz: Man

braucht verschiedene Zeichensätze.

Methode: Jede Ziffer wird in eine Folge von sieben weißen und

schwarzen Streifen gleicher Dicke übersetzt. (Diese Streifen fügen

sich zu mehr oder weniger dicken schwarzen und weißen Streifen

zusammen.) Siehe Tabelle auf der nächsten Folien.

Die Übersetzung einer EAN in den maschinenlesbaren Strichcode

erfolgt auf raffinierte Art und Weise.

Zusätzliche Ziele: 1. Man muss erkennen könne, in welcher Richtung

die Ziffern gelesen werden (von vorne nach hinten o.u.).

2. Man möchte zwei Hälften aus 6 Ziffern haben; daher wird die

erste Ziffer implizit durch die andern codiert. Konsequenz: Man

braucht verschiedene Zeichensätze.

Methode: Jede Ziffer wird in eine Folge von sieben weißen und

schwarzen Streifen gleicher Dicke übersetzt. (Diese Streifen fügen

sich zu mehr oder weniger dicken schwarzen und weißen Streifen

zusammen.) Siehe Tabelle auf der nächsten Folien.


Juni 2004Seite 24

Die Tabelle für die StrichcodesDie Tabelle für die Strichcodes


Juni 2004Seite 25

Prinzip des StrichcodesPrinzip des Strichcodes

Beobachtung: Jedes Zeichen des Zeichensatzes A hat eine

ungerade Anzahl von schwarzen Streifen, aber bei B und C hat

jedes Zeichen eine gerade Anzahl von schwarzen Streifen.

Tatsächlich ist C das „Komplement“ von A.

Wie werden die Ziffern a1, a2, a3, ..., a13 einer EAN

in Strichmuster codiert?

• Die Ziffern a8, a9, ..., a13 (also die zweite Hälfte) wird stets mit

Zeichensatz C codiert.

• Die Ziffern a2, a3, ..., a7 werden gemäß folgender Tabelle codiert.

Durch die Abfolge der Zeichensätze wird a1 automatisch codiert.

Beobachtung: Jedes Zeichen des Zeichensatzes A hat eine

ungerade Anzahl von schwarzen Streifen, aber bei B und C hat

jedes Zeichen eine gerade Anzahl von schwarzen Streifen.

Tatsächlich ist C das „Komplement“ von A.

Wie werden die Ziffern a1, a2, a3, ..., a13 einer EAN

in Strichmuster codiert?

• Die Ziffern a8, a9, ..., a13 (also die zweite Hälfte) wird stets mit

Zeichensatz C codiert.

• Die Ziffern a2, a3, ..., a7 werden gemäß folgender Tabelle codiert.

Durch die Abfolge der Zeichensätze wird a1 automatisch codiert.


Juni 2004Seite 26

Zeichensätze für die Ziffern a2, a3, ..., a7Zeichensätze für die Ziffern a2, a3, ..., a7

a1 a2 a3 a4 a5 a6 a7

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

a1 a2 a3 a4 a5 a6 a7

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


Juni 2004Seite 27

Abschließende BemerkungenAbschließende Bemerkungen

• Die „langen“ Striche sind „Trennzeichen“:

Der Scanner merkt, wann er anfangen und wann er aufhören muss.

• Der Scanner erkennt die Reihenfolge der Zeichen: Das erste Zeichen (a2) wird in jedem Fall mit A, d.h. mit einer

ungeraden Anzahl von schwarzen Streifen codiert. Das letzte Zeichen (a13) wird dagegen immer mit Zeichensatz C,

also einer geraden Anzahl von schwarzen Streifen codiert.

• Der Scanner zählt die schwarzen Streifen im ersten Zeichen,

welches er liest, und weiß dann, ob er von vorne nach hinten

o.u. liest.

• Die „langen“ Striche sind „Trennzeichen“:

Der Scanner merkt, wann er anfangen und wann er aufhören muss.

• Der Scanner erkennt die Reihenfolge der Zeichen: Das erste Zeichen (a2) wird in jedem Fall mit A, d.h. mit einer

ungeraden Anzahl von schwarzen Streifen codiert. Das letzte Zeichen (a13) wird dagegen immer mit Zeichensatz C,

also einer geraden Anzahl von schwarzen Streifen codiert.

• Der Scanner zählt die schwarzen Streifen im ersten Zeichen,

welches er liest, und weiß dann, ob er von vorne nach hinten

o.u. liest.

Documents

Kapitel 5 Fehlererkennende Codes. Kapitel 5 © Beutelspacher Juni 2004 Seite 2 Inhalt 5.1 Grundlagen: Was sind Vehler? 5.2 Vertuaschungsfehler 5.3 Der