Codetheorie

Inhaltsverzeichnis

1. Geschichte der Codes - Voynich-Manuskript 2
2. Grundbegriffe 3
3. Code fester Länge 3

3.1 Decodierung 4

3.2 Rendundanz 4

3.3 Beispiele 4

4. Codes variabler Länge 5

5. Erhöhung des Übertragungssicherheit 6

5.1 Hamming-Distanz 6

5.2 Fehlererkennende Codes 6

5.3 Fehlerkorrigierende Codes 7

Entwurf fehlerkorrigierender Codes 8

5.5 Paritätskontrolle 8
5.5.1 Längsparitätskontrolle 8
5.5.2 Querpartätskontrolle 8
5.6 CRC-Codes 8

CRC-Sicherung mit Polynomcode 9

6 Binärcodes 10

6.1 Allgemeines 10
6.1.1 Binäre Codes 10

6.1.2 Mögliche Eigenschaften von Codes 11

6.1.3 Decoder 11
6.1.4 Encoder 12
6.2 Dual-Code 12
6.2.1 Tabelle 12
6.2.2 Beispiel für eine Binär-Hex-Umrechnung 12
6.2.3 Karnaugh-Diagramm: 13
6.3 BCD-Code 13
6.4 Gray-Code 13
6.5 Hamming-Code 14
6.6 ASCII-Code 15
6.7 HUFFMAN-CODE 15

1. Geschichte der Codes - Voynich-Manuskript

Das sogenannte Voynich-Manuskript, ein 232 Seiten umfassendes illustriertes Buch, ist vollständig in einer Geheimschrift geschrieben, die noch nie entziffert worden ist. Sein Verfasser, sein Gegenstand und seine Bedeutung sind ungelöste Geheimnisse. Niemand weiß auch nur, in welcher Sprache der Text verfaßt wäre, sollte man ihn einmal entziffern. Den Leser, der sich um die Entzifferung bemüht, spannen fantastische Bilder nackter Frauen, seltsamer Erfindungen und nicht existenter Pflanzen und Tiere auf die Folter. Farbige Skizzen im anspruchsvollen Stil mittelalterlicher Herbarien zeigen Blüten und Gewürze, die niemals auf der Erde wuchsen, und Sternbilder, die der Himmel nicht kennt. Pläne für außerirdisch seltsame Rohrleitungen zeigen Nymphen in Sitzbadewannen, die durch verzweigte Leitungen im Makkaronistil miteinander verknüpft sind. Das Buch wirkt auf eine unheimliche Weise wie ein vollkommen vernünftiger Text aus einem anderen Universum. Illustrieren die Bilder Gegenstände, die der Text behandelt, oder dienen sie einer unverständlichen Camouflage? Niemand weiß es.

In einem 1666 verfaßten Brief wird behauptet, der deutsche Kaiser Rudolf II habe das Manuskript für 600 Golddukaten gekauft. Vielleicht hatte er es von Dr. John Dee gekauft, einem redegewandten Astrologen und Mathematiker, der sein Glück an einem königlichen Hof nach dem anderen probierte. Rudolf nahm an, das Manuskript stammte von dem englischen Mönch und Philosophen Roger Bacon (ca. 1220 - 1292). Bacon kommt genausogut als Autor in Frage wie jeder andere. Einige Generationen nach seinem Tod war er als "Dr. Mirabilis" zu einer fast schon legendären Gestalt geworden, galt halb als Gelehrter, halb als Magier. Bacon sammelte arkane Literatur. Er hatte von Schießpulver gehört und hat in seinen Schriften angedeutet, dass er um andere Dinge wisse, die er der Öffentlichkeit nicht zugänglich machen wollte. Zur Zeit seines Todes galten seine Werke als so gefährlich, dass sie angeblich an die Wand der Bibliothek von Oxford genagelt Wind und Wetter ausgesetzt wurden. Das Voynich-Manuskript soll sich lange Zeit im Jesuitenkolleg von Mondragone in Frascati befunden haben. 1927 hatte es Wilfried M. Voynich, ein Wissenschaftler und Bibliophile polnischer Abstammung, erstanden. Voynich war der Schwiegersohn des Logikers George Boole und der Ehemann von Ethel Lilian Voynich, die in der Sowjetunion und China zu den bekanntesten englischen Schriftstellern gehört, auch ihr epochemachender Roman The Gadfly ist längst in Vergessenheit geraten ist. Da das Manuskript keinen verständlichen Titel hatte, wurde es unter Voynichs Namen bekannt. Voynich brachte das Manuskript mit nach Amerika, wo es ausführlich erforscht wurde. In den letzten 75 Jahren ist das Voynich-Manuskript immer wieder von Gelehrten wie von eigenwilligen Spinnern interpretiert worden. Das Manuskript befindet sich jetzt in der Beinecke Rate Book and Manuscript Library der Universität Yale.

