Binäre Codes und Code-Umsetzer

[ EDEMI ] [ Inhalt ]   [ rückwarts ] [ vorwärts ]
 
  1. Historische Einordnung
  2. Erklärung des Begriffes "binär"
  3. Erklärung des Begriffes "code"
  4. Binäre Codes
    1. 8-4-2-1 Code
    2. Aiken Code
    3. Exzeß – 3 Code
  5. Subtraktion in Tetradencodes
  6. ASCII – Code
  7. Elementarvorrat
  8. Ungesicherte Codes
  9. Fehlererkennende Codes
  10. Fehlerkorrigierende Codes
  11. Codes mit Prüfbit
  12. Anhang
    1.  Worterläuterungen
    2. Aufgaben
    3. Tabelle zu Beispielen von Binär Codes
[ nach oben ]

1. Historische Einordnung

Der Mathematiker George Boole(1815-1864) war der Begründer der mathematischen Logik. Seiner Ansicht nach ist eine Aussage "wahr" oder "falsch", oder sie wird "negiert" – etwas anderes kann es nicht geben! Alle anderen Aussagen müssen darauf zurückzuführen sein.
Diese algebraische Beschreibung logischer Probleme wurde nach ihren Entwickler Boole benannt, die "Boolsche Algebra" gliedert sich heutzutage in folgende Punkte:
  1. Mengenalgebra
  2. Aussagenalgebra und symbolische Logik
  3. Wahrscheinlichkeitsrechnung
  4. Schaltalgebra
Erst viel später, nachdem Schaltungen auf binäre Basis (0,1) bereits existierten, erkannte man in der "Boolschen Algebra" das allgemeine mathematische Beschreibungsmittel zum Entwurf von Schaltungen.
[ nach oben ]

2. Erklärung des Begriffes "binär"

Das Wort "binär" bedeutet auch zweiwertig, dual oder bivalent.

Es bezeichnet die Eigenschaften einer Speicherzelle, einen von zwei Werten anzunehmen. Datenverarbeitungssysteme (DV-Systeme) bestehen aus elektronischen Bauelementen; diese elektronischen Bauelemente können nur zwei verschiedene Zustände annehmen, deshalb werden Sie auch binäre oder duale Bauelemente genannt.

Es gib eine ganze Reihe von Darstellungsmöglichkeiten für diesen zweiwertigen Zustand.
 
Der Strom fließt oder fließt nicht  (elektrischer Leiter) 
Der Strom fließt nach links oder rechts  (geschlossener Leiter) 
Es liegt eine positive oder negative Spannung an  (Halbleiter) 
Ein Magnetfeld besteht oder besteht nicht  (Magnetspeicher) 
 Alle zweiwertigen Zustände haben eines gemeinsam: sie können in kurzer Zeit die Form verändern, da sich im Idealfall elektrische oder magnetische Felder bzw. Licht mit einer Geschwindigkeit von 300000 km/sec bewegen. Daraus läßt sich die hohe Geschwindigkeit folgern, mit der die Rechner heutzutage arbeiten.

Um den zweiwertigen Zustand auch außerhalb des Rechners darzustellen, verwendet man das binäre Zahlensystem. Dabei werden die beiden Ziffern 0 und 1 als jeweiliger Ausdruck für einen der beiden möglichen Werte verwendet.

[ nach oben ]

3. Erklärung des Begriffes "code"

Ein Code dient zur Übertragung von Informationen in einer Zeichenart zu einer anderen Zeichenart. Das bedeutet eine formale Änderung, wobei der Inhalt der Information unverändert bleibt.

Als Code wird in diesem Zusammenhang häufig auch ein bestimmter Zeichenvorrat bezeichnet, wie z.B. der ASCII-Code oder der EBCDI-Code.

[ nach oben ]

4. Binär Codes (binary codes)

Der binär Code ist auch bekannt als binäre Verschlüsselung oder Dualcode. Dieser Code basiert auf zweiwertiger Basis, also nur zwei verschiedene Zeichen. Zur Darstellung ausreichend großer Mengen unterschiedlicher Zeichen werden Kombinationen von Binärzeichen (sogenannte Bitmuster) gebildet.

Grundlage für dieses Bit ist der Inhalt 0 oder 1; für die Darstellung einer Dezimalzahl sind mindestens 4 Bit nötig. Mit 4 Bit können 24 = 16 Zeichen verschlüsselt werden, also auch die Dezimalzahlen 0-9. Diese Kombinationen werden auch als Tetraden bezeichnet. Die restlichen Kombinationen der Dezimalzahlen 10-15 bezeichnet man als Pseudotetraden.

Im Folgenden werden einige binär Codes näher erklärt.

