Entropie (Informationstheorie)aus Wikipedia, der freien EnzyklopdieWechseln zu: Navigation, SucheDie Artikel Entropie (Informationstheorie) und Informationsgehalt berschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Die Diskussion ber diese berschneidungen findet hier statt. Bitte uere dich dort, bevor du den Baustein entfernst. Des Messers Schneide 16:13, 18. Jun. 2007 (CEST)

Entropie ist ein Ma fr den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichens, das in einem System oder einer Informationsfolge steckt. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide Begriffe haben Gemeinsamkeiten, deren Erkennen allerdings Kenntnisse in beiden Fachgebieten voraussetzt. Das informationstheoretische Verstndnis des Begriffes Entropie geht auf Claude E. Shannon zurck und existiert seit etwa 1948. In diesem Jahr verffentlichte Shannon seine fundamentale Arbeit A Mathematical Theory of Communication und prgte damit die moderne Informationstheorie.Inhaltsverzeichnis[Verbergen]

1 Definition 2 Interpretation 3 Maximaler Entropiewert und Normierung 4 Beispiel: Alphabet 5 Beispiel: Mnzwurf 6 Beispiel: Idealer Wrfel 7 Entropietests 8 Datenkompression und Entropie 9 Alternative Mglichkeiten der Informationsquantifizierung 10 Literatur

11 Siehe auch 12 Weblinks

Definition [Bearbeiten]Claude Elwood Shannon (1916-2001) definierte die Entropie H(X) einer diskreten gedchtnislosen Quelle (diskreten Zufallsvariable) X ber einem Alphabet einer hchstens abzhlbaren Menge durch mit der Wahrscheinlichkeit

(1)

,

wobei pi = p(zi) = P(X = zi) die Wahrscheinlichkeit ist, mit der das i-te Zeichen zi des Alphabets auftritt. Andere Schreibweise:

Nach der Regel von L'Hospital gilt . Summanden mit verschwindender Wahrscheinlichkeit tragen nicht zur Summe bei. Zur Berechnung der Entropie whlt man beim Logarithmus in der Regel die Basis 2, was zur Folge hat, dass man das Ergebnis auch zur Basis 2 erhlt, was damit in der Einheit der Information (Bit) dargestellt wird. Wrde eine andere Basis gewhlt werden, zum Beispiel 3 so erhielte man ternre Bits (Trits). Anders lsst sich die Entropie auch ber den Informationsgehalt eines Zeichens zi mit der Wahrscheinlichkeit pi ausdrcken

(2)

, wobei der Informationsgehalt I eines Zeichens durch

I(p) = log2(p) mit [I] = bit definiert ist. Der Erwartungswert bietet eine weitere Mglichkeit die Entropie zu definieren:

(3) Die Entropie liefert einen durchschnittlichen Informationsgehalt in Bit pro Zeichen:

Die mindestens notwendige Anzahl von Bits, die zur Darstellung der Information (des Textes) notwendig sind ergibt sich aus dem Produkt des durchschnittlichen Informationsgehalt eines Zeichens H(X) und der Anzahl N verschiedener Zeichen im Informationstext (=Alphabetgre): H(X) | Z | bzw. H(X)N.

Interpretation [Bearbeiten]Entropie ist ein Ma fr den mittleren Informationsgehalt pro Zeichen einer Quelle, die ein System oder eine Informationsfolge darstellt. In der Informationstheorie spricht man bei Information ebenso von einem Ma fr beseitigte Unsicherheit. Je mehr Zeichen im Allgemeinen von einer Quelle empfangen werden, desto mehr Information erhlt man und gleichzeitig sinkt die Unsicherheit ber das, was htte gesendet werden knnen.

Je kleiner die Auftrittswahrscheinlichkeit eines Zeichens ist, desto hher ist seine Information. Andersrum ist die Information eines Zeichens gering, wenn es oft vorkommt.

Anschaulich lsst sich die Definition des Informationsgehalts wie folgt begrnden: Wenn ein Ereignis, das mit Wahrscheinlichkeit pi eintreten kann, tatschlich eintritt, dann wird dadurch ein konkretes

Ereignis aus einer hypothetischen Menge von gleich wahrscheinlichen Ereignissen ausgewhlt. Um diese Anzahl von Ereignissen unterscheiden zu

knnen bentigt man Binrbits. Dieser Wert gibt also den Informationsgehalt eines speziellen Ereignisses in Bits an. Gewichtet man den tatschlichen Informationsgehalt der mglichen Ereignisse mit der jeweiligen Eintrittswahrscheinlichkeit, so erhlt man

