1
Inhaltsverzeichnis
1. Allgemeines zur Informationstheorie
Seite 3
2. Diskrete Informationsquellen und Kanäle
Seite 5
2.1. Informationsgehalt statistisch unabhängiger Zeichen mit diskreten Quellen
Seite 5
2.1.
1. Informationsgehalt von gleichwahrscheinlichen Zeichen
Seite 5
2.1.2. Informationsgehalt von nichtgleichwahrscheinlichen Zeichen
Seite 9
2.1.
3. Quellencodierung, Redundanz, Informationsfluß
Seite 11
2.1.4. Optimale, redundanzsparende Codes
Seite 13
2.1.
4.1. Codierung nach Fano
Seite 13
2.1.4.2.
Codierung nach Huffmann
Seite 14
2.2. Informationsgehalt statistisch verbundener Zeichen mit diskreten Quellen
Seite 17
2.3. Informationsübertragung, Kanalkapazität diskreter Kanäle
Seite 21
3. Kontinuierliche Informationsquellen und Kanäle
Seite 23
3.
1. Entropie kontinuierlicher Quellen
Seite 24
3.2. Kanalkapazität gestörter kontinuierlicher Kanäle
Seite 25
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
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:
Quellencodierung (Informationsextraktion aus dem Quellensignal)
Kanalcodierung (Informationsübertragung)
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.
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.
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.
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.
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).
Zeichen xi
x1 = a
x2 = b
x3 = c
x4 = d
(1) P1(xi)
P1(a) = 1/2
P1(b) = ¼
P1(c) = 1/8
P1(d) = 1/8
(2) P2(xi)
P2(a) = 1/4
P2(b) = ¼
P2(c) = 1/4
P2(d) = 1/4
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.
Zeichen xi
a
b
c
d
Wahrscheinlichkeit
P(xi)
P1(xi)
1/2
1/4
1/8
1/8
P2(xi)
1/4
1/4
1/4
1/4
Code
Code 1
0
10
110
111
Code 2
00
01
10
11
Binärstellenzahl m(xi)
Je CW
Code 1
1
2
3
3
Code2
2
2
2
2
Tabelle 2.2
Bild 2.5 zeigt zwei Codebäume zur Codierung der Zeichen a, b, c und d. Es wird behauptet, daß Code 2 zur Codierung von Fall 2 optimal ist und zur Codierung von Fall 1 ungünstig.
Anders-herum ist Code 1 zur Codierung von Fall 1 optimal und für Fall 2 ungünstig. Die Codes 1 und 2 sind aus der Tabelle ersichtlich. Auch kann man die Anzahl m der Binärstellen je Codewort ablesen. Es sei noch darauf hingewiesen, daß der Code 1 mit verschieden langen Codewörtern ohne Trennzeichen in Serie übertragen werden kann, da kein kurzes Codewort gleich dem Anfang eines langen Codewortes ist. Man kann daher jedes Codewort unterscheiden.
Betrachten wir nun eine Zeichenfolge aus n Zeichen.
Berechnet werden soll die Anzahl m‘ der tatsächlich dabei im Mittel aufgewendeten Binärstellen, wenn beide Codes in beiden Fällen angewendet werden. Im folgenden wird die konkrete Binärstelle durch Bit ausgedrückt, während der abstrakte Informationsgehalt weiterhin in bit angegeben wird.
Die Anwendung von Code 1 im Fall 1 ergibt für die Anzahl m‘ der im Mittel aufgewendeten Binärstellen:
Die Anwendung von Code 1 auf Fall 2:
Code 1 erweist sich also im Fall 1 optimal, hingegen im Fall 2 ungünstig, da er dort mehr Bit/Zeichen aufwendet, als der mittlere Informationsgehalt angiebt.
Die Anwendung von Code 2 im Fall 1 ergibt für die Anzahl m‘ der im Mittel aufgewendeten Binärstellen:
Die Anwendung con Code 2 im Fall 2 ergiebt:
Code 2 erweist sich also im Fall 2 als optimal, hingegen ist er für Fall 1 ungünstig. Die aufgeführten Beispiele machen plausibel, daß allgemein der folgende Quellencodierungssatz gilt:
Für jede diskrete Quelle der Entropie H läßt sich ein Code so finden, daß die im Mittel aufgewendete Anzahl m‘ von Binärstellen pro Zeichen der Beziehung H £ m‘ £ H+e folgt, wobei e>0 beliebig klein vorgegeben werden kann. Es gibt keinen Code, der im Mittel mit weniger als H Binärstellen pro Zeichen auskommt.
Im nächsten Abschnitt werden zwei systematische Verfahren erläutert, die Codes mit kleinem e liefern. Zur Beurteilung der informationstheoretischen Eigenschaften von Codes dient der Begriff der Redundanz. Die absolute Redundanz R = m‘-H. Die relative Redundanz r ist: . Der bereits verwendete Begriff der Gleichwahrscheinlichkeitsredundanz ergibt sich für den Fall, daß alle Zeichen gleichwahrscheinlich sind, und ihre Codewörter gleiche Länge haben. Bei gleichwahrscheinlichen Codewörtern ist nämlich die Entropie H gleich ld(N‘).
Weiters ist bei gleich langen Codewörtern die Anzahl der Binärstellen pro Codewort konstant, d.h. m‘=ld(N). (Das nicht gestrichene N ist die Anzahl der möglichen Codewörter).
Bei Informationsquellen, welche die einzelnen Zeichen zeitlich nacheinander abgeben, bezeichnet man die auf die Zeit t0 bezogene Entropie als Informationsfluß H‘
Dieser Informationsfluß gehört zu digitalen Signalen, sofern pro Zeiteinheit nicht unendlich viele Zeichen von der Quelle abgegeben werden.
Bei flächenhaften Anordnungen wird H entsprechend auf die Fläche A bezogen.
Man nennt diese Größe die Informationsdichte x.
Optimale, redundanzsparende Codes
Es wurden bereits zwei Verfahren angekündigt, mit denen Codes geringer Redundanz, d.h. mit sehr kleinem e, aufgestellt werden können. Dies sind die Verfahren nach Fano und Huffman.
2.
1.4.1 Codierung nach Fano
Gegeben sind die N‘ verschiedenen Zeichen xi der Gesamtheit einer Quelle mit ihren unterschiedlichen Auftrittswahrscheinlichkeiten P(xi). Diese werden nach fallender Wahrscheinlichkeit untereinander und notiert ihre Wahrscheinlichkeit P(xi) in der rechts danebenstehenden Spalte. Dann bildet man von unten nach oben die Teilsummen und unterteilt die Spalte möglichst nahe bei si = 50% = 0,5. Als nächstes schreibt man in alle Zeilen der oberen Hälfte eine 0, in alle Zeilen der unteren Hälfte eine 1.
Damit ist die erste Stelle der Codewörter festgelegt. Dann werden die beiden Hälften wiederum möglichst nahe an deren arithmetischen Mittelwert der Teilsummen geteilt. Die Zeilen der beiden unteren Hälften (die der unter und die der oberen Hälfte) werden wieder mit 0 beschrieben, die Oberen mit 1. So fährt man fort, bis sich nur noch Teile mit je einem einzigen Zeichen xi ergeben. Die Anzahl der Binärstellen m(xi) der Zeichen xi, d.h.
die Länge der Codewörter, nimmt von oben nach unten bei richtigem Vorgehen monoton zu.
xi
x1
x2
x3
x4
x5
...
xN‘
P(xi)
P(x1)
P(x2)
P(x3)
P(x4)
P(x5)
..
.
P(xN‘)
si
1,0
...
0,0
Tabelle 2.3
Zur Erläuterung dieses Verfahrens wird in Tabelle 2.
4 die Codierung der Zeichen a, b, c und d mit den in Tabelle 2.2 Fall 1 angegebenen Wahrscheinlichkeiten durchgeführt. Es zeigt sich, daß dieses Verfahren zwangsläufig auf den Code 2 von Tabelle 2.2 führt, der sich bereits als optimal erwiesem hat.
xi
P(xi)
si
Unterteilung
Code
M(xi)
1,000
a
0,5
0,500
b
0,25
0,250
c
0,125
0,125
d
0,125
0,000
0
1
10
2
110
3
111
3
Tabelle 2.4
Zuerst teilt man, wie bereits beschrieben, die Tabelle in der Nähe von 50% (0,5) in zwei Hälften.
Die obere Hälte wäre in unserem Fall a und die Untere b,c und d. a bekommt nun eine 0, b, c und d eine 1 in iheren Code. Da die obere Hälfte nur ein Zeichen besitzt, kann sie nicht mehr geteilt werden, die Untere jedoch schon. In der unteren Hälfte ist die Summe si = 0,5. Teilt man beim arithmetischen Mittelwert, welcher 0,25 ist, so steht b in der oberen Hälfte, c und d in der Unteren. b bekommt somit eine 0, c und d eine 1.
Die untere Hälfte mit c und d kann nochmals bei 0,125 geteilt werden, womit c eine 0 in seinen Code bekommt und d eine 1.
Codierung nach Huffmann
Dieses Verfahren liefert manchmal bessere Ergebnisse als jenes von Fano und soll einfachheitshalber an einem Beispiel erklärt werden (Bild 2.6). Die Zeichen werden wieder nach ihrer fallenden Wahrscheinlichkeit untereinander geschrieben. Die beiden Zeichen mit der geringsten Auftrittswahrscheinlichkeit werden in eine Gruppe mit der Klassenbezeichnung I zusammengefasst. Nun wird eine neue Spalte aufgestellt, in derdie neue Klasse I entsprechend ihrer Wahrscheinlichkeit eingeordnet wird (die beiden Zeichen der Klasse I werden natürlich nicht mehr angeschrieben).
Man wiederholt dieses Verfahren solange, bis nur mehr eine Klasse, in unserem Beispiel Klasse IV, über bleibt. Wenn man die Zusammen-fassungen rückwärts auflistet, so ergibt sich daraus der Codebaum. Die Anzahl der Binärent-scheidungen ist somit festgelegt. Für die Zuordnung der Binärziffern ist nicht festgelegt, in unserem Beispiel wird für die oberen Äste 0 und für die Unteren 1 gewählt.
Wenn alle auftretenden Wahrscheinlichkeiten von der Form 2-ni (ni ganzzahlig) sind, z.B.
2-1, 2-2
2-3, dann ist bei optimaler Codierung (nach Fano oder Huffman) die Redundanz gleich Null. Normalerweise sind Wahrscheinlichkeiten aber nicht von der Form 2-ni. Dies bedingt, daß die im Mittel aufzuwendende Anzahl von Binärschritten m‘ etwas größer als H wird, also die relative Redundanz einen gewissen positiven Wert erhält. Durch Codierung von Zeichenkombinationen läßt sich die Redundanz jedoch verringern.
Als weiteres Beispiel wird die Wahrscheinlichkeit des Auftretens der einzelnen Buchstaben in einem deutschen Text betrachtet (siehe Tabelle 2.5).
In der Buchstabenspalte ist das oberste Zeichen das Leerzeichen. Satzzeichen wurden dabei nicht brücksichtigt. Der Code in Spalte 5 wurde nach dem beschriebenen Verfahren von Fano gebildet.
Der mittlere Informationsgehalt pro Zeichen (Buchstabe) H ergiebt sich entsprechend durch Aufsummieren aller Zahlen in Spalte 8, die den Informationsgehalt des jeweiligen Zeichens angibt.
Lfd.Nr.
i
Buch-stabe
xi
Wahrschein-lichkeit
P(xi)
Summe
si
Code (Fano)
Binär-stellen je Buch-stabe
P(xi)m(xi)
1
2
3
4
5
6
7
8
1
0,15149
1
000
3
0,45447
0,41246
2
E
0,147
0,84851
001
3
0,441
0,40661
3
N
0,08835
0,70151
010
3
0,26505
0,30928
4
R
0,06858
0,61316
0110
4
0,27432
0,26513
5
I
0,06377
0,54458
0111
4
0,25508
0,25322
6
S
0,05388
0,48081
1000
4
0,21552
0,22705
7
T
0,04731
0,42693
1001
4
0,18924
0,20824
8
D
0,04385
0,37962
1010
4
0,1754
0,19781
9
H
0,04355
0,33577
10110
5
0,21775
0,19689
10
A
0,04331
0,29222
10111
5
0,21655
0,19615
11
U
0,03188
0,24891
11000
5
0,1594
0,15848
12
L
0,02931
0,21703
11001
5
0,14655
0,14926
13
C
0,02673
0,18772
11010
5
0,13365
0,13967
14
G
0,02667
0,16099
11011
5
0,13335
0,13944
15
M
0,02134
0,13432
111000
6
0,12804
0,11844
16
O
0,01772
0,11298
111001
6
0,10632
0,1031
17
B
0,01597
0,09526
111010
6
0,09582
0,09531
18
Z
0,01423
0,07929
111011
6
0,08538
0,08729
19
W
0,0142
0,06506
111100
6
0,0852
0,08715
20
F
0,0136
0,05086
111101
6
0,0816
0,08432
21
K
0,00956
0,03726
1111100
7
0,06692
0,06413
22
V
0,00735
0,0277
1111101
7
0,05145
0,05209
23
Ü
0,0058
0,02035
11111100
8
0,0464
0,04309
24
P
0,00499
0,01455
11111101
8
0,03992
0,03815
25
Ä
0,00491
0,00956
11111110
8
0,03928
0,03766
26
Ö
0,00255
0,00465
111111110
9
0,02295
0,02196
27
J
0,00165
0,0021
1111111110
10
0,0165
0,01525
28
Y
0,00017
0,00045
11111111110
11
0,00187
0,00212
29
Q
0,00015
0,00028
111111111110
12
0,0018
0,0019
30
X
0,00013
0,00013
111111111111
12
0,00156
0,00167
0
Im Mittel aufgewendete Binärschritte
Mittlerer Informationsgehalt
Tabelle 2.5 Buchstabenhäufigkeit in der deutschen Sprache und Code nach Fano
Zur Berechnung der Redundanz des Codes von Spalte 5 wird die im Mittel pro Buchstabe aufgewendete Anzahl m’ an Binärschritten benötigt. Dazu betrachten wir eine genügend lange (theoretisch unendlich lange) Buchstabenfolge mit n Zeichen. In dieser Folge kommt der 1. Buchstabe (i=1) mit m(x1) = 3 Binärstellen n(Px1)-mal vor, der Zweite mit m(x2) Binärstellen
n(Px2)-mal vor usw. Die Gesamtzahl der Binärstellen in der Folge von n Buchstaben ist also mit Aufsummierung von Spalte 7
Daraus ergeben sich absolute und relative Redundanz R und r
R = m‘-H = 0,03373 [bit/Buchstabe]
Würden die 30 Buchstaben (einschließlich des Leerzeichens) mit gleicher Wahrscheinlichkeit auftreten, so ergäbe sich der mittlere Informationsgehalt H
H = ld(30) = 4,9 [bit/Buchstabe]
Wir haben also festgestellt, daß der mittlere Informationsgehalt der Buchstaben in deutschen Texten etwa 4,11 bit beträgt.
Dies gilt allerdings nur unter der Vernachlässigun, daß alle Zeichen voneinander statistisch unabhängig sind. Man darf daher nicht den Schluß ziehen, daß der mittlere Informationsgehalt eines zusammenhängenden Textes sich als Produkt der Buchstabenzahl und diesen 4,11 bit/Buchstabe erechnen ließe. In Wirklichkeit sind die aufeinanderfolgenden Buchstaben nicht statistisch unabhängig voneinander. Beispielsweise folgt auf ein q fast sicher ein u, was bedeutet, das dieses u hinter einem q überhaupt keinen Informationsinhalt besitzt. Auf den Buchstaben j folgt im Deutschen fast stets ein Vokal, auf c folgt meist h oder k usw. Durch diese statistischen Bindungen ist der wirkliche mittlere Informationsgehalt wesentlich kleiner als 4,11 bit/Buchstabe.
Mit diesem Thema beschäfitgt sich das nächste Kapitel.
2.2 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.
2.3 Informationsübertragung, Kanalkapazität diskreter Kanäle
Ein Übertragungskanal wird hauptsächlich durch seine Bandbreite und die in ihm auftretenden Störungen charakterisiert. Es soll nun untersucht werden, in welchem Maß über einen solchen Kanal Information fehlerfrei übertragen werden kann. Die kennzeichnende Größe dabei ist die sogenannte Kanalkapazität C.
Sie ist definiert als der Maximalwert desjenigen Teils des Informationsflusses H‘, welcher von der Informationsquelle bei optimaler Codierung über den gegebenen Kanal fehlerfrei in den Empfänger bzw. an den Informationsverbraucher gelangen kann.
Wir betrachten nun einen gestörten Kanal, an dessen Anfang eine Informationsquelle der Entropie H(x) liegt. Als Folge der Störungen wird nicht jedes der von der Informationsquelle abgegebenen Zeichen xi am Kanalende richtig empfangen. Ein Teil der am Kanalende empfangenen Zeichen yi sei wegen der Störungen von den Zeichen xi am Eingang verschieden. Von der Entropie H(x), die ja der durchschnittliche Informationsgehalt pro Zeichen am Kanaleingang ist, gelangt also nur ein Teil T welcher Transinformation genannt wird, ins Kanalende.
Der Rest, der Äquivokation (=Vieldeutigkeit) genannt wird, geht verloren. Wie sogleich gezeigt wird, ist die Äquivotation gleich der bedingten Entropie H(x½y). Damit gilt also:
T = H(x) – H(x½y)
Die bedingte Entropie H(x½y) ist ja laut Definition die zusätzliche durchschnittliche Informationsmenge pro Zeichen, welche durch die Zeichen xi dann noch geliefert wird, wenn die Zeichen yj bereits bekannt sind. Die Zeichen xi bringen keine zusätzliche Information, wenn sie durch die Zeichen yi bereits völlig bestimmt sind, was bei fehlerfreier Übertragung der Fall ist. Die bedingten Wahrscheinlichkeiten sind dann P(xi½yj)=1 damit sind die Logarithmen und damit wird auch H(x½y) gleich Null. Bei gestörter Übertragung enthalten die Zeichen xi der Quelle neben der Transinformation noch zusätzliche Information, die verlorengeht.
Diese zusätzliche Information muß gleich der bedingten Entropie sein, womit die obige Gleichung erklärt ist.
Für den Empfänger wirkt das Kanalende wie eine Informationsquelle der Entropie H(y). Diese Entropie setzt sich zusammen aus der Transinformation und den Störungen, der Irrelevanz, die, wie noch gezeigt wird, gleich der bedingten Entropie H(y½x) ist, also gilt:
T = H(y)-H(y½x)
Die bedingte Entropie H(y½x) ist laut Definition die zusätzliche Entropir welche die Zeichen yj dann noch bringen, wenn die Zeichen xi bekannt sind. Diese zusätzliche Information (die zusätzlichen „Überraschungen“ am Kanalausgang) können nur von den Störungen herrühren. Faßt man all dies zusammen so ergibt sich das Schema von Bild 2.7
Elimineirt man in der letzten Gleichung die bedingte Entropie H(y|x), dann erhält man eine weitere Beziehung zur Berechnung der Transinformation, nämlich
T = H(x)+H(y)-H(x,y)
Bezieht man die Entropie auf die Zeit t0, dann errechnet sich derTransinformationsfluß T‘ eines digitalen Signals wiefolgt.
T‘ = H‘(x)-H‘(x|y)
Die Kanalkapazität C eines Kanals ist nun als Maximalwert des Transinformationsflusses definiert, den der Kanal zuläßt.
C = T’max = MAX(H‘(x)-H‘(x|y))
In diesem Zusammenhang steht der sogenannte Kodierungssatz:
Sind ein diskreter Kanal der Kapazität C und eine diskrete Informationsquelle mit dem Informationsfluß H‘(x) gegeben, wobei C ³ H‘, dann läßt sich stets ein Code finden, der es erlaubt, die Information mit einem beliebig kleinen Fehler (bzw. mit einer beliebig kleinen Äquivokation) über den Kanal zu überragen. Ist C<H‘, dann kann die Äquivokation kleiner als H‘-C+e gemacht werden, wobei e beliebig klein ist. Es ist jedoch nicht möglich die Äquivokation kleiner als H‘-C zu machen.
Die Transinformation sei noch an einem Beispiel erklärt: Ein Kanal wird von einer Binärquelle mit Zeichen im Binärcode mit den Symbolen x1=1 und x2=0 gespeist.
Beide Symbole mögen mit der Wahrscheinlichkeit P(x1) = P(x2) = 0,5 auftreten. Die Entropie H(x) am Kanaleingang ist dann:
Mit einer Telegraphiegeschwindigkeit von 1 Bit/sec. Ergibt sich damit auch der Informationsfluß H‘(x) mit 1 bit/s.
Die auf dem Kanal auftretenden Störungen seien sehr groß. Die Wahrscheinlichkeiten, daß bei empfangenen yj = 0 am Eingang xi = 0 oder xi = 1 gesendet wurde, und daß bei empfangenen
yj = 1 am Eingang xi = 0 oder xi = 1 gesendet wurde, seien je P(xi|yj) = 0,5. Die Äquivokation wird damit:
Damit ist die Transinformation T=0, was eigentlich selbstverständlich ist, denn die am Kanal-ausgang empfangenen Binärzeichen hätte man genausogut durch Zufall bestimmen können (z.
B. durch Werfen einer Münze).
3. Kontinuierliche Informationsquellen und Kanäle
Eine kontinuierliche Informationsquelle liegt vor, wenn die Nachricht z.B. in Form irgendeiner analogen Zeitfunktion x(t) anfällt, wie das beispielsweise für die Ausgangsspannung eines Mikrophons gegeben ist (siehe Bild 3.
1). Kennzeichnend ist daran vor allem, daß die Spannung jetzt nicht mehr nur diskrete Werte annehmen darf, sondern einen kontinuierlichen Wertebereich durchlaufen kann. Wenn durch eine solche Funktion Information geliefertwird, dann darf die nicht vollständig vorhersagbar sein. Eine periodische Funktion, z.B. die Sinusfunktion, bringt keine Information.
Als informationstragende Funktion kommen nur Zufallsfunktionen, oder anders ausgedrückt, Musterfuntionen zufälliger Prozesse in Frage. Die in Bild 3.1 dargestellte Funktion x(t) sei eine von unendlich vielen möglichen Musterfunktionen
Bild 3.1 Beispiel einer analogen Zeitfunktion
Welcher Funktionswert x(t1) zu einem willkührlich gewählten Zeitpunkt t1 konkret angenommen wird, läßt sich zu Zeiten t<t1 nicht exakt vohersagen. Für jeden Funktionswert x(t1) läßt sich nur eine Wahrscheinlichkeit angeben (die realerweise noch von der Vorhersagezeit t1-t abhängt, was aber hier zunächst nicht weiter beachtet werden soll). Da zum festen Zeitpunkt t1 die möglichen Funktionswerte in einem Kontinuum liegen, hat im Normalfall jeder Funktionswert eine verschwindend kleine Wahrscheinlichkeit.
Würde man auf einen solchen Funktionswert den für diskrete bzw. digitale Signale definierten Begriff des Informationsgehaltes anwenden, dannergäbe sich ein extrem hoher Informationsgehalt, der aber mit verschindend kleiner Wahrscheinlichkeit auftritt. Für die Entropie, d.h. für den Mittelwert des Informationsgehalt über alle möglichen Funktionswerte x zum Zeitpunkt t ergibt sich jedoch in der Regel ein endlicher Wert. Zur Berechnung der Entropie zum Zeitpunkt t1 bei analogen stochastischen Prozessen benutzt man anstelle der diskreten Wahrscheinlichkeiten P(xi) die Wahrscheinlichkeitsdichte p(x).
Der Übergang vom diekreten zum kontinuierlichen Fall bringt aber, wie sich zeigen wird, noch einige zusätzliche Eigenschaften mit sich, die für informationstheoretische Betrachtungen nicht unwesentlich sind. Es ist deshalb bequem, in diesem Zusammenhang von passenden Neudefinitionen zu sprechen.
Entropie kontinuierlicher Quellen
Die Entropie einer diskreten Quelle statistisch voneinander unabhängiger Zeichen war:
In entsprechender Weise wird nun die Entropie kontinuierlicher Quellen mit der Wahrscheinlichkeitsdichtefunktion p(x) folgendermaßen definiert:
Die Definition für H(x) für kontinuierliche Quellen ergibt ähnliche Eigenschaften für die Entropie H wie die Definition für H(x) für diskrete Quellen. Wenn alle Musterfunktionen x(t) beschränkt sind auf einen endlichen Wertebereich, dann läßt sich zeigen, daß H(x) maximal wird, wenn p(x) eine Rechteckverteilungsdichte aufweist (siehe Bild 3.2). Dieses Ergebnis ist plausibel, da ja auch im diskreten Fall sich die maximale Entropie dann ergab, wenn alle Zeichen gleich wahrscheinlich wahren.
Wenn der Wertebereich von x zwar nicht beschränkt ist, aber trotzdem die mittlere Signaleistung beschränkt ist, dann ergibt sich über eine Variarionsrechnung die maximale Entropie, wenn p(x) eine Gaußsche Verteilungsdichte darstellt:
(Normalverteilung)
s² ist die Streuung. Ihre positive Wurzel s heißt Standardabweichung. Wenn x eine Spannung ist, dann ist die Standardabweichung gleich dem Effektivwert der Spannung s = Ueff. Daraus folgt, daß bei beschränkter Leistung eine solche Zeitfunktion x(t) die maximale Entropie H ergibt, welche die gleichen statistischen Eigenschaften wie z.B. Widerstandrauschen hat.
Auch Verbundentropie und bedingte Entropie ergeben sich bei kontinuierlichen Quellen ebenso wie bei diskreten Quellen.
p(y|x) bedingte Wahrscheinlichkeitsdichte, daß y im Bereich dy auftritt, wenn x aufgetreten und bekannt ist.
p(x|y) bedingte Wahrscheinlichkeitsdichte, daß x im Bereich dx auftritt, wenn y aufgetreten und bekannt ist.
Für die Dichtefunktion p(x,y) und p(y|x) gelten ganz entsprechende Beziehungen wie für die
Entsprechenden Wahrscheinlichkeiten P(x,y) und P(y|x). Es allerdings einen wichtigen
Unterschied zwischen der Entropie diskreter und kontinuierlicher Signale. Während die Entropie diskreter Signale ein absolutes Maß über die Unsicherheit der Zeichen xi liefert, gibt die Entropie kontinuierlicher Signale nur ein relatives Maß über die Unsicherheit der Variablen x.
Dieses relative Maß hängt vom gewählten Koordinatensystem ab. Das soll anhand eines Beispiels verdeutlicht werden: Wir betrachten eine Quelle, die eine Zeitfunktion x(t) erzeugt, wobei die Ordinate x beschränkt sei und eine rechteckige Wahrscheinlichkeitsdichtefunktion entsprechend Bild 3.2 hat. Es sei mit a=2: -2 £ x £ 2
Der größte Ordinatenwert ist x=2, der kleinste ist x=-2. Dazwischen sind alle x gleichwahrscheinlich.
Die Entropie ist somit
Das Signal x(t) soll nun mit einem idealen störungs- und verzerrungsfreien Verstärker achtfach verstärkt werden.
Dann ist am Verstärkerausgang der größte Ordinatenwert x=16, der Kleinste x=-16. Dazwischen sind wieder alle Werte gleichwahrscheinlich, d.h. –16 £ x £ +16 p(x)=1/32.
Die Entropie am Verstärkerausgang ist nun
Der ideale Verstärker kann natürlich keine zusätzliche Information bringen. Die Änderung der Entropie ist lediglich durch eine Maßstabänderung, d.
h. eine Änderung des Koordinatensystems bedingt. Es zeigt sich aber, daß Maßstabänderungen keine rolle spielen, wenn Differenzen von Entropien betrachtet werden. Diese wichtige Tatsache soll nicht allgemein bewiesen, aber an einem einfachen Beispiel erläutert werden. Eine Quelle hat die Entropie H(x) = 2. Eine andere Quelle hat die Entropie H(y) = 4.
Die Werte x und y sind als gleichförmig verteilt angenommen. Die Entropiedifferenz ist also H(y) – H(x) = 2. Wenn beide Signale x und y achtfach verstärkt werden, dann ergeben sich H(x) = 5 und H(y) = 7. Die Differenz bleibt jedoch 2, also konstant und davon unberührt.
Die Unabhängigkeit von Entropiedifferenzen vom Maßstab ist von großer praktischer Bedeutung, da bei der Informationsübertragung hauptsächlich die Transinformation und die Kanalkapazität von Interesse sind. Beide Größen werden von Entropiedifferenzen gebildet und sind somit vom Maßstab unabhängig.
Zur Berechnung des Informationsflusses H‘ wird die Entropie auf die Zeit bezogen. Liegt ein bandbegrenztes kontinuierliches Signal vor, dann brauchen nach dem Abtasttheoremnicht für alle Zeitpunkte die Ordinatenwerte übertragen zu werden. Es genügt die Betrachtung der Ordinatenwerte in Zeitabständen der doppelten maximal auftretenden Frequenz. Da dies zugleich der kürzestmögliche Abstand für statistisch unabhängige Abtastwerte ist, errechnet sich der Informationsfluß H‘ zu:
Hierbei ist unterstellt, daß kontinuierliche Spektrum von x(t) den Bereich –fmax £ f £ fmax tatsächlich einnimmt.
Kanalkapazität gestörter kontinuierlicher Kanäle
Für Transinformation T und Kanalkapazität C gelten auch im kontinuierlichen Fall diesselben Beziehungen wie im diskreten Fall. Die Transinformation läßt sich also mit T = H(y)-H(y|x) bestimmen, wobei H(y) die Entropie am Kanalausgang und H(y|x) die zusätzliche Entropie der Variablen y am Kanalausgang ist, wenn die Variable x am Kanaleingang gekannt ist.
H(y|x) kennzeichnet also die am Ausgang wirksamen Störungen.
Alle Signale seien nun durch Spannungen ausgedrückt, die auf die Bezugsspannungen U normiert werden, damit die Argumente der verschiedenen Funktionen dimensionslos werden.
Für die gesendeten Signale gelte
Die empfangenen Signale mögen sich aus der Überlagerung von Sendespannung us und Störspannung un zusammensetzen.
us und un seien zufällige Spannungen, die statistisch voneinander unabhägig sind. Die bedingte Entropie des Ausgangssignals y bei bekannetem Eingangssignal x muß gleich der Entropie des Störsignals sein.
Für die Transinformation gilt damit:
Es sei nun angenommen, daß Nutzsignal us und Störsignal un normalverteilt sind, daher eine normalverteilte Wahrscheinlichkeitsdichtefunktion vorliegt.
Damit ist aber auch die Überlagerung von Nutz- und Störsignal normalverteilt.
Zur Berechnung der Transinformation T benutzen wir folgende Formeln
Die untere Gleichung ergibt sich durch partieller Integration aus dendarüber stehenden Beziehungen. Zur Durchführung der partiellen Integration setzt man z=u und den restlichen Integranden gleich v‘.
Die Entropie H(z) eines normalverteilten Signals z berechnet sich nun folgendermaßen:
Hierin ist
Und damit ergibt sich aus den beiden obigen Gleichungen:
Bezeichnet man den Effektivwert der Störspannung un mit Ueff,n, dann ergibt sich mit z = un/U und s = Ueff,n/U die Entropie.
Bezeichnet man ferner den Effektivwert der Signalspannung us mit Ueff,s, dann ergibt sich bei statistischer Unabhägigkeit von Signal un Störung der Effektivwert der Überlagerung us + un zu .
Mit und folgt:
Damit ergibt sich für die Transinformation
Ps ist die Signalleistung, Pn ist die Störleistung.
Die Bezugsspannung U, deren Größe den Maßstab bestimmt, spielt, wie zu erwarten war, bei der Berechnung der Transinformation keine Rolle.
Der Transinformationsfluß T‘ berechnet sich unter Voraussetzung bandbegrenzter Signale wiefolgt:
Da für die Herleitung der letzten Gleichung Signale mit Gaußschen Verteilungskurven vorrausgesetzt wurden, ist der berechnete Transinformationsfluß bei gegebener Störleistung Pn und maximal übertragbarer Leistung Ps = Psmax zugleich auch der maximal mögliche Transinformationsfluß T’max, der über einen Kanal geleitet werden kann. Damit hat ein solcher Kanal die Kanalkapazität
.
Bisher wurde vorausgesetzt, daß das Spektrum der Zeitfunktion un(t) bzw. us(t) sich von der Frequenz Null bis zu einer oberen Grenze fmax erstreckt (B=fmax). Diese Voraussetzung wurde insbesondere auch bei der Herleitung des Abtasttheorems gemacht.
Ist die Zeitfunktion u(t) auf die Bandbreite B begrenzt, wobei das Frequenzband aber im Bereich höherer Frequenzen liegt, also die Fequenz Null nicht enthält, dann gilt ein Abtasttheorem 2.Art. Dieses besagt, daß die Zeitfunktion u(t), welche die Bandbreite B hat und als höchste Frequenzkomponente fmax enthält, eindeutig durch einzelne Funktionswerte im Abstand m/2fmax bestimmt ist. Dabei ist m die größte ganze Zahl, die fmax/B nicht überschreitet. Der größte Abstand ergibt sich, wenn fmax ein ganzzahliges Vielfaches von B ist. Dann beträgt der maximale Abstand 1/2B
Die Klammer bedeutet die nächst-höhere ganze Zahl.
Der Beweis dieses Theorems ist sehr aufwendig und wäre deshalb nicht angebracht.
Für bandbegrenzte und gestörte Kanäle mit der Bandbreite B und der Störleistung Pn sowie der maximal übertragbaren Signalleistung Ps gilt
.
Die letzte Gleichung stellt eines der wichtigsten Ergebnisse der Informationstheorie dar. Dieser theoretische Maximalwert kann praktisch nur durch sehr komplizierte Sende- und Empfangssysteme asymptotisch erreicht werden. Im Normalfall ist Ps >> Pn, so daß gilt . Dieses Verhältnis (=Störabstand) wird zweckmäßiger Weise in dB angegeben, d.
h. es wird 10lg(Ps/Pn) gebildet. Dazu muß der dyadische Logarithmus in den Dekadischen umgerechnet werden. Es ergibt sich dann folgende Beziehung.
In Tabelle 3.1 sind die Kanalkapazitäten einiger elektrischer Übertragungskanäle zusammengestellt.
Kanal
Bandbreite
B
Störabstand
Ps/Pn [dB]
Kanalkapazität
C [bit/s]
Telegraphiekanal (50 Baud)
25 Hz
15
75
Fernsprechkanal
3,1 kHz
50
50.000
Rundfunk-MW
6 kHz
70
140.000
Rundfunk-UKW
15 kHz
70
350.000
Fernsehkanal
5 MHz
45
75.000.000
Tabelle 3.
1
| Anmerkungen: |
| impressum | datenschutz
© Copyright Artikelpedia.com
