Digitaltechnik von Prof. Jürgen Plate

1 Nachricht und Information

Neben der Energie (und der Materie) ist Information eine zweite Basisgröße von universeller Bedeutung. Ihre Eigenständigkeit wurde erst spät erkannt, da ihre Weitergabe immer an energetische oder materielle Träger gebunden ist. An Informationen gelangt man über Nachrichten. Die Definition von Information in der Informatik deckt sich nicht ganz mit dem umgangssprachlichen Gebrauch.

• Information ist die Kenntnis über Irgendetwas.
• Nachrichten dienen zur Darstellung von Information.

Die abstrakte Information wird durch die konkrete Nachricht mitgeteilt.

Nachrichten und Alphabete

Zur exakten Definition einer Nachricht geht man vom Begriff des Alphabets aus: Ein Alphabet besteht aus einer abzählbaren Menge von Symbolen (Symbolvorrat) und einer Regel, durch welche eine feste Anordnung der Symbole definiert ist. Üblicherweise betrachtet man nur Alphabete mit einem endlichen Symbolvorrat. Daraus lassen sich einige Definitionen ableiten:

Symbol:	Element eines Symbol- oder Zeichenvorrates. Dieser Vorrat ist eine festgelegte endliche Menge von verschiedenen Symbolen (Elemente der Menge). Der Unterschied zwischen Symbol und Zeichen ist recht subtil: Ein Symbol ist ein Zeichen mit bestimmter Bedeutung. Oft macht man den Unterschied nicht und spricht von "Zeichen" bzw. "Zeichenvorrat" oder "Zeichenmenge". Beispiel: X
Alphabet:	Eine geordnete abzählbare Menge von Symbolen. Beispiel: A, B, C, D, E, F, ..., X, Y, Z
Wort:	Folge von "zusammengehörigen" Zeichen, die in einem bestimmten Zusammenhang als Einheit betrachtet werden. Beispiel: DONALD
Nachricht:	Zusammenstellung von Symbolen (Zeichen) zur Informationsübermittlung. Beispiel: DONALD SUCHT DAISY

Eine Nachricht ist eine aus den Symbolen eines Alphabets gebildete Symbolfolge. Diese Folge muss nicht endlich sein, aber abzählbar (d. h. man muss die einzelnen Symbole durch Abbildung auf die natürlichen Zahlen durchnummerieren können), damit die Identifizierbarkeit der Zeichen sichergestellt ist.

Die Menge aller Nachrichten, die mit den Zeichen eines Alphabets A gebildet werden können, heißt Nachrichtenraum N(A) über A. Bisweilen schränkt man den betrachteten Nachrichtenraum auf Symbolfolgen mit einer maximalen Länge s ein; in diesem Fall umfasst der eingeschränkte Nachrichtenraum A^s nur endlich viele Elemente, sofern das zu Grunde liegende Alphabet endlich ist.

Nachrichten sind somit konkrete, wenn auch idealisiert immaterielle Objekte, die von einem Sender zu einem Empfänger übertragen werden können. Häufig wird eine Nachricht nicht in ihrer ursprünglichen Form, sondern durch Signale physikalisch dargestellt, z. B. Schallwellen, elektromagnetische Wellen, Ströme, Spannungen, Licht, etc. Siehe später.

Informationsgehalt einer Nachricht

Beispiel: Bei welcher Nachricht ist die Information größer?

1. Am 1. Juli war die Temperatur größer als 25 Grad.
2. Am 1. Juli betrug die Temperatur 29 Grad.

Bei a) gibt es nur zwei Möglichkeiten (kleiner/größer 25 Grad), bei b) sind theoretisch beliebig viele Möglichkeiten gegeben. Also ist bei b) die Information größer. Daraus folgt, dass Information mit der Zahl der Möglichkeiten zu tun hat.

Beispiel: Wie komme ich zu meiner Freundin?