Die Geheimschrift des Manuskripts ist keine einfache Chiffre. Wäre dem so, wäre es seit langem dechiffriert. Das Manuskript verwendet keine lateinischen oder sonstwie üblichen Buchstaben oder Zeichen. Es handelt sich auch nicht um eine spiegelbildliche Darstellung oder einfach die verzerrte Form bekannter Buchstaben. Der Code besteht aus etwa 21 verschlungenen Symbolen, die vage an einige Schriften des nahen Ostens erinnern. Natürlich entstammen die Zeichen keiner nahöstlichen Schrift. Manche Zeichen treten miteinander verbunden auf. Einige Zeichen erscheinen nur selten, es sei denn, es handele sich um unscharf geschriebene Formen anderer Zeichen.

2. Grundbegriffe

Nachricht nennt man eine Wirkung, unabhängig von der physikalischen Beschaffenheit ihres Trägers.

Beispielsweise zeigt eine persönlich betreffende Nachricht eine Wirkung, gleichgültig, ob die Information von der Zeitung, dem Fernsehen oder mündlich weitergegeben wird. Die Wirkung erfaßt das gesamte System (in diesem Fall den Menschen) und verändert es, ohne tatsächlich physikalischen Einfluß genommen zu haben.

Information ist der Gehalt der Nachricht.

Hier wird im Grunde nur der Begriff "Information" durch den ebenso vielschichtigen, aber geläufigeren Begriff "Gehalt" ersetzt. Ein ganz einfaches Beispiel für eine solche Unklarheit ist die Nachricht:

"Der Hahn bewegt sich nicht."

Hier kann das Tier, ein Wetterhahn oder ein Wasserhahn gemeint sein, je nachdem, welche Assoziation der Empfänger mit dem Wort Hahn verbindet.

Als Signal bezeichnet man den physikalischen Träger einer Nachricht.

Signale können elektrisch (z.B. Fernsehen, Radio oder Funk), mechanisch (z.B. Flaggen), chemisch (z.B. Nervensubstanz, Hormone), akustisch, optisch oder sonst irgendwie sein, trotzdem sind sie imstande, die gleiche Nachricht zu übertragen. Signale, die die gleiche Nachricht übertragen, sind zueinander äquivalent und haben die Nachricht als gemeinsames klassifizierendes Merkmal.

Nachrichtenraum wird die Menge aller möglichen Nachrichten genannt, gebildet aus Elementen eines Alphabets. Fehlt eine Begrenzung der Zeichen je Nachricht, wird der Nachrichtenraum unendlich groß.

Codierung ist die Abbildung von einem Nachrichtenraum in einen anderen.

Alphabet: alle Zeichen eines Zeichensystems (= Zeichensatz)(z.B. alle Buchstaben des dt. Alphabetes)

Zeichen: Elementarmenge einer Nachricht. Zeichen, die aus einem zwischen Sender und Empfänger vereinbarten Alphabet stammen, werden übertragen. Eine Nachricht entspricht demnach einer

Zeichenfolge.

Wort: Eine Folge von Zeichen.

Unter Decodierung versteht man die Rückverwandlung einer verschlüsselten Information in die Originalform.

Redundanz R ist definiert als Differenz zwischen dem maximal möglichen und dem tatsächlichen Informationsgehalt eines Codezeichens innerhalb eines bestimmten Codes.

3. Code fester Länge

Besitzt ein Alphabet eine einheitliche Stellenzahl 'S' (= alle Worte haben die Länge 'S') und eine bestimmte Anzahl von Zuständen 'Z' je Stelle, so hat es einen Alphabetumfang 'Au' mit der Größe Au = Z^S

Beispielsweise erreicht man mit dem Buchstabenalphabet und einer Begrenzung der gebildeten Worte auf Worte zu genau 4 Buchstaben insgesamt einen Alphabetumfang von Au = 26⁴= 456976.

In diesem Alphabetumfang sind dann natürlich auch sprachlich sinnlose Kombinationen wie beispielsweise 'KLMZ' enthalten.

Bei Binärcodes und Worten von fester Stellenlänge existieren je Stelle zwei Zustände, daher ergibt sich der Alphabetumfang mit Au = 2^S

3.1 Decodierung

Rückverwandlung einer verschlüsselten Information in die Originalform

Bei einer Binärcodierung entspricht die Anzahl der Entscheidungen 'ES' direkt der Stellenzahl.

ES = log2(Au) = ld Au = ld Z^S= S.ld Z

ld ... Logarithmus Dualis, Logarithmus zur Basis 2

Z=2 : ES = S.ld 2 = S

Bei einem Alphabetumfang, der keine Potenz von 2 ist, ergibt sich keine ganzzahlige Anzahl der Entscheidungsschritte, hier wird ein neuer Begriff eingeführt:

Informationsgehalt IG = ld Au (bit)

Es ist dies der Informationsgehalt eines Zeichens mit fester Stellenlänge.

3.2 Redundanz

Redundanz ist definiert als Differenz zwischen dem maximal möglichen und dem tatsächlichen Informationsgehalt eines Codezeichens innerhalb eines bestimmten Codes.

Es gibt zwei Maßangaben für die Redundanz:

a) absolut (in bits)

R = IGmax - IG

IGmax ... Informationsgehalt maximal

IG ... Informationsgehalt tatsächlich

relativ (in Prozent)

R = ld AuZ - ld AuQ = ld(AuZ/AuQ)

AuZ ... Alphabetumfang des Zielalphabets

