Beispiel zu Fehlererkennungscode

Es wurde schon angesprochen, dass Fehlererkennung nur durch Redundanz zu erreichen ist.

Redundanz - redundancy
Redundanz (lat. redundare – im Überfluss vorhanden sein) bezeichnet in diesem Zusammenhang Nachrichtenelemente, die keine zusätzliche Information liefern, sondern bestimmte Informationen einer Nachricht wiederholen. In linearen Barcodes erzeugt die Strichhöhe vertikale Redundanz (mehrfachem Scannen an verschiedenen Stellen).

Um das noch klarer zu machen, betrachte man folgendes: Es sei eine Quelle mit vier verschiedenen Symbolen gegeben (z.B. rechts, links, oben und unten) und man codiert diese Symbole binär

  1. 00 rechts
  2. 01 unten
  3. 10 links
  4. 11 oben

Überträgt man diese zwei Bit langen Codewörter und wird durch einen Fehler eine 0 zu einer 1 oder umgekehrt, so ist aus dem ursprünglichen Codewort ein anderes gültiges Codewort entstanden. Im Decodierschritt ist das unmöglich zu erkennen, d.h. wenn ein Fehler beim Übertragen des Codewortes auftritt, darf kein gültiges Codewort dadurch erzeugt werden. Ein auftretender Fehler muss ein ungültiges Codewort erzeugen, damit der Fehler erkannt werden kann.

Also kann man nicht alle möglichen Codewörter benutzen, um sie mit Quellsymbolen zu identifizieren (hier rechts, links, etc.). Es müssen einige Codewörter verbleiben, die keinem Quellsymbol zugeordnet werden. Man verwendet diese Codewörter, um Fehler erkennen zu können. Diese für die eigentliche Datenübertragung „überflüssigen“ Codewörter stellen die Redundanz des Codes oder der Übertragung dar.

Im obigen Beispiel könnte man die Codewörter um ein Paritätsbit verlängern.

Parität - Parity
Ein System zur Verschlüsselung von Zeichen als „ungerade“ / odd (mit einer ungeraden Anzahl von binären Einsen in der Struktur) oder als „gerade“ / even (mit einer geraden Anzahl von binären Einsen in der Struktur). Es wird als Selbstprüfmechanismus in Strichcodes verwendet.

Paritätsbit - Paritybit
Das Paritätsbit ist ein einer binären Zeichenfolge zugeordnetes Bit, das zum Erkennen von Übergangsfehlern dient. Es ist so hinzugefügt, dass die Modulo-2-Summe aller in der Zeichenfolge betrachteten Bits gleichen Wertes (einschließlich des Paritätsbits) je nach Rechenvorschrift ‚0‘ oder ‚1‘ ist. Durch Verwendung von Paritätsbits wird der Hammingabstand eines Codes um 1 erhöht.

Passiver Tag - Passive Tag
Siehe Passiver Transponder.

Passiver Transponder - Passive Transponder
Transponder ohne eigene Energiequelle. Die Energie zur Datenübertragung wird aus dem Sendesignal der Antenne gewonnen.

Penetration - Penetration
Der Ausdruck wird gebraucht, um die Eigenschaften von Radio Frequenz Signalen anzugeben, die nicht in der Lage sind, metallische Materialien zu durchdringen. Tags mit niedriger Frequenz haben gute penetrierende Eigenschaften. Mikrowellen-Tags haben weniger Penetrationsfähigkeiten, auch in Anbetracht der größeren Reichweite.

PAN - Personal Area Network
Netz, das mit Hilfe von drahtlosen Kommunikationstechniken erzeugt werden kann, allerdings nur eine Reichweite von wenigen Metern hat.

Phasenmodulation (PM) - Phase Modulation (PM)
Daten sind festgehalten durch Änderung (Verschiebung) in der Phase des Trägersignals, die binäre Form ist bekannt als PSK (Phase Shift Keying).

Photometer - Photometre
Ein Instrument, das zur Messung der Intensität von Licht einer speziellen Wellenlänge benutzt wird.

Pixel - Pixel
Das kleinste Bildelement, das in Kombination mit anderen Elementen eine komplette Graphik bildet.

POI - Point of Information
Wörtlich übersetzt „Informationspunkt“, beispielsweise eine bildschirmbestückte Säule, auch Kiosksystem genannt, die nur visuelle Informationen ausgibt. Der Bildschirm ist dabei meist ein Touchscreen.

Polar-/Felddiagramm - Polar-/Field-Diagram
Eine geographische Darstellung der Feldstärke der Suchantenne.

Port Concentrator
Ein Apparat, der die Ausgangssignale einer Anzahl Kommunikations-Interfaces akzeptiert und in ein Kommunikationsnetzwerk übergibt.