[ nach oben ]

4.1. 8-4-2-1 Code

Der 8-4-2-1 Code ist zum Umschreiben von Dezimalzahlen in Binärzahlen geeignet. Bei ihm werden die Dezimalzahlen 0-9 in das Dualsystem verschlüsselt. Erfolg in der Dezimalzahl ein Zehnerübertrag, so muß in der Binärzahlrechnung als Korrektur 0110 addiert werden.

Beispiel :
 
0100 0001 0111 0101 = 8-4-2-1 Tetraden für 4175
+0010 0011 1001 1000 = 8-4-2-1 Tetraden für 2398
0110 0101 0000 1101  
nein nein ja ja = Zehnerübertrag
    0110 0110 = Korrekturtetrade
0110 0101 0111 0011 = 8-4-2-1 Tetraden für 6573

[ nach oben ]

4.2. Aiken Code

Der Aiken – Code ist für elektronische Zähler sehr gut geeignet. Doch wie beim 8-4-2-1-Code existieren beim Addieren komplizierte Sonderregeln. Eine interessante Eigenschaft des Aiken – Codes ist, daß bei ungeraden Dezimalzahlen die letzte Binärstelle eine 1 und bei geraden Dezimalzahlen die letzte Binärstelle ein 0 hat, wobei die erste Binärstelle bei den Werten 0-4 das Zeichen 0 und bei den Werten 5-9 das Zeichen 1 hat.
Beim Aiken – Code bewirkt ein Dezimalübertrag auch einen Tetradenübertrag.

Beispiel:
 
  1101  = Aiken Tetrade für 7
  1100  = Aiken Tetrade für 6
  1001  = Aiken Pseudotetrade und Übertrag
  -0110  = Korrekturtetrade (-6)
0001 0011  = 2 Aiken Tetrade für 13

[ nach oben ]

4.3. Exzeß – 3 Code

Der Exzeß-3-Code hat keine Stellenbewertung für die Dezimalziffern 0-9. Die verschiedenen Kombinationen aus 0 und 1 sind den Dezimalzahlen nur zugeordnet, deshalb wird der Exzeß-3-Code auch als ein Zuordnungscode bezeichnet. Der Exzeß-3-Code ist durch einfache Korrekturen zum Rechnen geeignet. Erfolg bei einer Addition einer Dezimalstelle ein Zehnerübertrag, so entsteht auch in der binären Rechnung ein Übertrag. Daraus folgt, daß als Korrektur 0011 (3) zum Ergebnis addiert werden muß. Falls kein Übertrag stattfindet, so muß den dem Ergebnis als Korrektur 1101 (-3) zu addiert werden.

Beispiel:
0100 1011 = Exzeß-3 Tetraden für 18
0100 0110 = Exzeß-3 Tetraden für 13
1001 0001  
1101 0011 = Exzeß-3 Korrekturtetraden
0110 0100 = Exzeß-3 Tetraden für 31

[ nach oben ]

5. Subtraktion in Tetradencodes

Bei Aiken-Code und Exzeß-3-Code erfolgt die Subtraktion mit Hilfe der Komplementbildung. Die Komplementbildung erfolgt durch eine einfaches Vertausch von 1 und 0.

Beispiel : 17 – 14 = 3 im Aiken-Code
 
