Quelle

6.2 Quelle

Quelle:

Eine diskrete gedächtnislose Quelle X erzeugt in jedem Zeittakt T ein Zeichen x_i aus dem Alphabet X = {x₁,x₂,…,x_N} mit der Wahrscheinlichkeit P(x_i) = p_i.

→Gedächtnislos heisst, das aktuelle Zeichen ist unabhängig von den bereits erzeugten.

Information:

Die Definition des Informationsgehalts eines Zeichens ist

( ) 1- I(xi) = ld pi = − ld pi

(6.2.1)

mit folgenden Eigenschaften:

Der Informationsgehalt ist ein nicht negatives Maß
$I(xi) ≥ 0 wegen 0 ≤ pi ≤ 1$ (6.2.2)
Für ein Zeichen mit p_i = 1∕2 ist der Informationsgehalt I(x_i) = 1. Dies ist die Pseudoeinheit der Information. Sie wird als bit (binary indissoluble information) bezeichnet⁶

Ein seltenes Symbol hat einen größeren Informationsgehalt als ein häufiges Symbol (der Informationsgehalt ist eine stetige Funktion der Wahrscheinlichkeit)

I(x1) ≥ I(x2) ≥ 0 falls p1 ≤ p2

(6.2.3)

Sonderfall keine Information:⁷
$I(xi) = 0 falls pi = 1$ (6.2.4)

Sonderfall unendliche Information:⁸

I(xi) = ∞ falls pi = 0

(6.2.5)

Für unabhängige Zeichenpaare (x_i,x_j) mit der Verbundwahrscheinlichkeit p(x_i ∧ x_j) = p_i ⋅ p_j gilt
$I(xi ∧ xj) = I(xi) + I(xj)$ (6.2.6)

Entropie:

Die Entropie einer Quelle wird (in Anlehnung an die Thermodynamik) als mittlerer Informationsgehalt ihrer Zeichen definiert zu

∑N H (X ) = E {I(X )} = − pi ld pi i=1

(6.2.7)

mit der Einheit bit.

→ Die Entropie ist ein Maß für die Ungewissheit der Zeichen X der Quelle. Das Chaos hat die maximale Entropie!

Die Entropie wird maximal (gleich dem Entscheidungsgehalt des Alphabets), wenn alle N Zeichen des Alphabets gleichwahrscheinlich sind
$N∑ 1 1 N 1 Hmax (X ) = − ---⋅ ld---= − --ld ---= ldN i=1 N N N N$ (6.2.8)

→ Bei binären Quellen mit N verschiedenen Zeichen (für die ld N eine ganze Zahl ist) ist ld N gerade die Anzahl der Binärstellen, um die Zeichen unabhängig von deren Auftrittswahrscheinlichkeit zu kodieren.

Beispiel 6.2.1 (Quelle)

Eine Quelle verwendet das Alphabet

X = {i,n,f,o,r,m, a,t,-}

Sie sendet damit folgende Nachricht

Z = {i n-f-o-r-m a t-i-o n-}

Wie groß ist der Informationsgehalt der Zeichen:

positionsunabhängig,
d.h. es ist NICHT bekannt, dass jedes 2. Zeichen ein Leerzeichen ist und
positionsabhängig,
d.h. es ist bekannt, dass jedes 2. Zeichen ein Leerzeichen ist.

Lösung:

Die Lösung wird in der Vorlesung erarbeitet. Zahlenwerte sind:

Positionsunabhängige Wahrscheinlichkeiten:
$1- p(zi = x9) = 2 1 p(zi ⁄= x9) = -- 2$

Informationsgehalt pro Zeichen:
$H1(X ) = 2,5bit-$
Positionsabhängige Wahrscheinlichkeiten:
$p(z1 = x9) = 0 p(z = (x ∨ x ∨ ...x )) = 1 1 1 2 8 p(z2 = x9) = 1$

Mit Umkodieren:
$H2 (X ) = Hmax (X ) = 3bit-$

Redundanz:

Die Differenz zwischen maximaler Entropie und der vorhandenen Entropie einer Quelle ist die Redundanz␣der␣Quelle

R = Hmax (X ) − H (X )

(6.2.9)

→ Bei einer redundanten Quelle treten einige Zeichen mit größerer Wahrscheinlichkeit auf als andere.

Sonderfälle:

Stationäre Quelle:
Bei einer stationären Quelle sind die Zeichenwahrscheinlichkeiten p_i invariant gegenüber einer Zeitverschiebung
→ p(x_i,t + Δt) = p(x_i,t).
Markoff-Quelle (gedächtnisbehaftete Quelle):
Die Zeichenwahrscheinlichkeiten p_i hängt ab von den letzten k Symbolen: Markoff-Quelle k-ter Ordnung⁹
→ p(x_i) = f(p_i−1,p_i−2,… ,p_i−k).

⁶Das Wort Bit (großgeschrieben) bezeichnet dagegen ein physikalisches Bit, z.B. eines Datenbusses mit 16 Bits. Ebenso werden Datenraten (bit pro Sekunde) auch kleingeschrieben, z.B. 10 Mbit/s.

⁷Das ist genau der Fall, den wir am Anfang besprochen haben: Ich bekomme eine Nachricht, die ich schon kenne …

⁸Das kannman sich eigentlich nicht vorstellen, aber was wäre, wenn wir im Radio die Nachricht hören würden: Vor dem Brandenburger Tor ist gerade ein UFO gelandet …

⁹Wie schwer das Gedächtnis einer Quelle zu finden ist, kann man am Beispiel des Roulettespiels sehen: Ist die Wahrscheinlichkeit für eine rote Zahl nach einer Folge langen Folge von schwarzen Zahlen größer, da ja die Quelle „weiß“, dass sie insgesammt mittelwertfrei sein muss? Die Quelle kann ja die aktuelle Verschiebung des Mittelwertes nur ausgleichen wenn sie mehr schwarze als rote Zahlen generiert!

[next] [prev] [prev-tail] [front] [up]