AuQ ... Alphabetumfang des Quellenalphabets

Es gibt auch noch eine anschaulichere Bezeichnung der Begriffe AuZ und AuQ:

AuZ = Anzahl der möglichen Codeworte

AuQ = Anzahl der günstigen Codeworte

3.3 Beispiele

Bei der Codierung der englischen Buchstaben (26) mit fünfstelligen Binärwörtern ergibt sich die Redundanz:

R = 5 - 4.7 = 0.3 bit

IG eines 5-stelligen Binärwortes = ld 32 = 5

IG eines Buchstabens = ld 26 = 4.7

Die Codierung von Ziffern (0...9, 10 Zeichen) mit vierstelligen Binärwörtern ergibt eine Redundanz von:

R = 4 - 3.32 = 0.68 bit

IG einer Ziffer = ld 10 = 3.32

Die Codierung der 95 verwendeten Textzeichen (Ziffern, Buchstaben, Interpunktionen, Sonderzeichen) mit achtstelligen Binärwörtern ergibt eine Redundanz von:

R = 8 - 6.57 = 1.43 bit

4. Codes variabler Länge

Bei diesen Codes geht man von der Annahme aus, dass nicht alle Zeichen gleich häufig auftreten.

Die Formel für den Alphabetumfang eines Wortalphabets bei Verwendung von Zeichen mit unterschiedlicher Auftrittswahrscheinlichskeit lautet:

N!

Au = -----------------------------------------------

(p_a * N)! * (p_b * N)! * ... *(p_z * N)!

p_a, p_b, p_z ... relative Häufigkeit des Auftretens eines bestimmten Zeichens

N ................. durchschnittliche Anzahl der Zeichen eines Wortes

Summe aller p_i (i = a ... z) = 1

Untersucht man den Alphabetumfang, zeigt sich ein Maximum, wenn alle Zeichen mit gleicher Häufigkeit auftreten. Das ist im Zahlensystem, das keine Redundanzen besitzt, auch der Fall.

Schon Samuel Morse berücksichtigte in seinem Morsealphabet diesen Sachverhalt und codierte seine Zeichen mit variabler Länge, d.h. er codierte die am häufigsten auftretenden Buchstaben mit dem kürzesten Codewort.

5. Erhöhung des Übertragungssicherheit

Eine Raumsonde fliegt zu einem fernen Planeten. In ein paar Tagen fliegt sie nahe der Oberfläche des Planeten vorüber, nimmt mehrerer hundert Bilder auf und speichert sie intern. Obwohl sie sich in die Tiefe des Raums jenseits des Planeten entfernt, beginnt sie, ihre Bilder über ungeheure Weiten zu Empfangsstationen auf der Erde zu übertragen.

Jedes Bild wird, ähnlich einem Fernsehbild, in horizontale Abtaststreifen unterteilt, und jede Abtastzeile wird erneut in Pixel zerlegt, die durch von 32 möglichen Grauwerten dargestellt werden. Dabei wird weiß durch 0, schwarz durch 31 und die dazwischenliegend Graustufen durch 1 bis 30 symbolisiert.

Jedes Pixel wird in eine elektronische Nachricht codiert und jagt mit Lichtgeschwindigkeit zur Erde zurück. Selbst bei dieser Geschwindigkeit benötigt das Signal unter Umständen viele Minuten, um zur Erde zu gelangen, und kann während der Reise entstellt werden. Selbst wenn es die Empfangsantenne erreicht, kann das Signal wegen seiner extremen Schwäche mit Hintergrundrauschen verwechselt werden.

Folglich ist es möglich, dass sich ein einzelnes Pixel, codiert in ein elektronisches Muster von Nullen und Einsen, von seiner ursprünglichen Form verändert. D.h. man müsste die Nachricht dann so codieren, dass es beim Empfänger möglich ist, Fehler, die aufgetreten sind, zu entdecken oder auch zu korrigieren.

Bei Datenübertragung von Binärcodes ist es möglich, dass Fehler auftreten wie z.B., dass aus einem 1 eine Null wird oder umgekehrt. Ist nur eine Veränderung in eine Richtung möglich, ist der Fehler einseitig (z.B. nur von 1 auf 0), dann kann man jedem Codewort eine feste Zahl von 0-Bits zuordnen und einfach nach der Übertragung abzählen.

5.1 Hamming-Distanz

STELLENDISTANZ:

Untersucht man zwei beliebige Nutzworte eines Codes auf die Anzahl der Stellen, in denen sie sich voneinander unterscheiden, ergibt sich die 'STELLENDISTANZ' SD, die von Kombination zu Kombination variiert.

HAMMINGDISTANZ:

Untersucht man alle vorhandenen Nutzwortkombinationen auf die minimale paarweise Stellendistanz, erhält man die HAMMINGDISTANZ h. Die Hammingdistanz ist die wesentliche Größe, von welcher die Eigenschaften eines Codes abgeleitet werden können.

Es gilt immer:

h <= SD Hammingsdistanz ist immer gleich oder kleiner der Stellendistanz eines Codes

h = min (d [i,j]) Hammingsdistanz ist der minimale Abstand zweier Worte eines Codes

