 |
DigitaltechnikProf. Jürgen Plate |
|
DigitaltechnikProf. Jürgen Plate |
Bei der Übermittlung von Informationen in der Schriftform bedient man sich eines Systems mit vereinbarten Symbolen, die durch zugeordnete Kombinationen zu Trägern von Nachrichten werden. Theoretisch gibt es eine unüberschaubare Zahl von Möglichkeiten der Zuordnung von Symbolen und Begriffen.
Die Umsetzung einer Nachricht in eine geeignete Darstellung oder die physikalische Repräsentation wird als Codierung bezeichnet. Die Nachricht wird codiert, damit die enthaltene Information in einem Nachrichtentechnischen System verarbeitet werden kann. Der Informationsgehalt bestimmt die Codierungsvorschrift.
| Ein Code ist eine Vorschrift für die eindeutige Zuordnung (= Codierung) der Zeichen eine Zeichenvorrats (Objektmenge) zu den Zeichen eines anderen Zeichenvorrats (Bildmenge). |
Häufig wird mit "Code" auch nur die Bildmenge bezeichnet.
Nachricht:
Zusammenstellung von Symbolen (Zeichen) zur
Informationsübermittlung.
Symbol:
Element eines Symbol- oder Zeichenvorrates. Dieser Vorrat ist
eine festgelegte endliche Menge von verschiedenen Symbolen (=
Elemente der Menge). Der Unterschied zwischen Symbol und Zeichen
ist recht subtil. Ein Symbol ist ein Zeichen mit bestimmter
Bedeutung.
Alfabet:
Ein geordneter Vorrat von Symbolen. Anzahl von zur Verfügung
stehenden Zeichen.
Wort (Codewort):
Folge von "zusammengehörigen" Zeichen, die in einem
bestimmten Zusammenhang als Einheit betrachtet werden.
Coderahmen:
Länge der Worte (falls der Code lauter gleich lange Worte besitzt).
Beispiele:
Alfabet: A,B,C,D,E,F,...,X,Y,Z
Wort: DONALD
Nachricht: DONALD SUCHT DAISY
Wie kann man nun mit wenigen verschiedenen Schriftzeichen (beim lateinischen Alfabet gerade mal 26) beliebig viele Begriffe darstellen? Dies geschieht durch Kombinationen der zur Verfügung stehenden wenigen Zeichen, wobei der Anordnung der Zeichen untereinander eine wichtige Bedeutung zukommt, z. B. "REGEN" oder "NEGER". Beide Symbolanordnungen (Worte) unterscheiden sich nicht bezüglich der verwendeten Zeichen, geben aber zwei völlig verschiedene Begriffe wieder. Zwischen dem Umfang des Alfabets und der sich durch ihre Kombinationen ergebenden Wortlängen besteht ein Zusammenhang: Je weniger verschiedene Zeichen das Alfabet hat, um so länger werden die einzelnen Wörter, wenn man denselben Begriff ausdrücken will.
Wie gesagt ist der Zweck der Codierung die Anpassung der Nachricht an technische Systeme (z. B. Morsecode). Die Codierung ändert nur die Darstellungsform einer Nachricht, nicht ihre Bedeutung!
Wenn ein Code ein Alfabet aus B möglichen Zeichen besitzt und alle Codeworte n Symbole lang sind (Coderahmen: n), beträgt die Anzahl der moglichen Codeworte M:
Für die Codierung von M unterschiedlichenNachrichten kann man den notwendigen Coderahmen n berechnen:
Beispiel:
Alphabet mit 26 Buchstaben plus Leerzeichen, eine Zeile mit 40 Zeichen:
→ 2740 mögliche Zeilen, mit allen möglichen Texten in allen möglichen Sprachen,
die "unsere" 26 Buchstaben verwenden. (Anmerkung: 2740 ist ca. 1057)
Informationsverarbeitungssysteme arbeiten in der Regel mit binären Signalen. Aus diesem Grund besteht auch der Symbolvorrat der in der Digitaltechnik verwendeten Codes aus den Binärzeichen {0, 1} bzw {O, L}. Leider werden durch die Symbolbeschränkung auf die beiden Binärzeichen die Codierungsprobleme der Digitaltechnik nicht einfacher, denn es lassen sich mit den Zeichenelementen 0 und 1 außerordentlich viele verschiedene Zuordnungssysteme (Codes) z. B. für Zahlen aufbauen.
Beispiele binärer Zeichenvorräte:
| Intensität | hell | dunkel |
| Zahlen | 1 | 0 |
| Zustände | gelocht | ungelocht |
| Wahrheitswerte | wahr | falsch |
| Spannungen | 5 Volt | 0 Volt |
| Ströme | 20 mA | 0 mA |
Da auf allen Gebieten der numerischen Informationsverarbeitung Signale Verwendung finden, müssen auch alle Zahlen binär codiert werden. Will man eine beliebige Dezimalzahl binär codieren, so liegt es nahe, diese Dezimalzahl zuerst in eine entsprechende Dualzahl überzuführen, deren Dualziffern 0 und 1 dann durch die entsprechenden Codesymbole "0" und "1" repräsentiert werden.
verschiedene (gleichlange) binäre Codewörter gebildet werden. Zur Codierung von M Zeichen sind also Codeworte der Länge
nötig. Ist M keine Zweierpotenz, können mehr Codeworte gebildet werden als brenötigt werden. Die nicht verwendeten Codeworte heißen "Pseudowörter" → Code-Redundanz. Die Codewortlänge wird oft auch als "Coderahmen" bezeichnet.
Die Zeichen des Alphabets werden häfig auch als Binary Digit, abgekürzt Bit bezeichnet (Achtung: das bit als Informationseinheit und das Bit als Bezeichnung für Codesymbole sind unterschiedliche Dinge.). Ein Codewort mit einer Codewortläge von n = 8 wird oft als Byte oder Oktett bezeichnet (das geschieht aber auch bei Binärzahlen mit 8 Stellen).
Es gibt auch Codes, bei denen die Codewortlänge kleiner als ld(M) ist. Die Codeworte sind dann doppelt belegt und Umschaltzeichen ordnen den nachfolgenden Codeworten die Belegung zu (z. B. Telegraphenalfabet CCITT Nr. 2: n = 5, Umschaltung zwischen zwei Ebenen: Buchstaben bzw. Ziffern und Sonderzeichen).
Die Forderungen werden aus den o.g. Gründen abgeleitet, was zum Teil auch wiedersprüchliche Merkmale nach sich zieht → ein für alle Zwecke optimaler Code existiert nicht → Anwendung mehrerer Codes in einem System (DV-System) nicht ungewöhnlich → Umcodie- rung notwendig.
Beispiele für Codeeigenschaften (Forderungen):
Gewichtete Codes: Jeder Position im Codewort ist ein (numerisches) "Gewicht" zugeordnet. Fasst man die Symbole 0 und 1 als Binärzahlen auf, multipliziert diese mit dem jeweiligen Gewicht und addiert die Ergebnisse, erhät man den codierten Zahlenwert (siehe 8-4-2-1-Code unten).
Anordnungscodes: Es spielt nur die Position des Symbols eine Rolle; es gibt keine Gewichtung.
Mehrschrittige Codes: Die Codeworte unterscheiden sich um mehr als eine Stelle untereinander.
Einschrittige Codes: Zwei Codeworte sind nur in einer Stelle unterschiedlich (z. B. Gray-Code).
Der Dualcode ist ein reiner Binärcode, der der Zahlendarstellung im Dualsystem entspricht (siehe Kap.3) → wortorganisierte binäre Codierung, einfache Arithmetik, Umcodierung bei Ein-/Ausgabe oder Übertragung relativ schwierig.
Von den insgesamt 16 Tetraden werden nur 10 Nutztetraden benötigt → 6 Pseudotetraden. Die Aufteilung der 16 Tetraden in Nutz- und Pseudotetraden führt zu verschiedenen tetradischen Codes. In der Digitaltechnik haben nur einige Möglichkeiten Bedeutung gewonnen.
Ein Code mit dem Coderahmen (Wortlänge) n, dessen Nutzwörter alle m 1-Bits besitzen heißt m-aus-n-Code. Beispiele:
Der oben dargestellte 2-aus-5-Code ist ein Beispiel für einen M-aus-N-Code. Dies ist ein Binärcode mit der festen Wortlänge N, bei dem die Codewörter alle genau M 1-Bits haben. Die Anzahl der möglichen Codeworte im M-aus-N Code ist:
Beispiel beim 5 aus 8 Code:
N ist also 56.
Nebenbemerkung: Kettencodes sind n-Bit-Codes, bei denen über eine zyklische Anordnung von maximal 2n Bits ein Ablesefenster verschoben wird, das n aufeinanderfolgende Bits herausgreift. Für n=3 ist das z. B. mit der folgenden Anordnung von 8 Bits möglich:
Die Einschrittigkeit macht den Gray- bzw. Glixon-Code besonders wichtig. Insbesondere bei messtechnischen Anwendungen sind einschrittige Codes notwendig, um korrekte Messergebnisse zu erhalten. Zum Messen von Längen können Messlineale eingesetzt werden. Winkel können mit Hilfe von ähnlich aufgebauten Winkelgebern bestimmt werden.
Bei Messung mit dem dualcodierten Lineal oben ist beispielsweise der Übergang vom Wert 7 auf den Wert 8 besonders kritisch, weil sich hier alle Binärstellen ändern. Bei einer Abtastung mit einem optischen Sensor kann nicht garantiert werden, dass alle Bitpositionen zur exakt gleichen Zeit wechseln. Schon auf Grund einer kleinen Dejustierung kann ein falscher Wert (z. B. "0") ermittelt werden. Beim Gray-Code-Lineal darunter kann diese Fehlersituation nicht auftreten. Selbst bei leicht ungenauer Abtastung einzelner Bits ergibt sich kein Codesprung, so dass kein falscher Zwischenwert ausgegeben wird. In Messinstrumenten dieser Art werden also grundsätzlich einschrittige Codes verwendet.
Konstruktionsmethode für Gray-Codes
Man geht von einer frei wählbaren Binärzahl als Startwert aus. Die von links gerechnet erste
1 des zugehörigen Wortes im Gray-Codes steht dann an derselben Stelle wie die erste 1 des
entsprechenden Wortes im Binär-Code. Danach wird nach rechts fortschreitend eine 1 eingetragen,
wenn sich die korrespondierende Binärziffer des aktuellen Binärwortes von der links von ihr
stehenden Ziffer unterscheidet, sonst eine 0. Das folgende Beispiel verdeutlicht dieses
Verfahren:
Dezimal Binär Gray Dezimal Binär Gray Dezimal Binär Gray 0 00000 00000 11 01011 01110 22 10110 11101 1 00001 00001 12 01100 01010 23 10111 11100 2 00010 00011 13 01101 01011 24 11000 10100 3 00011 00010 14 01110 01001 25 11001 10101 4 00100 00110 15 01111 01000 26 11010 10111 5 00101 00111 16 10000 11000 27 11011 10110 6 00110 00101 17 10001 11001 28 11100 10010 7 00111 00100 18 10010 11011 29 11101 10011 8 01000 01100 19 10011 11010 30 11110 10001 9 01001 01101 20 10100 11110 31 11111 10000 10 01010 01111 21 10101 11111
10 Ziffern, 26 Buchstaben, 10 Sonderzeichen → 46 Zeichen → 6 Bit Wortlänge
Abkürzungen der Steuer- und Sonderzeichen:
| ACK | acknowledge - positive Rückmeldung | BEL | bell - Klingel |
|---|---|---|---|
| BS | backspace - Rückwärtschritt | CAN | cancel - ungültig, Abbruch |
| CR | carriage return - Wagenrücklauf | DCi | device control i - Gerätesteuerung i |
| DEL | delete - löschen, Entfernen | DLE | data link escape - Datenübertragungsumschaltung |
| EM | end of medium - Ende der Aufzeichnung | ENQ | enquiry - Stationsaufforderung, Anfrage |
| EOT | end of transmission - Ende der Übertragung | ESC | escape - Umschaltung |
| ETB | end of transmission block - Ende Datenübertragungsblock | ETX | end of text - Ende des Textes |
| FF | form feed -Formularvorschub | FS | file seperator - Hauptgruppentrenner |
| GS | group seperator - Gruppentrenner | HT | horizontal tabulation - Horizontaltabulator |
| LC | lower case - untere Stellung, Kleinbuchstaben | LF | line feed - Zeilenvorschub |
| NAK | negative acknowlegde - negative Rückmeldung | NL | new line - neue Zeile |
| NUL | nil - Null (Füllzeichen ohne Einfluß auf Zeicheninhalt) | RS | record seperator - Untergruppentrenner |
| SI | shift in - Rückschaltung in Standardcode | SO | shift out - Dauerumschaltung in andere Codetabellen |
| SOH | start of heading - Anfang des Kopfes | STX | Start of text - Anfang den Textes |
| SUB | substitution - Austausch eines Zeichens | SYN | synchronous idle - Synchronisationslauf |
| UC | upper case - obere Stellung, Großbuchstaben | US | unit seperator - Teilgruppentrenner |
| VT | vertical tabulation - Vertikaltabulator |
Die Codes von Unicode-Zeichen werden hexadezimal mit vorangestelltem "U+" dargestellt. Der Coderaum von Unicode umfasste ursprünglich 65.536 Zeichen (UCS-2, 16 Bit), was bald auch nicht mehr ausreichte. In Version 2.0 wurde das Konzept der Planes (Ebenen) eingeführt. Sie bilden ein Präfix zu den bisherigen, 16 Bit langen Codes und vervielfachen so die Menge der unterscheidbaren Codes. In Unicode 5.0, sind 99.089 Codes individuellen Zeichen zugeordnet. Die Codebereiche (Blöcke), in welche die Unicode-Ebenen untergliedert werden, sind in der "Liste der Unicode-Blöcke" vollständig aufgeführt. Neben den gültig kodierten Zeichen sind auch noch geplante Erweiterungen aufgeführt.
Die Speicherung und Übertragung von Unicode erfolgt in unterschiedlichen Formaten (auch "Encodings" genannt):
Überträgt man Nachrichten, kann Datenkompression die Datenmenge bei Beibehaltung des Informationsgehalts reduzieren (Redundanz wird reduziert). Kommunikationskanäle werden einerseits zwar immer preiswerter, andererseits steigen die zu übertragenden Datenmengen und die Prozessorleistungen so stark, daß Datenkompression immer noch sinnvoll ist. Kompression wird erreicht, indem man häufigen Nachrichten kürzere und selteneren Nachrichten längere Sequenzen von Symbolen zuordnet. Das kann man aber nur mit einer variablen Wortlänge erreichen. Kompression ist aber nur im Durchschnitt über eine große Menge von Nachrichten garantiert; es können nicht unbedingt alle Einzel-Nachrichten komprimiert werden. Voraussetzung für die Datenkompression ist eine Wahrscheinlichkeitstabelle für das Auftreten der zu codierenden Zeichen. Dies wird im folgenden Beispiel verdeutlicht.
In einem fernen Land lebte vor langer, langer Zeit ein kleiner König, der war dick faul und unzufrieden und wollte den lieben langen Tag immer nur essen. Wir wollen hier nur seine Nahrungs- gewohnheiten betrachten - insbesondere, da seine Ernährung recht einseitig war. Den lieben langen Tag aß er nur:
(1) Schweinebraten,
(2) Schokoladenpudding,
(3) Essiggurken,
(4) Erdbeertorte.
Zudem war der König sehr maulfaul und mit der Zeit wurde es ihm sogar zu anstrengend, seine Bestellungen aufzugeben (die er sowieso im Telegrammstil kundtat: "Braten, Torte, Gurken"). Eines Tages beschloß er, eine Codierung zu entwickeln, mit der er seine Befehle auch loswurde, ohne den Mund aufzutun. Durch Zufall wurde es sogar eine Binärcodierung:
Die rechte Hand ein wenig heben heiße: Schweinebraten Die linke Hand etwas heben heiße: Schokopudding Erst die rechte und dann die linke Hand heben: Gurken Zweimal nacheinander die rechte Hand heben: Erdbeertorte
Der Übersichtlichkeit halber wollen wir die Codierung etwas abkürzen. "R" steht für "rechte Hand heben" und "L" für "linke Hand heben". Dann ergibt sich folgende Codezuordnung:
R Braten
L Pudding
RL Gurken
RR Torte
Und schon gab es Probleme. Angenommen der König hob dreimal die rechte Hand (→ RRR). Dann konnte dies bedeuten:
Braten, Braten, Braten oder
Braten, Torte oder
Torte, Braten
Nun mußte der König einmal wirklich viel reden. Er rief seinen Hofmathematikus zu sich und erklärte den Sachverhalt. "Hmmmm" überlegte dieser: "Majestät haben Höchstdero Speisewünsche binär codiert. Vorzüglich, Vorzüglich." "Aber es klappt nicht", raunzte der König,"jedesmal, wenn ich Schweinebraten und Pudding will, bringen diese Hornochsen mir Gurken!" und er sank erschöpft auf seinen Thron zurück. "Mit Verlaub, die Codierung ist nicht ein- deutig, Majestät", wagte der Mathematikus einzuwerfen. "Ich weiß!
Laß Dir gefälligst was einfallen!" grunzte der König. Und vor lauter Angst, wieder etwas Falsches zu bekommen, brüllte er: "Braten und Torte, aber fix!".
Der Mathematiker brütete inzwischen über eine eindeutige binäre Codierung nach und gelangte zu folgenden Überlegungen:
Braten RR
Pudding RL
Gurken LR
Torte LL
Nun war die Codierung unverwechselbar. Die Zeichenfolge "LRRLLLRRRRLL" konnte nur noch bedeuten: Gurken, Pudding, Torte, 2 x Braten, Torte.
Zwar war die Codierung eindeutig, aber war sie auch optimal? Bisher wurde davon ausgegangen, daß der König keine spezielle Vorliebe für bestimmte Gerichte hat (alle Codewörter sind gleich wahrscheinlich). Zudem beschwerte sich der König schon nach kurzer Zeit darüber, daß er viel zu häufig die Hände heben müsse.
Also vergatterte der Mathematikus seinen Assistenten, eine Statistik der königlichen Essenswünsche aufzustellen. Heraus kam folgendes. Jeden Tag verspeiste der König im Schnitt 18 Gerichte.
Die Häufigkeitsverteilung stellte sich so dar:
9 x Schweinebraten,
6 x Schokopudding,
1 x Gurken,
2 x Erdbeertorte.
Soll die Codierung optimal, also eindeutig und zweckmäßig sein, mußte der Matehmatikus versuchen, für den Braten einen möglichst
kurzen Code zu wählen. Dafür darf der Code für eine Grurkenbestellung ruhig länger sein. Also legte er erst einmal fest:
Braten → R
Damit ist das "R" 'verbraucht', denn es darf wegen der Eindeutigkeit kein Codewort mehr mit "R" beginnen (Fano-Bedingung: Kein Code darf der Beginn eines anderen verwendeten Codes sein). Weiter geht es mit:
Pudding → LR
Es bleibt somit noch ein zweistelliges Codewort übrig (LL, denn RR und RL sind wegen der Fano-Bedingung 'verboten'), aber es sind noch zwei Speisewünsche zu codieren. Also müssen die nächsten Codes dreistellig sein. Unter Beachtung der Eindeutigkeit ergibt sich:
Torte → LLR Gurken → LLL
wahlweise auch:
Torte → LLL Gurken → LLR
Ist diese Codierung nun wirklich besser, d. h. kürzer? Beim alten Code benötigte der König für 18 Gerichte 36 bit. Nun sieht es bei der oben genannten Häufigkeitsverteilung folgendermaßen aus:
9 x Schweinebraten 9 bit
6 x Schokopudding 12 bit
1 x Gurken 3 bit
2 x Erdbeertorte 6 bit
---------
Summe 30 bit
Es wurden also durchschnittlich 6 bit pro Tag gespart. Probieren
wir zum Schluß der Geschichte aus, ob es klappt. Was will der
König bei "LRRRLLR"? Da die Codewortlänge variiert, muß man
schrittweise vorgehen. Das erste "L" bedeutet noch nichts. "LR"
heißt eideutig "Pudding". Dann kommt "R" für "Braten"
und gleich noch einer. Wieder ein "L", das noch nichts besagt. Auch das
folgende "L" liefert noch keine Lösung. Erst das letzte "R"
gibt Aufschluß: "Torte!".
Führt eine n-malige Verwirklichung der geforderten Bedingung in m Fällen zum zufälligen Ereignis A, dann liegt die Häufigkeit h(A) = m/n beliebig nahe an der Wahrscheinlichkeit P(A).
Jetzt können wir die Ergebnisse unseres Märchens aufarbeiten. An der königlichen Tafel sind vier zufällige Ereignisse bedeutsam:
A1: Der König bestellt Braten A2: Der König bestellt Pudding A3: Der König bestellt Torte A4: Der König bestellt GurkenAuch die Häufigkeiten sind bekannt. Wir nehmen an, daß die Werte auf genügend vielen Beobachtungen beruhen. Also können wir die Wahrscheinlichkeiten durch die Häufigkeiten annähern:
P(A1) = 9/18 = 1/2 P(A2) = 6/18 = 1/3 P(A3) = 2/18 = 1/9 P(A4) = 1/18 = 1/18Die Summe aller Wahrscheinlichkeiten P(A1) + P(A2) + P(A3) + P(A4) ergibt immer den Wert 1. Betrachten wir nun den König als Nachrichtenquelle. Seine Nachrichten sind A1, A2, A3 und A4. Die oben erwähnten Wahrscheinlichkeiten stellen zusammen mit den zugehörigen Nachrichten das Bild einer (sehr abstrakten) Nachrichtenquelle dar. Die Nachricht A1 hat eine relativ hohe, die Nachricht A4 eine relativ geringe Wahrscheinlichkeit. Mit anderen Worten: A1 dürfte in einer Nachrichtenfolge öfter auftauchen als A4 (wobei nichts über die Position von A1 ausgesagt werden kann). Damit können wir auch den Informationsgehalt definieren:
Je kleiner die Wahrscheinlichkeit des Auftretens einer Nachricht ist, desto höher ist ihr Informationsgehalt. Als Formel:
I(A) = ld( 1/P(A) ) [bit]Wenden wir nun diese Formel auf die Nachrichten A1 bis A4 an:
I(A1) = ld( 1/(1/2) ) = ld(2) = 1,000 bit I(A2) = ld( 1/(1/3) ) = ld(3) = 1,585 bit I(A3) = ld( 1/(1/9) ) = ld(9) = 3,170 bit I(A4) = ld( 1/(1/18) ) = ld(18) = 4,170 bitNun besitzen wir präzise Zahlenwerte über den Informationsgehalt der einzelnen Nachrichten. Das Maß für die Unsicherheit darüber, welche Nachricht nun als nächste in einer Folge kommt, ist die "mittlere Information" (oder Entropie) H:
H(A1, ..., An) = Summe(P(Ai) * ld(1/P(Ai))) für i=1 ... nFür unser Königs-Ernährungsproblem ergibt sich:
H = 1,000/2 + 1,585/3 + 3,170/9 + 4,170/18 = 1,614 bitDieser Wert sagt uns aber noch nicht viel; wir brauchen Vergleichswerte. Betrachten wir nun die binär codierten Essenswünsche, die ja nur noch aus den Zeichen "R" und "L" bestehen. Zunächst die erste Codierung mit jeweils zwei bit für jedes Codewort (man schreibe einfach die Codes entsprechend obiger Häufigkeiten auf und zähle die "R"s und "L"s):
P(R) = 25/36 → H1(R,L) = 0,883 bit P(L) = 11/36Nun sehen wir uns die optimierte Codierung mit unterschiedlicher Länge der Codeworte an:
P(R) = 17/30 → H2(R,L) = 0,988 bit P(L) = 13/30Also trägt hier jedes Signal mehr Information.
Es läßt sich aber für eine bestimmte aufgabe ein Code finden, für den H beliebig nahe an m liegt. Zur Informationstheoretischen Beurteilung der Eigenschaften von Codes dient die Redundanz:
absolute Redundanz relative Redundanz:
R = m - H r = (m - H)/m = R/m
Wie sieht das für unseren stets hungrigen König aus?
(1) Code mit fester Wortlänge 2:
H = 1,614 bit R = 2 - 1,614 = 0,386 m = 2 bit r = 0,386/2 = 0,193 = 19,3%
(2) Code mit variabler Wortlänge:
H = 1,614 bit R = 1,722 - 1,614 = 0,108 m = 1,722 bit r = 0,108/1,722 = 0,063 = 6,3%
Fassen wir zusammen. Das Shannonsche Codierungstheorem besagt:
Die zweite Behauptung impliziert auch, daß es nicht den optimalen Code gibt, sondern nur einen relativ besten.
Wir haben gesehen, daß Codes redundant sein können. Formelmäßig läßt sich das Maß für die Redundanz eines Codes allgemein folgendermaßen festlegen:
absolute Redundanz relative Redundanz: R = m - H r = (m - H)/m = R/mm = mittlere Codewortlänge H = Informationsgehalt
Sind alle Codewörter gleich lang, gilt:
absolute Redundanz relative Redundanz:
R = ld(M) - ld(n) r = (ld(M) - ld(n))/ld(M)
= R/ld(M)
M = Anzahl der möglichen Codewörter
n = Anzahl der verwendeten Codewörter
Beispiel: tetradische Codes (Darstellung der Ziffern 0 bis 9) Der Informationsgehalt I = ld(10) ist 3,32 bit. Wir müssen also Codeworte von 4 bit Länge verwenden. Mit 4 bit können jedoch 16 Codeworte dargestellt werden, wir haben also 10 Nutzbits und 6 Pseudoworte. Die Redundanz ergibt sich zu: Rc = 4 - ld(10) = 4 - 3,32 = 0,68 und rc = 0,68 / 4 = 0,17 → 17%.
Der Morsetelegraph hatte einen dreiwertigen Code (Punkt, Strich, Leerraum) und variable Codelänge.
Die Störung muß groß genug sein, um die physikalische Repräsentation umzukehren. Ja nach Repräsentation ist das nur schwer möglich (Vorteil gegenüber der Analogtechnik). Die "Stärke" der Störung wird durch die Bitfehler-Wahrscheinlichkeit ausgedrückt. Eine Bitfehlerwahrscheinlichkeit von z. B. 0,00001 bedeutet, daß auf 10000 übertragene Bits eines verfälscht ist. Die Bitfehlerwahrscheinlichkeit von 0 ist die theoretische Grenze und mit endlichem Aufwand nicht erreichbar. Für ISDN-Leitungen der Telekom wird beispielsweise eine Bitfehlerwahrscheinlichkeit von 10-7 für sogenannte Dauerwählverbindungen angegeben.
Aufgabe der Codesicherung ist es, die Bitfehler in Codewörtern oder Codewort-Blöcken zu erkennen oder zu beseitigen. Fehlererkennung ist nur möglich, wenn durch Bitfehler ungültige Codeworte entstehen (= Codeworte, die nicht im Codewort-Vorrat definiert sind). Bitfehler die ein Codewort in ein anderes gültiges Codewort verfälschen sind nicht erkennbar.
Beispiel: 5-4-2-1-Code:
0 1 0 1 (= 5) 0 1 0 1 (= 5)
| |
1 1 0 1 (Pseudotetrade) 0 1 0 0 (= 4)
→ Fehler erkannt → Fehler nicht erkannt
Grundsätzlich gilt: Codewörter ohne Zeichenzuornung müssen vorhanden
sein → Code muß redundant sein.
Beispiel: tetradische Codes:
m = 4 Rc = 4 - ld(10) = 4 - 3,32 = 0,68 M = 10 rc = 0,68 / 4 = 0,17 → 17%Die Redundanz stellt aber die Sicherheit gegen Übertragungsfehler noch nicht her. Codes gleicher Redundanz können unterschiedlich übertragungssicher sein.
Beispiel: 2-aus-5-Walking-Code <→ Libway-Craig-Code Für beide gilt: m = 5, M = 10, Rc = 1,68, rc = 33,6%
Beim 2-aus-5-Walking-Code führt jede Verfälschung nur eines Bits zu einem fehlerhaften Codewort. Beim Libway-Craig-Code kann ein 1-Bit-Fehler zu einem gültigen Codewort führen.
Das unterschiedliche Verhalten der beiden Codes ist darauf zurückzuführen, daß sich zwei beliebige Codeworte beim 2-aus-5-Walking-Code in mindestens zwei Stellen voneinander unterscheiden und beim Libway-Craig-Code nur ein Bit Unterschied besteht.
|
Distanz (Stellendistanz): Anzahl von Stellen, in denen sich zwei bestimmte,
gültige Codewörter eines Codes voneinander unterscheiden: 1 <= d < m
Hammingdistanz: Die Mindestzahl der Stellen, in denen sich jedes gültige Codewort eines Codes von jedem anderen unterscheidet: h = dmin Hamming-Gewicht: Die Anzahl der gesetzten Bits. Beispiel: Das Hamming-Gewicht von 1011 ist 3. Bei einer Zeichenkette ist es die Anzahl der Zeichen mit Ausnahme des Nullzeichens. |
Beispiele:
Code mit 4 Codewörtern: C1 = 0001, C2 = 0011, C3 = 0111, C4 = 1111
d12 = 1, d13 = 2, d14 = 3, d23 = 1,
d24 = 2, d34 = 1 → h = 1
Code mit 4 Codewörtern: C1 = 0000, C2 = 0011, C3 = 1100, C4 = 1111
d12 = 2, d13 = 2, d14 = 4, d23 = 4,
d24 = 2, d34 = 2 → h = 2
Für die weiter oben gezeigten Codes gilt z. B.:
2-aus-5-Walking-Code: h = 2
Libway-Craig-Code: h = 1
Alle n-aus-m-Codes besitzen die Eigenschaft h > 2; somit ist Fehlererkennung möglich, z. B. durch Überprüfung der Anzahl der 1-Bits im empfangenen Codewort.
Für die Ermittlung der Hamming-Distanz eignet sich besonders eine Matrix-Darstellung, wie
das folgende Beispiel zeigt. Gegeben sei folgende binäre Codierung:
1 = 001, 2 = 010, 3 = 011, 4 = 100
Man erhält daraus folgende Matrix:
001 010 011 100
001 - - - -
010 2 - - -
011 1 1 - -
100 2 2 3 -
Die Hamming-Distanz als kleinste Stellendistanz ist in diesem Beispiel h = 1. Mit
einem leicht abweichenden Code kann auch hier die Hammingdistanz h = 2 erreicht
werden:
000 011 101 110
000 - - - -
011 2 - - -
101 2 2 - -
110 2 2 2 -
Fehler konnen bei der Datenübertragung und Datenspeicherung auftreten. Bei einer Bit-Fehler-Wahrscheinlichkeit von z.B. 10-7 ist die Wahrscheinlichkeit für das Auftreten eines Ein-Bit-Fehlers in einem 8-Bit Wort: 8 * 10-7 * (1 - 10-7)7 ~ 8 * 10-7
Die Wahrscheinlichkeit für zwei Ein-Bit-Fehler pro 8-Bit Wort beträgt: 82 * (10-7)2 * (1 - 10-7)6 ~ 28* 10-14
→ Wichtigste Massnahme: Erkennen von Ein-Bit-Fehlern! Um eine Anzahl e von Fehlern zu erkennen, benötigt man einen Hammingabstand von mindestens e + 1. Es gilt also:
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?
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.
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
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
Ein weiteres Beispiel ist das einheitliche Kontonummernsystem (EKONS) der Banken.
Man ergänzt dort die Summe:
2·Z1 + Z2 + 2·Z3 + Z4 + 2·Z5
+ Z6 + 2·Z7 + Z8 + 2·Z9
durch Addition einer Prüfziffer p auf eine durch 10 teilbare Zahl. Hier werden
fast alle Fehler durch falsche Ziffern und Vertauschungen aufgedeckt.
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
|
Codierung des 13. Zeichens
|
Von links nach rechts besteht der gesamte EAN-13-Barcode aus:
Die letzte Ziffer (ganz rechts) ist eine Prüfziffer, die folgendermaßen ermittelt wird:
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 3Von links nach rechts besteht der gesamte EAN-8-Barcode aus:
Auch hier ist wieder das letzte Zeichen ganz links ein Prüfzeichen zur Fehlererkennung.
Um Bitfehler nicht nur erkennen, sondern auch korrigieren (d. h. lokalisieren) zu können, muß der Hammingabstand auf h >= 3 erhöht werden. Beispiel h = 3:
O: gültiges Codewort
X: ungültiges Codewort
Ein Bitfehler führt zu einem ungültigen Codewort, das sich vom verfälschten Codewort in nur einem Bit unterscheidet. Zu allen anderen gültigen Codeworten hat es mindestens zwei Bit Unter- schied. Da die Auftrittswahrscheinlichkeit des 1-Bit-Fehlers in einem Codewort wesentlich höher ist, als bei zwei oder mehr Bit- fehlern, ordnet man das fehlerhafte Codewort dem ähnlichsten gültigen Codewort zu → Fehlerkorrektur. Allgemein gilt für die Anzahl der korrigierbaren Fehler:
k = Anzahl der korrigierbaren Fehler
e = Anzahl der erkennbaren Fehler
Es existieren eine Reihe von Verfahren zur Fehlersicherung, z. B.
Beispiel: Blockübertragung mit Kreuzsicherung
Ein System zum Aufbau von Haming-Codes zur Korrektur eines Fehlers verwendet 4 Nutzbits (n1 - n4) + 3 Prüfbits (p1 - p3) → 7 Bits:
Berechnung der Prüfbits (Addition modulo 2):
Beispiel: 8421-Code mit Hammingzusatz (h = 3):
Wert | p1 p2 n1 p3 n2 n3 n4
-----+---------------------
0 | 0 0 0 0 0 0 0
1 | 1 1 0 1 0 0 1
2 | 0 1 0 1 0 1 0
3 | 1 0 0 0 0 1 1
4 | 1 0 0 1 1 0 0
5 | 0 1 0 0 1 0 1
6 | 1 1 0 0 1 1 0
7 | 0 0 0 1 1 1 1
8 | 1 1 1 0 0 0 0
9 | 0 0 1 1 0 0 1
Gesendet wird: 1 0 0 0 0 1 1
empfangene Prüfbits: 1 0 0
berechnete Prüfbits: 1 1 1
Daraus ergibt sich:
1 0 0
1 1 1
-------
(Antivalenz): 0 1 1
LSB MSB
"von rückwärts" gelesen: 1 1 0
→ Stelle 6 ist zu korrigieren.
Ganz allgemein gilt für das Verhältnis von Daten- und Prüfbits:
| Datenbreite | Prüfbits | Codebreite | Prüfbits/Datenbits |
|---|---|---|---|
| 4 | 3 | 7 | 75% |
| 8 | 4 | 12 | 50% |
| 16 | 5 | 21 | 31% |
| 32 | 6 | 38 | 19% |
| 64 | 7 | 71 | 11% |
| 128 | 8 | 136 | 6% |
| 256 | 9 | 265 | 4% |
