Shannon Entropie

Herkunft / Verwendung: Der Entropie-Wert nach Shannon liefert einen Wert für die Informationsdichte einer binären Nachricht und lässt so darauf schließen, ob eine Datei verschlüsselt oder komprimiert ist. Für textuelle Nachrichten ist der Koinzidenzindex besser geeignet.

Der Begriff Entropie in der Informationstheorie wurde 1948 von Claude E. Shannon geprägt. Er ist ein Maß für den mittleren Informationsgehalt einer Nachricht. Der Minimalwert Null steht für keine Zufälligkeit, während der Maximalwert für totale Zufälligkeit steht. Ein Standardtext in deutsch oder englisch sollte sich bei 3,5 bis 5 bewegen. Komprimierte oder stark verschlüsselte Daten sollten bei über 6,5 liegen. Die Entropie wird üblicherweise mit einem großen Eta (Η) abgekürzt.

1948 veröffentlichte Shannon seine fundamentale Arbeit A Mathematical Theory of Communication und prägte damit die moderne Informationstheorie. In diesem Werk geht es um die Übertragung von Daten, dessen Störung von außen und die Rekonstruktion von Datenfragmenten, die durch Störungen verloren gegangen sind.

Er ersann einen Algorithmus, um den mittleren Informationsgehalt einer Nachricht zu messen und prägte damit den Begriff der Entropie in der Informationstheorie, den er aus der Physik (eine thermodynamische Zustandgröße in Joule per Kelvin) übernahm.

Den mittleren Informationsgehalt bzw. die Informationsdichte zu kennen war für die elektronische Übertragung wichtig, den je höher die Dichte ist, desto schwieriger lassen sich verlorene Zeichen wiederherstellen und desto schwieriger ist es, die Daten zu komprimieren.

In einem gewöhnlichen Text ist die Informationsdichte nicht so hoch (Entropiewert von etwa 3,5 bis 5) und einzelne fehlende Zeichen lassen sich aufgrund ihrer Nachbarn und Wortbedeutung wiederherstellen. Der geschriebenen Sprache ist insofern eine "Checksumme" durch Grammatik eingebaut.

Aber bei einem zufälligen binären Schlüssel (z. B. zur Verwendung bei einem One-Time-Pad) ist die Informationsdichte sehr hoch (Entropiewert von etwa 6 bis 8) und die Rekonstruktion von verloren gegangenen einzelnen Bits nicht möglich. Darum fügt man moderner Kommunikation Paritätsbits hinzu, mit Hilfe dessen sich die Unversehrheit einer Nachricht feststellen lässt und aus denen sich auf mathematischen Wege einzelne, verloren gegangene Teile wiederherstellen lassen, solange noch genügend unbeschädigte Bits in der Nachricht vorhanden sind. Diese Fehlerkorrektur-Bits finden sich in Modem-Datenübertragungsstandards (z. B. MNP5), QR-Codes, RAM-Bausteinen und anderen binären Daten, ohne dass wir sie auf dem ersten Blick erkennen.

Eine Zeichenkette aus Eintausend gleichen Buchstaben hat einen Entropiewert von Null. Die Nachricht ist das Gegenteil von zufällig und besonders gut packbar, denn man könnte statt 1000 As hintereinander (Speicherverbrauch: 1000 Bytes) auch schreiben : "merke dir: 1000 As" (Speicherverbrauch ~ 10 Bytes).

Den Entropiewert kann man nicht nur dazu verwenden, zu bestimmen, ob und in welchem Umfang man eine Fehlerkorrektur benötigt. Man kann ihn auch dazu verwenden, ein Chiffrat einzuordnen. Dabei ist allerdings zu beachten, dass die Shannon-Entropie für binäre Daten (256 Zuständige pro Zeichen 0...255) geschaffen wurde, nicht fürden begrenzten Raum eines Alphabets (26 Zustände, A...Z). Die Werte werden für textuelle Chiffrate also eher keine so signifikanten Unterscheid aufweisen wie für binäre Daten. Für textuelle Daten ist der Koinzidenzindex besser geeignet.
  • Ist die Entropie eher niedrig (um 4) handelt es sich wohl um einen Text, bei dem nur eine Transposition oder monoalphabetische Substitution zum Einsatz kam

  • Ist die Entropie dagegen eher hoch (um 4.5) handelt es sich wohl um einen Text, bei dem eine polyalphabetische Substitution zum Einsatz kam

  • Ist die Entropie für eine binäre Datei hoch (über 6,5), kann man davon ausgehen, dass die Datei verschlüsselt oder gepackt ist.
