Index

Informatische Grundlagen der ITG

1. Messen von Datenmengen


Auszugsweise aus: Herrmann/Schmälzle, Daten und Energie, Metzler/Teubner, 1987

Die Datenmenge

Frieda und Gerda planen eine Radtour. Zur Abstimmung, ob sie jeweils mitdürfen, verabreden sie für spät abends ein Zeichen, das sie jeweils von ihrem Fenster aus mit einer Taschenlampe senden:

Ich darf mit!
Ich darf nicht mit!

Dies ist die Antwort auf die Frage: Darfst du mit?
Also "ja" bzw. "nein".
Hierbei wird 1 bit Datenmenge übertragen.

1 bit ist die Datenmenge, die mit der Antwort auf eine Ja-Nein-Frage übertragen wird.
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.

Das Shannonsche Informationsmaß H, oder kurz die Datenmenge, ist definiert als:

Shannon'sche Formel für die Datenmenge Dabei gilt:
N = Gesamtzahl der verwendeten Zeichen
pi = Wahrscheinlichkeit für das Auftreten des Zeichens i
ld = Logarithmus zur Basis 2

Sind alle Symbole gleichwahrscheinlich, vereinfacht sich die Formel zu: Vereinfachte Shannonformel.

Beträgt die Zeichenzahl N = 2n, so werden n bit übertragen. Man könnte dies als n aufeinanderfolgende Antworten auf jeweils eine Ja-Nein-Frage auffassen.

Dreistufiger Binärbaum

Entscheidungsbaum für drei aufeinaderfolgende Ja-Nein-Fragen: 3 bit.
Jedes Astende (Blatt) entspricht dann einem Zeichen, also ergeben sich 23 = 8 Zeichen, die hiermit übertragen werden können.

Beispiele

Musik und Datenmenge

Wenn ein Musikstück gespielt und gehört wird, werden Daten übertragen. Der Spieler mit dem Instrument ist die Quelle, der Hörer der Empfänger.
Wir nehmen an, das Instrument sei ein Xylophon mit 15 Tönen. Es sollen nur Viertelnoten angeschlagen werden, wobei eine Viertelpause auch als Ton zählt. Werden alle Töne mit gleicher Wahrscheinlichkeit angeschlagen, so trägt jeder Ton 4 bit, andernfalls weniger.
Während man Musik hört, hat man eine bestimmte Erwartung darüber, welches wohl der nächste Ton sein wird. Bei einer Melodie, die so anfängt, wie es Bild 1 zeigt, erwartet man vielleicht, dass der nächste Ton ein cl ist. Es ist unwahrscheinlich, dass z. B. ein f1 oder ein h1 folgt.


Bild 1 Welches ist der nächste Ton?

Man kann nun feststellen, dass man ein Musikstück als unschön empfindet,
a) wenn die Erwartung zu oft enttäuscht wird
b) wenn die Erwartung zu oft erfüllt wird.

Wenn die Melodie nie so weitergeht wie man es erwartet, erscheint sie uns als chaotisch, oder "unverständlich". Dieser Fall liegt vor, wenn jeder Ton gleichwahrscheinlich ist, wenn also die Töne die maximale Bitzahl tragen.
Geht dagegen die Tonfolge sehr oft so weiter wie man erwartet, so empfindet man sie als langweilig. In diesem Fall bekommt man mit jedem neuen Ton wenig bit, man kann ihn ja leicht im Voraus erraten.

Wir haben damit eine Regel für das Komponieren gefunden: Die Datenmenge darf nicht zu groß und nicht zu klein sein. Das Wesentliche der Kunst des Komponierens ist damit allerdings noch nicht erfasst.
Die historische Entwicklung der Musik verlief übrigens so, dass die Datenmenge ständig zugenommen hat. Das erklärt, warum man die jeweils moderne Musik stets als schwerer verständlich empfunden hat, als die alte.

Datenreduktion

Computer Eine Datenverarbeitungsanlage nimmt Daten auf und gibt Daten ab. Ist ein Computer nur ein Codierer, d.h. die Daten am Eingang enthalten dieselbe Information wie am Ausgang, nur anders verschlüsselt? Wäre das der Fall, so müsste die Datenmenge der aufgenommenen Daten genauso groß sein wie die der abgegebenen. Wir wollen untersuchen, ob das zutrifft. Wir betrachten zu diesem Zweck ein einfaches Beispiel.