0 0001 0100 = +14
1 1110 1011 = -14 (Komplementbildung
0 0001 1101 = +17
0 0000 1000  
0 0000 1001 = +Übertrag
    -0110 = Korrekturtetrade(-6) 
0 0000 0011 = +3

[ nach oben ]

6. ASCII – Code

Der ASCII-Code (American Standart Code for Information Interface) ermöglicht nicht nur die Verschlüsselung von Dezimalzahlen, sondern auch von Texten und Zeichenketten. Diese Darstellung nennt man auch alphanumerische Darstellung. Mit jeweils 8 Bit = 1 Byte werden die alphanumerischen Zeichen verschlüsselt, d.h. es können 28 = 256 verschiedene Zeichen verschlüsselt werden. Der ASCII-Code verwendet 128 Zeichen, Großbuchstaben, Kleinbuchstaben, Ziffern und Sonderzeichen, sowie Steuerungssignale. Für 128 Zeichen sind nur 7 Bit notwendig, da bei der alphanumerische Darstellung aber 8 Bit zur Verfügung stehen, verwendet man das 8te Bit als Prüfbit. Das 8te Bit ist dann 1, wenn die Quersumme der Bit mit dem Wert 1 geradzahlig ist . Die 8 Bit Verschlüsselung der Ziffer 7 ist beispielsweise 0011 0111.
[ nach oben ]

7. Elementarvorrat

In dem folgenden Beispiel soll die Codierung anhand  einer Nachrichtenübertragung verdeutlicht werden. Man nehme an, daß der Sender über einen Nachrichtenvorrat von 8 Buchstaben (A-H) verfügt, dies bedeutet, daß sein Elementarvorrat (EV) = 8 beträgt.
Der Elementarvorrat gibt also die Anzahl der Zeichen des Alphabets (Codes) an. Möchte der Sender z.B. die Nachricht "C" an den Empfänger übertragen, so muß er sich eines physikalischen Mediums bedienen;  in unseren Beispiel sollen dafür drei Lampen zur Verfügung stehen.
Jede Lampe hat zwei Zustände, sie ist entweder eingeschaltet = 1 oder ausgeschaltet = 0. So erhalten wir ein Binärsystem, bei dem jeder der 8 Buchstaben unseres Alphabets einer Kombination aus 0 und 1 zugeordnet werden kann. Bedingung für eine  korrekte Übertragung ist, daß Sender und Empfänger über die selbe Zuordnungsliste zwischen dem Nachrichten-Alphabet (Alphabet 1) und dem Signal-Alphabet (Alphabet 2) verfügen.
[ nach oben ]

8.Ungesicherte Codes

Bei der Übertragung codierter Zeichen wird ein völlig fehlerfreies Arbeiten der technischen Geräte angestrebt. Dennoch können Fehler nicht gänzlich ausgeschlossen werden. Da bei der Codierung fast ausschließlich mit binären Zeichen (0,1) gearbeitet wird, kann es vorkommen, daß durch eine Störung im Übertragungskanal ein Zeichen umgekehrt wird. Einigt man sich beispielsweise auf die Darstellung von 1 durch einen Spannungsimpulse von 4V und auf die Darstellung von 0 durch einen Impulse von 0V, so führt schon ein Störimpulse von 2V zu einem Fehler, da eine eindeutige Zuordnung dieser Spannung zu einem Binärzeichen nicht möglich ist. Um solchen Fehlern vorzubeugen, verwendet man Codes, die es dem Empfangsgerät ermöglichen, Fehler zu erkennen oder sogar zu korrigieren. Bei einen ungesicherten Code werden alle Codeworte als Nutzworte (NW) verbraucht. Jede Störung führt zu einem neuen Nutzwort, welches vom Empfänger angenommen wird. Bei einem ungesicherten Code ist keine Redundanz vorhanden.

Redundanz tritt auf, wenn bei einem Code mehr Informationen übertragen werden, als gebraucht werden. Je größer die Redundanz ist, desto besser ist die Fehlererkennung; diese verlangen aber auch höhere Kosten. Geht man z.B. von einem zweistelligen Code (EV = 2² = 4 Zeichen) A, B, C, D aus ( A = 00, B = 01, C = 10, D = 11), so kann ein Fehler, z.B. bei A = 00 zu den neuen Worten B = 01 oder C = 10 führen. Dies bedeutet, daß keine Fehlererkennung möglich ist.

[ nach oben ]

9. Fehlererkennede Codes

Um Fehler bei einer Übertragung zu vermeiden, darf bei einem Code nicht der gesamte Elementarvorrat als Nutzworte verbraucht werden. Einige Kombinationen müssen  Pseudoworten (PW) zugeordnet werden. Diesen Pseudoworten wird zwar Binärcode aus dem Alphabet 2 zugeordnet, aber keine Information aus dem Alphabet 1. Diese Codes besitzen also eine Redundanz. Verwenden wir einen 3stelligen Code (EV = 2³ = 8), werden zwei Codeworte als Nutzworte (A,B, C, D) und zwei Codeworte als Pseudoworte verwendet.
Wir können also bei diesem fehlererkennenden Code -  trotz des 2stelligen Codes -  nur zwei Nachrichten übertragen.

Empfängt der Empfänger nun ein Pseudowort (001 oder 010), so erkennt er den Fehler und kann eine Wiederholung der Übertragung veranlassen.

[ nach oben ]

10. Fehlerkorrigierende Codes

Bei fehlerkorrigierende Codes nimmt man an, daß nur ein Fehler pro Nutzwort auftritt.
Tritt bei der dargestellten Zuordnung ein Übertragungsfehler auf, so wird PW empfangen, welches wieder dem ursprünglichen Nutzwort zugeordnet werden kann.

Nun kann man die zu erkennenden und zu korrigierenden Fehler berechnen.

Hammingdistanz(h): geringste paarweise Stellendistanz zwischen allen Nutzworten eines Codes
 Allgemein gilt : e = h –1 e = die Anzahl der mit Sicherheit zu erkennenden Fehler 
  k = (h –1 ) / 2 k = die Anzahl der mit Sicherheit richtig zu korrigierenden Fehler
daraus ergibt sich die Beziehung: e = 2 * k  
 

 
 
bei unserem Beispiel ergibt sich daraus e = h – 1 = 3 – 1 = 2 2 Fehler werden erkannt
  k = (h – 1) / 2 = (3 – 1) / 2 = 1 1 Fehler kann korrigiert werden
 
[ nach oben ]

11. Codes mit Prüfbit

Bei Codes mit Prüfbit wird ein Bit pro Nutzwort dazu benutzt, um eine gerade (even parity check) oder ungerade (add parity check) Quersumme anzuzeigen. Der Empfänger ermittelt das Prüfbit des Nutzwortes und vergleicht es mit dem übertragenen Prüfbit. Bei einer Übereinstimmung war die Übertragung erfolgreich, bei einer Nichtübereinstimmung wird eine Wiederholung der Übertragung veranlaßt.
[ nach oben ]

12. Anhang

12.1. Worterläuterungen

Code:  bei der Codierung angewandte Regel der Zuordnung
Codierung:  Zuordnung eines Zeichens aus dem Alphabet 1 zu einem Zeichen eines Alphabet 2
Codeworte:  alle 0,1 – Kombinationen eines Codes (Alphabet 2)
Nutzworte:  alle 0,1 – Kombinationen, denen in Alphabet 1 eine Nachricht zugeordnet ist
Pseudoworte:  alle 0,1 – Kombinationen, denen in Alphabet 1 keine Nachricht zugeordnet ist
Stellen-Distanz(d):  Anzahl Binärstellen, in denen sich jedes Nutzwort von jedem anderen Nutzwort eines Codes unterscheidet
Hammingdistanz(h):  geringste paarweise Stellendistanz zwischen allen Nutzworten eines Codes
es gilt:  h =< d
Zahl der mit Sicherheit erkannten Fehler e:  e = h – 1 
Zahl der mit Sicherheit richtig korrigierten Fehler k:  k = (h-1) / 2 
  e = 2 * k
 [ nach oben ]

12.2 Aufgaben

 1. Gegeben sei ein Code mit den Nutzworten
 
NW1: 0110
NW2:
 0011
NW3: 1010
 
  • Ermitteln Sie alle Stellendistanzen !
  • Ermitteln Sie die Hammingdistanz !
  • Wie groß ist die Zahl der mit Sicherheit erkennbaren Fehler ?

    •  
    2. Gegeben seien folgende beiden Codes
     
    A:  00101 B:  00101
      10001   10011
      11011   11100
     Bei welchem Code ist die Zahl der mit Sicherheit erkennbaren Fehlern größer ?

    3. Wie groß ist die Hammingdistanz (h) eines Codes mit den Nutzworten 0011, 1000, 1101 ?

     

    4. Wie groß ist die Zahl der mit Sicherheit erkennbaren Fehler im Code nach Aufgabe (3) ?

     

    5. Bei welchem Übertragung-Code benötigt man neben dem eigentlichen Übertragungskanal noch einen Rückmeldekanal ?

    1. bei fehlererkennede Codes
    2. bei fehlerkorrigierende Codes
    3. bei ungesicherten Codes
    [ nach oben ]

    12.3. Tabelle zu Beispielen von Binär Codes

     
    Dezimalzahl  8-4-2-1 Code  Exzeß-3 Code  Aiken Code 
    0  0000  0011  0000 
    1  0001  0100  0001 
    2  0010  0101  0010 
    3  0011  0110  0011 
    4  0100  0111  0100 
    5  0101  1000  1011 
    6  0110  1001  1100 
    7  0111  1010  1101 
    8  1000  1011  1110 
    9  1001  1100  1111 
    Darstellung ohne Pseudotetraden
    Tetradencode  8-4-2-1 Code  Exzeß-3 Code  Aiken Code 
    0000  0  *  0 
    0001  1  *  1 
    0010  2  *  2 
    0011  3  0  3 
    0100  4  1  4 
    0101  5  2  * 
    0110  6  3  * 
    0111  7  4  * 
    1000  8  5  * 
    1001  9  6  * 
    1010  *  7  * 
    1011  *  8  5 
    1100  *  9  6 
    1101  *  *  7 
    1110  *  *  8 
    1111  *  *  9 
     
      Darstellung mit Pseudotetraden (*)
    Exzeß-3 Code : Kodewert = Dualwert + 3

    Aiken Code : Kodewert = Dualwert, falls Zahlenwert < 5

    Kodewert = Dualwert + 6, falls Zahlenwert >= 5

    [ EDEMI ] [ Inhalt ] [ nach oben ] [ rückwarts ] [ vorwärts ]