Informationsgehalt statistisch verbundener zeichen mit diskreten

Quellen Zeichenfolgen, bei denen die einzelnen Zeichen nicht statistisch unabhängig voneinander sind, sondern bei denen die Wahrschinlichkeit für das Auftreten einesbestimmten Zeichens an einer bestimmten Stelle auch davon abhängt, welche Zeichen vorausgegangen sind, bezeichnet man als Markhoffsche Prozesse. Im einfachsten Fall wird die Wahrscheinlichkeit für das Auftreten eines Zeichens nur vom unmittelbar vorausgegangenen Zeichen beeinflußt. Im nächst komplizierteren Fall hängt die Wahrscheinlichkeit von den zwei vorausgegangenen Zeichen ab usw. Im Rahmen dieses Refarats soll uns nur die Abhängigkeit von eiem einzigen vorausgegangenen Zeichen interessieren.

Zur Beschreibung von Quellen, deren Zeichen in der oben beschriebenen Weise voneinander abhängen, werden die Begriffe Verbundwahrscheinlichkeit P(xi, yj) und bedingte Wahrscheinlichkeit P(xiyj) bzw. P(yjxi) benötigt.

Im folgenden werden jetzt Kombinationen von je zwei diskreten Zeichen (xi, yj) betrachtet. Diese Zeicchenpaare können z.B. von je zwei aufeinanderfolgenden Zeichen derselben Quelle gebildet werden, oder aber auch von Zeichen aus verschiedenen Quellen. Die Verbundentropie H(x, y) eines solchen Zeichenpaares ist



Für den Fall, daß xi und yj statistisch unabhängig sind erechnet sich H(x, y)

In diesem Fall ist also die Verbunentropie gleich der Summe der Einzelentropien. Liegt aber statistische Bindung vor, dann gilt:

H(x, y) < H(x)+H(y)

Sind die Zeichen xi bekannt, so können die Zeichen yi nur dann zusätzliche Information enthalten, wenn die bedingten Wahrscheinlichkeiten P(yjxi) für das Auftreten von yi kleiner als Eins sind. Die Logarithmen aus den Kehrwerten von P(yjxi) multiliziert mit den Wahrscheinlichkeiten P(xi, yj) ergeben die bedingte Entropie H(yx).


Sind x nd y statistisch unabhängig, dann errechnet sich, daß die bedingte Entropie H(yx) gleich der Entropie.

Zwischen der bedingten Entropie und der Verbundentropie errechnet sich folgender Zusammenhang:





Hält man im ersten Term der Gleichung das i konstant und summiert über alle j auf, dann kann ausgeklammert werden und es ergibt sich:


Weiters gilt H(x, y) = H(y)+H(xy)

Die Entropie eines Verbundereignisses ist also gleich der Entropie des einen Ereignisses plus der bedingten Entropie des anderen Ereignisses, sofern das erste Ereignis bekannt ist. Ist das Auftreten der einzelnen Zeichen statistisch unabhängig, dann ergibt sich, daß die Verbundsentropie H(x, y) gleich der Summe der Einzelentropien ist.

Mit Hilfe der Tabellen 2.6 und 2.7, die als Angabe dienen, soll ein Beispiel für doe Berechnung der Verbundentropie gegeben werden.


Verbundentropie

P(xi, yj) yj


a b c


xi a 0 0,267 0,067
b 0,296 0,296 0

c 0,037 0,0296 0,0074


Tabelle 2.6 Verbundentropie




bedingte Entropie
P(yjxi) yj


a b c

xi a 0 0,8 0,2

b 0,5 0,5 0
c 0,5 0,4 0,1

Tabelle 2.7 bedingte Entropie



Wäre keine statistische Bindung zwischen den Buchstaben vorhanden gewesen, dann hätte sich für dieselbe Quelle mit Tabelle 2.8 die Entropie als Summe der Einzelentropien gegeben:

xi

yj


a
b

c
P(xi)

P(yj) 0,33 0,593 0,0741


Tabelle 2.8




Die statistische bindung zwischen den Buchstaben hat in diesem Beispiel also eine Entropiedifferenz von 0,354 bit/Buchstabe zur Folge.

Bei einem normalen Text mit gewöhnlichem Alphabet aus 30 Buchstaben herrscht jedoch eine Bindung über mehr als zwei aufeinanderfolgenden Buchstaben. Das hat zur Folge, daß die Entropie solcher Texte relativ klein wird. Das heißt, das durch die statistische Bindung zwischen den Buchstaben der Textaufwand steigt, um die selbe Nachricht zu übertragen, als wenn die Buchstaben voneinander unabhängig wären. Für englische Texte errechnete Shannon, daß ein der Informationsgehalt eines Buchstaben 1 bit beträgt. In deutschen Texten haben die Buch-staben eine etwas geringere Entropie. Der schon in Kapitel 2.1.1 erwähnte Quellencodierungs-satz gilt auch für Informationsquellen mit statistisch gebundenen Zeichen. Dies sei am Beispiel des Alphabets erläutert werden. Betrachtet man in einem Text nicht aufeinanderfolgende einzelne Buchstaben, sondern das Aufeinanderfolgen zusammenhängender Ketten von z.B. fünf Buchstaben, so läßt sich in viel geringerem Maße von der Kenntnis einer Kette auf die nächst-folgende Kette schließen, als das bei der Betrachtung einzelner Buchstaben der Fall ist. Sehr lange Ketten sind praktisch unabhängig voneinander. Diese können dann als einzelne Super-zeichen aufgefaßt werden und optimal codiert werden. Die Anzahl der möglichen verschiedenen Superzeichen ist natürlich sehr groß.

Bei gesprochener deutscher Sprache ergeben sich bei 0,9 bit/Buchstabe folgende Zahlen:

langsames Sprechen (5...7) Buchstaben/sec. (4,6...6,5) bit/sec.
normales Sprechen (12...15) Buchstaben/sec. (11...14) bit/sec.
schnelles Sprechen (18...26) Buchstaben/sec. (16...24) bit/sec.

Werden die einzelnen Telegraphiezeichen übertragen, dann ist es bei optimaler Codierung nach dem Codierungssatz theoretisch möglich, gesprochene Sprsche mit einer Telegraphiegeschwind-igkeit von weniger als 50 Bit/sec. Zu übertragen. Die bisher realisierten technischen Übertrag-ungssysteme sind jedoch von dieser Grenze weit entfernt.