den mittleren oder erwarteten Informationsgehalt eines Zeichens. Die Einheit 1 Shannon ist definiert als der Informationsgehalt, der in einer Zufallsentscheidung eines idealen Mnzwurfes enthalten ist. Ein idealer Mnzwurf hat nur zwei Mglichkeiten Kopf oder Zahl , die beide mit der gleichen Wahrscheinlichkeit p = 0,5 auftreten. Shannons ursprngliche Absicht, die Entropie als das Ma der bentigten Bandbreite eines bertragungskanals zu nutzen, wurde schnell verallgemeinert. Die Entropie wurde generell als ein Ma fr den Informationsgehalt betrachtet. Bei einer kleinen Entropie enthlt der Informationstext Redundanzen oder statistische Regelmigkeiten. Die rein statistische Berechnung der informationstheoretischen Entropie nach obiger Formel ist gleichzeitig ihre Beschrnkung. Beispielsweise ist die Wahrscheinlichkeit, eine 0 oder 1 in einer geordneten Zeichenkette 1010101010 zu finden, genauso gro, wie in einer Zeichenkette, die durch statistisch unabhngige Ereignisse (etwa wiederholten Mnzwurf) entstanden ist. Daher ist Shannons Entropie fr beide Zeichenketten identisch, obwohl man intuitiv die erste Kette als weniger zufllig bezeichnen wrde. Eine angemessenere Definition der Entropie einer Zeichenkette liefert die bedingte Entropie und Quellentropie, die beide auf Verbundwahrscheinlichkeiten aufbauen. In engem Zusammenhang zur bedingten Entropie steht auch die Transinformation, die die Strke des statistischen Zusammenhangs zweier Zufallsgren angibt.

Noch einfacher formuliert, ist die Entropie die durchschnittliche Anzahl von Entscheidungen (bits), die bentigt werden, um ein Zeichen aus einer Zeichenmenge zu identifizieren oder zu isolieren. Es ist sinnvoll, dass ein Alphabet aus mindestens zwei verschiedenen Zeichen vorliegt. Eine Alphabetsgre von eins bedeutet, dass man weder ber neue ankommende Zeichen aus der Senderquelle neue Information erhlt, noch die Unsicherheit ber das vorangegangene Zeichen verringern kann.

Maximaler Entropiewert und Normierung [Bearbeiten]Mchte man ein normiertes Ma fr die Entropie einer beliebigen diskreten Verteilung haben, ist es von Vorteil, die maximal mgliche Entropie, die bei Gleichverteilung der pi erreicht wird, zur Normierung heranzuziehen. Sei N = | Z | die Anzahl der Zeichen in X ber dem Alphabet Z, dann ist die maximale Entropie Hmax gegeben durch:

Daraus folgt beispielsweise Hmax = 1 fr eine Binrverteilung (Z = {0,1}), also bentigt man 1 Bit pro Zeichen und | I | Zeichen fr die komplette Information I. Dieser Wert wird erreicht, wenn Nullen und Einsen gleich hufig vorkommen. Normiert man nun die Entropie einer beliebigen Verteilung mit N = | Z | verschiedenen Zeichen mit Hmax erhlt man:

Die so erhaltene Entropie wird immer maximal gleich 1. Um die Entropien von Nachrichten unterschiedlicher Lnge vergleichen zu knnen, hat man die Entropierate eingefhrt, die die Entropie auf das einzelne Zeichen bezieht (siehe dort).

Beispiel: Alphabet [Bearbeiten]Bei gleichmiger Verteilung kann bei einem Alphabet auf kein Zeichen verzichtet werden. Dagegen ist die Buchstabenhufigkeit in der deutschen Sprache ungleichmig. Beispielsweise ist der Buchstabe E sieben Mal hufiger als M oder O, was zu Redundanz im Alphabet fhrt. Nun mchte man herausbekommen, wie gro diese Redundanz ist. Sei N = 26 die Gre des Alphabets. Die Redundanz R berechnet sich mit R = H(X)max - H(X). Fr das deutsche Alphabet errechnet man anhand der Buchstabenhufigkeit eine Entropie H(X) von 4,0629 bit/Zeichen. Die maximale Entropie betrgt Hmax(X) = log2|26| = 4,7004 bit/Zeichen. Damit folgt eine Redundanz von R = 4,7004 - 4,0629 = 0,6375 bit/Zeichen. Berechnet man weiter die gesamte Redundanz, die sich aus der Summe der Redundanzen eines jeden Zeichens ergibt, so erhlt man RN = 16,575 Bits. Nun wre interessant zu wissen, wie