1) Ein Computer sei so programmiert, dass er den Mittelwert von Zahlen berechnen kann. Der Einfachheit halber nehmen wir an, dass die einzugebenden Zahlen ganze Zahlen sind, und dass der Mittelwert ohne Stellen hinter dem Komma berechnet wird. Wir lassen den Computer den Notenmittelwert eines Tests berechnen. Wir nehmen an, die Klasse habe 30 Schüler und bei dem Test seien maximal 15 Punkte zu erreichen gewesen. In den Computer werden also 30 Zahlen eingetippt, von denen jede einen der 16 verschiedenen Werte von 0 bis 15 annehmen kann. Da 16 = 24 ist, bekommt der Computer mit jeder Zahl 4 bit, zusammen also 30×4 bit = 120 bit. Man startet nun das Programm, und der Computer gibt kurz darauf den Mittelwert aus: eine einzige der Zahlen von 0 bis 15. Die Datenmenge am Ausgang beträgt damit nur 4 bit. Der Computer hat also die Datenmenge vermindert oder "reduziert".

Die Behauptung, der Computer reduziere die Datenmenge, könnte aus zwei Gründen auf Zweifel stoßen:
Am Ausgang des Computers erscheinen Daten, die der Benutzer noch nicht kennt, die ihn sozusagen klüger machen. Also, könnte man schließen, hat der Computer Daten erzeugt.
Es gibt eine ganze Reihe von Aktivitäten, bei denen "mehr Daten" aus dem Computer herauskommen, als man eingegeben hat. Wenn man die Zahl p berechnen lässt, gibt man ein relativ kurzes Programm ein, und der Computer liefert Ziffern ohne Ende. Oder man gibt ein Programm zur Berechnung von Primzahlen ein, und der Computer hört nicht mehr auf, immer neue Primzahlen zu liefern.

Jedem dieser beiden Einwände liegt ein Fehlschluss zu Grunde. Der erste oben zitierte Einwand beruht darauf, dass das Nichtwissen einer Person als Maß der Datenmenge betrachtet wird. Es ist durchaus legitim, die Datenmenge als ein Maß für die Unsicherheit aufzufassen, die der Empfänger darüber hat, welches Zeichen er als nächstes empfangen wird.
Wir nehmen nun an, der Computer berechne die Summe S aus zwei Zahlen A und B, und wir wenden unser "Messverfahren" auf die Datenmengenwerte HA , HB und HS an. Sieht man in der Person wirklich nicht mehr als ein Messinstrument, so muss man davon ausgehen, dass der Person weder der Wert von S , noch der von A und von B bekannt ist. Nun ist aber die Unsicherheit, die die Person über S hat, kleiner als die, die sie über A und B zusammen hat, denn man kann ein und dieselbe Summe durch verschiedene Kombinationen von zwei Summanden erhalten.
Dass man sich bei der Beurteilung von Datenmengen so leicht täuscht, mag daran liegen, dass man gern davon ausgeht, die Werte von A und B seien bekannt; über diese Werte bestehe also gar keine Unsicherheit, und nur der Wert der Summe sei noch unbekannt. Zu dem vermeintlichen Problem kommt es also nur deshalb, weil das "Messinstrument" falsch eingesetzt wird.

Nun zu dem zweiten oben zitierten Einwand. Wenn man etwa ein Programm vor sich hat, das Primzahlen berechnet, so ist man geneigt anzunehmen, jede Primzahl trage eine bestimmte Datenmenge, und mit jeder neu hinzukommenden Primzahl vergrößere sich die insgesamt vom Computer gelieferte Datenmenge. Auch hier liegt ein Fehlschluss vor. Bei gegebenem Programm liefert der Computer eine vollständig determinierte Zahlenfolge, und diese Folge kann als ein einziges Zeichen mit der Wahrscheinlichkeit eins aufgefasst werden. Die Datenmenge beträgt also sowohl am Eingang als auch am Ausgang 0 bit.