5.2 Fehlererkennende Codes

Die Fehlerwahrscheinlichkeit ist meistens symmetrisch.

Das Vorgehen dabei ist folgendes:

Der Code wird in seiner Stellenanzahl verlängert und eine Reihe von eigentlich überflüssigen Codebits und Codewörtern wird eingeführt. Diese zusätzlichen Codeworte haben die Bezeichnung FEHLERWORTE, die eigentlichen Codeworte heißen NUTZWORTE. Doch diese fehlererkennenden Codes beginnen zu versagen, wenn die Zahl der Fehler pro Codewort steigt.

Für die Anzahl der erkennbaren Fehler e innerhalb einer Codierung gilt die Formel:

h = e + 1

bzw.

e = h - 1

Beweis:

Mindestens ein Bit Unterschied muss bei zwei Codeworten da sein, da sich sonst die Codeworte überhaupt nicht unterscheiden. Sind zwischen allen Codeworten zwei Bits unterschiedlich und ändert sich ein einzelnes Bit durch einen Übertragungsfehler, entsteht ein nicht in der Codeliste vorkommendes Wort, wodurch der Fehler erkannt werden kann. Bei drei Bit Unterschied dürfen zwei Bits falsch sein und der Fehler kann noch immer erkannt werden.

Codeworte:

10

01

Die Hammingsdistanz beträgt bei diesen Code 2. Würde bei einem der 2 Codeworte ein bit fallen, so könnte man dieses falsche Codewort erkennen, weil e = 2- 1 =>1. Würden aber beide bits fallen, so könnte man diese Störung nicht erkennen.

Beträgt die Hammingsdistanz nur 1, dann könnte man keinen Fehler erkennen.

5.3 Fehlerkorrigierende Codes

Fehlerkorrigierende Codes erkennen nicht nur Fehler, sondern können sie auch je nach Hammingdistanz korrigieren. Es gilt die Formel für die Anzahl der korrigierbaren Fehler:

k = (h-1) / 2

oder

h = k + e / 2 + 1

k ... korrigierbare Fehler

Treten also bei der Übertragung eines Codes Fehler auf, so dürfen maximal k Fehler auftreten, die dann auch korrigiert werden können. Übersteigt die Zahl der fehlerhaften Bits innerhalb eines Codewortes die Zahl k, kann nicht mehr korrigiert werden.

Beweis:

Erhält man ein fehlerhaftes Codewort, kann man annehmen, dass es dem nächstliegenden Nutzwort mit minimalem Abstand entspricht (minimaler Abstand bedeutet den geringsten Unterschied an Bits, bezogen auf alle Codewortstellen). Eine Korrektur kann daher durch Zuordnung zu diesem Nutzwort erfolgen. Es wird daher die Hälfte der auf einer Hammingdistanz liegenden Fehlerworte dem nächstliegenden Nutzwort zugeschlagen. Ist deren Anzahl jedoch ungerade, kann bei dem mittleren Fehlerwort keine Entscheidung getroffen werden, da es zu beiden Nutzworten paßt.

Code:

1: 00100

2: 01111

3: 10011

Stellendistanz 1-2: 3

Stellendistanz 1-3: 3

Stellendistanz 2-3: 4

Minimale Stellendistanz ist 3, daher beträgt die Hammingsdistanz auch 3.

KF = INT((3-1)/2) = 1. D.h. wenn ein bit fällt, kann man diesen Fehler erkennen und korrigieren.

Fallen aber zwei bits, so kann man noch erkennen, dass ein Fehler aufgetreten ist (e = 3 - 1 = 2), aber man kann diesen Fehler nicht korrigieren.

5.4 Entwurf fehlerkorrigierender Codes

Der zu übertragende Code bestehe aus binär codierten Dezimalziffern, denen Korrekturbits zur Erkennung und Korrektur einzelner Fehler zugeordnet werden sollen. Zur Abschätzung der Anzahl der Korrekturbits hilft folgende Überlegung:

Fügt man zu einem k-Bit-Code n redundante Bits hinzu, kann man 2ⁿFehlermöglichkeiten erkennen (einfache Fehler, bei denen im gesamten Codewort nur ein Bit verfälscht wird).

Die vollständige Zahl von Varianten bei einfachen Fehlern ergibt sich aus der folgenden Aufstellung:

- kein Fehler

- k einzelne Fehler (je Codebit c)

- n einzelne Fehler (je Korrekturbit n)

Es sind dies k+n+1 Fehlermöglichkeiten, daher muss gelten:

2ⁿ>= k+n+1

5.5 Paritätskontrolle

In vielen Fällen wird die Paritätskontrolle anderen Fehlererkennungen vorgezogen, da die Annahme des Auftretens ausschließlich einfacher Fehler bei langsamer Übertragung und auch bei magnetischer Aufzeichnung geringer Dichte durchaus zulässig ist, und eine Korrektur durch Doppelübertragung fehlerhafter Codeworte oft einfacher ist, als mit einem Algorithmus die Datensicherheit zu gewährleisten.