viele Zeichen dies aus unserem Alphabet entspricht. Dividiert man die redundanten Bits durch den durchschnittlichen Informationsgehalt eines gleichverteilten Zeichens, so erhlt man (RN)/Hmax(X) = 3,53 Zeichen => 3 Zeichen (ohne Redundanzen). Rechnet man allerdings (RN)/H(X) = 4,08 (=> 4 Zeichen), so bestimmt man die Anzahl von Zeichen mit einer Redundanz, wie sie auch im Alphabet vorhanden ist. Ohne Informationsverlust knnte das Alphabet also um vier Buchstaben reduziert werden. Diese berlegung bercksichtigt nur die statistische Verteilung der Buchstaben. Hufige Buchstabenkombinationen wie SCH oder ST bleiben genauso unbercksichtigt (bedingte Entropie) wie gleich klingende Buchstaben (Q, K).

Beispiel: Mnzwurf [Bearbeiten]

Maximale Entropie bei p=0.5

Bei einem Mnzwurf sind idealerweise Kopf oder Zahl gleich wahrscheinlich. Wenn man die Entropie als Ma fr die Ungewissheit auffasst, wird sie hier einen maximalen Wert aufweisen. Es ist vllig ungewiss, ob beim nchsten Wurf Kopf oder aber Zahl geworfen wird. Sei X eine diskrete Zufallsvariable und der Erwartungswert E[X]= P(X=xi)xi mit P(X=x0) = p0 = p = (Kopf) und P(X=x1) = p1 = q= (Zahl) ergibt sich aus obiger Definition (1) Entropie H(X) = 1 bit. Anders bei einer gezinkten Mnze, etwa einer Mnze, die im Mittel in 60 % der Flle Kopf und nur in 40 % der Flle Zahl anzeigt. Die Ungewissheit ist hier geringer als bei der normalen Mnze, da man eine gewisse Prferenz fr Kopf hat. Gemessen als Entropie liegt die Ungewissheit bei nur noch etwa 0,971. Die Summe der Wahrscheinlichkeiten ist immer 1. p+q=1 Die Entropie lsst sich in diesem Fall mit folgender Formel berechnen:

Ersetzt man q durch den Ausdruck 1 p, so erhlt man die Formel

Dies kann man grafisch folgendermaen darstellen:

Fr jedes p kann man daraus die Entropie direkt ablesen. Die Funktion ist symmetrisch zur Geraden p = 0,5. Sie fllt bei p = 0 steil zu einem Entropie-Wert von 0 ab. Auch bei Werten, die sich dem sicheren Ereignis von p = 1 nhern, fllt die Entropie auf 0 ab. Dieser Zusammenhang gilt jeweils fr ein Zufallsereignis. Bei mehreren Zufallsereignissen muss man die einzelnen Entropien zusammenzhlen und man kann so leicht Entropiewerte ber 1 erreichen. Die Wahrscheinlichkeit p dagegen bleibt auch bei Wiederholungen definitionsgem immer zwischen 0 und 1.

Entropie in Abhngigkeit von der Zahl der Mnzwrfe

Wiederholt man den Mnzwurf zweimal, wchst die Zahl der Mglichkeiten auf vier. Die Wahrscheinlichkeit jeder einzelnen Mglichkeit liegt bei 0,25. Die Entropie des zweimaligen Mnzwurfes ist dann 2 Sh. Wenn man einen idealen Mnzwurf mehrfach wiederholt, dann addiert sich die Entropie einfach. Die Entropie einer Reihe von 20 idealen Mnzwrfen berechnet sich einfach: . Dies ist im Bild dargestellt. Man kann nicht einfach aus einem Wert der Wahrscheinlichkeit die Entropie ausrechnen. Die Entropie betrifft den gesamten Zufallsprozess. Jede Teilwahrscheinlichkeit eines mglichen Ergebnisses geht in die Berechnung der Entropie des Gesamtprozesses ein. Die Angabe einer Teilentropie fr jedes mgliche Ergebnis ist dabei wenig sinnvoll. In der Shannonschen Entropieformel sollte also die Summe der Wahrscheinlichkeiten 1

ergeben, sonst kann das Ergebnis missverstndlich sein. Speichert man eine Folge von Mnzwrfen als Bitfolge, dann bietet es sich an, Kopf stets durch 0 und Zahl stets durch 1 zu reprsentieren (oder umgekehrt). Bei der gezinkten Mnze sind kompaktere Kodierungen mglich. Diese erhlt man beispielsweise durch den Huffman-Kode.

