close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Kapitel 21: Fehlererkennende Codes: Was ist eigentlich EAN?

EinbettenHerunterladen
Kapitel 21: Fehlererkennende Codes:
Was ist eigentlich EAN?
Olaf Loga
30.04.09
1. Was bedeutet EAN?
EAN bedeutet ursprünglich European Article Number ist jedoch heute aufgrund der
Internationalisierung auch unter dem Begriff International Article Number zu finden. Die EAN dient
zur Identifizierung von Produkten und wird häufig auch durch einen Strichcode dargestellt um ihn
maschinenlesbar zu machen. Sie besteht aus 8 (EAN-8) oder 13 (EAN-13 = ISBN-13) Zeichen, wobei
die EAN-8 im Gegensatz zur EAN-13 nicht weltweit eindeutig ist. Im folgenden werden wir uns auf die
13-stellige EAN beschränken.
Beispiel:
4
0
0
1
5
0
5
0
0
0
7
3
7
- Die ersten 3 Ziffern beschreiben das Herkunftsland (400 = Deutschland)
(Hinweis: Bücher stammen immer aus "Bookland" 978 oder 979)
- Die nächten 3 Ziffern geben den Hersteller an (150 = Steiff)
- Die folgenden 5 Ziffern ist eine vom Hersteller gewählte Artikelnummer
- Die letzte Ziffer ist die EAN-Prüfziffer
Die Vergabe der EAN-13 wird weltweit von der GS1-Gruppe organisiert und sind damit eindeutig
(http://www.gs1.org/).
2. Strichcode einer EAN
Jede Ziffer (bis auf die erste) der EAN wird
durch 4 Linien repräsentiert, wobei die Linien in
4 Strichstärken auftreten. Die Linien können
doppelt, dreifach oder vierfach so breit sein wie
die einfache Linie. Jede Ziffer hat sowohl eine
"odd" als auch eine "even" Darstellung.
Beispielsweise hat die 0 die Darstellung 3211 (even) oder 1123 (odd). Ob nun eine Ziffer "odd" oder
"even" codiert wird, hängt von der ersten Ziffer der EAN ab, da diese durch die "odd"/"even"
Anordnung codiert wird (hier: OEOOEE OOOOOO = 4). Die letzten 6 Zeichen werden immer "odd"
codiert, damit der Scanner die Leserichtung erkennt. Start-, Zwischen- und Endmarke haben für die
Codierung keine Bedeutung.
3.1 Berechnung der EAN Prüfziffer
Sei x = x1 x 2 ...x13 eine EAN, wobei x13 die passende Prüfziffer darstellt die sich wie folgt berechnet:
1
x13 = (10 − ( s ( x1 ,..., x12 ) mod 10)) mod 10
s ( x1 ,..., x12 ) = ( x1 + x3 + ... + x11 + 3 ⋅ ( x 2 + x 4 + ... + x12 )) mod 10
Beispiel:
x = 400150500073x13
s ( x1 ,..., x12 ) = (4 + 0 + 5 + 5 + 0 + 7) + 3 ⋅ (0 + 1 + 0 + 0 + 0 + 3)) mod 10
= (21 + 3 ⋅ 4) mod 10 = 33 mod 10 ≡ 3
x13 = 10 − 3 ≡ 7
(mod10)
(mod10)
3.2 Erkennung von Tippfehlern
Im folgenden wird gezeigt, dass die EAN einen Tippfehler (1 Stelle der EAN wurde falsch eingegeben)
erkennt.
Sei x = x1 x 2 ...x13 eine richtige und y = y1 y 2 ...y13 eine falsche EAN. Falls wir uns bei der Prüfziffer
geirrt haben, wird dies durch die ersten 12 korrekt eingegebenen Ziffern erkannt, da
s ( x1 ,..., x12 ) = s ( y1 ,..., y12 ) und folglich auch x13 = y13 sein muss. Nun nehmen wir an, dass wir uns
an der i-ten Stelle vertippt haben ( i ≠ 13 ) und sich daraus eine andere Prüfziffer ergibt. Es gilt
y i = xi + t , wobei − 9 < t < 9 ist.
1. Fall: i ist ungerade:
s ( y1 ,..., y12 ) = ( y1 + y 3 + ... + y11 + 3 ⋅ ( y 2 + y 4 + ... + y12 )) mod 10
= ( x1 + x3 + ... + xi + t + ... + x11 + 3 ⋅ ( x 2 + x 4 + ... + x12 )) mod 10
= ( s ( x1 ,..., x12 ) + t ) mod10
Da t ≠ 0 gilt: y13 ≡ 10 − s ( y1 ,..., y12 ) ≡ 10 − s ( x1 ,..., x12 ) − t ≡ x13 − t ≠ x13
2. Fall: i ist gerade:
Ergibt sich analog mit
y13 ≡ 10 − s ( y1 ,..., y12 ) ≡ 10 − s ( x1 ,..., x12 ) − 3t ≡ x13 − 3t ≠ x13
Vertippt man sich allerdings an mehreren Stellen, wird dies nicht immer erkannt. Die EAN kann nur
einen Tippfehler sicher erkennen!
3.3 Erkennung von Zahlendrehern
Ein Zahlendreher beschreibt die Vertauschung von 2 benachbarten Ziffern. Dazu betrachten wir
wieder x = x1 x 2 ...x13 (richtige EAN) und y = y1 y 2 ...y13 (falsche EAN) mit xi = y i +1 und xi +1 = y i .
Im folgenden nehmen wir an, dass i ungerade ist (der Fall, dass i gerade ist ergibt sich wieder analog):
s ( y1 ,..., y12 ) = ( y1 + y 3 + ... + y i + ... + y11 + 3 ⋅ ( y 2 + y 4 + ... + y i +1 + .. + y12 )) mod 10
= ( x1 + x3 + ... + xi +1 + ... + x11 + 3 ⋅ ( x 2 + x 4 + ... + xi + .. + x12 )) mod 10
2
= ( x1 + x3 + ... + xi +1 + ... + x11 + 3 ⋅ ( x 2 + x 4 + ... + xi + .. + x12 ) + 2 xi +1 − 2 xi − 2 xi +1 + 2 xi ) mod 10
= ( s ( x1 ,..., x12 ) + 2 ⋅ ( xi + xi +1 ) mod 10
Demnach ergibt sich für y13
y13 ≡ 10 − s ( y1 ,..., y12 ) ≡ 10 − ( s ( x1 ,..., x12 ) + 2 ⋅ ( xi + xi +1 ) ≡ x13 + 2 ⋅ ( xi + xi +1 )
Falls sich nun xi +1 und xi um genau 5 unterscheiden, d.h. xi − xi +1 ≡ 5
wegen 2( xi − xi +1 ) ≡ 0
(mod10)
(mod10) , dann hat y
(mod10) die gleiche Prüfziffer. Andernfalls wird der Fehler erkannt.
4.1 Verbesserte Prüfziffernberechnung
Um nun alle Zahlendreher erkennen zu können definieren wir
s ( x1 ,..., x12 ) = (∑i =1 i ⋅ xi ) mod 13 = x13
12
Offensichtlich kann die Prüfziffer nun Werte zwischen 0 und 12 annehmen, wobei wir um eine
einstellige Prüfziffer zu erhalten 10=A,11=B und 12=C definieren. Es wird modulo 13 gerechnet, da
alle Ziffern der Summe <13 sind, 13 eine Primzahl ist und die Zahlenfolge eine Länge von 12 hat.
(Würde die Zahlenfolge länger sein, würde man die nächst größere Primzahl nehmen).
4.2 Erkennung von Tippfehlern
Sei x = x1 x 2 ...x13 eine richtige und y = y1 y 2 ...y13 eine falsche EAN. Wurde die Prüfziffer falsch
eingegeben, ergibt sich derselbe Fall wie bei der normalen Prüfziffernberechnung. Nun nehmen wir
wieder an, dass wir uns an der i-ten Stelle vertippt haben ( i ≠ 13 ) und sich daraus eine andere
Prüfziffer ergibt. Es gilt y i = xi + t , wobei − 12 < t < 12 ist.
s ( y1 ,..., y12 ) = ( y1 + 2 ⋅ y 2 + ... + 12 ⋅ y12 ) mod 13
= ( x1 + 2 ⋅ x 2 + ... + i ⋅ ( xi + t ) + ... + 12 ⋅ y12 ) mod 13
= ( s ( x1 ,..., x12 ) + i ⋅ t ) mod13
Da t ≠ 0 gilt: y13 ≡ s ( y1 ,..., y12 ) ≡ s ( x1 ,..., x12 ) + t ⋅ i ≡ x13 − t ⋅ i ≠ x13
4.3 Erkennung von Zahlendrehern
Unter gleichen Voraussetzungen wie in 3.3 ergibt sich:
s ( y1 ,..., y12 ) = ( y1 + ... + i ⋅ y i + (i + 1) ⋅ y i +1 + ... + 12 ⋅ y12 )) mod 13
= ( x1 + ... + i ⋅ xi +1 + (i + 1) ⋅ xi + ... + 12 ⋅ x12 )) mod 13
= ( x1 + ... + (i + 1) ⋅ xi +1 + i ⋅ xi + ... + 12 ⋅ x12 + xi − xi +1 )) mod 13
= ( s ( x1 ,..., x12 ) + xi − xi +1 )) mod 13
= ( x13 + xi − xi +1 )) mod 13
3
Damit ( x13 + xi − xi +1 )) mod 13 = x13 ist, müsste xi − xi +1 ≡ 0
(mod13) sein. Dies ist nicht
möglich, da xi und xi +1 Zahlen zwischen 0 und 12 sind und xi ≠ xi +1 (sonst wäre es kein
Zahlendreher/Fehler).
5. Einfacher fehlerkorrigierende Codes
Es wird offensichtliche 1 Fehler erkannt und das Verhältnis
zwischen Ursprungsdaten und
den codierten Daten beträgt
1/3.
6. Hamming Code
Der Hamming Code besitzt einen Minimalabstand
d(C)=3 und ist dementsprechend 1-fehlerkorrigierend
und 2-fehlererkennend. Das Verhältnis zwischen
Ursprungsdaten und codierten Daten beträgt 4/7
7.1 Reed-Solomon Codierung
Ein RS Code RS(q,m,n) (q: Größe des Alphabets, m: Länge des Eingabealphabets, n = Länge des
codierten Wortes) hat einen Minimalabstand von n-m+1. Damit kann er n-m Fehler erkennen und (nm)/2 Fehler korrigieren. Jedoch kann mithilfe der Lagrange Interpolation bis zu n-m Ausfälle
decodieren.
Zur Codierung wird das zu codierende Wort als Polynom wie folgt definiert:
, wobei z.B. u i = i − 1
Die codierte Nachricht ergibt sich aus
gewählt werden kann.
7.2 Dekodierung von Ausfällen
Eine Möglichkeit der Dekodierung ist mithilfe der Lagrange Interpolation.
Nun kann man die Nachricht wieder dekodieren indem man sich das Polynom wieder zusammenbaut
Quellen:
Johannes Blömer, Uni Paderborn, Algorithmische Codierungstheorie, http://wwwcs.uni-paderborn.de/cs/agbloemer/lehre/ac2_SS2007/material/skript.pdf , SoSe 2007, 27.04.2009
Alexandra Souza und Angelika Steger, Kapitel 21: Fehlererkennende Codes - Was ist eigtl. EAN?, Taschenbuch der Algorithmen, Springer,
2008
Dr. Klaus Kriegel, FU-Berlin, MafI III, WiSe 05/06
GS1-Group, GS1 Barcode Prefix List, http://www.gs1.org/productssolutions/barcodes/support/prefix_list.html, 27.04.2009
Wikipedia, EAN, http://de.wikipedia.org/wiki/International_Article_Number, 27.04.2009
Wikipedia, Fehlerkorrekturverfahren, http://de.wikipedia.org/wiki/Fehlerkorrekturverfahren , 27.04.2009
4
Document
Kategorie
Internet
Seitenansichten
1
Dateigröße
293 KB
Tags
1/--Seiten
melden