• Einfacher Weg: Sie wohnt in derselben Straße. Es gibt nur eine Entscheidung (nach rechts oder nach links gehen).
  
• Komplizierter Weg: Es gibt mehrere Abzweigungen; bei jeder Gabelung muß entschieden werden, ob man rechts oder links geht.

Der Informationsgehalt einer Nachricht ist also feststellbar und wird durch die Anzahl der (rechts-links) Entscheidungen bestimmt und wird in "bit" gemessen. 1 bit entspricht dabei einer Entscheidung:

Einfacher Weg:	Information 1 bit
Komplizierter Weg:	2 Weggabelungen 4 Möglichkeiten, 2 bit 3 Weggabelungen 8 Möglichkeiten, 3 bit 4 Weggabelungen 16 Möglichkeiten, 4 bit usw.

1 bit ist die Datenmenge, die mit der Antwort auf eine Ja-Nein-Frage (Elementarentscheidung) übertragen wird. In diesem Fall besteht das verwendete Alphabet auch nur aus zwei Symbolen (z. B. ja - nein, wahr - falsch, 0 - 1).

Besteht die Nachricht aus N = 2ⁿ Symbolen, so werden n bit übertragen. Man könnte dies als n aufeinanderfolgende Antworten auf jeweils eine Ja-Nein-Frage auffassen.

Jedes Astende (Blatt) entspricht dann einem Zeichen, also ergeben sich 2³ = 8 Symbole bzw. Zeichen, die hiermit übertragen werden können. Allgemein gilt:

Zur Übertragung von N Symbolen benötigt man H = ld(N) bit.

Anmerkung:
ld = logarithmus dualis: y = 2ⁿ n = ld(y)
Umrechnung: ld z = lg(z)/lg(2) = ln(z)/ln(2) (Basis beliebig)

Mit einem Binärzeichen wird nur dann 1 bit übertragen, wenn die beiden Zeichen des Zeichenvorrats gleichwahrscheinlich sind. In allen anderen Fällen wird weniger als 1 bit übertragen. Damit kommt die Auftretenswahrscheinlichkeit von Zeichen innerhalb einer Nachricht ins Spiel. Zum Beispiel bei den folgenden Nachrichten:

1. Am 1. Januar war die Temperatur größer als 25 Grad.
2. Am 1. Juli war die Temperatur größer als 25 Grad.

Die von Claude Shannon maßgeblich entwickelte Informationstheorie beschäftigt sich mit der mathematischen Beschreibung des statistischen Informationsgehalts I(x) eines Zeichens oder Wortes x, das in einer Nachricht mit der Auftrittswahrscheinlichkeit p(x) vorkommt:

1. Je seltener ein bestimmtes Zeichen x auftritt, d. h. je kleiner p(x) ist, desto größer ist der Informationsgehalt dieses Zeichens. I(x) muss demnach zu einer von 1/p(x) abhängigen Funktion proportional sein und streng monoton wachsen.
2. Die Gesamtinformation einer Zeichenfolge, z. B. x₁x₂x₃ soll sich aus der Summe der Einzelinformationen ergeben, also
   I(x₁x₂x₃) = I(x₁) + I(x₂) + I(x₃).
3. Für den Informationsgehalt eines mit Sicherheit auftretenden Zeichens x, also für den Fall p(x)=1, soll I(x)=0 gelten.

Die Basis 2 des Logarithmus bestimmt lediglich den Maßstab, mit dem man Informationen messen möchte. Zur Festlegung dieses Maßstabes geht man von dem einfachsten denkbaren Fall einer Nachricht aus, die nur aus einer Folge der beiden Zeichen 0 und 1 besteht, wobei die beiden Zeichen mit der gleichen Wahrscheinlichkeit p₀ = p₁ = 0,5 auftreten sollen. Dem Informationsgehalt eines solchen Zeichens wird nun der Zahlenwert 1 bit zugeordnet. Man erhält für den statistischen Informationsgehalt eines mit Wahrscheinlichkeit p(x) auftretenden Zeichens x den Zweierlogarithmus aus der reziproken Auftrittswahrscheinlichkeit. Die Basis des Logarithmus wird auch als "Entscheidungsgrad" bezeichnet; man kann sie als die Anzahl der Zustände interpretieren, die in der Nachrichtenquelle angenommen werden können. Im Falle des Zweierlogarithmus sind das nur zwei Zustände ("ja" und "nein").