Beispiel: Idealer Wrfel [Bearbeiten]Bei einem Wurf eines idealen Wrfels mit sechs Mglichkeiten ist die Entropie grer als 1. Im Allgemeinen ist die Entropie grer als 1 fr ein Zufallsereignis mit stochastisch unabhngigen Zufallsvariablen aus einem Zufallsexperiment mit mehr als zwei gleichberechtigten Mglichkeiten im Ergebnisraum. Ihr Wert wird bei gleichwahrscheinlichen Mglichkeiten im Ergebnisraum folgendermaen berechnet: Anzahl der Mglichkeiten: N, damit ergibt sich fr die

Wahrscheinlichkeiten und fr die Entropie

. Beim idealen Wrfel sind sechs Mglichkeiten im Ergebnisraum. Daraus folgt die Entropie fr einmaliges Werfen:

Entropie vs. Zahl der Mglichkeiten

Einfach zu berechnen ist die Entropie eines Wurfes eines idealen Achterwrfels: Er hat acht gleichberechtigte Mglichkeiten.

Die Entropie eines Wurfes mit dem idealen Achterwrfel entspricht der Entropie von drei Wrfen mit der idealen Mnze. Die Abbildung stellt den Zusammenhang zwischen der Entropie und der Zahl der gleichberechtigten Mglichkeiten eines Zufallsexperimente s dar.

Entropietest s [Bearbeiten]Um zu testen, wie gut Daten komprimierbar sind, oder um Zufallszahlen zu testen, werden Entropietests verwendet. Als Zufallszahltest wird die Entropie einer bestimmen Anzahl von Zufallszahlen bestimmt und ab

einem Mindestwert, beispielsweise 7 Bit je Byte, gilt er als bestanden. Allerdings gibt es viele solcher Tests, da die Entropie nicht eindeutig ist; sie kann beispielsweise bitbasiert oder bytebasiert definiert sein. Ein einfaches Beispiel: Eine Quelle, etwa ein Spielwrfel oder eine Mnze, gebe nur die Werte 0xAA (dezimal 170) und 0x55 (dezimal 85) aus, beide mit gleicher Wahrscheinlichkeit. Bitweise ist die Ausgabe zu 50 % 0 oder 1, byteweise ist sie zu 50 % 0xAA oder 0xFF. Die bitweise Entropie ist (mit log = ln)

whrend die byteweise Entropie mit

deutlich kleiner ist. Der Hersteller dieses Zufallszahlengener ators wird natrlich als Entropie des Gerts die bitweise Entropie, also 1, angeben. Analog wird ein Programmierer eines Kompressionsprog ramms mglichst diejenige Basis whlen, bei der die Entropie minimal ist (hier Bytes), sich also die Daten am besten komprimieren lassen. Dieses Beispiel ist wenig realistisch, da nur zwei von 256 mglichen Werten verwendet werden, aber wenn auch die anderen Bytes mit einer

kleinen Wahrscheinlichkeit von beispielsweise 1/123456789 ausgegeben werden, so ndert dies an der bitweisen Entropie nichts und die byteweise wird kaum grer; sie bleibt unter 1/2. Erst mit Annherung der ByteWahrscheinlichkeit en an 1/256 erreicht die byteweise Entropie den Wert 1, aber dann kann es noch Korrelationen der Bytes geben, also etwa die Folge 0xaaaa viel hufiger sein als die Folge 0x5555. Dies ist der Hauptgrund, weshalb es viele verschiedene Zufallszahlentests gibt. Diese Mehrdeutigkeit ist

nicht mglich beim Entropiebelag, da dort nicht nur ber Wahrscheinlichkeit en summiert wird, sondern ber ergodische Wahrscheinlichkeit en von Zustnden, Zustandsbergang swahrscheinlichkeit en und bedingte Wahrscheinlichkeit en. Berechnet wird er mit der Theorie der Markov-Kette. Allerdings ist der Rechenaufwand dafr bei realen Zufallszahlengener atoren hoch.

Datenkompr ession und Entropie[Bearbeiten]

Die Entropiekodierung ist ein Kompressionsalgor ithmus, um Daten verlustfrei zu komprimieren. In diesem Zusammenhang

spielen die Kreuzentropie sowie die KullbackLeibler-Divergenz als Ma fr die durch eine schlechte Kodierung ausgelsten Verschwendungen von Bits eine Rolle. Beispiel: Gegeben sei die Zeichenkette ABBCAADA (siehe auch Entropiekodieru ng). Die BuchstabenWahrscheinlich keit: pA = 4 / 8 = 0,5; pB = 0,25; pC = pD = 0,125