Bei der Paritätskontrolle wird im einfachsten Fall dem Codewort ein Prüfbit zugeordnet, das die Anzahl der '1'-Bits auf eine gerade oder ungerade Zahl ergänzt (je nach Vereinbarung). Ergänzt man auf gerade Zahl, nennt man die Kontrolle 'even parity check', im anderen Fall 'odd parity check'.

ASCII-Codezeichen mit gerader Parität:

Zeichen	ASCII-Code	Parität
A	1000001(65)	0
B	1000010(66)	0
C	1000011(67)	1

Dieses Verfahren ist nur begrenzt und nur bei seltenem Auftreten von Fehlern wirksam, da es nur einfache Fehler erkennt oder eine ungerade Anzahl anzeigt. Ändern sich zwei oder mehrere sonstige gerade Zahl von bits fehlerhaft, stimmt die Quersumme trotzdem und der Fehler wird nicht erkannt.

5.5.1 Längsparitätskontrolle

Durch Hinzufügen weiterer redundanter Bits kann die Fehlerkontrolle verbessert werden, dieses Verfahren ist vor allem dann interessant, wenn mit einer Zerstörung mehrerer Bits zu rechnen ist (Fehlerblöcke auf magnetischen Datenträgern sind meistens größer als ein einziges Bit). Dieses Verfahren lohnt sich allerdings wieder nur dann, wenn mit dem Auftreten größerer Fehlermengen in kleinen Datenblöcken gerechnet werden muss.

5.5.2 Querpartätskontrolle

Ein gebräuchliches Verfahren fügt zu einem übertragenen Datenblock eine weitere Paritätskontrolle (Querparität) hinzu, wobei nicht nur das einzelne Wort, sondern auch die übereinstimmenden Stellen ein gemeinsames Paritätsbit erhalten.

Wortstelle	Längs-
1 2 3 4 5 6 7	parität
1	1	0	0	0	1	0	1
0	0	1	1	1	0	1	0
0	0	1	1	1	1	0	0
1	1	1	1	0	0	1	1
0	0	0	0	1	0	1	0
0	1	0	0	1	1	1	0
1	1	0	1	0	1	0	0
1	0	1	0	0	0	0	0

Hier wird nach der Ausgabe der sieben Codeworte (mit Paritätsbit) ein Code mit der Querparität nachgesandt. Die Empfangsstelle prüft nach dem Empfang jedes einzelne Wort auf seine Längsparität und bildet außerdem die Querparität. Beim Empfang wird der Code der Querparität mit dem selbst errechneten verglichen und ein gültiger Empfang quittiert. Waren die Paritäten nicht gleich, verlangt der Empfänger noch einemmal den gleichen Datenblock. Sollte auch nach mehrmaliger Übertragung kein fehlerloser Empfang möglich sein, wird im allgemeinen die Übertragung abgebrochen und beim Sender die entsprechende Fehlermeldung durchgeführt.

Ein einzelner Fehler kann bei diesem Verfahren sicher korrigiert werden, da die fehlerhaften Paritätsbits in der Quer- und Längsparität eindeutig auf das falsche bit zeigen, das zur Korrektur nur mehr umgekehrt werden muss.

5.6 CRC-Codes

CRC, die Abkürzung für CYCLIC REDUNDANCY CHECK bedeutet ein Prüfverfahren für datenübertragende Systeme. Die CRC-Kontrolle beruht auf einem Divisionsverfahren mit rückgekoppelten Schieberegistern.

Auf der Empfangsseite durchläuft der Datenstrom inklusive des CRC-Wortes eine äquivalente Schaltung, der entstehende Rest muss 0 sein. Entsteht dieses Ergebnis, kann mit sehr hoher Wahrscheinlichkeit angenommen werden, dass kein Übertragungsfehler auftrat. Die einzige Fehlerwahrscheinlichkeit entsteht durch die Möglichkeit, dass sowohl im Datenstrom als auch im CRC-Wort ein Bit derart verändert wurde, dass wieder beide zusammenpassen, eine äußerst geringe Wahrscheinlichkeit.

Es gibt genormte Rückführungspolynome, die in der folgenden Liste aufgeführt sind:

Polynom Anmerkung

x¹⁶+x¹⁵+x²+1 CRC-16

x¹⁶+x¹⁴+x+1 CRC-16 invers

x¹²+x¹¹+x³+x²+x+1 CRC-12

x⁸+1 LRC

x¹⁶+x¹²+x⁵+1 CRC-CCITT

x¹⁶+x¹¹+x⁴+1 CRC-CCITT invers

Die Hauptanwendung dieses Verfahrens liegt in der Kontrolle des Datentransfers über DÜ-Leitungen, bei magnetischen Medien, bei Band-, Platten- oder Floppydiskstationen, bei denen immer mit einem Datenausfall gerechnet werden muss. Beispielsweise liegen die Angaben der Hersteller bei Floppystationen bei

- behebbarer Fehler 1 Bit/je 10⁹Bit

- nicht behebbarer Fehler 1 Bit/je 10¹²Bit

wobei ein behebbarer Fehler in der Leseeinrichtung erscheint und durch nochmaliges Lesen behoben werden kann. Nicht behebbare Fehler entstehen beim Schreiben und sind dann bereits fest auf dem Datenträger gespeichert.