Damit ist geklärt, wie viele Entscheidungen (oder binäre Fragestellungen) notwendig sind, um eine bestimmte Nachricht aus einer Vielzahl von Nachrichten auszuwählen. Eine elementare Entscheidung besteht aus zwei Möglichkeiten: "ja" oder "nein". Wenn die Informationsquelle n Nachrichten liefern kann, dann sind mindestens N = ld(n) (ggf. auf die nächst größere ganze Zahl aufgerundet) elementare Fragen (Entscheidungen) notwendig, um die Information einer dieser Nachrichten zu ermitteln. Daraus folgt, dass sich mit N elementaren Fragen (Bits) eine spezielle Nachricht aus einer Menge von n verschiedenen Nachricht aussondern lässt. Diese Größe nennt man den Entscheidungsgehalt H₀ dieser Informationsquelle, genauer: H₀(n) = ld(n) [bit]

Informationsgehalt und Entropie

Als Maß für den Informationsgehalt einer Nachricht kann somit eine Funktion der Wahrscheinlichkeit für die richtige Voraussage herangezogen werden. Wenn also p(N) die Wahrscheinlichkeit dafür ist, dass die Nachricht (Information) N eintrifft, dann ist I(N) = ld(1/p(N)) = -ld(p(N)) als ihr Informationsgehalt definiert.

Frage: Passt das mit den anfänglichen Überlegungen zusammen, z. B. bei drei Weggabelungen?

Antwort: Ja! Bei n gleich wahrscheinlichen Möglichkeiten gilt p = 1/n. Die Information ist dann ld(1/p) = ld(1/(1/n)) = ld(n).

Es gilt:

1. I(N) ist umso kleiner, je größer p(N) ist, also je eher man Nachricht N erwartet.
2. Erhält man zwei Nachrichten N₁ und N₂, deren Eintreffen statistisch unabhängig ist, addiert sich ihr Informationsgehalt:

   I(N₁ und N₂) =
   - ld(P(N₁ und N₂)) =
   - ld(P(N₁) × P(N₂)) =
   - (ld(P(N₁)) + ld(P(N₂)) =
   I(N₁) + I(N₂)

3. Wenn man auf eine elementare Frage mit gleicher Wahrscheinlichkeit die Antwort "ja" oder "nein" erhält, dann ist der Informationsgehalt dieser Antwort gleich dem Entscheidungsgehalt der Frage. Denn p(ja) + p(nein) = 1 und p(ja) = p(nein) bedeutet, dass p(ja) = p(nein) = 0,5 ist. Also gilt I(x) = -ld(0,5) = 1 = H₀(2).

Interessant ist nun der Informationsgehalt einer Nachricht. Gegeben sei eine Informationsquelle Q = (N₁,p₁; ..., N_n,p_n), deren Nachrichten N_i die Wahrscheinlichkeiten p_i, i = 1, ..., n haben. Den mittleren Informationsgehalt der Informationsquelle nennt man ihre Entropie H (Eta). Sie ist definiert als:

Dabei gilt:
n = Gesamtzahl der Nachrichten
p_i = Wahrscheinlichkeit für das Auftreten der Nachricht i

Dabei ist vorausgesetzt, dass p₁ + p₂ + ... + p_n = 1 gilt, d. h. die Quelle liefert uns überhaupt eine Information. Die Entropie ist maximal, wenn alle eintreffenden Nachrichten gleich wahrscheinlich sind, wenn also die größte Unsicherheit darüber besteht, welche Information wir von der Quelle erhalten werden. Die Entropie ist genau dann maximal, wenn für alle i gilt: p_i = 1/n.

Die Entropie einer binären Informationsquelle ist 0, wenn eines der beiden Bits mit Sicherheit erwartet werden kann. Sie ist maximal, wenn beide Bits gleich wahrscheinlich sind: Hmax = ld(2) = 1.

Kommen wir auf das Beispiel mit den Weggabelungen zurück. Sind die beiden Alternativen nicht gleich wahrscheinlich, kommen wir um etwas Rechnerei nicht herum. Wenn beispielsweise die Freundin in der Stadt wohnt, dann können wir festlegen:

1. Feldweg kommt nur selten vor p_a = 0,1
2. Teerstraße ist häufiger p_b = 0,9

Es gilt also:

1. Feldweg:     ld(1/p_a) = ld(10) = 3,320 bit
2. Teerstraße: ld(1/p_b) = ld(90) = 0,152 bit

Wie groß ist der mittlere Informationsgehalt? 10% der Antworten lauten "Feldweg" mit I_a = 3,320 bit und 90% der Antworten lauten "Teerstraße" mit I_b = 0,152 bit. Nachdem das Auftreten beider Alternativen nicht gleich wahrscheinlich ist, muss der Informationsgehalt mit den jeweiligen Wahrscheinlichkeiten gewichtet werden:

p_a*I_a + p_b*I_b = p_a*ld(1/p_a) + p_b*ld(1/p_b) = 0,469.

Damit haben wir den mittleren Informationsgehalt, die Entropie, ermittelt. Mit der Entropie einher geht die Redundanz R. Für eine Informationsquelle der Größe n gilt R = |H(n) – H₀(n)|. R ist um so geringer, je größer der zu erwartende Informationsgehalt der Nachrichten ist. Das Minimum liegt offensichtlich bei H(n) = H₀(n), also bei Gleichverteilung.

Beispiel: Das neu eröffnete Eheanbahnungsinstitut "Liebesglück" verteilt Fragebogen an heiratslustige Herren mit drei Fragen, die durch Ankreuzen zu beantworten sind:

(1) Haarfarbe:	blond 0, braun 1	[0] [1]
(2) Augenfarbe:	blau 0, grün 1	[0] [1]
(3) Figur:	kräftig 0, zierlich 1	[0] [1]

Frage: Ist jede Wahlmöglichkeit gleich wahrscheinlich, erhält man wie viele Wahlmöglichkeiten und welchen Informationsgehalt?

Nach Eingang der ersten Fragebögen stellen sich jedoch folgende Vorlieben der Kunden heraus:

80% blonde Haare	20% braune Haare
50% blaue Augen	50% grüne Augen
90% kräftig	10% zierlich

Frage: Wie groß ist jetzt die Information bei

1. braunen Haaren?
2. blauen Augen?
3. kräftige Figur?

Fragen:
Wie groß ist der mittlere Informationsgehalt auf jedem Fragebogen?
Wie groß ist die Redundanz beim Fragebogen mit den drei Feldern

1. nach Eröffnung des Instituts?
2. nach Eingang der ersten 1000 Fragebögen?

Technische Darstellung von Nachrichten

Analoge (wertkontinuierliche) Signale:

• Kontinuierliche Zuordnung einer physikalischen Größe zum Informationsgehalt einer Nachricht, z. B. Temperatur etntsprechend der Höhe der Quecksilbersäule, Zeiger eine Messinstruments
• meist sehr anschaulich
• es sind beliebige Zwischenwerte darstellbar
• benachbarte Werte sind oft schwer zu unterscheiden

Digitale (wertdiskrete) Signale:
Hier gibt es nur eine endliche Zahl von möglichen Zuständen einer physikalischen Größe (im einfachsten Fall zwei), z. B. Ziffernanzeige eines Messinstruments, Balkenanzeige. Da die meisten physikalischen Größen analog sind, wird oft eine Digitalisierung vorgenommen.

Es erfolgt in der Regel eine Rasterung, eine Abtastung der Werte einer Funktion an bestimmten vorgegebenen Stellen. Der kontinuierliche Verlauf des Funktionsgraphen wird dann durch eine Treppenfunktion oder eine Anzahl von äquidistanten Pulsen angenähert.

Der Übergang von einer kontinuierlichen zu einer digitalen Nachricht erfordert nach der Rasterung noch einen zweiten Diskretisierungs-Schritt, die Quantelung. Man erhält auf diese Weise aus einer beliebigen Nachricht eine digitale Nachricht, die aus einer endlichen Folge von natürlichen Zahlen besteht, die ihrerseits wieder in ein beliebiges Alphabet abgebildet werden können.

Anders als bei der Rasterung ist mit der Quantelung eine irreversible Änderung der ursprünglichen Nachricht verbunden, wobei die Abweichungen umso kleiner sein werden, je mehr Quantisierungsstufen man verwendet. Als Quantisierungsfehler definiert man den Betrag der Differenz zwischen dem exakten Funktionswert f(t) und dem durch die Quantisierung gewonnenen Näherungswert f'(t).

Daher unterscheidet man - wie schon in der Einführung geschildert - zwischen Analogtechnik und Digitaltechnik. In den normalerweise verwendeten Digitalrechnern wird eine Digitaltechnik mit nur zwei möglichen Werten eingesetzt. Diese beiden Signale (meist durch "0" und "1" dargestellt) müssen in irgend einer Form aus dem Signal erkennbar sein. Je nach verwendeter physikalischer Größe ergeben sich oft mehrere eindeutige Möglichkeiten für die "0" oder "1".

Die Information kann in verschiedenen Kenngrößen (Parametern) des Signals enthalten sein. Den Parameter, dessen Wert(e)verlauf die Nachricht darstellt, nennt man Signalparameter oder Informationsparameter. Beispielsweise ist bei einem kontinuierlichen Gleichspannungssignal die Spannung der Signalparameter. Bei einem frequenzmodulierten Wechselspannungssignal (Radiowelle) ist dagegen die Frequenz der Signalparameter.

Aufgaben

1. Wie groß ist die Wahrscheinlichkeit p, mit einem idealen Würfel eine gerade Zahl zu würfeln und wie groß ist der zugehörige Informationsgehalt I?
2. Wie viele Knoten, Kanten und Blätter hat ein vollständiger Entscheidungsbaum der Tiefe 5 und allgemein der Tiefe n?
3. 1. Wie oft muß höchstens gefragt werden (Fragen mit ja/nein-Antwort), um eine Zahl zwischen 1 und 50 zu erfragen?
   2. Ein Korb enthalte 24 gleich schwere Kugeln und eine, die schwerer ist. Wie oft muß man höchstens vergleichend wiegen (Balkenwaage), um die schwerere zu ermitteln? Wie groß ist der Entscheidungsgehalt einer einzelnen vergleichenden Wägung?
   3. Mit drei Wägungen lässt sich die schwerere aus maximal wie vielen Kugeln ermitteln?
4. Gegeben sei das Alphabet A = {x, y, z} mit den folgenden Auftrittswahrscheinlichkeiten:
   p(x) = 0.5, h(x) = 1; p(y) = 0.25, h(y) = 2; p(z) = 0.25, h(z) = 2.

   Wie hoch ist der mittlere Informationsgehalt? Wie hoch ist der gesamte Informationsgehalt?

Zum vorhergehenden Abschnitt

Zum Inhaltsverzeichnis

Zum nächsten Abschnitt

Copyright © FH München, FB 04, Prof. Jürgen Plate

Letzte Aktualisierung: 21. Mar 2008