Maximalentropi e (pA = pB = pC = pD = 0,25):

Die Maximalentropi

e lsst sie ebenso mit der Formel der maximalen Entropie berechnen:

Alternative Mglichkeite n der Informations quantifizieru ng [Bearbeiten]Ein anderer Zugang, den Informationsgehalt einer Nachricht zu messen, ist durch die KolmogorowKomplexitt gegeben, worin der krzestmgliche Algorithmus zur Darstellung einer gegebenen Zeichenkette die Komplexitt der Nachricht angibt. hnlich ist die Logische Tiefe definiert, die sich aber auf die

Laufzeit oder Zeitkomplexitt eines Algorithmus zur Erzeugung der Daten bezieht. Gregory Chaitin ist ebenfalls ber die Shannonsche Definition der Entropie einer Information hinausgegangen (siehe Algorithmische Informationstheorie ).

Literatur[Bearbeiten]

Johanneson, Rolf: Informationsthe orie, AddisonWesley 1992, ISBN 3893194657 Claude Elwood Shannon und Warren Weaver: The Mathematical Theory of Communication , University of Illinois Press

1963, ISBN 0252725484 (Softcover) und ISBN 0252725468 (Hardcover) Norbert Bischof: Struktur und Bedeutung, 1998, ISBN 3456830807 (Das Buch ist fr Sozialwissensc haftler geschrieben und erklrt mathematische Zusammenhn ge NichtMathematikern in sehr verstndlicher Weise. Das Kapitel 2 widmet sich der Informationsthe orie.) Sven P. Thoms: Ursprung des Lebens. Frankfurt: Fischer 2005 ISBN 3-59616128-2 (Das

Buch ist aus biologischer und chemischer Perspektive geschrieben. Ein Kapitel behandelt den Zusammenhan g von Leben und Entropie.) Cover, Thomas: Elements of Information Theory, WileyInterscience 2006, ISBN 0471241954 (Das Buch ist nur auf Englisch erhltlich. Es behandelt ausfhrlich die Informationsthe orie und ist mathematisch gehalten.) Martin Werner: Information und Codierung,View eg 2002 ISBN 3-528-03951-5

Siehe auch[Bearbeiten]

Kolmogorov-Entropie, Kolmogorov-Sinai-Entropie, Maximum-EntropieMethode, Metrische Entropie, Nat, Ornstein Theorem, Redundanz, Topologische Entropie, Markow-Kette, Rnyi-Entropie, Tsallis-Entropie, Theil-Entropie, Negentropie, Entropiekodierung1. 1.

Entropie

Weblinks[Bearbeiten] Wikibooks: Entropie Lernund Lehrmaterialien

1.

http://www.madeasy.de/2/zufallgz.htm

1. Einfhrung der Entropie als Gesamtzufallsmenge mit vielen Beispielen und hilfreichen Erklrungen zur Formel von Shannon. http://www.techfak.unikiel.de/matwis/amat/mw1_ge/kap_5/advanced/t5_3_2.html2.

1.3. 1.

Entropie und Information, gut erklrt http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html (englisch) Shannons Originalarbeit: A Mathematical Theory of Communication Von http://de.wikipedia. org/wiki/Entropie_ %28Informationsth eorie%29 Kategorien: Wikipedia:Redund anz Juni 2007 | Kybernetik | Theoretische Informatik | InformationstheorieAnsichten

1. 2. 3.

Artikel Diskussion Seite bearbeiten

4.

Versionen/Autoren Persnliche Werkzeuge 1. Anmelden Navigation

1. 2. 3. 4. 5. 1. 2. 3. 4.

Hauptseite ber Wikipedia Themenportale Von A bis Z Zuflliger Artikel Mitmachen Hilfe Autorenportal Letzte nderungen Spenden SucheTop of Form

Artikel

VolltextBottom of Form

Werkzeuge1. 2. 3. 4. 5. 6. 7. 1. 2. 3. 4. 5. 6.

Links auf diese Seite nderungen an verlinkten Seiten Hochladen Spezialseiten Druckversion Permanentlink Seite zitieren Andere Sprachen English Espaol Franais

Magyar

7. 8. 9. 10. 11. 12. 13. 14. 15. 16.

Italiano Nederlands Polski Simple English Svenska Ting Vit

1.

Diese Seite wurde zuletzt am 15. November 2007 um 15:05 Uhr gendert.2.

Ihr Text steht unter der GNU-Lizenz fr freie Dokumentation.3. 4. 5.

Wikipedia ist eine eingetragene Marke der Wikimedia Foundation Inc. Datenschutz ber Wikipedia Impressum