CRC-Sicherung mit Polynomcode

Polynom(G(x)): x³+ x²+ 1 = 1 1 0 1 Generatorpolynom

Nachricht(N(x)): 1 1 1 0 1 1

Der Sender fügt an den zu übertragnenden Nachricht N(x) zusätzlich 0-bits an, und zwar um eines weniger als die Länge des Polynoms. D.h. dass wir 3 0-bits anhängen müssen.

1 1 1 0 1 1 0 0 0

Der Sender dividiert Modula 2 die verlängerte Nachricht durch das Polynom.

1 1 1 0 1 1 0 0 0 % 1 1 0 1 = 1 0 0

Von der verlängerten Nachricht wird der Rest abgezogen, d.h. aber nichts anders als, dass die zugefügten Nullen durch den Rest ersetzt werden. Die sich ergebende Zahl ist nun ohne Rest teilbar.

1 1 1 0 1 1 0 0 0

- 1 0 0
1 1 1 0 1 0 1 0 0 übertragende Zahl

Diese Zahl wird an den Empfänger übertragen.

Der Empfänger führt die Division mit dem Polynom durch und prüft auf Rest Null. Falls die Division nicht Null Rest ergibt, so ist ein Fehler aufgetreten.

Entwurf:

6 Binärcodes

6.1 Allgemeines

Binärcodes lassen sich in Zahlen-, Ziffern- und Zeichencodes einteilen. Zahlencodes codieren beliebige Zahlen in Binärdarstellung, Zifferncodes die 10 Dezimalziffern von 0 bis 9, während Zeichencodes beispielsweise auch Buchstaben und Sonderzeichen enthalten.

Die meisten Zifferncodes stammen aus der Zeit der ersten Rechenmaschinen und spiegeln häufig die schaltungstechnischen Gegebenheiten wieder, da durch geeignete Wahl des Codes einfachere Rechenschaltungen möglich waren.

Seit dem Eindringen der Mikrocomputer in die Schaltungen der Digitaltechnik ersetzt man Verdrahtung und Schaltung in vielen Fällen durch Programme. Für eine Programmentwicklung ist ein konsequent beibehaltener Code wesentlich einfacher und daher günstiger als besondere Eleganz des Codes und Anpassung an eine bestimmte Aufgabenstellung.

Zur mathematischen Manipulation werden von den Zifferncodes daher praktisch nur mehr der DUAL- und der BCD-Code (siehe Seite ..) verwendet, die anderen Codes haben eher historische oder didaktische Bedeutung. Bei den Zeichencodes hat sich der ASCII-Code so eindeutig durchgesetzt, dass kaum ein anderer Code bei Neuentwicklungen verwendet wird.

6.1.1 Binäre Codes

Alle Codes, die nur mit zwei Zeichen auskommen, nennt man Binärcodes. Da auch Digitalschaltungen nur zwei Zustände kennen, werden zur digitalen Verarbeitung von Informationen ausschließlich Binärcodes verwendet, von denen es theoretisch unendlich viele gibt. Vor allem historisch bedingt sind die ältesten in der Digitaltechnik verwendeten Codes reine Zifferncodes, bei welchen die 10 Dezimalziffern in irgendeiner Form verschlüsselt erscheinen.

Aus praktischen Gründen sind nahezu alle Zahlencodes der Digitaltechnik Codes fester Länge, ebenso Zeichencodes. Codes variabler Länge, ähnlich dem Morsecode, wurden erst beim Einsatz von Computern realisierbar, da sie sehr anpassungsfähige Schaltungen benötigen.

6.1.2 Mögliche Eigenschaften von Codes

Codes unterscheiden sich voneinander durch bestimmte mögliche Eigenschaften. Jede dieser Eigenschaften bringt bestimmte Vorteile, sie können aber nie alle gleichzeitig in einem einzigen Code untergebracht werden. Es ist daher eine Abschätzung der wichtigsten gewünschten Eigenschaften des bei einer bestimmten Anwendung eingesetzten Codes erforderlich.

Symmetrie:

Die Umwandlung von symmetrisch zur Mitte liegender Codeworte ineinander entsteht durch Vertauschen von 0 und 1. Diese Eigenschaft war vor allem für Rechenschaltungen wichtig.

Beispiel: 00

01 wenn alle 0 in 1 und alle 1 in 0 wechselt, kommt man zur

10 anderen Zahl

11

Gewichtung:

Jeder Binärstelle eines gewichteten Codes ist ein Wert zugeordnet. Addition der Gewichtungen entsprechend auf 1 stehender Bits ergibt die Nummer des Codewortes bzw. die codierte Zahl. Solche Codes kann man leicht wieder in das entsprechende Quellzeichen oder Ziffernzeichen rückwandeln.

Beispiel: 0101 = 0*2^{3 +} 1^*2^{2 +} 0^*2^{1 +} 1^*2^{0 =} 5

Einschrittigkeit:

Von einem Codewort zum Folgecodewort ändert sich jeweils nur ein einziges Bit. Zähler mit diesem Code erzeugen keine Spikes, hervorgerufen durch unterschiedliche Schaltzeiten der Gatter oder FlipFlops des Decodernetzwerks und Zählers.

