Digitaltechnik


Prof. Jürgen Plate

2 Codes

Das Problem der Codierung von Informationen ist uralt. Bereits in der Frühgeschichte bediente nan sich zur Übermittlung von Nachrichten eines vereinbarten Symbol- oder Signalvorrats. Durch die Sprache wurde die direkte, mit der Schrift auch die zeitlich versetzte Kommunikation möglich. Die von uns verwendete Sprache und Schrift ist nur eine der vielen möglich Symbol- oder Signalvereinbarungen.

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.

2.1 Zielsetzung, Entwurfskriterien

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.

Einige Definitionen:

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:

M = Bn

Für die Codierung von M unterschiedlichenNachrichten kann man den notwendigen Coderahmen n berechnen:

n = logB(M)

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äthelldunkel
Zahlen10
Zuständegelochtungelocht
Wahrheitswertewahrfalsch
Spannungen5 Volt0 Volt
Ströme20 mA0 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.

2.2 Kenngrößen von Codes

Zur binären Codierung aller Zeichen einer Objektmenge sind Codewörter aus einer bestimmten Anzahl von Binärzeichen nötig. Mit einer Stellenzahl (= Wortlänge) von n können entsprechend der obigen Formel

M = 2n

verschiedene (gleichlange) binäre Codewörter gebildet werden. Zur Codierung von M Zeichen sind also Codeworte der Länge

n = aufgerundet(ld (M))

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).

Gründe für die Codierung:

2.3 Forderungen an einen Code:

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):

2.4 Einteilung der Binärcodes

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).

2.5 Beispiele für numerische Codes

Einige der vorgestellten numerischen Codes haben ihre Bedeutung mit dem Fortschreiten der technischen Entwicklung verloren. Sie wurden entwickelt, um beim Bau von Rechenanlagen elektrische oder elektronische Komponenten zu sparen (z. B. Rundungserkennung). Die Namen der Codes sollte man aber zumindest einmal gehört haben.

Dualcode

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.

BCD-Codes (binary coded decimal)

Jede Ziffer einer Dezimalzahl wird unabhängig codiert → ziffernorganisierte binäre Codierung. Es entsteht eine gemischte Darstellung; die Ziffernstruktur der Objektmenge bleibt erhalten und jeder Dezimalziffer wird ein binäres Codewort zugeordnet. Zur Darstellung werden 4 Bit benötigt → tetradischer Code. Das Codewort für eine Ziffer wird Tetrade genannt.

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.

Mehrstellige BCD-Codes (n > 4, nicht tetradisch)

Häufig werden für die Codierung der Dezimalziffern mehr als vier Binärstellen verwendet → Übertragungssicherheit, Ausgabe, etc. Bedeutung haben fast nur Codes mit gleicher Anzahl der 1-Bits in allen Codeworten → gleichgewichtige Codes → hohe Redundanz.

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:

Einschrittige BCD-Codes

Bisher haben sich beim Übergang von einem Codewort zum nächsten mehrere Bits geändert → mehrschrittige Codes. Bei Abtastvorrichtungen für die Längenmessung oder bei der Analog-Digital-Wandlung gibt es mit solchen Codes Fehlentscheidungen, wenn Abtastung und Signalwechsel gleichzeitig erfolgen → Bei einschrittigen Codes unterscheiden sich benachbarte Codeworte nur in einem Bit. Beispiele:

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

Mehrschrittige Anordnungscodes

Codes für spezielle Aufgaben. Als Beispiel 7-Segment-Code für Ziffernanzeigen.

2.6 Beispiele für alphanumerische Codes

Binärcodes für die Darstellung von Buchstaben, Ziffern und Sonderzeichen. Nach der Wortlänge unterscheidet man 5-, 6-, 7- und 8-Bit-Codes. Die mindestens benötigte Codewortlänge ergibt sich aus:

10 Ziffern, 26 Buchstaben, 10 Sonderzeichen → 46 Zeichen → 6 Bit Wortlänge

5-Bit-Codes

Hier erfolgt eine Doppelbelegung → nicht eindeutig, es wird ein Umschaltzeichen (Einfachbelegung) benötigt. Störung bei Übertragung des Umschaltzeichens führt zu falscher Decodierung.

6-Bit-Codes

Wenig verbreitet; neben Buchstaben, Ziffern und Sonderzeichen auch Steuerzeichen vorgesehen.

7-Bit-Codes

8-Bit-Codes

Unicode

Unicode ist ein internationaler Standard, in dem langfristig für jedes sinntragende Zeichen bzw. Textelement aller bekannten Schriftkulturen und Zeichensysteme ein digitaler Code festgelegt wird. Ziel ist es, das Problem unterschiedlicher, inkompatibler Kodierungen zu beseitigen. In Unicode finden Zeichen der wichtigsten ISO-Zeichensätze eine 1:1-Entsprechung (das bedeutet, dass bei einer Konvertierung von ISO zu Unicode und zurück das gleiche Ergebnis herauskommt). Unicode wird laufend um Zeichen weiterer Schriftsysteme ergänzt.

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):