Wir führen nun die Datenbilanz für einige typische Beispiele durch. Vorher sei noch einmal betont, dass man, um überhaupt eine Datenmenge berechnen zu können, eine Präparationsvorschrift angeben muss, in unserem Falle also eine Vorschrift, die angibt, wie der Computer zu präparieren ist. Dabei muss man darauf achten, dass aus der Vorschrift sowohl die Eingangs- als auch die Ausgangsdatenmenge folgt. Keinesfalls darf man für Ein- und Ausgangsdaten verschiedene Vorschriften ansetzen

2) Datenreduktion findet bereits in den Elementarbausteinen von Computern statt. Wir betrachten als Beispiel ein NAND-Glied. Die Wahrscheinlichkeiten für das Auftreten der Zeichen 0 und 1 an den Eingängen E1 und E2 seien:
Wahrscheinlichkeiten an den Eingängen.
Die Angabe dieser Wahrscheinlichkeiten ist der Angabe einer Präparationsvorschrift äquivalent.

Eingang 1: 0 1 0 1
Eingang 2: 0 0 1 1
Ausgang: 1 1 1 0

Aus der Verknüpfungstafel, ergibt sich für die Wahrscheinlichkeit der 0 und der 1 am Ausgang des NAND-Gliedes:
Wahrscheinlichkeit der 0 am Ausgang Wahrscheinlichkeit der 1 am Ausgang.
Die Datenmenge pro Zeichen an jedem der beiden Eingänge ergibt sich zu
H an jedem Eingang.
Für beide Eingänge zusammen erhält man also
H an beiden Eingängen.
Für den Ausgang liefert die Shannonsche Formel
H am Ausgang.

3) Man programmiere den Computer so, dass er die Zahl p auf neun Stellen hinter dem Komma berechnet. Dies ist eine Präparationsvorschrift. Wir nehmen zunächst an, dass durch diese Vorschrift ein ganz bestimmtes Programm definiert werde. Das bedeutet aber, dass die Datenmenge am Eingang des Computers null ist, denn die Anwendung derselben Präparationsvorschrift hat immer wieder dieselbe Zeichenfolge am Eingang des Computers zur Folge. Dasselbe gilt auch für den Ausgang. Bei jeder Wiederholung der Prozedur liefert der Rechner dasselbe Ergebnis. Die Wahrscheinlichkeit dafür, dass am Ausgang die Zahl 3,141592654 erscheint, ist gleich eins, und folglich hat die Datenmenge den Wert null. Tatsächlich wird nun aber durch die Präparationsvorschrift das Programm gar nicht eindeutig festgelegt, denn es gibt verschiedene Methoden, p zu berechnen. Man muss also eigentlich annehmen, dass am Eingang mehrere verschiedene Zeichenfolgen auftreten, so dass die Datenmenge am Eingang größer als null ist. Jedes der möglichen Programme liefert aber am Ausgang dieselbe Zahl. Die Datenmenge am Ausgang hat also auch in diesem Fall den Wert null.

4) Man programmiere den Computer so, dass er eine Zahl durch eine andere dividiert und das Ergebnis auf zehn Stellen hinter dem Komma genau angibt. Man dividiere beliebige, maximal dreistellige natürliche Zahlen durcheinander.
Um die Datenmenge am Eingang zu berechnen, fassen wir jedes geordnete Zahlenpaar am Eingang als ein Zeichen auf. Da es 1000 dreistellige natürliche Zahlen gibt, gibt es 106 solcher Zahlenpaare. Das Wort "beliebig" in der Präparationsvorschrift interpretieren wir so, dass wir die Wahrscheinlichkeiten dieser Zahlenpaare als untereinander gleich ansetzen. Die Datenmenge am Eingang wird also
H einer Division.
Den genauen Wert von HA wollen wir nicht bestimmen. Man sieht aber leicht, dass sich weniger als 20 bit ergeben muss. Zu jedem der gleichwahrscheinlichen Wertepaare am Eingang gehört ein Wert, d. h. ein Zeichen am Ausgang. Nun ist aber erstens die Zahl der verschiedenen zehnstelligen Zahlen am Ausgang kleiner als 106, denn viele der möglichen Divisionen ergeben dasselbe Resultat (z. B. 800/400 = 798/399 = 10/5 = ... = 2,0000000000). Darüber hinaus sind die verschiedenen Ergebnisse nicht mehr gleichverteilt. Beides führt dazu, dass die Datenmenge kleiner ist als am Eingang.

[Index]


Autor: Jürgen Dehmer
Letzte Änderung: 26. Oktober 2001