Beispiel: 0000

0001

0011

0111

0101 usw.

Redundanz:

Redundanz kann nur dann entstehen, wenn mehr Codeworte aus den möglichen Bitkombinationen zur Verfügung stehen, als tatsächlich verwendet werden. Redundanz ist für Fehlererkennung und Fehlerkorrektur unbedingt erforderlich.

Fehlererkennbarkeit:

Erkennung von ein- und/oder mehrfachen Fehlern

Fehlerkorrigierbarkeit:

Korrigierbarkeit von ein- und/oder mehrfachen Fehlern.

Tetraden:

Zur Codierung von Dezimalziffern sind mindestens 4 bit notwendig. Falls ein Zifferncode tatsächlich nur aus diesen 4 bit besteht, nennt man ihn tetradisch, er ist ein Minimalcode.

6.1.3 Decoder

Decoder sind Logikschaltungen, mit deren Hilfe man aus dem Codewort wieder das Quellwort erhält. Die Komplexität des Decoders ist direkt abhängig von der Redundanz des Codes, im Prinzip besteht er aber nur aus einem Gatternetzwerk.

Ein Decoder besitzt so viele Eingänge, wie das Codewort Bits enthält, und so viele Ausgänge, als Quellworte vorhanden sind. Jeder Decoderausgang steht daher stellvertretend für ein mögliches Quellwort, das aus den gelieferten Mustern herausdecodiert wird.

Falls redundante Codeworte vorhanden sind, lässt sich der Decoder vereinfachen.

6.1.4 Encoder

Encoder sind Logikschaltungen, die aus den Quellworten verschlüsselte Binärworte erzeugen. Ein Encoder besitzt immer so viele Eingänge, als Quellworte zur Verfügung stehen, und so viele Ausgänge, als das Codewort Bits enthält.

6.2 Dual-Code

Der Dual-Code ist der klassische Binärcode, der zur Codierung von beliebig großen ganzen Zahlen verwendet wird. Er entspricht einer Umsetzung des dezimalen Zahlensystems in das binäre Zahlensystem der Dual-Zahlen. Von besonderer Bedeutung sind die Dual-Codes fester Stellenlänge mit 4, 16 oder 32 bit Wortlänge.

Die Ziffern des Hexadezimalsystems (kurz: Hexziffern) sind nicht anderes als eine Kurzdarstellung für jeweils eine 4-bit-Gruppe. Diese Darstellung ist vorallem bei Mikrocomputern weit verbreitet und erlaubt eine Kurzform für lange Bitmuster, die weitaus leichter zu lesen ist als eine Kette von "0" und "1".

6.2.1 Tabelle

6.2.2 Beispiel für eine Binär-Hex-Umrechnung

1011 0110 0010 1101 Þ B62D

6.2.3 Karnaugh-Diagramm:

Für größere Zahlen lässt sich der Dual-Code in seiner Stellenzahl beliebig erweitern. Häufig verwendet man den 16-bit-Code. Die Besonderheit der Karnaugh-Tafel ist die Einschrittigkeit.

1-schrittig

1-schrittig

Abb. Dual-Code, in eine Karnaugh-Tafel eingetragen

6.3 BCD-Code

Er ist mit dem binären Zahlensystem verwandt und er ist ein tetradischer Code. D.h. 4 - bits werden zur Darstellung verwendet, die Codeworte sind die ersten 10 Codes des Dualcodes.

Bei gewichteten Codes lässt sich die damit codierte Zahl wieder einfach rekonstruieren, wenn man jeweils die mit "1" belegten Bits mit ihrer Gewichtung multipliziert und dann summiert.

Beispiel: 0111 ® 0*8 + 1*4 + 1*2 + 1*1 = 7 ... Codeziffer

6.4 Gray-Code

Der Gray-Code ist ein Beispiel für einen einschrittigen Code, bei dem sich ein Wort vom folgenden durch nur ein Bit unterscheidet. Bei einschrittigen Codes treten bei der Decodierung eines entsprechenden Asynchron-Zählers keine Laufzeitprobleme und damit Spikes beim Decoder auf, wie sie bei mehrschrittigen Codes sehr wohl möglich sind.

Da sich bei einem einschrittigen Code beim Übergang auf das Folgewort nur ein einziges Bit ändert, kann selbst bei unterschiedlichen Gatterzahlen im Decoder kein unerwünschter Zwischenzustand entstehen.

Störend ist beim unvollständigen Gray-Code der Übergang von Zustand 9 zu Zustand 0, da sich hier drei Bits gleichzeitig ändern und daher der Code eigentlich nicht einschrittig ist. Dieser Bruch kommt aus der Entwicklungsgeschichte dieses Codes, der eigentlich ein Binär- und kein Dezimalcode ist. Verlängert man den Code auf 16 Codeworte, bleibt die Einschrittigkeit erhalten.

Jetzt ist der Ãœbergang vom letzten auf das erste Codewort ebenfalls einschrittig.

6.5 Hamming-Code

Der Hamming-Code ist der am häufigsten verwendete fehlerkorrigierende Code. Er besteht aus einem normalen BCD-Code, der mit drei Kontrollbits und einem Kontrolllbit, das die Kontrollgruppe auf gerade Parität ergänzt. Geprüft wird durch Quersummenbildung im an-kommenden Codewort.