Auch hat die Länge der Nachricht einen Einfluss auf den Algorithmus. Längere Nachrichten liefern aussagekräftigere Werte.

Beschreibung des Verfahrens

Claude Elwood Shannon definierte die Entropie H einer diskreten, gedächtnislosen Quelle (diskreten Zufallsvariable) X über einem endlichen, aus Zeichen bestehenden Alphabet Z={z1, z2, z3, ...} wie folgt: Zunächst ordnet man jeder Wahrscheinlichkeit p eines Ereignisses seinen Informationsgehalt I(z)= - log 2} pz zu. Dann ist die Entropie eines Zeichens definiert als der Erwartungswert des Informationsgehalts.



Beispiele

aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa aaaaa Entropie (Shannon) = 0 Dies ist ein gewöhnlicher deutscher Text, mit Groß- und Kleinschreibung, Satzzeichen und Umlauten. Entropie (Shannon) = 3,963 And this is a simple english text without much sense but with a lot of letters and some words. Entropie (Shannon) = 3,969 KDZfg fiOTY JSRcf hbITO DacGa dDAYi PPiEN gKfMZ GZgcF dJiFJ HPaBG HOeaL MjDQW PAhig AZejL ddEhj dKeQO CeIBf EMAjb bKPYI (100 zufällige Buchstabe A-Z|a-z) Entropie (Shannon) = 4,269 3B26EE53 23F63A6D 1817D894 1A88C60D B107C2D6 551B0EF0 4B3CAC18 91AE9BD4 E42C969D CCFCE374 C11D80DF C38F2B57 5A526A21 FE22B7F7 F3425462 39B4FFDA 8C333FA4 0478BBE2 56829E56 BD9D35E0 2581327A 6285F419 C8DFD69E 2BBA8E13 57DE7AA (100 zufällige Binärzeichen, hex-kodiert) Entropie (Shannon) = 6,624 2B6462A4 396898A1 10A8FAB6 5BDAF2D5 A84DBFDE FD6B39FF BBD5E173 85A3F716 A1EF61AA 6FBF2D25 BB7741A7 EFB8AAEF C6BB6F4C FB7DBC38 1EBC7FB9 6AB5F7BF D713838F 2A0360C0 F272EACD FBCE0D58 4038C1AF 17B819B0 03F68A0A 41CED2D5 4EAFDDB6 EBBE9B13 3936CEFB D1FBE2F0 5AFCCB38 44824DFD B7CE8670 452D74C0 3FA4EF81 F86DEF1B BEAF308D 2D6F87A6 759FC305 894F8D52 FA9A16A9 249FCD36 BF29D278 5E708044 7838E14B FF8D5EB7 2318E0E3 27E0DF8D FF593AD8 5E4B9D17 0280CCC9 36DADA34 3E25F348 EABA96FF CEC2C542 FF36FA7B FFC7D7A6 FFB79DFF AA0812DF 476438C1 9DC26BCD EEDB1CC0 F1A6E7D9 679B67C7 287A315F 809B3B8B 6F505B67 C37AAD91 4EE05FE0 AEF7F7BB 202060F0 1CE7B1F5 9F47D91A B5B676DB 8020B248 0D8DB4B6 567B3C7C (300 Bytes aus einer Zip-komprimierten Datei) Entropie (Shannon) = 7,185 513ADFFA 4B012BBA D9ACE2BB 56AE85D6 B790E20B 42E27440 E7BB61C1 AC46B397 4227D8A1 58F847D1 47448F86 19ACE546 BBC16856 C0C8A1B1 0E346D44 3CEB0AD8 BD44092B 83825DAC 7C2657C2 BB69F338 611624D7 BDDDA912 E0C70079 53C2541D 9F161D75 70221C20 F0AB35D0 59D8ECEC 1A77F499 16287F2A 34842495 914293F3 FAE5D46B 6EC37BC7 57477E50 7D8147D9 50BCD241 BB6F522C 0AF2A567 6D44ED8B 6285448C 5E7FABDE B822C4F4 3F373828 0194B38A C9CADB15 0315EEB8 D4E43CF7 5C6BC0ED 5BD5FD9F F86DE865 58BC02ED B6751053 341B4778 E2EEBE22 C08AC79D A3FAF60F 0B8C4BCB 0FA9CE44 1460EC66 D090B44A 60C74A63 6202353D ED4AECB6 18B0A1B4 D2AB2A0A 5145A1F4 C6040601 0A4945CB 8F034051 453383E2 DF84F958 20B9E958 3741CB08 891BFFFC 386B4B8B (304 Bytes aus einer AES-128bit-CBC-Verschlüsselung) Entropie (Shannon) = 7,234 4CFFFAA8 FBD45FE8 092FBD20 68B55CBF 63744F50 93316D1B D1576C2A 41AEC4B9 5E018FAC BEFA95AF 962F1C69 A3C0473B 057EE14B EE93A397 ABADB807 47FB8F05 3CEE7769 B2F209EA A06108C4 3F489AC8 1B0D910D 9A1CEDB7 8FADE4A8 44BE7582 A0388793 27082032 0CBF33A6 AD22126B 75D1A16D 7C093B90 848DA507 24E121A3 E844F043 8F243141 6070F123 8FC1233A 34B484E6 6E093F8C A96F7E13 3DF513A2 2180678A 55F6F8B4 E88BA3B1 E885F772 201F8D07 F8BD2890 59F8681B 153F639C 9A666347 D7C3C7A1 50EB8FA4 C713A5BA FFF04C32 907ADFF8 C6379A3F FEE33F2E D7D55547 499B6E81 A3BA8AE4 C936A4E8 A095F77C 2881CCD3 9FFF05D4 F522C550 A869F29E 80BEE873 FA8693E4 204F78F9 86D3366F 7DD2B308 1833BCF7 BE56FD22 7464E47F BF3D526C 77F90461 (300 Bytes aus .png-Grafikdatei (komprimiert)) Entropie (Shannon) = 7,199 FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFF1F1F 1F202020 20202020 20202020 20202020 20202020 20202020 201F1F1F FFFFFFFF FFFFFFFF FFFFFFFF 1F1F1F20 20202020 20202020 20202020 20202020 2020201F 1F1FFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFF1F1F 1F202020 20202020 20202020 20202020 20202020 20202020 201F1F1F FFFFFFFF FFFFFFFF FFFFFFFF 1F1F1F20 20202020 20202020 20202020 20202020 2020201F 1F1FFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFF1F1F 1F202020 20202020 20202020 20202020 20202020 20202020 201F1F1F FFFFFFFF FFFFFFFF FFFFFFFF 1F1F1F20 20202020 20202020 20202020 20202020 2020201F 1F1FFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFF1F1F 1F202020 (300 Bytes aus .bmp-Grafikdatei (unkomprimiert)) Entropie (Shannon) = 1,427 (gruppierte Zeichenfolgen ohne Leerzeichen, diese dienen lediglich der besseren Lesbarkeit)

Code / Chiffre online dekodieren / entschlüsseln bzw. kodieren / verschlüsseln (Decoder / Encoder / Solver-Tool)

Quellen, Literaturverweise und weiterführende Links

Wikipedia-Artikel zur Entropie
Wikipedia-Artikel zur Entropie
Claude E. Shannon: A Mathematical Theory of Communication, 1948