4. Codierung

Def. Unter Codierung versteht man das Umsetzen einer vorliegenden Repräsentation A in eine andere Repräsentation B . Häufig liegen beide Repräsentationen A und B in der selben Abstraktionsebene. Die Interpretation von B nach A muss eindeutig sein. Ist sie auch umkehrbar eindeutig, so spricht man von einer Umcodierung .

Die folgende Tabelle zeigt eine Reihe mehr oder weniger gebräuchlicher binärer Codierungen für Dezimalziffern.

Jede Wandlung von einem Code dieser Tabelle in einen anderen der Tabelle ist eine Umcodierung. Welcher Code vorliegt, geht nicht aus den Codewörtern hervor.

Def. Werden zur Repräsentation B Wörter eines Zeichenvorrats Z verwendet, so bezeichnet man diese als Codewörter .

Def. Die Menge aller Codewörter heißt Code .

Def. Ein Code, dessen Codewörter alle dieselbe Länge haben, heißt Blockcode .

Def. Enthält ein Zeichenvorrat nur genau zwei verschiedene Zeichen, so nennt man diese Zeichen Binärzeichen und Wörter aus diesen Binärwörter .

Def. Sind die Codewörter Binärwörter, so liegt ein Binärcode vor.

Alle in der obigen Tabelle genannten Codes sind Binärcodes, jeweils eine Spalte listet alle Codewörter des Codes. Heute werden Zahlen, mit denen gerechnet werden soll, zumeist nicht dezimal gespeichert. Die genannten Codes sind daher nicht sehr gebräuchlich.

Außerordentlich wichtig ist dagegen die Codierung von geschriebenem Text. Man trennt dabei den reinen Text von seiner Formatierung. Der reine Text besteht aus der Reihenfolge der Zeichen. Die Formatierung dagegen gibt die Wahl des Fonts, die Größe, Farbe etc. an. Der reine Text wird üblicherweise codiert mit 8-Bit-Wörtern pro Zeichen. Das ermöglicht die Benutzung von 256 verschiedenen Symbolen einschließlich einiger Steuerzeichen für den Drucker. Leider sind das zu wenig Zeichen, um alle nationalen Zeichensätze enthalten zu können. Der reine Text benötigt daher immer die Information, welcher nationale Zeichensatz verwendet werden soll.

Die folgende Tabelle liefert den ASCII-Code in Matrixform. Das zu einem Zeichen gehörige Codewort wird nach Klick auf das Zeichen in der Titelleiste in rot dargestellt, und zwar als 8-Bit-Binärwort, 2-stellig Hexa und als Zahlenwert der Ganzzahlinterpretation.

asciimat

Die Schwierigkeiten im Umgang mit verschiedenen nationalen und speziellen Zeichensätzen einerseits und die Verfügbarkeit großer und billiger Speicher haben zur Entwicklung des 16-Bit-Uni-Codes geführt, der in 65536 Codewörtern die nationalen Zeichensätze praktisch aller lebenden Schriften einschließlich der chinesischen und japanischen und der Blindenschrift ermöglicht sowie auch die der meisten historischen Schriften wie Ogham und Runen. Auch eine sehr große Zahl von Symbolen ist vorhanden inklusive aller nötigen Zeichen für einen klassischen Notensatz.

Einschrittige Codes

Eine Menge, in der eine Ordnungsrelation gilt, kann durch einen einschrittigen Binärcode repräsentiert werden. Benachbarte Elemente der Menge werden dabei repräsentiert durch Binärwörter, die sich in genau einer Stelle unterscheiden. Solche Codes müssen immer dann benutzt werden, wenn das Ablesen der Bits nicht verhindert werden kann, wenn gerade ein Wechsel zwischen zwei Codewörtern stattfindet. Die folgende Graphik demonstriert das Ablesen mit unvermeidlichen zufälligen Verschiebungen bei den einzelnen Bits:

demoeinschritt(0:59);            % nicht-einschrittiger Code

demoeinschritt(einschritt(60));  % einschrittiger Code

Einschrittige Codes der Länge n werden entweder durch Finden eines nicht unterbrochenen Weges der Länge n in einem KV-Diagramm entworfen

oder rekursiv:
Hat der Code nur 2 Codewörter, so sind dies die Bits 0 und 1 . Andernfalls generiert man einen einschrittigen Code C der Länge ceil(n/2) . Den ersten Teil des gesuchten Codes erhält man durch Verlängerung der Codewörter von C durch eine 0 , den zweiten durch Anfügung einer 1 an den in umgekehrter Reihenfolge notierten Code C .

openbyextension('einschritt.m')

Ein einschrittiger Code mit 12 Wörtern ist z.B. der folgende

binmatout(num2binmat(einschritt( 12 )',ceil(log2( 12 ))))

Die beiden Gray-Codes in der Tabelle zur Codierung der Dezimalziffern sind einschrittig.

Unterscheiden sich auch das erste und das letzte Codewort eines einschrittigen Codes nur in einem Bit, so liegt ein zyklisch einschrittiger Code vor. Die mit der Funktion einschritt(n) rekursiv generierten einschrittigen Codes sind zyklisch einschrittig, wenn n gerade ist. Zyklisch einschrittige Codes werden z.B. bei binärer Winkelcodierung benötigt.

Codes variabler Länge

Bei der seriellen Übertragung können die Codewörter eines Blockcodes einfach aneinandergehängt (concateniert) werden. Wegen der festen Länge der Codewörter sind diese später wieder zu rekonstruieren, sofern kein Bit verlorengeht.

Die Zerlegung einer unstrukturierten Bitsequenz in Codewörter ist auch möglich, wenn die Codewörter unterschiedliche Länge haben. Eine hinreichende Bedingung dafür ist die Fano-Bedingung : Kein Codewort ist identisch mit dem Anfang eines anderen Codewortes.

Als Beispiel nehmen wir den einfachsten Fall eines binären Fano-Codes, bei dem drei Symbole codiert werden in die Codewörter 1 ; 01 ; 00 . Als Symbole nehmen wir der Reihe nach die Symbole "Punkt" ; "Strich" und "Zeichentrennung" des Morsecodes. Damit kann nun jeder Text aus dem Alphabet
"ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.-?/"
zunächst nach Morse codiert und anschließend mit obigem Fano-Code binär umcodiert werden.

Zur Umcodierung von ASCII nach Morse nehmen wir die Funktion str2morse :

str2morse('HALLO')

Und zur Umcodierung dieses Strings in den oben genannten speziellen Fano-Code die Funktion

morse2bits( str2morse( 'HALLO' ));

Die Umkehrung erfolgt mit

morsebits2text( morse2bits( str2morse( 'HALLO' ) ) )

Im Gegensatz zum Blockcode gelingt das Zerlegen der Bitsequenz in Codewörter in diesem Fall auch dann sicher, wenn Bits verloren gehen oder eingefügt werden. Bei der folgenden Demonstration wird der korrekten Bitsequenz eine zufällige Anzahl von 0...n-1 zufälliger Bits vorangestellt. Dann wird dieser Bitvektor dekodiert um zu zeigen, dass der Code auch nach beliebigen Fehlern sofort wieder dekodiert werden kann. Zum Vergleich wird das selbe mit der ASCII-Codierung durchgeführt. In diesem Fall gelingt das Lesen nur, wenn die Anzahl der eingefügten Bits ein Vielfaches von 8 ist.

demomorserobust

Das automatische Decodieren realer tönender Morsesignale ist ein Problem der Nachrichtentechnik, das hier nicht behandelt wird.

morsesound('INFORMATIK',120,660,2000);