Wie überträgt man Information?

Scutus

Stammuser
Hallo HaBo!

Dieser Artikel beschäftigt sich mit Quell- und Kanalkodierung und noch ein bisschen mit dem Übertragungskanal. Diese drei "Sachen" kann man wie folgt betrachten:

Quelle -> Quellkodierung -> Kanalkodierung -> Übertragung -> Kanaldekodierung -> Quelldekodierung -> Senke

Man sieht zunächst, dass man 2mal kodiert, bzw. wieder dekodieren muss. Die Erklärung ist recht simpel: Man hat eine Quelle mit einem Alphabet (ein Satz von Zeichen). Zunächst will man dieses Alphabet möglichst redundanzarm (sprich ohne unnütze Zeichen) auf ein {0,1}-Alphabet abbilden. Warum man nun den binären Weg einem anderen vorzieht wird später erläutert, man könnte auch durchaus auf ein {0,1,2}-Alphabet kodieren. Diese redundanzarme Abbildung ist die Quellkodierung. Bei der Kanalkodierung versucht man Redundanz zu schaffen, also weitere 1en und 0en an das Wort (bestehend aus 1en und 0en) dranzusetzen. Dadurch erreicht man, dass bei einer Störung im Übertragungskanal über die nützliche Redundanz das gesendete Codewort wieder erhält. Zusammengefasst: Quellkodierung versucht Redundanz zu vermeiden, Kanalkodierung erzeugt sie um Fehler zu erkennen.

Quellcodierung

Das Ziel der Quellcodierung ist klar vorgegeben, nun stelle ich ein paar Beispiele vor, mit denen man genau das erreichen kann. Im weiteren betrachte ich diskrete Quellen. Eine diskrete Quelle besteht, wie schon oben beschrieben, aus einem Alphabet X = {x1, x2, x3,...,xn}. Dabei sind die Zeichen aus X als Ereignisse zu sehen, so kann man einem Ereignis aus X auch eine Wahrscheinlichkeit zuweisen.
Nun kann man ein Maß für die Unbestimmtheit einführen. Unbestimmtheit bedeutet, umso wahrscheinlicher ein Zeichen ist, umso weniger Information gewinne ich daraus, "da es ja keine große Überraschung ist". Somit gewinnt man aus einer Quelle, die nur ein Zeichen sendet keine Information. Das Maß der Unbestimmtheit eines (!) Zeichens ist: -log(p(x)). Wobei p(x) die Wahrscheinlichkeit des Zeichens ist.
Dadurch ist uns auch ein Maß für den Informationsgehalt einer Quelle gegeben: Es werden alle Unbestimmtheiten der Zeichen, gewichtet mit dessen Wahrscheinlichkeit aufaddiert. Also die Summe über alle Zeichen von p(x)*(-log(p(x))). Die Basis des Logarithmus ist 2. Diesen Mittelwert der Unbestimmtheit bezeichnen wir im weiteren als Entropie, bzw. Quellenentropie.

Wie man eventuell schon gelesen hat, bezieht sich die Wahrscheinlichkeit eines Zeichens nur auf sich selbst - es besteht also keine Verbindung zu den vorherigen Zeichen. Dass das aber nicht ganz stimmt, sollte klar sein: Bei uns im deutschen Sprachraum ist die Wahrscheinlichkeit für ein Zeichen nach einem "v", höher bei Vokalen als bei Konsonanten -> sie bedingen sich. Man bezeichnet eine diskrete Quelle mit bedingten Ereignissen auch Markow-Quelle. Dazu gibt es dann auch Rechenmodelle, jedoch ähneln sie sich der, der unabhängigen Quellen (man muss hier mit bedingten Wahrscheinlichkeiten rechnen), weshalb ich nicht weiter darauf eingehen werde.

Nachdem wir eine Quelle nun genauer betrachtet haben, geht es nun an die Kodierung. Wie schon oben aufgeführt, versuchen wir ein beliebiges Alphabet auf 1en und 0en abzubilden. Dabei bezeichnen wir ein Wort mit einer gewissen Länge (Anzahl Nullen + Anzahl Einsen) als Kodewort, die Menge aller Kodewörter einer Länge als Kode. Die Koderedundanz beziehen wir aus der Differenz der Kodewortlänge und dem mittleren Informationsgehalt der Quelle. Natürlich muss die Zuordnung zwischen Quellzeichen und Kodewort eindeutig sein. Jedoch muss man auf das Präfix-Verhalten aufpassen. So kann man, wenn man x1 mit 0, x2 mit 110 und x3 mit 1100 kodiert, die Folge 1100 nicht eindeutig zurückführen, da es entweder x1 + x2 sein kann, oder auch nur x3. Deshalb muss der Kode präfixfrei sein. Trivialerweise gilt das auch bei Kode, bei denen die Kodewörter die gleiche Länge haben.

Konstruktion eines Kodes durch Shannon-Fano-Verfahren

Hier muss man folgende Schritte befolgen:

Ordnen der Wahrscheinlichkeit der zu kodierenden Quellzeichen nach fallenden Werte -> Teilen der "Tabelle", so dass die Gesamtwahrscheinlichkeit der beiden Gruppen möglichst gleich sind (und somit die größte Entropie) -> Der ersten Gruppe wird nun eine 1 (bzw. 0) und der zweiten Gruppe eine 0 (bzw. 1) zugewiesen. Jedes Kodewort aus der ersten Gruppe beginnt also mit einer 1 (bzw. 0), jedes aus der zweiten Gruppe mit einer 0 (bzw. 1). -> Solange Teilen und den Gruppen 1en und 0en zuweisen, bis jede Teilgruppe nur noch ein Element enthält.

img3.gif


Konstruktion eines Kodes durch Huffman-Verfahren

Zuerst werden die Zeichen nach der Wahrscheinlichkeit fallend geordnet -> Zusammenfassung der letzten beiden Wahrscheinlichkeiten (Addition) zu einer Neuen -> Tabelle neu ordnen -> Solange Zusammenfassen und neu Ordnen, bis die letzten beiden Wahrscheinlichkeiten 1 ergeben -> Aufstellen eines Kodebaums

abra_05.gif


Nun haben wir zwei Verfahren, wodurch wir eine Quelle möglichst redundanzarm darstellen können.

Kanalkodierung

Wie schon weiter oben gesagt, versuchen wir nun ein Kodewort so zu kodieren, dass bei einer möglichen Störung der Fehler behoben, bzw. erkannt werden kann. Einen behebaren Fehler kann man durch Rekonstruktion entfernen, falls ein Fehler nur erkannt wird, kann man ihn durch Wiederholung beheben.

Eine wichtige Komponente der Kanalkodierung ist der Hamming-Abstand. Man hat zwei Kodewörter der selben Länge. Nun vergleicht man die beiden an jeweils der selben Stelle, falls sie sich in einer Stelle unterscheiden, erhört sich der Hamming-Abstand um 1. So ist die Distanz zwischen 10110 und 10010 gleich 1, bei 10110 und 10000 ist sie 2.

Nun werden aus einer Wortmenge nicht alle Wörter als Kodewörter genommen, sondern es existieren auch Wörter, auf denen kein Quellwort abgebildet wurde. Jetzt versucht man diese Kodewörter so zu wählen, dass sie jeweils einen möglichst großen Abstand zu Nächstgelegenden haben.

image3.png


Hier wäre u und v Kodewörter. Auf deren Verbindungslinie liegen weitere Wörter, die aber keine Abbildung sind. Innerhalb der Kugeln um u und v sind die Wörter jeweils einem Kodewort direkt zuzuordnen. Somit kann man, falls eine Stelle verfälscht wurde, schnell auf das eigentliche Kodewort zurückschließen.

Man kann schon erkennen, dass Blockkodes eine große Bedeutung in der Kanalkodierung haben. Jedoch gibt es auch blockfreie Kodes, diese werden auch als Faltungskodes bezeichnet. Hier wird die Redundanz kontinuierlich durch Faltung der Information hinzugefügt. Im Weiteren werde ich jedoch Blockkodes besprechen.

Innerhalb der Blockkodes existieren spezifischere Kodes, für die man weitere Aussagen treffen kann. So gilt: Blockkodes <- Gruppen-Kodes <- Linear systematische Kodes <- zyklische Kodes. Natürlich zählt auch Hamming-Kode (siehe Hamming-Distanz) (darauf aufbauend Reed-Muller-Kodes) und iterierte Kodes Teilgruppen des Blockkodes. Weiter sind BCH-Kodes und RS-Kodes Teilgruppen von zyklischen Kodes.

Für die Beschreibung dieser Kodes ist ein gewisses mathematisches Wissen im Bereich linearer Algebra und algebraischen Strukturen nötig.

Da die Kodewörter aus den Zeichen {0,1} bestehen, wird für weitere Rechnungen ein Modulo 2 immer gelten. So ist 1+1=0, bzw. u^4 + u^4 = 0. Bei Linearkodes müssen die Axiome einer abelschen Gruppe erfüllen. Dabei werden die Kanalwörter (auf dem das Quellwort abgebildet werden soll) durch algebraische Vorschriften abgebildet. So muss das Alphabet der Kanalwörter abgeschlossen, assoziativ, kommutativ sein und jeweils ein neutrales und inverses Element enthalten.
Nun wird ein Kanalwort als Vektor gesehen. Diese geben einen Vektorraum über dem Körper K. Da der Vektor binär ist, sind die weiteren Axiome für einen Körper erfüllt. Um nun einen n-Dimensionalen Vektorraum zu erhalten genügen n Basisvektoren. Mit diesen Basisvektoren kann man eine Generatormatrix erstellen (n "hoch" und N "breit, wobei N Anzahl der Stellen des Basisvektors ist).
Mit dieser Generatormatrix kann man das Quellenkodewort kodieren, indem man es mit der Matrix multipliziert. Um die Wörter wieder dekodieren zu können, benötigt man eine Kontrollmatrix, für die gilt:

Generatormatrix * transponierte Kontrollmatrix = 0

Wenn man nun das erhaltene Kodewort transponiert und mit der Kontrollmatrix multipliziert erhält man den sogenannten Fehlerverktor, bzw. das Fehlersyndrom. Mit diesem kann man einen Fehler erkennen, bzw. beheben.

Bei Zyklischen Kodes ist zudem ein Verständnis der Restklassen-Algebra nötig. Weiter kann man eine Folge von 1en und 0en auch als Polynom sehen. So steht 1011 für u^3 + u^1 + u^0, wobei u^2 ausgelassen wird, da an dieser Stelle eine 0 steht. Ferner erfüllt der zyklische Kode auch die Körperaxiome und dadurch insbesondere Gruppen- und Ringaxiome und ist somit ein spezieller Linearkode. Ein Kode heißt zyklisch, wenn für jedes Kanalwort durch zyklische Verschiebung wieder ein Kanalwort entsteht.
Das Generatorpolynom ist ein Produkt irreduzibler Minimalpolynome, das den zyklischen Kode vollständig beschreibt.
So entsteht die Generatormatrix aus dem Verschieben eines Kanalwortes. Ein Kanalkodewort zu erzeugen, verwenden wir die Quellkodewörter. Nun multiplizieren wir das Quellpolynom mit x hoch dem Grad vom Generatorpolynom (= a). a teilen wir nun durch das Generatorpolynom, wodurch wahrscheinlich ein polynomieller Rest entsteht. Diesen Rest addieren wir zu a hinzu und erhalten unser Kanalkodewort. Um eine Fehlerkennung zu gewährleisten, muss das übertragen Kodewort durch das Generatorpolynom teilbar sein.

Falls noch weitere Fragen oder Anregungen sind, stehe ich gerne zur Verfügung. Ich hoffe, dass ich das Themengebiet etwas näher bringen konnte. Als Ausblick kann man noch den Kanal genauer beschreiben, bzw. weitere Kodes genauer definieren.

Grüße,

Scutus
 
Zuletzt bearbeitet:

Chromatin

Moderator
Mitarbeiter
Feiner Artikel. Wäre noch geiler wenn es so eine Art Einleitung "Plot" geben würde, nach dem Vorbild der RFCs vielleicht.

Darüber hinaus könnte der Artikel etwas mehr in Richtung nicht-Mathematiker gestaltet sein, so dass ich als nicht-mathe Spezi, auch noch die Möglichkeit habe relativ schnell einen Einblick zu bekommen.
 

bluez

Member of Honour
Hervorragender Artikel! :)

Ich bin mir aber nicht ganz sicher, was du damit meinst:
Da die Kodewörter aus den Zeichen {0,1} bestehen, wird für weitere Rechnungen ein Modulo 2 immer gelten. So ist 1+1=0 [...]
Meinst du damit die Addition zweier binärer einsen wobei nur ein Ergebnisbit vorhanden ist?
Was hat das denn mit Modulo zu tun?
Meinst du nicht untere Gaußklammern?

Kleiner Ergänzungsvorschlag:
Wie wärs, wenn du die Parität direkt vor der Hamming-Distanz ergänzt? Du hast sie indirekt ja schon angesprochen ...

Ansonsten wirklich super gemacht und ich finde auch nicht, dass da zu viel Mathematik drin ist. Vielleicht sollten wir aber mal über einpaar Mathematiktutorials nachdenken :D
 

Darkslide

New member
Du hast eine abgeschlossene Menge bestehend aus {0, 1}. Was passiert, wenn du 1+1 rechnest? Es kommt 2 raus, was aber kein Element der Menge mehr ist. Daher wäre 2 ein ungültiges Ergebnis. Wie auch in der Kryptographie macht man sich die Modulorechnung zu nutze:

1+1=2==0 mod 2

Somit sind alle möglichen Ergebnisse einer Addition von 0 und 1 in der Menge {0,1}.
 

bluez

Member of Honour
Modulo war mir eigentlich nur für die Division bekannt.

Ich versteh auch offen gesagt nicht, warum bei einer abgeschlossenen Menge das Ergebnis aus Elementen außerhalb der Menge bestehen sollte. Ich würde mir eher Ergebnisworte aus der Menge zusammenbasteln.
 

Darkslide

New member
Die Ergebnise liegen ja durch die Modulorechnung immer in der Menge. Nehmen wir z.B. die Caesarverschlüsselung aus der Kryptographie:

Du hast ein Alphabet a-z, welches du einem anderen Alphabet 0-25 zuordnest. Damit erhälst du einen Ring, nennen wir ihn Z_26.

Nun wählst du deinen Schlüssel k=3. Was passiert mit den Buchstaben x, y und z, wenn du sie verschiebst? Sie sind nicht mehr Teil der Menge, denn:

x=23 -> x+k=26 -> 26 ist kein Element von Z_26
y=24 -> y+k=27 -> 27 ist kein Element von Z_26
z=25 -> z+k=28 -> 28 ist kein Element von Z_26

Nimmst du das Ergebnis aber Modulo 26, so erhälst du:

x->a
y->b
z->c

Somit bekommst du ein zyklisches Rotieren innerhalb des Rings Z_26 hin.

Hoffe es ist jetzt verständlicher
 

Scutus

Stammuser
Man definiert durch mod M, wobei M prim ist, einen endlichen Körper (falls M nicht prim nur einen Ring). Dadurch werden Restklassen definiert. Wie schon oben geschrieben, wird eine Folge von 1en und 0en als Polynom gesehen. So kann man das ganze Spielchen auch mit mod M(u) fortsetzen. Die Restklassen kann man durch zyklisches Verschieben des Polynoms erzeugen.

So ist das Beispiel 1+1 (mod 2) so zu sehen, dass man zuerst die Addition durchführen und danach die 2 einer Restklasse zuordnet - in diesem Fall der 0. Binäre, dyadisch oder allgemein adische Zahlen sind Darstellungen von Zahlen und haben mit einer endlichen Körper-, bzw. Ringbildung nichts zu tun. Das ist von mir recht schlampig ausgedrückt worden, vor allem um zu viel Mathe zu vermeiden.

Was eventuell noch einen gewissen praktischen Aspekt berücksichtigt, sind linear rückgekoppelte Schieberegister, die im Schema eines Polynoms aufgebaut sind. Wenn man nach und nach das gegeben Kodewort dort einfließen lässt, steht zum Ende hin das Fehlersyndrom im Register.
 
Oben