POS - Point of Sale
Damit wird jener Bereich im Einzelhandel bezeichnet, in dem normalerweise die EAN/UPC Strichcodesymbole der Waren gescannt werden (Kassenbereich).

Präfixcode - Prefix Code
Kein Codewort darf im Anfangsteil eines anderen Codewortes vorkommen, wodurch z.B. ein Code-128 unverzögert decodiert werden kann.

Programmiergerät - Programmer
Ein elektronisches Gerät, das engen Kontakt oder elektronischen Kontakt voraussetzt, um Änderungen vorzunehmen oder Daten einzubringen.

Programming of RF-Tags
Read only (R/O) RF-Tag, das im Moment der Herstellung programmiert ist und danach ausschließlich gelesen werden kann. Manchmal auch factory programmed genannt.

Prüfziffer / -zeichen - Check Digit / Character
Eine Zeichen oder eine Ziffer, die auf der Basis anderer Zeichen in einem Code berechnet wird. Dient zur Kontrolle der Zusammensetzung des Codes. „Ein Prüfzeichen im Sinne der Nummerierung ist ein Nummernzeichen, das aus einer gegebenen Nummer nach bestimmten Regeln ermittelt wird, um das Prüfen dieser Nummer auf ihre Richtigkeit zu ermöglichen.“ (DIN 67663) Siehe Symbolprüfzeichen und Datenprüfzeichen / -ziffer.

PSU - Power-Supply Unit
Elektrische Versorgungseinheit.

Pulkerfassung - Batch - / Multiple Reading
Möglichkeit bzw. Vorgang des Lesens mehrerer Transponder, die sich gleichzeitig im Antennenfeld befinden. Dazu werden die Transponder meist einzeln vom Lesegerät angesprochen, während alle anderen „stumm“ geschaltet werden.

Pulsweitenmodulation (PWM) - Pulse Width Modulation (PWM)
Daten sind festgehalten durch Verschiebungen/Veränderungen der Pulslänge des Trägersignals.

  • Gültige Codewörter sind 000 rechts 011 unten 101 links 110 oben.
  • Die ungültigen Codewörter sind 001 010 100 111.

Es gibt im ganzen 23 = 8 mögliche Codewörter, also sind 4 Codewörter gültig und 4 ungültig. Wandelt sich durch einen Übertragungsfehler eine beliebige Stelle in einem gültigen Codewort von einer 1 zur 0 oder umgekehrt, so wird das empfangene Codewort ungültig sein. Wenn aber 2 Bits den Zustand ändern, ist die Parity (Parität) wieder korrekt.

Also kann dieser einzelne Fehler in der Decodierphase erkannt werden. Es ist offensichtlich, dass eine gerade Anzahl von Bitfehlern nicht erkennbar ist. Ein Paritycheck erzeugt einen einzelfehlererkennenden Code. Mit der Parity kann zwar ein Fehler erkannt, aber nicht korrigiert werden. Dies wird durch Hinzufügen weiterer Redundanz erreicht.

Von fundamentaler Bedeutung für die weiteren Betrachtungen ist der Begriff des Hammingabstandes eines Codes.

Hammingabstand - Hammingdistance
Unter dem Hammingabstand eines Codes versteht man das Minimum der Anzahl voneinander unterschiedlicher Positionen je zwei verschiedener Codewörter. Nur Codes mit Hammingahstand größer Null sind sinnvoll, denn nur dann sind sämtliche Codewörter voneinander verschieden.

Abbildung: Drei Schritte sind notwendig,um aus dem gültigen Coderwort ROT ein anderes gültiges Codewort GRÜN zu erzeugen. Der Hammingabstand ist drei!

Vereinfachen wir das Beispiel für eine 2 Zustandsübertragung: {1} sei oben und {0} sei unten. Fügen wir 2 weitere Bits hinzu und codieren 1 oben mit {1,0,0} und unten mit {0,1,1}. Abbildung 2.3 zeigt: der Hammingabstand ist jetzt 3. Diese Codierung erlaubt einen 1-Bit-Fehler zu korrigieren.

Im Allgemeinen gilt: Gegeben sei ein Code mit m Informationsbytes und k Korrekturbytes. Ein derartiger Code kann maximal k falsche Symbole pro Codewort erkennen und k/2 korrigieren.

Basics.BeispielFehlererkennung by Katrin Reiher at 14.02.2007 16:18

Servicebereich:

Autorenkontakt, PDFs der Vorlesungsfolien und des Skripts, off-line CD, Links, das Glossar uvm.

weiter...

Alle Bilder zum Thema:Basics

weiter...

Die gesamte Literaturliste

weiter...

Übungsfragen:Basics

weiter...

Glossar der Identifikation

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Abkürzungen