2.7 Codierung mit variabler Wortlänge

Alle obigen Beispiele repräsentieren Codes mit einer festen Wortlänge. Jedes vom Sender zu übertragende Zeichen besteht aus gleich vielen Symbolen. Bei einem Datenstrom vom Sender zum Empfänger gibt es deshalb beim Empfänger nicht das Problem, wo ein Zeichen beginnt und endet.

Ü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.

"Vom schweigsamen König, der gern Schweinebraten aß"

(Frei nach: Walter R. Fuchs: Knaur's Buch der Denkmaschinen, 1968)

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:

  1. Es sind vier Worte binär zu codieren, also brauche ich eine Codewortlänge von mindestens 2 Binärzeichen.
  2. Die Codierung der vier Speisewünsche sah folgendermaßen aus:

    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!".

Mathematischer Hintergrund:

Oben war von "Häufigkeiten" die Rede. Es handelt sich dabei um Erfahrungswerte, die durch Beobachtung gewonnen werden (empirische Werte). Die empirischen Häufigkeitswerte müssen zu den theoretischen Wahrscheinlichkeiten in klare Beziehung gebracht werden. Wir wissen alle, daß beim Münzwurf die Wahlscheinlichkeit für Kopf oder Zahl jeweils 1/2 beträgt. Um durch empirische Ermittlung auf die exakte Übereinstimmung zwischen Häufigkeiten und Wahrscheinlichkeit zu kommen, müßte man unendlich viele Würfe auswerten. Die praktische Regel der Wahrscheinlichkeitsrechnung erspart uns Zeit, denn sie besagt, daß sich bei genügend vielen Versuchen die Häufigkeit eines Ereignisses nur noch sehr wenig von der Wahrscheinlichkeit für das Eintreten dieses Ereignisses unterscheidet. Es gilt:

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 Gurken 
Auch 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/18 
Die 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 bit 
Nun 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 ... n 
Für unser Königs-Ernährungsproblem ergibt sich:
   H = 1,000/2 + 1,585/3 + 3,170/9 + 4,170/18 = 1,614 bit 
Dieser 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/36 
Nun 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/30 
Also trägt hier jedes Signal mehr Information.

Coderedundanz

Dank der bisher erarbeiteten Formeln läßt sich diese auch nun exakt berechnen. Alle bisherigen Beispiele zeigen, daß durch die Codierung im Mittel mindestens soviele Binärstellen m verwendet werden müssen, wie durch den mittleren Informationsgehalt H berechnet werden. Es gilt also immer: H <= m.

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:

  1. es eine untere Grenze für die mittlere Codewortlänge gibt
  2. die Redundanz eines Codes beliebig klein werden kann

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/m 
m = 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.

2.8 Fehlersicherung

Bei der Übertragung und Speicherung von Nachrichten können Fehler auftreten. "Fehler" eines binären Signals ist die Inversion dieses Signals (0 → 1, 1 → 0). Diese Störungen führen zur Verfälschung von Symbolen.

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:
1 = 000, 2 = 011, 3 = 101, 4 = 110
       000 011 101 110
   000  -   -   -   -
   011  2   -   -   -
   101  2   2   -   -
   110  2   2   2   - 

2.9 Fehlererkennung

Codes für die Fehlererkennung sind so zu konstruieren, daß h = 2 ist → "fehlererkennende Codes", "prüfbare Codes". Hierzu gehören z. B. die oben erwähnten m-aus-n-Codes (gleichgewichtige Codes).

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:

Anzahl erkennbarer Fehler 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?

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:

Die letzte Ziffer (ganz rechts) ist eine Prüfziffer, die folgendermaßen ermittelt wird:

  1. Quersumme aller Ziffern in ungerader Position
  2. Quersumme aller Ziffern auf gerader Position
  3. Ergebnis von b) multipliziert mit 3
  4. Summe von a) und c)
  5. 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:

Auch hier ist wieder das letzte Zeichen ganz links ein Prüfzeichen zur Fehlererkennung.

2.10 Fehlerkorrektur

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 = (h - 1)/2 = e/2

k = Anzahl der korrigierbaren Fehler
e = Anzahl der erkennbaren Fehler

Es existieren eine Reihe von Verfahren zur Fehlersicherung, z. B.

Ganz allgemein gilt für das Verhältnis von Daten- und Prüfbits:

DatenbreitePrüfbitsCodebreitePrüfbits/Datenbits
43775%
841250%
1652131%
3263819%
6477111%
12881366%
25692654%

Zum vorhergehenden Abschnitt Zum Inhaltsverzeichnis Zum nächsten Abschnitt


Copyright © Hochschule München, FK 04, Prof. Jürgen Plate
Letzte Aktualisierung: