Datenkompression: Theoretische Grundlagen

Bereits im zweiten Kapitel wurden Begriffe verwendet, deren eigentliche Begrifflichkeit bislang nicht exakt definiert wurden. Das sind zum Beispiel die Begriffe Information, Entropie, Redundanz, Kanal, Nachrichtenquelle und einige andere mehr. Dieses Kapitel setzt sich mit genau diesen Problemen auseinander. Es erläutert diese Begriffe und beschreibt wie einige dieser Begriffe quantifiziert werden können.

Lassen Sie uns zunächst untersuchen, was ein geeignetes Maß, in Bezug auf die Information ist, und wie viel Information bspw. in einer Informationsquelle enthalten ist. Die Informationsquelle wird in diesem Buch auch als Nachrichtenquelle, als Datenquelle oder einfach als Quelle bezeichnet. Das Codieren von Informationen aus einer derartigen Quelle bezeichnet man als Quellencodierung (eng. sourcecoding). Der Begriff Datenkompression (eng. datacompression) wurde erst sehr viel später populär.

Um sich dem Modell der Nachrichtenquelle zu nähern, wie sie durch Claude Shannon erdacht wurde, ist es hilfreich sich mit einigen Grundlagen der Statistik und der Wahrscheinlichkeitsrechnung zu befassen. Nachdem die Nachrichtenquelle eingeführt worden ist, beginnt der Abschnitt der sich mit Information befasst. Was genau sie ist und wie sie funktioniert. Sollten Sie sich mit diesen Themen gut auskennen, so sei Ihnen eines der nachfolgenden Kapitel empfohlen.

Statistik und Wahrscheinlichkeit

Dieser Abschnitt ist derart umfangreich, dass die Entwicklung des Buches stark verzögert werden würde, diesen Abschnitt derzeit zu formulieren.

Nachrichtenquelle

Eine Nachrichtenquelle ${\mathcal {Q}}$ kann im mathematischen Sinne als geordnetes Paar ${\mathcal {Q}}=\left({\mathcal {S}},{\mathcal {P}}\right)$ verstanden werden, wobei ${\mathcal {S}}$ eine endliche Menge von Symbolen des Quellenalphabets darstellt. Das Quellenalphabet ist der sog. Symbolvorrat, den eine Nachrichtenquelle zu erzeugen im Stande ist. Für eine binäre Quelle ist das Quellenalphabet ${\mathcal {S}}=\left\{0,1\right\}$ nur ein Beispiel von vielen. ${\mathcal {P}}$ steht für die Wahrscheinlichkeitsverteilung des Quellenalphabets ${\mathcal {S}}$ . Das bedeutet dass ein bestimmtes Symbol aus einer Nachrichtenquelle mit einer ganz bestimmten Wahrscheinlichkeit erwartet werden kann. Mathematisch soll das in diesem Buch wie folgt formuliert werden: $p_{i}$ bzw. $p(x_{i})$ entspricht der Wahrscheinlichkeit, mit der das Symbol $x_{i}$ von der Nachrichtenquelle ausgegeben wird.

kontinuierliche Quellen
diskrete Quellen
gemischte Quellen

Im Allgemeinen spricht man bei Quellen mit einer endlichen Anzahl von möglichen Symbolen von einer wertdiskreten Quelle. Beispiele für wertdiskrete Quellen sind Computerprogramme, Bankauszüge oder Wiki-Bücher.

Beispiele für Quellen
- wertdisktret,
- zeitdiskret,
- wertkontinuierlich,
- zeitkontinuierlich
Abtastung

Gedächtnisfreie Quellen

Ein Quelle heißt gedächtnisfrei, wenn jedes einzelnen Element (Symbol) unabhängig voneinander auftritt. Welches Symbol wann auftritt, wird nicht durch die vorangegangenen Symbole beeinflusst. Mathematisch formuliert bedeutet dies, dass die Wahrscheinlichkeit für ein Symbol $x_{k}$ mit seinen bedingten Wahrscheinlichkeit identisch ist: $\forall x_{k}\in {\mathcal {S}}$ gilt: $P(X_{k}=x_{k})=P(X_{k}=x_{k}|X_{k-1}=x_{k-1},\cdots ,X_{2}=x_{2},X_{1}=x_{1})$

Wenn man die Begriffe aus der Wahrscheinlichkeitsrechnung oder der Statistik verwenden möchte, dann entspricht eine gedächtnisfreie Quelle einer Quelle, deren Symbole statistisch unabhängig voneinander sind. Die bedingte Wahrscheinlichkeit jedes Symbols ist identisch mit seiner nicht bedingten Wahrscheinlichkeit.

Modell Würfel

Gedächtnisbehaftete Quellen

Eine Quelle heißt gedächtnisbehaftet, wenn es mindestens ein Element (Symbol) dieser Quelle gibt, dass irgendwie vom Auftreten eines anderen Symbols abhängt. Damit ist gemeint, dass es Situationen geben kann, in denen sich eine Quelle anders verhält, wenn zuvor eine bestimmte Kombination von Symbolen ausgegeben worden ist. Mathematische formuliert heißt das, dass es mindestens ein solches Symbol gibt. $\exists x_{k}\in {\mathcal {S}}$ für das gilt: $P(X_{k}=x_{k})\neq P(X_{k}=x_{k}|X_{k-1}=x_{k-1},\cdots ,X_{2}=x_{2},X_{1}=x_{1})$ .

Mit Begriffen aus der Statistik oder Wahrscheinlichkeitsrechnung ausgedrückt, ist eine gedächtnisbehaftete Quelle eine Quelle, deren Symbole statistich nicht unabhängig voneinander sind.

Modell Kartenspiel oder Urne ohne zurücklegen

Entropie und Information

Man stelle sich folgende Situation vor, in der man ein Zeichen der Quelle ${\mathcal {Q}}=\left({\mathcal {S}},{\mathcal {P}}\right)$ liest, und man erhält ein Zeichen aus dem Symbolalphabet ${\mathcal {S}}$ entsprechend der Wahrscheinlichkeitsverteilung ${\mathcal {P}}$ .

Noch bevor das Zeichen gelesen wird, herrscht ein gewisses Maß an Unsicherheit darüber, welches Zeichen durch die Quelle ${\mathcal {Q}}$ ausgegeben werden wird. Nach dem Lesen hat man eine gewisses Maße an Information über die Quelle ${\mathcal {Q}}$ erhalten, indem ein gewisses Maß an Unsicherheit beim Empfänger reduziert wurde. Das zeigt, dass das Konzept über die Unsicherheit beim Empfänger und das über die Information direkt miteinander zusammenhängen.

Um es noch etwas besser zu verdeutlichen, soll eine ganz besondere Quelle betrachtet werden. Diese hat die folgende Eigenschaft $p\left(x_{1}\right)=1$ und für alle anderen Symbole des Alphabets soll die folgende Wahrscheinlichkeit gelten $p(x_{i})=0,i=2\dots |{\mathcal {S}}|$ . Das bedeutet, dass das Element $x_{1}\,$ immer ausgegeben wird und es gibt keinerlei Unsicherheit darüber, welches Zeichen als nächstes zu erwarten ist. Man erhält also keinerlei Information aus dieser Quelle. Man sagt der Informationsgehalt ist Null. Man stelle sich nun eine Quelle vor, bei nur einige wenige Symbole eine von Null verschiedene Auftretenswahrscheinlichkeit haben, so kann man ebenfalls schlussfolgern, dass die Unsicherheit über das zu erwartende Zeichen relativ gering ist, weil eben nur wenige Zeichen in Frage kommen, die durch diese Quelle ausgegeben werden. Andererseits ist die Unsicherheit am größten, wenn man überhaupt nicht in der Lage ist, das folgende Zeichen mit einer gewissen Sicherheit vorherzusagen. Das ist genau dann der Fall, wenn jedes Symbol aus dem Alphabet mit der gleichen Wahrscheinlichkeit auftritt, wenn also gilt: $p_{i}={\frac {1}{n}},n=|{\mathcal {S}}|,i\geq 1$ . In diesem Fall erhält der Empfänger das maximale Maß an Information, das eine Quelle bereitstellen kann.

Die Entropie ist ein Maß für die Unsicherheit darüber,
welches Zeichen durch eine Nachrichtenquelle als
nächstes gelesenes Zeichen zur Verfügung stehen wird.

Nun ist definiert, was die Entropie ist. Andererseits hängen Entropie und Information miteinander zusammen. Aber Information kann ja nicht das Maß für die Unsicherheit sein, die wir verspüren.

Was ist Information?
Information != Entropie; Information ist ja nicht die Unsicherheit!

Herleitung der Entropiefunktion

Gesucht wird eine Funktion $H\left(p_{1},p_{2},\dots ,p_{n}\right)$ , mit der die Unsicherheit quantifiziert werden kann, die mit dem Lesen einer Quelle verbunden ist. Eine wesentliche Eigenschaft der Entropiefunktion sollte sein, ausschließlich von der Wahrscheinlichkeitsverteilung abzuhängen, statt von den zu codierenden Elementen des Alphabets. Außerdem sollte $H$ für alle Werte und Kombinationen von

0\leq p_{i}\leq 1,i\in 1\dots n

definiert sein, für die gilt:

\sum _{i=1}^{n}p_{i}=1

.

Die maximale Unsicherheit über das von der Quelle nächste ausgegebene Zeichen herrscht genau dann, wenn das Symbolalphabet eine gleichmäßige Verteilung besitzt, also wenn gilt:

p_{i}={\frac {1}{n}},n=|{\mathcal {S}}|,i\in 1\dots n

.

Die Unsicherheit ist größer, wenn eine Gleichverteilung für ein Symbolalphabet auftritt, welches ein zusätzliches Zeichen besitzt, verglichen mit einem Alphabet mit weniger Symbolen und Gleichverteilung. Anders formuliert bedeutet es, dass H eine monoton steigende Funktion in Abhängigkeit von einem steigenden n ist. Mathematisch sieht diese Forderung wie folgt aus:

H({\frac {1}{n}},{\frac {1}{n}},\dots ,{\frac {1}{n}})<H({\frac {1}{n+1}},{\frac {1}{n+1}},\dots ,{\frac {1}{n+1}})

.

Entwicklung und Beschreibung der letzten wichtigen Eigenschaft (Zerlegbarkeit)
Entwicklung der Bedingungen und Überlegungen

Zusammenfassung aller Bedingungen

) $H(p_{1},p_{2},\dots ,p_{n})$ ist definiert und eine kontinuierliche Funktion und ausschließlich abhängig von der Wahrscheinlichkeitsverteilung. So dass die folgende Eigenschaft erfüllt ist: $0\leq p_{i}\leq 1,i\in 1\dots n$ gelten, für die gilt: $\sum _{i=1}^{n}p_{i}=1$ .
) $H({\frac {1}{n}},{\frac {1}{n}},\dots ,{\frac {1}{n}})<H({\frac {1}{n+1}},{\frac {1}{n+1}},\dots ,{\frac {1}{n+1}})$
) Die Funktion soll zerlegbar sein ... (schwer zu beschreiben)

vorstellen einer Funktion die exakt diese Bedingungen erfüllt
Beweis dass alle Bedingungen durch diese Funktion erfüllt sind

Die Entropiefunktion

Die Entropie beschreibt den mittleren Informationsgehalt, der mit den Symbolen einer Nachrichtenquelle assoziiert ist.

$H(p_{1},\dots ,p_{|{\mathcal {S}}|})=-\sum \limits _{i=1}^{|{\mathcal {S}}|}p_{i}\cdot \log \left(p_{i}\right)$

Logaritmus zur beliebigen Basis.
Basis 2 = Binärentropie (Einheit Bit/Shannon)

Einheit der Entropie

Eigenschaften der Entropie

Alter Text

obsoleter Text....

Das bedeutet, man sammelt $L$ aufeinanderfolgende Werte einer Nachrichtenquelle. Somit erhält man einen Nachrichtenvektor X mit der Länge $L$ , der auch als Symbolkette bezeichnet wird.

Eine Nachricht aus einer Quelle Q mit der Länge 4 kann beispielsweise aus der Symbolkette $x_{4}=\{q_{1},q_{2},q_{1},q_{1}\}$ bestehen. Die Elemente $q_{1},q_{2},q_{3}$ seien mögliche Realisierungen des Quellenalphabets.

Die Entropie nullter Ordnung ist dann definiert durch:

$H_{0}(x_{n})=-\sum \limits _{i=1}^{|S|}p_{i}\cdot \log \left(p_{i}\right)$

Wobei der Logarithmus zur Basis 2 genommen wird, um die Entropie in bit zu messen.

... bis hier

Geplante Themen

Rückschlussentropie
Streuentropie
Quellenentropie
Senkenentropie
Informationsgehalt
Shannons Codier-Theorem
Binäre symmetrische Kanäle
Stochastische Prozesse
Stationäre und nicht Stationäre Prozesse
Einzelcodierung vs. Blockcodierung
Markov/ff-Quellen
verlustfreie Codierung von Audio / Video und Bilddaten
PCM/DPCM/ADPCM

Das Ziel dieses Kapitels besteht darin, die Grundlagen zu schaffen, um den realen Informationsgehalt einer Information, Nachricht oder einer Nachrichtenquelle zu bestimmen. Dazu ist es zunächst notwendig eine Reihe von Begriffen einzuführen und zum Teil zu definieren.

Codierungstheorie / Informationstheoretische Grenzen
Berechnung von Informationsgehalt und Entropie
Ist es möglich Entropie zu reduzieren ?
Wahrscheinlichkeit und bedingte Wahrscheinlichkeit
Informationsgehalt bei bedingter Wahrscheinlichkeit
Transformation
Statistik und Stochastische Grundlagen
Verteilungen - Gleich/Gauss/Laplace - Verteilung Ausnutzen der Verteilung