![[HaBo]](/styles/default/logoklein.png)
Scutus
0
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.
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
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.
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
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.
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
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.
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:
