INFORMATIONSTHEORIEInhaltsverzeichnis
1. Allgemeines zur Informationstheorie Der Begriff Information wird verwendet, wenn es sich um den quantitativen Aspekt von Nach-richten geht. Quantitativ bedeutet, daß z.B. ein Buch mehr Informationsmenge besitzt als ein Flugblatt, bezogen auf die Seitenanzahl. Die Inhaltsschwere oder die subjektive Wertung dieser Nachricht hat aber nichts mit der Informationsmenge zu tun und ist für das technische Übertrag-ungssystem unwichtig und daher nicht von Interesse. Die von Claude E. Shannon 1948 begründete Informationstheorie gestattet es, die Leistung von verschiedenen Verfahren der Nachrichtenübertragung miteinander zu vergleichen und die Grenzen ihrer Leistungsfähigkeit aufzuzeigen. Bild 1.1 zeigt ein allgemeines Schema einer einseitig gerichteten Nachrichtenübertragung. Die Nachrichten- oder Informationsquelle erzeugt die Information, die dem Informationsverbraucher mitgeteilt werden soll. Mit Hilfe des Signals x wird die Information abgegeben. Der Codierer formt das Quellenausgangssignal x, in ein für die räumliche Übertragung über den Kanal ge-eignetes Signal X um. Durch Störungen und Verzerrungen auf dem Kanal wird das Signal X in das Signal Y umgeformt. Der Decodierer formt dieses Signal Y in das Signal y um, welches der Verbraucher aufgrund der Kommunikationsvereinbarung die an ihn gerichtete Information zu-ordnen kann. Bei Quelle und Verbraucher kann es sich um Maschinen, Menschen, oder sonstige, als Quelle und Verbraucher geeignete, Dinge handeln 52653gvi61okx4n
Bild 1.1 Allgemeines Schema einer Nachrichtenübertragung Ein und dieselbe Nachricht muss nicht immer durch genau das selbe Signal x dargestellt werden. Das kommt daher, da bei einer sprachlichen Kommunikation derselbe Inhalt schnell oder lang-sam, laut oder leise, mit oder ohne Dialektfärbung gesprochen werden kann. Der Quellencodierer hat nun die Aufgabe, alle verschiedenen Erscheinungsarten, welche eine Nachricht darstellen kann, in die gleiche Klasse einzuordnen. Der Quellencodierer teilt dem Kanalcodierer nur mit, in welche spezielle Klasse das von der Quelle gelieferte Signal x fällt. Der Kanalcodierer seiner-seits teilt der betreffenden Klasse ein Signal X zu, welches dann übertragen wird. Während der Quellencodierer ein Entscheidungsorgan ist, handelt es sich beim Kanalcodierer nur um einen Zuordner. Im Kanaldecodierer wird beim Empfang des Signal Y entschieden, zu welcher Klasse Y gehört. Diese Entscheidung wird wiederum dem Quellendecodierer mitgeteilt, der entsprech-end der getroffenen Entscheidung das Ausgangssignal y erzeugt und an den Verbraucher weiter-gibt. Der Quellendecodierer ist wie der Kanalcodierer ein Zuordner, der Kanaldecodierer wie der Quellencodierer ein Entscheidungsorgan. Nach diesem soweit beschriebenen Schema gliedert sich das Codierungsproblem in zwei Teilfragen:
Für die Sprachübertragung ist das Problem keineswegs in aller Vollkommenheit gelöst. Das Quellensignal x wird üblicherweise in aufeinanderfolgenden Zeitintervallen betrachtet. Dies bedeutet für den Verbraucher eine Quantisierung des Signals. Es kommt daher zu Verzerrungen, die jedoch in einem gewissen Maß zulässig sind. Das heißt, daß der Verbraucher keine exakte Reproduktion des Eingangssingals x benötigt, um die darin enthaltene Information zu erkennen. vk653g2561okkx Ein Maß zur quantitativen Beschreibung des Informationsgehalts eines Quellensignals dient der Begriff der Entropie. Weiter stellt die Entropie Verfahren bereit, wie ein Quellensignal am Besten zu Codieren ist, wenn die Entropie bekannt ist. Ferner liefert die Informationstheorie mit dem Begriff Kanalkapazität ein Maß dafür, wieviel Information pro Zeiteinheit über einen Kanal übertragen werden kann. Die sogenannte Rate-Distortion-Theorie beantwortet die Frage, unter welchen Bedingungen es möglich ist, ein Übertragungssystem so zu entwerfen, daß eine vorgegebene obere Grenze für eine vorgegebene durchschnittliche Verzerrung am Verbraucher-eingang nicht überschritten wird. Das Wesen einer Nachricht liegt darin, daß sie etwas neues zum Ausdruck bringt. Sie darf also nicht völlig vorhersagbar sein. Bevor also z.B. von einer diskreten Quelle eine Zeichen abge-geben wird, muß am Verbraucher eine gewisse Unsicherheit drüber herrschen, welches spezielle Zeichen folgt. Erst wenn dieses Zeichen eintrifft ist diese Unsicherheit beseitigt. Die Information eines jeden Zeichens liegt in der Unsicherheit, welche durch das Eintreffen desselben Zeichens beseitigt wird. Der Begriff Information soll nun an einem einfachen Beispiel erläutert werden, um zu zeigen, daß er sich durchaus im umgangssprachlichen Bedeutungsbereich von Information befindet. Allerdings bedarf er im Sinne der Informationstheorie einer exakten und damit einschränkenden Definition. Nach Bild 1.2 enthalte eine Urne sehr viele Kugeln. Davon sollen 70% weiß, 20% schwarz und 10% rot sein. Eine Person X zieht jeweils eine Kugel und teilt das Ergebnis (=Farbe) einer anderen Person Y mit. Der Empfänger kennt nur ihre Wahrscheinlichkeiten, mit denen sie auf-treten, nämlich 0,7 für weiß, 0,2 für schwarz und 0,1 für rot. Es ist offensichtlich, daß rot die größte Nachricht und weiß die geringste Information enthalten muß, denn wären beispielsweise alle Kugeln in der Urne weiß, wo würde stets die Nachricht weiß erscheinen, und das würde für den Empfänger keinerlei Information bedeuten, da er die Nachricht vorhersehen kann, aufgrund der Wahrscheinlichkeit von 1.
Bild 1.2 Ungestörte Nachrichtenübertragung Aus dieser Überlegung ergeben sich zunächst zwei Kriterien für die Definition des Informationsgehalts einer Nachricht - Der Informationsgehalt einer Nachricht muß um so größer sein, je kleiner die Wahrscheinlichkeit ihres Auftretens ist, d.h. je größer ihr „Überraschungswert“ ist. Es wird so die „Neuigkeit“, nicht die Inhaltsschwere der Nachricht definiert. - Eine Nachricht mit der Wahrscheinlichkeit 1 muss den Informationsgehalt 0 haben. Und ein drittes Kriterium erhält man, wenn man vernünftiger Weise verlangt, daß sich der Informationsgehalt voneinander unabhängiger Nachrichten addieren soll. 2. Diskrete Informationsquellen und Kanäle Eine diskrete Informationsquelle ist dadurch gekennzeichnet, daß sie nur diskrete Zeichen liefert, z.B. Ziffern, Buchstaben und dergleichen bzw. deren digitalen Codewörter. Sie liefert keine analogen Nachrichten. 2.1 Informationsgehalt statistisch unabhängiger Zeichen mit diskreten Quellen Eine Voraussetzung die wir zu Beginn treffen ist die, daß unter den beliebig vielen Zeichen und Merkmalen die wir betrachten, nur eine endliche Anzahl N von unterscheidbaren Zeichen vorhanden ist (z.B. ein geschriebener Text, der nur aus 30 verschiedenen Zeichen mit Zwischen-räumen und Satzzeichen besteht). Die Anzahl der unterscheidbaren Zeichen wie als Zeichen-vorrat oder Alphabet bezeichnet. Meist treten irgendwelche Zeichen in typischen Kombination-en auftreten. Solche Kombinationen oder Zeichenserien fast man der Einfachheit halber zu einem neuen Zeichen zusammen, das als Superzeichen bezeichnet wird (z.B. folgt nach einem q stets ein u Þ Superzeichen qu). Es können aber auch ganze Wörter als Superzeichen aufgefasst werden. In diesem Fall sind die Buchstaben zeichen und die Wörter Superzeichen. Dies kann man noch weiter Fortsetzen: Mehrere Wörter bilden ganze Sätze, die wiederum Absätze bilden usw. Ein solches Ordnungsschema bezeichnet man als Hierarchie Im folgenden soll sunächst nur der Fall interessieren, daß die einzelnen Zeichen keine statist-ische Bindung untereinander haben. Das heißt, daß die Wahrscheinlichkeit für das auftreteneine speziellen Zeichens unabhängig davon Ist, welche anderen Zeichen die Informationsquelle zuvor abgegeben hat. 2.1.1 Informationsgehalt von gleichwahrscheinlichen Zeichen Betrachtet wird eine Quelle mit einem Zeichenvorrat von N‘ Zeichen. Die Wahrscheinlichkeit das von diesen Zeichen ein bestimmtes auftritt ist für alle Zeichen gleich. Es ergibt sich somit: .... Auftrittswahrscheinlichkeit eines bestimmten Zeichens Der Informationsgehalt He eines beliebigen einzelnen Zeichens wird nun definiert als der Logarithmus des Zeichenvorrats N‘, oder dem Logarithmus aus der reziproken Wahrschein-lichkeit, wobei die Basis des Logarithmus vorerst offeinbleibt. .... Informationsgehalt Hiermit bestätigt sich die vorher getroffene Aussage, wonach ein Zeichen mit der Wahrschein-lichkeit P=1 keinen Informationsgehalt besitzt. Denn setzen wir für P=1 in die Formel für den Informationsgehalt He ein, ergibt dieser null. Die Informationsmenge He eines eher unwahr-scheinlichen Zeichens ist daher sehr groß. Die Wahrscheinlichkeit für das nacheinanderfolgende Auftreten zweier bestimmter Zeichen ergibt sich aus dem Produkt der einzelnen Wahrscheinlichkeiten. Da in unserem Beispiel die Wahrscheinlichkeit für jedes Zeichen groß ist ergibt sich P2. Damit ergibt sich auch der doppelte Informationsgehalt. Somit ergeben x Zeichen den x-fachen Informationsgehalt. Es ist auch ersichtlich und logisch, daß der Informationsgehalt immer positiv ist. Die Einheit des Informationsgehalts wird durch die Wahl der Basis des Logarithmus bestimmt. Die Logarithmen aus einer Zahl N‘ zur Basis 10, zur Basis 2 oder zu irgendeiner anderen Basis unterscheiden sich nur durch einen konstanten Faktor. Es gilt: logx(N‘) = logx(Y)*logy(N‘) Für uns sind eigentlich nur drei verschiedene Logarithmen interessant. Nämlich der zur Basis 10, der zur Basis 2 und der zur Basis e. Meist werden folgende Abkürzungen benutzt: log2 = ld ... dyadischer Logarithmus, Einheit [bit] loge = ln ... natürlicher Logarithmus, Einheit [nit] log10 = lg ... Brigg’scher Logarithmus, Einheit [dit] Es ergeben sich somit verschiedene Faktoren für die Umrechnung eines Logarithmus in einen Anderen: ld(N‘) = 3,322*lg(N‘) Û lg(N‘) = 0,301*ld(N‘) ld(N‘) = 1,443*ln(N‘) Û ln(N‘) = 0,693*ld(N‘) ln(N‘) = 2,304*lg(N‘) Û lg(N‘) = 0,434*ln(N‘) Wird für die Berechnung des Informationsgehaltes He der dyadische Logarithmus verwendet, ist seine Einheit 1bit, beim natürlichen Logarithmus 1nit und beim Brigg’schen Logarithmus 1dit. Die Bezeichnung bit kommt vom englischen binary digit (Binärziffer). Wenn der Informationsgehalt He mit dem dyadischen Logarithmus ld berechnet wird, dann gibt er an, wieviele Binärentscheidungen zur Auswahl eines beliebigen Zeichens aus dem Zeichen-vorrat N‘ benötigt werden. Die diesbezügliche Aussage des Quellencodierungssatzes lautet: Jedes von N‘ gleichwahrscheinlichen Zeichen in einer langen Zeichenfolge läßt sich im Durchschnitt mit minimal ld(N‘)+e Binärziffern codieren. Hierbei ist e eine positive Größe, die beliebig klein vorgegeben werden kann. Betrachten wir nun ein Beispiel mit einer Informationsquelle, deren Zeichenvorrat aus N‘ = 8 = 23 verschiedenen Zeichen a, b, c, d, e, f, g, h besteht. Alle Zeichen besitzen die gleiche Wahr-scheinlichkeit. Um jedes der acht Zeichen zu erhalten, kann man den Auswahlvorgang in mehrere Binärentscheidungen zerlegen, indem man beispielsweise eine Pyramide mit drei digitalen Schaltern aufbaut (Bild2.1). Durch die Angabe in welcher Schalterstellung sich die Schalter befinden, kann jedes Zeichen ausgewählt werden. Für den Buchstaben d gilt z.B. die Entscheidungsfolge 011 (Schalter1 offen, Schalter2 und Schalter3 geschlossen). Das Verzweig-ungsschema nennt man Codebaum. Aus diesem graphischen Codebaum (Bild 2.2) kann man die jeweilige Entscheidungsfolge eines jeden Zeichens ablesen. In diesem Beispiel wird jedes Zeichen nicht durchschnittlich, sondern mit genau He = ld8 = 3 Binärschritten ausgewählt.
Bild 2.2 Codebaum zu obiger Abbildung
Ist N‘ keine ganzzahlige Potenz von 2, dann kann jedes Zeichen mit durchschnittlich ld(N‘)+e Binärschritten ausgewählt werden, wobei die Größe e durch eine entsprechend günstige Codierung klein gemacht werden kann. Zur Erklärung dazu dient das nächste Beispiel. Der Zeichenvorrat sei N‘=3. Daher erhält man für He = ld(3) = 1,585. Der Zeichenvorrat besteht aus den gleichwahrscheinlichen Zeichen a, b und c. Bild 2.3 zeigt den einfachsten Codebaum zur Codierung dieser drei Zeichen. Die Buchstaben a und b werden durch zwei, c durch einen Binärschritt erreicht. Da alle Buchstaben gleichwahrscheinlich sind, wird Jeder mit durchschnit-tlich 5/3 = 1,667 Binärschritten (Gesamtanzahl der Binärschritte/ Zeichenanzahl) ausgewählt. Günstiger wird es, wenn je zwei Zeichen ein gemeinsames Codewort erhalten, was in Bild 2.4 dargestellt ist. Mit diesen Zweierkombinationen läßt sich ebenfalls jede Zeichenfolge aus den drei Zeichen a, b und c codieren, da es ja nur diese Zeichen gibt, keine Pausen oder Zwischen-räume. Sieht man sich den Codebaum an so erkennt man, daß jede Zweierkombination mit durchschnittlich 29/18 = 1,611 Binärschritten codiert werden. Dieser Wert ist schon bedeuted näher an ld8 als der vorherige. Durch Codierung längerer Zeichenketten kann dieser Wert erreicht werden, wobei definitionsgemäß e null wird. Bild 2.3 einfach aber ungünstiger Codebaum Bild 2.4 informationstheoretisch günstiger Codebaum 2.1.2 Informationsgehalt von nichtgleichwahrscheinlichen Zeichen
Wichtig ist es in einer langen Zeichenkette mit nichtgleichwahrscheinlichen Zeichen den Informationsgehalt He pro Zeichen zu erhalten. Betrachten wir zum Beispiel eine diskrete Quelle die wiederum nur die Zeichen a, b und c ausgiebt. Diesmal treten die Zeichen aber mit unter-schiedlicher Wahrscheinlichkeit auf. Dabei soll das Zeichen a mit der Wahrscheinlichkeit P(a) auftreten, b mit P(b) und c mit P(c). Für die Summe aller Wahrscheinlichkeiten gilt natürlich
P(a)+P(b)+P(c) = 1. Allgemeiner auch
Der Informationsgehalt des Zeichens a ist mit He,a = ld(1/P(a)) definiert. Betrachten wir nun eine sehr lange Zeichenkette mit n Zeichen, so tritt a mit n*P(a) nach dessen Wahrscheinlichkeit auf. Zählt man nun alle Informationsgehälter aller Zeichen a zusammen, so erhält man den Informationsbeitrag Ba mit . Somit ergibt sich der gesamte Informationsgehalt der Nachricht mit den Zeichen a, b und c mit:
Wollen wir nun den durchschnittlichen Informationsgehalt pro Zeichen, müssen wir den Informationsbeitrag B pro Zeichen n berechnen. Dazu braucht man die obige Formel nur umformen und erhält:
Allgemein würde diese Formel wiefolgt aussehen:
H(x) ist nun der durchschnittliche Informationsgehalt pro Zeichen für eine diskrete Informations-quelle mit N‘ verschiedenen, voneinander unabhängigen Zeichen xi (i = 1,2..N‘), von denen das i-te Zeichen mit der Wahrscheinlichkeit P(xi) auftritt. Der durchschnittliche Informationsgehalt pro Zeichen ist derselbe wie der Erwartungswert, d.h. jener Wert den man für den Informations-gehalt des Zeichens erwartet.
Es sei angenommen das die Zeichen mit gleicher Wahrscheinlichkeit auftreten. Setzten wir nun in die Formel für nichtgleichwahrscheinliche Zeichen, die allgemeine Gültigkeit besitzt, ein, so erhalten wir wenn gilt: P(xi) = 1/N‘ . Der durchschnittliche Informationsgehalt pro Zeichen muß bei gleichwahrscheinlichen Zeichen Natürlich gleich dem Informationsgehalt eines jeden einzelnen Zeichen sein (siehe Kapitel 2.1.1). H wird auch als Entropie der Quelle bezeichnet (manchmal auch als Negentropie). Bei gleichwahrscheinlichen Zeichen wird die Entropie noch dazu maximal. Dies läßt sich einfach an einem Beispiel mit einer Binärquelle veranschaulichen:
Eine Binärquelle liegt dann vor, wenn die Quelle nur zwei verschiedene Zeichen x1=a und x2=b aussenden kann. N‘ ist daher gleich zwei. Diese zwei Zeichen können dargestellt werden durch die logischen Zustände 0 und 1 bei digitalen Systemen. Tritt nun das Zeichen a mit der Wahr-scheinlichkeit P auf, so muß das Zeichen b mit der Wahrscheinlichkeit 1-P auftreten. Die Entropie, oder druchschnittliche Informationsgehalt pro Zeichen, ist demnach also:
Zur Bestimmung derjenigen Wahrscheinlichkeit P, bei welcher H maximal wird, müssen wir vorher den natürlichen Logarithmus einführen, da dieser beim Ableiten gebraucht wird:
Diese Beziehung wird nun in die obige Gleichung für H eingesetzt.
Nun können wir das Maximum berechnen, indem wir die Ableitung bilden
Diese Gleichung müssen wir nun null setzen um die Extremstellen zu erhalten. Für P=0,5 wird die Gleichung null und wir erhalten eine Extremstelle. P=0,5 bedeutet das beide Zeichen glechwahrscheinlich sind. Ob es sich bei dieser Extremstelle um ein Minimum, oder ein Maximum handelt, wird die zweite Ableitung zeigen.
Der mittlere Informationsgehalt pro Zeichen erreicht also ein Maximum, wenn beide Zeichen glechwahrscheinlich sind. Dasselbe Ergebnis erhält man für eine Quelle mit einem Zeichenvorrat von N‘ Zeichen. Da die allgemeine Ableitung aber etwas länger dauert und zum Verständnis nicht viel beiträgt wird sie hier übergangen. Es soll lediglich ncoh anhand eines Beispiels einer Quelle mit vier Zeichen a, b, c und d unterschiedlicher Wahrscheinlichkeit (Fall 1) gezeigt werden, daß man mit weniger Binärschritten auskommt, als wenn alle Zeichen gleichwahr- scheinlich währen (Fall 2).
Tabelle 2.1 Fall 1 liefert für H:
Fall 2 liefert für H:
Bei den ungleichen Wahrscheinlichkeiten von Fall 1 benötigt man also im Durchschnitt ¼ bit pro Zeichen weniger als im Fall 1 bei gleichen Wahrscheilichkeiten. 2.1.3 Quellencodierung, Redundanz, Informationsfluß Am Ende des vorigen Kapitels wurden zwei Quellen betrachtet, die je vier verschiedene Zeichen erzeugen können, einmal mit gleicher Wahrscheinlichkeit, einmal mit ungleicher Wahrschein-lichkeit. In der unteren Tabelle sind diese Werte noch einmal angeführt. Die Bedeutung der anderen Zeichen wird später erklärt.
|