6.5.1 Kontrollgruppen:

Zur Prüfung wird die Modulo-2-Summe aus folgenden Bits gebildet.

Z1= K0+D+B+A

Z2= K1+D+C+A

Z3= K2+D+C+B

Die entstehende Binärzahl Z3Z2Z1 gibt in Form einer Dualzahl die falsche Stelle des Codes an; ist sie 0, stimmt das übertragene Wort. Wie sich zeigt, stellen die Kontrollbits nichts anderes als die Ergänzung der angegebenen Bit auf gerade Parität dar.

Beispiel:

Statt 1001100 wurde 1101100 übertragen.

Z1: 0+1+0+1=0

Z2: 0+1+1+1=1

Z3: 1+1+1+0=1 Bit Nr. 110 ® das Bit Nr. 6 ist fehlerhaft!!

6.6 ASCII-Code

Der ASCII-Code (American Standard Code of Information Interchange) ist der in der Computertechnik am weitesten verbreitete Zeichencode, der alle lesbaren Zeichen des Fernschreibecodes sowie zusätzliche Steuer- und Kontrollzeichen enthält.

Ausschnitt einer ASCII-Tabelle:

Beispiel: "K" hat den ASCII-Code 4B (in Hex)

In der Digitaltechnik findet man den ASCII-Code nicht sehr häufig, er ist eher der Hauptcode der datenübertragenden und datenverarbeitenden Maschinen. Ursache ist der Anwendungsbereich digitaler Geräte, da bei Steuerungen die einzelnen Bits der verarbeiteten Bitmuster oft individuelle Bedeutung besitzen, während bei rechnerischen Aufgaben BCD- und DUAL-Code dominieren.

Der ASCII-Code ist aber nur für Englisch, und nicht für andere Länder, anwendbar.

6.7 HUFFMAN-CODE

Dieser Code ist ein ausgezeichnetes Beispiel für einen Code variabler Länge wobei hier nicht weiter auf die dahinterstehende Theorie eingegangen, sondern nur das Verfahren gezeigt werden soll.

Wie für einen Code variabler Länge Voraussetzung für eine sinnvolle Anwendung, beruht er auf einem Quellalphabet mit Zeichen, deren Auftretenswahrscheinlichkeit unterschiedlich ist. Bevor man daher mit der Codierung beginnt, muss man zuerst die Auftretewahrscheinlichkeit jedes einzelnen Zeichens feststellen und in einer Liste festhalten.

Das Quellalphabet der Tabelle stammt aus einer zufälligen Liste von Zahlen mit insgesamt 400 Ziffern und zeigt die darin festgestellte Auftretewahrscheinlichkeit der 10 Ziffernzeichen.

Beim Huffman-Code verteilt man die kürzeren Codeworte an Zeichen mit höherer Häufigkeit, die längeren an Zeichen mit seltenerem Auftreten. Für einen Huffman-Code gelten dann eine Reihe von Randbedingungen, die diesen Code kennzeichnen:

a) die beiden Codeworte der zwei seltensten Zeichen sind von gleicher Länge und unterscheiden sich nur durch das letzte Bit.

b) Kein kürzerer Code darf gleichzeitig auch der Beginn eines längeren Codes sein.

c) Existieren zwei Codeworte gleicher Länge L, müssen entweder alle zulässigen Codes mit L-1 Bits oder eine der möglichen Anfangsteilsequenzen als Code verwendet

werden.

Man kann aus diesen Bedingungen (ohne Beweis) eine Tafel entwickeln, aus der sich der Code ableiten lässt. Die Tafel wird folgendermaßen aufgebaut:

1. Man faßt die beiden untersten Zeichen zu einem Hilfszeichen zusammen.

2. Dieses Hilfszeichen wird als neuer Zeichen in eine neue Spalte eingetragen, in der alle anderen noch nicht reduzierten Codes eingetragen sind.

3. Dieser Vorgang wird so lange wiederholt, bis nur mehr ein letztes Hilfszeichen übrig ist.

Daraus ergibt sich folgende Tabelle:

4 10

0 000

9 010

1 011

3 110

7 0011

6 1110

2 1111

5 00100

8 00101

Der Vorteil des Huffman-Codes zeigt sich, wenn man jetzt den Codierungsaufwand der gleichen Zahlenfolge mit ASCII-, BCD- und Huffman-Code vergleicht:

Aufwand in Bits:

ASCII 2800

BCD 1600

HUFFMAN 1250

Es zeigt sich, dass der Huffman-Code bei dieser Ziffernverteilung im Vergleich zu BCD um fast 25 % weniger Codieraufwand benötigt. Wären die Ziffern gleich verteilt, brächte der Huffman-Code keine Vorteile.

Anwendung dieses und ähnlicher Codes ist die Reduktion des Aufwands bei Datenübertragung und des Speicherbedarfs von Textverarbeitungssystemen, digitaler Fernsehbildverarbeitung und Bildübertragungen im Allgemeinen.

4738 Worte in "deutsch"  als "hilfreich"  bewertet